CLISP Lambda演算Div实现

Question

我试图用实现一个除法函数。风格

我从这站点上看到一个部门的lambda表达式是：

Y (λgqab.LT a b(对q) (g (SUCC Q) (SUB b) b)) 0

这些都是对的和假的

(defvar TRUE #'(lambda(x)#'(lambda(y)x)))
(defvar FALSE #'(lambda(x)#'(lambda(y)y)))

这些是Int和教堂编号之间的转换函数。

(defun church2int(numchurch)
    (funcall (funcall numchurch #'(lambda (x) (+ x 1))) 0)
)
(defun int2church(n)
    (cond
        ((= n 0) #'(lambda(f) #'(lambda(x)x)))
        (t #'(lambda(f) #'(lambda(x) (funcall f
            (funcall(funcall(int2church (- n 1))f)x))))))

)

这是我的“如果-然后-否则”实现。

(defvar IF-THEN-ELSE
    #'(lambda(c)
        #'(lambda(x)
            #'(lambda(y)
                #'(lambda(acc1)
                    #'(lambda (acc2)
                        (funcall (funcall (funcall (funcall c x) y) acc1) acc2))))))
)

这是我的div实现

(defvar division
    #'(lambda (g)
        #'(lambda (q)
            #'(lambda (a)
                #'(lambda (b)
                    (funcall (funcall (funcall (funcall (funcall IF-THEN-ELSE LT) a) b)
                        (funcall (funcall PAIR q)a))
                        (funcall (funcall g (funcall succ q)) (funcall (funcall sub a)b))
                    )))))

)

对，SUCC和子函数工作良好。我把我的教堂编号设成这样

(set six (int2church 6))
(set two (int2church 2))

那我就做：

(setq D (funcall (funcall division six) two))

我有：

#<FUNCTION :LAMBDA (A)
  #'(LAMBDA (B)
     (FUNCALL (FUNCALL (FUNCALL (FUNCALL (FUNCALL IF-THEN-ELSE LT) A) B) (FUNCALL (FUNCALL PAR Q) A))
      (FUNCALL (FUNCALL G (FUNCALL SUCC Q)) (FUNCALL (FUNCALL SUB A) B))))>

据我所知，这个功能返回一对教会。如果我尝试使用函数FRST (FRST工作正常)获得第一个元素，如下所示：

(功能为D级)

我有

#<FUNCTION :LAMBDA (B)
  (FUNCALL (FUNCALL (FUNCALL (FUNCALL (FUNCALL IF-THEN-ELSE LT) A) B) (FUNCALL (FUNCALL PAR Q) A))
   (FUNCALL (FUNCALL G (FUNCALL SUCC Q)) (FUNCALL (FUNCALL SUB A) B)))>

如果我试图用Church2int获得int值(Church2int工作正常)，如下所示：

(church2int (funcall frst D))

我有

*** - +:
       #<FUNCTION :LAMBDA (N)
         #'(LAMBDA (F)
            #'(LAMBDA (X)
               (FUNCALL (FUNCALL (FUNCALL N #'(LAMBDA (G) #'(LAMBDA (H) (FUNCALL H (FUNCALL G F))))) #'(LAMBDA (U) X)) (LAMBDA (U) U))))>
      is not a number

在那里我期望得到3

我认为问题在除法函数中，如果-然后-否则，我尝试修改它一点点(我认为它是一个嵌套括号问题)，但我有很多错误。

如能提供任何帮助，将不胜感激。

谢谢

Answer 1

你的定义有几个问题。

DIVISION不使用Y组合器，但原始定义使用。这一点很重要，因为DIVISION函数在g参数中需要自己的一个副本。

但是，即使您添加了Y调用，您的代码仍然无法工作，而是进入无限循环。这是因为Common和当今大多数语言一样，是一种按值调用的语言。所有参数都是在调用函数之前计算的。这意味着您不能像传统的lambda演算语义所允许的那样优雅地定义条件函数。

这里有一种在普通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