3 ms·
Return statements and "early exit" are not built into functional languages. If the language, like Scheme, supports continuations, we can use callCC to implement
by tikhonj 11y ago
Return statements and "early exit" are not built into functional languages. If the language, like Scheme, supports continuations, we can use callCC to implement an early return[1]:
(define (example x)
(call/cc (lambda (return)
(when (< x 0) (return #f))
; more code, including possible more calls to return
0)))
However, most functional languages do not have callCC built in. Happily we can get a similar effect by writing our code in continuation-passing style (CPS)[2]. (Think Node.js.)
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-short-circuit-return 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-functional-programming/answer/Tikhon-Jelvis?share=1 https://www.quora.com/What-is-continuation-passing-style-in-...
- ridiculous_fish 11y agoIs 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.
- tikhonj 11y agoRight, 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.