Re: [Caml-list] Error Reporting

[Frank Atanassow <franka@cs.uu.nl>]

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