Ah yes! I remember that Flanagan paper. Now maybe I can really try to
understand it. I really appreciate all your feedback and the pointer to the
surrounding context papers.

I am compiling to OCaml closures. And for the most part the translation is
direct. However, I found that the compilation of match clauses benefited
greatly from CPS style.

I actually did one version of the compiler that used CPS throughout and I
found that I could almost do that except for the management of the OCaml
exception frames. But I also found that the code tended to run about 30%
slower (test programs took 1.3 times longer to run). The bulk of the code
was not measured, but your papers indicate that CPS is a bit of a memory
hog.

Many thanks to all who responded!

- DM

----- Original Message -----
From: "Frank Atanassow" <franka@cs.uu.nl>
To: "David McClain" <barabh@qwest.net>
Cc: <caml-list@inria.fr>
Sent: Monday, October 01, 2001 7:17 AM
Subject: Re: [Caml-list] Error Reporting


> David McClain wrote (on 28-09-01 09:49 -0700):
> > > There must be a past history, or otherwise you would not be able to
implement
> > > function application.
> >
> > I must confess that I don't understand this statement...
> [..]
> > But I suppose you are hinting that the compiler knows that all three of
> > these closures are contained in the outermost one and so some record of
> > activation history could be maintained by the compiler secretly plating
> > static linkage information into each sub-closure. Not a bad idea! It
> > certainly beats runtime computation of dynamic linkage and storing all
that
> > in a history queue.
>
> Something like that. John Prevost gave a nice example.
>
> In the CPS transform, in the case for application, you pass the
continuation
> of the application term to the operator, because the result of the
application
> has to be returned to the context of the call. That continuation is your
past
> history, since it tells you where you were before the function body was
> evaluated.
>
> In the case for a tail call, you don't return to the calling context; that
is,
> you discard the current continuation. Instead, (I think) you just pass the
> function to itself, since so it serves as its own continuation.
>
> So, for example, in
>
>   let rec f x = if x=0 then 1 + g x else f (x-1)
>
> you translate g x as
>
>   [g x] = fun k -> [g] (fun g' -> [x] (fun x' -> g' k x'))
>
> but f (x-1) as
>
>   [f (x-1)] = fun _ -> [f] (fun f' -> [x-1] (fun x' -> f' f' x'))
>
> Err... approximately at least. :) You will have to double-check this, but
the
> point is that distinction between these two cases gets obliterated in the
> image of the translation, because no function _ever_ returns (as you
> said).
>
> Therefore, you have to add the error-handling information before you do
the
> transform, for example by turning continuations into an abstract datatype
like
> John did. Indeed, this is what you have to do anyway when you use CPS to
> compile to machine code, since machines don't understand lambda-calculus,
but
> I assume you are compiling to Ocaml source.
>
> Anyway, you might want to read this paper:
>
>   The Essence of Compiling with Continuations
>   Flanagan, Sabry, Duba, Felleisen
>   http://citeseer.nj.nec.com/174731.html
>
> which shows why CPS transformation is redundant, and it is better to do a
> source-to-source transformation anyway. If you are really serious about
this,
> then you may also wish to check the Context (papers which reference this
> paper) to see extensions of this idea.
>
> --
> Frank Atanassow, Information & Computing Sciences, Utrecht University
> Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
> Tel +31 (030) 253-3261 Fax +31 (030) 251-379
>
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr