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.