Manfred von Thun 著、第17回 EuroForth 会議にて発表(2001 年 11 月 23 - 26 日、ドイツ、ザールブリュッケン、ダグストル城) Reuben Thomas による代理発表。
Joy 言語概要
Joy 言語は純粋関数型言語です。他の関数型言語では、関数に引数を適用する事が基礎になっていますが、Joy の基礎は関数合成です。Joy の全ての関数はスタックを引数として、結果のスタックを生成します。結果的には、Joy はただの普通の後置記法に見えますが、Joy の関数はスタックからいくつでも引数を取り、スタックにいくつでも結果を残します。正しく結合されたプログラムは、プログラムを意味する関数の合成を意味します。Joy のデータ型にはクォートされたプログラムがあり、リストは単にそれの特別なケースとなっています。ある関数はクォートされたプログラムがスタックの先端にあるとみなし、効果的にクォートを外し色々な方法で実行します。という事で、他の関数型言語が抽象(訳注: ラムダ抽象？)と適用を使っている所を、Joy ではクォーテーションとコンビネータ(クォートを外す働きをする関数)を使います。その結果、名前付き仮引数や仮引数の実引数への変換、名前と値のペアによる環境が不要になります。Joy のコンビネータは、他の言語で言うと関数的、または高階関数として振舞いますが、再帰定義や非再帰定義をあまり使わなくて良いようになっています。環境が必要無いので、Joy の代数はびっくりするほど単純で、Joy プログラムを手や他のプログラムから簡単に扱えます。沢山のプログラムが他のプログラムを組み立て、そして実行されます。
この記事は Forth プログラマのための紹介として書かれました。
導入
二つの整数を足し合わせるために、2 たす 3 をやってみましょう。こんな風にタイプします。
2 3 +
内部的にな動作を見てみましょう。まず最初の数字は 2 をスタックにプッシュします。二番目の数字 3 がその上にプッシュされます。それから加算演算子 + が二つの整数をスタックからポップし、合計の 5 をスタックに戻します。つまり見た目は普通の後置記法みたいに見えます。Joy 処理系はピリオドで完了するまでこのようにプログラムを読み込みます。実行するのはそれからです。デフォルトモードでは、スタックの一番上の要素(この例では 5)が出力ファイル(普通はスクリーン)に書き出されます。
整数の二乗を計算するには、まず数字を複製しなくてはなりません。二つの数字の合計をそれぞれの二乗するには、足し算の結果を自分自身と掛け算する必要があります。出来るだけ二度も足し算をしたくありません。次のプログラムが 2 足す 3 の結果を二乗するものです。
2 3 + dup *
2 と 3 の合計を計算した後、スタックには整数の 5 が置かれています。この
Forth と違い、Joy にはデータ構造としてリストがあります。整数のリストはかぎ括弧の中に書きます。一つの整数が足したり色んな事が出来るように、リストにも色々な操作があります。次の concat は二つのリストを繋げます。
[1 2 3] [4 5 6 7] concat
二つのリストはまずスタックにプッシュされ、concat 演算子はそれをポップして結果の [1 2 3 4 5 6 7] をスタックにプッシュします。
Joy ではほとんどの関数型言語に比べてよく コンビネータ を使います。主流の関数型言語ではコンビネータは引数を取る(ラムダ抽象された)関数です。Joy では、コンビネータはトップの先端に置かれた物に作用する演算子のような物です。ただスタックの先頭にある物を処理する演算子とは異なり、コンビネータはかぎ括弧で囲まれたプログラムのクォーテーション を扱います。コンビネータには例えばリストの要素に関数を使ってもう一つのリストを作る map があります。このプログラムを見てみましょう。
[1 2 3 4] [dup *] map
これはスタックにまず整数のリストを積み、それからクォートされた二乗プログラムを積みます。map コンビネータはリストとクォーテーションを取り出して、リストの各要素にプログラムを適用して新しいリストを作成します。結果はこのようになります。
[1 4 9 16]
これがスタックの先頭に残されます。
Forth と同じように、新しい関数を定義するのに仮引数は使わず、従って実引数から仮引数への置換はありません。次の定義により、
square == dup *
シンボル square を dup * の代わりに使う事が出来ます。他のプログラミング言語のように、再帰的に定義しても構いません。
Joy のデータ型
Joy のデータ型は単純型と集合型があります。単純型は、整数、浮動小数点、文字、そして真です。集合型はセット、文字列、リスト、そしてファイルです。リテラルはどんな型でもその値をスタックにプッシュします。そこで dup、pop、pop、そして swap やそのほか Forth おなじみの操作が出来ます。また特定の型を操作する演算子もあります。
整数と浮動小数点数は十進法で書き、普通の二項演算子や比較演算子が提供されています。演算子はオペランドの後ろに書きます。二項演算子はスタックの先頭から二つの値を取り出し、結果を一つ代わりに積みます。単項演算子も同じですが、一つだけスタックから取り出します。整数型に加えて、普通に操作できる文字型と真偽型(ブーリアン)があります。
集合型には、順番の無いセットと順番のある文字列やリストがあります。集合はくっつけたり分割したり要素を調べる事が出来ます。セットは順序が無くゼロ以上の小さな数 (0から31) の集まりです(訳注: ようするに 32 ビットフラグという事です)。セットはリテラルとして、{3 7 21} のように波括弧の中に書きます。普通の操作が出来ます。
文字列は順序のあるゼロ個以上の文字の列です。この型のリテラルは "Hello world" のようにダブルクォートで囲みます。
リストは順序のあるゼロ個以上の集まりで、値の型は何でも良いです。リストのリテラルは [peter paul mary] や [42 true {2 5}] のようにかぎ括弧で囲みます。リストにはどんな型の値も混ぜて含める事が出来ます。特に、リストを要素として含める事が出来るので、リスト型は再帰的なデータ型と言えます。普通のリストの操作が出来ます。行列はリストのリストとして表現され、普通の行列演算を行う小さなライブラリが存在します。大まかに言って構造化した型の操作は同じような物です。リストはリンク構造で実装されていて、スタックそのものもリストです。だからスタックをリストとして扱ったり逆の事も可能です。
クォーテーションとコンビネータ
実はリストはクォートされたプログラムの特別な例でしかありません。リストは色々な型の値だけを含みますが、クォートされたプログラムは他に演算子や後で説明する色々な物を含みます。クォーテーションはリストのような不活性なデータ構造とみなせます。例えば、
[ + 20 * 10 4 - ]
は長さが 6 で二番目と三番目の値が 20 と * で、順番をひっくり返したり他のクォーテーションとくっつける事が出来ます。さらに不活性なクォーテーションはデクォーテーションによって活性化することが出来ます。
もしこのようなクォーテーションがプログラムの中にあると、そのクォーテーションはスタックにプッシュされます - リストが詰まれるのと同じです。他にもクォート式をスタックの先端に置くには、部分をくっつけたり、大きなクォーテーションから抜き出したり、入力から読み込んだり、色々方法があります。置き方はともかく、クォーテーションを扱うには二通りの方法があります。不活性なデータ構造として、または活性なプログラムとしてです。かぎ括弧は、プログラムを活性化しないようにします。かぎ括弧が無ければ、プログラムは実行され、スタックにある二つの数字を足し合わせ、20 を掛け、最後に 10 と 4 の差である 6 がスタックに残されるでしょう。コンビネータは、スタックの先端にあるクォーテーションを独自の方法で実行します。単純な例は i コンビネータです。i コンビネータは先端のプログラムをただ実行するだけです。文法的に言うと、これはプログラムが実行出来るようにクォートのかぎ括弧を外す事になります。つまり、次の二つのプログラムは同じです。
[ + 20 * 10 4 - ] i
+ 20 * 10 4 -i コンビネータは主に理論的に重要ですが、たまに使われます。他にも Joy のプログラミングで大切な沢山のコンビネータがあります。
コンビネータには特定の型を要求する物があります。多くは他のプログラミング言語でお馴染みの、map、filter、fold などの高階関数です。map は先ほどご紹介しました。
他に集合を取るコンビネータとして、filter コンビネータがあります。まず真偽値を返すクォートされたプログラムを取り出し、次に取り出した集合の中で、プログラムが真と判定したものだけを集めて新しい集合を作ります。例えばクォートされたプログラム ['Z >] は文字コードが Z より大きいときに真と判定します。これで大文字と空白を文字列から削除する事が出来るので、結果は "ohnmith" になります。
"John Smith" ['Z >] filter
たまに集合全部の値を足したり掛けたりしたい時があります。fold はそれにぴったりです。これは、fold したい集合、クォートされた初期値、要素を計算するクォートされた二項演算、という三つの引数を取ります。他の言語では、このコンビネータを reduce (集合が一つの値になるので)と呼んだり、insert (それぞれの要素に二項演算子を挟み込むように動くので) と呼んだりします。次に二つのプログラムを紹介します。一つ目はリストの要素を合計するもので、二つ目は要素を二乗した値を合計します。結果はそれぞれ 10 と 38 です。
[2 5 3] 0 [+] fold
[2 5 3] 0 [dup * +] fold
間奏曲: ラムダ抽象と適用
二乗する関数はだいたいどんなプログラミング言語でも定義出来ます。中置記法を使った定義の見た目はこんな感じでしょう。
square(x) == x * x
内部的には、また外部的にもそうかも知れませんが、こんな風になっています。
square == Lx : x * x
"Lx" は "\x" や "lambda x" または "fn x" のように書く事もあります。右辺の式は「この関数は引数 x を取り、結果として x * x を答える」と読みます。このような表現はラムダ抽象として知られている物です。ほとんどのプログラミング言語は、少なくとも内部ではこのような構造を使っています。
このような定義は、例えば square に引数として 2 が適用されると、次のように実行されます(ここで、@ という中置演算子を適用を明示するために使っています)。
square @ 2
(Lx : x * x) @ 2
2 * 2
4二行目で、square は定義と置き換えられます。それから x = 2 という環境を構築し、仮引数 x に実引数 2 を設定します。環境とは、仮引数と実引数の組を集めた物です。最も単純な場合を除き、環境はこのような組をいくつか含みます。三行目において、仮引数 x を実引数 2 に変換するためにこの環境を使います。こういった操作は最初にあげた関数定義を実行する際、ユーザの見えない所で行われます。
ラムダ抽象と適用と言う二つの操作は双補完的な物で、主流の関数型言語や命令型言語の基礎になるラムダ計算の心臓部です。Joy ではプログラムのクォート式と関数合成によって、この抽象化、適用、変換といった操作を不要にします。
抽象化と環境無しでやってみる
先ほどのラムダ抽象を使った二乗の定義をこう書いてみます。
square == Lx : x x *
square == Lx : x dup *二番目の定義で右辺の式は「これは、スタックの先端を x と呼び、それを取り去り x dup *の結果を積むスタックの為の関数である」と読みます。しかし明示的にラムダ抽象を書かないでこうする事も出来るでしょう。
x square == x x *
x square == x dup *下の式で、両辺とも先頭は仮引数の x で、他のどこにも x は現れません。では左右に現れる仮引数を両方とも「消去」してしまう事は出来るでしょうか？そのとおり、そして定義はこうなります。
square == dup *
主流の命令型言語では、代入可能な変数と現在の値の組み合わせという状態が存在します。値はプログラム実行中に変化してゆきます。こういう言語では、定義された関数やプロシージャが呼び出されるときに設定される、仮引数と実引数の組である環境を持ちます。純粋関数型言語には状態がありません。しかし主流の関数型言語はラムダ計算を元にしているので、環境がります。この純粋関数型言語 Joy は、状態も環境もありません。命令型言語である Forth には両方あります。
ほかの言語のように、Joy でも再帰的な定義を書けます。次の例では、最初の行に普通の関数型言語で書いた階乗の定義を紹介します。次の行は Joy の再帰定義です。
factorial(x) = if x = 0 then 1 else x * factorial(x - 1)
factorial == [0 =] [pop 1] [dup 1 - factorial *] ifteまたまた、Joy の定義には仮引数 x が無くて、このように動きます。右辺の定義は、条件部、成功部、失敗部という三つのクォーテーションをプッシュします。それから if-then-else コンビネータである ifte がこれらを取り去り、結果の数値をスタックに置きます。ゆえに普通の条件式と同じように振舞います。(訳注: factorial はスタック先頭に置かれた数値の階乗、すなわち 1 * 2 * 3 * .. * n を計算する。ifte はまず最初のウォート式 [0 =] によりスタック先端が 0 かどうか調べる。もし結果が 0 だったら階乗の定義より答えは 1 なので [pop 1] により 1 をプッシュする。0 以外では、[dup 1 - factorial *] によりスタック先端をコピーして 1 を引いた物に factorial して掛け(ややこしいですが、ノートに書くと分かります)、プッシュする。)
再帰コンビネータ
与えられたリストのそれぞれを階乗したければこのようにします。
[ factorial ] map
しかしこれには、どこか他で factorial の定義が必要です。なぜなら factorial の定義は再帰を使っているからです。もしも単に数列の階乗が欲しいだけならば、単に再帰が要るからと言ってわざわざ factorial を別に定義しないといけないのはちょっぴり面倒な話です。
わりと多くの再帰関数は同じパターンで表現されています。まずテストがあって、終了条件を調べます。もしそうならば再帰の元になる非再帰的な部分が実行されます。そうじゃないなら再帰的に自分自身を呼び出します。
Joy には linrec という便利なコンビネータがあります。これは線形な再帰パターンを使って再帰的に定義されているかもしれない 無名関数を計算する事が出来ます。ifte コンビネータでは三つのクォーテーションを引数として使いましたが、linrec コンビネータは四つを使います。条件部、成功部、再帰部1、再帰部2 です。再帰は二つの再帰部の間で起こります。例えば階乗関数はこのようになります。
[null] [succ] [dup pred] [*] linrec (訳注: なぜか null や succ 等使う演算子が変わってしまっているが、最初 の例の通り書けば [0 =] [1 +] [dup 1 -] [*] linrec となる。)
もはや定義の必要は無く、このプログラムをそのまま直接使う事が出来ます。これを使ってリストの階乗を計算するにはこのようにします。
[ [null] [succ] [dup pred] [*] linrec ] map
また多くの再帰定義が、二つの再帰呼び出しを使って定義されています。これは二項再帰と言って、クイックソートやフィボナッチ関数の定義に使われます。線形再帰に linrec を使ったように、Joy には二項定義を表すbinrec があります。次にご紹介するのはリストなら何でも(リストのリスト以外) クイックソート する物です。
[small] [] [uncons [>] split] [swapd cons concat] binrec
Joy の数学的な基礎
Joy プログラムはたった二つの小さな構築子、接合子とクォーテーションから形作られています。結合子は二項構築子で、しかも結合的(訳注: (x + y) + z = x + (y + z) のような性質)なので、括弧なしの中置記法に適しています。結合子はたった一つの二項構築子なので、Joy では明示的な記号としては記述しません。
クォーテーションはプログラムを引数に取る単項構築子です。Joy では、プログラムのクォーテーションはかぎ括弧で包みます。究極的には、全てのプログラムは部分の無い原始的なプログラムから構成されています。
Joy の意味論は原子プログラムの意味、部分から構成される結合されたプログラムの意味、クォートされたプログラムの意味によって説明されなければなりません。さらに、全体のプログラムの意味を変えないでどういう風に部分を変更出来るかによっても説明されます。
Joy プログラムは一つの引数を取り一つの値を返す関数によって表現されます。引数と値にはいくつかの構成要素があります。主要な構成要素はスタックで、他には何も要りません。Joy の意味論の詳細はプログラムごとの特性に依存しています。
しかしながら、Joy の意味論の中心は次のような物で、Forth の純粋関数的な側面を表しています。
二つのプログラムを結合した物は、二つのプログラムが表す関数を合成した物である。
関数合成は結合的なので、この記法は結合的なプログラム合成の文法的な操作を、結合的な関数合成の意味的な操作に対応させます。
結合された物の一部は同じ機能を表すほかの部分と結合全体の記号を保ったまま交換可能でしょう。
あるクォートされたプログラムは、クォートされたプログラムが実行によってデクォートされるような文脈の中にある同じ機能を意味するほかの記号と交換可能でしょう。このような文脈は Joy のコンビネータが提供します。これらは他の言語で言う高階関数として振舞います。これは Forth には無い機能です。
ここまでの説明をまとめます。P、Q1、Q2 そして R がプログラムで、C をコンビネータとすると、次の原理が成り立ちます。
IF Q1 == Q2
THEN P Q1 R == P Q2 R
AND [Q1] C == [Q2] C(訳注: 上の章は訳がこなれてなくて意味不明です。すみません。)
Joy 代数
この原理は、Joy プログラムの等価性を扱い、つまりプログラムとして記述された関数の同一性を扱う、Joy 代数の重要な推論規則です。代数の中のいくつかの法則はコンビネータ無しで表現可能ですが、ほとんどは表現に一つ以上のコンビネータを使います。Joy プログラムの結合は、それぞれの部分が表現する関数を合成した物を表します。したがって Q1 と Q2 が同じ関数を表すプログラムで、P と Rが他のプログラムならば、二つの結合 P Q1 R と P Q2 R は同じ関数を表します。
言い換えると、プログラム Q1 と Q2 は結合の中で入れ替える事が出来ます。これは書き換えの為の推論規則として働きます。
前提として、次の最初三行までが公理で、四行目が定義だとします。
(+) 2 3 + == 5 (dup) 5 dup == 5 5 (*) 5 5 * == 25 (def square) square == dup *
このような公理と定義を使った導出はこんな風になります。
2 3 + square
== 5 square (+)
== 5 dup * (def square)
== 5 5 * (dup)
== 25 (*)右はしに書いたコメントは、前の行からどうやって導いたか書いてあります。この導出は最初の式と最後の式が同じ関数であるか、最初の関数と最後の関数が同値である事を示しています。
中置記法で書かれた次の等式を見てみましょう。最初に x を 2 で掛けた物が、同じ物を足すのと同じ結果になると言っています。次の物は reverse した物の size は、なにもしないで size した物と同じだと言ってます。
2 * x = x + x size(reverse(x)) = size(x)
Joy では、次のように同じ等式を変数なしで書く事が出来るのです。
2 * == dup + reverse size == size
他にも、色々な演算子の代数的な性質から来る等価性があります。例えば、数字の次の値 succ の前の値 pred は単に自分自身です。ある真偽値と、その自分自身との and の結果もやはり自分自身です。小なり関係 < は、大なり関係 > の反対です。あるリストに cons で数字を入れて、それから sum するのと、元のリストの sum にその数字を後で足すのも同じ事です。
普通の書き方では、これらは次のように表現します。
pred(succ(x)) = x x and x = x
x < y = y > x sum(cons(x,y)) = x + sum(y)Joy では、変数を使わないで、id という等価関数 を使い、こう書きます。
succ pred == id dup and == id
< == swap > cons sum == sum +コンビネータならではの演算子もあります。例えば dip コンビネータはスタックの先頭にプログラムがあり、他にもう一つ値が来るとみなします。dip はその値を抜き取ってプログラムを実行し、値を戻します。
以下の最初の例では、dip コンビネータは加算の結合法則を表現しています。別の例として、app2 コンビネータはスタックの先頭にプログラム、続いて二つの値を取ります。そして二つの値をプログラムに適用します。二つ目の例はド・モルガンの法則です。三つ目の例は、二つのリストを concat した物の size を取ると、二つの別々に size を取って足した物と同じであると示しています。最後に、掛け算と足し算の分配法則(右辺)を表すのにコンビネータを使った例です。(app2 の引数はまず被乗数と * によって構築されます。)
[+] dip + == + +
and not == [not] app2 or
concat size == [size] app2 +
[+] dip * == [*] cons app2 +
訳注: 中置記法で書くと、スタックに z y x の順で積んだ後、
x + (z + y) == x + y + z
not(x and y) == (not x) or (not y)
concat(x y) == concat(x) + concat(y)
x * (y + z) == cons (x, [*]) (y) + cons (x, [*]) (z)
== [x *] (y) + [x *] (z)
== (x * y) + (x * z)
Joy と Forth
Joy と Forth との類似点や相違点は印象的で意義深い物です。これらは http://groups.yahoo.com/group/concatenative にあるメーリングリストで議論されています。Joy のホームページは http://www.latrobe.edu.au/phimvt/joy.html にあります。
訳注
以上は http://www.latrobe.edu.au/phimvt/joy/forth-joy.html の翻訳です。Joy の事を伊藤さんの記事 http://d.hatena.ne.jp/nqthm/20070509/p1 で知ってこの文章を読み。大変感動したので翻訳しました。途中読みにくい所もあると思いますが、特に「Joy 代数」の章にはぐっと来ました。
