From 3eb4346a1a250eca9e4cf52a9d7ba78ea8e11496 Mon Sep 17 00:00:00 2001
From: JJ
Date: Tue, 14 May 2024 18:32:38 -0700
Subject: implement the simply-typed lambda calculus

---
 lc.rkt | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
 create mode 100644 lc.rkt

(limited to 'lc.rkt')

diff --git a/lc.rkt b/lc.rkt
new file mode 100644
index 0000000..06fb7eb
--- /dev/null
+++ b/lc.rkt
@@ -0,0 +1,24 @@
+#lang racket
+(require "lib.rkt")
+
+;; the untyped lambda calculus
+
+(define (interpret expr [ctx #hash()])
+  (match expr
+    [val #:when (or (number? val) (string? val)) val]
+    [val #:when (symbol? val)
+      (with-handlers
+        ([exn:fail? (λ (exn) val)]) ; note: unbound identifiers are supported
+        (interpret (dict-ref ctx val) ctx))]
+    [`(λ ,id ,body) `(λ ,id ,body)]
+    [`(,body ,arg)
+      (match (interpret body ctx)
+        [`(λ ,id ,body) (interpret body (dict-set ctx id (interpret arg ctx)))]
+        [expr `(,(interpret expr ctx) ,(interpret arg ctx))])]
+    [expr (err (format "unknown expression ~a" expr))]))
+
+(require rackunit)
+(check-equal? (interpret '(λ x x)) '(λ x x))
+(check-equal? (interpret '((λ a a) (x y))) '(x y))
+(check-equal? (interpret '((λ a (x y)) (λ z z))) '(x y))
+(check-equal? (interpret '((λ a (a y)) x)) '(x y))
-- 
cgit v1.2.3-70-g09d2