[<<][sm][>>][..]
Sat Jan 18 18:52:28 CET 2020

Representing continuations : union of maximum frames

The main point is to avoid copies.  It's probably ok to create a
separate C structure for each continuation point.

The stack can be split into 3 pieces:
   shared - old
   shared - new

The issue is in overwriting old.  In a standard implementation this
happens naturally.  Can it be done naturally in a similar way?

There is no real difference, other than that there are many transient
forms of stack frames, and not all of them are relevant.

How to split this up?  Generate all the stack frames: every ANF
operation has an associated frame.  If the operation is blocking, the
frame is reified.

Or.. The store is just there, but there is a different interpretation
at each stack frame.  This is likely the simplest form, but requires a
lot of structures.  Using short typedef names for the structs:
s1,s2,.... and a short name for the stack, the ANF sequence looks
like:

((f1*)s)->a = 123;
((f2*)s)->b = ((f1*)s)->a + 1;

It could be implemented using a union.

union {
  struct {
    int a;
  } f1;
  struct {
    int a;
    int b;
  } f2;
}

s->f1.a = 123;
s->f2.b = s->f1.a + 1;

That can then be further simplified by reducing the number of
structures by using e.g. f2 where f1 would suffice:
 
s->f2.a = 123;
s->f2.b = s->f2.a + 1;

That would avoid quadradic clutter in the generated C code.  There
will be no issues with undefined variables as definition will be
ensured by code gen from proper ANF.

This actually seems quite straightforward.  

Maybe later find a way to reduce notational clutter, but for now
readability isn't a big issue.  As long as names are preserved it
would be fine.


Summary:

- Each operation has its associated environment.  All forms are
  'let*', meaning the environment grows, and previous variables are
  accessible.

- Casts are done for each reference.  Casts can be implemented using
  unions.

- Map each frame to its "maximum", and only generate and use those in
  C code.  This removes quadratic explosion.


Simple, but the combination is what makes it workable.

When this is represented in Haskell, it's probably possible to
parameterize and infer types, so instead of starting out with a data
type, maybe start out with a finally tagless form?

EDIT: Simple, but optimizer can't do much.  In between resume points,
we want to allow for optimization.  So when taking a continuation, or
when performing a tail call, it is probably best to copy any
additional variables.  But this then immediately opens up issues that
previously frozen stack frames no longer have the same size.  It's
hairy: gets very difficult very quickly.





[Reply][About]
[<<][sm][>>][..]