Practice Questions for Class Test 1

‎

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:

dyn-exp.rkt

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.rkt

6.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.