1. Introduction
Here are some practice questions for the first in class test. While you can generally use a computer to check your answers, I strongly suggest that you try to solve them by hand first. This is too many questions for one test, but I wanted to cover most of the material. Some of the questions also include more code than might be given on paper.
2. Evaluation
Here is a simple interpreter for expressions involving booleans and numbers.
if.rkt
It doesn’t have proper (dynamic or static) type checking but we will
fix that in a later question. Replace the ....
in interp
so that
the final test passes. Make sure you only evaluate one branch of the
if
.
3. Scope and Environments
For the following questions, consider the following SMoL program.
(let ([x 1]) (let ([f (let ([x 2]) (lambda (y) (+ x y)))]) (let ([x 3]) (f 4))))
3.1. Static scope
What is the answer when this code is evaluated according to the usual static scope rules?
You can check your answer in DrRacket or Stacker
3.2. Environments for Static Scope
Draw the relevant environments and heap values at the step of
evaluation when (+ x y)
is evaluated.
You can check your answer using Stacker but you don’t have to match the stacker diagram exactly.
3.3. Dynamic scope
What is the value when the program is evaluated under dynamic scope
Here you will need to use DrRacket with #lang smol/dyn-scope-is-bad
to check your environment.
3.4. Environments for dynamic scope
Draw the relevant environments and heap values at the step of
evaluation when (+ x y)
is evaluated under dynamic scope.
This one is a bit harder to check, but you can use the values of env
output by a stripped down version of the dynamic scoped interpreter
from Lecture 4:
4. Macros
4.1. Let in terms of lambda
Replace the ....
in the following using lambda
to implement a
macro equivalent to let
.
(define-syntax my-let2 (syntax-rules () [(my-let2 ([var val] ...) body) (....)])) (test (my-let2 ([x 3] [y 4]) (+ x y)) 7)
This is in the lecture notes and the text.
4.2. Let* in terms of lambda
Replace the ....
in the following using lambda
to implement
let*
(i.e. don’t use let
or let*
.
(define-syntax my-let* (syntax-rules () [(my-let* () body) body] [(my-let* ([v0 e0] [v1 e1] ...) body) (....)]) (test (my-let* ([x 1] [y (+ x 2)] [x (+ y 3)]) x) 6)
Probably the easiest way to solve this is to modify the recursive
my-let*
macro from class and replace the one use let
with a call
to a single argument lambda.
You can use DrRacket to verify your solution(s).
4.3. Hygiene
For the following questions, consider the following macro definition (and use).
#lang racket (define-syntax unless (syntax-rules () [(_ tst body ...) (let ([not (not tst)]) (if not (begin body ...) (void)))])) (let ([not 42]) (unless false (println not)))
4.3.1. Output
What is the output of evaluating this program?
4.3.2. Colouring Code
The following is the fully expanded version of the (last two lines of) the above code.
Each symbol has been suffixed with :__
; write in the “colour” (or number) corresponding
which macro expansion the symbol comes from. Make sure you don’t mix up shadowing with
macro symbol colouring.
(let:__ ((not:__ 42)) (let:__ ((not:__ (not:__ false:__))) (if:__ not:__ (begin:__ (println:__ not:__)) (void:__))))
You can check this question in DrRacket.
5. Objects
5.1. Instance and static variables
In the following questions, consider the following code from class.
(defvar mk-o-static (let ([counter 0]) (lambda (init) (let ([amount init]) (begin (set! counter (+ 1 counter)) (lambda (m) (if (equal? m "get") (lambda () amount) (if (equal? m "count") counter (error "no such member"))))))))) (defvar o1 (mk-o-static 1000)) (defvar o2 (mk-o-static 0)) (o1 "count") ((o1 "get")) (o2 "count")
5.1.1. Output
What is the output of this code?
5.1.2. Environments
Diagram the environments when evaluating the final (o2 'count)
.
You can check your answer using Stacker but you don’t have to match the stacker diagram exactly.
5.1.3. Patterns
Label each relevant identifier (variable) according to it’s object-oriented role (instance variable, class variable, constructor, constructor parameter etc…)
5.2. Self reference
Fill in the code around the given lambda
(without modifying the
given code) so that the recursion via self
works. You may find it
easier to do in #lang racket
, but it is possible in #lang
plait
. If you use #lang racket
, you will need to import the test
macro like in class.
(define fact (lambda (n) (cond [(zero? n) 1] [else (* n (self (- n 1)))])) ) (test (fact 6) 720)
Note: Giving this question for the first time on a test would be mean. But now you’ve seen it.
5.3. Dynamic dispatch
Complete the constructors leaf
and mt
so that the test passes.
#lang racket (require [only-in plait test ....]) (define (msg obj selector . args) (apply (obj selector) args)) (define (node v l r) (lambda (m) (case m [(collect) (lambda () (cons v (append (msg l 'collect) (msg r 'collect))))]))) (define (leaf v) ....) (define (mt) ....) (define leafy-tree (node 10 (leaf 5) (node 15 (leaf 6) (mt)))) (test (msg leafy-tree 'collect) (list 10 5 15 6))
Hint: this is essentially the same as one of the tree-sum examples from class.
6. Types
Consider the following partial type-checker for our language from the first question
if-tc.rkt6.1. Type rules
Give the type rule for if
. Explain your answer.
6.2. Type checker
Replace the ....
in the given code to add type checking for the
if
construct.