Staged Pipelines

In an effort to make the MetaSharp pipelines more powerful I’m about to add the concepts of stages and connectors. I’ve been thinking about it a bit and I drew up some diagrams to help me express how the pattern should work.

At a high level it’s pretty simple, for every pipeline there are multiple stages and for each stage there are multiple steps. Each stage has 1 or many input connectors and 1 or many output connectors, which connects to the next stage of the pipeline.

image

With this in mind there are four possible types of stages, defined by their input and output connectors. Stages must be chained together with matching input and output connections. You want multiple types because there are certain types of operations that are simply not possible to do simultaneously but there are other types that are completely isolated and are perfectly acceptable to run asynchronously.

image

Many to Many

For each type of input a complete inner pipeline of steps is created. Meaning each input value from a previous stage will be processed by the same steps. Each inner pipeline will run asynchronously and should not communicate between each other. The stage will complete when all steps have completed running.

image

1 to 1

This type of stage will accept one input value and produce one output value. It will create exactly one chain of steps and execute synchronously.

image

1 to Many

This type of stage will accept one input value and have exactly one chain of steps but will produce many output values.

image

Many to One

This type of stage will accept many values and run them all through exactly one chain of steps.

image

 

From this I should be able to make any type of compilation pipeline imaginable. For example a typical pipeline might be something like this:

  • Parse files
  • Combine AST
  • Resolve References
  • Generate Assembly

In which case you might end up with the following stages:

  • M:M, Parse files all at once
  • M:1, Combine the ASTs into one tree.
  • 1:1, Resolve and transform the tree.
  • 1:1, Transform into IL

You could also imagine that last step transforming into multiple objects or multiple files or something like that quite easily. Also the good news is that I think this shouldn’t actually be that complicated. The pipeline simply deals with connecting stages and each stage has a very simple strategy for processing the steps. The real work will lie in the implementing the stages but even then each stage is completely modular and singularly focused.

An Alternative to the Building Construction Metaphor for Software Development

I am currently reading “The Pragmatic Programmer” while riding the bus to work in the mornings. It’s pretty good and I read something earlier today that I thought was especially interesting, something I hadn’t thought about before at all and I would like to share it here.

This excerpt is on the subject of refactoring (Chapter 6 pg. 184). He begins by using the standard metaphor of construction of buildings for the process of software development, which I found interesting because I have heard this exact metaphor several times from various software architects. But then he goes on to say:
Well, software doesn’t quite work that way. Rather than construction, software is more like gardening – it is more organic than concrete. You plant many things in a garden according to an initial plan and conditions. Some thrive, others are destined to end up as compost. You may move plantings relative to each other to take advantage of the interplay of light and shadow, wind and rain. Overgrown plants get split or pruned, and colors that clash may get moved to more aesthetically pleasing locations. You pull weeds, and you fertilize plantings that are in need of some extra help. You constantly monitor the health of the garden, and make adjustments (to the soil, the plants, the layout) as needed.
Which is an amazing metaphor, I’ve never been able to quite put my finger one what I didn’t like about the construction metaphor but for lack of anything better I’ve been unable to refute it. The organic metaphor appeals to me much more. There have been a lot of good things in this book but this is the first thing I have read that is a completely new idea to me so I thought I would share it with you.

Appearance in CoDe Magazine

If you haven’t already taken a look at the Nov / Dec 2008 issue of CoDe magazine I would highly recommend it 😉 On my last gig at Magenic I had the pleasure of working for Rocky Lhotka, Sergey Barskiy and Nermin Dibek on CSLA Light. Along the way we managed to crank out an article for CoDe Magazine related to the work we were doing. Here is a link to the article online, Using CSLA .NET for Silverlight to Build Line-of-Business Applications.

I got a copy of this magazine at the last Twin Cities Code Camp and didn’t even know that I was a co-author of one of the articles in it! It wasn’t until the following monday that a coworker of mine pointed out to me that I was in the magazine and he only knew because he recognized my picture. That was pretty funny.

Now that I’m famous if anyone wants me to autograph their copy of CoDe magazine just let me know!

Prisoner’s Dilemma .NET

The prisoner’s dilemma is a classic game of logic that has made its way into the computer science arena in the past. I am presenting Prisoners Dilemma.NET as a general programming challenge based around this game. I will be accepting custom built prisoners and facing them off in a master interrogation competition at the end of this challenge.

The challenge deadline will be May 1st, 2008. All you have to do is to create your prisoners into 1 or more .NET assemblies (v2.0 or greater) and send them to me in a zip file to enter the challenge.
I have created a prisoners dilemma application for you to use as a test bench for prisoner creation. It comes complete with the prisoner’s dilemma core source code for you to review, unit tests and a WPF application to see how your prisoners line up against other prisoners visually. There is a sample project created for you called “CustomPrisoners” with a basic prisoner outlined. All you need to do is implement a few abstract methods to get your prisoner going.
For example, here is the Mafia Hitman source code:
public class MafiaHitman : Prisoner
{
    public override bool Interrogate(string partnerId)
    {
        return false;
    }
 
    public override void Sentence(InterrogationResponse partnerResponse, string partnerId)
    {
    }
 
    public override string Name
    {
        get
        {
            return “Mafia Hitman”;
        }
    }
}
 
Why the Prisoner’s Dilemma?
For a real detailed explanation of the prisoner’s dilemma you should head over to the Wikipedia article for the Prisoner’s Dilemma. If this is too dense for you and you would prefer someone to explain it in simpler terms I recommend hearing Richard Dawkins explanation, from Nice Guys Finish First. It’s lengthy but quite good.
What caused me to put together this challenge, though, was a conversation I had with a colleague regarding the use of torture as a valid means of interrogation. At some point in the discussion I decided to use the Prisoner’s Dilemma as an example to counter one of his arguments. Essentially he was arguing that American’s should be allowed to torture terrorists because they are also torturing American soldiers. So, of course, this discussion gets much more complicated than this but when I brought up the idea that the Prisoner’s Dilemma should illustrate that cooperation is more beneficial than betrayal (or not torturing enemies of America as, at least, a gesture to also not torture American soldiers) he disregarded the study and claimed that it has questionable scientific validity to begin with.
So as someone who values reason I would like to perform a bit of a scientific study to validate or invalidate the theory behind the Prisoner’s Dilemma before we continue with this point of the debate.
Challenge Details
·         You may freely download and run the source code for the Prisoners Dilemma .NET challenge. You may also modify it but this is the code that will run for the challenge.
·         Changes may be made to the PrisonersChallenge.Core code base between now and the challenge deadline. Be sure to check more recent blog posts for notifications of any changes before submitting your entry. Anybody who has already made an entry will be notified of changes if contact information is available.
·         Changes will not be made to the codebase unless major bugs are found or critical security issues are revealed with the present codebase.
·         You must submit only a single .NET library file (dll) per submission. All other file types will be disregarded.
·         All entries must be packaged in a single zip file. So that means 1 dll in 1 zip file is an entry.
·         (optional) You should create an Assembly level attribute in each submitted assembly of the type PrisonersDilemma.Core.PrisonerAuthorAttribute with your name and email address so I can get back to you later with results.
·         The challenge will be run on a VPC with limited memory and no internet access.
·         No code obfuscation allowed.
·         No private reflection allowed.
·         The challenge will be run in a medium trust environment.
·         You may use the Temporary folder for writing files if you so choose.
·         You may package files and 3rd party assemblies as embedded resources in your prisoner assembly if you so choose but your submission must be only a single .NET assembly file.
·         By submitting code to this challenge you give me (Justin Chase) the rights to execute and distribute this source code as I see fit.
·         I reserve the right to deny any entry for any reason.
·         Entries will be denied if they appear to be doing anything malicious to the machine or to the memory of the application.
Challenge Procedure
Each prisoner will iteratively be interrogated against each other Prisoner. What this means is that for each prisoner in the application your prisoner will be put up against that prisoner 100 times. A unique value will identify each prisoner so they can keep track of each interrogation against a specific partner.
Insanity Variation
Given the fact that I’m executing arbitrary, 3rd party code for this challenge I, naturally, needed to cover the situations where a Prisoner throws an exception from within its Interrogate or Sentence methods. Rather than take down the entire application for these scenarios I have decided to eat those exceptions and treat them as if the Prisoner has “plead insanity”. If a prisoner does this then they will receive the maximum sentence.
This has some interesting implications because it expands the previous game states from 2 possible choices to 3, which adds a little variety into the mix. I will draw up a small chart to illustrate the various possibilities.
A / B
Silent
Betray
Plead Insanity
Silent
2, 2
5, 0
2, 5
Betray
0, 5
4, 4
4, 5
Plead Insanity
5, 2
5, 4
5, 5
 
I chose these values by the following logic:
·         This whole theory assumes that both parties are in fact guilty and that the reward comes from not being able to be proven guilty with 100% certainty.
·         If you’ve plead insane then you are known to be 100% guilty.
·         Betraying someone who has pleaded insanity does not benefit the cops at all, you are simply admitting your own guilt.
·         This probably won’t change the game too much since it’s unlikely anyone will ever take the tactic of intentionally pleading insanity.
Recommendations
It’s well known that the “tit for tat” strategy was the winning strategy behind the original Prisoner’s Dilemma challenges. I would love to see some interesting tit-for-tat prisoners appear on the scene but it will only be interesting if we have lots of varied strategies to compare it with. I have included a few basic strategies that aren’t very interesting but I would love to see every possible tactic exhausted for comparison.
Just remember this isn’t a competition! This is a programming challenge intended to be fun and to be a casual scientific experiment so please, create a variety of interesting prisoners.
If you find any bugs in the source code or have any recommendations feel free to email me directly!