Y-combinator - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

--
←　前のページに戻る

Yコンビネータ

このデカルトLispは、クロージャや遅延処理機能こそ持ちませんが、高階のλ式を受け取ってλ式を返す機能を持っています。 そのため、Yコンビネータだって平気で実行できます。

ところで、Yコンビネータ(Y Combinator)とは、何でしょうか？

簡単に言い切ってしまうと、無名のλ式だけで再帰プログラムに相当する処理を可能にするものです。

これだけでは何のことかわかりませんね。次項より説明していきましょう。

1. 無名関数（λ式）による再帰処理？

このデカルトLispでは、λ式が中心的な役割を果たします。

さて、λ式は、関数に名前を与えない無名の関数を記述します。

このような、無名の関数だけで、果たして再帰に相当するようなプログラムを書けるでしょうか？ ふつう、再帰するプログラムでは、関数を定義する時にその関数の定義の中で自分自身を呼び出すことによって実現します。

階乗を計算するプログラムで再帰を使いましょう。たとえば、以下のようになります。

(define (factor n)
        (cond
                ((<= 0) n 1)
                (T (* n (factor (- n 1))))
        )
)

factor関数の定義の中で(factor (- n 1)を呼び出しています。 次々と、引数の値から1を引いた値で、factor関数自身を呼び出し、引数が0になったところで1を返します。 値が返ってくると、今度は呼び出した関数に値を返しながら引数を掛けてさらに呼び出した関数へ返します。 結果として、最初に呼び出したときの引数の階乗が答えとして返り、処理が完了します。

しかし、無名のλ式の場合には、文字通り名前のない関数であるため、関数名"factor"に相当するものが存在しません。 だから、その関数自身を呼び出そうにも、名前がないので呼び出しようがないのです。

さて、困りました！

2. コンビネータとは

コンビネータ(combnator)とは、何でしょうか。

調べてみると、自由変数を含まない、束縛変数で構成されるλ式のことのようです。 束縛変数とは、λ式の引数に設定される変数です。 束縛されていない変数は、自由変数と呼びます。

コンビネータには、I, S, Kなどのようにいろいろな種類があります。 そして、コンビネータを組み合わせることによって、任意の式を表すことができます。

ここでは、コンビネータの中でも、興味深い不動点コンビネータとなるYコンビネータに ついて、本文で説明したいと思います。

3. 不動点コンビネータとは

不動点コンビネータとは何でしょうか

まず、不動点とは、数学の用語です。

aが関数f の不動点であるとは、f(a) = a が成り立つことを言います。

つまり、引数に入れた値が、関数を評価した結果が元の値に戻るということです。

では、不動点コンビネータとは、どういうことでしょうか。

実は、不動点コンビネータといってもいくつか種類があります。 ここでは、そのうちの一つである「Yコンビネータ」で説明しましょう。

このYコンビネータには、任意のラムダ式Fに対して

F(YF) = YF

という関係があります。 先ほどの f(a) = a と見比べてみてください。 同じ構造であることがわかります。

ちょっと左右を逆にしてみましょう。

  YF = F(YF)

右辺を見ると左辺と同じYFが見えるのでそれに代入してみましょう。

  YF = F(YF) = F(F(YF))

これは、いくらでも可能です。

  YF = F(YF) = F(F(YF)) = F(F(F(…F(F(YF))…)))

このような性質を持つYをコンビネータとして使うことにより、ラムダ式Fを再帰呼び出ししたのと同等の処理を行わせることができるようになるのです。

4. Yコンビネータとは

ここで説明するYコンビネータとは以下のような形をしています。

  λfλp (f λa ((p p) a))
     λp (f λa ((p p) a))

このλ式が、不動点オペレータであるYコンビネータです。

このYコンビネータをとりあえず、Yという名前で定義します。

(define Y 
  λfλp (f λa ((p p) a))
     λp (f λa ((p p) a)))

そして、階乗を計算するλ式をfactとして定義します。

(define fact 
  λfλn 
        (cond 
          ((<= n 1) 1) 
           (T (* n (f (- n 1))))))

これらの２つの定義により、準備は完了しました。

では、さっそく階乗の計算を試してみましょう。

(define Y 
  λfλp (f λa ((p p) a))
     λp (f λa ((p p) a)))


(define fact 
  λfλn 
        (cond 
          ((<= n 1) 1) 
           (T (* n (f (- n 1))))))

((Y fact) 5) 

上記をファイルに保存して、デカルトLispからloadします。 仮にfactとして保存したとします。

$ descartes lisp-utf8
descartes λ Lisp (c) 2010 H.Niwa
Ready
(load fact)
>  (define Y (λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p)
a)))))))
(λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))))

>  (define fact (λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))))
(λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1)))))))

>  ((Y fact) 5)
120

T

5の階乗が計算されて、120が答えとして出力されています。

でも、これだと、Yとかfactとかの変数を使っていますね。この変数は本当はいらないのではないでしょうか？

今度はYとfactを展開した形で実行しましょう。

Yの値は、上のfactを実行した後にYと打った後にEnterを押せば、LispのS式の形式で表示されます。 複雑なλ式になるので、こちらを使いましょう。

Y
(λ (f) (f ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))) a))

factも同様です。

fact
(λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1)))))))

この２つのS式で表現されたλ関数を組み合わせて、引数をつけて実行してみましょう。 こんな形に組み合わせます。

((Yのλ関数 factのλ関数) 引数)

これでも、階乗の計算が正しく実行されるでしょうか？

(((λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a)))))) (λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1)))))))) 5)
120

こんなに複雑なλ関数なのに、正しく動きました！！！

無名のλ関数であっても、再帰の階乗の処理が実行できると本当に実感できました。

このデカルトLispは、クロージャや遅延処理機能こそ持ちませんが、高階のλ式を受け取ってλ式を返す機能を持っているのでこのような複雑なλ式の処理も正しく実行できます。

では、ここで一つ疑問が浮かびました。

上の階乗のλ関数で、関数に相当する引数以外のλ関数はどういう形に評価されているのでしょうか？

つまり、次に示す関数はどのような形をしているのでしょうか？

(Yのλ関数 factのλ関数)

試してみましょう。

(((λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))))(λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))))

実行結果はこんなことになってしまいます。

(λ (n) (cond ((<= n 1) 1) (T (* n ((λ (n) (cond ((<= n 1) 1) (T (* n ((λ (a)(((λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p) a))) a)) (- n 1)))))) (- n 1))))))

本当にこれで階乗の計算ができるのか、引数をつけて実行してみます。 引数に7をいれて、7の階乗を計算してみましょう。

((λ (n) (cond ((<= n 1) 1) (T (* n ((λ (n) (cond ((<= n 1) 1) (T (* n ((λ (a)(((λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p) a))) a)) (- n 1)))))) (- n 1))))))
7)
5040

本当に計算できてしまいました。 確かに階乗を計算するλ関数となっているようです。 こんなに複雑でもちゃんと計算してくれます。

5. Yコンビネータを使ったその他のプログラム

階乗の計算以外にも、Yコンビネータを使うと再帰を使ったプログラムが作れます。

リストの長さを返すプログラムと、フィボナッチ数を計算するプログラムを作成します。

上で示したように３種類のλ関数の定義方法で示します。比較してみてください。

次のプログラムをファイル"Y-combinator"に保存します。

; Y-combinator for descartes Lisp/ λ

;; Y-combinator

(define Y 
  λfλp (f λa ((p p) a))
     λp (f λa ((p p) a)))


;; factorial
(define fact 
  λfλn 
        (cond 
          ((<= n 1) 1) 
           (T (* n (f (- n 1))))))

((Y fact) 5) 

;; Factorial by λ type 1
(((λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))))
  (λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))))
  6)

;; Factorial by λ type 2
((λ (n) (cond ((<= n 1) 1) (T (* n ((λ (n) (cond ((<= n 1) 1) (T (* n ((λ (a)
(((λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p) a))
 (λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p) a)))
 a)) (- n 1)))))) (- n 1))))))
7)

;; list length

(define length
  λfλl
        (cond 
          ((equal l ()) 0) 
          ((atom l) 1)
          (T (+ (f (cdr l)) 1))))

((Y length) '(a b c)) 

;; length by λ type1
(((λ (f) (f ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))) a))
 (λ (f) (λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ (f (cdr l)) 1))))))
 '(1 2 3 4 5 6 7))

;; length by λ type2
((λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ ((λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ ((λ (a) (((λ (p) ((λ (f) (λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ (f (cdr l)) 1))))) (p p) a)) (λ (p) ((λ (f) (λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ (f (cdr l)) 1))))) (p p) a))) a)) (cdr l)) 1)))) (cdr l)) 1))))
 '(1 2 3 4 5 6 7))

;; Fibonacci number

(define fib
  λfλn 
        (cond 
          ((= n 0) 0) 
          ((= n 1) 1) 
          (T (+ (f (- n 1)) (f (- n 2))))))


((Y fib) 3)

;; Fibonacci by λ type1
(((λ (f) (f ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))) a))
  (λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))))
  4)

;; Fibonacci by λ type2
((λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ ((λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ ((λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)) (- n 1)) ((λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)) (- n 2)))))) (- n 1)) ((λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ ((λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)) (- n 1)) ((λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)) (- n 2)))))) (-
 n 2))))))
  5)

では、まとめて実行した結果を以下に示しましょう。

複雑なλ関数になるので、実行時間も長くなりがちですが気長に結果が出るのを待ってください。

$ descartes -u exapmle/lisp/lisp-utf8
descartes λ Lisp (c) 2010 H.Niwa
Ready
(load "example/lisp/y-combinator/y-combinator-utf8")
>  (define Y (λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p)
a)))))))
(λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))))

>  (define fact (λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))))
(λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1)))))))

>  ((Y fact) 5)
120

>  (((λ (f) ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))))
(λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1)))))))) 6)
720

>  ((λ (n) (cond ((<= n 1) 1) (T (* n ((λ (n) (cond ((<= n 1) 1) (T (* n ((λ
(a) (((λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p)
 a)) (λ (p) ((λ (f) (λ (n) (cond ((<= n 1) 1) (T (* n (f (- n 1))))))) (p p)
a))) a)) (- n 1)))))) (- n 1)))))) 7)
5040

>  (define length (λ (f) (λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ (f (
cdr l)) 1))))))
(λ (f) (λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ (f (cdr l)) 1)))))

>  ((Y length) (quote (a b c)))
3

>  (((λ (f) (f ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))
) a)) (λ (f) (λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ (f (cdr l)) 1)))
))) (quote (1 2 3 4 5 6 7)))
7

>  ((λ (l) (cond ((equal l ()) 0) ((atom l) 1) (T (+ ((λ (l) (cond ((equal l (
)) 0) ((atom l) 1) (T (+ ((λ (a) (((λ (p) ((λ (f) (λ (l) (cond ((equal l ())
 0) ((atom l) 1) (T (+ (f (cdr l)) 1))))) (p p) a)) (λ (p) ((λ (f) (λ (l) (co
nd ((equal l ()) 0) ((atom l) 1) (T (+ (f (cdr l)) 1))))) (p p) a))) a)) (cdr l)
) 1)))) (cdr l)) 1)))) (quote (1 2 3 4 5 6 7)))
7

>  (define fib (λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (
f (- n 2))))))))
(λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2)))))))


>  ((Y fib) 3)
2

>  (((λ (f) (f ((λ (p) (f (λ (a) ((p p) a)))) (λ (p) (f (λ (a) ((p p) a))))
) a)) (λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2)
))))))) 4)
3

>  ((λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ ((λ (n) (cond ((= n 0) 0) ((= n
 1) 1) (T (+ ((λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (
T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((= n
 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)) (- n 1)) ((
λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)
) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1)
 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)) (- n 2)))))) (- n 1)) ((λ
 (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ ((λ (a) (((λ (p) ((λ (f) (λ (n) (co
nd ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p)
((λ (f) (λ (n) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))
) (p p) a))) a)) (- n 1)) ((λ (a) (((λ (p) ((λ (f) (λ (n) (cond ((= n 0) 0)
((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a)) (λ (p) ((λ (f) (λ (n
) (cond ((= n 0) 0) ((= n 1) 1) (T (+ (f (- n 1)) (f (- n 2))))))) (p p) a))) a)
) (- n 2)))))) (- n 2)))))) 5)
5

T
Ready