Introduction

This page collects some midterm questions from recent years. This is about twice as many questions as would be included on a single midterm.

Environments and SMoL I

Consider the following SMoL code:

(let ([f (let ([g (lambda (x) (+ 1 x))])
           (lambda (x) (+ x (g 3))))])
  (f 2))

The following diagram shows the environments (ovals) and heap (rectangles) for the above code at the point when the body of g, i.e. (+ 1 x) is evaluated. Fill in any missing values and draw arrows from the functions to their defining environments.

Environments and SMoL II

Consider the following SMoL code:

(defvar v (mvec 0 0))
(defvar f!
  (let ([u (mvec 2 v)])
    (lambda (w)
      (begin 
        (vec-set! w 0 u)
        (vec-set! u 0 w)))))
(f! v)

The following diagram shows the environments (ovals) and values on the heap (rectangles) for the above code at the point when (vec-set! u 0 w) is evaluated.

• Fill in any missing values, and
• draw arrows between environments and values to show references.

Macros

Consider the following macro definition (roughly speaking this is like the standard case macro, except that it evaluates the expressions being tested.

(define-syntax evcase
  (syntax-rules ()
    [(_ key-expr) (error 'evcase "missing case")]
    [(_ key-expr [val body] clauses ...)
     (if (equal? key-expr val) body
         (evcase key-expr clauses ...))]))

Give the fully expanded version of the expression (as might be shown by the DrRacket macro stepper). Make sure to indicate the “colour” (introduction context) e.g. with a number for each identifier introduced by a macro expansion.

(You can check this question using DrRacket)

(evcase 42
  [(+ 4 2) #f]
  [(* 6 7) #t])

Objects

The following tests demonstrate an object oriented implementation of the unary natural numbers from CS2613. (Z) makes a zero object and (S arg) creates the successor of its argument. Two methods are supported: pred returns the previous natural number and num converts the object to a Racket number.

(test (msg (Z) 'num) 0)
(define nat3 (S (S (S (Z)))))
(test (msg nat3 'num) 3)
(test (msg (msg nat3 'pred) 'num) 2)

Assume a correct implementation of msg and (Z) is given, complete the num method for non-zero objects by giving a replacement for ....

(define (S nat)
  (let ([self #f])
    (set! self
          (lambda (selector)
            (case selector
              [(pred) nat]
              [(num) ....])))
    self))

Type rule I

Give a type rule for single argument function application.

Types and Macros

Suppose our typed language has a primitive evcase equivalent to the following macro (roughly speaking this is like the standard case macro, except that it evaluates the expressions being tested.

(define-syntax evcase
  (syntax-rules ()
    [(_ key-expr) (error 'evcase "missing case")]
    [(_ key-expr [val body] clauses ...)
     (if (equal? key-expr val) body
         (evcase key-expr clauses ...))]))

Type rule II

Give a suitable type rule for the evcase primitive.

Typing

Use your type rule to build type determination tree for the following expression.

(evcase 42 [(+ x 2) #f] [(* 6 7) #t]))