Scheme:パーザジェネレータ

Scheme:LazyEvaluation で出た話題:

横槍の横槍ですみません。macroの話題がでてきたところで便乗して...ひとつ、 質問させて下さい。 普段は、lua使いなので、schemeについてはいまひとつ？ なのですが、正規表現を使える macro の処理系というのは存在しないのでしょうか？　 あそこまで強力にするのであれば、lexer並の機能を期待してしまうのは自然な ことだと思うのですが。ちなみにgemaのような仕様 をscheme風に整理したものを 想像しています。 あっ”Scheme:マクロの効用”の方に書くべきだったか。--toki?

に関して議論を進めるコーナー。

LispのマクロはあくまでS式からS式へのトランスレータなので、 入力コードもS式としてパーズ可能であることを前提としています。 もし、例えばコードをinfixで書いておいてそれをLispプログラムとして 読みたいとなると、lexerの部分を拡張しなければなりませんが、 その標準的な方法はSchemeにはありません。(Common Lispだと入力文字に 対して処理手続きを付けるという形でカスタマイズが可能ですが)。

• いくつかのScheme処理系では、read-eval-print-loopやloadで使う readerをプログラマが指定できます。その部分を自前のパーザに置き換えて やる、というのが第一歩。
• Bigloo には強力な lexer/parser generatorがついていますし、 MzScheme には awkみたいな関数があります。そういうのを使えば自前のパーザが 楽に書けるでしょう。

ただ、そこまでしてしまうとマクロ処理というよりは自分で言語を 作ってしまっているようなことになりますね。結局、Paul Grahamも 言及しているように、Lispのマクロが簡単に強力な処理ができるのは、 コード自体がS式で書かれているという事実に負うところが大きいと思います。

• S式を拡張して、infix構文を入れ、一番外側の括弧を省略し、define の代わりに infixの'='を使えば、構文的にはかなり、Haskellに近くなり、あとは、Lazy にすれば バッチリ :-) --nobsun (2002/05/19 15:14:44 PDT)

個人的には、parser/lexer的なものを書く機会が多いので、 そのへんも手軽に処理できるフレームワークがあるといいなと思っては いるのですが… --Shiro (2002/05/19 03:29:02 PDT)

私も、基本的には制御屋なのですが、時代の流れをうけてかpacketのような serial dataを構文解析する機会が非常に増えてきました。 とくにhtmlのようなrecursiveに処理になければならない構造をもつdataを 扱わなければならない場面が度々あるんですよね。このような場合、flexをはじめ とする既存のlexical analyzerでは今ひとつ煩雑ですし、dfaによる正規表現の実装では 完全にstaticになりますから、柔軟性に欠けます。 この状況は、もとよりflex以下の機能しかもたないsilexなどのschemeによる実装でも 変わらないようです。 でｓ式の処理に特化したschemeのmacroで何か実験的な試みがないかなと。 現状では、gemaをluaに組み込んで使っているんですが、日本語が... 汎用のmacro言語の研究って、m4以降あまり活発ではないんですよね。 言語ではなく、pcreでもhogeったらという声が聞こえてきそうですが。　--toki?

• recursiveな構造があるならregular grammerでは表現不可能ですから、 求められるのはcontext free grammerのパーザでかつgrammerが ダイナミックに定義できるようなもの、ということでしょうか。 うーん、BiglooのLALR parserも文法定義は静的ですしねえ… 学習つきの自然言語処理なんかをやっているところでなにかdynamicなパーザが あるかもしれませんが、私にはちょっとわからないです。 --Shiro

• LL(1)程度の文法なら、parser combinator を使ってダイナミックにparserを 構成できると思います(たぶん^^;)。-- nobsun

• "Implementing functional language: a tutorial"の１章に parser combinator の実装があります。(miranda のコードです) ただし、Lazy evaluation を前提とした実装です。おっ。遅延評価の話題にもどりましたね。:-) Haskell の実装は HugsのLibraryに付属しています。遅延ストリームを使えば Schemeでも簡単にかけるかも。 -- nobsun (2002/05/20 15:16:56 PDT)

• lazy evaluationによるimplementは面白そうですね。 でも、patternにmatchするactionがひとつ実行された後、patternにmatchしなかったevaluation途中のactionの状態は無駄になるのでは？ --toki?

• Lazy ならその心配はいらないかと。(『Lazy天国』。。。なんてね） --nobsun

どもども。いやparser generatorがあればかなり救われるんです。 ただ、使い易いparser generatorの処理系ってないんですよね。 大抵；

• parser書いてcode generation
• lexer書いてcode generation
• glue部分を書いて
• 言語本体を起動、test!!

でもdebugは、genaratorが機械的に吐き出したperformance優先の分り難いcodeが相手。 ちょっとメげます。せっかくinterpreter使ってrapid programmingしてるのに。 どうも、世の中のparser設計者はparser generatorというとcode generationしないといけないと 思っているようなんですね。でもlexer部分は基本的にはregular expressionで、 こちらは既にlibraryが存在する(GPLでよければrxとか)。 parser部分も定型処理がほとんどで、library化も機械的な作業で可能でしょうし、 performanceも変わらないのではないかと。 でも存在しないんですね、open sourceのparser generatorのinterpreter(library)。

• もちろんルールをコンパイルしておいたほうがずっと速いんですが インタラクティブにやりたいのなら、prolog系はいかがでしょう。 ほとんど構文規則そのまま書いておけば処理系が勝手にパーズしてくれたような (もう全然触っていないのでやり方を忘れてしまいましたが)。 Schemeにもschelogというprologもどきがありますね。ちょっと遊んでみようかな。--Shiro
• prologによるimplementとなるとpatternにmatchするまでback trackを重ねて総当たりですね。 制御屋の欲しがるものですから、 いくら華麗な技をもっていても足の遅いplayerは選考枠に入りません:-) 制御屋は"どこでもstate machine"な人種です。 華麗な"lambda"よりも、どろくさくても実効の上がる"goto"を選択するんです:-p schemeとは対極の世界に住まふ人種なのかもしれません。
• parser generatorのlibraryについて;　　　　 regular expressionのように内部でcompileすれば、performanceの低下は最小限です。 parser generatorもregular expression同様、 pattern match部分は最終的にstate machineのtableになり、 のこりは、reduce shift accept stackの操作といったparserの定型処理の部分とになります。 後者は既にlibrary化されていたりするので、後はstate machineのtableを...と道のりはそんなに遠くない。 じゃあ自分で作ればとなるんですが、制御屋は経験からくる信頼性も欲しがるんですね。 新しい実装方法には、おおいに興味がありますがperformanceは重要です。 --toki?

• でも、on-the-flyでコンパイルするregular expressionのライブラリで、 完全にDFAにしてしまうものってあまり無いのでは? 複雑なregexpだと状態数が爆発 しますし、いろいろ拡張されたregexpはそもそもregular grammerをはみ出た 範囲を扱っているし… Spencerの新しいregexでは必要に応じて部分的にDFAにするとかっていう やり方をしていたような。PCREはどうだったかな。 で、NFAにするのならどっちにせよバックトラックするわけですな。 --Shiro (2002/05/21 13:56:38 PDT)

• ひとつづつ；
  • 完全にDFAにしてしまうregular expressionのライブラリ；　　　　 DFA -> state machineのregular expressionのライブラリですね。 はい、ほとんど棲息していることが知られていないことは、ヤンバルクイナ級かも知れません。 私は、いくつかの実装の棲息を確認しています。 ほとんどがflexをlibrary化したものです。実は私も作りました:-) net上では、rubyの森でextenionとして棲息しているやつの生態が観測できると思います。

　　　　　　http://www.inf.bme.hu/~pts/flex_rb-latest.tar.gz

• 複雑なregexpだと状態数が爆発する；　　　　 爆発してしまったものはしょうがない:-) が、state machineのtableが現実的でない程大きくなるということならば、 tableのcompaction技術が複数あって、flexにも実装されています。 case by caseですが予想以上に小さくなります。 perlやpythonのlexerはfull tableのそれよりも、少なくとも2桁は小さくなっていると思います。 その分遅くなるのは御愛嬌です。 grepのdfaやrxのdfaなどは、速度優先でfull tableを使っているため、lazy evaluationですね。 上記rubyのextensionは、1種類のtableしか扱えません。私のはfull function。 まあ、flexが使われる用途にはそこそこ使えるということで。

• PCREその他；　　　　 Spencerの新しいregexはdfaでも、state machine tableは生成していないのではないかと。 pcreは立派なnfa。それでもpcreはperlよりは速くなったといふ。ここまで単なる噂、真偽不明。 完全にstate machineなregular expressionは、制御の世界では使いでがあるんです。
  • staticなのでmemory管理が必要ない。OS組み込みとか。
  • バックトラック 0 なので、実行時間が入力dataによらず一定になる。 これは、real time制御の時には非常に有効です。 あっ、DFAでも最長検索の場合は、残念ながら多くの場合バックトラックしてしまいます。 バックトラック 0 が保証されるのは最小matchの場合ですね。
  • state machineのtableとactionへのjump tableだけなのでprogramが簡単でresource最小
  • ライブラリ化されているとcompilerが必要ないので機器組み込みが容易。 うーん、ニッチな上にschemeの用途とはぜんぜん関係ない。 --toki?

• なるほどなるほど。確かに、開発が済んだらstaticなtableとして 組み込んでしまえるのは大きな利点ですね。 それでもって、プログラム開発中はインクリメンタルにルールを追加したら その都度テーブルを生成してくれると嬉しいと。 flexの組み込みはSchemeにもあったら便利かも。--Shiro (2002/05/24 23:44:20 PDT)

こんなのありました。on-the-flyでコンパイルしてくれます。 Essence, an LR parser generator for Scheme --Shiro (2002/05/21 14:06:45 PDT)

• これは、興味深い。scheme48が必要と...gaucheで動いたら報告します。 --toki?

ところで、Gaucheのmacro適用部分は、展開された形でdebugするようになるのでしょうか。 それとも、元のままdebug可能になるんですか？ --toki? ネストを元に戻すにはどしたらいいんだらふ。

• 最終的には、hygienic macroを使った場合は展開前のソースコード情報を残すようにするつもりです。--Shiro

Tag: Macro