closures.rkt

;; CIS352 -- Fall 2023
;; Closure-Creating Interpreters
#lang racket

(define (expr? e)
  (match e
    [(? symbol? x) #t] ;; variables
    [(? number? n) #t]
    ;; single-variable let binding
    [`(let ([,(? symbol? x) ,(? expr? e-let-binding)]) ,(? expr? e-body)) #t]
    ;; single-variable lambdas 
    [`(lambda (,(? symbol? x)) ,(? expr? e-body)) #t]
    ;; application of a lambda (or something that computes to a lambda) to a value e1
    [`(,(? expr? e0) ,(? expr? e1)) #t]
    [`(+ ,(? expr? e0) ,(? expr? e1)) #t]
    [`(* ,(? expr? e0) ,(? expr? e1)) #t]
    [`(- ,(? expr? e0) ,(? expr? e1)) #t]
    [`(/ ,(? expr? e0) ,(? expr? e1)) #t]
    [`(if0 ,(? expr? e0) ,(? expr? e1) ,(? expr? e2)) #t]
    [_ #f]))

(expr? '(if0 ((lambda (x) (let ([y 3]) (+ x y))) (+ 5 2))
             (((lambda (y) y) (lambda (x) x)) 5)
             ((lambda (z) (+ z 3)) 6)))

;; Now this is a valid expression
;; '(if0 (+ x y) (* y 2) (- y 3))
;; this is a valid expr?, but it should crash at runtime
;; because there is no binding for x
;; What form could I use to bind x to some value?

;; values are either numbers or closures
;; a closure is the result of interpreting a lambda
(define (value? v)
  (match v
    [(? number? n) #t] ;; numbers are values
    ;; closures are the interpreter's runtime representation of lambdas
    [`(closure (lambda (,(? symbol? x)) ,(? expr? e-body)) ,(? environment? env)) #t]))

;; Environments are hashes which map variables to values
;; I.e., environments are "finite maps" from variables
;; to values
(define (environment? env)
  (and (andmap symbol? (hash-keys env))
       (andmap value? (hash-values env))))

;; Examples
(environment? (hash 'x 5 'y 8))

;; let's say that lambdas evaluate to themselves
((lambda (x) x) 5)
;; then, (lambda (x) x) evaluates to itself, (lambda (x) x)
;; and callsites first evaluate the function position
;; down to lambda, and then extend the environment to bind
;; the variable x

;; this seems good, but what about this?
;; (((lambda (x) ((lambda (y) x))) 7) 5)
;; if we try evaluating this, we end up with
;; ((lambda (y) x) 5)
;; x ERR -- no binding for x

;; Lesson: lambdas can't just evaluate to themselves
;; We will use a *closure*, which is essentially a pair
;; of the lambda along with an environment used to define
;; the lambda, which gives bindings to the free variables

;; In the environment env, e evaluates to the value v
;; env, e ⇓ v
;; Input is expr?
;; Output is a value?
(define (⇓ e env)
  (match e
    [(? symbol? x) (hash-ref env x)] ;; to evaluate a symbol, look up its value in the environment
    [`(lambda (,x) ,e-body)
     ;; how do I evaluate a lambda?
     `(closure (lambda (,x) ,e-body) ,env)]
    ;; application of functions
    ;; ((lambda (x) 5) 7)
    ;; (((lambda (x) x) (lambda (x) x)) 8)
    [`(,e0 ,e1)
     ;; e0 has to evaluate to a function (i.e., a lambda)
     ;; how does the interpreter evaluate lambdas?
     (match (⇓ e0 env)
       ;; this must evaluate to a closure--if it doesn't, then the user
       ;; was applying something that wasn't a function, and thus
       ;; they made a type error
       [`(closure (lambda (,x) ,e-body) ,env+)
        ;; the environment env+ is the environment that gives bindings
        ;; to the free variables in e-body. When I evaluate e-body
        ;; I *must use* the environment env+, *not* the current env,
        ;; which may have *different* values for variables than env+
        (define v (⇓ e1 env))
        ;; evaluate the closure's body in an environment which extends
        ;; env+ (i.e., the environment *stored by the closure*) with
        ;; a new binding for x ↦ v
        (⇓ e-body (hash-set env+ x v))]
       ;; user tried to apply something that was *not* a lambda
       [_ (error "tried to apply a non-closure value")])]
    [`(let ([,x ,e]) ,e-body)
     ;; first, evaluate e using the current environment
     ;; then, build a new environment which extends the current environment
     ;; with a binding for x to its new value (i.e., the value you got by
     ;; evaluating e). Then, use that new environment to evaluate e-body
     (⇓ e-body (hash-set env x (⇓ e env)))]
    ;; Handling arbitrary numbers of bindings
    [`(let ([,xs ,es] ...) ,e-body)
     (⇓ e-body (foldl (λ (x e env+) (hash-set env+ x (⇓ e env))) env xs es))]
    [(? number? n) n] ;; Const rule
    [`(+ ,e0 ,e1) (+ (⇓ e0 env) (⇓ e1 env))] 
    [`(* ,e0 ,e1) (* (⇓ e0 env) (⇓ e1 env))]
    [`(- ,e0 ,e1) (- (⇓ e0 env) (⇓ e1 env))]
    [`(/ ,e0 ,e1) (/ (⇓ e0 env) (⇓ e1 env))]
    [`(if0 ,e-guard ,e-then ,e-else)
     (if (equal? 0 (⇓ e-guard env))
         (⇓ e-then env)
         (⇓ e-else env))]))

(⇓ '(let ([fac ((lambda (x) (x x))
                (lambda (f)
                  (lambda (x)
                    (if0 x
                         1
                         (* ((f f) (- x 1)) x)))))])
      (fac 20))
   (hash))