02-27.rkt

;; CIS352 -- Feb 27, 2023
;; Definitional interpreters for Scheme (warmup to e3)
#lang racket

(define (expr? e)
  (match e
    [(? number? n) #t]
    [`(+ ,(? expr? e0) ,(? expr? e1)) #t]
    [(? symbol? x) #t]
    ;; (let ([x (+ y z)]) x)
    ;; here, x would match to 'x
    ;; e would match to '(+ y z)
    ;; e-body would match to 'x
    [`(let ([,(? symbol? x) ,(? expr? e)]) ,(? expr? e-body)) #t]
    [`(lambda (,(? symbol? x)) ,(? expr? e)) #t]
    [`(,(? expr? e0) ,(? expr? e1)) #t]
    [_ #f]))

;; we add env to our interp function
;; env is going a hash mapping symbols (how we will represent variables)
;; to values (the runtime representation of objects in our langauge)
(define (interp e env)
  (pretty-print e)
  (match e
    [(? number? n) n]
    [(? symbol? x) (hash-ref env x)]
    ;; another way to implement let -- I will shadow the next definition
    [`(let ([,(? symbol? x) ,(? expr? e)]) ,(? expr? e-body))
     (interp `((lambda (,x) ,e-body) ,e) env)]
    [`(let ([,(? symbol? x) ,(? expr? e)]) ,(? expr? e-body))
     ;; first evaluate e by calling interp using the current environment env
     ;; then evalute e-body in a *new* environment, that extends env
     ;; with a new binding for x to the value of the interpreted expression
     ;; e
     (define v (interp e env))
     (define new-env (hash-set env x v))
     (interp e-body new-env)]
    [`(+ ,e0 ,e1) (+ (interp e0 env) (interp e1 env))]
    [`(lambda (,x) ,e-body)
     ;; this will allocate / build a closure, which will bundle up this code (i.e., the lambda
     ;; expression), along with the current environment
     `(closure ,e ,env)]
    ;; a function call, we know it wasn't +, so it must be a closure
    [`(,e0 ,e1)
     ;; e0 is the function
     (match (interp e0 env)
       ;; assume this gives me back a closure--if not, something is seriously wrong
       ;; they tried to call something that was not a function.
       [`(closure (lambda (,x) ,e-body) ,env+)
        ;; here x is the argument of the closure we got after evluating e0
        ;; e-body is the body of the closure we got after evaluation e0
        ;; env is environment that was alive when the closure was created.
        ;; To respect static/lexical scoping, we evaluate e-body in the 
        ;; environment that was alive at the time the lambda was constructed
        ;; except, we need to add a binding for x
        (interp e-body (hash-set env+ x (interp e1 env)))]
       [_ (interp '(let ([f 5]) (f 3)) (hash 'z 8))(error "application: not a procedure")])]
    [_ (error "can't process this (yet?)")]))

;; ((lambda (x) (lambda (y) x)) 5)
;; let's say we call the return value
;; (lambda (y) x)

;; Issue: if you use an explicit environment, and not substitution
;; then you "forget" the values of bound variables when lambdas
;; escape and return from calls.

;; A "closure" is a representation of code + data, more specifically,
;; it's a lambda plus the environment that existed when that lambda
;; was created 


;; Let can be thought of as a "left-left lambda" which is a lambda
;; that is immediately applied
(let ([x 5]) (let ([y (+ x 2)]) (+ y x)))
;; translate every binder to a lambda, and then take the thing being
;; bound and make that the argument to the lambda which is immediately applied
((lambda (x) ((lambda (y) (+ x 2)) (+ x 2))) 5)

e3.rkt

#lang racket

;; Exercise 3: A CE (Control and Environment) interpreter for Scheme

;; NOTE: You *MAY* collaborate with other students on this exercise,
;; but *not* the later project. Feel free to work with up to two other
;; students (groups of three) and submit the same code as them. Use
;; that code to begin your solution for p3.

;; Name: ________________________________
;; Collaborator 1: ________________________________
;; Collaborator 2: ________________________________
(provide interp-ce)

; Interp-ce must correctly interpret any valid scheme-ir program and yield the same value
; as DrRacket, except for closures which must be represented as `(closure ,lambda ,environment).
; (+ 1 2) can return 3 and (cons 1 (cons 2 '())) can yield '(1 2). For programs that result in a 
; runtime error, you should return `(error ,message)---giving some reasonable string error message.
; Handling errors and some trickier cases will give bonus points. 
(define (interp-ce exp)
  (define (interp env exp)
    (match exp
      [(or (? number?) (? boolean?)) exp]
      [`(let ([,x ,rhs]) ,body)
       (interp (hash-set env x (interp env rhs)) body)]
      [`(lambda (,arg) ,body)
       `(closure (lambda (,x) ,body) ,env)] ;; closures have a lambda + environment
      [(? symbol? x)
       (hash-ref env x)]
      [`(if ,ge ,te ,fe)
       (if (interp env ge)
           (interp env te)
           (interp env fe))]
      ;; not required, but you may want to add this
      #;[`(apply-prim ,op ,x)
       'todo]
      [`(,ef ,earg)
       (match (interp env ef)
         [`(closure (lambda (,x) ,e-body) ,env+)
          (define v-a (interp env earg))
          (interp e-body (hash-set env+ x v-a))])]))
  ;; TODO: update?
  (define starting-env (hash))
  (interp starting-env exp))