This is a memo after reading 3imp up to chapter 3. I wrote something Scheme-like before, so I wanted to make something better. 3imp is a helpful paper that concretely introduces three types of Scheme implementations: heap-based, stack-based, and string-based. I’ll particularly write down the workings of the heap-based VM in chapter 3.
Compiler
Scheme code -> Compiler -> Intermediate code -> Execute on VM
The flow is like this, so first we create a compiler from Scheme code to intermediate code. Something like continuation-passing style. Basically, instructions flow from front to back. I’ll omit the compiler details as they’re in the paper.
;; Scheme code
(if #f 10 20)
↓
;; Intermediate code
(constant #f (test (constant 10 (halt))
(constant 20 (halt))))
VM Specification
The register and intermediate code specifications are as follows. First, the VM has the following 5 registers.
- Register a - the accumulator
- Used universally for function return values, constant/variable loads, function arguments, conditional expressions, etc.
- When returned to top level, it contains the computation result
- Example: 10, (1 2 3)
- Register x - the next expression
- Stores the next expression to be evaluated (intermediate code)
- Actually, the expressions to be evaluated are passed as a list, but the car part is the next expression to evaluate
- Example: (constant #f (test …))
- Register e - the current environments
- Stores the current variable assignment (environment)
- When applying a closure, its arguments are newly added and the environment is updated
- Variable names don’t have particular meaning (explained later), so just store values
- The head of the list is the most recent scope.
- Example: ((1 2 3) (#t #f) ()), ()
- Register r - the current rib
- Used as an argument list when calling functions
- Cons the values of evaluated register a
- Example: (1 2 3), ()
- Register s - the current stack
- Call frame
- Added when calling functions, stores (x e r s) of the caller in this order
- Restore registers saved here when returning from functions
- Extract as continuation object or assign with call/cc
- Example: ((return) (1 2 3) () ()), ()
The intermediate code is as follows.
- (halt)
- Halt the VM
- The value in register a becomes the computation result
- (refer var x)
- Extract the value of variable var from current environment to register a
- Set argument x (next instruction) to register x
- (constant obj x)
- Set obj to register a
- Set argument x (next instruction) to register x
- (close body x)
- Create closure object from body and current environment, put in register a
- Set argument x (next instruction) to register x
- (test then else)
- If register a is #f, set register x to then
- Otherwise, set register x to else
- (assign var x)
- Set register a to variable var in current environment
- Set argument x (next instruction) to register x
- (conti x)
- Create continuation object from register s, set to register a
- Set argument x (next instruction) to register x
- Continuation object is treated as a type of closure object
- (nuate s var)
- Stack restoration
- Set call frame argument s to register s
- Extract the value of variable var (here (0.0)) from current environment, set to register a
- Set register x to (return)
- (frame ret x)
- Create new call frame
- Empty register r
- Set (argument ret, register e, register r, register s) to register s
- (argument x)
- Cons register a to register r
- Set argument x (next instruction) to register x
- (apply)
- Closure application
- Extract closure body body and environment e from register a
- Set register x to body
- Add register r to environment e, set to register e
- (return)
- Based on register s, extract register list (x e r s),
- Set to each register
Closure Definition & Invocation
;; Scheme code
((lambda (x y z) (if x y z))
#f 2 3)
↓
;; Intermediate code
(frame
(halt)
(constant
3
(argument
(constant
2
(argument
(constant
#f
(argument
(close
(refer
(0 . 0)
(test
(refer
(0 . 1)
(return))
(refer
(0 . 2)
(return))))
(apply)))))))))
This is the transition of each register’s value when executing this intermediate code.
In the initial state, most registers are empty, and only register x points to the next instruction. In 1., create a call frame from current x, e, r, s registers and push to register s. From 2. to 7., load values to register a with constant and add to register r with argument. In 8., add the first argument of close instruction (closure object) to register a, and the second argument (function application) to register x. In 9., set the body from register a (closure object) to register x, and add register r to the closure object’s environment to register e. Empty register r. In 10., extract the value at position (0.0) from current environment e. In 11., check the contents of register a and set the 1st argument of test instruction if true, or 2nd argument if false to register x. In 12., extract the value at position (0.2) and set to register a. In 13., extract (x e r s) from register s and restore the state before function call.
0. ** a = () x = (frame (halt) (constant ...)) e = () r = () s = ()
1. *frame* a = () x = (constant 3 ...) e = () r = () s = ((halt) () () ())
2. *constant* a = 3 x = (argument ...) e = () r = () s = ((halt) () () ())
3. *argument* a = 3 x = (constant 2 ...) e = () r = (3) s = ((halt) () () ())
4. *constant* a = 2 x = (argument ...) e = () r = (3) s = ((halt) () () ())
5. *argument* a = 2 x = (constant #f ...) e = () r = (2 3) s = ((halt) () () ())
6. *constant* a = #f x = (argument ...) e = () r = (2 3) s = ((halt) () () ())
7. *argument* a = #f x = (close (refer ...) (apply)) e = () r = (#f 2 3) s = ((halt) () () ())
8. *close* a = ((refer (0 . 0) ...) ()) x = (apply) e = () r = (#f 2 3) s = ((halt) () () ())
9. *apply* a = ((refer (0 . 0) ...) ()) x = (refer (0 . 0) ...) e = ((#f 2 3)) r = () s = ((halt) () () ())
10. *refer* a = #f x = (test (refer ...) (refer ...)) e = ((#f 2 3)) r = () s = ((halt) () () ())
11. *test* a = #f x = (refer (0 . 2) (return)) e = ((#f 2 3)) r = () s = ((halt) () () ())
12. *refer* a = 3 x = (return) e = ((#f 2 3)) r = () s = ((halt) () () ())
13. *return* a = 3 x = (halt) e = () r = () s = ()
14. *halt* Return computation result a=3
Continuation
;; Scheme code
(call/cc (lambda (k) (if (k #f) 10 20)))
↓
;; Intermediate code
(frame
(halt)
(conti
(argument
(close
(frame
(test
(constant
10
(return))
(constant
20
(return)))
(constant
#f
(argument
(refer
(0 . 0)
(apply)))))
(apply)))))
Continuation objects are created by conti, with body (nuate s (0 . 0)) and empty environment set as a closure to register a. The frame is called twice: once to call the λ expression with continuation object as argument, and once to call the continuation object (a type of closure). First, since call/cc calls a function with continuation object as argument, create a call frame in 2. In 3. and 4., create continuation object from stack and set as argument. In 5., create closure object from the first argument of close (frame …) and current environment, set to register a. In 6., set environment e and register x from register a to apply the closure. Now we evaluate (if (k #f) 10 20).
In 7., evaluate (k #f). This is a function call, so create a new call frame. In 8. and 9., add constant #f to the argument list. In 10., extract k (continuation object) from current environment and set to register a. In 11., apply that function (continuation object). In 12., extract stack from continuation object and set. Also set register x to return. In 13., restore register group, and halt makes #f the computation result.
1. ** a = () x = (frame (halt) (conti ...)) e = () r = () s = ()
2. *frame* a = () x = (conti ...) e = () r = () s = ((halt) () () ())
3. *conti* a = ((nuate ...) ()) x = (argument ...) e = () r = () s = ((halt) () () ())
4. *argument* a = ((nuate ...) ()) x = (close (frame ...) (apply)) e = () r = (((nuate ...) ())) s = ((halt) () () ())
5. *close* a = ((frame ...) ()) x = (apply) e = () r = (((nuate ...) ())) s = ((halt) () () ())
6. *apply* a = ((frame ...) ()) x = (frame ...) e = ((((nuate ...) ()))) r = () s = ((halt) () () ())
7. *frame* a = ((frame ...) ()) x = (constant #f ...) e = ((((nuate ...) ()))) r = () s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
8. *constant* a = #f x = (argument ...) e = ((((nuate ...) ()))) r = () s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
9. *argument* a = #f x = (refer (0 . 0) ...) e = ((((nuate ...) ()))) r = (#f) s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
10.*refer* a = ((nuate ...) ()) x = (apply) e = ((((nuate ...) ()))) r = (#f) s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
11.*apply* a = ((nuate ...) ()) x = (nuate ...) e = ((#f)) r = () s = ((test ...) ((((nuate ...) ()))) () ((halt) () () ()))
12.*nuate* a = #f x = (return) e = ((#f)) r = () s = ((halt) () () ())
13.*return* a = #f x = (halt) e = () r = () s = ()
14.*halt* Return computation result a=#f
You can see that closure objects store a set of instructions and the environment at definition time, and continuation objects are closure objects containing instructions to restore the stack. In heap-based, both first-class functions and first-class continuations can be implemented relatively easily. I wonder if anyone reads this far. Let’s move on to stack-based.