Lisperの為のSmalltalkが飛ばしてる件について

なんで急に Y combinator なんて出てきたかというと、なにげなく仕事をサボって気分転換に読んでたこのページがきっかけです。

Smalltalk for Lispers -Smalltalk/X Programmers guide


タイトルから SmalltalkLisp の文法比較かな、と思って読み始めたのですが、最初は確かにそんな感じだったのだけれど、下の方にいくに連れなにやら雲行きが怪しくなってきて、結局行き着いた先は 関数で自然数を表現するところから始まるバリバリのlambda抽象のお話──去年流行った おとうさん、ぼくにもYコンビネータがわかりましたよ! -きしだのはてなSmalltalk版みたいな感じでした (^^;


で、その中に

Y := [:f |
	    [:x |
	      [:y |
		 f value:(x value:x)]]
	    value:
	      [:x |
		[:y |
		  f value:(x value:x)]]].

みたいな Y combinator があって、これがとてもすっきりしていて読みやすい。

あんまりカッコイイので、「凄いよこのSmalltalk/X!さすが Smalltalk/A のお兄さん!!」・・みたいに盛り上がってしまったのだけれども、よくよくみれば、あれれ、なにこれ、なんか変です?(:yってなんです??)

でも Y combinator 自体の理解度がいまいちだったので 何が変だかチンプンカンプン。そこでちゃんと自分で Y combinator 書いて覚えよう!・・というのが今回の次第です(←仕事中になにやってるんだか^^;)。

さて、せっかくなので件のページの問題の項「For the curious: Lambda Calculus in Smalltalk」を軽くなぞってみます(翻訳・・じゃないのがチキンです)。ちなみに原文は Smalltalk/X 対象(というか、Smalltalk/X 自体のユーザーズガイド)なのですが、手元にあったのは GNU Smalltalk で、少々コードが違ってますが、そこらへんはご容赦です。


* * *


まずは基本の基本。Smalltalk では、

lambda x.B.

[:x | B]

のように書きます。

( lambda x.x 5 )

[:x | x] value: 5

です。

というわけで単位元

IDENTITY := [:x | x].
(IDENTITY value: 'hello world') printNl. "=> 'hello world'"

ですね。・・といったところでウォーミングアップは終了。

早速、boolean と 条件式を作ってみましょう。

T := [:x | 
       [:y |
           x ]].

F := [:x | 
       [:y |
           y ]].

IF := [:b | 
        [:x |
           [:y |
              (b value:x) value: y ]]].

T や F や IF はワークスペース変数です。処理系依存ですが、GNU SmalltalkSqueak の場合は 何も考えないでこのままコードを評価すれば 勝手に変数が作られます。

早速テスト。

(((IF value: T) value: 'then') value: 'else') printNl.
(((IF value: F) value: 'then') value: 'else') printNl.
'then'
'else'

おー。らしく動きます。True は 与えられた二つの引数のうち最初の引数を、False は二つ目の引数を返す関数です。で、If は この定義した Boolean に 二つの引数を渡してあげる関数になっています。

・・って、これは Smalltalk ネイティブの #ifTrue:ifFalse: そのまんまですね。(あんまり有り難味無いなぁ)

で、引き続き 否定を定義します。あとラムダ抽象な論理値ですが、この先表示できないと何が何ださっぱりで困るので、今のうちにSmalltalk で表示するブリッジな関数を作っておきます(もちろんこれはラムダ計算じゃないよ)。

NOT := [:b | ((IF value: b) value: F) value: T].
printBool := [:f | ((IF value: f) value: 'true') value: 'false'].

テスト。

(printBool value: T) printNl.
(printBool value: F) printNl.
(printBool value: (NOT value: T)) printNl.
(printBool value: (NOT value: F)) printNl.
'true'
'false'
'false'
'true'

お次は Pair を作ります。と言われると「なんのこと?」「なんでこんなに最初につくるの?」感が漂いますが、cons と car, cdr と言われれば、超重要!さっさと作らなきゃ!!・・ですね。

PAIR := [:a |
          [:b |
            [:f | (f value: a) value: b] ]].

FIRST  := [:p | p value: T].
SECOND := [:p | p value: F].

テスト。

(FIRST value: ((PAIR value: 1) value: 2)) printNl.
(SECOND value: ((PAIR value: 1) value: 2)) printNl.
1
2

うん、car も cdr も絶好調である!・・ですね。

で、作ったコレ、実は自然数の定義に必要だったんです。・・・ということで自然数。まずはゼロとゼロチェック。

ZERO    := (PAIR value: T) value: T.
IS_ZERO := [:n | FIRST value: n].

そして再帰的にすべての自然数を作ってしまいましょう。

SUCC := [:n | (PAIR value: F) value: n].
PRED := [:n | SECOND value: n].

ONE := SUCC value: ZERO.
TWO := SUCC value: ONE.

これは、

0: (t t)
1: (f (t t))
2: (f (f (t t))

のように自然数を定義していくイメージです。ではテスト。

(printBool value: (IS_ZERO value: ZERO)) printNl.
(printBool value: (IS_ZERO value: ONE)) printNl.
(printBool value: (IS_ZERO value: (PRED value: ONE))) printNl.
(printBool value: (IS_ZERO value: (PRED value: (PRED value: TWO)))) printNl.
'true'
'false'
'true'
'true'

と、自然数もできたのでまたもや便利な表示関数を定義します。

convert_bool      := [:f | ((IF value: f) value: true) value: false ].
IS_ZERO_asBoolean := [:n | convert_bool value: (IS_ZERO value: n) ].

convert_number_helper := [:n :v |
    (IS_ZERO_asBoolean value: n) 
	ifTrue: [v]
        ifFalse: [convert_number_helper value: (PRED value: n) value: v + 1]].

convert_number := [:n | convert_number_helper value:n value: 0].
(convert_number value: ZERO) printNl.
(convert_number value: ONE) printNl.
(convert_number value: TWO) printNl.
(convert_number value: (SUCC value: TWO)) printNl.
(convert_number value: (FIRST value: ((PAIR value: TWO) value: ONE))) printNl.
0
1
2
3
2

皆さんお待ちかねの Y combinator は、もちろん再帰を実現するために必要ですが、実は Smalltalk で Y combinator を実現するのは、例えば引数が常に評価されてしまうとかで 厳しいのです。

なので、ちとトリッキーな手を使っちゃうので、とりあえず頭を壁にぶつけるところから始めるとよかですよ(←わたしが言ってるんじゃないですよ)

Y := [:f |
         [:x |
             [:y |
                f value: (x value: x)]]
    value:
       [:x |
           [:y |
              f value: (x value:x)]]].

FORCE := [:x | x].

さあ、加算を実装です。

A := [:g |
         [:a |
            [:b |
               (((IF value: (IS_ZERO value: a))
                 value: ( [:x | b] ))
                 value: ( [:x | ((g value: FORCE)
                                   value: (PRED value: a))
                                   value: (SUCC value: b)] )) value: FORCE]]].

ADD := (Y value: A) value: FORCE.

さあ、二項の足し算が出来るところを観てみましょ。

(convert_number value: ((ADD value: ZERO) value: ZERO)) printNl.
(convert_number value: ((ADD value: ZERO) value: ONE)) printNl.
(convert_number value: ((ADD value: ONE) value: ONE)) printNl.

two   := (ADD value: ONE) value: ONE.
four  := (ADD value: two) value: two.
eight := (ADD value: four) value: four.
(convert_number value: ((ADD value:eight) value:four)) printNl.
0
1
2
12

(ひー、いまいちよくわかんない〜/けど、動いてるー、なんじゃこりゃー)

2項のイコールを追加します。こんな感じ。

E := [:g |
         [:a |
             [:b |
                 (((IF value: (IS_ZERO value: a))
                    value: ( [:x | (IS_ZERO value: b)] ))
                    value: ( [:x | ((g value: FORCE)
                                     value: (PRED value: a))
                                     value: (PRED value: b)])) value: FORCE ]]].
EQ := (Y value: E) value: FORCE.

テスト。

(printBool value: ((EQ value: TWO) value: TWO)) printNl.
(printBool value: ((EQ value: ONE) value: TWO)) printNl.
(printBool value: ((EQ value: ((ADD value: ONE) value: ONE)) value:TWO)) printNl.
'true'
'false'
'true'

ま、とりあえずここまで。引き算、掛け算、階乗、自然数以外の数なんかは読者への宿題です。リストについてのいくつかのアルゴリズムが役に立つかもですよ。


* * *


というわけで、Z combinator いまいちだよね、Haskell やろうぜ!・・に対する「Smalltalkだってできるモン」と微妙に斜め上をいくサンプルみたいな。ちょっとズれてる感がとっても Smalltalkらしく感じてしまうのはなぜでしょう。

ていうか、かえって分かりにくいので、あやうく 豆腐の角に頭をぶつけて死んでしまいそうでした。