Compiling with ContinuationsとORBITの関係
前回の記事でも紹介したOlin ShiversのT Programming Languageに関する回顧録で
It had a big influence on Andrew Appel, at Princeton, who subsequently adopted a lot of the ideas in it when he and Dave MacQueen's group at Bell Labs built the SML/NJ compiler for SML; Andrew described this in the book he subsequently wrote on that compiler, Compiling With Continuations. ... So the lineage of the CPS-as-compiler-IR thesis goes from Steele's Rabbit compiler through T's Orbit to SML/NJ.
という文章があった。
確かに時系列的にもORBITがSML/NJに影響を与えているのは想像に難くないなとは思うのだが、どれだけはっきりと影響を受けているのかが気になった。
Compiling with ContinuationではReferencesにORBITの論文が含まれてはいるものの、本文中での言及は一回のみ。例えばIntroductionなどでは一度もORBITの名前は出てこないので、CPS変換の手法の多くがORBITから来ている、というような印象は受けない。
実際のところどうなのかなーと不思議に思っていたのだが、少し探してみるとAppel & Jim名義のContinuation-Passing, Closure-Passing Styleという論文が1988年に出ていた（POPL1989に出したとは書いてあるが、採択されたのかどうか？）。
この論文には随所にORBITの名前が出てきていて、かなり影響を受けているのがわかる。
なにせOverviewの第一段落に：
Rather than hack a register allocator into the abstract stack machine, we decided to try a continuation-passing style (CPS) code generator. Kranz’s ORBIT compiler shows how CPS provides a natural context for register allocation and representation decisions.
と書いてあるくらいで：
The ORBIT compiler translates CPS into efficient machine code, making representation decisions for each function and each variable. ORBIT does an impressive set of analyses in its back end, but they’re all tangled together into a single phase. We have a series of phases, each of which re-writes and simplifies the representation of the program, culminating in a final instruction emission phase that’s never presented with complications.
とORBITを下敷きに、より綺麗なアーキテクチャにしてあることが窺える。
他にもRABBITやCAMへの言及もあり、いくつかの先行研究に影響を受けていることがわかるのだが、Overviewやベンチマークの対象などで最も頻出しているのがORBITだ。さらに謝辞にORBIT作者のDavid Kranzへの言及がある：
David Kranz made many useful suggestions about benchmarks.
というわけでSML/NJがCPS形式をIRにした上で最適化しているのがORBITの強い影響を受けてのことだというのは確かのようだ。Compiling with Continuationsではまあ先行研究への言及よりも手法の解説を優先した、ということだろう。
またこのContinuation-Passing, Closure-Passing Styleという論文はCompiling with Continuationsのさわりだけ把握したい、という場合は便利ではないだろうか。
ちなみにAppelの有名なSSA is functional programmingもORBITコンパイラの作者の一人であるKelseyのA correspondence between continuation passing style and static single assignment formを下敷きにしている。
