究極の関数型言語による至高のHello, world!
以下の記事は、 R 教授による S 大学での講義録を Haskell Advent Calendar 2012 のために転載したものである。
はじめに
えー、それでは、今年最後の授業を始めたいと思う。今日は『究極の関数型言語による至高の Hello, world!』について講義することにしたい。
“究極”の関数型言語が何であるかについては諸説あろうが、ここでは SKI コンビネータ計算を指すものとする。また“至高”の定義を、最も簡潔であること、すなわち最も短く記述されていることと定める。
諸君は第一プログラミング言語として Haskell を選択している者がほとんどであろう。当初この講義も Haskell をベースに行おうと考えていた。だが、Haskell は非常に巨大な言語となってしまっており、言語仕様を把握するだけでも難しい。だいたい STG が Spineless Tagless G-machine だろうが、Shared Term Graph だろうが、違いの分かる者がどれだけいるだろうか。また最近の Haskell は、HTTP という世俗的な目的のためにフレームワークを用意するなど、大衆に媚びておる。ここは純粋関数型言語の原点に立ち返ることが必要であろう。
いずれにせよ、Haskell を含めた純粋関数型言語を深く理解する上で、コンビネータ計算／論理は極めて重要な概念である。コンビネータ計算に習熟すれば、遅延評価もポイントフリースタイルも思いのままなのである。なお一点だけ断っておくと、コンビネータ計算の世界に型はない。プログラミングを誤るとデバッグは極めて困難である。だが世の中、Haskell のように素晴らしい型を持つ言語ばかりではない。諸君も必要に迫られて Ruby や Perl を触らなくてはならないときがあるかもしれない。そんなときのためにも、型に頼らずバグを見つける嗅覚を養っておくことは重要であろう。
なおコンビネータ計算を具現化した言語として、今回は Lazy K を採用する。より簡潔なプログラミングを志向する者が集う場も提供されているので、諸君もこの講義を機に、ぜひ参加するとよいだろう。なに？Haskell Golf は止めたのかだと？Haskell Golf では henkma 氏に勝てないので 研究が忙しくてな、今は休んでおる。
チャーチ数とリスト（15620）
さて本題に入ろう。
"Hello, world!" という文字列を出力することが、プログラムの目的である。関数型言語において、文字列は文字のリストに決まっている。配列を使おうなどという考えは堕落である。また Lazy K において、文字はすなわちチャーチ数なので、チャーチ数のリストを得るというのが最初の目標となる。
念のため確認しておこう。チャーチ数は 0 = λ f x . x, 1 = λ f x . f x, 2 = λ f x . f (f x) となるような関数のことだ。SKI で表現すると、0 = SK, 1 = I, 2 = S(S(KS)K)I 。B = S(KS)K とおけば 2 = SBI となり、さらに任意のチャーチ数 n について n = SB(n-1) として帰納的に導ける。なお 0 = KI と表現する方が一般的かもしれないが、SK の方が何かと都合がよいので、今後はこちらを用いる。
また Lazy K におけるリストは cons = λ x y z . z x y という関数である。car = K, cdr = SK とおくと、(cons x y) car = Kxy = x, (cons x y) cdr = SKxy = y となり、リストとして機能していることが容易に確認できる。変数 z を除くと cons x y = S(SI(Kx))(Ky) となる。出力リストの終わり end-of-output は λ z . 256 = K 256 である。
これだけの知識があれば、以下のように仕様を満たすプログラムを書くことができる。
K(cons 72 (cons 101 (cons 108 (cons 108 ( ... (cons 33 end-of-output))))))
ここで 72（'H'）は、実際には SB(SB(SB( ... (72回適用) ... I))) = S(S(KS)K)(S(S(KS)K)(S(S(KS)K))(...I))) という記述になる。その他の数も同様である。
また Lazy K では入力がプログラムの引数として渡されるので、それを無視するため、先頭に K を置いている。
このプログラムは正しく動作するが、美しいとは言いがたい。何しろ 15620 bytes にもなるのだ。
いかにしてこれを簡潔に記述するかというのが、今日のテーマである。
算数（974）
Lazy K の処理系をここから取得しているなら、lazier.scm というファイルが含まれているだろう。これは scheme で書かれた DSL から Lazy K プログラムを生成するコンパイラであるが、これを利用して Hello, world! プログラムを生成してみよう。以下のような scheme プログラムを実行してみる。
(load "lazier.scm") (load "prelude.scm") (load "prelude-numbers.scm") (lazy-def '(hello input) '(cons 72 (cons 101 (cons 108 (cons 108 (cons 111 (cons 44 (cons 32 (cons 119 (cons 111 (cons 114 (cons 108 (cons 100 (cons 33 end-of-output)))))))))))))) (print-as-cc (laze 'hello))
これで生成されるプログラムは 1050 bytes。さらに最後の行の print-as-cc を print-as-unlambda と書き換えて Unlambda 記法で出力するようにすれば、974 bytes まで縮む。先ほどのコードのなんと 1/16 である。
何が違うのか具体的に見てみよう。
まず cons については特に変わりない。S(SI(Kx))(Ky) という表現が随所に出てくることが確認できる。
変わったのは、個々のチャーチ数である。たとえば 72('H') は S(K(SII(S(S(KS)K)I)))(S(S(KS)K)(S(S(KS)K)(S(SII)I(S(S(KS)K)I)))) と表現されている。
これがどのように導出されたかは、prelude.scm と prelude-numbers.scm を確認すれば分かる。関連する箇所を抜粋すると以下のようになっている。
72 = 4 * 18 18 = (1 +) 17 17 = (1 +) 16 16 = (λ x . x x x) 2 4 = (λ x . x x) 2
(1 +) は先ほど説明した SB = S(S(KS)K) である。
(*) の定義は λ a b f . a (b f) となっている。これが実際に a * b と等価であること、さらに S(Ka)b と書けることは、各自で確認してほしい。
16 と 4 の定義にあるラムダ式を理解するには、チャーチ数におけるべき乗が x ^ y = λ y x . y x となることを理解しておく必要がある。すなわち、λ x . x x は x ^ x、λ x . x x x は (x ^ x) ^ x と等しく、引数に 2 を与えれば、それぞれ 4 と 16 が得られる。
なお、λ x . x x = SII, λ x . x x x = S(SII)I である。ラムダ式から SKI コンビネータへの変換（abstraction elimination）については、資料もあるし、最終的にはプログラムに実行させることになるだろう。だが、これを十分に理解しておくことが、SKI コンビネータを自在に操れるようになるための鍵である。紙と鉛筆による演習をお奨めする。
さらに算数（687）
チャーチ数をこれ以上簡潔に記述することは不可能だろうか？いや、そんなことはない。先ほど例に挙げた 72('H') には B = S(KS)K が 4 回も出現する。これをまとめれば、より短い記述ができそうである。このことにいち早く気付いたのが 51b 氏である。氏はチャーチ数を B の関数とみなすことにより、それぞれのチャーチ数がどのように記述されるか整理した。このようにチャーチ数を B コンビネータの関数とみなし、B を除去したものを 51b 数と呼ぼう。
51b 数に関する代表的な演算の規則を、以下にまとめる。51b 氏オリジナルの規則に加えて、私が気付いたものもいくつか加えている。
(1 +) が SS と 2 項で書けること、(1 + xB) ^ xB や (1 + xB) * xB がもとの xB に加えてたった 4 項の追加で実現できることなどがコードの短縮に大きく寄与している。
1 + xB = SB(xB) = SSxB xB + yB = xB(SB)(yB) = S(SxS)yB xB * yB = B(xB)(yB) = S(SIx)yB xB ^ yB = (yB)(xB) = SyxB (1 + xB) ^ xB = xB(SSxB) = Sx(SSx)B = SS(SS)xB (1 + xB) * xB = B(xB)(SB(xB)) = SB(SB)(xB) = S(SSS)xB ((1 + xB) ^ xB) ^ xB = xB(SS(SS)xB) = Sx(SS(SS)x)B = SS(SS(SS))xB ((1 + xB) * xB) ^ xB = xB(S(SSS)xB) = Sx(S(SSS)x)B = SS(S(SSS))xB ((1 + xB) * xB) * xB = B(xB)(SB(SB)(xB)) = SB(SB(SB))(xB) = S(SS(SSS))xB
これにより Hello, world! は 687 bytes で表現できるようになる。
なお、これらの規則も含め、検証用に私が作成したコードはすべて GitHub に上げた。諸君は他人のコードを使うよりも、自ら実装することを好むだろうが、いくばくかの参考にはなるかもしれない。
再帰とYコンビネータ（607）
さて、Hello, world! のプログラムは、チャーチ数の生成とリストへの追加を繰り返しているだけである。繰り返しを避けることでより簡潔に記述できないだろうか。もちろん SKI コンビネータの世界でも再帰は可能だが、自分自身を呼び出すために、ちょっとした工夫が必要となる。
たとえば以下のような、リストの要素の和を計算する関数を考える。ここまで 1 行も Haskell が出てきていないので、Haskell で書いてみよう。
sum = \ x -> if null x then 0 else head x + sum (tail x)
これを SKI で表現したいが、sum の定義の中で、sum を呼び出すことができない。そこで、引数を一つ追加して定義する。
sum = \ g x -> if null x then 0 else head x + g g (tail x) -- 右辺が g ではなく g g なのがポイント！
その上で、sum sum と自分自身を引数に設定して呼び出せば、当初の関数と同様、再帰的に実行される。
再帰つながりで、どうしても Y コンビネータを使いたければ、sum の定義をちょっと変えて y sum と呼び出せば同等の振る舞いが得られる。
sum = \ g x -> if null x then 0 else head x + g (tail x) -- 右辺がちょっと変わっている。 y = (\ g -> g g) (\ y f -> f (y f)) -- Yコンビネータ
ただし、Yコンビネータは必要以上に汎用的であるため、利用するとプログラムは一般的に長くなる。そのため、それぞれの関数を個別に再帰させる方が、簡潔さという観点では優れていることが多い。
実は再帰を利用した Hello, world! についても 51b 氏が既に書いている。リンク先のプログラムではチャーチ数 30 を加える操作を共通化しているが、まずは再帰によるリストの構築までに留めると、以下のようになる。
hello = M (λ f x y . (ifnozero (y B)) (f f (cons (y B) x)) x) end-of-output main = hello <33> <100> <108> <114> <111> <119> <32> <44> <111> <108> <108> <101> <72> <0>
ここで M = λ g . g g = SII、すなわち、ものまね鳥である。
なお、この Hello, world! を Unlambda 記法で記述すると、607 bytes となる。
ショートコーディング（509）
だいぶ短くなってきたが、他に何ができるだろうか？繰り返し出てくるチャーチ数を共通化する？既に作成したチャーチ数をもとに別のチャーチ数を生成する？ここから先は様々な方法が考えられる。
今回、私はできるだけ短い 51b 数を組み合わせて必要な出力を得ることを考えた。
具体的には以下のようなプログラムで、<27> + y <73> <81> という部分が肝である。
hello = M (λ f x y . (ifnozero (y <1> <1>)) (f f (cons ((<27> + y <73> <81>) B) x)) x) end-of-output (K(K <5>)) K (SK) ... (K(K <45>)) KK
これにより 509 bytes のコードが得られた。
細かいテクニック（458）
ここからは、本質的でないが、コードを短くするために利用可能なテクニックをいくつか解説する。
- Lazy K の出力形式としてはコンビネータ記法（カッコを使う）や Unlambda 記法（適用演算子 '`' を使う）が選択できるが、引数が 1 つのときは Unlambda 記法、2 つ以上のときはコンビネータ記法を使うと、最も短く書ける。
- たとえば ss(ss) は ssss と等価である。コンビネータ記法では、後者のように書くことでカッコの分コードが短くなる。
- これは処理系に依存するが、エラー終了が可能であれば、end-of-output = K 256 よりも単純に K 等を用いた方が短い。
こうしたテクニックを利用することにより、Hello, world! のコードは最終的に 458 bytes となった。
