Атрибутивные переменные: библиотечные интерфейсы / реализации / переносимость

Когда я недавно просматривал некоторые вопросы, связанные спрологом , я наткнулся наэтот ответ @mat на вопрос, Как представить направленный циклический граф в прологе с прямым доступом к соседним вертикалям .

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

Во-первых, хорошая новость: мое первое использование атрибутивных переменных сработало так, как я хотел.

затем, не очень хорошие новости: Когда я опубликовал ответ, я понял, что в прологе есть несколько API и реализаций для атрибутивных переменных.

Я чувствую, что я здесь выше головы... В частности, я хочу знать следующее:

  • какие API широко используются? До сих пор я нашел два: SICStus и Сви.
  • какие функции предлагают различные реализации приписываемых переменных? Те же самые? Или одно подчиняет себе другое?
  • существуют ли различия в семантике?
  • Как насчет фактической реализации? Являются ли некоторые из них более эффективными, чем другие?
  • может быть (или является) использование атрибутивных переменных проблемой переносимости?

Здесь много вопросительных знаков... Пожалуйста, поделитесь своим опытом / позицией? Заранее вам спасибо!

Править 2015-04-22

Вот фрагмент кода ответа , упомянутого выше: 

init_att_var(X,Z) :-
    put_attr(Z,value,X).

get_att_value(Var,Value) :-
    get_attr(Var,value,Value).

Пока я" только " использую put_attr/3 и еще get_attr/3, но-согласно документации Sicstus Prolog по атрибутивным переменным - - - sicstus предлагает put_attr/2 и еще get_attr/2.

Так что даже Этот очень мелкий случай использования требуется некоторая эмуляция слоя (так или иначе).

4 43
prolog

4 ответа:

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

  • можно ли принимать во внимание атрибуты при рассуждении о одновременных объединениях, как в [X,Y] = [0,1]?

Это возможно, например, в прологе SICStus, потому что такие привязки отменены перед вызовом verify_attributes/3. В интерфейсе, предоставляемом hProlog (attr_unify_hook/2, называемом после объединения и со всеми привязками уже на месте), трудно учитывать (предыдущие) атрибуты Y при рассуждении об объединении X в attr_unify_hook/2, потому что Y больше не является переменной в этот момент! Этого может быть достаточно для решателей, которые могут принимать решения, основываясь только на базовых значениях, но это серьезное ограничение для решателей, которым, как правило, требуются дополнительные данные. хранится в атрибутах, чтобы увидеть, должно ли объединение быть успешным, и которые затем уже не так легко доступны. Один очевидный пример: булева унификация с диаграммами решений.

По состоянию на 2016 год, verify-attributes ветвь SWI-Prolog также поддерживает verify_attributes/3, благодаря большой работе по реализации Douglas Miles. Ветвь готова к тестированию и предназначена для слияния в master, как только она будет работать правильно и эффективно. Для совместимости с hprolog, ветвь также поддерживает attr_unify_hook/2: она делает это путем переписывания таких определений в более общий verify_attributes/3 во время компиляции.

С точки зрения производительности ясно, что у verify_attributes/3 может быть обратная сторона, потому что одновременное использование нескольких переменных может позволить вам быстрее увидеть (в attr_unify_hook/2), что объединение не может быть успешным. Тем не менее, я с удовольствием и в любое время обменяю это, как правило, незначительное преимущество на повышенную надежность, простоту использования и повышенную функциональность, которые более общий интерфейс дает вам, и который в любом случае уже является стандартным поведением в Sicstus Prolog, который на вершине своей общности также является одной из самых быстрых систем пролога вокруг.

Sicstus Prolog также имеет важный предикат под названием project_attributes/2: он используется на верхнем уровне для проецирования ограничений на переменные запроса. SWI-Prolog также поддерживает это в последних версиях.

Существует также одно огромное преимущество интерфейса SWI: остаточные цели, которые attribute_goals//1 и, следовательно, copy_term/3 дайте вам всегда список . Это помогает пользователям избежать дефолтности в их коде и поощряет более декларативный интерфейс, поскольку список чистых целей ограничения не может содержать структуры управления.

Интересно, что ни один из интерфейсов не позволяет интерпретировать унификации иначе, чемсинтаксически . Лично я думаю, что есть случаи, когда вы можете интерпретировать унификации иначе, чем синтаксически, однако, также могут быть хорошие аргументы против этого. Другие предикаты интерфейса для приписываемых переменных в основном легко взаимозаменяемы с простыми предикатами оболочки для различных систем.
11

Jekejeke Minlog имеет безгосударственные илитонкие атрибутивные переменные. Ну не совсем, переменная атрибута может иметь ноль, один или несколько крючков, которые могут быть замыканиями, и, следовательно, может нести небольшое состояние.

Но обычно реализация управляет состоянием в другом месте. Для этого назначение Jekejeke Minlog позволяет создавать ссылочные типы из переменных, чтобы их можно было использовать в качестве индексов в таблицах.

Полный потенциал высвобождается, если это сочетается с трейлингом и-или передняя цепь. В качестве примера мы реализовали CLP (FD). Существует также небольшой учебник по решателям.

Примитивными ингредиентами в нашем случае являются:

1) атрибутивные переменные без состояний
2) трейлинг и переменные ключи
3) Очередь Продолжения

Крючки атрибутивных переменных могут иметь эффект привязки вплоть до расширения очереди продолжения, но выполняются только один раз. Цели из очереди продолжения могут быть недетерминированными.

Есть некоторые дополнительные слои перед реализацией приложений, которые в основном являются агрегациями примитивов для временного внесения изменений.

Основными приложениями на данный момент являются open source here и here :

A) Решатель Ограничений Конечной Области
b) ограничения Гербранда
в) подвеска цели

Пока

7

Вы можете найти одну из самых старых и наиболее сложных реализаций атрибутивных переменных в ECLiPSe, где она является частью более широкой инфраструктуры для реализации решателей ограничений.

Основными характеристиками этой конструкции являются:

  • атрибуты должны быть объявлены, и в ответ компилятор поддерживает эффективный доступ
  • синтаксис для атрибутивных переменных, чтобы их можно было читать и записывать
  • более полный набор обработчиков для атрибута операций, так что атрибуты учитываются не только для унификации, но и для других универсальных операций, таких как копирование терминов и тесты подсчета
  • четкое разделение между понятиями переменных атрибутов и условных целей
  • используется в более чем дюжине библиотек ECLiPSe

Эта статья (раздел 4) и документация ECLiPSe содержат более подробную информацию.

6

Дополнительная перспектива библиотек атрибутивных переменных заключается в том, сколько атрибутов может быть определено для каждого модуля. В случае SWI-Prolog/YAP и цитирования документации SWI:

Каждый атрибут связан с модулем, а крюк (attr_unify_hook/2) выполняется в этом модуле.

Это серьезное ограничение для разработчиков библиотек, таких как CLP (FD), поскольку оно вынуждает использовать дополнительные модули с единственной целью иметь несколько атрибутов вместо того, чтобы иметь возможность определите столько атрибутов, сколько требуется в модуле, реализующем их библиотеку. Это ограничение отсутствует в интерфейсе Sicstus Prolog, который предоставляет Директиву attribute/1, позволяющую объявлять произвольное число атрибутов для каждого модуля.

5