Интерпретатор бестипового лямбда-исчисления на Scheme

lc.scm

(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))) )
) )