Continuation Passing Style
Gerald Smith
Does anyone know if there are any other uses of CPS other than
creating interpreters/compilers. I am trying to justify the effort
of learning the technique.
I am using the book "Essential of Programming Languages" as my
tutorial.
My main motivation is in trying to "improve" the use of
continuations in Common Lisp. Presently, I am using Paul Graham's
macros.
Marc Wachowitz
Gerald Smith <70363...@CompuServe.COM> wrote:
> Does anyone know if there are any other uses of CPS other than
> creating interpreters/compilers. I am trying to justify the effort
> of learning the technique.
CPS makes the concept of continuations in "ordinary" language constructs
visible, and general continuations can be used to understand and implement
(in Scheme itself, not only in a compiler) sophisticated control constructs.
Advanced Scheme (or Lisp in general) programming often consists basically
of _embedding_ (not merely implementing as separate level) a problem-oriented
sub-language into Scheme, so whatever high-level concepts you know about the
implementation of interpreters and compilers might still be useful. I'd say,
if you're curious about these things, go for it, even if you're not expecting
to ever implement something like a full Scheme compiler.
-- Marc Wachowitz <m...@ipx2.rz.uni-mannheim.de>
Tim Olson
In article <OHyjEnI...@ntawwabp.compuserve.com>, Gerald Smith
<70363...@CompuServe.COM> wrote:
| Does anyone know if there are any other uses of CPS other than
| creating interpreters/compilers. I am trying to justify the effort
| of learning the technique.
CPS certainly isn't limited to creating interpreters and compilers. I've
used it in cases where I was heavily using functions that wanted to return
multiple values (and didn't have a Scheme that handled them). Compare:
----- "normal" version
(define (pop-value list1 list2 final-list)
(cond
((null? list1)
(if (null? list2)
(cons list1 list2 final-list)
(cons list1 (cdr list2) (cons (car list2) final-list)))
((null? list2)
(cons (cdr list1) list2 (cons (car list1) final-list)))
(else
(if (> (car list1) (car list2))
(cons (cdr list1) list2 (cons (car list1) final-list))
(cons list1 (cdr list2) (cons (car list2) final-list))))))
(define (doit v1 v2)
(let ((result (pop-value v1 v2 #()))
(let ((list1 (car result))
(list2 (cadr result))
(final-list (caddr result)))
.
.
----- "cps" version
(define (pop-value list1 list2 final-list cont)
(cond
((null? list1)
(if (null? list2)
(cont list1 list2 final-list)
(cont list1 (cdr list2) (cons (car list2) final-list)))
((null? list2)
(cons (cdr list1) list2 (cons (car list1) final-list)))
(else
(if (> (car list1) (car list2))
(cont (cdr list1) list2 (cons (car list1) final-list))
(cont list1 (cdr list2) (cons (car list2) final-list))))))
(define (doit v1 v2)
(pop-value v1 v2 #()
(lambda (list1 list2 final-list)
.
.
-----
In the CPS version we let lambda take care of binding the multiple values,
rather than having to explicitly do it by building up and immediately
tearing down a list.
--
-- Tim Olson
Rob Warnock
Gerald Smith <70363...@CompuServe.COM> wrote:
+---------------
| Does anyone know if there are any other uses of CPS other than
| of Programming Languages" as my tutorial.
Look at the summary at the end of Chapter 9, where they point out that
by reifying continuations as data structures, you can [sometimes] use
them even in languages or environments that don't support them natively,
e.g., to add coroutines or "threads" to C or assembler code.
Or, it may just put an interesting light on something else, e.g., one
can view an interrupt as as a non-deterministic forced invocation of a
continuation (which may or may not be transformable into a "subroutine
call", depending on the nature of the interrupt)...
+---------------
| My main motivation is in trying to "improve" the use of continuations
| in Common Lisp. Presently, I am using Paul Graham's macros.
+---------------
I suspect that at a minimum you'll come away from reading EoPL with a
significantly improved understanding of Graham's CL macros. Not that
you'll necessarily find that *satisfying*, since using continuations
in an environment that doesn't support them natively will probably
always be a bit clunky...
-Rob
-----
Rob Warnock, 7L-551 rp...@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd. FAX: 650-933-4392
Mountain View, CA 94043 PP-ASEL-IA
Gareth McCaughan
Gerald Smith wrote:
> Does anyone know if there are any other uses of CPS other than
> creating interpreters/compilers. I am trying to justify the effort
> of learning the technique.
Henry Baker[1] came up with one use: emulating multiple values
reasonably efficiently in languages that lack them, for such
purposes as multiple-precision arithmetic.
For instance, a language interpreter[2] I've been writing recently
contains code like (but not identical to):
Object make_long_low64(u32 a0, u32 a1, u32 a2, u32 a3) {
return new_Long(a0,a1);
}
Object multiply_long_long(Object x, Object y) {
return mult6464(low(x),high(x), low(y),high(y), make_long_low64);
}
Whether this is really more efficient than
Object multiply_long_long(Object x, Object y) {
u32 a[4];
mult6464(low(x),high(x), low(y),high(y), a);
return new_Long(a[0],a[1]);
}
is not obvious, and probably depends strongly on the efficiency
of your system's calling conventions.
[1] In the middle of his "Critique of DIN Kernel Lisp", which
you can find on his website at, errrrm,
<URL:ftp://ftp.netcom.com/pub/hb/hbaker/> or something
of the sort.
[2] I know you said "other than interpreters/compilers"; note
that you might easily want to do this sort of stuff in a
symbolic algebra package or something.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
gj...@dpmms.cam.ac.uk Cambridge University, England.
Jean-Paul Roy
Gerald Smith <70363...@CompuServe.COM> wrote:
> Does anyone know if there are any other uses of CPS other than
> creating interpreters/compilers. I am trying to justify the effort
> of learning the technique.
Gerald,
Maybe an interesting use of "soft" continuations (I mean constructed
by lambda as opposed to call/cc) is with several parameters
continuations, to simulate multiple-valued functions. The classical
example is probably the extended gcd algorithm, to get both the gcd
g of positive integers a,b and the Bezout coefficients u,v verifying
g = u*a + v*b
(define (extended-gcd a b k) ; returns (k g u v)
(if (zero? b)
(k a 1 0)
(extended-gcd b (modulo a b) ; Euclid g = (gcd a b) = (gcd b r)
(lambda (g u v) ; pretend that g = u*b + v*r
(k g v (- u (* v (quotient a b)))))))) ; g = v*a + (u-q*v)*b
(extended-gcd 78 18 list)
;Value: (6 1 -4)
(extended-gcd 78 18 (lambda (g u v) g))
;Value: 6
So you can compute (extended-gcd a b list) to get all of them, or
only (extended-gcd a b (lambda (g u v) g)) for the gcd alone.
You do not need to cons, for just after destructuring the list with
car/cdr.
Jean-Paul Roy
Dept. Informatique
Faculte des Sciences de Nice
FRANCE
[r...@unice.fr]
Sean Case
In article <66lcm4$6u...@fido.asd.sgi.com>,
rp...@rigden.engr.sgi.com (Rob Warnock) wrote:
>Or, it may just put an interesting light on something else, e.g., one
>can view an interrupt as as a non-deterministic forced invocation of a
>continuation (which may or may not be transformable into a "subroutine
>call", depending on the nature of the interrupt)...
This is more or less how the IOTRANSFER primitive described in Wirth's
_Programming in Modula-2_ works - it attaches an interrupt to a suspended
coroutine, which is effectively a single-use-only continuation.
Sean Case
Paul Prescod
In article <863ek1h...@g.pet.cam.ac.uk>,
Gareth McCaughan <gj...@dpmms.cam.ac.uk> wrote:
>Gerald Smith wrote:
>
>> Does anyone know if there are any other uses of CPS other than
>> creating interpreters/compilers. I am trying to justify the effort
>> of learning the technique.
>
>reasonably efficiently in languages that lack them, for such
>purposes as multiple-precision arithmetic.
And check out Matthew Fuchs' work:
How to escape the ubiquitous GUI event loop and eliminate the tortured,
dismembered programming style it engenders. The essential realization is
that "reactive programming" with callbacks is really a twisted form of
Continuation Passing Style, a source code transformation commonly used
in compilers for functional languages.
http://cs.nyu.edu/phd_students/fuchs/
Paul Prescod
Shriram Krishnamurthi
I'm posting this part on behalf of Matthias Felleisen:
----------------------------------------------------------------------
CPS is useful for many things. I suspect that we haven't discovered all of
it yet.
Here are three anecdotes. You're free to share them with your instructor
and others.
0. In 1994 I was on sabbatical at CMU. A systems PhD student, whose name
escpaes me for a moment, defened his thesis on the kernel of Mach 4. He
had transformed the kernel into cps and had used something called a control
delimiter to protect the micro-kernel from unwanted control actions. All of
his work was done in C, where he had to model closures with function ptrs
and records (for the envs).
[When time came for related work, he went on and on mentioning how some
obscure language theoretician seemed to have anticipated this stuff with
"unreadable publications" until one of his committee members pointed out
that this person wasn't obscure and that he was in the audience. I had
"invented" prompts about 10 years earlier and published about them in
POPL87. :-)]
1. During my first (or second) semester here (1987), I had a student in
class who asked your question. He was a mediocre student and was forced to
take my course so that he would have enough credit for graduating. He
_hated_ the cps segment of the course (a major component at the time). He
constantly challenged me in and out of class with questions concerning its
utility. He got a bad grade and left.
Not a year later, he showed up in my office -- to apologize. He had taken a
job with a local oil company. The company used Cray's and Fortran xyz, a
language w/o recursion. His boss assigned him the task of implementing a
recursive mathematical algorithm in Fortran xyz. he recalled my warnings
that someone in class would have to do exactly that, pulled out his course
notes, designed the algorithm in Scheme, cps'ed, elmiminated closures,
applied the register transformation, and voila` had a recursion-free
version. He then translated into Fortran xyz and the code ran the first
time. His boss was amazed and the student was cured.
Of course, the nicest part was that he let me know.
----------------------------------------------------------------------
The third anecdote that Matthias refers to is an essay written by
Jonathan Sobel at Indiana, forwarded via Dan Friedman.
----------------------------------------------------------------------
\magnification=\magstep5
\overfullrule=0pt
\centerline{\bf Is Scheme Faster than C?}
\centerline{\bf Jonathan Sobel}
\centerline{\bf Indiana University}
\bigbreak
During my first term of graduate school at Indiana University, I had
the good fortune to be taking the courses Analysis of Algorithms and
Programming Languages at the same time. One of the assignments in the
Algorithms course was a major term project in which we were to
implement and optimize the Fast Multiplication algorithm. Fast
Multiplication is a recursive, divide-and-conquer algorithm for
multiplying two numbers, especially large numbers: hundreds or
thousands of digits. (It is also used at the hardware level, where
the units are bits, instead of digits.)
Part of our grade for this project was based on how fast the program
ran. Everyone else immediately started writing in C, and even some in
Assembly. Of course, they all spent hours upon hours debugging as
they tried to get their highly optimized programs running. Modify,
re-compile, test; modify, re-compile, test; on and on....
To everyone's amazement and surprise, I started writing in Scheme. I had
only seen Scheme for the first time two months before, in my Programming
Languages course, but its simplicity made it attractive. Even more
importantly, I had discovered the joy of incremental compilation: make a
change or an addition without recompiling everything. I wonder how many
hours I saved.... On the other hand, the speed of the program was the most
important factor, and even though Chez Scheme (the Scheme implementation we
use here at Indiana University) is amazingly fast, it can't quite keep up
with C in most cases. So why choose Scheme?
Each call to {\bf fast-multiply} produces three recursive
calls to {\bf fast-multiply} (or to a simple {\bf multiply} routine, once you
reach small enough numbers). What I noticed was that each of those
three recursive calls had nearly the same control context. In a
simple-minded implementation in C, that context would be saved and
restored three times, being destroyed after the return of each call.
I thought to myself: If only I had explicit control over the flow of
my program, I could speed it up significantly by creating that context
only once and using it three times, destroying it only after the
return of the third recursive call. Function calls are so costly!
But I would never want to attempt such a thing from scratch in C.
What I had been learning in my Programming Language course, however,
was that I really could manage my own control flow if I wanted.
Furthermore, I could start with a simpler, more naive program and
basically derive the sophisticated one by a series of
correctness-preserving program transformations. This is where Scheme
really won. Because of its extremely algorithmic---almost
mathematical---nature, Scheme can be easily manipulated in a sort of
algebraic style. One can follow a series of rewrite rules (just about
blindly) to transform a program into another form with some desirable
property. This was exactly what I needed.
I started by implementing the algorithm very directly, following the
steps given in our Analysis of Algorithms textbook line by line. (I
definitely did NOT spend much time debugging in this phase.) Then I
converted the program to continuation passing style. Next I made
the continuations into explicit record structures, rather than Scheme
procedures. Finally, I transformed all the procedures to pass
information via registers, instead of calling each other with
arguments. At this stage, a procedure call is merely a simple {\bf goto},
quite a cheap operation. I completed the entire transformation in a
few hours.
With the Scheme program in its final form, it was a simple matter to
translate it into C. The C program contained no function calls
whatsoever; I really did use {\bf goto}. I had never had the courage to
use a {\bf goto} in C before; it was just too dangerous a tool. It was
kind of fun to use them now, knowing that I was completely safe in
doing so. That was the amazing part: I had produced a program that I
could not have written, and in any case would not have wanted to write.
Of course, you might be asking yourself, as I was, ``But does it run
fast?'' Speed was, after all, my main goal. The answer is a very
resounding ``Yes!'' Out of a class of about 15 students, only one
person beat me (and only barely), and he wrote significant portions of
his program directly in Assembly Language. The next fastest after me
took nearly twice as long to do the same work.
Now I know of several more transformations which I could have applied
to my Scheme program before I translated it into C, which would have
put mine in first place. A runtime profile of my program revealed
that the majority of time was spent in the C routines {\bf malloc} and
{\bf free}. I could have eliminated that heap usage by transforming my
program into a form in which all data allocation and control
management would have been completely stack-based, with an explicitly
managed stack. I could have pushed onto the stack exactly that
control information which I deemed necessary. There were places where
I could have modified the existing stack record, rather than popping
it off and creating a (similar) new one in its place. These
transformations were also presented in my Programming Languages
course. Unfortunately, at the time that I did my Algorithms project,
I did not yet grasp them well enough to use them.
What I learned from this experience was the importance of a
structured, systematic approach to programming. I have found that is
it better to write a simple, direct program to solve a problem,
having become convinced through experience that radical structural
transformations can come later; and I can depend on those
transformations to preserve the semantics of my program. I
have also learned that I can be free to focus on the nature of
whatever problem I am trying to solve, rather than on how efficient
my solution is. Efficiency comes from elegant solutions, not
optimized programs. Optimization is just a few
correctness-preserving transformations away.
\bye
----------------------------------------------------------------------
Gerald Smith
Orig' post:
> Does anyone know if there are any other uses of CPS other than
> creating interpreters/compilers. I am trying to justify the
>effort of learning the technique.
Thanks everyone. I now have incentive for learning CPS.
BTW, if anyone has pointers to how I can learn to code Wind/Unwind
which I want to use to directly process errors in an embedded
function, without needing to go to a near-toplevel function just
to process the error, as in the CL unwind/protect - -
Thanks again everyone
Gerald
Rolf-Thomas Happe
In article <j7vk9d3...@new-world.cs.rice.edu>
I'm posting this part on behalf of Matthias Felleisen:
----------------------------------------------------------------------
CPS is useful for many things. I suspect that we haven't discovered all of
it yet.
[...]
that someone in class would have to do exactly that, pulled out his course
notes, designed the algorithm in Scheme, cps'ed, elmiminated closures,
applied the register transformation, and voila` had a recursion-free
version. He then translated into Fortran xyz and the code ran the first
[...]
Is there a comprehensive text (textbook, lecture notes, survey
article, whatever) describing program transformation techniques?
If so, please tell me about it.
Thanks in advance,
rthappe
--
Getretener Quark wird weich und breit. (Tucholsky)
http://www.cauce.org/ Coalition Against Unsolicited Commercial Email
Brent Benson
Rolf-Thomas Happe wrote:
>
>Is there a comprehensive text (textbook, lecture notes, survey
>article, whatever) describing program transformation techniques?
>If so, please tell me about it.
"Essentials of Programming Languages" by Friedman, Wand and Haynes deals
with program transformation techniques in general, and CPS transformation
in detail: