Интерпретатор бестипового лямбда-исчисления на Scheme
(define-library (lc) | |
(import (scheme base) | |
(only (srfi 1) first second third) ) | |
(export term? eval) | |
(begin | |
;; Dispatcher | |
(define (eval exp env) | |
(cond ((ref? exp) (eval-ref exp env)) | |
((lam? exp) (eval-lam (first (second exp)) (third exp) env)) | |
((app? exp) (eval-app (first exp) (second exp) env)) | |
(else (error "eval: syntax error" exp)) ) ) | |
;; Syntax | |
(define (term? exp) | |
(or (ref? exp) (lam? exp) (app? exp)) ) | |
(define (ref? exp) (symbol? exp)) | |
(define (lam? exp) | |
(and (list-of? 3 exp) | |
(eqv? 'lambda (first exp)) | |
(list-of? 1 (second exp)) | |
(symbol? (first (second exp))) | |
(term? (third exp)) ) ) | |
(define (app? exp) | |
(and (list-of? 2 exp) | |
(term? (first exp)) | |
(term? (second exp)) ) ) | |
;; Semantics | |
(define (eval-ref var env) | |
(lookup var env) ) | |
(define (eval-lam var exp env) | |
(lambda (arg) | |
(eval exp (bind var arg env)) ) ) | |
(define (eval-app fun arg env) | |
((eval fun env) (eval arg env)) ) | |
;; Environments | |
(define (bind var val env) | |
(cons (cons var val) env) ) | |
(define (lookup var env) | |
(let ((cell (assq var env))) | |
(if cell (cdr cell) | |
(error "lookup: unbound variable" var) ) ) ) | |
;; Utils | |
(define (list-of? len list) | |
(and (list? list) (= len (length list))) ) | |
) ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment