Saturday, December 29, 2007

Dunce Cap Removal

OK, I have something to admit. I realized the other day that I totally misunderstood how variable bindings in Haskell do blocks propagated to later statements in the block. Once I realized this and saw how wrong I had been it was sort of like taking off a dunce cap that I didn't know I was wearing. I guess it was a good thing that I never went shooting my mouth off about this subject else my dunce cap would have become visible to everybody else as well.

To be a bit more explicit about what I was so wrong about consider this bit of Haskell code:

   do
    x <- someAction
    y <- someOtherAction
    putStrLn $ show $ x + y

How does the last line access the x binding? For some reason I had concocted this crazy complicated mechanism where the compiler was creating ever longer tuples containing all the variables bound in the do block and then automatically extracting the proper element from the tuple in each statement that a variable was used in. It was really hand-wavey and looking back on it I guess I was being a bit lazy. Had I really sat down and worked out how this ever-growing tuple thing worked I would have seen how clunky it was and probably noticed the dunce cap a lot sooner.

Then the other day I decided to manually de-sugar a do block in some code that I was working on. Doing the same to the above results in

 someAction >>= 
        (\x -> someOtherAction >>= 
        (\y -> putStrLn $ show $ x + y))

It was at this point I realized how big of an idiot I had been. The compiler doesn't need to start creating tuples of ever-growing length. In the putStrLn expression y is passed in so it is obviously available. But notice that the lambda expression containing putStrLn is defined within another lambda expression that x is passed into. x is part of the putStrLn lambda's environment and thus is accessible. So instead of building bigger and bigger tuples as we go further into the do block the compiler is instead nesting more and more lambda expressions. Since the previous lines in a do block become lambda expressions containing the current expression any parameters they take are available in the inner lambda expressions.

So now my dunce cap is off. Maybe if I had exposed it to someone earlier they would have disabused me of my misunderstanding earlier. Maybe they would have just pointed and laughed or let me go on thinking the way that I was, sort of an intellectual kick-me sign. At least getting rid of this dunce cap means that I am learning. Though now I'm left wondering how many more dunce caps I'm wearing that I don't know about.