This is a memo for chapter 4.1 of 3imp. A simple example of scheme with first-class functions, continuations, and tail-call optimization removed.
Registers
a: accumulator, used for general purposes
x: next instruction
e: frame of one outer scope
s: stack top
Call Frame
Static link (pushed last)
1st argument
:
:
last argument
next expression (return address)
Dynamic link (pushed last)
Instructions
Since there are no continuations, there is no conti,nuate.
- (halt)
- Halts the VM.
- Returns the value of the accumulator as the result
- (refer n m x)
- Follows the static link
- n… offset from the current frame
- (constant obj x)
- Puts constant obj into the accumulator and sets x
- (close vars body x)
- Creates a functional
- (test then else)
- Checks if the accumulator is null, and sets the next expression to next or else.
- (assign var x)
- Binds the accumulator to var
- Sets the next expression to x.
- (frame x ret)
- Creates the base of a frame from the dynamic link and ret
- (argument x)
- Pushes the value of the accumulator onto the stack
- Sets the next expression to x.
- (apply)
- Retrieves the static link and pushes it
- Makes the closure body the next expression.
- At this point, the frame is complete
- (return n)
- The size of the frame excluding the dynamic link and next expression
- In other words, subtracting n from the frame top retrieves the next expression and dynamic link
- This removes the frame and returns to the frame at the dynamic link origin
Example
((lambda (x y) (x y))
(lambda (x) (if x 10 20))
#f)
(frame (halt)
(constant
#f
(argument
(close
(refer 0 0 (test (constant 10 (return 2)) (constant 20 (return 2))))
(argument
(close
(frame (return 3) (refer 0 1 (argument (refer 0 0 (apply)))))
(apply)))))))
1. frame (halt)
s=2 -> | (halt) | ret destination
| 0 | dynamic link e
e=0 -> |-----------------|
2. constant #f
a = #f
3. argument (close ...
s=3 -> | #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
e=0 -> |-----------------|
4. close (refer 0 0 ...
a = ( (refer 0 0 ...) 0 ) collection of body and link
5. argument
s=4 -> |((refer00...) 0) | 1st argument
| #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
e=0 -> |-----------------|
6. close (frame (return 3) ...
a = ( (frame (return 3) ...) 0)
7. apply
s=3 -> | 0 | static link e (environment where closure is defined)
e=4 -> |((refer00...) 0) | 1st argument
| #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
_e=0 -> |-----------------|
8. frame (return 3) ...
s=7 -> | (return 3) | ret destination
| 4 | dynamic link e
| 0 | static link e (environment where closure is defined)
e=4 -> |((refer00...) 0) | 1st argument
| #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
_e=0 -> |-----------------|
9. refer 0 1
a = (index e 1) = #f
10. argument (refer 0 0
s=8 -> | #f | 1st argument
| (return 3) | ret destination
| 4 | dynamic link e
| 0 | static link e (environment where closure is defined)
e=4 -> |((refer00...) 0) | 1st argument
| #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
_e=0 -> |-----------------|
11. refer 0 0 (apply
a = (index e 0) = ((refer00...) 0)
12. apply
s=9 -> | 0 | static link e
e=8 -> | #f | 1st argument
| (return 3) | ret destination
| 4 | dynamic link e
| 0 | static link e (environment where closure is defined)
_e=4 -> |((refer00...) 0) | 1st argument
| #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
_e=0 -> |-----------------|
13. refer 0 0 (test
a = #f
14. test
x = (constant 20 ...)
15. constant 20
a = 20
16. return 2
s=5 -> | 0 | static link e (environment where closure is defined)
e=4 -> |((refer00...) 0) | 1st argument
| #f | 2nd argument
| (halt) | ret destination
| 0 | dynamic link e
_e=0 -> |-----------------|
17. return 3
s,e=0 -> |-----------------|
18. halt
Returns 20 in register a