CS4400-Spr24 Assignment 5 Starter Code

code.rkt

#lang plait

;;;;;;;;;;;;;
; Problem 1 ;
;;;;;;;;;;;;;

; We define the lambda-calculus.
(define-type lcalc
  (var [s : Symbol])
  (lam [s : Symbol] [b : lcalc])
  (app [fn : lcalc] [b : lcalc]))

; We'll also give you substitution, which will be immensely useful.
(lam-subst : (lcalc Symbol lcalc -> lcalc))
(define (lam-subst [e1 : lcalc] [x : Symbol] [e2 : lcalc])
  (type-case lcalc e1
    [(var s) (if (symbol=? s x)
                 e2
                 (var s))]
    [(lam id body) (if (symbol=? x id)
                       (lam id body)
                       (lam id (lam-subst body x e2)))]
    [(app e1App e2App) (app (lam-subst e1App x e2)
                            (lam-subst e2App x e2))]))

; We'll be using Omega a lot, so let's define it here.
(define Omega (app (lam 'x (app (var 'x) (var 'x))) (lam 'x (app (var 'x) (var 'x)))))

; Problem 1a

(call-by-value : (lcalc -> lcalc))
(define (call-by-value exp)
  (error 'Unimplemented "Implement me!"))

; Problem 1b

(call-by-name : (lcalc -> lcalc))
(define (call-by-name exp)
  (error 'Unimplemented "Implement me!"))

; Problem 1c

(define example (error 'Unimplemented "Implement me!"))

; (test (equal? (call-by-name example) (call-by-value example)) #f)

;;;;;;;;;;;;;
; Problem 2 ;
;;;;;;;;;;;;;



#|
Your tree here...
|#

#|
Your tree here...
|#

#|
Your tree here...
|#

;;;;;;;;;;;;;
; Problem 2 ;
;;;;;;;;;;;;;

(define-type LType
  [NumT]
  [FunT (arg : LType) (body : LType)])

(define-type LExp
  [varE (s : Symbol)]
  [numE (n : Number)]
  [ifE (g : LExp) (thn : LExp) (els : LExp)]
  [lamE (arg : Symbol) (typ : LType) (body : LExp)]
  [appE (e : LExp) (arg : LExp)])

; We'll give you a substitution function, like the one in class.
(subst : (LExp Symbol LExp -> LExp))
(define (subst e1 x e2)
  (type-case LExp e1
    [(varE s) (if (symbol=? s x)
                  e2
                  (varE s))]
    [(numE n) (numE n)]
    [(ifE g thn els) (ifE (subst g x e2) (subst thn x e2) (subst els x e2))]
    [(lamE id typ body)
    (if (symbol=? x id)
      (lamE id typ body)              ; shadowing case
      (lamE id typ (subst body x e2)))]
    [(appE e1App e2App)
     (appE (subst e1App x e2)
           (subst e2App x e2))]))
; Problem 3a

(interp : (LExp -> LExp))
(define (interp exp)
  (error 'Unimplemented "implement me!"))

; Problem 3b

; Your tests here...

; Problem 3c

#|
Your rule(s) here...
|#

; Problem 3d

; We'll give you the type environment (context)
; and related functions that we covered during class.

(define-type-alias TEnv (Hashof Symbol LType))
(define mt-env (hash empty)) ;; "empty environment"

(define (lookup (n : TEnv) (s : Symbol))
  (type-case (Optionof LType) (hash-ref n s)
             [(none) (error 'type-error "unrecognized symbol")]
             [(some v) v]))

(extend : (TEnv Symbol LType -> TEnv))
(define (extend old-env new-name value)
  (hash-set old-env new-name value))

(type-of : (LExp -> LType))
(define (type-of e)
  (error 'Unimplemented "Implement me!"))