「「Rubyで作る奇妙なプログラミング言語 ～Esoteric Language～」 発売」記事へのコメント

いまだにラムダ計算がわかりません

[YOUsuke (6796)]

誰かリンゴとバナナで説明してください。

--
妖精哲学の三信
「だらしねぇ」という戒めの心、「歪みねぇ」という賛美の心、「仕方ない」という許容の心

Re:いまだにラムダ計算がわかりません

[kr (10950)]

＞ 誰かリンゴとバナナで説明してください。

よっしゃ、リンゴとバナナね。 おいしい果物に置き換えれば、 小難しいラムダ算法も簡単になるに違いない!

そもそも、ラムダ算法の教科書なんか眺めても、なんだか意味がわからないし。 どれどれ、例えば、こんなことが書いてあるぞ……。

ラムダ算法では、Church booleanを用いて、論理値を以下の様に表わせる。
    TRUE := λ x y. x
    FALSE := λ x y. y
すると論理演算子を次のように定義できる。
    NOT := λ p. λ a b. p b a
    AND := λ p q. p q p
    OR := λ p q. p p q
    IFTHENELSE := λ p a b. p a b

ほうら、変な記号が並んでいてワケワカメだ。 そういやRubyにもtrue, false, and, or, not, if〜then〜elseってのはあるけど、 ラムダなんちゃらいうこの記号でどうして計算ができるっていうだ?

そこで、リンゴとバナナだ。

使うのはリンゴとバナナだけ、わけの分からない記号は一切使わない。

実はどんなラムダ式も、リンゴとバナナを並べて代用できる、と言ったら驚くかな? さてここからはリンゴとバナナを沢山使うから、先にスーパーに行って、 懐の許す限りリンゴとバナナを買って来よう!

準備は良い? じゃあ、手始めにさっき出てきた、 TRUEとやらをリンゴとバナナに置き換えるよ! 一緒にリンゴとバナナを並べてね!

リンゴ バナナ リンゴ バナナ リンゴ バナナ バナナ

並べたかな? 順序を間違えちゃ駄目だよ。

甘い香りが漂ってくる。無味乾燥な記号と違って、一目瞭然、とっても美味しそうだね! ん? 今一実感が湧かないって? お金が無くてリンゴとバナナを買えなかった? そうか、まあスーパーで買い占めなんかしても人様に迷惑だし、 ここは臨場感溢れる絵文字を並べて我慢しよう。

σισισιι

言うするまでもなく、σがリンゴでιがバナナだ。 なんて写実的な表現だろう! よだれが出てくるね!

じゃあどんどん行くよ。っていうか、もう面倒だからまとめて書くよ。

TRUE := σισισιι
FALSE := σσισισιισιι
NOT := σσσισισισιισσσισισισιισιισσσισισισιισσισισιισισισιισσισισιισιισσισισιισισισιι

うーん、おいしそうだ。え、ANDやORはどうしたって? あんまり続けてると、荒らしモデが付きそうだから自粛したんだ。

ともかく、これでラムダ計算がリンゴとバナナに置き換えられたから、 もうラムダ計算が分かったよね! そう、つまり、「リンゴとバナナはおいしい(でもあんまり沢山有っても飽きる)」ということだ。以上。さあ、帰った帰った。

は? 本当にラムダ式がリンゴとバナナに置き換えられているのか信用できない? 疑い深いなあ、じゃあストーリーの趣旨に合わせて、Rubyプログラムを置いておくから、 自分で試してごらんよ。

def iota (s)
  $s = s
  rec = lambda do
    i = $s[0]
    $s = $s[1..-1]
    if i == ?* then
      f = rec[]
      f[rec[]]
    elsif i == ?i then
      lambda {|c| c[lambda {|x| lambda {|y| lambda {|z| (x[z])[y[z]] } } } ][lambda {|x| lambda {|y| x} } ]}
    else
      raise "invalid char"
    end
  end
  rec[]
end

使い方は、こんな感じだ。irbを使うと便利だ。

irb> t = iota("*i*i*ii")
=> #<Proc:…>
irb> f = iota("**i*i*ii*ii")
=> #<Proc:…>
irb> n = iota("***i*i*i*ii***i*i*i*ii*ii***i*i*i*ii**i*i*ii*i*i*ii**i*i*ii*ii**i*i*ii*i*i*ii")
=> #<Proc:…>

iotaって何かって? なんだかバナナの絵文字ιのことを、そう言うらしいよ。 なので、バナナの代わりにiと書いてある。 リンゴの代わりは*だ。 こっちは陽を浴びて輝く真っ赤なリンゴを表わしているわけさ。

ラムダ計算をリンゴとバナナだけで表わしたバナナ言語を Rubyオブジェクトにコンパイルするのがiota関数だ。 コンパイル結果を格納したt, f, nが、 それぞれTRUE, FALSE, NOTに 対応していることが分かるね。

ん? これだけでは分からない? じゃあIFTHENELSEに当たる書き方を教えよう。 Rubyの(if p then a else b)という式は、 p a bと表わせる。 これをirbで試すには、 p [ a ][ b ] と書けば良い。例えば、こんな風に試すことが出来る。

irb> t["True!"]["False!"]
=> "True!"
irb> f["True!"]["False!"]
=> "False!"

関数適用f(x)はf [ x ]と書けるので、 NOTはこう書ける。

irb> n[t]
=> #<Proc:…>

おっと、これでは意味が分からないので、 さっきのIFTHENELSEで分かりやすく表示させよう。

irb> (n[t])["True!"]["False!"]
=> "False!"
irb> (n[f])["True!"]["False!"]
=> "True!"

ちゃんと論理が反転しているのが分かったかな? つまり、t, f, nは、 それぞれちゃんとバナナ言語で書いた論理値や論理演算を表わしているということだ。

では、実験に使ったリンゴとバナナは、残さずみんなで食べよう。 食べ物は粗末にしないこと! じゃあね!

================================================================

一応説明すると、上のバナナ言語は一種のCombinatory Logicの応用です。 任意のラムダ式を、SKIコンビネータに変換する方法は、 たいていのラムダ算法の本に載っています。 しかしSKIコンビネータはS, K, Iの3つのコンビネータと、括弧を必要とします。 そこで工夫を凝らして、コンビネータを減らし、 しかも括弧を不要にしたのがバナナ言語です。

なお、上のバナナ言語は、実は 「奇妙なプログラミング言語」のひとつ、 Iota言語 [nyu.edu] そのもので、Rubyで書いた処理系は、前記リンク先のScheme版を移植したものです。 つまりはパクリです。(_ _)

Brainf*ckは8つのオペレータを使いますが、 Iotaは2つしか使いません。それでもチューリング完全です。

SKIコンビネータを、括弧無しで、しかもたった二つのコンビネータで表わす方法は、 他にも色々考えられます。 読み物としては、 Flattening Combinators: Surviving Without Parentheses [usma.edu]が楽しく分かりやすいと思います。

ところで「Rubyで作る奇妙なプログラミング言語」にはiotaも載ってるのでしょうか? どんな言語が入ってるかちょっと楽しみ。

Re:いまだにラムダ計算がわかりません

[Deasuke (34806)]

> ところで「Rubyで作る奇妙なプログラミング言語」にはiotaも載ってるのでしょうか?
有名だから乗ってて然るべきだと思いますがねぇ。unlambdaもRubyにはcallccがあるからunlambdaの実装も楽でしょう。

--
Best regards, でぃーすけ