バックトラックを言語仕様にうまく組み込んだ例

 

1. Prolog系ロジック言語

代表: Prolog, Mercury, Curry など

• 基本アイデア

  • 事実とルールを書く

  • クエリに対して、

    • 左から右

    • 上から下
      の順に試す深さ優先探索が「仕様として」定義されている。

  • 失敗したら自動でバックトラックして別の候補を試す。

• うまい点

  • *「述語を呼び出す」ことと「条件分岐＋ループ＋探索」*が一体化している。

  • ;（選言）や -> ;（if-then-else）など、構文レベルでバックトラックと整合している。

  • cut (!) などで探索空間を制御する手段も仕様に含まれる。

• 弱点（設計上のトレードオフ）

  • 論理式の“見た目”と探索手順が強く結びつくので、

    • 文の並びを変えると意味（実行結果）が変わる

    • 実装依存の挙動を理解してないと予測しづらい

  • つまり「宣言的」と「手続き的」がかなり混ざっている。

---

2. Icon の「ゴール指向評価」

代表: Icon, その後継の Unicon など

個人的に「バックトラックを言語デザインとして一番きれいに統合している例のひとつ」です。

• コアの発想

  • すべての式が「成功」か「失敗」を返し、

    • さらに複数の値を順次生成しうる（generator）。

  • ある式が失敗すると、その直前の式が「別の値を生成しなおす」かを試す。
    それがバックトラック。

• 例のイメージ（かなり擬似コード）

  1. # s の中から "abc" を含む位置を順に返すような感じ every i := find("abc", s) do write(i)

• うまい点

  • 「success / failure / multiple results」という概念を式レベルに落とし込んでいる。

  • 制御構造（if, while, every など）が成功・失敗に一貫して基づいて設計されている。

  • バックトラックが「パターンマッチ専用の機能」ではなく、
    言語全体の評価モデルに統合されている。

---

3. SNOBOL4 のパターンマッチ

代表: SNOBOL4 などの文字列処理言語

• 特徴

  • 文字列パターンが第一級オブジェクトとして扱われる。

  • パターンマッチの過程で、

    • 区間の長さを変えたり

    • 選択肢を切り替えたりする時に
      自動的にバックトラックが行われる。

• うまい点

  • 「パターンマッチ」という限定された領域に
    バックトラックを特化しているので、挙動を理解しやすい。

  • パターン言語自体がかなり表現力があり、
    正規表現よりもずっとリッチな“マッチ DSL”として機能する。

---

4. 正規表現エンジン（言語内DSLだが、設計としては好例）

代表: Perl, Ruby, JavaScript などの バックトラッキング型正規表現

• 多くの言語の正規表現は、

  • |（オルタネーション）

  • *, +, ?（繰り返し）

  • ?=, ?!（先読み）
    などの記法に対し、
    仕様としてバックトラックするマッチングアルゴリズムを想定している。

• うまい点

  • 「バックトラックを隠蔽しつつ、必要なときに制御できる」設計。

  • 量指定子（*? などの最短一致）や否定先読みで、
    パフォーマンスや意味をある程度制御できる。

  • メイン言語の中に、
    バックトラック付きの小さな言語（正規表現）が埋め込まれている形。

• 注意点

  • 複雑なパターンで指数時間に落ちるなど、
    バックトラック特有の性能問題はつきまとう。

---

5. パーサコンビネータ系（Haskell など）

代表: Haskell の Parsec / Megaparsec、OCaml/F# の parser combinator など

• 発想

  • Parser a のような型で「入力から値 a を抜き出す計算」を表現。

  • (<|>) などのコンビネータで
    「まず左のパーサを試し、失敗したら右にバックトラック」
    という挙動をライブラリレベルで抽象化している。

• 仕様上の組み込み度合い

  • これは「言語仕様」というより「ライブラリ＋型システム」ですが、

    • do 記法（モナド）と

    • バックトラック付きパーサ
      がかなり自然に合成されるので、
      言語の一部のような書き心地になります。

• うまい点

  • 型で「どの程度バックトラックするのか」「どの情報を残すか」を制御できる。

  • 必要に応じて

    • LL(1) 的にバックトラックを抑制したり

    • エラーメッセージをリッチにしたり
      といった調整がしやすい。

---

6. 述語・関係プログラミング（miniKanren など）

代表: miniKanren（Scheme/CL系の関係プログラミング言語）

• 特徴

  • 「関数」ではなく「関係」を書いて、
    その関係を満たす値をバックトラックで探す。

  • conde（条件の選択）、fresh（新しい論理変数の導入）といった
    小さなプリミティブに、探索とバックトラックの意味がきれいに落ちている。

• うまい点

  • とても小さなコア仕様（数十行レベル）で
    完全なロジックプログラミングの探索とバックトラックを実現している。

  • 言語仕様としても「極小コア＋マクロ」で説明できるのが美しい。

---

ざっくりまとめ

「バックトラックを言語仕様にうまく組み込んだ」例として挙げやすいのは：

1. Prolog 系

   • ロジックプログラミングそのものとして統合。

   • ただし宣言的と手続き的が密着しがち。

2. Icon（＋SNOBOL4 パターン）

   • 成功／失敗と多値生成を評価規則の中心に据えた、とてもきれいな設計。

3. バックトラッキング正規表現

   • 言語内 DSL として、パターンマッチに特化した成功例。

4. パーサコンビネータ / miniKanren

   • 言語＋ライブラリ＋型（またはマクロ）で、
     少ないプリミティブからバックトラックの計算モデルを構成している。