J言語をOMeta2/Squeakで作る
APLの集まりに参加した関係上、私も処理系の1つぐらいは作らなくてはな、ということで雑用に追われる中(実は転職しました)ちょっと作ってみました。
実装の都合上、シンボルはAPLのシンボルではなく、ASCIIベースでやっているJ言語のものを使っています。
実装に使う言語はOMeta2/Squeakで、パーザーとインタープリターをそれぞれ別のクラスとします。あ、ちなみに世界に蓄積された「効率の良いAPL処理系を作る」ためのノウハウ(http://www.slac.stanford.edu/pubs/slacreports/reports07/slac-r-114.pdf にある"drag-along and beating"とか)とは距離を置き、とにかく簡単な実装とすることを目標とします。
パーザーはJParserというOMeta2クラスのサブクラスとして作ります。
Jの実行単位は「文」と呼ばれているもので、それは簡単に言ってしまえば、「要素」の1つ以上の列です。ですので、文を認識する構文規則は以下のようになります。
sentence =
element+
ですが、一応認識したもののリストを結果として取り出し、よけいな余白などがあっても動くようにするわけなので、実際の規則は
sentence =
element+:s spaces -> [{#sentence}, s reversed]
のようになっています。認識した結果は逆順にひっくり返された後、#sentenceというキーワードをあたまにつけたリストになります。
ここで使われている要素を認識するためのelementという構文規則は以下のような感じです。
element =
"(" sentence ")" | number number+ | number | primitive | name
文を括弧でくくったもの、数字の2つ以上の並び、一つだけの数字、記号、そしてアルファベットで始まる普通の名前のどれか、ということになっています。elementも認識したものを結果としての粉作手は行けないので、実際には
element =
"(" sentence:s ")" -> [s]
| number:f number+:s -> [{#array. f}, s] |
| number |
| primitive:p -> [{#primitive. p}] |
| name:n -> [{#name. n}] |
(2 3 $ 1 2 3) +/ 4 4 4のような入力を食わせると
{#sentence.
{#array. {#number. 4}. {#number. 4}. {#number. 4}}.
{#primitive. #/}.
{#primitive. #+}.
{#sentence.
{#array. {#number. 1}. {#number. 2}. {#number. 3}}.
{#primitive. #'$'}.
{#array. {#number. 2}. {#number. 3}}}}
という構文解析の結果を出力します。
次はインタープリターです。インタープリターの基本的な動作は http://www.jsoftware.com/help/dictionary/dicte.htm に記述されています。要するに入力を後ろからスタックに積んでいき、スタックトップの近くで還元できる要素があれば還元する、ということになります。OMeta2は要素の後ろの方を処理するという機能がないので、パーザーの方で順序をひっくり返していたのでした。
インタープリターはJInterpreterというOMeta2クラスのサブクラスとして作ります。
JInterpreterはスタックを状態として持ち、入力要素を見るたびにスタックに「シフト」し、還元できるようなら「リデュース」するという動作になるので、これをそのまま書き下して
sentence =
{#sentence (shift | reduce(false. stack))+} reduce(true. stack)*
-> [stack last]
と書きます。sentenceキーワードで始まるリストの要素を全部見終わった後にもスタック上に還元すべき要素がまだ残っているかもしれないので、最後には還元できる間ループして(クリーネ閉包*を使う)、スタックトップを結果とします。
shift規則の骨子は
shift =
({(#array
({#number anything:n} [n])+:nn
[JArray new: {nn size} data: nn offset: 0]
| #number anything:n [n]):n
} [n]
| anything):n
[stack addLast: n]
というくらいのもののはずです。#arrayキーワードで始まる配列が来た場合は、JArrayというJの配列を表すオブジェクトを作ります。数値やシンボルなどは構文解析の結果そのもので良いです。
ですが、上記のページを見ると副詞(adverb)や接続詞(conjunction)の結合規則について何やら書いてあります。構文解析時にバラバラのままにしておいた+や/のシンボルはどこかの段階で結合させなくてはならないようです。ですので、シフトしようとしたものが副詞や接続詞だった場合には、その時点で読めるだけ読んで結合したものを動詞としてシフトするようにします。 さらに、もともと丸括弧で囲まれていた副文であった場合にはそれを評価しなくてはならないので、それもシフト時にやってしまうことにします。
shift =
(
parseVerb
| {
(#array
({#number anything:n} [n])+:nn
[JArray new: {nn size} data: nn offset: 0]
| #number anything:n [n]):n
} [n]
| anything):n
(
isInnerSentence(n)
| [stack addLast: n])
例によってparseVerbやisInnerSentenceの定義は省きます。
還元を表すreduce規則はだいたい
reduce :last =
{(
arg:n conjunctions:c
-> [self pop: 4 andPush: c andPush: n]
| arg:r dyadOp:o ~verb arg:l
-> [self pop: 3 andPush: (o value: l value: r)]
| arg:r monadOp:o (?[last] | (~arg ~conjunction anything))
-> [self pop: 2 andPush: (o value: r)]
):n _*}
[n]
のようなものです。
というわけで、後は必要となるヘルパーを書いて、パーザーとインタープリターの完成です。
ただ、実際に計算を行う演算子の実装にはまだ手間がかかります。+や-といった2項演算子であっても、引数となっている配列の次元の組み合わせ、そしてランクオペレータの指定するランクによって振る舞いが変わってくるので、その辺に対処したものをSqueakのコードとして書きます。Jの場合は演算子の動作の定義を、JArrayのメソッドとして書いて、左辺と右辺を非対称にするのは気が進まないので、JInterpreterの暮らすメソッドとして "doDyad: op with: l with: r lRank: lr rRank: rr"のようなシグネチャのものとして書きます。
さらには、このような演算子は副詞や接続詞によって際限なく修飾されうるので、Squeakのクロージャーを活用して、組み合わせることにします。例えば、+が使われたときに適用される関数は
Dyad at: #'+' put: [:a :b :ar :br | self doDyad: [:x :y | x + y] with: a with: b lRank: ar rRank: br].のようにDyadという辞書にしまっておきます。4つ引数があるのは、２つの引数およびそれぞれの引数のランク情報を渡すためです。 そして、例えば一般化された外積を表す2項演算子の'/'は、
DAdverb at: #'/' put: [:v |
[:l :r :lr :rr | self outerProduct: v with: l with: r lRank: lr rRank: rr]].
のようにDAdverbという辞書にしまっておきます。入力として"+/"のような組み合わせが現れた場合には、
(DAdverb at: #'/') value: (Dyad at: #'+')のようにすると、再び4引数のブロックが結果として返るので、それを2項演算子として使うことができるわけです。 で、せっかくSqueakで作った以上、対話的な環境を作らねばなりませぬ。というわけで、Workspaceのサブクラスを作って2,3のメソッドをオーバーライドし、入力したものがJの式として評価されるようなものを作ります。
さらなる発展があるかどうかはかなり謎ですが、まあ記録までに日記にしてみました。
