Created
March 1, 2022 01:22
-
-
Save kmicinski/89043871dc380796868c4cce8aa3b13c 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
;; Closure-Creating Interpreters in Racket | |
#lang racket | |
;; expressions comprise the λ-calculus extended | |
;; to include numeric constants and the + builtin | |
(define (expr? e) | |
(match e | |
[(? number? n) #t] | |
[`(+ ,(? expr? e0) ,(? expr? e1)) #t] | |
[(? symbol? x) #t] | |
[`(lambda (,(? symbol? x)) ,(? expr? e)) #t] | |
[`(,(? expr? e0) ,(? expr? e1)) #t])) | |
;; values are either numbers or closures | |
(define (value? v) | |
(match v | |
[(? number? n) #t] | |
[`(closure ,(? expr? e) ,(? environment?)) #t])) | |
;; environments are mapping from variables to values | |
(define environment? (hash/c symbol? value?)) | |
;; the interpreter takes an expression and environment | |
;; (used for variable lookup) and produces a value | |
(define/contract (interp expr env) | |
(-> expr? environment? value?) | |
(match expr | |
[(? number? n) n] | |
[(? symbol? x) (hash-ref env x)] | |
[`(lambda (,x) ,e) `(closure ,expr ,env)] | |
[`(+ ,e0 ,e1) | |
(let* ([v0 (interp e0 env)] | |
[v1 (interp e1 env)]) | |
(+ v0 v1))] | |
[`(,e0 ,e1) | |
(let ([clo-to-apply (interp e0 env)]) | |
(match clo-to-apply | |
[`(closure (lambda (,x) ,e-body) ,env+) | |
(interp e-body (hash-set env+ x (interp e1 env)))] | |
[_ (error "expected to apply a closure")]))])) | |
;; running a program is simply running an expression | |
;; with the empty environment--this will work when | |
;; the program is closed (no free vars) | |
(define (run e) | |
(interp e (hash))) | |
;; As an example... | |
(run '(((lambda (y) (lambda (x) (y x))) (lambda (z) (+ z 5))) 4)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment