
2026/11/12 23:15
ピロログ二十年史
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
Pyrolog は、2006 年に Uni Düsseldorf の PyPy EU 研究プロジェクト内で誕生した、復活させた RPython ベースの論理プログラミング言語です。当初は、例外ベースのバックトラッキングとヒープ保存された成功継続を備えたオブジェクト指向型 RPython を用いた実験的な実装として開始されました。その後、失敗側の継続をリファイ(具現化)する改修を行い、JIT 対応のための平坦なホストスタックを実現しましたが、予期せぬバックトラッキングの際に極めてパフォーマンスの崖が生じるという課題が発生しました。主要なマイルストーンには以下があります:
- 「pyjitpl」として RPython に移植された追跡ベースのプロログ JIT プロトタイプ(2008/2009 年),これが PyPy のメタ-JIT の基礎となりました。
- LOPSTR 2009("Towards Just-In-Time Partial Evaluation of Prolog")および PPDP 2010("Towards a Jitting VM for Prolog Execution")での発表。
- 学生による追加機能の導入(2011/2012 年),これによりモジュール、DCG(辞書生成文法)、属性付き変数、freeze、when が実装されました。
- David Schneider の ARM JIT バックエンド(2011 年 1 月)および「Unipycation」プロジェクト(2013 年)における早期テストケースとしての活用,これにより Python と Prolog 間の異種言語追跡を可能にしました。
- Pycket(2013 年)への影響,Pycket は RPython の CEK マachine を通じて小さな継続オブジェクトと平坦なホストスタックを採用しています。
- Effekt 関連言語の RPython 実装の開発(2022–2024 年)。
商業利用は現時点では行われていませんが、Pyrolog は例外ベースの選択ポイント、継続管理、平坦なホストスタック、異種言語追跡など高度なコンパイラ技術のテストベッドとして依然意義を有しています。バグ修正および利便性の向上が行われ、2026 年秋に新しい GitHub リポジトリに統合される予定です。
本文
Pyrolog プロジェクト回顧:20 年の軌跡と RPython との関わり
Pyrolog は、RPython ベースのプロログ実装プロジェクトです。2006 年に最初のコミットを PyPy リポジトリへマージし、現在で約 20 年が経過しています。本記事では、開発の背景からアーキテクチャの進化、JIT 技術への寄与、そしてプロジェクトの結論までを時系列順に整理します。
目次
- 背景 (Context)
- 2006/2007 初年度
- 2008/2009 PyPy 側における JIT 開発
- 2009-2010 新しい Pyrolog アーキテクチャ:より多くの継続
- 2011/2012 プロログサポートの拡大
- 2012/2013 コンプレストレム(圧縮された項)
- 2013 ユニパイクエーション (Unipycation)
- 2013 Pycket
- 2022-2024 Effekt の RPython 実装
- 2026 ギット変換 (Git Conversion)
- 結論 (Conclusion)
- 参考文献 (Bibliography)
背景 (Context)
EU プロジェクトの一環として、私たちは制約プログラミングの実装や統一機構 (unification)および制約解決機能の追加を目標としました。
- 学習プロセス: 『Programming Prolog』[CM2003] や『The Art of Prolog』[SS1994] などを研究し、分野に入門しました。
- スプリント参加 (2006 年): Logilab と共催し、ベルギー・ユーCLouvain で開催されました。Peter Van Roy 氏や Gecode の研究者らが参加しました。
- モチベーション: Logilab メンバーは『Java Programming for Scientists and Engineers』に感銘を受け、Van Roy 氏の Prolog 実装サーベイ論文を精読しました。
- 学士課程と課題 (2006 年): デュッセルドルフ大学での学士課程修了前に、Michael Leuschel 教授の講義に参加し、**RPython を用いたプロログインタプリタ(後の Pyrolog)**の開発を始めました。
- 注: 初期コミットの多くは Subversion から Mercurial への移行時やアーカイブ問題で失われています。
2006/2007 初年度
Pyrolog の第一形態は、オブジェクト指向の RPython コードとグローバルな配列による変数管理を用いたシンプルな実装でした。
アーキテクチャとパフォーマンス
- 継続 (Continuation) ベース:
- 成功継続 (
) はヒープ上に格納され、連続的に割り当てられました。success continuations - BinProlog ([TB1990]) や他の CP-style プロログ論文を基盤にしました。
- 成功継続 (
- スタックレス変換:
- C スタック溢れを防ぐため、ホストスタックを展開し情報をヒープ上に格納する手法を用いました。
- これによりテール再帰最適化が可能になりましたが、実用的ではありませんでした。
- バイナリサイズが 2 倍になり、速度も低下しました。
- JIT 実験:
- 第一世代の RPython JIT を使用した実験を行いました。Python プログラムへの効果はありましたが、Pyrolog 自体への改善は限定的でした。
- パフォーマンス結果:
- SWI や SICStus との比較では、SICStus よりも桁違いに遅いケースが頻発しました([Bolz2007])。
機能実装
- Tic-Tac-Toe ケーススタディ: Python で GUI/ロジックを実装し、Prolog でゲームロジックを記述するアプローチを可能にしました。
- 変数表現の変更:
- グローバル配列から、各変数オブジェクトが自身のバインドを保持する方式へ変更しました。
- 開発期間: 例外に基づくバックトラックアーキテクチャは、この変更後もさらに 2 ヵ年間維持されました。
2008/2009 PyPy 側における JIT 開発
EU プロジェクト終了後、新しい RPython メタ-JIT アーキテクチャの開発に注力しました。
- プロトタイプ作成: Armin Rigo 氏らと、Prolog 版の新しい JIT プログラムを 2 つ作成しましたが、満足いくものではありませんでした。
- Trace-based JIT の実験 (2008 年):
- Prolog を用いてパターンマッチングやメタプログラミングを行い、デザインを実験的に検証しました。
- プロトタイプ名は
("pl" は "Prolog" の略)。pyjitpl5
- 成果: この設計は現在の PyPy メタ-JIT コンパイラーの基盤となりました。
- Eurostars プログラムにおける第二回 PyPy EU プロジェクトの研究対象にもなりました。
- LOPSTR 2009 で論文を発表しました [BLR2010]。
2009-2010 新しい Pyrolog アーキテクチャ:より多くの継続
2009 年のクリスマス休暇中、スタックレス変換との互換性欠乏から新しいアーキテクチャへの切り替えを行いました(現在でも使用されているものです)。
アーキテクチャの転換
- 失敗継続の格納:
- 成功継続に加え、失敗継続 (
) もリファイアされた RPython オブジェクトとしてヒープ上に格納するよう変更しました。failure continuations
- 成功継続に加え、失敗継続 (
- トラール (Trail) の活用:
- バックトラック時に元に戻す変数バインドをセグメンテーションされた
オブジェクトに格納し、失敗継続が参照できるようにしました。trail
- バックトラック時に元に戻す変数バインドをセグメンテーションされた
# シンプル化したメインインタプリタループ 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)
デメリットと課題
- GC の負荷: 成功・失敗のすべての継続にヒープデータを連続的に割り当てる必要があるため、RPython の GC に多大な負荷がかかります。
- ホストスタック依存:
- 項の統一 (unification) はまだホストスタックを使用するため、深い項処理時に再帰エラーを引き起こす可能性があります。
JIT サポート ¶
このリファクタリングの主眼は、インタプリタを JIT 向けに最適化することでした。
- トレース可能性:
- 継続による非再帰的な呼び出しにより、Prolog レベルのループが JIT によってトレース可能になりました。
- 継続の連続的割り当ては、RPython JIT の**割り当てる除去 (allocation removal)**により最適化可能です。
- 性能と限界:
- 制御フローが予測可能で美しいループを持つコードに限れば、SICStus よりも顕著に速くなりました。
- しかし、バックトラック検索など制御フローが複雑で予測不能なプログラムでは、継続が JIT の最適化領域を超え、再びヒープ上で割り当てられる必要が生じます。
- その結果、Pyrolog は極めて**急峻なパフォーマンスの崖 (cliffs)**を持っていました。
学術的な影響と交流
- 論文発表: PPDP 2010 で論文を発表しました [BLS2010](Michael Leuschel 氏らとの共著)。
- 研究者との交流:
- BinProlog を考案した Paul Tarau 氏や、Olivier Danvy 氏らに会いました。
- これらの会話から意欲を失っていた時期にも励みを得ました。
- 有循環項の統一:
- バスでの対話を通じて、有循環項(有理木)の統一実装方法(ティエリー・マルティネス氏のトリック?)に触れ、サポートを追加しました。
2011/2012 プロログサポートの拡大
この時期、複数の学生を指導し、Pyrolog の機能拡充を行いました。
- 追加された機能:
- プロログモジュール、DCG(定義的な文法)、属性変数、freeze、when サポートなどを追加しました。
- これらは基本的な実行モデルを変更せずに実装されました。
- エラーメッセージ改善: 例外でのバックトレース表示など、ユーザビリティを向上させました。
- ARM JIT バックエンドテスト:
- David Schneider 氏の ARM JIT を早期にテストするケーススタディとして役立ちました。
- 博士論文:
- Pyrolog の成功からRPython メタ-JIT が幅広い言語に適用可能であることを示唆しました [Bolz2012]。
- メータセージング JIT と古典的部分評価アプローチの比較も議論しました。
移動と研究環境の変化
- 2013 年より、King's College London で Laurence Tratt 氏と共に研究を開始し、デュッセルドルフを離れました。
- この後、Pyrolog の大きな進展はなく、アイデアは他のプロジェクトへと引き継がれていきます。
2012/2013 コンプレストレム(圧縮された項)
Pyrolog ではマージされなかった実験の一つですが、コンプレストレムのアイデアは後続に影響しました。
- 概要:
- 関連リスト
のようなパターンが繰り返される場合、各エントリに対して個別のオブジェクトを割り当てるのではなく、「形状 (shape)」を共有し、データを平坦なストレージに格納する方式です。[A/B|C]
- 関連リスト
- 課題:
- 変数のバインドが動的に後からこれらのパターンを作成するため、静的な圧縮戦略には不向きでした。
- 関連プロジェクト:
- これらのアイデアは関数型言語
(後の Theseus)でも実装され、トビアス・パペ氏らによってさらに発展しました [PBH2015, PBH2017]。lamb - 後にPycketで実際に試みられることになります。
- これらのアイデアは関数型言語
2013 ユニパイクエーション (Unipycation)
ロンドンでの研究プロジェクト「言語構成 (language composition)」の一環として、異なる言語を統合する RPython 実装を行いました。
- 目標: PyPy と別の言語を組み合わせた統一された実行環境の実現。
- 対象: PyPy と Pyrolog の組み合わせ [BBT2013]。
- Python ↔ Prolog の相互呼び出しを可能にしました。
- RPython メタ-JIT を跨いで最適化(クロス言語インライン化)を行いました。
- 結果:
- 魅力的なユースケースを見出すことはできず、プロジェクトは終了しました。
2013 Pycket
Racket の RPython 実装である Pycketを開始し、Pyrolog の影響を間接的に受けています。
- 参加者: Sam Tobin-Hochstadt 氏、Jeremy Siek 氏ら(後年に Tobias Pape 氏らも加入)。
- アーキテクチャ:
- CEK マシンを RPython で実装し、平坦なホストスタックを採用しました。
などの実装を比較的手軽にできるようにしました [Pycket2015]。call/cc
- 導入された新技術:
- 偽ループフィルタリング (false loop filtering):
- 関数呼び出しの文脈を考慮し、JIT が「偽ループ」を検知するのを防ぎます(IBM Research 由来)。
- 継続オブジェクトの小型化:
- ヒープへの割り当て負荷を減らすため、Pyrolog でも持ち込まれました。
- 偽ループフィルタリング (false loop filtering):
2022-2024 Effekt の RPython 実装
2016 年 King's College を退官後、2017 年にデュッセルドルフ大学に戻り、2022 年から新しい取り組みを開始しました。
- プロジェクト: Effekt および関連言語の RPython 実装 [GBB2025]。
- 特徴:
- 効果ハンドラ (effect handlers) を持つための JIT 実装。
- リファイアされたスタックフレーム/継続を持つアプローチを採用し、その上に効果ハンドラを追加しています。
2026 ギット変換 (Git Conversion)
今年(2026 年)、Pyrolog は設立から20 周年を迎えます。
- 対応策:
- GitHub リポジトリへの完全移行(Mercurial の履歴マージ)。
- バグ修正と利便性機能の追加を行いました。
結論 (Conclusion)
Pyrolog は常に研究志向のプロジェクトであり、実用的な製品を目指したものではありませんでした。
- 成果:
- PyPy や RPython メタ-JIT に対して、異なる実行モデルやオブジェクト指向命令型言語以外の適用可能性を示す重要な役割を果たしました。
- 多くの興味深い研究成果を生み出し、後のプロジェクト(Pycket など)に影響を与えました。
- 課題:
- 実装上の制約プログラミング分野において、PyPy が直面した「パフォーマンスの崖」をさらに深刻化させる要因となりました。
- ユーザーベースを持たないまま、具体的なユースケースを見出すことができませんでした。
- 将来性:
- 現在は具体的ユースケースがないため活動は低調ですが、プロジェクトが「bursty(突発的・短命的)」に進んできた歴史から、将来的に再び取り組む必要がある可能性を残しています。
参考文献 (Bibliography)
- [TB1990] P. Tarau, M. Boyer. Elementary logic programs. PLILP 1990.
- [Tarau1992] Paul Tarau. BinProlog: a continuation passing style Prolog engine. PLILP 1992.
- [SS1994] Leon S. Sterling, Ehud Y. Shapiro. The Art of Prolog: Advanced Programming Techniques. MIT Press, 1994.
- [Lindgren1994] Thomas Lindgren. A Continuation-Passing Style for Prolog. ILPS 1994.
- [VanRoy1994] Peter Van Roy. The Wonder Years of Sequential Prolog Implementation. JLP 1994.
- [Neumerkel1995] Ulrich Neumerkel. Continuation Prolog: A new intermediary language.... Post-ILPS 1995.
- [CM2003] William F. Clocksin, Christopher S. Mellish. Programming in Prolog. Springer, 2003.
- [BD2004] Dariusz Biernacki, Olivier Danvy. From Interpreter to Logic Engine by Defunctionalization. LOPSTR 2003.
- [BR2007D071] CF Bolz, Armin Rigo. Support for massive parallelism.... PyPy Consortium Deliverable D07.1, 2007.
- [Bolz2007] (1,2) CF Bolz. A Prolog Interpreter in Python. Bachelor thesis, Uni Düsseldorf, 2007.
- [BLR2010] CF Bolz, Michael Leuschel, Armin Rigo. Towards Just-In-Time Partial Evaluation of Prolog. LOPSTR 2009.
- [BLS2010] (1,2) CF Bolz, Michael Leuschel, David Schneider. Towards a Jitting VM for Prolog Execution. PPDP 2010.
- [HWISN2011] Hayashizaki et al. Improving the Performance of Trace-based Systems by False Loop Filtering. ASPLOS XVI, 2011.
- [BBT2013] Edd Barrett, CF Bolz, Laurence Tratt. Unipycation: A Case Study in Cross-Language Tracing. VMIL 2013.
- [Pycket2015] Bauman et al. Pycket: A Tracing JIT for a Functional Language. ICFP 2015.
- [PBH2015] Tobias Pape, CF Bolz, Robert Hirschfeld. Adaptive Just-in-time Value Class Optimization.... SAC 2015.
- [PBH2017] Tobias Pape, CF Bolz, Robert Hirschfeld. Adaptive just-in-time value class optimization.... Science of Computer Programming, 2016/2017.
- [GBB2025] Marcial Gaißert, CF Bolz-Tereick, Jonathan Immanuel Brachthäuser. Tracing Just-in-Time Compilation for Effects and Handlers. OOPSLA 2025.