Talk:Continuation-passing style

Organization and Scope

The material beginning "programming with continuations" to the end of that section seems outside the scope of this article: it is about using continuations as a program control flow mechanism, within a program written largely in direct style, rather than about CPS per-se. I would suggest that this material be moved to its own page, possibly fleshed out, and that a pointer be made from this page saying something like "continuations are useful in less formal contexts, for instance as ways of passing and manipulating control in a GUI system. This is called Programming with Continuations. Any thoughts or objections? Barak (talk) 12:49, 25 January 2008 (UTC)

Need an example of how to call

For people not as familiar with continuations, like me, it might be good to include an example of how to call at least one of the scheme CPS examples.

For instance, I pasted the factorial example into my scheme interpreter, but I have no idea how to call it so that it prints out 120 as the answer. ( factorial 5 ??? ) what do I type for the ??? ?

I added an example about the identity function. But I think the CPS style examples (pyth, factorial) are wrong, because they dont't work. --SteloKim (talk) 06:05, 3 January 2008 (UTC)

I don't find this a very good example. Instead I will add an example of calling the CPS version of factorial, showing how to interface between code in direct style and code in CPS. This will also remove the call/cc, which is premature at that point in the article. However it would be nice to add a section on call/cc in Scheme, or perhaps better a separate article on call/cc and a pointer to it. Barak (talk) 23:50, 14 January 2008 (UTC)

The pyth CPS example isn't valid scheme, in that is will error when run. A continuation must be applied at some point for it to be run. I will update the pyth with a contrived example, say where pyth gives a non-whole number and you pass in a continuation for dealing with that case. Ozten (talk) 00:41, 24 January 2008 (UTC)

Added a verbose re-write of pyth example. Examples of CPS tend to be more verbos... pyth isn't a problem where CPS technique would shine, so I invented a requirement where you could pass in a continuation for dealing with weird error situation such as the pythagorean number being a real number instead of a whole number. Using the examples from "Scheme the Programming Language" would be better, but I guess copyright issues would prevent that. Added this book to references... Ozten (talk) 01:08, 24 January 2008 (UTC)

I backed out this change to the pyth example because it was wrong: it was no longer in CPS. There is a specific technical definition of CPS, and this did not fulfill it. Eg, it called + without a continuation, and called it in a nested fashion. (feel free to email me if you want to discuss.) Barak (talk) 09:04, 25 January 2008 (UTC)

Examples of compilers that use CPS internally

As continuation passing style renders return values virtually useless, it can also be used to eliminate the need for a runtime stack. Several compilers and interpreters for functional programming languages use this ability internally in novel ways.

Can anyone fill this in a bit with examples of specific compilers and/or interpreters that make use of CPS, and which novel ways they do so in? Ari 08:20, 26 December 2005 (UTC)

• I believe SML/NJ uses CPS internally. It did, at least, in the mid nineties. As I recall, this also makes the implementation of CML thread much more efficient. I'll see if I can dig out some references... Brighterorange 18:25, 26 December 2005 (UTC)
• yeah

CPS is a monad?

The article says "CPS is a monad." Can someone please make this clearer with "CPS is a monad because..." or something like that. Toby 21:48, 20 March 2006 (UTC)

Ok, I found a paper explaing how it is a monad (or rather how continuations are monads). I'll add it on the "monads in functional programming" page and clarify / correct this sentance when I get back from work later on.--NotQuiteEXPComplete 00:05, 3 August 2006 (UTC)

On second though I'll remove this comment since the statement that "CPS is a monad" is wrong. Continuations are monads, but saying this in an article on CPS doesn't make much sense. --NotQuiteEXPComplete 12:52, 3 August 2006 (UTC)

CPS as GOTO

Think about that for a moment. This certainally smells like a goto chain.

• Yes, it is much like GOTO, except that a call to a continuation can transfer control non-locally. — brighterorange (talk) 18:53, 25 September 2006 (UTC)
• Continuations are the functional equivalent of the GOTO statement in imperative languages. Same risk - functional spaghetti-code. Phraine 07:58, 26 December 2006 (UTC)
  • I think they're also rather similar to how higher level languages implement functions in assembler, i.e. by pushing a return value to stack so the function knows where to return when it's done. Eudoxie (talk) 08:19, 4 October 2011 (UTC)

The return address is already in the top stack frame. What TCO does, is instead of pushing a new frame onto the stack, with the new where-to-return address, it just changes this address inside the frame already in the stack, at its top. It might also change the value of some parameters (if the tail call has arguments) passed in the call frame normally, thus reusing the top frame. The call stack not growing, is the key feature (and the goal) of TCO.

But CPS is a programming technique, and TCO is implementational technique. To call a thunk (function without parameters) is to jump into its head. The name of a function is the pointer into its code, conceptually. CPS makes the what-to-do-next choice explicit. It is there, in the source code, in a form of a thunk situated in the tail call position (i.e. last call made by a function).

Without TCO it would indeed get pushed onto the run-time call stack and that would grow too, in addition to a possibly growing continuation being built bit by bit by the program, so there better be TCO employed at run-time. The growing continuation is thus an explication of the run-time structure that would grow on the run-time stack in the usual programming model during a program's execution. That's why in translations of tail-recursive functions the size of the continuation being built isn't growing, and in translations of non-tail recursive functions it does. WillNess (talk) 07:25, 6 October 2011 (UTC)

Example code

I was looking for an example of CPS-transformation, found none and did it myself. If anyone is interested, here it is ("cps" takes target "k" as second argument):

(defun cps-progn-rec (l k)
  (let ((sym (gensym)))
    (if l
	`(lambda (,sym) ,(cps (car l) (cps-progn-rec (cdr l) k)))
	k)))

(defun cps-progn (l k)
  (if (consp l)
      (caddr (cps-progn-rec l k))
      (cps nil k)))      

(defun cps (expr k)
  (cond
    ((atom expr) `(,k ,expr))  
    ((eql (first expr) 'quote) `(,k ,expr))
    ((eql (first expr) 'lambda)
     `(lambda ,(second expr) ,(cps-progn (cddr expr) k)))
    ((eql (first expr) 'if)
      (let ((test (gensym)))
	(cps (second expr)
	     `(lambda (,test)
		(if ,test
		    ,(cps (third expr) k)
		    ,(cps (fourth expr) k))))))
     (t
      (let* ((args (rest expr))
	     (syms (mapcar (lambda (x) (if (atom x) x (gensym))) args))
	     (result `(,(first expr) ,@syms ,k)))
	(loop
	   as sym in (reverse syms)
	   as arg in (reverse args)
	   do (if (not (atom arg))
		  (setf result (cps arg `(lambda (,sym) ,result)))))
	result))))

C'ya, folks! —Preceding unsigned comment added by 85.140.198.80 (talk) 05:55, 28 October 2009 (UTC)

Rather Hard to Understand

It says (in the "Use and implementation" section):

     Without first-class functions, techniques such as trampolining of 
     thunk closures can be used; in this case, it is possible to convert 
     tail calls into gotos in a loop, eliminating even the need for TCO.

If you follow the links to "trampolining" "thunk" "closure" they each have many definitions. This statement is written so generally that it's very hard to understand. Is this implementing a lazy language in a lowlevel language? can an example be mustered up? a citation? —Preceding unsigned comment added by 99.63.209.53 (talk) 04:41, 10 March 2010 (UTC)

This (the original quotation I mean) actually makes no sense at all since thunk closures are first-class functions par excellence. I think "first class functions" should be replaced with "tail calls optimization" here, as trampolining is about dealing with function calls when you have no (tail-call optimized) function call mechanism in an underlying language, AFAIUI - which would be like, in pseudocode, loop { nextcall = nextcall(); }, where nextcall in Lisp would be a thunk-returning function, but in C, say, could be a function pointer (or functions could be despensed with altogether with explicit jumps as in { LB1: jump lb; }) and any code section jumped into, uniformly ending with { set lb nextcall; jump LB1; } ... right?). I'll go ahead and change it in the article. WillNess (talk) 21:05, 14 March 2011 (UTC)

No mention of Plotkin?

Are you serious???

I'm not an expert in the history of CPS, but I've always been under the impression that it started with Gordon Plotkin's "Call-by-name, call-by-value and the λ-calculus", and I find it rather odd that the history section only mentions the Scheme memo. —Preceding unsigned comment added by 93.123.21.116 (talk) 07:24, 15 April 2010 (UTC)

Not sufficiently serious!

There may be two different notions called `continuations' -- I'm no expert in history either. Christopher Stratchey and Christopher P. Wadsworth, as I recollect, introduced/used the notion in 1974 to provide denotational semantics for `goto'. It could not be described adequately in direct denotational semantics. Plotkin refers to their work in the article mentioned above, and the qualification `continuation style' was used to indicate this kind of denotational semantics. Informally the notion meant `the rest of the computation' and no corresponding, explicit argument was required. Oldfux (talk) 19:15, 13 December 2015 (UTC)

References

A-normal form and eager evaluation

This line seems curious:

“Functional compilers can also use A-normal form (ANF) (but only for languages requiring eager evaluation)”

AFAIK, there is no necessary connection between ANF and eager evaluation. ANF simply arises as the normal form under administrative reductions performed on the equivalent CPS terms; the fact that it's usually the call-by-value CPS transform that's used isn't really the point.

(Alternatively, GHC has in the past been said to use ANF, though only in the very broad sense of “function arguments are atomic”; I'm pedantic enough to say that's not really ANF.)

I wouldn't dispute that ANF is usually only used for eager languages, but the claim is about suitability.

Luke Maurer (talk) 04:56, 5 October 2016 (UTC)