Re: lexical mumblings

[Andrew Innes]

On 30 Oct 2001 23:52:18 +0900, Miles Bader <address@hidden> said:

> Hi Andrew,
> 
> I read your notes, and have the following comments:
> 
>   1) For byte-codes, I think the implementation I suggested earlier is
>      the right way to go, mostly because it's _so_ much simpler, and
>      probably more efficient in the common case.

Yes, your approach of putting lexical variables in the bytecode stack is
better than my approach.  I'm not sure why I discarded the idea - I did
so very early on, and don't remember why.

I also like the versatility from getting full stack access in the
process - that could well be useful in its own right.

(BTW, I would recommend expanding Bstack_ref and Bstack_set to a set of
8 opcodes each, mirroring Bvarref and Bvarset - use the opcode ranges I
chose for Blocalref/set in my version.)

One issue that caused me to make certain things more complicated than it
seems they should be, is that I was careful to avoid making Lisp_Objects
point to stack-allocated memory.  There is no guarantee that I'm aware
of that the C stack is always within the addressable range of the
pointer field in Lisp_Objects, even though that is almost certainly true
on most platforms.

However, if we change the tagging system to use bottom bits for tags
(which I believe we can probably do now, given Ken Raeburn's work to
prepare for Guile), then this limitation is lifted.

>      As far as I can tell, the main potential advantage your approach
>      has is that it defers creating heap environments for closed-over
>      variables until the point where the closure is actually created at
>      runtime, whereas my approach puts closed-over variables into an a
>      heap-allocated environment-vector based only on compiler analysis
>      (for cases where it's not obvious that the closure can't escape).

The reason I move objects to the heap when constructing closures is to
handle the creation of multiple closures that close over a mixture of
shared and private bindings (see below).

Also, I took pains in my approach to make closures only include
references to the specific variables they need, and not entire
environment blocks.  This is part of the general principle of being
"safe for space-complexity" in garbage collection terms - ie. not
holding on to unneeded references that may live much longer than
expected (and which are inaccessible to the programmer).  I believe this
is a fairly important principle to follow.

BTW, I haven't understood in your approach how you will handle
situations where multiple closures are generated in the same function
(eg. in a loop) where some of the bindings being closed over are
different each time.  To illustrate, consider this example:

  (defun adders (base n)
    "Return list of setter and N adder functions"
    (let ((result (list (lambda (newbase)
                          (setq base newbase)))))
      (while (> n 0)
        (let ((value n))
          (push (lambda ()
                  (+ value base))
            'result))
        (setq n (1- n)))
      result))

The return value from calling (adders 3 5) is a list of 6 closures.
Each closure has a reference to the single binding of `base' which is
shared between all of them.  Additionally, 5 of the closures have
references to private bindings of `value' (a different one for each
closure).

Using your approach, you would allocate `base' in a vector of its own,
created at the start of `adders'.  On each iteration of the while loop,
you would make a new vector to hold each instance of the binding of
`value'.  So far, so good.  But how do you make the combination of the
two vectors available to the closures?

Okay, the answer to that is pretty obvious - you could make another
vector (again once for each iteration of the loop) which then holds the
other two vectors.  The closures would then dereference through two
vectors to get to the actual bindings of `base' and `value'.

In the general case, a closure's environment would consist of a "tree"
of vectors, some parts of which may have been constructed by closures
further out in the nesting.

In my patch, I handled the multi-level indexing operation in the
bytecode intepreter itself, while your version would handle it with
multiple opcodes.  Likewise, my patch constructed the environment block
with a variable length opcode containing a script, while yours uses
multiple opcodes.

I think your approach is much cleaner, since it makes the operations
visible at the lisp disassembly level.  Also, you are using opcodes
which are generally useful, like the Bvector one, rather than special
purpose opcodes like I did.

>      However, my intuition is that this probably not much of an
>      advantage in practice, and not worth the extra complexity.
> 
>   2) For the interpreter, your strategy seems reasonable.
> 
>      However, I'm making the assumption that it's not worth a lot of
>      extra complexity to make the interpreter ultra efficient (that's
>      what the byte-compiler is for), and that it's sufficient that it be
>      `good enough' (after all, macros are expanded every time they're
>      evaluated!).
> 
>      So I would make these suggestions:
> 
>        (a) Don't bother stack-allocating the interpreted environment
>            blocks, just use normal lisp vectors (or alists, or
>            whatever).
> 
>        (b) Just use a normal lisp (dynamically bound :-) variable to
>            hold the current top of the interpreted environment stack.
>            [call this `current-interp-lexenv' for reference]

Hmm.  Again I wonder why I didn't think of that.  I ended up going to a
lot of trouble to make a private env_chain pointer part of the
interpreter state, storing it in backtrace structs and handling it
correctly during unwind operations etc.  I would have to double check to
be sure your approach works correctly, but off-hand I can't think of a
reason why it wouldn't.  (Damn!)

I took care to make `let' respect CL-style (declare (foo special))
declarations, but if you instead introduce `llet' which only makes
lexical bindings (even if the symbols have been defvar'd?) then you
don't have that complexity.

AndrewI

>      Then you basically get the following changes to existing lisp
>      functions (here I'm assuming nil == no lexical environment, as
>      distinct from an empty lexical environment):
> 
>         funcall just does:
>                 if (current-interp-lexenv != nil)
>                    bind (current-interp-lexenv, nil)
> 
>         `llet' pushes stuff on current-interp-lexenv, by rebinding it
> 
>         `let' does:
>                 if (current-interp-lexenv != nil)
>                    call `llet'
>                 else
>                    do normal let dynamic binding
>            ;; this is to support the optional lexical binding
> 
>         `function' (the special form) of a lambda expr does:
>                 if (current-interp-lexenv != nil)
>                    return (llambda current-interp-lexenv (args) body)
>                 else
>                    return (lambda (args) body)
> 
>         evaluating a `llambda' of course, just binds
>         current-interp-lexenv to the enclosed environment.
> 
>     So, no GC magic, etc.
> 
>     The method I suggested earlier for turning on file-scope optional
>     lexical binding could be implemented in the above framework by
>     simply having `eval' bind current-interp-lexenv to an empty (not
>     nil) environment block whenever `use-lexical-binding' was non-nil.
> 
> -Miles
> -- 
> Yo mama's so fat when she gets on an elevator it HAS to go down.