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