高速化ツールを作った。このツールでgaucheのスクリプトを処理すると約10倍以上の速度*1で動くようになる。gaucheの機能のごく一部しかフォローしていないので公開は控えておくけども。 手法。 gauche->stalinの変換を行う。以上。 感想。 やっぱりstalinは…

XXX(自作言語)では文法と入力の両方に継続が存在する。文法の継続はスタックベース、入力の継続はストリームベース。

XXX(自作言語)のコアは独自拡張PEGです。本来のPEGでは入力ストリームを解析しますが、XXX(自作言語)PEGでは入力ストリームを解析する際に並行して副ストリームへの操作を行います。この副ストリームへの操作をアクションと呼びます。 アクションは 入力スト…

現XXX(自作言語)で実装したスタック言語が非常に使いやすい。bootstrap言語に採用しても良さそう。

http://d.hatena.ne.jp/kilrey/20090117#p2の解説。 PEGに足りないものは以下のように導出する。 A? := A/ A* := (A A*)/ A+ := A A* &A := !!A ちなみにfailは内部実装でのみ利用する。ここでは考慮していないが、実用上はエラー報告がきわめて重要。 (追記…

実装終了。高速化はまた明日にしよう。 call/ccを使えるschemeだから何とかなった*1けど、C言語で実装するのはかなり面倒かも。ループに変換できるはずだけど、ねえ。 *1:きっとforthでも何とかなる。

左再帰対応PEGについて改めて考え直してみた。 実装できることは確定。 実行効率にオーバーヘッドがあるかも。 動作自体はかぎりなく右再帰に近い。 文法は左再帰、実行は右再帰という合いの子が出来るということだ。悪くないね。

PEGは左再帰ができない。Wikipediaにも載っている程度の常識的な話だ。 でも、それは本当なのかちょっと疑わしいような気がしてきた。あくまでも実装上の都合にすぎないのではないか、と。もう少し考えを整理する必要はあるけどもたぶん実装できる。 右再帰…

本来のPEGよりも小さくしたミニマムパーザを作る。それには fail 単一値判定 順接 選択 否定先読み だけで充分だ。ただし、パーザを遅延評価するという実装上の都合として lazy も付ける。あとはアクションの記法を考えなくては。

XXX(自作言語)で書ける部分はXXX(自作言語)で書く。 ライブラリとしても使えるように

PPEGについてちょっと考え直してみたら、PEGを生成するParser Combinatorという扱いになるようだ。Parser CombinatorというとHaskellのものが有名だが、今回の用途だと向いていないかもしれない。とりあえず、このままschemeで書く。stalinでもコンパイルで…

入力を抽象化しまくったらMonadになった。

PEGをGaucheで書いてみた。……想像以上に簡単に書けた。python要らない？ (追記) http://practical-scheme.net/wiliki/wiliki.cgi?amb 特に役立っているはこのambマクロだと思う。 文法要素はすべてthunkにした。ambマクロを包んだthunkを実行するたびにバッ…

C++版はひとまず後回しに。

decoratorsライブラリをもうちょっと充実させたい。言うまでもなくdocassertは毎回evalせずとも動くはずだし。Packrat関係で作ったメモ化デコレータも公開する予定。

PPEG(Parameterized Parsing Expression Grammar)というのはどうだろう。要するにPEGの文法要素にパラメータを渡して解析の自由度を上げようというアイディア。理論的には夾雑物以外の何者でもないが、ライブラリの実装も文法の実装もかなり楽になるはずだ。…

C++版を書いてみようと思います。結局、PEGとVMの両輪さえあれば何でもできるということか。

gccがどれくらい速いのかというのを確認するためにintの階乗という簡単なプログラムを手書きアセンブラとC言語で書いて実行してみた。手書きアセンブラは末尾再帰にしたりレジスタ渡しにしたりその場で思い付く限りの高速化を加えたもの。 しかし、手書きア…

今は簡単なDSLを作りながらXXX(自作言語)に必要なものを考えている。例えばForth風の言語を一つでっちあげてみた。言語系の要素は 無名関数定義 ':' ... ';' 辞書読み '?' 辞書書き '@' プリミティブ実行 '!' 数値 [1-9][0-9]* 識別子 それ以外全部 実行系の…

現状の実行系は python関数を並べた配列一つがXXX(自作言語)関数の一つに相当する。 実行状態ポインタがXXX(自作言語)関数の一部を指している。 run()は実行状態ポインタのポイント先を実行→インクリメントの繰り返し。 jump系の操作では実行状態ポインタを…

自作言語の名前をXXX(自作言語)にしようと思う*1。メタ言語という点に因んだ名前が思いつかなかったが、 不定形という点を強調してみよう。 テケリ？いやいや。 あまり畏れ多い名前もダメ。 XXX(自作言語)なら響きも良いな。 という曲折を経て決定した。半分…

PEG内PEGを使ってPackrat Parserを生成できるようにした。 Packrat Parserとは要するにメモ化付きのPEG実装だ。PEGでは非終端記号と入力列の位置だけから結果が求まる。つまりメモ化すれば(非終端記号の種類)×（入力列の長さ)程度の時間で解析が終わる。 た…

PEGでPEGを書いた。これで標準入力から文法を入力できる。 自前のPEGを書いていた動機はこの点にある。大抵のコンパイラ・コンパイラやパーザ・ジェネレータは静的なパーザしか生成できない。普通の用途ではそれで十分だし、速度面のメリットもある。しかし…

PEGでの開発速度を測ってみた。 後置記法電卓 実装＋テストで3分。 中置記法電卓 実装＋テストで5分。 lisp記法電卓 実装＋テストで10分。 lispのみバグがあったので長い。それを差し引いても10分で書ければ悪くないだろう。

……表題に偽りあり。既にpythonでプロトタイプが動いているので今から作るわけではない。しばらくしたら公開する予定だけどまだ名前を考えていない。 まあ、超スマートポインタもPEGも基本的にそっちの系列だし、既存言語の実装の次は自作言語の作成だよね。 …