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

Question

Я пытаюсь реализовать функцию разделения с кликсом Lambda Calc. Стиль

Я прочитал от this сайта, что лямбда-выражение деления: (. λgqab LT AB (ПАР QA) (г (SUCC д) (SUB AB) б))

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

) 

Это мой IF-THEN-ELSE Реализация

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

И это моя реализация ДИВ

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

) 

PAIR, SUCC и функции SUB работают нормально. Я поставил свои церковные номера до как этот

(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 работает нормально), как это:

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

Если я пытаюсь получить прерывания INT значение с Church2int (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

Я думаю, что проблема в функции DIVISION, после IF-THEN-ELSE, я попытался изменить его немного (я думал, что это вложенная проблема скобки), но У меня много ошибок.

Любая помощь будет оценена

Благодаря

Answer 1

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

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

Однако, даже если вы добавили призыв , ваш код все равно не будет работать , но вместо этого перейдите в бесконечный цикл. Это потому, что 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