UNB/ CS/ David Bremner/ teaching/ cs4613/ tests/ T1/ practice

1. Introduction

1.1. Background

These are questions from previous midterms or finals. In some cases they have been edited to fit better with this year’s course. In order to reduce the total amount of code you have to read, the parsing of concrete syntax has been eliminated. A potential downside is that the tests are a bit harder to read, since they are written in terms of the abstract syntax. A typical midterm would have one or two questions, so not everything covered in class will be tested.

1.2. Handin Server

Like the assignments, we will use the handin server for the tests. In particular you can and should hand in multiple versions as you complete various parts. Unlike the assignments, there will not be automated checking of handed in tests. Our setup of the handin-server only deals with single files; in order to fit multiple questions (possibly in different languages) into one file, use the module form like the following.

#lang racket/base
(module question1 plait
  )
(module question2 plait #:untyped
        )
(module question3 plait
  )
(require (only-in 'question1))
(require (only-in 'question2))
(require (only-in 'question3))

The require forms at the end are used to make sure the code is actually run e.g. in DrRacket. This can help make sure your tests are actually running. If you don’t want to run the tests, you can comment out those requires.

2. Let2

In this question a new construct Let2 has been added to the LAE abstract syntax from the early lectures.

(define-type LAE
  [Num  (val : Number)]
  [Add  (l : LAE) (r : LAE)]
  [Id   (name : Symbol)]
  [Let1 (name : Symbol) (val : LAE) (expr : LAE)]
  [Let2 (name1 : Symbol) (val1 : LAE) (name2 : Symbol) (val2 : LAE) (expr : LAE)])

You can imagine this evaluates like a two clause let in plait. In particular this means parallel binding, rather than nested or sequential. For example

(test (let ([x 1] [y 2])
        (let ([x y] [y x])
          (- x y)))
      1)

Update the given subst function to support Let2.

(define (subst expr from to)
  (type-case LAE expr
    [(Num n) expr]
    [(Add l r) (Add (subst l from to) (subst r from to))]
    [(Id name) (if (eq? name from) to expr)]
    [(Let1 bound-id named-expr bound-body)
     (Let1 bound-id
           (subst named-expr from to)
           (if (eq? bound-id from)
               bound-body
               (subst bound-body from to)))]
    [(Let2 bound-id1 named-expr1 bound-id2 named-expr2 bound-body) ....]))

To cut down on the amount of code, we will work directly with the abstract syntax. Here are some tests of the new Let2 functionality:

(test (subst
       (Let2 'x (Id 'x) 'y (Id 'y) (Id 'x))
       'x
       (Num 5))
      (Let2 'x (Num 5) 'y (Id 'y) (Id 'x)))

(test (subst
       (Let2 'x (Id 'x) 'y (Id 'y) (Id 'y))
       'y
       (Num 5))
      (Let2 'x (Id 'x) 'y (Num 5) (Id 'y)))

(test (subst
       (Let2 'x (Id 'x) 'y (Id 'y) (Id 'z))
       'z
       (Num 5))
      (Let2 'x (Id 'x) 'y (Id 'y) (Num 5)))

3. Sum with lambda

Complete the curried definition of ’sum’ so that the following test passes. You should only use lambda, not any other binding forms like define or named-let.

(module lambda-sum plait  #:untyped
  (test
   (let ([sum ....])
     ((sum sum) '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18)))
     171)
  )

4. Free variables

Complete the function free-vars below that finds all free variables in a given FLANG expression. Note that environments here are sets of bound identifiers implemented with hash tables.

(module free-vars plait
  (define-type FLANG
    [Num  (val : Number)]
    [Add  (l : FLANG) (r : FLANG)]
    [Id   (name : Symbol)]
    [Let1 (id : Symbol) (named-expr : FLANG) (bound-body : FLANG)]
    [Fun  (param : Symbol) (body : FLANG)]
    [Call (fun : FLANG) (val : FLANG)])

  (define (bound name env)
    (if (none? (hash-ref env name)) #f #t))

  (define (extend name env)
    (hash-set env name #t))

  (define empty-env (hash empty))

  (test (bound 'x empty-env) #f)
  (test (bound 'x (extend 'y (extend 'x empty-env))) #t)

  (define (union the-set other-set)
    (hash (map (lambda (x) (pair x #t))
               (append (hash-keys the-set) (hash-keys other-set)))))

  (define (free-vars expr env)
    (type-case FLANG expr
      [(Num n) empty-env]
      [(Add l r) (union (free-vars l env) (free-vars r env))]
      [(Let1 bound-id named-expr bound-body) ....]
      [(Id name) (if (bound name env) empty-env (extend name empty-env))]
      [(Fun bound-id bound-body) ....]
      [(Call fun-expr arg-expr) ....]))

  (test (free-vars (Num 3) empty-env) empty-env)
  (test (free-vars (Add (Id 'x) (Num 3)) empty-env) (extend 'x empty-env))
  (test (free-vars (Add (Id 'x) (Num 3)) (extend 'x empty-env)) empty-env)
  (test (free-vars (Let1 'x (Num 3) (Add (Id 'x) (Num 3))) empty-env) empty-env)
  (test (free-vars (Let1 'x (Num 3) (Add (Id 'x) (Num 3))) (extend 'x empty-env)) empty-env)
  (test (free-vars (Let1 'x (Id 'y) (Add (Id 'x) (Num 3))) (extend 'x empty-env)) (extend 'y empty-env))
  (test (free-vars (Fun 'x  (Add (Id 'x) (Num 3))) (extend 'x empty-env)) empty-env)
  (test (free-vars (Call (Id 'x) (Id 'x)) empty-env) (extend 'x empty-env))
  )

5. Call Dynamic

Suppose extend FLANG abstract syntax by adding an option CallDyn to call a function with dynamic rather lexical scope.

(define-type FLANG
  [Num  (val : Number)]
  [Add  (l : FLANG) (r : FLANG)]
  [Id   (name : Symbol)]
  [Let1 (id : Symbol) (named-expr : FLANG) (bound-body : FLANG)]
  [Lam  (param : Symbol) (body : FLANG)]
  [CallDyn (fun : FLANG) (val : FLANG)]
  [Call (fun : FLANG) (val : FLANG)])

The following two tests contrast the lexically scoped Call with the dynamically scoped CallDyn.

(define (example body)
  (Let1 'x (Num 3)
        (Let1 'f (Lam 'y (Add (Id 'x) (Id 'y)))
              (Let1 'x (Num 5)
                    body))))

(test (interp (example (Call (Id 'f) (Num 4))) (EmptyEnv))
      (NumV 7))

(test (interp
       (example (CallDyn (Id 'f) (Num 4))) (EmptyEnv))
      (NumV 9))

Complete the environment based `interp` function for this new construct

(define (interp expr env)
  (type-case FLANG expr
    [(Num n) (NumV n)]
    [(Add l r)
     (NumV (+ (NumV-n (interp l env)) (NumV-n (interp r env))))]
    [(Let1 bound-id named-expr bound-body)
     (interp bound-body (Extend bound-id (interp named-expr env) env))]
    [(Id name) (lookup name env)]
    [(Lam bound-id bound-body) (LamV bound-id bound-body env)]
    [(CallDyn fun-expr arg-expr) ....]
    [(Call fun-expr arg-expr)
     (let ([fval (interp fun-expr env)])
       (type-case VAL fval
         [(LamV bound-id bound-body f-env)
          (interp bound-body (Extend bound-id (interp arg-expr env) f-env))]
         [else (error 'interp "non-function")]))]))

The remaining definitions you need are as follows.

(define-type ENV
  [EmptyEnv]
  [Extend (name : Symbol) (val : VAL) (rest : ENV)])

(define-type VAL
  [NumV (n : Number)]
  [LamV (arg : Symbol) (body : FLANG) (env : ENV)])

(define (lookup name env)
  (type-case ENV env
    [(EmptyEnv) (error 'lookup "no-binding")]
    [(Extend id val rest-env) (if (eq? id name) val (lookup name rest-env))]))

6. Typecheck+

In this question AE is a trivial, but polymorphic language. There is one operation, +, but it operates on both numbers (in the obvious way) and on Booleans (as or). The type rule for + is as follows (there is no notion of “type environment” here, because there are no identifiers).

e1 : t1  e2 : t1
----------------
{+ e1 e2} : t1

Complete the following typecheck function

(define (typecheck [ae : AE]) : Type
  (type-case AE ae
    [(Num n) (NumT)]
    [(Bool v) (BoolT)]
    [(Add l r) ....]))

Your completed function should pass the following tests:

(test (typecheck (Add (Num 1) (Num 2))) (NumT))
(test (typecheck (Add (Bool #t) (Bool #f))) (BoolT))
(test/exn (typecheck (Add (Bool #t) (Num 1))) "type mismatch")
(test/exn (typecheck (Add (Num 1) (Bool #t))) "type mismatch")

The remaining definitions needed for this question are

(define-type AE
  [Num  (val : Number)]
  [Bool (val : Boolean)]
  [Add  (l : AE) (r : AE)])

(define-type Type
  [NumT]
  [BoolT])