Реализация CLISP Lambda Calculus Div

Есть несколько проблем с вашим определением.

DIVISION не использует комбинатор Y, но используется в исходном определении. Это важно, потому что функция DIVISION ожидает свою копию в параметре g.

Однако, даже если вы добавите вызов Y, ваш код все равно не будет работать, а вместо этого войдет в бесконечный цикл. Это потому, что Common Lisp, как и большинство современных языков, является языком вызова по значению. Все аргументы оцениваются перед вызовом функции. Это означает, что вы не можете определить условные функции так элегантно, как это позволяет традиционная семантика лямбда-исчисления.

Вот один из способов деления церковных чисел в Common Lisp. Я позволил себе ввести некоторый синтаксис, чтобы сделать его немного более читабельным.

;;;; -*- coding: utf-8 -*-
;;;; --- preamble, define lambda calculus language

(cl:in-package #:cl-user)

(defpackage #:lambda-calc
  ;; note: not using common-lisp package
  (:use)
  (:export #:λ #:call #:define))

;; (lambda-calc:λ (x y) body)
;;   ==> (cl:lambda (x) (cl:lambda (y) body))
(defmacro lambda-calc:λ ((arg &rest more-args) body-expr)
  (labels ((rec (args)
             (if (null args)
               body-expr
               `(lambda (,(car args))
                  (declare (ignorable ,(car args)))
                  ,(rec (cdr args))))))
    (rec (cons arg more-args))))

;; (lambda-calc:call f a b)
;;   ==> (cl:funcall (cl:funcall f a) b)
(defmacro lambda-calc:call (func &rest args)
  (labels ((rec (args)
             (if (null args)
               func
               `(funcall ,(rec (cdr args)) ,(car args)))))
    (rec (reverse args))))

;; Defines top-level lexical variables
(defmacro lambda-calc:define (name value)
  (let ((vname (gensym (princ-to-string name))))
    `(progn
       (defparameter ,vname nil)
       (define-symbol-macro ,name ,vname)
       (setf ,name
             (flet ((,vname () ,value))
               (,vname))))))

;; Syntax: {f a b}
;;   ==> (lambda-calc:call f a b)
;;   ==> (cl:funcall (cl:funcall f a) b)
(eval-when (:compile-toplevel :load-toplevel :execute)
  (set-macro-character #\{
                       (lambda (stream char)
                         (declare (ignore char))
                         `(lambda-calc:call
                            ,@(read-delimited-list #\} stream t))))
  (set-macro-character #\} (get-macro-character #\))))

;;;; --- end of preamble, fun starts here

(in-package #:lambda-calc)

;; booleans
(define TRUE
  (λ (x y) x))
(define FALSE
  (λ (x y) y))
(define NOT
  (λ (bool) {bool FALSE TRUE}))

;; numbers
(define ZERO
  (λ (f x) x))
(define SUCC
  (λ (n f x) {f {n f x}}))
(define PLUS
  (λ (m n) {m SUCC n}))
(define PRED
  (λ (n f x)
    {n (λ (g h) {h {g f}})
       (λ (u) x)
       (λ (u) u)}))
(define SUB
  (λ (m n) {n PRED m}))

(define ISZERO
  (λ (n) {n (λ (x) FALSE) TRUE}))
(define <=
  (λ (m n) {ISZERO {SUB m n}}))
(define <
  (λ (m n) {NOT {<= n m}}))

(define ONE   {SUCC ZERO})
(define TWO   {SUCC ONE})
(define THREE {SUCC TWO})
(define FOUR  {SUCC THREE})
(define FIVE  {SUCC FOUR})
(define SIX   {SUCC FIVE})
(define SEVEN {SUCC SIX})
(define EIGHT {SUCC SEVEN})
(define NINE  {SUCC EIGHT})
(define TEN   {SUCC NINE})

;; combinators
(define Y
  (λ (f)
    {(λ (rec arg) {f {rec rec} arg})
     (λ (rec arg) {f {rec rec} arg})}))

(define IF
  (λ (condition if-true if-false)
    {{condition if-true if-false} condition}))

;; pairs
(define PAIR
  (λ (x y select) {select x y}))
(define FIRST
  (λ (pair) {pair TRUE}))
(define SECOND
  (λ (pair) {pair FALSE}))

;; conversion from/to lisp integers
(cl:defun int-to-church (number)
  (cl:if (cl:zerop number)
    zero
    {succ (int-to-church (cl:1- number))}))
(cl:defun church-to-int (church-number)
  {church-number #'cl:1+ 0})

;; what we're all here for
(define DIVISION
  {Y (λ (recurse q a b)
       {IF {< a b}
           (λ (c) {PAIR q a})
           (λ (c) {recurse {SUCC q} {SUB a b} b})})
     ZERO})

Если вы поместите это в файл, вы можете сделать:

[1]> (load "lambdacalc.lisp")
;; Loading file lambdacalc.lisp ...
;; Loaded file lambdacalc.lisp
T
[2]> (in-package :lambda-calc)
#<PACKAGE LAMBDA-CALC>
LAMBDA-CALC[3]> (church-to-int {FIRST {DIVISION TEN FIVE}})
2
LAMBDA-CALC[4]> (church-to-int {SECOND {DIVISION TEN FIVE}})
0
LAMBDA-CALC[5]> (church-to-int {FIRST {DIVISION TEN FOUR}})
2
LAMBDA-CALC[6]> (church-to-int {SECOND {DIVISION TEN FOUR}})
2