Life Goes On

まあまあだけど楽しんでる方です

Hello, world! ふたたび

Haskell Lazy K

R 教授による S 大学での講義録。

はじめに

えー、前回の講義からだいぶ間が空いてしまったが、講義を始めたい。
今回はクワインについて話す予定であったが、その前にもう一度だけ Hello, world! について話をさせてほしい。
前回の講義の直後、irori 氏によって、399bytes の Hello, world! の存在が証明された。
その詳細について氏は何も語らなかったが、今年の 7 月になってソースコードが公開された。
それを解読した結果、および解読の過程で新たに得られた知見について、今回の講義では話をしたいと思う。

ロジックの見直し（451）

前回の講義で "Hello, world!" という文字列に対応するチャーチ数を得るため、

<27> + f <73> <81>

という式を提示した。だが、どうやらこれは少々複雑に過ぎるようである。

<28> + f <80>

という式の方が、必要なチャーチ数を簡潔に生成できることが分かっている。

Jot 記法（421）

irori 氏のコードを読むと、'0' という見慣れない文字が頻繁に出てくることに気づく。
これは何か？そう、Jot 記法である。
Lazy K で Jot 記法は以下のように定義されている。

NonemptyJotExpr
    ::= JotExpr "0"     (JotExpr S K)
      | JotExpr "1"     (lambda (x y) (JotExpr (x y)))

つまり単体の 0 は SK すなわち真偽値の「偽」と等価である。
SK は 51b 数にも必ず登場するため、"`SK" を "0" に置換することでコードを大きく短縮できるのだ。

irori 氏の手法（399）

irori 氏は、さらに以下の 3 つの手法を用いてコードを短縮し、400bytes を切るまでに至った。

関数の構造の見直し

もともと私が定義していた関数の構造は以下のとおりである。

hello a x = if x == 0 then a else hello (g x : a)

これに対して irori 氏が定義した関数の構造は以下のようになっている。

hello a x = (if x = 0 then tail else hello) (g x : a)

追加された tail の分、操作は増えているが、引数 a の出現箇所が減っているので、abstraction elimination 時のコード増加量が抑えられ、結果的に 15bytes ほど短くなっている。

51b 数の有効活用

51b 数はチャーチ数を生成するためのものであり、チャーチ数に変換してから、すなわち B コンビネータを与えてから利用するというのが本来の使い方である。
だが、51b 数に他の値を与えることにも意味がある。irori 氏は SK を与えることで、再帰の終了判定を簡潔に記述しており、5bytes ほど短くなっている。
さすが 51b 数の生みの親である。51b 数を深く理解されている。
ちなみに 51b 数 に Bコンビネータ以外の値を与える場合、結合則を満たす 2 引数関数 f であれば、およそ以下のように簡約される。

<N> f x
  => (f x (f x (f x ... (fをN-1回適用) ... (f x x)))))
技巧的な再帰

再帰を実現するには M コンビネータ (SII) を利用し、自分自身を引数とする関数を生成するのが一般的である。
だが irori 氏は少々込み入った定義をして、再帰を実現している。煩雑になるため、詳細は割愛する。
これにより得られる効果は高々 2bytes であるが、全体のサイズは 401bytes → 399bytes となり、夢の 300bytes 台を達成しているのである。

チャーチ数による再帰（365）

300bytes 台を達成したところで、これ以上の短縮は不可能であろうか？
いや、キリのよいサイズのコードはまだ縮むというのがゴルファーの間の鉄則だ。これはむしろ、より短いコードへの足掛かりと捉えるべきである。

これまでのコードをさらに短縮する上では、やはり関数の構造に大きく手を入れることが不可欠であろう。
また irori 氏は 51b 数を有効に活用していたが、他にも同じようなことができないだろうか。
ここまで考えて私は、Hello, world! のメインループを書き換える方法に思い至った。
明示的に再帰構造を記述するのではなく、チャーチ数により再帰を実現するのである。
どういうことか？たとえばチャーチ数 <3> が与えられたとき、 

f a b x = a (x : b)

のように定義しておくと、<3> f a b x y z という式は以下のように簡約され、f を再帰的に 3 回呼ぶのと同じ効果が得られる。

<3> f a b x y z
  => f (f (f a)) b x y z 
  => f (f a) (x : b) y z
  => f a (y : x : b)) z
  => a (z : y : x : b)))

固定長の引数を扱うプログラムでは、再帰を終了させるための条件分岐も不要になり、コードを大きく短縮することが可能である。
今回の場合、これにより 365bytes のコードを得ることができた。
実はこの手法（チャーチ数による再帰）は関数型プログラマの間では比較的ポピュラーなものであり、Grass におけるショートコーディングなどでも活用されている。今回、私が気づかなかったのは、ひとえに私の力不足によるものである。

おわりに

というわけで、Hello, world! における irori 氏の手法と、新たに得られた知見について解説した。
次回の講義では、今度こそクワインについて話すつもりだ。