Drill 7 Solutions

Consider the following Lisp program:

(let ((x (add1 4))) (+ y x))

Which variables are free in the above expression?

* [ ] `x`
* [X] `y`
* [ ] `z`

The next several questions will be about this program, compiled using the compiler we ended up with after class on Wednesday.
```
(define (and x y)
(if x y false))

(define (between-detector x y)
(lambda (z) (and (< x z) (< z y))))

(let ((f (between-detector 3 8)))
(print (and (f 4) (and (f 6) ((between-detector 2 5) 7)))))
```
a. Which variables appear free in the lambda expression in between-detector?
- x
- y
- z
- f
- and
b. When the program is executed, how many closures will be created pointing at that lambda expression?
- 2
c. How many 8-byte heap cells are taken up by each of those closures?
- 3
d. Consider the call (f 4). For that call, what is the position of the return address, relative to that function's starting rsp?
- (X) rsp - 0
- ( ) rsp - 8
- ( ) rsp - 16
e. Consider the call (f 4). For that call, what is the position of a tagged pointer to a closure on the heap, relative to that function's starting rsp?
- ( ) rsp - 0
- ( ) rsp - 8
- (X) rsp - 16
f. Consider the call (f 4). For that call, what is the position of 16 (the runtime representation of 4), relative to that function's starting rsp?
- ( ) rsp - 0
- (X) rsp - 8
- ( ) rsp - 16
Here's a grammar describing the JSON data format. One of the terminals is left-ambiguous and will need to be left-factored if we want to write a top-down predictive parser. Which one?

<entity> ::=
| NUM
| STRING
| <obj>

<obj> ::=
| LBRACKET <kvs> RBRACKET

<kvs> ::=
| EPSILON
| <kv>
| <kv> COMMA <kvs>

<kv> ::=
| STRING COLON <entity>

* ( ) `<entity>`
* ( ) `<obj>`
* (X) `<kvs>`
* ( ) `<kv>`

Which of the following would be most appropriate for the type of a tokenizer function?
- s_exp -> token list
- token list -> s_exp
- string -> token list
- token list -> string
- string -> s_exp
- s_exp -> expr
Which of the following would be most appropriate for the type of a parser function, if the tokenizer has been factored into its own function?
- s_exp -> token list
- token list -> s_exp
- string -> token list
- token list -> string
- string -> s_exp
- s_exp -> expr