pop@lastresort.cs.umass.edu (06/12/90)
I fail to see why the callee-saves convention should be inapplicable to
closures. Reading between the lines, I think that the problem is that
the conventional view is that closures are about FREE VARIABLES,
and therefore require register manipulation to access them.
A much simpler approach was introduced in POP-2, namely that closures
are obtained by CURRYING, although we called it "partial
application". Free variables can be eliminated by a process that has been
called "lambda lifting" (see [Jones 87]). POP-2 programmers were expected to
know how to do this by hand. Subsequently POP-11 programmers have had it
automated, as detailed below.
In the POP-2 implementation of closures, a partial application
was compiled to a short sequence of code which only affected the
stack-pointer.
E.g. the closure f(%x1,....xn%) was compiled to
PUSH Ref_x1
PUSH Ref_x2
.
.
PUSH Ref_xn
JUMP Ref_f
Where Ref_x1...Ref_xn, Ref_f were references (i.e. one-element
data-structures) containing the evaluated x1.....xn, f.
The state of the machine having performed the JUMP is equivalent to that
obtaining if the function f were called directly. POP-2 of course did not
support laziness in any systematic way, so that the closure mechanism did not
support immediate return as specified by Simon Jones. This would however
present no problems, since in that case the disturbance to the machine-state
pertaining in the caller is minimal. Likewise any call to a subroutine that
makes local some non-local object would, on return, restore machine state as
it pertained in the closure.
The current POPLOG VM provides the following treatment of lexical variables,
which supports the requirements of Common Lisp as well as POP-11 and ML.
It preserves the essentials of the POP-2 approach. The main drawback is that
type 2 non-locals introduce a significant overhead to the swapping of
POP-11 processes, and that efficient use of registers depends on the
programmer declaring the most-used variables first. It is of course intended
for a conventional Von-Neumann architecture.
EXTRACT FROM THE ON-LINE MANUAL ENTRY "ref vmcode"
Implementation of Lexical Scoping
---------------------------------
This section describes the way in which lexically-scoped variables
declared with -sysLVARS- will actually be implemented in the final
output code. Top-level variables (i.e. those declared at execute level)
simply translate to unique fixed identifiers, and are irrelevant to what
follows. Otherwise, a lexical variable X declared inside a procedure P
falls into one of three categories, depending on its usage:
type 1
------
Used strictly locally, i.e. X is not referenced non-locally
inside any procedure nested within P, and is not pushed as
an identifier with -sysIDENT-.
type 2
------
Used non-locally inside a nested procedure Q, but does not
cross a 'push' boundary. By this we mean that neither Q nor
any other procedure that encloses it inside P is pushed as a
data object (see below). Also not pushed as an identifier
with -sysIDENT-.
type 3
------
Used non-locally inside a nested procedure, and does cross a
'push' boundary, or directly pushed as an identifier with
-sysIDENT-.
A procedure is 'pushed as a data object' if the object returned by
-sysENDPROCEDURE- is given to -sysPUSHQ-, or -sysPASSIGN-'ed to any
identifier other than a lexical constant. If assigned to a lexical
constant, it is also 'pushed' by any -sysPUSH- for that constant. In
POP-11 terms, this means that the only kind of nested -define- that does
not count directly as a 'push' is 'define lconstant ...'.
Thus for example, in the following POP-11 procedure W is of type 1,
X is of type 2, and Y and Z are of type 3:
define P();
lvars W X Y Z;
W => ;;; W only used locally
define lconstant Q();
X => ;;; X used non-locally
enddefine;
Q(); ;;; Q is called but not pushed
define lconstant R();
define lconstant S();
Y => ;;; Y used non-locally
enddefine;
S(); ;;; S is called but not pushed
enddefine;
R -> W; ;;; but R is pushed
define vars T(); ;;; T is pushed by being "vars"
Z => ;;; and it uses Z non-locally
enddefine;
enddefine;
The different variable types are implemented by the following
mechanisms, given in order of decreasing efficiency:
-- The first N type-1 variables (in order of declaration) are
allocated to machine registers, where the number N is
implementation dependent. (In most current systems, N = 2;
exceptions are the Sun-4, for which N = 8, and the Sequent
Symmetry, for which N = 0.)
-- The rest of the type-1's are allocated to stack frame cells.
-- Type-2 variables are allocated to unique dynamically local
identifiers.
-- Type-3's require the run-time construction of identifier
records in the heap to hold their values, since a 'pushed'
procedure that uses them non-locally (or the identifiers
themselves if pushed with -sysIDENT-) can be passed either
(a) up and right out of the current lexical environment,
or
(b) down into another invocation of that same
environment.
They use stack frame cells initialised to hold identifiers,
these being created on entry to the home procedure and
passed down as hidden extra arguments to nested procedures
that use them non-locally. Whenever such a procedure is
'pushed', a closure of the base procedure with the run-time
identifier arguments is created and in addition, an auxilary
variable is generated to hold the closure, ensuring that it
is only produced once for each invocation of the
environment. (This variable itself may come out as any of
the three types, depending on whether it is used non-locally
or across a push boundary.)
In fact, providing neither (a) nor (b) actually happens for a type-3, a
unique dynamic variable (as for type-2 variables) would suffice; the VM
compiler is unable to recognise this, but the user may be able to in
many situations. For this reason the -sysDLVARS- declaration is
provided: this is identical to -sysLVARS-, except that type-3
-sysDLVARS- are forced to be type-2's.
A typical use of this in POP-11 would be something like the
following procedure to count the number of characters printed for an
object:
define countchars(x) -> n;
lvars x; dlvars n;
define vars cucharout();
-> ; ;;; erase the character
n+1 -> n ;;; increment non-local count
enddefine;
0 -> n;
pr(x)
enddefine;
On the other hand, it may be known that an individual 'push' for a
particular procedure (or a push of an identifier with -sysIDENT-) does
not necessitate the use of type-3 variables. E.g. in
applist([1 2 3 4], P)
where P is a procedure that uses non-locals, (a) or (b) cannot happen
(because -applist- is a system procedure that can never do either with
P).
Where this sort of information is known to the compiler writer, the
flag VM_DISCOUNT_LEX_PUSHES in -pop_vm_flags- can be employed. While
set, -sysPUSH-, -sysPUSHQ- and -sysIDENT- instructions that would
otherwise cause variables to be marked as type-3 will not do so.
(However, any other -sysPUSH- or -sysPUSHQ- on the relevant procedure
while this flag is NOT set will cause the 'damage' to be done,
irrevocably.)
In fact, the VM compiler DOES recognise this situation when the
pushed procedure is the last argument to one of a small number of system
procedures: currently, these are just the 'app' procedures -applist-,
-maplist-, -appdata- and -appproperty-. So, the particular example above
will not (in itself) cause the production of type-3 variables.
Simon L Peyton Jones [1987] "The Implementation of Functional Programming
Languages" Prentice Hall.