Что такое алгоритм объединения? - PullRequest
Новая
       17

Что такое алгоритм объединения?

6 голосов
/ 18 декабря 2010

Ну, я знаю, это может звучать немного странно, но да, мой вопрос: «Что такое алгоритм объединения». Ну, я пытаюсь разработать приложение на F #, чтобы действовать как Пролог. Он должен принимать ряд фактов и обрабатывать их при выполнении запросов.

Мне предложили начать реализацию хорошего алгоритма унификации, но я понятия не имел об этом.

Пожалуйста, обратитесь к этому вопросу, если вы хотите немного глубже понять, что я хочу сделать.

Большое спасибо и счастливого Рождества.

Ответы [ 3 ]

6 голосов
/ 18 декабря 2010

Если у вас есть два выражения с переменными, тогда алгоритм объединения пытается сопоставить два выражения и дает вам присваивание переменных, чтобы сделать два выражения одинаковыми.

Например, если вы представляли выражения в F #: 

type Expr = 
  | Var of string              // Represents a variable
  | Call of string * Expr list // Call named function with arguments

И имели два таких выражения: 

Call("foo", [ Var("x"),                 Call("bar", []) ])
Call("foo", [ Call("woo", [ Var("z") ], Call("bar", []) ])

Тогда алгоритм объединения должен дать вам назначение: 

"x" -> Call("woo", [ Var("z") ]

Это означает, что если вы замените все вхождения переменной "x" в двух выражениях, результаты этих двух замен будут одним и тем же выражением.Если у вас были выражения, вызывающие различные функции (например, Call("foo", ...) и Call("bar", ...)), тогда алгоритм скажет вам, что они не являются единообразными.

В WikiPedia также есть некоторые объяснения , ипри поиске в Интернете вы наверняка найдете полезное описание (и, возможно, даже реализацию на каком-то функциональном языке, похожем на F #).

3 голосов
/ 02 августа 2011

Я нашел работу Баадера и Снайдера наиболее информативной.В частности, они описывают несколько алгоритмов объединения (включая почти линейный алгоритм Мартелли и Монтанари с использованием union-find) и описывают как синтаксическое объединение, так и различные виды семантического объединения.

После того, как вы объединитесь, вы такженужно вернуться.* Киселев / Шань / Фридман LogicT Framework поможет здесь.

2 голосов
/ 18 декабря 2010

Очевидно, что деструктивное объединение будет гораздо более эффективным, чем чисто функциональное, но также и намного менее F-острым. Если вам нужна производительность, возможно, в конечном итоге вы реализуете подмножество WAM:

http://en.wikipedia.org/wiki/Warren_Abstract_Machine

И, вероятно, это может помочь:

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.3203

...