Lazy K 入門 - Life Goes On

何となく触ってみました。以下に体験記を。
Lazy K の入力はチャーチ数のリストとして与えられます。出力もチャーチ数のリストとして構成。Haskell の interact が最初から備わっているような感じ。
なので、入力をそのまま出力する echo サーバは以下のように書けます。

"K〜"とすれば、入力を無視して"〜"を出力します。
Hello, world! は大変そうなので、まずは一文字出力に挑戦。作るのが簡単そうな"@"(0x40)を選びました。
最初に書いたコードはこんな感じ。

K
  (S(KS)K
    (S(S(K(S(KS)K))S)(KK)I
      (K(SII(SII(S(S(KS)K)I)))))
    (S(S(K(S(KS)K))S)(KK)I
      (S(S(KS)K)(S(S(KS)K)I)(S(S(KS)K)I(S(S(KS)K)I)))))

簡単に解説すると、K (cons 64 (K 256)) を作ってます。（終端文字は 256 で表現する）
cons x y f = f x y だから cons x y = ($y).($x) = flip id y.flip id x = (.) (flip id y) (flip id x) となって、(.) = S(KS)K、flip = S(S(K(S(KS)K))S)(KK)、id = I という風に考えました。
64 は (2^2)^(1+2) で、2 = S(S(KS)K)I、(+1) = S(S(KS)K) として構成。
いちおう動きます。

C:\lazy-k>lazy 64.lazy
@

実は Lazy K の処理系には、Scheme のコードから Lazy K のコードを生成するコンパイラが標準でついてます。
それを使って、(cons 64 end-of-output) という Scheme コードから生成すると、

K
  (S(SI
    (K(S(S(S(KS)K))(SII)(S(S(KS)K)I))))
    (K(K(SII(SII(S(S(KS)K)I))))))

手で一所懸命書いたやつより短い‥‥orz
気を取り直して何がいけなかったのか見てみると、まず cons x y = S(SI(Kx))(Ky) と書ける。
これが断然短い。
それから 64 の作り方も、(\x -> x x) = SII と書けるので、2^2 を作るのに 2 = S(S(KS)K)I を2個並べるより、SII 2 としたほうが短い。さらに (+1) 2 ((\x -> x x) 2) という式は S を使って S (+1) (\x -> x x) 2 と書けるので、もっと短くなる。
という訳で、Scheme → Lazy K コンパイラを目一杯活用しましょうという結論に。
それでも飽き足らない人は、あなごるでも眺めるとよいと思います。
ちなみに irori さん作の Haskell → Lazy K コンパイラもあるのですが、以下のようなエラーでまだ実行できてません。むむむ。[追記]付属のPrelude.hsをリネームしたら、ちゃんと動きました。[/追記]

c:\hs2lazy>ghc --make Main.hs
[ 1 of 12] Compiling Lexer            ( Lexer.hs, Lexer.o )

wrappers.hs:1:0:
    attempting to use module `Prelude' (.\Prelude.hs) which is not loaded

参考サイト：