Pyrolog 20年の歩み
20 Years of Pyrolog (pypy.org)
要約
この記事は、RPythonベースのProlog実装であるPyrologが20周年を迎えたことを記念した、作者による個人的な回顧録です。Pyrologは広く利用されることはありませんでしたが、興味深い研究を生み出し、他のRPythonプロジェクトに影響を与えました。記事では、初期の設計からJITコンパイラとの連携、継続ベースのアーキテクチャ、そして他のプロジェクトへの影響まで、20年間の開発の変遷を詳細に振り返っています。
全文翻訳
Pyrolog 20年の歩み
2006年11月12日、私はRPythonベースのProlog実装であるPyrologの最初の生き残ったコミットをPyPyリポジトリに投入しました。既に2006年の春から取り組んでいました。その年は最初のPyPy EU研究プロジェクトを終え、私はデュッセルドルフ大学での学士課程を終えるところでした。それから20年が経過したので、このプロジェクトについての個人的な回顧録を書きたいと思いました。Pyrologは実際にユーザーを獲得することはありませんでしたが、それでもいくつかの興味深い研究につながり、他の多くのRPythonプロジェクトに影響を与えました。
背景¶
EUプロジェクトの一環として、制約プログラミングをPyPyに実装するなど、多くのことを約束していました。この作業のために、私はClocksinとMellishの『Programming Prolog』[[CM2003]]を読み、その後『The Art of Prolog』[[SS1994]]を読みました。
2006年3月、PyPyプロジェクトのパートナーであるLogilabは、ベルギーのルーヴァン・ラ・ヌーヴでスプリントを主催しました。そこにはPeter van Roy氏とGecodeに取り組んでいる研究者たちが参加していました。計画は、PyPyに何らかのユニフィケーションと制約ソルバーを追加することでした。Logilabの人々はVan Roy/Haridiの書籍[[VH2004]]に非常に触発されており、私は後に彼のProlog実装のサーベイ論文[[VanRoy1994]]を研究しました。
2006年には、指導教官であるMichael Leuschel氏のデュッセルドルフでのProlog講義にも参加しました。その間、RPythonでPrologインタプリタの開発を始め、後にPyrologと名付けました。残念ながら、初期のコミット履歴の多くは失われており、SubversionからMercurialへの移行が正しく行われず、現在コードアーカイブがどこにあるのかも不明です。
2006/2007 初年度¶
Pyrologの最初の形態は、オブジェクト指向のRPythonコードでユニフィケーションを比較的単純に実装したものでした。論理変数はインデックスを格納し、そのバインディングはグローバル配列にそのインデックスで格納されていました。
[画像: メモリレイアウトの図]
Pyrologのメモリレイアウト [[Bolz2007]]
このバージョンでは、選択点を表現するためにインタプリタレベルで例外ハンドラを使用し、例外を発生させてそれを上位で捕捉することでバックトラックを行っていました。実行すべき呼び出しを格納するために、継続ベースのアーキテクチャを使用していました。これらの成功継続はヒープに格納され、継続的に割り当てられ消費されていました。このアプローチは、Paul TarauのBinProlog[[TB1990], [[Tarau1992]]から取られ、他のいくつかのProlog論文[[Lindgren1994], [[Neumerkel1995]]にも基づいていました。
Prologプログラムが典型的に行う深い再帰に対処するため、このバージョンのPyrologはRPythonのスタックレス変換 [[BR2007D071]]に依存していました。これはホストスタック(つまりCスタック)をアンワインドし、ホストスタックオーバーフローが近づくとその情報をホストヒープに格納するものでした。Cスタックフレームをこのようにヒープに格納する際、ある程度の末尾再帰最適化も行っていました。当時はこのアイデアに非常に熱中していました。しかし、バイナリサイズが2倍になり遅くなるため、実際にはあまり実用的ではないことが判明し、最終的に削除されました。
また、このバージョンのPyrologで最初のRPython JITを使用する実験も行いました。そのJITは部分評価ベースのメソッドJITであり、いくつかの小さなPythonプログラムを高速化することに成功しました。しかし、Pyrologに対してはあまり効果がなかったと思います。
このバージョンのPyrologのパフォーマンスは非常に残念なものでした。私の学士論文[[Bolz2007]]では、SWIやSicstus Prologと比較していくつかの測定を行いました。この時点では、SicstusはPyrologよりもしばしば1桁高速でした。
論文では、PythonコードからPrologを呼び出す方法も実装し、ケーススタディとしてPythonでTic-Tac-ToeのGUIを実装し、ゲームロジックをPrologで記述しました。
論文を終えて間もなく、変数の表現を変更しました。グローバルバインディング配列へのインデックスではなく、各変数オブジェクトが独自のバインディングを格納するようにしました。例外ベースのバックトラックアーキテクチャは、さらに2年間維持されました。
2008/2009 PyPy側のJIT開発¶
EUプロジェクト終了後、RPythonメタJITの様々な新しいアーキテクチャアイデアに取り組み始めました。Armin Rigo、私、そして他の数名が2つの新しいプロトタイプを作成しました。それらに満足できなかったため、2008年にArminと私は新しいトレースベースJITのプロトタイプをPrologで記述して実験を開始しました。Prologを使用した理由は、そのパターンマッチングとメタプログラミングの容易さにより、さまざまな設計をより簡単に実験できたためです。
2008年末から2009年にかけて、Armin、Maciej Fijałkowski、私、そして他の人々は、その設計をRPythonに移植し始め、pyjitpl5(名前に含まれる「pl」は「Prolog」を意味します)と名付けました。これは現在のPyPyメタJITコンパイラの基盤であり、Eurostarsプログラムの2番目の(小規模な)PyPy EUプロジェクトの主題となりました。
最終的に、Prolog版JITに関する論文[[BLR2010]]をLOPSTR 2009で発表しました。
2009-2010 新しいPyrologアーキテクチャ:継続の活用¶
2008年と2009年は主にPyPyと新しいJITに取り組んでいましたが、2009年のクリスマス休暇中にPyrologの開発を再開しました。スタックレス変換は新しいJITと互換性がなかったため、現在も使用されている別のアーキテクチャに切り替える必要がありました。Pyrologアーキテクチャの最初のバージョンは既に成功継続をヒープに格納していました。このリファクタリングの目標は、失敗継続も再ified RPythonオブジェクトとして格納することでした。
# 単純化されたメインインタプリターループ
def interpret(sc, fc, trail):
while not sc.is_done():
try:
sc, fc, trail = sc.activate(fc, trail)
except UnificationFailed:
sc, fc, trail = fc.fail(trail)
これにより、Prolog呼び出しをインタプリタで実行している間、ホストスタックの使用は完全にフラットになりました。Prolog実行を継続するために必要な状態は、常にヒープ上の継続オブジェクトに格納されます。したがって、インタプリタは、成功時にアクティブになる継続と、失敗時にアクティブになる継続の2つの継続を扱います。
さらに、バックトラック時に元に戻す必要がある変数バインディングを格納する(セグメント化された)トレイルオブジェクトがあります。失敗継続は、アクティブ化されたときにバックトラックする必要があるトレイルの部分への参照を持っています。
このアプローチの欠点は、インタプリタがすべての成功および失敗継続のために継続的にヒープデータを割り当てる必要があることです。これはRPythonのGCに大きな負荷をかけます。また、項のユニフィケーションは依然としてホストスタックを使用するため、非常に深い項をユニファイすると問題が発生し、実装レベルの再帰エラーにつながる可能性があります。
JITサポート¶
リファクタリングの真の目的は、インタプリタをJITフレンドリーにすることでした。インタプリタはProlog呼び出しに再帰を使用しなくなったため、Prologレベルのループ(再帰として表現される)はJITによってトレースできます。継続の継続的な割り当ては、RPython JITのアロケーション除去によって最適化できます。これらすべてが正しく機能すれば、Pyrologのパフォーマンスは非常に良好になり、適切なマイクロベンチマークではSicstusを大幅に上回ることがよくあります。
[画像: /images/2026-pyrolog-vmgen.svg]
Pyrolog VM生成と実行時間の比較 [[BLS2010]]
残念ながら、これは主に予測可能な制御フローを持つコード、理想的にはきれいなループを持つコードの場合に当てはまります。Prologの主な魅力はバックトラック検索を行うことなので、興味深いPrologライクなプログラムでは、制御フローは通常あまり予測可能ではありません。制御フローが複雑になりすぎると、継続はJITが最適化する領域を超えて生存し、再びヒープに割り当てる必要が出てきます。そのため、Pyrologには非常に極端なパフォーマンスの断崖があります。
このバージョンのPyrologについて、PPDP 2010で論文[[BLS2010]](Michael Leuschelと私の同僚David Schneiderとの共著)を発表しました。その会議は私にとって非常に興味深く、重要なものでした。Paul Tarau(BinPrologの発明者であり、Pyrologのインスピレーションの一つ。彼は後に2016年の仮想マシンサマースクールで素晴らしいPrologの講演を行いました)、Olivier Danvy(彼の論文[[BD2004]]を引用すべきでした。本当に nicest peopleの一人)、Kenichi Asai(部分評価とリフレクションに取り組んでいた)など、多くの研究者と会いました。博士課程のこの時期、私は比較的意欲を失っていましたが、これらの研究者との会話は信じられないほど励みになりました。
[画像: https://www3.risc.jku.at/conferences/ppdp2010/photos/img_8487.jpg]
会議の夕食会場であるグムンデンへのバス旅行中、誰かが循環項(つまり有理木)のユニフィケーションの実装方法を説明してくれました。残念ながら、それが誰だったかはもうよく覚えていませんが、Thierry Martinezだったかもしれません。これにより、循環項ユニフィケーションのサポートを実装しました。私はこのトリックが今でも大好きで、今年初めにPhil Zuckerに説明しようとしました。いずれブログで取り上げたいと思っています。面白いユースケースについては、DFA最小化のための有理木ユニフィケーションに関する私のブログ投稿を参照してください。
2011/2012 Prologサポートの拡充¶
2011年から2012年にかけて、Pyrologに機能を追加するいくつかの学士・修士論文を指導しました。その過程で、Prologモジュール、DCG、属性付き変数、freeze、whenのサポートを追加しました。これらはすべて、私の優秀な学生であるSven HagerとRené Bartelmusによって行われました。これにより、基本的な実行モデルは(いくつかの小さな追加とともに)そのまま維持されました。また、Pyrologのエラーメッセージを改善し、例えばProlog例外のバックトレースを表示するようにしました。
Pyrologは、David SchneiderのARM JITバックエンドの初期テストケースとしても使用されました。2011年1月、彼は既にBeagleBoard上でJITを使用してPyrologマイクロベンチマークを実行できましたが、バックエンドはより複雑なPythonベンチマークを実行する前にデバッグが必要でした。
2012年は主に博士論文[[Bolz2012]]の執筆に費やしました。そこには、PPDP 2010の論文に基づいたPyrologに関する章が含まれています。その章では、Pyrologが比較的うまく機能するという事実が、RPythonメタJITが非常に多様な言語に使用できることを示していると主張しています。
また、メタトレーシングJITが、より古典的な部分評価アプローチとどのように機能するかを比較する別の章もありました。そのコードは再びPrologで記述され、元々は ここにブログで 提示されました。
この時点でデュッセルドルフを離れました。2012/13年の冬学期には、ポスドクとしてHasso-Plattner-Institutで博士課程の共同指導教官であるRobert Hirschfeld氏のもとで半年間ベルリンに滞在しました。2013年には、King's CollegeでLaurie Tratt氏と共同で働き始めました。
この時点で、Pyrologの主要な物語はほぼ終わりです。その後数年間は、ごくわずかな改善しか行われませんでした。しかし、Pyrologのアイデアは他のプロジェクトでフォローアップ研究につながり、それらについて議論したいと思います。
2012/2013 圧縮項¶
2010年と2011年にPyrologで実装しようとしたものの、最終的にマージされなかった実験の1つに、圧縮項がありました。このアイデアは、特定の項のパターンが繰り返し現れるという観察から来ています。例えば、連想リストは[A/B|C]という形式の項を繰り返します。各エントリに対して個別のリストオブジェクトとペアオブジェクトを割り当てる代わりに、その構造の説明である「形状」を共有し、各エントリのキーと値をフラットなストレージデータ構造に格納する計画でした。これにより、各エントリはより少ない間接参照を持ち、より少ないメモリワードを使用できるようになります。
しかし、変数バインディングが後からこれらのパターンを作成できるため、Prologでこの圧縮を機能させることはできませんでした。当初は未束縛の変数を含んでいたフィールドが、後に構造化された項全体を参照できるようになり、圧縮の機会は構築後に変化し、バックトラック時にさらに変化しました。
2012/2013年の冬にHPIに6ヶ月滞在していた際、Tobias Pape氏と協力して、lambというより単純な関数型言語、後にTheseusと呼ばれる言語で同じ圧縮アイデアを実装しました。Tobias氏はその後数年間、このアプローチをさらに推し進めました[[PBH2015], [[PBH2017]]。私の希望は、問題を十分に理解してPyrologに移植することでしたが、その部分は実現しませんでした。しかし、後にPycketでこれらのアイデアを試しました。
2013 ユニフィケーション¶
2013年にロンドンでの仕事を開始しました。私たちの研究プロジェクトの目標は「言語構成」でした。Edd Barrett、Laurie Tratt、私は、PyPyと別の言語の組み合わせたRPython実装を、2つの言語を統合する方法とともに実装しました。最初に試したペアは、Unipycation[[BBT2013]]というプロジェクトでPyPyとPyrologを組み合わせることでした。このプロジェクトにより、PythonからPrologへ、またその逆の呼び出しが可能になりました。RPythonメタJITは、この言語境界を越えて最適化し、クロス言語インライン化さえ実行できます。残念ながら、この組み合わせには非常に説得力のあるユースケースを見つけることはできませんでした。
2013 Pycket¶
同じく2013年に、Sam Tobin-Hochstadt氏とJeremy Siek氏と共に、RacketのRPython実装であるPycketの開発を開始しました。後にTobias Pape氏とSpenser Bauman氏も参加しました。Pycketのアーキテクチャは、Pyrologの継続アプローチに間接的に影響を受けていました。CEKマシンをRPythonに比較的直接実装しました。これもフラットなホストスタックを使用し、call/ccなどの実装を比較的簡単に行えるようにしました[[Pycket2015]]。
Pycketで採用した素晴らしい新機能の1つは、IBM Research[[HWISN2011]]に由来する「偽ループフィルタリング」でした。これは、関数呼び出しをトレースする際に呼び出しコンテキストを考慮し、JITが1回しか実行されない「偽ループ」を認識するのを防ぎます。私は常にこのアイデアをPyrologに移植したいと考えており、プロトタイプを実装しましたが、マージできるほど十分に洗練させることはできませんでした。
Pycketのもう1つの実装技術は、継続オブジェクトをはるかに小さくすることでした。これにより、ヒープにエスケープするケースの影響を軽減できました。このアプローチはPyrologにも取り入れられました。
2022-2024 EffektのRPython実装¶
2016年にKing's Collegeを離れ、2017年からデュッセルドルフ大学(半日勤務)に戻りました。2022年、Marcial Gaißert氏とJonathan Brachthäuser氏と共同で、Effektおよび関連言語のRPython実装に取り組み始めました。これは、RPythonにおけるエフェクトハンドラのJITの実装でした[[GBB2025]]。ここでも、インタプリタが操作でき、その上にエフェクトハンドラを追加できる、再ifiedスタックフレーム/継続を持つアプローチを使用しています。
2026 Gitへの移行¶
この秋、ある研究者からPyrologに関するメールを受け取り、今年で20周年であることを知りました。その後、残っていたMercurial履歴の様々な部分を新しいGithubリポジトリにマージし、いくつかのバグを修正し、いくつかの便利な機能を追加しました。
[画像: /images/2026-pyrolog-screenshot.png]
Pyrologのスクリーンショット
結論¶
[画像: /images/2026-pyrolog-activity-by-month-authors.svg]
メインブランチにおける月ごとのコミット数(著者別)
Pyrologは、PyPy自体よりも常に研究的なプロジェクトでした。PyPyはオープンソースプロジェクトおよび「製品」であろうとしますが、Pyrologはユーザーを獲得することなく、私も小さなデモ、いくつかの研究プロトタイプ、ベンチマーク以外では使用しませんでした。Pyrologから非常に興味深い研究が生まれましたが、その上に実際のアプリケーションがいくつか実行されていれば、改善のためのより具体的な目標が得られたと思います。
実装面では、PyrologはPyPyの一部の問題を継承しました。PyPyでは、最初の数年間はピークパフォーマンスに非常に強く焦点を当てていたため、パフォーマンスの断崖が生じました。Pyrologも、インタプリタの継続的な割り当てのため、それらをさらに強く持っていました。
Pyrolog、様々なProlog JITプロトタイプ、そしてPyPy/RPythonメタJITの間には、非常に興味深い相互作用が生じました。Pyrologは、RPython JITにかなり異なる実行モデルをサポートすることを強制し、オブジェクト指向の命令型言語だけでなく、他の言語にも適用可能になりました。
Pyrologの具体的なユースケースはまだありませんので、現時点ではあまり取り組む可能性は低いですが、このプロジェクトでの私の開発は常に断続的だったので、将来いつかは戻ってくるでしょう。
貢献者、他の共同研究者、そして私にインスピレーションと励ましを与えてくれた多くのProlog研究者に感謝して締めくくりたいと思います。
参考文献¶
[[TB1990]]
P. Tarau, M. Boyer. Elementary logic programs. PLILP 1990, LNCS 456, pp. 159–173. DOI.
Paul Tarau. BinProlog: a continuation passing style Prolog engine. PLILP 1992, LNCS 631, pp. 479–480. Poster.
[[SS1994]]
Leon S. Sterling, Ehud Y. Shapiro. The Art of Prolog: Advanced Programming Techniques. 2nd edition, MIT Press, 1994. Publisher page.
Thomas Lindgren. A Continuation-Passing Style for Prolog. International Logic Programming Symposium, 1994, pp. 603–617.
Peter Van Roy. 1983–1993: The Wonder Years of Sequential Prolog Implementation. Journal of Logic Programming 19–20, 1994, pp. 385–441. DOI; author-hosted technical report PDF (DEC Paris Research Laboratory report 36, December 1993).
Ulrich Neumerkel. Continuation Prolog: A new intermediary language for WAM and BinWAM code generation. Post-ILPS 1995 Workshop on Implementation of Logic Programming Languages, 1995. PDF.
[[CM2003]]
William F. Clocksin, Christopher S. Mellish. Programming in Prolog: Using the ISO Standard. 5th edition, Springer, 2003. DOI.
[[BD2004]]
Dariusz Biernacki, Olivier Danvy. From Interpreter to Logic Engine by Defunctionalization. LOPSTR 2003, revised selected papers, published 2004, pp. 143–159. DOI, PDF.
CF Bolz, Armin Rigo. Support for massive parallelism, optimisation results, practical usages and approaches for translation aspects. PyPy Consortium, EU deliverable D07.1, 28 February 2007. Listed by PyPy as Massive Parallelism and Translation Aspects. Official report index; report PDF.
CF Bolz. A Prolog Interpreter in Python. Bachelor thesis, Heinrich Heine University Düsseldorf, 2007. PDF.
CF Bolz, Michael Leuschel, Armin Rigo. Towards Just-In-Time Partial Evaluation of Prolog. LOPSTR 2009, revised selected papers, LNCS 6037, 2010, pp. 158–172. DOI; author manuscript.
CF Bolz, Michael Leuschel, David Schneider. Towards a Jitting VM for Prolog Execution. PPDP 2010, pp. 99–108. DOI; author manuscript.
Hiroshige Hayashizaki, Peng Wu, Hiroshi Inoue, Mauricio J. Serrano, Toshio Nakatani. Improving the Performance of Trace-based Systems by False Loop Filtering. ASPLOS XVI, 2011, pp. 405–418. DOI; IBM Research publication page.
Edd Barrett, CF Bolz, Laurence Tratt. Unipycation: A Case Study in Cross-Language Tracing. VMIL 2013, pp. 31–40. DOI; author manuscript.
Spenser Bauman, CF Bolz, Robert Hirschfeld, Vasily Kirilichev, Tobias Pape, Jeremy G. Siek, Sam Tobin-Hochstadt. Pycket: A Tracing JIT for a Functional Language. ICFP 2015, pp. 22–34. DOI; author manuscript.
Tobias Pape, CF Bolz, Robert Hirschfeld. Adaptive Just-in-time Value Class Optimization: Transparent Data Structure Inlining for Fast Execution. SAC 2015. DOI; PDF.
Tobias Pape, CF Bolz, Robert Hirschfeld. Adaptive just-in-time value class optimization for lowering memory consumption and improving execution time performance. Science of Computer Programming 140, 2017, pp. 17–29. Published online in 2016. DOI; PDF.
Marcial Gaißert, CF Bolz-Tereick, Jonathan Immanuel Brachthäuser. Tracing Just-in-Time Compilation for Effects and Handlers. Proceedings of the ACM on Programming Languages 9 (OOPSLA2), Article 307, October 2025. DOI; author publication page; technical report.