- •Методические указания и рекомендации по выполнению лабораторных работ
- •Лабораторная работа №1 Основы работы в системе Prolog.
- •Основные понятия программирования на Прологе
- •Рекурсия
- •Задание для самостоятельной работы.
- •Лабораторная работа №2 Синтаксис и семантика программ в Prolog
- •Задание
- •Лабораторная работа №3 Работа со списочными структурами в Prolog
- •Представление списков
- •Некоторые операции над списками
- •Задания
Задание
1. Какие из следующих выражений представляют собой правильные объекты в смысле Пролога? Что это за объекты (атомы, числа, переменные, структуры)?
(а) Диана
(b) диана
(с) 'Диана'
(d) _диана
(e) 'Диана едет на юг'
2. Предложите представление для прямоугольников в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
3. Предложите представление для квадратов в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
4. Предложите представление для окружностей в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
5. Предложите представление для куба в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
6. Предложите представление для параллелепипеда в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
7. Предложите представление для пирамиды в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
8. Предложите представление для трапеции в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
9. Предложите представление для квадрата в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
10. Предложите представление для ромба в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на рис. 5. Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.
11. Какие из следующих выражений представляют собой правильные объекты в смысле Пролога? Что это за объекты (атомы, числа, переменные, структуры)?
(a) едет( диана, юг)
(b) 45
(c) 5( X, Y)
(d) +( север, запад)
(e) три( Черные( Кошки) )
Лабораторная работа №3 Работа со списочными структурами в Prolog
Задачи:
-
Научиться работать со списочными структурами.
Представление списков
Список - это простая структура данных, широко используемая в нечисловом программировании. Список - это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так:
[ энн, теннис, том, лыжи ]
Однако таково лишь внешнее представление списков. Все структурные объекты Пролога - это деревья. Списки не являются исключением из этого правила. Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом [ ]. Во втором случае список следует рассматривать как структуру состоящую из двух частей:
(1) первый элемент, называемый головой списка;
(2) остальная часть списка, называемая хвостом.
Например, для списка
[ энн, теннис, том, лыжи ]
энн - это голова, а хвостом является список
[ теннис, том, лыжи ]
В общем случае, головой может быть что угодно (любой прологовский объект, например, дерево или переменная); хвост же должен быть списком. Голова соединяется с хвостом при помощи специального функтора. Выбор этого функтора зависит от конкретной реализации Пролога; мы будем считать, что это точка:
.( Голова, Хвост)
Поскольку Хвост - это список, он либо пуст, либо имеет свои собственную голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:
.( энн, .( теннис, .( том, .( лыжи, [ ] ) ) ) )
На рис. 7 изображена соответствующая древовидная структура. Заметим, что показанный выше пример содержит пустой список [ ]. Дело в том, что самый последний хвост является одноэлементным списком:
[ лыжи ]
Хвост этого списка пуст
[ лыжи ] = .( лыжи, [ ] )
Рис. 7. Представление списка [энн, теннис, том, лыжи] в виде дерева.
Рассмотренный пример показывает, как общий принцип структуризации объектов данных можно применить к спискам любой длины. Из нашего примера также видно, что такой примитивный способ представления в случае большой глубины вложенности подэлементов в хвостовой части списка может привести к довольно запутанным выражениям. Вот почему в Прологе предусматривается более лаконичный способ изображения списков, при котором они записываются как последовательности элементов, заключенные в квадратные скобки. Программист может использовать оба способа, но представление с квадратными скобками, конечно, в большинстве случаев пользуется предпочтением. Мы, однако, всегда будем помнить, что это всего лишь косметическое улучшение и что во внутреннем представлении наши списки выглядят как деревья. При выводе же они автоматически преобразуются в более лаконичную форму представления. Так, например, возможен следующий диалог:
?- Список1 = [а, b, с],
Список2 = (a, .(b, .(c,[ ]) ) ).
Список1 = [а, b, с]
Список2 = [а, b, с]
?- Увлечения1 = .( теннис, .(музыка, [ ] ) ),
Увлечения2 = [лыжи, еда],
L = [энн, Увлечения1, том, Увлечения2].
Увлечения1 = [теннис, музыка]
Увлечения2 = [лыжи, еда]
L = [энн, [теннис, музыка], том, [лыжи, еда]]
Приведенный пример также напоминает вам о том, что элементами списка могут быть любые объекты, в частности тоже списки.
На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть
L = [а, b, с]
Тогда можно написать:
Хвост = [b, с] и L = .(а, Хвост)
Для того, чтобы выразить это при помощи квадратных скобок, в Прологе предусмотрено еще одно расширение нотации для представления списка, а именно вертикальная черта, отделяющая голову от хвоста:
L = [а | Хвост]
На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ " | ", а после этого - список остальных элементов. Так, только что рассмотренный пример можно представить следующими различными способами:
[а, b, с] = [а | [b, с]] = [a, b | [c]] = [a, b, c | [ ]]
Подытожим:
-
Список - это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста. Хвост в свою очередь сам является списком.
-
Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде
[Элемент1, Элемент2, ... ] или
[ Голова | Хвост ] или
[ Элемент1, Элемент2, ... | Остальные]