« C++のvector | Main | STLFilt »

2007.08.18

末尾最適化の本

多分、ひげぽんさんが必要としているのは、Essentials of Programming Languages。通称EoPL。

7章が継続渡し(Continuation-Passsing Interpreters)で60ページほど、それを引き継いで8章(Continuation-Passing Styele)で40ページほど末尾最適化について書かれてあると思う。「と思う」とあやふやなのは、8割近く意味がわからないから。ちょっと悔しい。継続がらみで100ページ使っている!

もうちょっと突っ込んで内容を書きます。
Section 8.1がTail Formというタイトルで、(define fact (lambda (n) (if (zero? n) 1 (* fact (- n 1))))))から始まります。それをiteratorと、accumlatorで書き直します(SICPレベル)。次にソースコードのBNFの説明が入り、ソースコードをhead positionとtail positionに分解。さらに、simple expressionをBNFで定義。いろんな式を、tail formか、simple expressinに分類。add1(x)はsimpleかつtail form、(f + (x, y))はtail formだけどsimpleじゃない、proc(x) add1 ((f x))は、simpleだけど、tail formじゃない。

いったんまとめが入ります。
Tail form implies iterative control behavior.

If an expression is in tail form, and any procedures accessible through vairable bindings are also in tail form, then expression will execute with iterative control behavor.

次に、tail formのBNF表記があって、上の末尾最適化されていない階乗を末尾最適化で書き直し。続いて練習問題、ここまでで8ページ。練習問題の一つはこんな感じ。

Exercise 8.10:write a Scheme procedure tail-form? that takes a program in the language of figure 8.1 and determines whether or not it is in tail form, by checking the abstract syntax tree of the program against the grammar of figure 8.3 .

figure 8.3がtail formのBNFなので、ひげぽんさんの求めている物に近いと思う。

Section 8.2からconverting to Continuation-Passing Styleとなって、疑似コードが続きます。続くのですが、ここから理解できない。再帰呼び出しを、継続渡しStyleの再帰呼び出しに変換している所までは分かる。これが、コード書く人間にこう書けと言っているのか、インタープリターレベルでこう変換できると言っているのかどっちなんだろう。どちらにしても、アセンブラのcall/jmpの枠組みではなく、継続の視点で再帰呼び出しを説明している所が興味深いです。


以下、蛇足。

Compilers: Principles, Techniques, and ToolsConcepts, Techniques, and Models of Computer ProgrammingHow to Design ProgramsA Retargetable C Compiler: Design and Implementationコンパイラ入門コンパイラ構成法と調べました。

末尾再帰について全く載っていないか、紹介程度で終わってます。意外に書籍化されていない情報なのかもしれません。

|

« C++のvector | Main | STLFilt »

Comments

おお。丁寧に解説ありがとうございます。
EoPLの書評などを漁ってみます。
それにしてもブログ面白いですね。早速subscribeさせていただきました!

Posted by: ひげぽん | 2007.08.19 at 01:45 PM

この後、googleで調べてみましたが、CPS変換がキーワードみたいですね。興味が出てきました。

ひげぽんさんの「関数型言語を学ぼう」でSICPの勉強を始めた一人なので、ひげぽんさんには感謝しています。
まだ半分くらいですが、確実に視野は広がって来ています。

Posted by: なつたん | 2007.08.20 at 04:46 AM

http://www.takeoka.org/~take/ailabo/prolog/metakuta.html

ここの、3.2. テイル・リカーシブ・インタープリタにもヒント発見。
そうか、コンパイラとインタプリターでは、実現方法が全然違っていて、ひげぽんさんが知りたいのはこっちの方かも。


Posted by: なつたん | 2007.08.20 at 07:33 AM

> この後、googleで調べてみましたが、CPS変換がキーワードみたいですね。興味が出てきました。

そうなんですよ。Continuation Passing Style を理解したいと前々から思っています。
鋭いですねー>なつたんさん

>ひげぽんさんの「関数型言語を学ぼう」でSICPの勉強を始めた一人なので、ひげぽんさんには感謝しています。
>まだ半分くらいですが、確実に視野は広がって来ています。

それはとてもうれしいです。
過去ブログを読ませていただいて、なつたんさんは常に勉強されていて偉いなあと思いました。

>ここの、3.2. テイル・リカーシブ・インタープリタにもヒント発見。
>そうか、コンパイラとインタプリターでは、実現方法が全然違っていて、ひげぽんさんが知りたいのはこっちの方かも。

お。この資料良いです!。
正直このあたりは1週間位まえに理解してしまったのであれですが、日本語でこのことが書いてある資料ををはじめて見ました。

Posted by: ひげぽん | 2007.08.20 at 10:34 PM

ひげぽんさん

いえいえ、ひげぽんさんに影響されて勉強している部分も多いですよ。
5年前は「そういうのは、初めて読む486、Minix本くらい読んでからじゃないかぁ」と某スレで応援していたのですが、
いつの間にか遠くに行ってしまわれた感は持っていました。MonaもSchemeのshellも期待しています。

Posted by: なつたん | 2007.08.21 at 06:56 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/16153547

Listed below are links to weblogs that reference 末尾最適化の本 :

» [book] Essentials of Programming Languages [ひげぽん OSとか作っちゃうかMona-]
なつたんさんから、僕が探しているのはEssentials of Programming Languagesでは無いかとのアドバイスを頂きました。 ありがとうございます!。 なつたんさんの紹介してくれている「なつたん: 末尾最適化の本」記事の中で引用されている部分を見ていてもかなり今知りたいこ... [Read More]

Tracked on 2007.08.19 at 01:56 PM

« C++のvector | Main | STLFilt »