CLISP Lambda微積分Div執行

我試圖用clisp Lambda Calc實現一個Division功能。風格CLISP Lambda微積分Div執行

我從this站點讀取的分割的lambda表達式爲：（。λgqabLT AB（PAIR QA）（克（SUCC Q）（SUB AB）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)))))) 

)

這是我的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)))))) 
)

，這是我的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和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)))>

如果我試圖讓與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

我認爲這個問題是在分割功能，在IF-THEN-ELSE後，我試圖改變它一點點（我認爲這是一個嵌套的括號問題），但我有很多錯誤。

任何幫助，將不勝感激

感謝

來源

2012-11-24 Ivan

有幾個問題與你的定義。

DIVISION不使用Y組合，但原來的定義。這很重要，因爲DIVISION函數需要參數g 中的一個副本。

但是，即使您添加了Y調用，您的代碼仍然不會運行，但是會進入無限循環。這是因爲與當今大多數語言一樣，Common Lisp是一種按價值計算的語言。所有參數在函數調用之前進行評估。這意味着你不能像傳統的lambda演算語義所允許的那樣優雅地定義條件函數。

以下是在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

來源

2012-12-20 18:04:13

CLISP Lambda微積分Div執行

回答

相關問題