rtl, stack pointers, segmented stacks, foo

[Andy Wingo]

Hi,

The RTL branch tries hard to fix stack frame sizes, in order to avoid
moving around a stack pointer and causing numerous overflow checks.  I
think it's sufficient though to simply design procedures to have a
mostly fixed-size stack frame, but to update a top-of-the-stack pointer
when entering and leaving procedures.  Unlike the Guile 2.0 bytecode,
the stack pointer would not be used for addressing, generally.

This has the advantage that it's easier to deal with arbitrary numbers
of values on the stack, as is the case for nonlocal returns of some
number of values.  It also works better with the existing stack-walking
code that expects there to be both a frame pointer and a stack pointer
just works.

Having a nlocals marker in the instruction stream for code to parse out
was cute but not so useful, as it's possible for a frame to have some
other number of stack slots (for example, while dispatching on
case-lambda arities).  With this change, the code pointer of RTL
procedures will be just that: a pointer to code, with no data.  In Guile
2.0 terms, this would be like struct scm_objcode having no fields.

Another thought: segmented stacks.  This is for the case in which you
want a stack to expand and contract.  You need this to implement `map'
in the straightforward way:

  (define (map f l)
    (match l
      (() '())
      ((x . xs) (cons (f x) (map f xs)))))

Currently Guile's map does the reverse-accumulator dance.

Anyway, we can implement this in a fairly straightforward way: reserve
the first word in a stack segment for a 'previous sp' marker.  If
when backtracing, the next fp is either before the start of the segment,
or after the current fp, then it's in some other stack segment, and we
follow the 'previous sp' marker to get the new sp (instead of computing
SCM_FRAME_LOWER_ADDRESS (fp) - 1).

If the stack overflows at runtime, we can create a new stack segment,
place a frame that includes some stack cleanup code at the beginning of
the stack, then copy over a few frames from the old stack to the new
stack.  (Copying old frames gives hysteresis, as Dybvig's partial
continuations paper suggests.)

Anyway, somewhat disconnected thoughts here; sorry about that.
Ultimately these are minor things, that could even be implemented in the
2.0 branch, but that can give some interesting expressiveness gains
(having an effectively unlimited stack would be quite nice).

Andy
-- 
http://wingolog.org/