UpToEleven.ca

A couple weeks ago I ordered the three “Schemer” books - The Little Schemer, The Seasoned Schemer and The Reasoned Schemer - from Amazon and have been working my way through the first one in my spare time. The books have a “dialog” sort of style to them that’s different than what you’ll find in most programming books, but so far Scheme is making a lot more sense than it did in second year university.

I breezed through the first several chapters without much trouble. I’ve already got a pretty good handle on recursion, though practicing it in Scheme gives you a different way to think about it than in something like C#. Even Currying - another topic I never really picked up on in university - was something I found was doing in my own code without actually calling it that. I was feeling pretty smart until the second half of the chapter entitled “Lambda the Ultimate” when suddenly continuations showed up and my head just about exploded.

In Continuation-passing style:

Instead of “returning” values as in the more familiar direct style, a function … takes an explicit continuation argument which is meant to receive the result of the computation performed within the function.

So instead of the “normal” function (+ x y), the CPS equivalent would be something like (cps+ x y k) where k is a function being passed in. The first version adds x and y and then returns the result, while the second adds x and y and then passes the value into the function k. I think.

Here’s a function for the Pythagorean theorem in “normal” Scheme:

and here’s the same function using “continuation-passing style”:

Last night that second version meant absolutely nothing to me, though now having stared at it long enough to come up with this post, I think I’m starting to catch on. I’m still not clear on where using CPS is a clear “win”, but my brain hurts less now.

I think next up is the Y-Combinator. That could hurt some more.