順番が無茶苦茶だけど、四番のドキュメントを読みます。スタック言語におけるモナドの扱いに触れるのが目標です。Joy 代数によって、高階関数の色々な性質を変数無しで表現する事が出来るらしいです。
準備
私は http://www.latrobe.edu.au/philosophy/phimvt/joy/joy.tar.gz からダウンロードできる joy を使っています。cygwin, linux, mac 等で展開して make して、/usr/local/bin 等にバイナリをコピーすると良いです。http://d.hatena.ne.jp/shortsleeved/20070604#p1 を参考に rlwrap をインストールすると便利さ倍増です(cygwin の場合は chmod 700 ~ が必要かも知れません)。joy は基本的に標準入力から読んで標準出力に出すという単純な仕組みなので、ファイルに保存したプログラムを実行するときはシェルの機能を使ってリダイレクトします。この意味が分からない人はプログラム全体をベッタリ Joy コマンド実行時にコピペして下さい。実行例を示します。
例題によっては、ライブラリ関数が必要な事があります。関数が上手く動かないと思ったらコンパイルしたディレクトリで ./joy を実行すると、usrlib.joy から順に読まれます。
$ rlwrap joy
JOY - compiled at 13:54:32 on May 17 2007 (NOBDW)
Copyright 2001 by Manfred von Thun
$ cat fizzbuzz.joy
# http://d.hatena.ne.jp/shortsleeved/20070530#p1
DEFINE
one-step ==
dup dup 3 rem
[null]
[pop dup 5 rem [null] [pop pop "FizzBuzz"] [pop pop "Fizz"] ifte]
[pop dup 5 rem [null] [pop pop "Buzz"] [pop] ifte]
ifte
swap pred;
fizzbuzz == [] swap [null] [pop] [one-step [swap cons] dip] tailrec.
$ echo '10 fizzbuzz.' | cat fizzbuzz.joy - | joy
JOY - compiled at 13:54:32 on May 17 2007 (NOBDW)
Copyright 2001 by Manfred von Thun
[1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz"]ある関数の動作を知りたいときは helpdetail を使います。
[関数名] helpdetail.
基本
『代数』というと難しく聞こえますが、意味は簡単です。Joy のプログラムの中で、同じ動作をする部分同士を交換しても意味が変わらないという事を利用したゲームだと思えば良いです。例えば
- 2 3 + == 5
というのが成り立つとします。2 3 + は 2 足す 3 の結果をスタックに置く Joy プログラムで、5 というのは 5 をスタックに置くプログラムなので、両辺の実行結果は同じです。という事は、Joy プログラムの中に「2 3 +」という記号の並びがあるとき、何時でもそれを「5」に書き換える事が出来ます。2 足す 3 は 5 だ！と普通に言わないで、何で代数などと言う言葉を使うかと言うと、未知数が入ってきた時に違いが分かります。
- 2 * == dup +
左辺は 2 をプッシュしてスタックの二つの値を掛け合わせ、プッシュします。左辺はスタックの値をコピーして、二つを足してプッシュです。両辺とも、スタックにすでに一つの数値がある事を期待しています。こう書いても訳が分からないと思うので普通に書くと
- 2 * x = x + x
となります。Joy では x はスタックに置かれた値が引数になるので明示的にx を書きません。つまり、変数を使いません。これはすごい事です。例えばプログラムの色んな所に、二倍する演算が使われているとします。ある時は 2 * x でしょうし、あるときは 2 * width かも知れないし 2 * length かも知れません。これを何らかの理由で全部足し算に変換したい場合、変数名に合わせて丁寧に書き換えなくてはいけません(アルファ変換)。Joy なら単純に記号列を置き換えるだけです。
Joy 記法を使って様々な数学的事実を表現してみます。
- succ pred == id : 足して引くと同じ物。x + 1 - 1 = x
- dup and == id : ある事実かつある事実はある事実。x and x = x
- < == swap > : 小なりは大なりの反対 x < y = y > x
- cons sum == sum + : 合計とは、リストを全部足した物。sum(cons(x,y)) = x + sum(y)
idempotent, inverse, unit elements
ある関数を二回適用しても一回適用しても結果が同じなら、その関数は idempotent (訳語教えてください！)です。例えば -3 の絶対値は 3 です。-3 の絶対値の絶対値も 3 です、-3 の絶対値の絶対値の絶対値もやっぱり 3 なのです。こういう関数の事です。この性質を Joy と普通の(中置記法の)言語でそれぞれ書きます。: の後ろが普通の例です。
- abs abs == abs : abs(abs(n)) = abs(n)
- sort sort == sort : sort(sort(s)) = sort(s)
ある関数 f の反対の動きをする関数を inverse (逆関数)と呼びます。例えば pred (前の値) と succ (次の値) はお互いに inverse です。これは、何もしない事を表現する関数 id を使って次のように書きます。
- pred succ == id : succ(pred(x)) = x
- succ pred == id : pred(succ(x)) = x
また、ある数に 0 を足したり、1 を掛けたりしても答えは最初の数と同じになりますが、こういうのを unit element (単位元) といいます。これも id で表現出来ます。
- 0 + == id : n + 0 = n
- 1 * == id : n * 1 = n
Idempotency, zero elements and arities
f(x, x) = x のようになる関数 f を idempotency と呼びます。例えば and や or 等です。
ここで、Joy では二つの同じ引数を表すのに dup を使っています。dup とは、スタックの先端をコピーしてもう一つ積む関数です。
- 42 dup == 42 42
f(x, c) = c のようになる定数 c を、関数 f の zero element と呼びます。例えば、0 は掛け算に対する zero element です。(0 * x = 0 なので)。
- 0 * == pop 0 : n * 0 = 0
Joy では、zero element を表現するのに pop 関数を使えます。pop 関数はただスタックから一つ値を捨てます。ちなみに、以上の zero element と unit element の議論では話を省略して引数が右にある場合だけ書きました。
Converses, commutativity and symmetry
この項目ではスタック操作に対応する性質について書いてありますが、退屈なので飛ばします。
Associativity
dip は Joy 特有の関数で、二つ以上の値をとります。dip はまず二番目の値をスタックから取り出してどこかに保存しておき、一番目の値をクォートとみなして実行します。最後に保存しておいた値を積みなおします。
つまり 3 4 5 [*] dip + は 3 4 * 5 + という意味になります。dip を使うと値の順序を変えずに評価順序を変更する事が出来ます。
- 3 4 5 + * == 27 : 3 * (4 + 5)
- 3 4 5 [*] dip + = 17 : (3 * 4) + 5
Homomorphisms, De Morgan and distribution
app2 は二回実行する map のような物です。最初の値をクォートとして二回実行しますが、それぞれスタックから値を取得します。クォートが二つ以上の引数をとる場合さらにスタックの四番目以降の値を使います。最初の実行も二回目の実行も二つ目以降の引数は同じ値を参照しますが、ポップしません。別の世界で平行に二度実行されて戻ってくる感じです。
- 1 2 [3 *] app2 == 3 6
- 10 1 2 [+] app2 == 10 11 12
これを使って様々な法則を表現してみましょう。
- * log == [log] app2 + : log(x * y) = log(x) + log(y)
- + double == [double] app2 + : double(x + y) = double(x) + double(y)
こういう形をした変換を、homomorphism laws というらしいです。また、app2 はド・モルガンの法則と、驚くべきそっくりなリストに関する法則を表現する事が出来ます(concat はリスト結合、swoncat は逆向きリスト結合です)。
- and not == [not] app2 or : not (x and y) = (not x) or (not y)
- or not == [not] app2 and : not (x or y) = (not x) and (not y)
- concat reverse == [reverse] app2 swoncat : reverse(concat(x y)) = swoncat(reverse(x), reverse(y))
- swoncat reverse == [reverse] app2 concat : reverse(swoncat(x y)) = concat(reverse(x), reverse(y))
こういうのを distribution laws というらしいです。これには right distribution と left distribution の二種類があります。
- f(g(x,y),z) = g(f(x,z),f(y,z)) : right distribution
- 例: (x + y) * z = (x * z) + (y * z)
- f(x,g(y,z)) = g(f(x,z),f(y,z)) : left distribution
- 例: x * (y + z) = (x * y) + (x * z)
app2 を使って right distribution を表現する事が出来ます。特に後者は難しいように見えますが、[pop] dip は余った要素を削るだけの操作です。
