CLISP Lambda Calculus Div Mise en œuvre

Question

J'essaie de mettre en œuvre une fonction Division avec Lambda Calc clisp. le style

I lu à partir du site this que l'expression lambda d'une division est la suivante: (. λgqab LT ab (PAIR qa) (g (Succ q) (SUB ab) b))

Y 0

Ce sont VRAI et FAUX

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

Ce sont des fonctions de conversion entre les numéros Int et Eglise

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

) 

Ceci est ma mise en œuvre 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)))))) 
) 

Et voici ma mise en œuvre 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)) 
        ))))) 

) 

PAIR, succ et fonctions SUB fonctionne bien. Je mets mes numéros d'église comme ça

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

Alors je fais:

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

Et j'ai:

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

Pour ce que je comprends, cette fonction retourne une Eglise paire . Si je tente d'obtenir le premier élément avec une FRST fonction (FRST fonctionne bien) comme ceci:

(funcall FRST D)

J'ai

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

Si j'essaie d'obtenir la valeur int avec Church2int (fonctionne Church2int OK) comme ceci:

(church2int (funcall frst D)) 

J'ai

*** - +: 
     #<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 

Où devrais-je recevoir 3

Je pense que le problème est en fonction de la division, après l'IF-THEN-ELSE, j'ai essayé de changer un peu (je pensais qu'il était un problème de parenthèses imbriquées) mais J'ai eu beaucoup d'erreurs.

Toute aide serait appréciée

Merci

Answer 1

Il y a plusieurs problèmes avec votre définition.

DIVISION n'utilise pas le combinateur Y, mais la définition d'origine le fait. Ceci est important car la fonction DIVISION attend une copie de lui-même dans le paramètre g .

Cependant, même si vous avez ajouté l'invocation Y, votre code ne fonctionnera toujours pas mais utilisera plutôt une boucle infinie. C'est parce que Common Lisp, comme la plupart des langages d'aujourd'hui, est un langage call-by-value. Tous les arguments sont évalués avant qu'une fonction ne soit appelée. Cela signifie que vous ne pouvez pas définir des fonctions conditionnelles aussi élégamment que la sémantique traditionnelle du lambda-calcul le permet.

Voici une façon de faire la division des numéros d'église en Common Lisp. J'ai pris la liberté d'introduire une certaine syntaxe pour que ce soit un peu plus lisible.

;;;; -*- 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}) 

Si vous mettez cela dans un fichier, vous pouvez le faire:

[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