Сравнение синтаксических деревьев по модулю альфа-преобразования - PullRequest
Новая
       56

Сравнение синтаксических деревьев по модулю альфа-преобразования

4 голосов
/ 27 февраля 2012

Я работаю над компилятором / проверкой корректуры, и мне было интересно, есть ли у меня такое синтаксическое дерево, например: 

data Expr
    = Lambdas (Set String) Expr
    | Var String
    | ...

, если есть способ проверить альфа-эквивалентность (эквивалентность по модулю переименования) Expr с.Это Expr, однако, отличается от лямбда-исчисления тем, что множество переменных в лямбда-выражениях является коммутативным, т. Е. Порядок параметров не учитывает проверку.

(Для простоты, однако, Lambda ["x","y"] ... отличается от Lambda ["x"] (Lambda ["y"] ...), и в этом случае порядок имеет значение).

Другими словами, как два Exprs, как можетодин эффективно найти переименование от одного к другому?Этот вид комбинаторной проблемы пахнет NP-полной.

Ответы [ 2 ]

6 голосов
/ 27 февраля 2012

Коммутативность параметров намекает на экспоненциальное сравнение, правда.

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

Что я предлагаю сделать, так это то, что для каждого списка параметров посетите поддерево в (по порядку, по порядку, не имеет значения какЕсли вы последовательны), и сортируйте параметр по индексу порядка, в котором посещение впервые встречает использование параметра.Так что, если у вас есть 

  lambda(a,b):  .... b .....  a  ... b ....

, вы бы отсортировали список параметров следующим образом: 

  lambda(b,a)

, потому что сначала вы встретите b, затем секунду, а дополнительное столкновение b неиметь значение.Сравните деревья со списком нормализованных параметров.

Жизнь становится более запутанной, если вы настаиваете, что операторы в лямбда-выражении могут быть коммутативными.Я думаю, что вы все еще можете нормализовать его.

4 голосов
/ 27 февраля 2012

Мы можем обратиться к Даану Лейджену HMF за несколькими идеями. (Он имеет дело со связующими для «форалов», которые также кажутся коммутативными.

В частности, он связывает переменные в порядке появления в теле.

Тогда сравнение терминов включает в себя сколемизацию и сравнение результатов.

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

data Bound t a = Bound {-# UNPACK #-} !Int t | Unbound a

instance Functor (Bound t) where ...
instance Bifunctor Bound where ...

data Expr a
  = Lambdas {-# UNPACK #-} !Int (Expr (Bound () a))
  | Var a

Так что теперь вхождения Bound под лямбдой - это переменные, связанные непосредственно лямбда, вместе с любой информацией о типе, которую вы хотите поместить в событие, здесь я только что использовал ().

Теперь закрытые термины полиморфны в «а» и, если вы сортируете элементы лямбды по их сайту использования (и можете гарантировать, что вы всегда канонизируете лямбду, удаляя неиспользуемые термины), альфа-эквивалентные термины сравниваются просто с (== ), и если вам нужны открытые термины, вы можете работать с Expr String или другим представлением.

Более анальная сохраняющая версия подписи для Expr и Bound будет использовать экзистенциальный тип и естественный уровень типа для определения количества связанных переменных и использовать Fin в конструкторе Bound, но так как вы уже должны поддерживать инвариант, что вы связываете не больше переменных, чем #, встречающееся в лямбда-выражении, и что информация о типах совпадает по всем Var (Bound n _) с одним и тем же n, это не слишком большая нагрузка для поддержки другой.

Обновление: вы можете использовать мой пакет bound, чтобы сделать улучшенную версию полностью автономным способом!

...