3

clisp Lambda Calc で除算関数を実装しようとしています。スタイル

このサイトから、除算のラムダ式を読みました:

Y (λgqab.LT ab (PAIR qa) (g (SUCC q) (SUB ab) b)) 0

これらはTRUEとFALSEです

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

これらは、Int 数と Church 数の間の変換関数です。

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

)

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

私の理解では、この関数は Church Pair を返します。次のように関数 FRST (FRST は正常に動作) で最初の要素を取得しようとすると、次のようになります。

(funcall 最初の 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

問題は DIVISION 関数にあると思います。IF-THEN-ELSE の後、少し変更しようとしましたが (ネストされた括弧の問題だと思いました)、多くのエラーが発生しました。

どんな助けでもいただければ幸いです

ありがとう

4

1 に答える 1

1

あなたの定義にはいくつかの問題があります。

DIVISIONYコンビネータは使用しませんが、元の定義では使用します。 関数はパラメーターDIVISION内にそれ自体のコピーを期待するため、これは重要です。g

ただし、 Y呼び出しを追加した場合でも、コードは機能せず、代わりに無限ループに入ります。これは、今日のほとんどの言語と同様に、CommonLispが値による呼び出し言語であるためです。関数が呼び出される前に、すべての引数が評価されます。これは、従来のラムダ計算のセマンティクスで許可されるほどエレガントに条件関数を定義できないことを意味します。

CommonLispで教会番号の除算を行う1つの方法は次のとおりです。これをもう少し読みやすくするために、いくつかの構文を自由に導入しました。

;;;; -*- 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-20T18:04:13.797 に答える