Created
February 27, 2024 17:21
-
-
Save kmicinski/c8efee32697c87b2364e7e2a84eb0a54 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; 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) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment