Constraint Lingo – это высокоуровневый язык логического программирования для выражения табличных проблем с ограничениями, подобными тем, которые встречаются в логических головоломках. Рафаэль Финкель (Raphael Finkel) разрабатывал его, начиная примерно с 2000 года, как часть работы над Логическим программированием (Logic Programming) с Миреком Трущинским (Mirek Truszczynski ) и Виктором Мареком (Victor Marek).
Небольшой пример
Головоломка на английском языке
Четверо детей, Кэти, Фредерико, Кеалоха и Мустафа, рисовали картины для своего класса в детском саду, каждый из них использовал другой инструмент для рисования. Затем они с гордостью показывали свои фотографии классу в определенном порядке. Определите, какой инструмент использовал каждый ребенок и в каком порядке они представили свою работу, учитывая следующие четыре подсказки.
- Мустафа, показавший свою фотографию четвертым, не использовал маркер.
- Ребенок с помощью карандаша показывал свою работу сразу после работы, нарисованной кистью.
- Кэти не показывала свою картину второй.
- Кеалоха показала свою картину в двух местах после того, как нарисовала ее карандашом.
Перевод на 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. Этот код не представляет производственного качества; он находится в процессе разработки. Мы были бы признательны, если бы вы скачали его и поделились вашими впечатлениями. Пожалуйста, напишите разработчику [email protected] (без подчеркивания).
Документация
Мы написали несколько работ на Constraint Lingo.
Конец формы
Самая последняя в области Программного обеспечения – Practice and Experience, Volume 34, number 15, pages 1481-1504, December 2004.
Добавить комментарий