У меня есть интересный вопрос, но я точно не знаю, как это сделать ...Как найти оптимальный порядок обработки?
Рассмотрите исчисление лямбда. Для данного лямбда-выражения существует несколько возможных порядков сокращения. Но некоторые из них не прекращаются, а другие делают.
В исчислении лямбда получается, что существует один конкретный порядок восстановления, который гарантирует, что всегда заканчивается неприводимым решением, если оно действительно существует. Это называется Нормальный порядок.
Я написал простой логический решатель. Но проблема в том, что порядок, в котором он обрабатывает ограничения, по-видимому, оказывает огромное влияние на то, найдет ли он какие-либо решения или нет. В принципе, мне интересно, существует ли что-то вроде обычного порядка для моего логического языка программирования. (Или кастрированный баран это невозможно просто машина детерминировано решить эту проблему.)
Так вот что я после. Предположительно, ответ критически зависит от того, что такое «простой логический решатель». Поэтому я постараюсь, чтобы кратко описать это.
Моя программа тесно на основе системы комбинаторов в главе 9 удовольствия от программирования (Джереми Gibbons & Oege де Moor). Язык имеет следующую структуру:
вход решателя является одной предикат. Предикаты могут включать переменные. Выход от решателя равен нулю или более решения. Решение представляет собой набор переменных присваиваний, которые делают предикат истинным.
Переменные, содержащиеся выражения. Выражение представляет собой целое число, имя переменной или кортеж подвыражений.
Существует предикат равенства, который сравнивает выражения (не предикаты) для равенства. Выполняется, если подстановка каждой (связанной) переменной с ее значением делает эти два выражения одинаковыми. (В частности, каждая переменная равна себе, связана или нет). Этот предикат решается с помощью унификации.
Существуют также операторы для AND и OR, которые работают очевидным образом. Оператора NOT нет.
Существует оператор «существует», который по существу создает локальные переменные.
Объект для определения именованные предикаты включает рекурсивный цикл.
Один из «интересного» о логическом программировании является то, что когда-то вы пишете с именем предиката, он обычно работает fowards и назад (а иногда даже боком). Канонический пример: предикат для объединения двух списков также может использоваться для разбиения списка на все возможные пары.
Но иногда выполнение предиката назад приводит к бесконечному поиску, если вы не измените порядок терминов. (Например, замените LHS и RHS для AND или OR). Мне интересно, есть ли какой-то автоматизированный способ определения наилучшего порядка запуска предикатов, чтобы обеспечить быстрое завершение во всех случаях, когда набор решений конечно.
Любые предложения?
Это, вероятно, поможет, если вы разместите несколько примеров программ на вашем языке, и показать, как различные стратегии сокращения приводят к разные результаты. –
@ н.м. Хорошая идея. Я попытаюсь придумать минимальный пример ... – MathematicalOrchid
См. Также [Ассиметрия пресбергера] (http://en.wikipedia.org/wiki/Presburger_arithmetic) в случае, если вы этого не видели раньше - действительность разрешима , и это позволяет и, или, не, forall и индукцию (хотя, возможно, индукция не так сильна, как рекурсия, которую вы описываете). –