Lazy K での Hello World の書き方が分かった、気がする

CodeIQ の Hello World 問題に挑戦とかしてました。楽しかったです。

問題は「"Hello World" を出力するプログラムを、文字、文字列、数値リテラルを使わずに書け」というもの。最初は特に挑戦する気とかなかったんですが、ちょっと思いついたことをツイートしてみたら、出題者さんからレスをいただきました。*1

そういえば、Template Haskell を諦めたとしても、そもそも Lazy K 処理系を、数値リテラル抜きで書かなきゃないのでした。まぁ、@fumieval さんが書いた Lazy K 処理系と、Wikipedia からコピペしてきた Lazy K の Hello World を組み合わせただけで、自分が書いたプログラムとは言えないし、やっぱりやめとこ、とか思ったところで、また、ちょっと思いつきました。

……必要な数はわりと簡単に手に入る気がする。

というところで、@fumieval さんの Lazy K インタプリタを眺めてみましょう。

http://ideone.com/ST3kF

使っている数値リテラルは、0, 1, 256 の 3つだけです。というわけで、符号付き 8bit 整数の上限下限を組み合わせるだけで、いずれの値も手に入ります。

num127 :: Int
num127 = fromIntegral (maxBound::Int8)

num128 :: Int
num128 = abs $ fromIntegral (minBound::Int8)

num0 :: Int
num0 = num127 - num127

num1 :: Int
num1 = num128 - num127

num256 :: Int
num256 = num128 + num128

インタプリタの数値リテラルを、これらの変数で置き換えれば、要件は満たせますね。やったぁ。

……いえ、満たせません。問題はこうです。

標準出力に
Hello World
と出力するプログラムを作成して下さい。

Wikipedia からコピペした Lazy K プログラムの出力はこう。

Hello, world!

ざっとぐぐってみたところ、どの Hello World も "Hello, world!" っぽい。

ところで、わたしは Lazy K でのプログラムの書き方を知った上で、LazyKQQ の記事を書いたわけではないのです……。*2

Lazy K 処理系はなにをしているのか

そのようなわけで、Lazy K で ("Hello, world!" でなく) "Hello World" を出力する方法をさぐらなければいけなくなったのでした。そもそもの出題意図から軽く脱線している気がしますが、どうせいつものことです。

さて、既存の Lazy K プログラムを読んで理解しようなどと思うのは、多分無謀です。むしろ処理系の動作をちゃんと理解した上で、所望のプログラムを書くにはどうすればいいかを考える方がマシでしょう、多分。

もちろん、LazyKQQ を書いたときには、処理系がなにをしているかも全然分かってなかったのです。@fumieval さんのコードをコピペしただけですからねー。ただ、今月あたまにpartake.inという (正気とは思われない名前の) 会に参加させて頂いたこともあって、ちょっとはマシになったかな、と。

で、LazyKQQ を書いたときに、分かりやすく書き換えてみた main を引用してみましょう。

main = do
  input <- getContents
  output $ eval $ program :$ (encode input)

LazyKQQ は QuasiQuoter なので、コンパイル時にすでに program は構文解析済みの式ですが、そうでなければ、main でまずファイルからプログラムを読み込み、構文解析してから program を束縛します。

入力のバイト列は encode でコンビネータ式に変換されます。

(:$) は、2つの引数の、前者を後者に適用する式を作る構築子です。これで、program と (encode input) をひとつに式にします。合わせてできたひとつの式は、評価され、評価結果は encode と逆に (output 関数内で) デコードされ、標準出力に出力されます。

以上から、Hello World プログラムにおいて、eval に渡されるべき式はどうなるでしょう。イメージとしては、こう。

K "Hello World" (encode input)

Hello World は、入力に関わらず "Hello World" を出力しますので、プログラムとしては、Kコンビネータで、第2引数の入力を捨てるだけですね。*3 というわけで、問題は、文字列 "Hello World" をどうやって得るかですね。

……今、そこに、文字列をコンビネータ式に変換する encode 関数があるじゃないですか。

スコットエンコーディング

ghci で encode "Hello World" を評価してみましょう。

*LazyKQQ> encode "Hello World"
(S :$ ((S :$ I) :$ (K :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$
S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K))
:$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ (
(S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$

(中略)

K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ I)))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) :$ (K :$ ((S
:$ ((S :$ I) :$ (K :$ (((S :$ I) :$ I) :$ (((S :$ I) :$ I) :$ ((S :$ ((S :$ (K
:$ S)) :$ K)) :$ I)))))) :$ (K :$ (((S :$ I) :$ I) :$ (((S :$ I) :$ I) :$ ((S :

長ぇ!! (37092 bytes)

一応、これをそのままコードに埋め込んで Hello World は動くみたいだけど、実行速度的に不安がある、かな……。

仕方がないので、"Hello World" のエンコードもちゃんと考えてみましょう。

encode は、このようなコードになっています。*4

encode :: String -> Expr
encode = foldr cons (cons (church 256) (church 256)) . map (church . ord)

cons :: Expr -> Expr -> Expr
cons a b = S :$ (S :$ I :$ (K :$ a)) :$ (K :$ b)

Lazy K は、自然数をチャーチエンコーディング、リストをスコットエンコーディングでエンコードします。*5

チャーチエンコーディングは聞いたことあるけど、スコットエンコーディングってなんぞや? って話は、ゆるふわ Lazy K 入門会で勉強してきました。よく思い出してみたら SICP で読んだことありました。ラムダ式でコンスリストを表現するってやつです。*6

cons = λ a b . (λ f . (f a b))
car = λ p . (p (λ a b . a))
cdr = λ p . (p (λ a b . b))

SKI コンビネータで書くとこうなります。

cons a b = S (S I (K a)) (K b)
car p = p K
cdr p = p (K I)

なんで、こうなるのか、っていうと、こういうこと、……らしいです。

(なんか、機械的に求める方法もあるっぽい……? *7 )

car と cdr については簡単なんで考えてみて下さい。

そんなわけで、encode は、Char から Int に変換して、チャーチエンコーディングして、それらをコンスリストにする、という処理になってます。

チャーチエンコーディング

ついでにデコードするほうも見てみましょう。

output :: Expr -> IO ()
output expr
    | x < 256 = putChar (chr x) >> (output $ cdr expr)
    | x == 256 = exitWith ExitSuccess
    | otherwise = exitWith $ ExitFailure $ x - 256
    where
      x = realize $ car expr

car :: Expr -> Expr
car expr = apply expr K

cdr :: Expr -> Expr
cdr expr = apply expr $ K :$ I

デコードするだけでなく、出力までしてますが、こんな感じです。コンスリストの処理なので、当然のように cdr ダウンしてます。チャーチエンコーディングされたコンビネータ式を整数にデコードしてるのが realize です。

realize :: Expr -> Int
realize expr = export $ expr `apply` Inc `apply` Export 0

export :: Expr -> Int
export (Export x) = x
export x = error $ "invalid output format (result was not a number:" ++ show x

チャーチエンコーディングされた整数n、というのは、関数 f を受け取り、f を引数に n 回適用する関数を返す高階関数、ですから、整数をインクリメントする関数を succ として、(チャーチ数 succ) 0 とすれば、チャーチ数→整数というデコードができます。

51b 数

そんなわけで、encode "Hello World" は、

cons (church $ ord 'H') $ cons (church $ ord 'e') $ cons (church $ ord 'l') $ ...

のように作られ、その結果が 37092 bytes になるわけです。*8 それにしては、よく見られる "Hello, world!" を出力するプログラムはそれほど長くはありません。LazyKQQ のサンプルに使った Hello World で 1K bytes 前後です。

Lazy K と Hello World でぐぐると、究極の関数型言語による至高のHello, world! - Life Goes Onという記事が見つかります。この記事で、より短くチャーチエンコーディングする方法が紹介されています。ゴルフをするわけではないので、ここまでこだわることはありませんが、こちらの記事のために書かれたというコードを使わせてもらって、十分短い "Hello World" が得られそうです。

正直よく理解してませんが、得られたのでよしとしましょう。

Prelude> :l LazyK/Number.hs
*Main> map (fst . nb . Data.Char.ord) "Hello World"

として、得られた「51b数」のリストが以下です。

nbHelloWorld :: [Expr]
nbHelloWorld = [
 (S :$ ((S :$ S) :$ S)) :$ (((S :$ ((S :$ (K :$ S)) :$ (S :$ S))) :$ I) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ S) :$ ((S :$ ((S :$ S) :$ (S :$ K))) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))),
 (S :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ S)))) :$ ((S :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ S)))) :$ ((S :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ S) :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))),
 (S :$ ((S :$ S) :$ (((S :$ S) :$ I) :$ ((S :$ S) :$ (S :$ K))))) :$ ((S :$ S) :$ (S :$ K)),
 (S :$ ((S :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ (S :$ K)))) :$ S)) :$ ((((((S :$ S) :$ S) :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ S) :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))),
 (S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K)))))))),
 (S :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ S)))) :$ ((S :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ ((S :$ S) :$ (S :$ K))) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))]