Skip to content

Instantly share code, notes, and snippets.

@ilammy

ilammy/lc.scm Secret

Created Apr 7, 2014
Embed
What would you like to do?
Интерпретатор бестипового лямбда-исчисления на 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