なつたん

多分、ひげぽんさんが必要としているのは、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 Tools、Concepts, Techniques, and Models of Computer Programming、How to Design Programs、A Retargetable C Compiler: Design and Implementation、コンパイラ入門、コンパイラ構成法と調べました。

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