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])