ログインしてさらにmixiを楽しもう

コメントを投稿して情報交換！
更新通知を受け取って、最新情報をゲット！

関数型言語コミュの処理系の作成、実装技術関連

ログインして参加する

  • mixiチェック
  • このエントリーをはてなブックマークに追加

処理系の作成、実装技術関連

mixiユーザー 2005年02月07日 12:20

言語を作る側のトピックです。
語って下さい。
質問して下さい（自分はこっちですが...）。

コメント(19)

[1] mixiユーザー 02月07日 12:26

というわけで質問 :-)

scheme の継続の実装について調べているのですが、イマイチよく分かりません。簡単に作れて、そこそこ性能が出る実装法って、どんなものがあるのでしょうか？

[2] mixiユーザー 02月07日 12:51

SECDマシンじゃだめ？性能までは保障できないけど。

http://www.yuasa.kuis.kyoto-u.ac.jp/~nobu/study/palm/hood.html

私は良く知りませんがSECDR-Schemeとかtiny-Schemeとか有ったはず。

scheme実装で有名なShiroさんのページを紹介してみたり。

http://www.shiro.dreamhost.com/scheme/index-j.html

沖ソフトウェアを紹介してみたり。

http://www.okisoft.co.jp/esc/go/metrics.html

すいません。不勉強で、これ位しか判りません。

[3] mixiユーザー 02月07日 13:43

SECD マシンの方法って VM 作って、それ用のバイトコード生成する方式、という認識で合ってますか？

VM 作るとなると、一仕事になるような気がするんですが、そんな事ないのかな？？？

適当に、簡単な Lisp インタプリタみたいな感じで済ませられるなら済ましたいなぁ、と (^^;

[4] mixiユーザー 02月07日 15:36

「そこそこの性能」がどのくらいを指すのか、また、そのための処理系の他の部分にどのくらい影響を与えてよいのか、等によって答えは変わってくると思います。継続をどう実装するかは処理系のデザインのかなり根本的な部分に影響を与えるので。

「簡単なLispインタプリタ」というのもどういう意味で簡単なのか…GCのある言語なら、制御フレームを全てヒープに置くことで継続はわりと簡単に実装できます。

継続の実装戦略を昔、簡単に分類したことがあるので貼っときます：
http://lists.sourceforge.jp/mailman/archives/gauche-devel-jp/2002-November/000018.html

[5] mixiユーザー 02月07日 18:08

まさか gauche の川合さんから書き込みがあるとは。（良い意味で）予想外でビックリ。

確かに「そこそこの性能」ってのは分かりにくいですね。日本語特有の曖昧な良く分からん表現だったかもしれません。

改めて問われるとなかなか難しいのですが、せっかくなので、書いてみます :-)

そもそも scheme の処理系の内部に興味をもったのは、scheme の事を良く知らなかったからです。処理系を作れば、その過程で徐々にいろんな事が分かってくるだろう、という考えが背景にあります。

そして多分、処理系ができた時には、作った処理系で、scheme の勉強をすると思います。ですので「そこそこの性能」＝学習用のプログラムが支障なく動く程度の性能と読み替えてもらっても問題ないかと思います。

あと、実装する手間が同程度ならば、速い方が良いなあ、という気持ちもあったかも。

こんな感じです :-)

[6] mixiユーザー 02月07日 18:37

「簡単な Lisp インタプリタ」の方ですが、これは Lisp 処理系の入門に書かれているようなものを想定していました。

リストをパース（？）しながら順次実行していくようなタイプの処理系です。

ネットで知ってるのは

LispBook http://204.241.96.11/LispBook/

ぐらいしか見当たらないのですが、そういう処理系をイメージしていました。

あ〜でも、tail recursion とかを考えると、そもそもそういう処理系じゃダメなのかな...。

C/C++ で処理系作ったとして、C/C++ のスタックを操作しない限り、無理なのかな。
となると VM を作って、scheme のコードを VM のバイトコードに変換するしか方法が無いような気がしてきた...。

この認識は合ってるのでしょうか？うーむ。

[7] mixiユーザー 02月07日 18:49

実装言語はC/C++ですか? それでソースツリーをそのまま手繰りながらevalを再帰的に呼んでいますか?

その場合は、現実的に取れる選択はSCM方式だと思います。他の方式に比べると重いですが、よっぽどヘビーに継続を使わない限り(例えばユーザレベルスレッドを継続を使って組んで、何千とスレッドを走らせるとか)、支障が出る程にはならないんじゃないでしょうか。何よりCレベルでの再帰構造を書き直さなくて良いので楽です。

SCM方式はSCMのソースコードを見てもらうのが一番良いと思うのですが(他にもGuile等がこの方式を使っています)、基本的なアイディアは：

(1) 初期化時にCのスタックポインタ(sp)の値を覚えておく(base)
(2) call/ccが呼ばれたら、setjmpして(pcを含めた)その時点のレジスタの内容をjmp_bufに得て、jmp_bufの内容とbaseからspまでのスタックの内容をヒープにコピーして継続オブジェクトとする。
(3) 継続が起動されたら、セーブされたスタックの内容をbaseからスタックエリアに上書きし、保存しておいたjmp_bufへとlongjmpする。但し、継続起動時点でスタックエリアが上書きに十分な大きさが無い場合は、ダミー関数を再帰的に呼ぶことで十分な領域を確保する。

(3)でlongjmpすると(2)のsetjmpから戻ってきます。

あと、この方法を使うとCの関数から複数回戻ってくることが起きるため、
リソース管理に注意が必要です。
http://www.atdot.net/~ko1/w3ml/w3ml.cgi/langsmith/msg/166

[8] mixiユーザー 02月07日 18:56

>沖ソフトウェアを紹介してみたり。

>http://www.okisoft.co.jp/esc/go/metrics.html

間違いました。す、すんません。

http://www.okisoft.co.jp/esc/go.html

[9] mixiユーザー 02月07日 19:05

「C/C++のスタックを操作しなければならない」のは、Cから再帰的にevalを呼ぶためにSchemeの制御スタックフレームとCのスタックフレームがマシンスタックに混在してしまうのが本質的な理由です。それを避けられれば、VM/バイトコードを使う必要はありません。

(でも実際には手でSchemeの制御スタックを管理するコードを書くのは面倒なので、VMにしてしまった方が楽ですが)。

具体的には、CからSchemeを再帰で呼ばずに、全部トランポリンで書くようにします。コードを示そうと思ったんですが長くなりそうなので、時間ができたらWiLiKiあたりに何か書きます。

[10] mixiユーザー 02月07日 20:01

＞ shirok さん

実装言語は C/C++ を想定しています。
「想定しています」と言う事で、まだ書き始めていません。

継続の実装が良く分からず、また直感的に、これは処理系の根幹に大きく影響を与えそうだと感じたため、コードがまだ書けない状況にあります (^^;


ソースツリーをそのまま手繰りながら eval を再帰的に呼び出していくのが、分かりやすかったし、シンプルな感じがしたので、その方式でできるなら、それで実装したく思っておりました。

でも、shirok さんがおっしゃっておられるように、scheme の制御スタックフレームと C のスタックフレームを上手に管理するのは、自分にはチト厳しいかな、と。

上手いことトランポリンでさばけるコードを書けば、良さそうなんですが、なんかイマイチ良く分からない状況です (^^;


肝心の継続の方ですが、一連の議論を通じて、なんとなく分かって来た様な気がします。


VM でスタックを自由自在に扱えるような状況を整えておいた方が、何かと便利そうな感じがしてます。ただ、この場合、scheme のソースをバイトコードにコンパイルしないといけないので、その辺りが（個人的には）面倒な気が...。

シンプルにトランポリン化できれば、それが一番良さそうなんだけど、順次 eval を呼んでいく素朴な実装に比べると、素直な実装ではなくなる様な気がします。でも、VM 作って、VM 用のコンパイラ作るよりも、トータルの実装コストは少ない気もするんだけど...。
いや、でも、scheme の関数呼び出しをトランポリン化したとしても、自前で scheme のスタックを処理していかないといけないので、それって、結局 VM 作るのと同じだよな、と思ったりして。うーん。最初に ゆーあい さんに教えてもらったように素直に SECD マシンにした方が良いってことなのか？？？


「プログラマなら一度は Lisp を作る」なんていう言葉を聞いた事があります。個人的に少し時間ができたので、どうせなら現代的な scheme にチャレンジしてみるか、と思っていろいろ調べてみたら、なかなか結構難しい。

まだまだプログラマには成り切れていないのかな、と思ったりして (^^;


# WiLiK の方、楽しみにしております :-)

[11] mixiユーザー 02月07日 20:10

＞ゆーあい さん
沖ソフトウェアのページ、良いですよね :-)
僕も読みました。

Java だと５００行で Lisp が書けちゃうらしいので、結構ビックリしました。
# ガベコレは無いらしいですけど...。


僕の方は、東大の scheme 演習のページで勉強しました。

http://www-ui.is.s.u-tokyo.ac.jp/~hara2001/scheme/

最初、lexical scoping の実装方法が良く分からなかったのですが、このページで「環境」という概念が理解できた（ような気になりました）。

[12] mixiユーザー 04月02日 23:45

お久しぶりです。

参考になりそうなHPがあったので、勝手に張ります。


http://www.is.s.u-tokyo.ac.jp/~vu/01/jugyo/processor/process/soft/compilerresume/index.html

http://min-caml.sourceforge.net/
こっちは,中身までは読んでいません。

[13] mixiユーザー 04月03日 00:11

CPSで思い出しましたが、

Compiling with Continuations
http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521416957

は楽しい本です。ゆーあいさんのリンクから察するにこんな内容を某大学では学生に教えているようですが、ひょえーって言う感じです。

min-camlもすばらしいです。いろいろ省略している部分も多いので、現実的な処理系に近いものを目指す人にはちと物足りないですが、確かにこれなら学生さんにも教えられるかもしれない…という気がします。

[14] mixiユーザー 04月03日 10:19

>nobuさん
>するにこんな内容を某大学では学生に教えているようですが、ひょえーって言う感じです。

そうですよね。羨ましい限りです。
そこそこの学生と熱心な先生がいれば、こういう授業が出来るんでしょうね。

[15] mixiユーザー 09月20日 00:41

はじめまして、masamicと申します。

いま、仕事でS式をつかった計算処理系（∴LISPでは無い）を独自設計・実装にしたことにインスパイアされて、Java用のLISP処理系（ライブラリとしても使える。つーか、そっちのほうが主目的）を作成中です。

＃関数型言語でないのですが、並行してFORTHも作っています。（こちらは最近のOSへの対応方法を考えるため、ペンディング中です。）
FORTHコミュ⇒http://mixi.jp/view_community.pl?id=121720

とりあえず、シェルは無いけど、(+ 1 2)位はできるようになっています。まだラムダ式が処理できないのですが、これが出来れば、LISP1.5以上Will o'Lisp 未満くらいの機能（および実装方法）で最初のバージョンをリリースできそうです。その後はSchemeを目標に機能向上させたいと思います。

ANSI Common Lisp にするつもりはありませんｗ。

コードは sourceforge.net にプロジェクト「FLISP-J」に置いてます。
⇒https://sourceforge.net/projects/flisp-j/

よろしくお願いします。

[16] mixiユーザー 09月20日 13:25

あ、よく見るとsaitoさんもscheme狙ってる（た？）みたいですねｗ。
＃2月ごろみたいですけど。

私はLisp1.5の「Atomも一部はConsリスト」ってのからは脱却した程度の処理系を考えています。オブジェクト指向言語Javaで書くのですから、当然Atomはクラスです。

AtomもConsもLispRootObjectクラスのサブクラスになってます。

組み込み演算子はJavaのリフレクションを使って、自由に組み込み演算子を取り替えられるようにしたいなぁ。

とか考えて現在実装中です。

saitoさんがびっくりされている通り、結構小さくかけますよ。GCはJava任せになりますけど。
＃ま、裏にはCGと膨大なライブラリがあるからなんですけどｗ。

[17] mixiユーザー 08月27日 19:29

Turner さんの論文 A New Implementation Technique for Applicative Language に関してなのですが、この SK マシンを実装してみたことがあるかた、いらっしゃいますでしょうか？

論文中に、U コンビネータ（引数に関数とリストをとり、リストを car と cdr に分解して apply する）は再帰的に引数を評価する、とあり、また、相互再起のある関数は Y (U ([f] (U ([g] (... のようにコンパイルする、とあるのですが、その通り実装すると、U の引数の評価中にまた U の引数の評価が起き、止まらなくなりました。
U コンビネータをプリミティブとし、car と cdr は U を使って実装していたのですが、これを逆にして U コンビネータは car と cdr に書き換える実装にして再帰的な評価をおこなわないようにし、car と cdr で再帰的な評価が起こるようにしたところ、うまくいきました。
私が何かかんちがいしているのか、論文の通り実装するとハマるのか、相談したいのですが...

[18] mixiユーザー 08月28日 00:24

コンビネータとかは、引数をイーガに評価してはいけないのでは?
よくわかってませんが。

[19] mixiユーザー 08月28日 07:58

真偽値も if も自然数も cons もλ式で表現する、という実装をすればそうなのですが、λ式以外のプリミティブ値を導入しようとすると、イーガな評価が必要になります（たとえば if の条件節とか）。
正確にはコンビネータでなく、U オペレータと言うべきなのかもしれません（論文でコンビネータと言っているので、そのままそう呼んでしまいました）。

ログインすると、みんなのコメントがもっと見れるよ

mixiユーザー
ログインしてコメントしよう！

関数型言語 更新情報

関数型言語のメンバーはこんなコミュニティにも参加しています

星印の数は、共通して参加しているメンバーが多いほど増えます。

関数型言語

人気コミュニティランキング

困ったときには

関連ワード

mixiで趣味の話をしよう
新規登録（無料）

このページの上部へ