言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella

Joy == コンビネータ == ポイントフリースタイル?

さっきチラッと「Joy の文法は Haskell を逆にして、所謂ポイントフリースタイルを強制した物」と書きましたが、本当にそうなるか確認するために、haskell の階乗プログラムをどれくらい Joy っぽく書けるかやってみました。

-- まずはここら辺から始めます。
fact1 0 = 1
fact1 x = x * fact1 (x - 1)

-- 前置記法を使ってみましょう。
fact2 0 = 1
fact2 x = (*) x (fact2 ((+ -1) x))

-- ifte を実装します。
ifte :: (a -> b) -> (a -> b) -> (a -> Bool) -> a -> b
ifte f g cond x = case (cond x) of
                    True -> g x
                    False -> f x
fact3 x = ifte (\y -> y * fact3 (y - 1)) (const 1) (== 0) x

-- dup を実装します。
dup :: (a -> b -> c) -> (a -> b) -> a -> c
dup f g x = f x (g x)
fact4 0 = 1
fact4 x = dup (*) (fact4 . (+ -1)) x

-- dup (*) (fact4 . (+ -1)) == (\y -> y * fact1 (y - 1)) より
factorial = ifte (dup (*) (factorial . (+ -1))) (const 1) (== 0)

じゃーん。

factorial = ifte (dup (*) (factorial . (+ -1))) (const 1) (== 0)

となりました。ちなみに Joy で書いた階乗は

factorial  ==  [0 =] [pop 1] [dup 1 - factorial *] ifte

ひっくり返すと

ifte [* factorial - 1 dup] [1 pop] [= 0] == factorial

なので、「Haskell をひっくり返すと Joy になる」というのは割といい線行ってるんじゃないでしょうか???