Оригинал статьи.

Constraint Lingo – это высокоуровневый язык логического программирования для выражения табличных проблем с ограничениями, подобными тем, которые встречаются в логических головоломках. Рафаэль Финкель (Raphael Finkel) разрабатывал его, начиная примерно с 2000 года, как часть работы над Логическим программированием (Logic Programming) с Миреком Трущинским (Mirek Truszczynski ) и Виктором Мареком (Victor Marek).

Небольшой пример

Головоломка на английском языке

Четверо детей, Кэти, Фредерико, Кеалоха и Мустафа, рисовали картины для своего класса в детском саду, каждый из них использовал другой инструмент для рисования. Затем они с гордостью показывали свои фотографии классу в определенном порядке. Определите, какой инструмент использовал каждый ребенок и в каком порядке они представили свою работу, учитывая следующие четыре подсказки.

  1. Мустафа, показавший свою фотографию четвертым, не использовал маркер.
  2. Ребенок с помощью карандаша показывал свою работу сразу после работы, нарисованной кистью.
  3. Кэти не показывала свою картину второй.
  4. Кеалоха показала свою картину в двух местах после того, как нарисовала ее карандашом.

Перевод на Constraint Lingo

CLASS child: kathy frederico kealoha mustafa

CLASS place: 1 .. 4

CLASS instrument: crayon pencil marker paintbrush

 

# clue 1

CONFLICT mustafa marker

REQUIRED mustafa 4

# clue 2

OFFSET 1 place: paintbrush pencil

# clue 3

CONFLICT kathy 2

# clue 4

OFFSET 2 place: crayon kealoha

Решение вычислено с помощью Constraint Lingo

child      instrument place      

       ========== ========== ==========

       frederico  marker 2          

       kathy   crayon 1          

       kealoha   paintbrush 3          

       mustafa   pencil 4    

Как это работает

Компилятор преобразует программу на Constraint Lingo в низкоуровневый код, который затем выполняется логическим ядром. Постпроцессор форматирует результат в таблицу.

Компилятор написан на языке Perl. Он включает программу Constraint-Lingo в качестве комментариев в низкоуровневом коде. У нас есть много версий компилятора, поскольку мы экспериментируем с различными стратегиями (стандарт, лучший класс, номер строки), различными логическими движками и различными оптимизациями.

Мы поддерживаем следующие логические движки.

  • Smodels
  • ECLiPSe
  • DLV
  • aspps

Пост-процессор написан на Perl. Он специфичен для конкретного компилятора, который используется в предыдущих шагах.

Насколько это быстро?

Компилятор и постпроцессоры настолько быстры, что мы никогда не беспокоимся об их вкладе в общее время. Почти все 90-е или другие головоломки, которые мы запрограммировали, решаются менее чем за секунду всеми версиями компилятора и связанных с ними логическими движками. Некоторые из них занимают более 10 секунд с некоторыми компиляторами.

Насколько общий Constraint Lingo?

Мы можем кодировать несколько графовых задач в Constraint Lingo, в частности 3-раскраску, Гамильтоновы пути/схемы и независимые множества. Препроцессор преобразует графики в эквивалентные программы Constraint-Lingo.

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

Он доступен для скачивания

Вы можете скачать копию нашей текущей работы по ссылке ftp://ftp.cs.uky.edu/cs/software/cl.tar.gz. Этот код не представляет производственного качества; он находится в процессе разработки. Мы были бы признательны, если бы вы скачали его и поделились вашими впечатлениями. Пожалуйста, напишите разработчику raphael_@cs.uky.edu (без подчеркивания).

Документация

Мы написали несколько работ на Constraint Lingo.

Конец формы

Самая последняя в области Программного обеспечения – Practice and Experience, Volume 34, number 15, pages 1481-1504, December 2004.