[Caml-list] Error Reporting

[Caml-list] Error Reporting

[David McClain]

Hi,

I am looking for some ideas on handling program error reporting for a
compiler that is built largely on CPS. Since there are no stack frames to
crawl for traceback, I have a first cut based on keeping a finite length
queue of last visited closures. But this becomes problematic when there are
circularities in the code, i.e., recursion. Also, I think I have way too
much error tracking going on at each incremental execution step and so
runtime performance is cut back compared to what it could be.

This compiler is written in OCaml and so there really are stack frames in a
few places.

Any ideas?

- David McClain, Sr. Scientist, Raytheon Systems Co., Tucson, AZ
-------------------
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

Re: [Caml-list] Error Reporting

[David McClain]

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

Re: [Caml-list] Error Reporting

[Frank Atanassow]

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

Re: [Caml-list] Error Reporting

[John Prevost]

>>>>> "dm" == David McClain <barabh@qwest.net> writes:

    dm> I must confess that I don't understand this statement...

    dm> Let's take a trivial example of a sequence of 3 "primitive"
    dm> operations -- a primitive operation being one which cannot
    dm> make use of a continuation argument.

    dm> Normal OCaml syntax for such a function would be:

    dm> let seqFn () = aFn (); bFn (); cFn ()

    dm> Now let's write what the compiler would translate this
    dm> into....

    dm> let cPart () kont = cFn (); kont ()

    dm> let bPart () kont = bFn (); cPart () kont

    dm> let aPart () kont = aFn (); bPart () kont

This is a very specific for of tail calls where no continuation has
any argument--and yet, your assertion that you don't know anything
about history is incorrect.

The continuation passed to each function is very similar to a stack
frame.  Let's look at a more interesting example:

let plus a b = a + b
let mult a b = a * b
let a = plus (mult 3 5) (plus 8 (mult 7 10))

a CPS conversion of this would be:

let plus a b k = k (a + b)
let mult a b k = k (a * b)
let a = mult 3 5
       (fun x -> mult 7 10
         (fun y -> plus 8 y
          (fun z -> plus x z
           (fun w -> w))))

In this case, we see that the continuations are a bit more
interesting.  For a start, they take non-unit arguments.  Then we can
notice the dependencies between them.  Each application takes the code
to be run when the call "returns".  Now imagine this version of your
original code.  First, let's make aFn and friends be written in CPS
instead of somehow being outside it (the other bothersome thing about
your example):

val aFn : (unit -> 'a) -> unit -> 'a
val bFn : (unit -> 'a) -> unit -> 'a
val bFn : (unit -> 'a) -> unit -> 'a

(* example:
    let aFn k () = Printf.printf "a\n"; k () *)

let seqFn k = aFn (bFn (cFn k))

let program = seqFn id

program () results in:
a
b
c


This is a more realistic example of continuations in action.  Now, we
can extend this in a useful way!


let cont d f = (d,f)
let app (_,f) = f
let desc (d,_) = d

let aFn k () = Printf.printf "a (will return to %s)\n" (desc k); app k ()
let bFn k () = Printf.printf "b (will return to %s)\n" (desc k); app k ()
let cFn k () = Printf.printf "c (will return to %s)\n" (desc k); app k ()


let seqFn k =
  let seqFn_cont lineno f =
    cont ("seqFn (line " ^ string_of_int lineno ^ ")") f
  in
    aFn (seqFn_cont 2 (bFn (seqFn_cont 3 (cFn k))))

let program = seqFn (cont "main program" id)

program () results in:

a (will return to seqFn (line 2))
b (will return to seqFn (line 3))
c (will return to main program)


Again--these continuations are *just like stack frames*.  The only
difference is that in CPS they are treated as explicit manipulable
values.  In fact, SML/NJ uses continuations internally allocated on
the heap, rather than using a normal stack.

The right way to think about things is probably that a stack is, in
fact, a very simple continuation system which does not allow
continuations to be used in any way other than LIFO.


John.
-------------------
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

Re: [Caml-list] Error Reporting

[David McClain]

Er... sorry, I really hosed up the CPS translation...

> 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...

Let's take a trivial example of a sequence of 3 "primitive" operations -- a
primitive operation being one which cannot make use of a continuation
argument.

Normal OCaml syntax for such a function would be:

let seqFn () =
    aFn ();
    bFn ();
    cFn ()

Now let's write what the compiler would translate this into....

let cPart () kont =
     cFn ();
     kont ()

let bPart () kont =
    bFn ();
    cPart () kont

let aPart () kont =
    aFn ();
    bPart () kont

The compiler returns the "aPart" closure as the toplevel result of compiling
the seqFn. The kont argument of the toplevel call, at runtime, represents
the continuation that should be jumped to after the entire seqFn equivalent
has executed. But continuations are always forward pointing links to program
history and never backward links. Without a stack and normal function
subroutine calls there is no place for execution history.

Here you see that all continuations are executed as tail jumps without
leaving an audit trail of history. Each subfunction stands alone and knows
nothing of the others. All any of them know is what they must do for their
part, and what continuation to jump to to finish up the program.

So now, if an error occurs in any of these inner closures, how will they be
able to report the chain of events leading to their execution?

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.

Thanks,

- DM



----- Original Message -----
From: "Frank Atanassow" <franka@cs.uu.nl>
To: "David McClain" <barabh@qwest.net>
Cc: <caml-list@inria.fr>
Sent: Friday, September 28, 2001 8:24 AM
Subject: Re: [Caml-list] Error Reporting


> David McClain wrote (on 27-09-01 13:36 -0700):
> > In a tail call, and all continuations are tail calls, there is no record
of
> > past history -- hence no trail of continuation frames. I can easily
report
> > the location of the present error, but there is no history to report.
>
> There must be a past history, or otherwise you would not be able to
implement
> function application.
>
> Let's make a distinction between continuations and tail calls. Really, it
> sounds like you are only _representing_ continuations in the source
language
> as tail calls in the target language. So in the target language, the two
are
> identified, but when you are compiling the source, you know which
> continuations are tail-recursive calls in the source language, and which
are
> only functional returns. In the code you emit, i.e., in the target
> language, you can thus distinguish these two types of continuations, and
when an
> error occurs, traverse the continuations which represent functional
returns,
> which should eventually lead to the prime mover, the entire program's
> continuation.
>
> --
> 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
-------------------
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

Re: [Caml-list] Error Reporting

[David McClain]

> 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...

Let's take a trivial example of a sequence of 3 "primitive" operations -- a
primitive operation being one which cannot make use of a continuation
argument.

Normal OCaml syntax for such a function would be:

let seqFn () =
    aFn ();
    bFn ();
    cFn ()

Now rewrite this in CPS style:

let seqFn () kont =
  let aPart kont' =
     aFn ();
     kont' ()
  in
  let bPart kont' =
     bFn ();
     kont' ()
  in
  let cPart kont' =
     aFn ();
     kont' ()
  in
    aPart kont

Here you see that all continuations are executed as tail jumps without
leaving an audit trail of history. Each subfunction stands alone and knows
nothing of the others. All any of them know is what they must do for their
part, and what continuation to jump to to finish up the program.

So now, if an error occurs in any of these inner closures, how will they be
able to report the chain of events leading to their execution?

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.

Thanks,

- DM



----- Original Message -----
From: "Frank Atanassow" <franka@cs.uu.nl>
To: "David McClain" <barabh@qwest.net>
Cc: <caml-list@inria.fr>
Sent: Friday, September 28, 2001 8:24 AM
Subject: Re: [Caml-list] Error Reporting


> David McClain wrote (on 27-09-01 13:36 -0700):
> > In a tail call, and all continuations are tail calls, there is no record
of
> > past history -- hence no trail of continuation frames. I can easily
report
> > the location of the present error, but there is no history to report.
>
> There must be a past history, or otherwise you would not be able to
implement
> function application.
>
> Let's make a distinction between continuations and tail calls. Really, it
> sounds like you are only _representing_ continuations in the source
language
> as tail calls in the target language. So in the target language, the two
are
> identified, but when you are compiling the source, you know which
> continuations are tail-recursive calls in the source language, and which
are
> only functional returns. In the code you emit, i.e., in the target
> language, you can thus distinguish these two types of continuations, and
when an
> error occurs, traverse the continuations which represent functional
returns,
> which should eventually lead to the prime mover, the entire program's
> continuation.
>
> --
> 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
-------------------
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

Re: [Caml-list] Error Reporting

[Frank Atanassow]

David McClain wrote (on 27-09-01 13:36 -0700):
> In a tail call, and all continuations are tail calls, there is no record of
> past history -- hence no trail of continuation frames. I can easily report
> the location of the present error, but there is no history to report.

There must be a past history, or otherwise you would not be able to implement
function application.

Let's make a distinction between continuations and tail calls. Really, it
sounds like you are only _representing_ continuations in the source language
as tail calls in the target language. So in the target language, the two are
identified, but when you are compiling the source, you know which
continuations are tail-recursive calls in the source language, and which are
only functional returns. In the code you emit, i.e., in the target
language, you can thus distinguish these two types of continuations, and when an
error occurs, traverse the continuations which represent functional returns,
which should eventually lead to the prime mover, the entire program's
continuation.

-- 
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

Re: [Caml-list] Error Reporting

[David McClain]

Um, perhaps I misled everybody by claiming the compiler is reporting the
errors....

What I meant to say was that my compiler compiles a tree of closures passing
runtime control from one closure to the next with a CPS protocol. The errors
I am interested in reporting happen later at runtime when these trees are
executed.

The errors come as a result of invalid data types and possible user
interruptions of looping code. This compiler is NOT strongly typed, but
rather, behaves more like Lisp in that regard. It allows for dynamic typing
and sometimes this leads to program failure when inappropriate operations
are performed on data items.

So perhaps we can now get back on the same sheet of music. I see where you
thought I already had the information needed if, by error reporting, I had
meant that the compiler reports the errors. My compiler does quite well at
reporting program structural errors. The runtime errors of later execution
are the errors on which I am interested in building traceback information.

Thanks,

- DM

----- Original Message -----
From: "Krishnaswami, Neel" <neelk@cswcasa.com>
To: <caml-list@inria.fr>
Sent: Thursday, September 27, 2001 6:32 AM
Subject: Re: [Caml-list] Error Reporting


> David McClain [mailto:barabh@qwest.net] wrote:
> >
> > I am looking for some ideas on handling program error reporting for
> > a compiler that is built largely on CPS. Since there are no stack
> > frames to crawl for traceback, I have a first cut based on keeping a
> > finite length queue of last visited closures. But this becomes
> > problematic when there are circularities in the code, i.e.,
> > recursion. Also, I think I have way too much error tracking going on
> > at each incremental execution step and so runtime performance is cut
> > back compared to what it could be.
>
> Since you're using CPS, it seems like you have most of the infrastructure
> you need already. If you track source locations from parsing down to code
> generation, you can place a source location into each frame as you
allocate
> it. Then, when you have an error, you can simply walk back down the
> contination, emitting the source location of each frame. Since the
> continuation represents the rest of the computation, you automatically get
> the exact execution context of the erroneous statement.
>
> The overhead for this is one word per frame, plus initializing it
> at each continuation allocation. This is probably acceptable unless
> you are writing a really high-performance compiler. Also, tail-call
> optimization will make the traceback only approximate, but this is
> IME not a big deal in practice.
>
> Below is a small CPS-style lambda calculus interpreter that uses this
> idea to generate tracebacks of its evaluation. It's a treecode
> interpreter, but the ideas ought to carry over directly to bytecode too.
>
> -*-*-*-
>
> type var = string
> type pos = int
>
> (* Expressions carry the source location with them *)
>
> type expr =
>   | Lit of pos * int
>   | Var of pos * var
>   | Fun of pos * var * expr
>   | App of pos * expr * expr
>
> (*
>    Continuation frames have the position as an extra argument, so that
>    the continuation as a whole contains the backtrace info. Primitive
>    functions take the continuation as an extra argument so that they
>    can generate a backtrace on an error.
> *)
>
> type denot =
>   | Int of int
>   | Closure of env * var * expr
>   | Primop of (denot -> cont -> denot)
> and frame =
>   | KFun of pos * env * expr
>   | KArg of pos * env * denot
> and env = (var * denot) list
> and cont = frame list
>
> (*
>    Here are the guts of the machinery to generate a backtrace. We
>    need to extract a position from a frame and then just map over
>    the whole continuation to get the backtrace.
> *)
>
> exception Eval_error of string * pos list
>
> let framepos frame =
>   match frame with
>   | KFun(pos, _, _) -> pos
>   | KArg(pos, _, _) -> pos
>
> let backtrace k = List.map framepos k
>
> (*
>   We augment variable lookup so that failed lookups generate backtraces.
>   If you check statically for unbound variables this is unneccesary.
> *)
>
> let bind v d r = (v,d) :: r
>
> let lookup v r k =
>   try
>     List.assoc v r
>   with
>     Not_found -> raise (Eval_error("Unbound variable " ^ v, backtrace k))
>
>
> (*
>    In the interpreter proper, the only place where a backtrace is
>    generated is when an argument is applied to a non-function. If an
>    if-statement is added, then that should be too. Likewise, if
>    exceptions are added then an uncaught exception should generate
>    one also.
> *)
>
> let rec eval e r k =
>   match e with
>   | Lit(pos, n) ->
>       next (Int n) k
>   | Var(pos, v) ->
>       next (lookup v r k) k
>   | Fun(pos, formal, body) ->
>       next (Closure(r, formal, body)) k
>   | App(pos, f, arg) ->
>       eval f r (KFun(pos, r, arg) :: k)
> and next d k =
>   match k with
>   | [] -> d
>   | KFun(pos, r, arg) :: k' ->
>       eval arg r k'
>   | KArg(pos, r, func) :: k' ->
>       (match func with
>       | Int _ ->
>           raise (Eval_error("Not a function!", backtrace k))
>       | Closure(r, formal, body) ->
>           eval body (bind formal d r) k'
>       | Primop f ->
>           next (f d k) k')
> --
> Neel Krishnaswami
> neelk@cswcasa.com
> -------------------
> 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
-------------------
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

Re: [Caml-list] Error Reporting

[David McClain]

Thanks for the suggestions everybody...

I need to spend some time studying what Neel sent along. But it seems to me
that we have some misunderstandings between us about what I mean by CPS.

In a tail call, and all continuations are tail calls, there is no record of
past history -- hence no trail of continuation frames. I can easily report
the location of the present error, but there is no history to report.

but let me study what Neel sent along before I go off the wall any
further....

Cheers,

- DM

----- Original Message -----
From: "Krishnaswami, Neel" <neelk@cswcasa.com>
To: <caml-list@inria.fr>
Sent: Thursday, September 27, 2001 6:32 AM
Subject: Re: [Caml-list] Error Reporting


> David McClain [mailto:barabh@qwest.net] wrote:
> >
> > I am looking for some ideas on handling program error reporting for
> > a compiler that is built largely on CPS. Since there are no stack
> > frames to crawl for traceback, I have a first cut based on keeping a
> > finite length queue of last visited closures. But this becomes
> > problematic when there are circularities in the code, i.e.,
> > recursion. Also, I think I have way too much error tracking going on
> > at each incremental execution step and so runtime performance is cut
> > back compared to what it could be.
>
> Since you're using CPS, it seems like you have most of the infrastructure
> you need already. If you track source locations from parsing down to code
> generation, you can place a source location into each frame as you
allocate
> it. Then, when you have an error, you can simply walk back down the
> contination, emitting the source location of each frame. Since the
> continuation represents the rest of the computation, you automatically get
> the exact execution context of the erroneous statement.
>
> The overhead for this is one word per frame, plus initializing it
> at each continuation allocation. This is probably acceptable unless
> you are writing a really high-performance compiler. Also, tail-call
> optimization will make the traceback only approximate, but this is
> IME not a big deal in practice.
>
> Below is a small CPS-style lambda calculus interpreter that uses this
> idea to generate tracebacks of its evaluation. It's a treecode
> interpreter, but the ideas ought to carry over directly to bytecode too.
>
> -*-*-*-
>
> type var = string
> type pos = int
>
> (* Expressions carry the source location with them *)
>
> type expr =
>   | Lit of pos * int
>   | Var of pos * var
>   | Fun of pos * var * expr
>   | App of pos * expr * expr
>
> (*
>    Continuation frames have the position as an extra argument, so that
>    the continuation as a whole contains the backtrace info. Primitive
>    functions take the continuation as an extra argument so that they
>    can generate a backtrace on an error.
> *)
>
> type denot =
>   | Int of int
>   | Closure of env * var * expr
>   | Primop of (denot -> cont -> denot)
> and frame =
>   | KFun of pos * env * expr
>   | KArg of pos * env * denot
> and env = (var * denot) list
> and cont = frame list
>
> (*
>    Here are the guts of the machinery to generate a backtrace. We
>    need to extract a position from a frame and then just map over
>    the whole continuation to get the backtrace.
> *)
>
> exception Eval_error of string * pos list
>
> let framepos frame =
>   match frame with
>   | KFun(pos, _, _) -> pos
>   | KArg(pos, _, _) -> pos
>
> let backtrace k = List.map framepos k
>
> (*
>   We augment variable lookup so that failed lookups generate backtraces.
>   If you check statically for unbound variables this is unneccesary.
> *)
>
> let bind v d r = (v,d) :: r
>
> let lookup v r k =
>   try
>     List.assoc v r
>   with
>     Not_found -> raise (Eval_error("Unbound variable " ^ v, backtrace k))
>
>
> (*
>    In the interpreter proper, the only place where a backtrace is
>    generated is when an argument is applied to a non-function. If an
>    if-statement is added, then that should be too. Likewise, if
>    exceptions are added then an uncaught exception should generate
>    one also.
> *)
>
> let rec eval e r k =
>   match e with
>   | Lit(pos, n) ->
>       next (Int n) k
>   | Var(pos, v) ->
>       next (lookup v r k) k
>   | Fun(pos, formal, body) ->
>       next (Closure(r, formal, body)) k
>   | App(pos, f, arg) ->
>       eval f r (KFun(pos, r, arg) :: k)
> and next d k =
>   match k with
>   | [] -> d
>   | KFun(pos, r, arg) :: k' ->
>       eval arg r k'
>   | KArg(pos, r, func) :: k' ->
>       (match func with
>       | Int _ ->
>           raise (Eval_error("Not a function!", backtrace k))
>       | Closure(r, formal, body) ->
>           eval body (bind formal d r) k'
>       | Primop f ->
>           next (f d k) k')
> --
> Neel Krishnaswami
> neelk@cswcasa.com
> -------------------
> 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
-------------------
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

Re: [Caml-list] Error Reporting

[Krishnaswami, Neel]

David McClain [mailto:barabh@qwest.net] wrote:
> 
> I am looking for some ideas on handling program error reporting for
> a compiler that is built largely on CPS. Since there are no stack
> frames to crawl for traceback, I have a first cut based on keeping a
> finite length queue of last visited closures. But this becomes
> problematic when there are circularities in the code, i.e.,
> recursion. Also, I think I have way too much error tracking going on
> at each incremental execution step and so runtime performance is cut
> back compared to what it could be.

Since you're using CPS, it seems like you have most of the infrastructure 
you need already. If you track source locations from parsing down to code
generation, you can place a source location into each frame as you allocate
it. Then, when you have an error, you can simply walk back down the
contination, emitting the source location of each frame. Since the
continuation represents the rest of the computation, you automatically get 
the exact execution context of the erroneous statement. 

The overhead for this is one word per frame, plus initializing it 
at each continuation allocation. This is probably acceptable unless
you are writing a really high-performance compiler. Also, tail-call
optimization will make the traceback only approximate, but this is
IME not a big deal in practice. 

Below is a small CPS-style lambda calculus interpreter that uses this 
idea to generate tracebacks of its evaluation. It's a treecode 
interpreter, but the ideas ought to carry over directly to bytecode too. 

-*-*-*-

type var = string
type pos = int

(* Expressions carry the source location with them *)

type expr =
  | Lit of pos * int
  | Var of pos * var
  | Fun of pos * var * expr
  | App of pos * expr * expr

(*
   Continuation frames have the position as an extra argument, so that
   the continuation as a whole contains the backtrace info. Primitive
   functions take the continuation as an extra argument so that they
   can generate a backtrace on an error.
*)

type denot =
  | Int of int
  | Closure of env * var * expr
  | Primop of (denot -> cont -> denot)
and frame =
  | KFun of pos * env * expr
  | KArg of pos * env * denot
and env = (var * denot) list
and cont = frame list

(*
   Here are the guts of the machinery to generate a backtrace. We
   need to extract a position from a frame and then just map over
   the whole continuation to get the backtrace.
*)

exception Eval_error of string * pos list

let framepos frame =
  match frame with
  | KFun(pos, _, _) -> pos
  | KArg(pos, _, _) -> pos

let backtrace k = List.map framepos k 

(* 
  We augment variable lookup so that failed lookups generate backtraces.
  If you check statically for unbound variables this is unneccesary.
*)

let bind v d r = (v,d) :: r

let lookup v r k =
  try
    List.assoc v r 
  with
    Not_found -> raise (Eval_error("Unbound variable " ^ v, backtrace k))


(*
   In the interpreter proper, the only place where a backtrace is 
   generated is when an argument is applied to a non-function. If an 
   if-statement is added, then that should be too. Likewise, if 
   exceptions are added then an uncaught exception should generate
   one also.
*)

let rec eval e r k =
  match e with
  | Lit(pos, n) ->
      next (Int n) k
  | Var(pos, v) ->
      next (lookup v r k) k 
  | Fun(pos, formal, body) ->
      next (Closure(r, formal, body)) k
  | App(pos, f, arg) ->
      eval f r (KFun(pos, r, arg) :: k)
and next d k =
  match k with
  | [] -> d
  | KFun(pos, r, arg) :: k' ->
      eval arg r k'
  | KArg(pos, r, func) :: k' ->
      (match func with
      | Int _ ->
          raise (Eval_error("Not a function!", backtrace k))
      | Closure(r, formal, body) ->
          eval body (bind formal d r) k'
      | Primop f ->
          next (f d k) k')
--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
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

Re: [Caml-list] Error Reporting

[Damien Doligez]

>From: "David McClain" <barabh@qwest.net>

>I am looking for some ideas on handling program error reporting for a
>compiler that is built largely on CPS. Since there are no stack frames to
>crawl for traceback, I have a first cut based on keeping a finite length
>queue of last visited closures.

It seems to me that the current continuation in a CPS program should
contain the same information as the stack in a stack-based program.
You have the problem of losing information on a tail-call in both
systems, for example.  So you should be able to do as well as a stack
crawl with a "continuation crawl".  Of course, this will depend on the
data structure used to represent continuations, and if you use normal
closures for that, you will be compiler-dependent, but again this is
no worse than the stack-based case.

Or am I missing something ?

-- Damien
-------------------
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