This and this (follow the embedded SN-monad link) are the two most comprehensible descriptions of monads I've yet read, and I think part of the reason for that is that, since they're both in Scheme, you avoid Haskell's confusing (to the uninitiated) type-related syntax—also the first one explicitly notes that he has, mercifully, omitted the math.
Moderately relatedly I had the following thought. Suppose you have a recursively defined function, kind of like the fibonacci series, thus: f(0) = 1, f(1) = 1, f(n) = f(n-1) + 2*f(n-2). Then you could describe the recurrence relation postfixwise thus: n 1 - f 2 n 2 - f * + [it just occurred to me the way this is written presupposes that with binary operations first you pop the right operand and then the left operand, and I have no idea if that's the way it's usually done, but oh well]. Then it seems that there's a more or less straightforward way to read a continuation-passing style version of the computation from the postfix description, if you imagine that the syntax is arg1 arg2 … argn op cont. Go along, pushing the values until you reach an n-ary operation, pop n values, and instead of pushing the result, pass it to the continuation (obvs. values passed as arguments to continuations will have to count as being on the stack): then you get: n 1 - (\x -> x f (\x' -> n 2 - (\x'' -> x'' f (\x''' -> 2 x''' * (\x'''' -> x' x'''' + k))))). Moving the functions to the front and replacing the '+' , '*', '-' with CPS analogues kp, kt, km (for plus, times, minus) gets you something that actually works:
f 0 k = k 1
f 1 k = k 1
f n k = km n 1 (\nm1 -> f nm1 (\fn1 -> km n 2 (\nm2 -> f nm2 (\fn2 -> kt 2 fn2 (\fn22 -> kp fn1 fn22 k)))))
This occurred to me because you always see in talk about CPS the remark that it turns "expressions "inside-out" because the innermost parts of the expression must be evaluated first" (presumably the article means written first, because of course the innermost parts have to be evaluated first)—but that's also the case with postfix notation. This leads me to conjecture that Forth programmers and HP calculator users find CPS natural.
Comments