[virtmach] lambda (Re: virtmach-digest V1 #13)

[Lars Thomas Hansen]

>Date: Tue, 7 Dec 1999 21:22:18 +0000
>From: Ceri Storey <cez@nomorespam.freeserve.co.uk>
>Subject: [virtmach] lambda
>
>in a bytecode based VM, is it possible to have a lambda opcode? (as in
>scheme/lisp/lambda calculus) woud it be a case of pushing a pre
>comipled function onto the stack (from a vector of constants, as in
>emacs) or can you create one from the nomal 'stream' of instructions?
>(i apologise for the pointless question, and for apologising. [stack
>overflow from exessive recursion])

The VM in Larceny (a Scheme system) has a LAMBDA opcode.  The source form
is this:

	(lambda (instructions
		 go
		 here)
	  <n>			; number of closed-over registers
	  #f)			; documentation

e.g., the code for

	(define (addk k)
	  (lambda (n) (+ n k)))

would be similar to

	((args= 1)		; k is in register 1
	 (lambda ((args=   1)   ; n is in register 1
		  (lexical 1,1) ; get k
		  (setreg  2)   ; put k in register 2
		  (reg     1)   ; get n
		  (op2     +,2) ; compute n+k
		  (return))     ; return n+k
           1			; close over k
	   #f)
         (return))		; return the procedure

The assembler converts a LAMBDA into code that
	(1) allocates a new procedure structure of length <n>+3
	(2) fetches the code vector of the new procedure from the
	    constant pool of the enclosing procedure and stores it
	    in the procedure structure
	(3) ditto for the constant pool of the new procedure
	(4) stores registers 0..<n> in the procedure structure
	(5) leaves a pointer to the structure in the accumulator register

(In the current version of Larceny, the VM instructions are converted to
native code by the assembler, so there is no interpretation at runtime,
but a bytecoded system would do exactly what I've outlined.)

The LAMBDA instruction was probably inherited from the MacScheme virtual
machine, though I'm not 100% certain about that (I've never seen the
internals of MacScheme, but the design of the instruction set for
Larceny was done by Will Clinger who also wrote MacScheme.)

The instruction set is documented at 
http://www.ccs.neu.edu/home/will/Larceny/notes/note13-malcode.html

You may also be interested in 
  William Clinger, "The Scheme 311 Compiler: an exercise in denotational
  semantics.", ACM Conference on Lisp and Functional Programming, 1984.
which uses a similar instruction set, though based on a stack machine
if I remember correctly.

--lars