大島芳樹のカリフォルニア日記

2004 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
2010 | 01 | 02 | 03 | 05 | 09 | 10 | 11 | 12 |
2011 | 10 | 11 | 12 |
2012 | 01 | 02 | 05 | 08 | 10 |
2013 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 02 | 03 | 04 | 07 | 08 | 11 |
2015 | 01 | 03 | 05 | 10 |
2016 | 01 | 02 | 05 |
 | 

2014-07-24

[] J言語をOMeta2/Squeakで作る  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}]

のようになっています。それぞれ結果はあたまに適切なキーワードをつけたリストです。

まあnumberとかprimitiveとかの規則定義はしなくてはいけないのですが、それらはまあ簡単なのでここでは省きます。と

いうわけで、sentenceとelementという規則定義することによって、Jのパーザーが完成しました。このパーザーは例えば

(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つの引数およびそれぞれの引数ランク情報を渡すためです。

そして、例えば一般化された外積を表す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の式として評価されるようなものを作ります

http://tinlizzie.org/~ohshima/BattleFeverJ.png

さらなる発展があるかどうかはかなり謎ですが、まあ記録までに日記にしてみました。

トラックバック - http://d.hatena.ne.jp/squeaker/20140724
 | 

最近のコメント

1. 05/12 squeaker
2. 05/12 shiro
3. 11/10 squeaker
4. 11/28 squeaker
5. 11/10 kwakita
6. 11/28 (わ)
7. 11/10 squeaker
8. 11/10 abee2
9. 03/27 squeaker
10. 03/27 加藤正臣
11. 12/10 nomisuke
12. 12/12 squeaker
1129321