2

私はASTを変換しており、単純なパターンマッチング以上のものが必要です。したがって、統合アルゴリズムが必要です。

これは.NETプロジェクト用であり、.NET PROLOG実装と相互運用できることはわかっていますが、統合アルゴリズムを埋め込むだけで済みます。したがって、PROLOGはやり過ぎです。

F＃で記述された「Martelli、Montanari：An Efficient Unification Algorithm」を入手できれば完璧ですが、HASKELLを含むすべての関数型言語を採用し、F＃に翻訳します。

4

2 に答える 2

2

一般に、SOについて質問するときは、試みを共有することをお勧めします。人々は一般的にあなたにあなたの問題の完全な解決策を与えることはありません-あなたが特定の質問をしたり問題に取り組む方法を示唆したときに答えるだけです。

それで、私は一般的なアプローチについていくつかのヒントを共有しますが、それは完全な解決策ではありません。まず、ASTを何らかの方法で表現する必要があります。F＃では、識別された共用体を使用してこれを行うことができます。以下は、変数、値、および関数アプリケーションをサポートします。

type Expr =
  | Function of string * Expr list
  | Variable of string
  | Value of int

統合は、型を統合する式のリストを取得し、変数への(Expr * Expr) list割り当てを返す（Expr変数名への式の割り当てstring）関数です。

let rec unify exprs =
  match exprs with 
  // Unify two variables - if they are equal, we continue unifying 
  // the rest of the constraints, otherwise the algorithm fails
  | (Variable s1, Variable s2)::remaining ->
      if s1 = s2 then unify remaining
      else failwith "cannot unify variables"
  // Unify variable with some other expression - unify the remaining
  // constraints and add new assignment to the result
  | (Variable s, expr)::remaining 
  | (expr, Variable s)::remaining  ->
      let rest = unify remaining
      // (s, expr) is a tuple meaning that we assign 'expr' to variable 's'
      (s, expr)::rest

  // TODO: Handle remaining cases here!
  | _ -> failwith "cannot unify..."

追加する必要があるケースがいくつかあります。最も重要なことは、と統合FunctionするFunctionということは、関数名が同じであることを確認し（そうでない場合は失敗する）、すべての引数式を新しい制約としてremainingリストに追加する必要があることを意味します...

于 2012-03-01T22:50:48.450 に答える
2

Baader＆Snyderの最後の構文統合では、union-findを使用して、2つの構造のノードを同値類に分割します。次に、それらのクラスをウォークして、三角形の置換を構築します。

union-findを使用しているため、純粋関数型の答えを探している場合は運が悪いです。機能的なunion-findの書き方を誰も知らない。しかし、 ConchonとFilliâtre（OCamlで書かれている）のおかげで、少なくとも明らかに機能している永続的なユニオンファインドを書く方法を知っています。

于 2012-03-02T16:51:52.050 に答える