Программирование на языке Пролог

9. Написать программу, которая переписывает выражение исчисления высказываний (см. задачу 4), заменяя все вхождения and, or, implies и not единственной связкой nand. Определение связки nand задается следующим тождеством

(α nand β)⌉≡(α∧β)

10. Один из способов представления целых положительных чисел состоит в том, чтобы представлять их в виде термов Пролога с использованием целого числа 0 и функтора S с одним аргументом. Так, число 0 представляет само себя, 1 представляется как S(0), 2 как S(S(0)) и т. д. (каждое число представляется в виде функтора S примененного к представлению числа, на единицу меньшего, чем данное). Написать определение стандартных арифметических операций: сложение, умножение и вычитание, использующих указанное представление чисел. Например, нужно определить предикат plus который действует следующим образом:

?- plus(s(s(0)),s(s(s(0))),X)

X=s(s(s(s(s(0)))))

(2+3=5). Для вычитания нужно ввести соглашение о том, что делать, когда результат операции не является положительным целым числом. Определите также предикат «меньше чем». Какие аргументы нужно конкретизировать, чтобы ваши определения работали правильно? Что произойдет, если этого не сделать? Как это соотносится со стандартными арифметическими операциями Пролога? Попытайтесь определить более сложные арифметические операции, такие как деление нацело и извлечение квадратного корня.

11.2. Более сложные проекты

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

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

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

3. Написать процедуры обращения и умножения матриц.

4. Компиляцию с языка высокого уровня на язык низкого уровня можно представить себе как последовательное преобразование синтаксических деревьев. Написать такой компилятор сначала для компиляции арифметических выражений. Затем добавить управляющие структуры (типа if-then-else). Точное соблюдение синтаксиса ассемблера в данном случае не столь существенно. Например, арифметическое выражение х+1 может быть «упрощено» до ассемблерной операции inc x, где inc определена как одноместная операция. Проблема распределения регистров может быть отложена на потом за счет предположения, что объектный код предназначен для выполнения на машине с магазинной (стековой) памятью (безадресная машина),

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

6. Разработать формализм для описания набора аксиом, например, из теории групп, евклидовой геометрии, денотационной семантики, и исследовать проблему создания программы доказательства теорем для этих областей.

7. Интерпретатор утверждений Пролога может быть написан на самом Прологе. Напишите интерпретатор, реализующий иные семантики выполнения Пролога, такие как более гибкий порядок выполнения (вместо жесткого слева-направо), возможно, с использованием какого-нибудь «расписания» или планировщика.

8. Ознакомиться по литературе по искусственному интеллекту с вопросом построения планов решения задач, и реализовать генератор планов.

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

10. Написать программу, которая, используя правила грамматики, осуществляет разбор предложений вида;

Fred saw John.

Магу was seen by John.

Fred told Mary to see John.

John was believed to have been seen by Fred.

Was John believed to have told Mary to see Fred?