On Thu, 1 Mar 2018 19:26:06 +0000 (UTC), Kaz Kylheku
<
217-67...@kylheku.com> wrote:
>On 2018-03-01, George Neuner <
gneu...@comcast.net> wrote:
>
>> It certainly is true that closeure conversion is a better solution
>> overall because it flattens all non-local accesses to use a single
>> indirection ... but it also significantly complicates the compiler,
>> and creates a need for handling wide pointers (or equivalent). Many
>> useful languages simply don't need that extra complexity.
>
>How do flat representations handle the fact that different levels
>of the lexical environment have different lifetimes?
In fact they don't ... all the "levels" of the lexical environment
must persist IN SOME FASHION for as long as the function lives. That
is the whole point of the "closure" - to persist the environment.
>E.g.
>
> (let ((a 1) (b 2))
> (loop ...
> (let ((c 3) (d 4))
> (lambda ()))))
This particular example actually is better suited to lambda lifting
than to closure conversion, but ...
>The (c d) environment is freshly instantiated each time the loop
>re-enters the inner let, but the (a b) environment is the same.
>
>Each (lambda ()) invocation must capture a different environment,
>with a different (c d) but shared (a b).
>
>If there is just a flat vector, it must still contain an extra
>level of indirection, no?
As you discuss more below, the answer depends on whether or not any
binding are mutated and shared. Note, it does not depend on whether
they are "mutable" per the language, but whether they actually are
mutated.
The real point of closure conversion is to flatten the function's
environment as much as is possible to minimize the runtime effort of
accessing the variable. How far you can take it depends on the
complexity of your compiler.
If no bindings are mutated, the values simply can be copied into a
single structure which is passed to the function.
[ a b c d ]
Note, that this also is the case for shared bindings which are NOT
mutated. (more below)
If any of the bindings are mutated, then you have to assume that they
also are shared (unless you can prove otherwise), and so you need to
provide a more complex environment.
What this looks like depends on how much you want to optimize the
non-shared bindings:
The simplest and most direct translation: you allocate a separate
structure for each scope, and a vector of pointers to them. You then
pass the pointer vector to the function.
[ + + ]
| |
| +--> [ c d ]
|
+-----> [ a b ]
More complex: you allocate separately those bindings which are
mutated, and create a flat structure that contains values for the
static bindings and pointers to the mutable ones.
[ a + c d ]
|
+--> [ b ]
More complex still: figure out whether mutated bindings actually are
shared. A mutated variable, e.g., used as a private counter, need not
be allocated separately.
This can get quite complicated to figure out if there are multiple
functions mutating different sets of shared bindings.
Also note that if the closures are not passed upward out of the
definition environment, the environment "structures" may be stack
allocated [if the runtime uses mark:release style stack(s)].
>If the language is purely functional, then the bindings are immutable,
>and so the (lambda ()) can copy the whole damn thing.
>
>If bindings are mutable, then when one lambda modifies a or b,
>the other lambdas (with their different environment) must see the
>modification. Yet they are shielded from each other's modification
>of c or d.
>
>So the upshot is that there has to be an extra level of indirection.
>
>It cannot be the case that "all non-local accesses use a single
>indirection".
An extra indirection is required only for those bindings which are
BOTH mutated AND shared. Sharing alone or mutation alone does not
require a separate allocation.
The challenge for the compiler is to figure whether a binding actually
is mutated only, shared only, or both mutated and shared.
>> I would never use static chains ... if display wasn't viable I would
>> jump straight to closure conversion.
>
>What is the meaning of "display", anyway?
>
>It seems like it just means "array" instead of "linked list" (just
>specifically in the context of activation frame environments).
More or less. I don't know who named the construct originally, or why
the particular name "display" was chosen.
The object, however, is simple. With nested functions and recursion,
every call frame logically is a member of 2 lists: "who called who",
and "who defined who".
"who called who" pretty much has to be maintained as a list chained
through the call frames themselves because the call stack can become
arbitrarily deep, and because (modulo GC, debugger, etc) there never
is any runtime need to follow more than 1 pointer.
However, "who defined who" hierarchies typically are fairly shallow:
some large scale studies done on Pascal showed that 16 lexical scopes
sufficed for 99+% of the code they examined.
A display optimizes non-local access (more than 1 lexical scope away)
by maintaining "who defined who" as a vector of frame pointers rather
than as yet another list chained through the frames themselves. It
has the same O(1) maintenance overhead as the chained list, but its
use is O(1) rather than O(n).
>The C main function's argv[] is a "display" of strings, whereas
>the Lisp list '("bash" "-c" "ls") is a "chain".
Yes.
>Except that the context isn't environment access and so we don't use
>the word "display".
Yes, the term "display" - referring to a vector of pointers - is
rather unique to compiler construction. I haven't seen it used as
such elsewhere.
>[A display is an array of pointers to the frames of the enclosing
>scopes. You can access any variable in an enclosing frame by
>indirecting through the frame's entry in the current display and then
>indexing. This is for languges like Algol and Pascal, not Lisp. I
>don't ever recall anyone talking about displays and threads, although
>I think they should work OK so long as you keep your displays on the
>local stack. -John]
Yes - the display has to be considered aa part of the thread switch
context - like CPU registers.
The main point with a display is that the function's execution
environment is (Lisp eq) identical to its definition environment.
There is no separate allocation(s) created such that the function can
be called after its definition environment is gone.
George