Редукция лямбда-термов разными стратегиями - Lisp

(printLn "Редукция лямбда-термов:")
 
(defn appl (t1 t2)
    (def arg (car t1))
    (def v (cond (eq? "normal" reduct-type) t2 (reduce t2 "аргумент: ")))
    (def r (map (lambda (x) (cond (eq? x arg) v x)) (cdr t1)))
    (cond (eq? '. (car r)) (cdr r) r))
 
(defn is-lambda? (l) (cond (atom? l) False (elem '. l)))
 
(defn reduce (l trace) (cond (atom? l) l (
    (cond (eq? "" trace) 0 ((print trace) (printLn l)))
    (def f (reduce (car l) "первый подтерм: "))
    (cond (= 1 (length l)) f
          (is-lambda? f)
              (reduce (cons (appl f (car (cdr l))) (cdr (cdr l))) "применение: ")
          (map (lambda (x) (reduce x "")) l) ))))
 
(def reduct-type "normal")
(defn test (t)
    (printLn "") (print "Редукция терма: ") (printLn t)
    (defn go ()
        (printLn "")
        (print (cond (eq? "normal" reduct-type) "Нормальная" "Аппликативная"))
        (printLn " стратегия:")
        (def r (reduce t "Исходный терм: "))
        (print "Результат: ") (printLn r))
    (set! reduct-type "normal") (go)
    (set! reduct-type "applic") (go))
 
(test '((x y z . x z y) (x y . / x y) ((x . x) 3) 9))
(test '((((x y z . x z y) (x y . / x y)) ((x . x) 3)) 9))
(test '((x . a x) ((y . b y) c)))

Редукция лямбда-термов:
 
Редукция терма: ((x y z . x z y) (x y . / x y) ((x . x) 3) 9)
 
Нормальная стратегия:
Исходный терм: ((x y z . x z y) (x y . / x y) ((x . x) 3) 9)
первый подтерм: (x y z . x z y)
применение: ((y z . (x y . / x y) z y) ((x . x) 3) 9)
первый подтерм: (y z . (x y . / x y) z y)
применение: ((z . (x y . / x y) z ((x . x) 3)) 9)
первый подтерм: (z . (x y . / x y) z ((x . x) 3))
первый подтерм: (x . x)
применение: ((3))
первый подтерм: (3)
применение: (((x y . / x y) 9 3))
первый подтерм: ((x y . / x y) 9 3)
первый подтерм: (x y . / x y)
применение: ((y . / 9 y) 3)
первый подтерм: (y . / 9 y)
применение: ((/ 9 3))
первый подтерм: (/ 9 3)
Результат: (/ 9 3)
 
Аппликативная стратегия:
Исходный терм: ((x y z . x z y) (x y . / x y) ((x . x) 3) 9)
первый подтерм: (x y z . x z y)
аргумент: (x y . / x y)
применение: ((y z . (x y . / x y) z y) ((x . x) 3) 9)
первый подтерм: (y z . (x y . / x y) z y)
аргумент: ((x . x) 3)
первый подтерм: (x . x)
применение: ((3))
первый подтерм: (3)
применение: ((z . (x y . / x y) z 3) 9)
первый подтерм: (z . (x y . / x y) z 3)
применение: (((x y . / x y) 9 3))
первый подтерм: ((x y . / x y) 9 3)
первый подтерм: (x y . / x y)
применение: ((y . / 9 y) 3)
первый подтерм: (y . / 9 y)
применение: ((/ 9 3))
первый подтерм: (/ 9 3)
Результат: (/ 9 3)
 
Редукция терма: ((((x y z . x z y) (x y . / x y)) ((x . x) 3)) 9)
 
Нормальная стратегия:
Исходный терм: ((((x y z . x z y) (x y . / x y)) ((x . x) 3)) 9)
первый подтерм: (((x y z . x z y) (x y . / x y)) ((x . x) 3))
первый подтерм: ((x y z . x z y) (x y . / x y))
первый подтерм: (x y z . x z y)
применение: ((y z . (x y . / x y) z y))
первый подтерм: (y z . (x y . / x y) z y)
применение: ((z . (x y . / x y) z ((x . x) 3)))
первый подтерм: (z . (x y . / x y) z ((x . x) 3))
первый подтерм: (x . x)
применение: ((3))
первый подтерм: (3)
применение: (((x y . / x y) 9 3))
первый подтерм: ((x y . / x y) 9 3)
первый подтерм: (x y . / x y)
применение: ((y . / 9 y) 3)
первый подтерм: (y . / 9 y)
применение: ((/ 9 3))
первый подтерм: (/ 9 3)
Результат: (/ 9 3)
 
Аппликативная стратегия:
Исходный терм: ((((x y z . x z y) (x y . / x y)) ((x . x) 3)) 9)
первый подтерм: (((x y z . x z y) (x y . / x y)) ((x . x) 3))
первый подтерм: ((x y z . x z y) (x y . / x y))
первый подтерм: (x y z . x z y)
аргумент: (x y . / x y)
применение: ((y z . (x y . / x y) z y))
первый подтерм: (y z . (x y . / x y) z y)
аргумент: ((x . x) 3)
первый подтерм: (x . x)
применение: ((3))
первый подтерм: (3)
применение: ((z . (x y . / x y) z 3))
первый подтерм: (z . (x y . / x y) z 3)
применение: (((x y . / x y) 9 3))
первый подтерм: ((x y . / x y) 9 3)
первый подтерм: (x y . / x y)
применение: ((y . / 9 y) 3)
первый подтерм: (y . / 9 y)
применение: ((/ 9 3))
первый подтерм: (/ 9 3)
Результат: (/ 9 3)
 
Редукция терма: ((x . a x) ((y . b y) c))
 
Нормальная стратегия:
Исходный терм: ((x . a x) ((y . b y) c))
первый подтерм: (x . a x)
применение: ((a ((y . b y) c)))
первый подтерм: (a ((y . b y) c))
первый подтерм: (y . b y)
применение: ((b c))
первый подтерм: (b c)
Результат: (a (b c))
 
Аппликативная стратегия:
Исходный терм: ((x . a x) ((y . b y) c))
первый подтерм: (x . a x)
аргумент: ((y . b y) c)
первый подтерм: (y . b y)
применение: ((b c))
первый подтерм: (b c)
применение: ((a (b c)))
первый подтерм: (a (b c))
Результат: (a (b c))