Re:Early exit is a tail call optimization of procedural lang...
by ridiculous_fish on Monday December 14, 2015 @03:22PM
(#10733537)
Is it possible to use CPS with functional primitives like map? Or do you have to implement CPS-savvy replacements? It doesn't seem like a CPS transform would let you early-exit from map in tail position.
Re:Early exit is a tail call optimization of procedural lang...
by tikhonj on Monday December 14, 2015 @03:42PM
(#10733689)
Right, you'd need a CPS version of map. Luckily map isn't really a "primitive", it's just a library function, so using a different version of map is not a big deal.
One way to think about it is that languages with callCC built in are just transformed to CPS by the compiler before being run, which includes transforming the definition of map. (In fact, this is a reasonable strategy for compiling Scheme, I believe.)
It's pretty easy in Haskell which wraps CPS into a monad (Cont) because you use mapM from the Control.Monad library instead of having to write a specifically CPSed version of the function.
Nominally, CPS has some overhead because of the extra function calls involved. However, a CPS transform also puts every call in tail position, making them eligible for tail call elimination. This means that we can use CPS with no function call overhead in a language with proper tail calls.
What does this mean in practice? It means that calling a callback in CPS style—which, being in tail position, can be eliminated—is effectively just a jump under the hood. Not too different from return!
Putting it all together, we get that tail call elimination lets us write code in continuation passing style with no extra over head which gives us access to continuations that we can use to implement an early return in languages without return.
This turns out to not be what the article was on about, but I think it's more interesting.
[1]: Code from a StackOverflow answer by Nathan Shively-Sanders which goes into more detail: http://stackoverflow.com/questions/2434294/scheme-early-shor...
[2]: I wrote a brief explanation of CPS on Quora: https://www.quora.com/What-is-continuation-passing-style-in-...