I was told this is incorrect CPS:
let subk (a,b) k = k (a - b);;
let plus100 x = x + 100;;
Printf.printf "%i \n" (subk (7,5) plus100);;
but not this:
let subk (a, b) k = k (a - b);;
let plus100k x k = addk (x, 100) k;;
subk (7, 5) (fun d -> plus100k d (fun sum -> Printf.printf "%i \n" sum));;
why?
Okay, I’ll try my luck at explaining.
The latter is not incorrect CPS (great use of nested negation btw) because the idea of CPS is that the flow of the program continues to the continuation aka the parameter k. In your not latter program, the result is being returned directly up the callstack, whereas in your latter program with the inner print the result of the computation is being passed to the continuation which in turn prints the result.
If I removed the print statement of my first example would it be now in CPS? e.g.
(subk (7,5) plus100);;
Not really. Basically, in the CPS style, you chain your computations via continuations, e.g., once the first computation is ready, it passes its result to the continuation which in turn passes it to the next and so on. At some point of time you need to add this chain, i.e., there should be the final function that instead of passing the result next, shall stop the chain and return it directly.
I think it would be just easier to understand this using a concrete example. Consider the following non-tail-recursive and non-CPS (but classical) map function
let rec map f = function
| [] -> []
| x :: xs -> f x :: map f xs
And now let’s turn it into a tail-recursive function using CPS,
let rec mapk f xs k = match xs with
| [] -> k []
| x :: xs -> mapk f xs (fun xs -> k (f x :: xs))
When we apply it, e.g.,
mapk Char.uppercase ['h'; 'e'; 'l'; 'l'; 'o'];;
- : (Base.Char.t list -> '_a) -> '_a
we get a continuation as a result, which we don’t want to chain anymore since we want to get the result, to run the continuation, i.e., to finally materialize the result, therefore we pass an identity function that will receive the answer and just return it right away, e.g.,
mapk Char.uppercase ['h'; 'e'; 'l'; 'l'; 'o'] (fun x -> x);;
- : char list = ['H'; 'E'; 'L'; 'L'; 'O']
Of course, yours plus100 could be used instead of the identity function here (provided that we use a list of integers).
[N.B. It’s been 25 years since I learned this technique (from Olivier Danvy), and I’m sure there’s been progress. But it was crystal-clear at the time, and, well, I’ve never found anything better for more-or-less mechanically generating the CPS of a program while avoiding all the administrative redexes. I would be remiss if I didn’t mention Felleisen & Sabry’s work – they came up with A-normal form, which is what the result of step (2) is below. But Olivier is the one who made it child’s play to apply (to me, at least).]
Here’s maybe a different way of thinking of what CPS form is, to complement what Leonidas@ and ivg@ wrote. In CPS, any function-application (including primitive functions like - and printf) must not have arguments that are themselves function-applications. Their arguments must always be variables or constants (b/c those are values).
I’ve always found Olivier Danvy’s three-step CPS transformation to be useful, b/c so simple. So starting with
let sub (a,b) = a - b ;;
let plus100 x = x + 100 ;;
Printf.printf "%i \n" (plus100 (sub (7,5))) ;;
His method says (1) use lets for all embedded function-applications:
let b = plus100 (sub (7,5)) in
Printf.printf "%i \n" b;;
let b =
let a = sub (7,5) in
plus100 a in
Printf.printf "%i \n" b;;
At this point, any function-application MUST have arguments that are values (constants or variables).
Then (2) flatten any nested-trees of lets
let a = sub (7,5) in
let b = plus100 a in
Printf.printf "%i \n" b;;
then (3) introduce continuations at each let) [Danvy makes this clear in his paper, but it’s been 25 years since I saw it, so … I’m just gonna wing it] here’s the CPS-translation of the final expression:
fun k0 =>
sub_cont (7,5) (fun a =>
plus100_cont a (fun b =>
k0 (Printf.printf "%i \n" b)
)) ;;
and here’s the auxiliary functions:
let sub_cont (7,5) k = k (7 - 5);;
let plus100_cont a k = k (a + 100) ;;
To execute the final expression, you just apply it to the empty continuation (fun () => ())
I suppose this is the paper you are referring to.
I could be mistaken, but a quick scan (well, I read a bit of it) doesn’t ring any bells; and the paper that I remember was published much earlier – around 1994 – and was specifically about CPS, A-normal-form, and elision of administrative redexes. Remember, back then there was that open problem of how to efficiently generate CPS sans administrative redexes, and also the open problem of the “better solutions to dataflow analysis problems via CPS” ? Felleisen and Sabry solved both those problems with A-normal-form. And what Olivier did, was to demonstrate a straightforward, easy-to-remember, easy-to-apply, bone-head-simple technique, for effecting CPS.
Chances are it’s this one:
Interesting read, thanks!
I think that we moved away from the topic a bit. Not that it is bad, but let’s not confuse the CPS Programming and CPS Intermediate representation. The latter is used in compilers and is a representation which simplifies data relations and makes certain optimizations much easier. The idea that was inspired by CPS programming technique, which was used in different dialects of Lisp for many years before that. The compilation techniques had evolved since that time, and CPS IR was mostly superseded by ANF representation (see the CPS/ANF Saga for the brief summary).
And although it is an interesting topic on itself, it is more about writing a compiler, so it is rather a nice topic, unlike the CPS programming style which is a powerful technique that is practical and is used to (a non-exhaustive list):
The essence of CPS programming, is that a function accepts one or more functions as arguments and use them to return values back to the caller. For example, this is a CPS style parser, which takes two continuations, digit and error and use one or another
let parse_digit input ~digit ~error = match input with
| '0'..'9' -> digit (Int.of_char input)
| _ -> error input
Note, that in the example above we could use an ADT, but using continuations here saved us an allocation.
A recurring pattern in the CPS style is when a function has only one continuation, e.g.,
let computation args k =
let result = <do-some-computation> args in
k result
The type of such function is 'args -> ('a -> 'r) -> 'r. And it immediately hits us on an abstraction opportunity, as we can see that we have a computation parameterized with the type ('a -> 'r) -> 'r, which gives a rise to the Continuation Monad. Using the Continuation Monad it is very easy to chain computations without blowing your mind. This monad makes it easy to treat values of type 'a cont = ('a -> 'r) -> 'r as first-class routines which could be stored in data structures, resumed, scheduled, etc. So that we can implement lightweight threads, generators, resumptions, and other interesting techniques.
Going back to the CPS style map.
let rec mapk f xs k = match xs with
| [] -> k []
| x :: xs -> mapk f xs (fun xs -> k (f x :: xs))
Here we use CPS (or Continuation monad) to turn a non-tail recursive call into tail-recursive. We don’t want to turn into CPS every call, as this would be the same as unnecessary wrapping into monad pure computations, e.g.,
let impure_purity =
return 2 >>= fun x ->
return 3 >>= fun y ->
return (x + y)
This won’t give us any benefits, since our values are pure. Now let’s rewrite mapk using the monadic syntax,
let rec map' f xs = match xs with
| [] -> return []
| x :: xs ->
map' f xs >>= fun xs ->
return (f x :: xs)
Here, it becomes obvious that functions f and (::) are pure, while the map' itself is a computation. \
To summarize, CPS is a very powerful technique for expressing both – non-trivial dynamic behaviors of programs and, when ML-style type inference is present, static properties.
Yep, that’s the one. And as ivg@ says, there’s CPS-programming (writing code in CPS ) and there’s the use of CPS as an IL. And Danvy’s paper is about doing the former – about making it as dead-simple as possible to wriite your code in CPS form.
Surprisingly, but I think that this is the other way around, this paper is about transforming your IR into CPS style, hence the name and the list of keywords 
And honestly, translating all your lambda terms into CPS style doesn’t make any sense in programming, unless you’re trying to obfuscate your code.
The technique is, however, general, so not surprisingly it works even when applied to ML style syntax.
It’s possible that’s the case – that is, that the paper was written from the P.O.V. of an IR implementer. But I’ve only ever used it on ML code, and have used it on that extensively over the years, so I’ve never associated it with IR.
But it’s all good: it’s the best and simplest CPS-form methodology I’ve ever seen.
Oh ha, actually not. Even back in 2001 I used Olivier’s transformation to write a … monadic (I think that’s the term today?) runtime for a web-stress-tester in Ocaml … so I could run many thousands of user-agents, each doing complex click-trail testing. I could have done it using threads, but clearly at some point it’s more efficient to use continuations. And hardware wasn’t as powerful back then.
Today, of course, there are entire towers of libraries and such for Node.JS, Scala, maybe other languages, that help programmers to write monadic code so they can do I/O-concurrency without multi-threading. Heck, that’s Node.JS’ entire raison d’etre, no?
For oft I read stressed encouragement to have it tail-recursive. When I ponder on tail or not-tail recursion I can’t help but see this right hanging tree of calls.
In non-tail form, calls are layed in the call stack (and once up, folded down) whereas in tail form a lambda embeds lazily a computation to do later which results in a lambda-ed construction of the former form. It aledgedly maps and moves stacked calls to heaped calls.
Why is tail recursion sought after in regular style ? Isn’t performance slower with lambda pointers (or ADT) to dereference around ? Do I want this if, say locally, I don’t need CPS style uniformly or at all ?
I wonder a lot on this thing. I learn a functional language because I can write as if the machine was not there. The continuation monad, CPS etc look like abstraction patterns that enable for more. I get this stuff. But why summon terminal position of recursion which appears to be related to machine representation concerns ?
One simple reason people write in tail-recursive style, is in order to avoid stack blowup. The typical implementation of List.map
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
is not tail-recursive and when you apply it to a really long list, you can overflow your stack. So people will keep around tail-recursive versions to avoid this. And sure, this is at the cost of extra heap-allocation.
For sure, tail-recursion has costs, and specifically in heap-allocation. Henry Baker wrote many years ago, about treating the stack as a sort of “nursery,” and an important reason that C++ code can be faster, is stack-allocation of objects.
The idea is, though, that if you are good at writing code in tail-recursive form, then when you need to do it, you can do it effortlessly. And it comes up more often than you might think.
Cheney on the M.T.A.
CONS Should not CONS its Arguments
Or just read everything from http://www.pipeline.com/~hbaker1/, it is worth the read.