Lisperの為のSmalltalkが飛ばしてる件について
なんで急に Y combinator なんて出てきたかというと、なにげなく仕事をサボって気分転換に読んでたこのページがきっかけです。
Smalltalk for Lispers -Smalltalk/X Programmers guide
タイトルから Smalltalk と Lisp の文法比較かな、と思って読み始めたのですが、最初は確かにそんな感じだったのだけれど、下の方にいくに連れなにやら雲行きが怪しくなってきて、結局行き着いた先は 関数で自然数を表現するところから始まるバリバリの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 Smalltalk や Squeak の場合は 何も考えないでこのままコードを評価すれば 勝手に変数が作られます。
早速テスト。
(((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らしく感じてしまうのはなぜでしょう。
ていうか、かえって分かりにくいので、あやうく 豆腐の角に頭をぶつけて死んでしまいそうでした。