Функциональное и логическое программирование

Федеральное агентство связи Сибирский государственный университет телекоммуникаций и информатики М.Ю. Галкина Функциональное и логическое программирование Лекции Новосибирск 2008 Введение. Классификация языков программирования 3 Глава 1 Функциональное программирование. Основы языка Лисп 5 1.1 Типы данных в Лиспе 6 1.2 Функции 7 1.2.1 Арифметические функции 7 1.2.2 Функции обработки списков 8 1.3 Предикаты 10 1.4 Псевдофункции SET и SETQ 12 1.5 Интерпретатор языка Лисп EVAL 13 1.6 Определение функций пользователем 14 1.7 Функции ввода-вывода и работа с файлами 16 1.8 Последовательные вычисления 18 1.9 Разветвление вычислений 19 1.10 Рекурсия 20 1.10.1 Простая рекурсия 21 1.10.2 Использование накапливающих параметров 26 1.10.3 Параллельная рекурсия 28 1.10.4 Взаимная рекурсия 32 1.10.5 Вложенные циклы 32 1.11. Внутреннее представление s-выражений 33 1.12 Точечная пара 36 1.13 Функционалы 38 1.13.1 Аппликативные (применяющие функционалы) 38 1.13.2 Отображающие функционалы или MAP-функции 40 1.14. Вопросы и задания для самоконтроля 42 Глава 2 Логическое программирование. Основы языка Пролог 43 2.1 Факты и правила 45 2.2 Поиск решений Пролог-системой 48 2.3 Структура программы Турбо-Пролога 51 2.3.1 Описание доменов и предикатов, объекты данных 51 2.3.2 Ввод-вывод в Турбо-Прологе 54 2.3.3 Внутренние и внешние цели 54 2.4 Рекурсия 55 2.5 Семантика Пролога 57 2.5.1 Порядок предложений и целей 57 2.5.2 Пример декларативного создания программы 58 2.6 Внелогические предикаты управления поиском решений 61 2.6.1 Ограничение перебора – отсечение 61 2.6.2 Откат после неудач 63 2.6.3 Циклы, управляемые откатом 64 2.7 Списки 65 2.7.1 Голова и хвост списка 66 2.7.2 Операции со списками 66 2.7.2.1 Принадлежность элемента списку 66 2.7.2.2 Соединение двух списков 67 2.7.2.3 Добавление и удаление элемента из списка 68 2.7.2.4 Деление списка на два списка по разделителю 69 2.7.2.5 Подсчет количества элементов в списке 69 2.7.2.6 Подсписок 69 2.7.3 Сортировка списков. 70 2.7.3.1 Сортировка вставкой 70 2.7.3.2 Пузырьковая сортировка 70 2.7.3.3 Быстрая сортировка 71 2.7.4 Компоновка данных в список 71 2.8 Решение логических задач с использованием списков 72 2.8.1 Задача о фермере, волке, козе и капусте 72 2.8.2 Решение числовых ребусов 74 2.9 Строки 76 2.10 Предикаты для работы с файлами 78 2.11 Динамические базы данных 82 2.11.1 Добавление и удаление фактов 83 2.11.2 Заполнение динамической базы данных фактами из файла, сохранение динамической базы данных в файле 84 2.12 Экранные окна и создание меню 87 2.13 Операции над структурами данных 89 2.13.1 Деревья 89 2.13.1.1 Отображение деревьев 92 2.13.1.2 Обходы деревьев 93 2.13.2 Графы 94 2.14 Стратегии решения задач 97 2.14.1 Стратегия поиска в глубину 98 2.14.2 Стратегия поиска в ширину 98 2.15. Вопросы и задания для самоконтроля 99 Ответы на задания для самоконтроля 99 Рекомендуемая литература 100 Введение. Классификация языков программирования По одной из классификаций языки программирования можно разделить на три типа: процедурные (операторные), функциональные, декларативные. На практике языки программирования часто обычно содержат в себе черты различных типов. На процедурном языке часто можно написать функциональную программу или ее часть и наоборот. Поэтому, точнее было бы вместо типа языка говорить о стиле или методе программирования. Естественно, что различные языки поддерживают разные стили в разной степени. Программа на процедурном языке состоит из последовательности операторов и предложений, управляющих последовательностью их выполнения. Типичными операторами являются операторы присваивания, циклов, ввода-вывода, передачи управления. Из операторов можно составлять подпрограммы. Основа процедурного программирования: взятие значения какой-либо переменной, выполнение с ним какого-нибудь действия, сохранение нового значения и так до тех пор, пока не будет получено желаемое окончательное значение. К процедурным языкам относят такие языки программирования как Бейсик, Паскаль, Си. Функциональный стиль программирования является обобщением и развитием одного простого наблюдения – любую программу можно рассматривать как функцию, в качестве аргументов которой выступают входные данные этой программы, а в качестве значений – результаты ее работы. Основным методом программирования при таком подходе является суперпозиция функций. Функции часто прямо или опосредованно вызывают себя. “Чистое” функциональное программирование не признает операторов присваиваний, циклов и передач управления, функции взаимодействуют между собой только через аргументы и значения. На практике предположения чисто функционального подхода часто нарушаются. Некоторые функции обмениваются информацией через побочные эффекты. Другие, так называемые специальные функции, выполняются не по общим правилам (для их работы не требуется определения всех аргументов). Повторные вычисления при функциональном подходе к программированию осуществляются через рекурсию, разветвление вычислений основано на механизме обработки условного выражения. Как компьютер выполняет функциональную программу? Основное правило выполнения этой программы является прямым следствием главного предположения функционального программирования – программа есть функция в математическом смысле. Из этого утверждения следует, что сначала определяются все аргументы функции, а затем вычисляется ее значение. Выполнение этого правила приводит к тому, что выполнение функциональной программы сводится к последовательности замен примитивных и составных функций, которая постепенно упрощает исходную суперпозицию до одного значения – результата. На каждом шаге выполнения программы заменяется значением одна из функций, аргументы которой известны. В определенном смысле использование рекурсивных функций “экономит мышление” – позволяет компактно записывать решение задачи. Кроме того, часто весьма трудные для алгоритмических языков задачи с помощью рекурсивных функций естественно и легко формулируются и изящно решаются. В качестве примера рассмотрим известную задачу о Ханойских башнях. Эту задачу придумали буддийские монахи. Они верили, что время решения этой задачи для 64 дисков, соответствует времени наступления конца света. Задача заключается в следующем. Имеется три вертикальных стержня A, B, C и совокупность n круглых дисков различного диаметра с отверстием. В исходном состоянии диски нанизаны по порядку в соответствии со своим размером на диск A. Рисунок 1 – Задача о ханойской башне Требуется перенести все диски на стержень B, расположив их в том же порядке, соблюдая следующие правила: • За один раз можно перенести только один диск. • Больший по размеру диск нельзя положить на меньший. Третий стержень можно использовать как вспомогательный. Если он свободен или там лежит больший диск, то на него можно переложить очередной диск на то время, пока переносится ниже лежащий диск. В этой идее и содержится решение задачи. Ее лишь надо обобщить. Алгоритм решения задачи: 1. Перенести со стержня A n-1 дисков на вспомогательный стержень C (задача Ханойские башни для n-1). 2. Перенести нижний диск со стержня A на стержень B. 3. Перенести со стержня С n-1 дисков на стержень B (задача Ханойские башни для n-1). Для одного и двух дисков задача решается быстро. Для трех дисков в соответствии с изложенным алгоритмом следует выполнить следующие переносы: A  B, A  C, B  C, A  B, C  A, C  B, A  B. Для большего количества дисков количество переносов резко возрастает. Для решения задачи с 10 дисками нужно выполнить 1023, в случае n дисков решение задачи требует 2n-1 переносов. Если считать, что для 1 переноса требуется 1 микросекунда, то время решения задачи с 64 дисками составит 585000 лет. К функциональным языкам программирования относят такие языки, как Лисп, APL, Logo. Основным отличием декларативных языков от функциональных является то, что выполнение программы может идти помимо обычного выполнения и в обратном направлении: на основе результата вычислять исходные данные. В декларативных языках описываются объекты предметной области, зависимости между ними и цель задачи, а решение задачи находится автоматически. Представителями логических языков являются Пролог, Плэннер, Mandala. Первое время программирование на Лиспе и Прологе будет похоже на игру в волейбол одной рукой и будет вызывать чувство протеста. Но затем это чувство заменится на восхищение мощностью и лаконичностью этих языков. Глава 1 Функциональное программирование. Основы языка Лисп Язык Лисп был разработан в Америке Дж.Мак-Карти в 1961 году и ориентирован прежде всего на символьную обработку, которая не накладывает таких жестких требований к эффективности, как вычислительные задачи. Название языка Lisp – сокращенная запись List processing (“Обработка списков”). Списки – это наиболее гибкая форма представления информации. С помощью списков удобно представлять множества, графы, правила вывода и другие сложные объекты. Большая часть имеющихся на рынке программ символьной обработки, работы с естественным языком написаны на Лиспе. Это программы автоматического доказательства теорем, игры в шахматы, экспертные системы и т.д. На Лиспе реализован AutoCAD - система автоматизации инженерных расчетов, дизайна и комплектации изделий из имеющихся элементов, и популярный текстовый редактор Emacs для систем UNIX, Linux. В настоящее время Лисп используется как основное средство программирования в системе AutоCAD – системе автоматического проектирования. В нашей стране Лисп не получил широкого распространения, хотя Мак-Карти еще в 1968 году в Вычислительном центре CO AH заложил основу реализации языка на машине БЭСМ-6. БЭСМ-6 была мощной 48-битовой машиной с быстродействием около 1 миллиона операций в секунду и использовалась для научно-технических расчетов. Но, тем не менее, в Москве, Санкт-Петербурге, Тбилиси появились новые реализации Лиспа для машин других серий. В 1978 году появился первый учебник по Лиспу на русском языке. Основа Лиспа – лямбда-исчисление Черча, формализм для представления функций и способов их комбинирования. Например, в соответствии с этим формализмом функция может являться аргументом функции. Черты этого формализма есть в Паскале. Перечислим ряд удивительных свойств языка. Во-первых, это однообразная форма представления программ и данных. Во-вторых, это использование в качестве основной управляющей конструкции рекурсии. В-третьих, широкое использование данных “список” и алгоритмов обработки этих данных. Простота синтаксиса Лиспа является одновременно его достоинством и недостатком. Начинающий программист может выучить основные правила синтаксиса за несколько минут. Основной проблемой этого синтаксиса являются скобки. Часто в определении функции накапливается до 10-15 вложенных уровней скобок. Такие конструкции чрезвычайно трудно читать и отлаживать, и ошибка в расположении скобок является наиболее типичной синтаксической ошибкой в Лиспе. Часто встречаются ошибки, когда выражение для определения функции выглядит “осмысленно”, но семантика этого выражения не совпадает с тем, что в него хотели вложить. Существует даже шутливое толкование названия языка: Lots of Idiotic Silly Parentheses. Неудобством языка является то, что существует много диалектов и, к сожалению, ни один из них не принят в качестве стандарта. Все реализации языка являются интерпретаторами, т.е. любая команда сразу обрабатывается. Далее мы рассмотрим muLisp – один из самых удачных диалектов языка, созданный фирмой Soft WareHouse Inc (США). Для запуска интерпретатора следует запустить файл mulisp.com. На экране появится значок $ - приглашение ввести команду. Когда пользователь заканчивает ввод вызова функции или выражения, то интерпретатор сразу же вычисляет значение этого выражения, выдает на экран это значение и очередное приглашение для ввода команды. Для повторения команды, содержащейся в предыдущей строке достаточно нажать функциональную клавишу F3. Для завершения работы следует ввести команду (system). 1.1 Типы данных в Лиспе Основные типы данных в Лиспе – это атомы, списки, точечные пары. Атомы можно классифицировать следующим образом: Рисунок 2 – Типы данных в Лиспе Переменная – это последовательность из букв, цифр и специальных знаков. Переменные представляют другие объекты: числа, другие символы, функции. Например, символами являются *, as-2. Числа состоят из цифр и точки, которым может предшествовать знак + или –. Число не может представлять других объектов, кроме самого себя. Например, -34.5, 25 – числа. Специальные символы: t и nil. Символ t обозначает логическое значение истина, а nil – имеет два значения: логическая ложь и пустой список. Все структуры данных в Лиспе строятся из атомов. Списком называется упорядоченная последовательность, элементами которой являются атомы или списки. Список заключается в скобки, а элементы разделяются пробелами. Примеры: 1. (a) – список из одного элемента; 2. () или nil – пустой список; 3. ((my house) has (big windows)) – список из трех элементов. Часто бывает удобно не различать атомы и списки. В этом случае говорят о символьных выражениях (s–выражениях). Про точечные пары будет изложено дальше. 1.2 Функции В Лиспе вызов функции записывается в префиксной нотации. Cначала идет имя функции, пробел, затем аргументы через пробел, и все это заключается в скобки. Пример: Математическая запись f(x) соответствует лисповской записи (f x), а математическая запись xy–z соответствует (– (* x y) z). Видно, что по внешнему виду функция и список не различаются. Поэтому, для того, чтобы выражение в скобках воспринималось как список, а не вызов функции, используется специальная функция QUOTE (читается как квэут). Эта функция блокирует вычисления и соответствует математической функции f(x)=x. Причем, значение аргумента не вычисляется. Часто вместо (QUOTE x) пишут ‘x. Перед константой знак ‘ не ставят, т.к. константа и ее значение совпадают. Самая левая QUOTE блокирует все вычисления в своем аргументе. В приводимых примерах после – > приводится результат работы функции, который выводится на экран, если функцию вводить в командную строку. Примеры: 1. (QUOTE (+ 2 3)) –> (+ 2 3); 2. (+ ‘2 3) –> 5; 3. (QUOTE ‘(+1 2)) –> (QUOTE (+ 1 2)). 1.2.1 Арифметические функции В muLispе присутствуют основные арифметические функции: • Сложение. Обозначается, как + и может иметь несколько аргументов. Например, a+b+c+d на Лиспе будет иметь вид (+ a b c d). • Вычитание. Обозначается, как – и может иметь несколько аргументов. Например, a–b–c–d на Лиспе будет иметь вид (– a b c d). • Умножение. Обозначается, как * и может иметь несколько аргументов. Например, abc на Лиспе будет иметь вид (* a b c). • Деление. Обозначается, как / и может иметь несколько аргументов. Например, 16:2:4 на Лиспе будет иметь вид (/ 16 2 4). • Взятие модуля. Обозначается как ABS и имеет один аргумент. Например, |a| на Лиспе будет иметь вид (ABS a). Суперпозиция функций всегда вычисляется “изнутри наружу”. Примеры: Запишем на Лиспе следующие выражения: 1. (1+2)(3+4) 2. (a+b)/2 3. x2+2x-5 В первом случае, получаем (* (+ 1 2) (+ 3 4)), во втором – (/ (+ a b)), в третьем – (+ (* x x) (* 2 x) –5). 1.2.2 Функции обработки списков Разделим список на голову и хвост. Головой назовем первый элемент списка, а хвостом – список без первого элемента. Например, для списка ((1 2) 4 (5)) головой будет список (1 2), а хвостом – список (4 (5)). Функция CAR находит голову списка. Результатом работы функции будет s-выражение. Вызов функции имеет вид: (CAR список). Функция CDR находит хвост списка. Результатом работы функции будет список. Вызов функции имеет вид: (CDR список). Примеры: 1. (CAR ‘(a b c))  a; 2. (CDR ‘(a b c))  (b c); 3. (CAR nil)  nil (голова пустого списка – пустой список); 4. (CDR ‘(a))  nil. Последовательно применяя функции CAR и CDR можно выделить любой элемент списка. Только следует помнить, что функции применяются “изнутри - наружу”. Пример: Для выделения в списке ((а b c) (d e) (f)) элемента c необходимо выполнить: (CAR (CDR (CDR (CAR ‘((а b c) (d e) (f)) )))). Допускается сокращение (CADDAR ‘((а b c) (d e) (f))). При сокращении подряд не может идти больше четырех букв A и D. Функция CONS создает новый список, головой которого является первый аргумент функции, а хвостом – второй аргумент функции. Результатом работы функции будет список. Вызов функции имеет вид: (CONS s-выражение список). Примеры: 1. (CONS ‘a ‘(b c))  (a b c); 2. (CONS ‘a nil))  (a); 3. (CONS ‘(1 2) ‘(3 4))  ((1 2) 3 4); 4. (CONS (+ 1 2) (* 3 4))  (3 * 3 4); 5. (CONS nil nil))  (nil). Если второй аргумент функции CONS не является списком, то образуется так называемая точечная пара. О ней речь пойдет позже. Пример: (CONS 1 2))  (1.2). Можно заметить, что функции CAR и CDR являются обратными для CONS. Примеры: 1. (CONS (CAR ‘(1 2 3)) (CDR ‘(1 2 3))  (1 2 3); 2. (CAR (CONS 1 ‘(2 3))  1; 3. (CDR (CONS 1 ‘(2 3)))  (2 3). Функция LIST создает новый список, элементами которого являются аргументы функции. Результатом работы функции будет список. Вызов функции имеет вид: (LIST s1  sn), где si – s-выражение. Примеры: 1. (LIST ‘a ‘b ‘(+ 1))  (a b (+ 1)); 2. (LIST ‘((a)) nil)  (((a)) nil). Для любой функции LIST можно составить эквивалентную композицию функций CONS. Для примера 1 это будет (CONS ‘a (CONS ‘b (CONS ‘(+ 1) nil))). Функция APPEND создает новый список, элементами которого являются элементы списков - аргументов функции. Результатом работы функции будет список. Вызов функции имеет вид: (APPEND sp1  spn), где spi – список. Примеры: 1. (APPEND ‘(1 2) ‘(3) ‘(+ *))  (1 2 3 + *); 2. (APPEND ‘((1)) ‘()) ((1)). Функция LAST создает список из одного элемента – последнего элемента списка - аргумента функции. Результатом работы функции будет список. Вызов функции имеет вид: (LAST список). Примеры: 1. (LAST ‘(1 2 3))  (3); 2. (LAST ‘())  (nil). Функция REVERSE возвращает список, являющийся “перевернутым” списком – аргументом. Перестановка элементов осуществляется только на верхнем уровне. Результатом работы функции будет список. Вызов функции имеет вид: (REVERSE список). Примеры: 1. (REVERSE ‘(1 2 3))  (3 2 1); 2. (REVERSE ‘(1 (2 3) ((4))))  (((4)) (2 3) 1); 3. (REVERSE ‘())  nil. 1.3 Предикаты Если перед вычислением функции необходимо убедиться, что ее аргументы принадлежат области определения, или возникает задача подсчета элементов списка определенного типа, то используют специальные функции – предикаты. Предикатом называется функция, которая используется для распознавания или идентификации и возвращает в качестве результата логическое значение - специальные символы t или nil. Часто имена предикатов заканчиваются на P (от слова Predicate). Предикат ATOM возвращает значение t, если аргумент является атомом. Вызов предиката имеет вид: (ATOM s-выражение). Примеры: 1. (ATOM ‘x)  t; 2. (ATOM ‘((1) 2)  nil; 3. (ATOM nil)  t. Предикат LISTP возвращает значение t, если аргумент является списком. Вызов предиката имеет вид: (LISTP s-выражение). Примеры: 1. (LISTP ‘x)  nil; 2. (LISTP ‘((1) 2)  t; 3. (LISTP nil)  t. Предикат SYMBOLP возвращает значение t, если аргумент является атомом – переменной или специальным символом. Вызов предиката имеет вид: (SYMBOLP s-выражение). Примеры: 1. (SYMBOLP +x)  t; 2. (SYMBOLP 2)  nil; 3. (SYMBOLP ‘(a b c))  nil; 4. ((SYMBOLP t)  t. Предикат NUMBERP возвращает значение t, если аргумент является числом. Вызов предиката имеет вид: (NUMBERP s-выражение). Примеры 1. (NUMBERP 56)  t; 2. (NUMBERP ‘t)  nil. Предикат NULL возвращает значение t, если аргумент является пустым списком. Вызов предиката имеет вид: (NULL s-выражение). Примеры: 1. (NULL ‘(5 6))  nil; 2. (NULL (ATOM ‘(1 2))  t; 3. (NULL (LIST ‘(1 2))  nil. Рассмотрим еще несколько предикатов, аргументами которых являются числа. Предикат = возвращает значение t, если все аргументы – числа равны между собой. Вызов предиката имеет вид: (= n1 nm), где ni - число. Примеры: 1. (= 1 1 2)  nil; 2. (= 4 4)  t. Предикат < возвращает значение t, если все аргументы – числа упорядочены в порядке возрастания. Вызов предиката имеет вид: (< n1 nm), где ni - число. Этот предикат можно использовать для проверки попадания числового значения в заданный диапазон. Примеры: 1. (< 1 1 2)  nil; 2. (< 1 x 2)  3. (< 3 6 8 9)  t. Аналогично определяются предикаты: > (проверка аргументов – чисел на упорядоченность по убыванию);  (проверка аргументов – чисел на упорядоченность по неубыванию);  (проверка аргументов – чисел на упорядоченность по невозрастанию); /= (проверка аргументов – чисел на неравенство всех пар рядом стоящих аргументов). Примеры: 1. (> 4 1 -5)  t; 2. (<= 3 3 8 9)  t; 3. (>= 9 9 5 5)  t; 4. (/= 1 4 1)  t. Для сравнения s-выражений используется предикаты EQUAL и EQ. Предикат EQUAL возвращает значение t, если совпадают внешние структуры s-выражений. Вызов предиката имеет вид: (EQUAL s1 s2), где si (i=1,2) – s-выражение. Предикат EQ возвращает значение t, если совпадают внешние структуры s-выражений и их физические адреса. При использовании EQ следует помнить, что одноименные переменные всегда хранятся в одном месте, а списки – нет. Кроме того, малые целые числа (меньшие 65536 по абсолютной величине) определяются уникально, а большие целые числа (большие 65536 по абсолютной величине) и дробные числа не определяются уникально. Вызов предиката EQ производится аналогично вызову EQUAL. Примеры: 1. (EQUAL a a)  t; 2. (EQUAL ‘(a b) ‘(a b))  t; 3. (EQUAL ‘(a) a)  nil; 4. (EQ a a)  t; 5. (EQ 100000 100000)  nil; 6. (EQ ‘(a) ‘(a))  nil; Здесь список (a) создан дважды и хранится по разным адресам; 7. (EQ 2.25 2.25)  nil. Заметим, что функции EQUAL и EQ иногда называют примитивными функциями сопоставления с образцом. 1.4 Псевдофункции SET и SETQ Мы уже видели, что перед любыми лисповскими константами (числами и символами t и nil) не надо ставить апостроф, т.к. значением константы является сама константа. Символы могут обозначать некоторые выражения. Если символ не имеет значения, то считается, что символ представляет самого себя. Связать символ с некоторым значением можно при помощи функций SET и SETQ. Эти функции являются псевдофункциями, поскольку эти функции возвращают в качестве своего значения вычисленное значение второго аргумента, а связывание является побочным эффектом работы этих функций. Функция SET вычисляет значения обоих аргументов и возвращает значение второго аргумента. Побочным эффектом работы этой функции является связывание значений аргументов. Вызов функции имеет вид: (SET символ s-выражение). Примеры: 1. (SET a 2)  2, побочный эффект – связывание: a  2; (SET c ‘(1 2))  (1 2), побочный эффект – связывание: с  (1 2); (SET c ‘(3 4))  ошибка, не может выполниться связывание: (3 4)  (1 2) (символ c получил значение (3 4) в предыдущей строке); Для изменения значения c следовало обратиться к функции следующим образом: (SET ‘c ‘(3 4)). Тогда результатом работы функции будет (3 4), а побочным эффектом – связывание с  (3 4). 2. (SET a ‘(b c d))  (b c d), побочный эффект – связывание: a  (b c d); (SET (car a) 3)  3, побочный эффект – связывание: b  3; (SET b 4)  ошибка, не может выполниться связывание: 3  4 (символ b получил значение 3 в предыдущей строке); Для изменения значения b следовало обратиться к функции следующим образом: (SET ‘b 4). Тогда результатом работы функции будет 4, а побочным эффектом – связывание b  4. В случае если вычислять значение символа – первого аргумента не требуется, то вместо того, чтобы перед символом писать ‘, можно использовать функцию SETQ. Об автоматическом блокировании вычисления первого аргумента напоминает буква Q (от QUOTE) в имени функции. Функция SETQ имеет четное количество аргументов. Аргументы с нечетными номерами должны быть символами, а с четными – s-выражениями. Функция вычисляет значения аргументов с четными номерами и возвращает значение последнего вычисленного s-выражения. Побочным эффектом работы этой функции является связывание символов - аргументов с нечетными номерами со значениями вычисленных s-выражений. Вызов функции имеет вид: (SETQ p1 s1  pn sn), где pi-символ, si-s-выражение. Пример: Рассмотрим пример работы предиката SETQ: (SETQ a 1 b 2 c a)  1, побочный эффект – связывания: a  1, b  2, c  1. Все образовавшиеся связи действительны в течение всего сеанса работы с интерпретатором Лиспа. Если необходимо разорвать все образовавшиеся связи, следует выполнить команду (RESTART). 1.5 Интерпретатор языка Лисп EVAL Интерпретатор Лиспа называется EVAL и его можно так же, как и другие функции вызывать из программы. “Лишний” вызов интерпретатора может, например, снять эффект блокировки вычисления от функции QUOTE или найти значение значения выражения, т.е. осуществить двойное вычисление. Функция EVAL вычисляет значение значения аргумента и возвращает его. Вызов функции имеет вид: (EVAL s-выражение). Примеры: 1. (EVAL ‘(+ 4 8))  12; 2. (SETQ x ‘(a b c))  (a b c), побочный эффект – связывание: x  (a b c); (EVAL ‘x)  (a b c); (EVAL x)  ошибка, т.к. сначала вычисляется значение x, а потом делается попытка вычислить функцию с именем a; 3. (SETQ a ‘b)  b, побочный эффект – связывание: a  b; (SETQ b ‘c)  c, побочный эффект – связывание: b  c; (EVAL a)  c, вычисляется значение значения a, т.е. значение b; (EVAL ‘a)  b. 4. (SETQ a 3)  3, побочный эффект – связывание: a  3; (SETQ b ‘a)  a, побочный эффект – связывание: b  a; (EVAL b)  3, вычисляется значение значения a; (SETQ a 4)  4, побочный эффект – связывание: a  4; (EVAL b)  4, вычисляется значение значения b, т.е. значение a; (EVAL ‘b)  a. Для функции EVAL нет аналогий в процедурных языках программирования. Используя EVAL, мы можем выполнить “оператор”, который создан Лисп-программой и который может меняться в процессе выполнения программы. Лисп позволяет с помощью одних функций формировать определения других функций, программно анализировать и редактировать эти определения как s-выражения, а затем , используя функцию EVAL, исполнять их. Диалог с интерпретатором языка Лисп на самом верхнем, командном, уровне можно описать простым циклом: (PRINT ‘$) % На экран выводится приглашение; (PRINT (EVAL (READ))) % Ввод выражения с клавиатуры, вычисление его значения и вывод этого значения на экран (PRINT ‘$) % Повторение вывода приглашения. ……………… 1.6 Определение функций пользователем Определение функций и их вычисление в Лиспе основано на лямбда-исчислении Черча, представляющем простой и точный формализм для описания функций. Для описания функции в Лиспе используется лямбда-выражение, которое имеет вид: (LAMBDA (x1 x2  xn) S1 S2  Sk), где x1, x2, , xn – формальные параметры функции, S1, S2, , Sk – последовательность s-выражений, которые образуют тело функции и описывают вычисления. Список из формальных параметров называется лямбда-списком. Лямбда-выражение соответствует используемому в других языках определению функции. Например, функцию f (x, y) = x2 + y2 можно определить с помощью следующего лямбда-выражения: (LAMBDA (x y) (+ (* x x) (* y y))). Лямбда-выражение нельзя вычислить, оно не имеет значения. Но можно организовать лямбда-вызов, который соответствует вызову функции и имеет вид: (лямбда-выражение a1 a2  an), где a1, a2, , an – вычислимые s-выражения, задающие вычисления фактических параметров. Например, для того, чтобы найти вычислить значение функции f (2, 3) где f (x, y) = x2 + y2, можно организовать следующий лямбда-вызов: ((LAMBDA (x y) (+ (* x x) (* y y))) 2 3)  13. Вычисление лямбда-вызова производится в два этапа. Сначала вычисляются значения фактических параметров и соответствующие формальные параметры связываются с полученными значениями. На следующем этапе с учетом новых связей вычисляется тело функции, и последнее вычисленное значение возвращается в качестве значения лямбда-вызова. После завершения лямбда-вызова фактические параметры получают те связи, которые были у них до вычисления лямбда-вызова, т.е. происходит передача параметров по значению. Лямбда-вызовы можно объединять между собой и другими формами. Лямбда-вызовы можно ставить как на место тела функции, так и на место фактических параметров. Примеры: 1. Лямбда-вызов стоит на месте фактического параметра: ((LAMBDA (x) (LIST 2 x)) ((LAMBDA (y) (LIST y)) ‘a))  (2 (a)), (a) – вычисленное значение фактического параметра. 2. Лямбда-вызов стоит на месте тела функции: ((LAMBDA (x) ((LAMBDA (y) (LIST y x)) ‘a)) ‘b)  (a b), сначала x связывается с b, затем вычисляется тело функции – лямбда-вызов, при котором y связывается с a и создается список (a b). Лямбда-выражение является чисто абстрактным механизмом для определения и описания вычислений. Это безымянная функция, которая пропадает сразу после вычисления значения лямбда-вызова. Ее нельзя использовать еще раз, т.к. она не имеет имени. Тем не менее, безымянные функции используются при передаче функции в качестве аргумента другой функции или при формировании функции в результате вычислений. Дать имя функции можно с помощью функции DEFUN, вызов которой имеет следующий вид: (DEFUN имя_функции лямбда-список тело_функции). Функция DEFUN возвращает имя функции, а ее побочным эффектом является связывание символа - имени функции с соответствующим лямбда-выражением: (LAMBDA лямбда-список тело_функции). Примеры: 1. Определим функцию list2 с двумя аргументами, которая создает список из своих аргументов: ( DEFUN list2 (x y) (CONS x (CONS y nil)) )  list2; Обращение к функции: (list2 ‘a 1)  (a 1) 2. Определим функцию NEWFUN, которая имеет два аргумента x и y, и определяет другую функцию с именем x и лямбда-выражением y: (DEFUN NEWFUN (x y) (EVAL (CONS ‘DEFUN (CONS x (CDR y)))))  NEWFUN Обращение к функции NEWFUN для определения функции с именем SUM, вычисляющей сумму квадратов своих аргументов: (NEWFUN ‘SUM ‘(LAMBDA (x y) (+ (* x x) (* y y))))  SUM Теперь можно обратиться к функции SUM: (SUM 2 3)  13 (22+32) 3. Определим функцию без аргументов pi, которая приближенно вычисляет число : (DEFUN pi() 3.141592)  pi; Обращение к функции: (pi)  3.141592. 1.7 Функции ввода-вывода и работа с файлами До сих пор все определения функций набирались в командной строке, и обращение к стандартным функциям Лиспа и определяемым функциям осуществлялось так же через командную строку. Это неудобно, т.к. при каждом сеансе работы приходилось заново вводить описания новых функций. В дальнейшем будем новые функции сохранять в файле с расширением lsp (файл можно создать с помощью блокнота), а затем из командной строки Лиспа загружать этот файл в память. В файле так же может содержаться последовательность обращений к стандартным и вновь определенным функциям. Загрузку из файла можно осуществить функцией LOAD. Функция LOAD подает файл на вход интерпретатору Лиспа для дальнейшей обработки. Результатом работы функции будет имя файла, если файл был найден и успешно обработан или nil в противном случае. Вызов функции имеет вид: (LOAD ‘имя_файла). Имя файла должно начинаться с буквы! Если не указано расширение файла, то автоматически приписывается расширение lsp. Файл ищется в текущей папке, откуда был запущен Лисп. Для доступа к файлу, находящемуся во вложенной в текущую папку папке, следует указать путь от текущей папки. В остальных случаях следует набрать полный путь, заменив каждый \, встречающийся в описанном пути, на \\. Примеры: 1. (LOAD ‘lab1)  lab1.lsp, успешно загружен файл lab1.lsp, находящийся в текущей папке; 2. (LOAD ‘..\\labs\\lab5)  lab5.lsp, успешно загружен файл lab5.lsp, находящийся в папке labs на уровень выше, чем текущая папка; 3. (LOAD ‘c:\\lang\\lisp\\labs\\lab2.txt)  lab2.txt, успешно загружен файл lab2.txt, находящийся по указанному пути. Для обмена данными с файлом, файл сначала открывают с помощью функций OPEN-INPUT-FILE и OPEN-OUTPUT-FILE. Функция OPEN-INPUT-FILE возвращает имя файла, если удалось открыть файл с указанным параметром именем для ввода, и nil в противном случае. Функция OPEN-OUTPUT-FILE возвращает имя файла, если удалось открыть файл с указанным параметром именем для вывода, и nil в противном случае. Открытие файла – побочный эффект работы этих функций. Вызов функций имеет вид: (OPEN-INPUT-FILE ‘имя_файла), (OPEN-OUTPUT-FILE ‘имя_файла). Файл ищется в текущей папке, откуда был запущен Лисп. Для доступа к файлу, находящемуся во вложенной в текущую папку папке, следует указать путь от текущей папки. В остальных случаях следует набрать полный путь, заменив каждый \, встречающийся в описанном пути, на \\. После окончания работы с файлами их следует закрыть с помощью функций CLOSE-INPUT-FILE или CLOSE-OUTPUT-FILE, обращение к которым имеет вид: (CLOSE-INPUT-FILE ‘имя_файла), (CLOSE-OUTPUT-FILE ‘имя_файла). Для ввода с клавиатуры (по умолчанию) или из открытого для ввода файла, используется функция READ. Функция возвращает значение введенного s-выражения. Вызов функции имеет вид: (READ [‘имя_открытого_для_ввода_файла]). Параметр у функции READ является необязательным. Если он не указан, то ввод производится либо с последнего назначенного устройства, либо по умолчанию с клавиатуры. Для перенаправления ввода из файла на ввод с клавиатуры на месте параметра используют слово keyboard. Для ввода значений в переменную используют композицию функций SETQ и READ: (SETQ переменная (READ[‘имя_открытого_для_ввода_файла])). Мы уже видели, что все значения, возвращаемые функциями, и значения переменных, набранных в командной строке, автоматически выводятся на экран. Если обращение к функции производится из файла, который обрабатывается интерпретатором, то для вывода возвращаемых значений на устройство вывода используют функции PRINT, PRINC. Функция PRINT возвращает значение аргумента и, в качестве побочного эффекта, выводит на экран или в открытый для вывода файл это значение и осуществляет переход на следующую строку. Вызов функции имеет вид: (PRINT S [‘имя_открытого_для_вывода_файла]), где S – s-выражение, функция или строка, заключенная в кавычки. Функция PRINC возвращает значение аргумента и, в качестве побочного эффекта, выводит на экран или в открытый для вывода файл это значение. Вызов функции имеет вид: (PRINC S [‘имя_открытого_для_вывода_файла]), где S – s-выражение, функция или строка, заключенная в кавычки. Параметр <имя_открытого_для_вывода_файла> у функций PRINT и PRINC так же является необязательным. Если он не указан, то вывод производится либо на последнее назначенное устройство, либо по умолчанию на экран. Для перенаправления вывода из файла на экран на месте параметра используют слово screen. Вывод строки сопровождается заключением ее в специальные символы: ||. Для того чтобы убрать эти специальные символы, следует установить значение специальной системной переменной print-escape равным nil с помощью функции SETQ: (SETQ *print-escape* nil). Функция TERPRI всегда возвращает nil и, в качестве побочного эффекта, осуществляет переход на следующую строку (на экране или в открытом для вывода файле) указанное значением параметрa количество раз. Вызов функции имеет вид: (TERPRI вычислимое_выражение [‘имя_открытого_для_вывода_файла]). Если не был открыт файл для вывода, функции PRINT, PRINC и TERPRI осуществляют вывод на экран. Пример: Пусть с клавиатуры вводятся два числа и знак операции. Следует вывести в файл сформированное для вычисления выражение и результат вычисления. (TERPRI 2) ; Перевод строки 2 раза (SETQ *print-escape* nil) ; Запрет выводить специальные символы (PRINT “vvedite chislo znak chislo”) ; Приглашение ввести число, знак, число (SETQ a (READ) zn (READ) b (READ)) ; Ввод данных с клавиатуры (SETQ rez (EVAL (LIST zn a b))) ; Формируется выражение для вычисления в прединфиксной форме, вычисляется и результат вычислений связывается с переменной rez (OPEN-OUTPUT-FILE ‘itog.txt) ; Открывается файл для записи результатов работы (TERPRI 3) ; Перевод строки в файле 3 раза (PRINC a) ; Вывод в файл первого числа (PRINC zn) ; Вывод в файл знака операции (PRINC b) ; Вывод в файл второго числа (PRINC “=”) ; Вывод в файл знака равно (PRINC rez) ; Вывод в файл результата операции (CLOSE-OUTPUT-FILE ‘itog.txt) ; Закрытие файла После точек с запятыми идут комментарии. Если с клавиатуры будет введено 3 + 5, то в файл запишется выражение 3 + 5 = 8 с четвертой строки. 1.8 Последовательные вычисления В Лиспе имеются структуры, управляющие последовательностью вычислений. Такие структуры будем называть предложениями. Предложения выглядят внешне как вызовы функции. Предложение записывается в виде скобочного выражений, первый элемент которого является именем управляющей структуры, а остальные элементы «аргументами». Результатом вычисления так же, как и у функций, является значение. Но следует помнить, что предложения не являются вызовами функций и разные предложения по-разному используют свои аргументы. Предложения PROG1, PROGN позволяют работать с несколькими вычисляемыми формами. Они имеют следующую структуру: (PROG1 V1 V2  Vn) (PROGN V1 V2  Vn), где V1 V2  Vn – вычислимые выражения. У этих специальных форм переменное число аргументов, которые они последовательно вычисляют и возвращают в качестве значения предложения значение первого (для PROG1) или последнего (для PROGN) аргумента. Пример: (PROGN (SETQ x 2) (SETQ y (* 3 x))) –> 6 1.9 Разветвление вычислений Предложение COND является основным средством разветвления вычислений. Это синтаксическая форма, позволяющая управлять вычислениями на основе определяемых предикатами условий. Предложение имеет следующую структуру: (COND (P1 V1) (P2 V2)  (Pn Vn) ), где Pi – предикат, Vi – вычислимое выражение (i = 1,n). Значение предложения COND определяется следующим образом: слева направо (сверху вниз) вычисляются предикаты P1, P2,  до тех пор, пока не встретится предикат, возвращающий значение отличное от nil. Пусть это будет предикат Pk. Вычисляется выражение Vk и полученное значение возвращается в качестве значения предложения COND. Если все предикаты предложения COND возвращают nil, то предложение COND возвращает nil. Рекомендуется в качестве последнего предиката использовать специальный символ t, тогда соответствующее ему выражение будет вычисляться во всех случаях, когда ни одно другое условие не выполняется. При составлении предикатов можно использовать встроенные логические функции AND (и), OR (или) и NOT (отрицание). Число аргументов функций AND и OR может быть произвольным. В случае истинности предикат AND возвращает значение своего последнего аргумента, а предикат OR - значение своего первого аргумента, отличного от nil. Пример: Примем, что возможны три типа выражений: пустой список, атом, список. Определим функцию TYPE, определяющую тип выражения. (defun TYPE (l) (COND ((NULL l) ‘pustoi_spisok) ((LISTP l) ‘spisok) (t ‘atom) ) ) Рассмотрим примеры обращения к функции TYPE. (TYPE ‘(1 2)) –> spisok (TYPE (ATOM ‘(a t o m))) –> pustoi_spisok (TYPE ‘a) –> atom Пример: Определим функцию TWO_EQ, возвращающую t, если в двух списках совпадают два первых элемента. (defun TWO_EQ (l1 l2) (COND ((OR (NULL l1) (NULL l2)) nil) ; Нет элементов в одном из списков ((OR (NULL (CDR l1)) (NULL (CDR l2))) nil) ; В одном из списков один элемент ((EQUAL (CAR l1) (CAR l2)) (EQUAL (CADR l1) (CADR l2)) (t nil) ) ) Рассмотрим примеры обращения к функции TWO_EQ. ( TWO_EQ ‘(1 2) (1)) –> nil ( TWO_EQ ‘(1 2 (3 4)) ‘(1 2 8)) –> t В условном предложении может отсутствовать вычислимое выражение Vi (соответствующая строка имеет вид (Pi)) или на его месте может стоять несколько вычислимых выражений (соответствующая строка имеет вид (Pi Vi1 Vi2  Vik)). Если предикат Pi возвращает значение отличное от nil, в первом случае результатом предложения COND будет являться значение Pi, а во втором – выражения Vi1, Vi2, , Vik последовательно вычисляться слева направо и результатом предложения COND будет значение Vik (неявный PROGN). 1.10 Рекурсия Функция называется рекурсивной, если в ее определяющем выражении содержится хотя бы одно обращение к ней самой (явное или через другие функции). Будем говорить о рекурсии по значению, если рекурсивный вызов является выражением, определяющим результат функции. Если в качестве результата функции возвращается значение некоторой другой функции и рекурсивный вызов участвует в вычислении аргументов этой функции, то будем говорить о рекурсии по аргументам. Рекурсия в Лиспе основана на математической теории рекурсивных функций. В этой области математики изучаются вопросы, связанные с вычислимостью. Под вычислимыми понимаются такие задачи, которые можно запрограммировать и решить с помощью компьютера. Основная идея рекурсивного определения заключается в том, что функцию с помощью рекуррентных формул можно свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более «простыми» аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям. При определении рекурсивных функций в Лиспе применяется такой же подход. Во-первых, определение рекурсивной функции должно содержать хотя бы одну рекурсивную ветвь. Во-вторых, в рекурсивном описании должно быть условие окончания рекурсии. При написании рекурсивных функций следует обратить внимание на следующее. Когда выполнение функции доходит до рекурсивной ветви, функционирующий вычислительный процесс приостанавливается, а запускается с начала новый такой же процесс, но уже на новом уровне. Прерванный процесс запоминается, он начнет исполняться лишь при окончании запущенного им нового процесса. В свою очередь, новый процесс так же может приостановиться и т.д. Таким образом, образуется стек прерванных процессов, из которых выполняется лишь последний запущенный процесс. Функция будет выполнена, когда стек прерванных процессов опустеет. Рекурсия хорошо подходит для работы со списками, так как списки могут содержать в качестве элементов подсписки, т.е. иметь рекурсивное строение. Для обработки рекурсивных структур естественно использовать рекурсивные функции. Так же в Лиспе рекурсия используется для организации повторяющихся вычислений. На рекурсии основано разбиение проблемы и разделение ее на подзадачи, решение которых пытаются свести к уже решенным задачам, или в соответствии с основной идеей рекурсии к решаемой в настоящий момент задаче. При поиске решения задачи в Лиспе часто используется механизм возврата (backtracking), основанный так же на рекурсии. При помощи этого механизма можно вернуться из тупиковой ветви к месту разветвления, аннулировав проделанные вычисления. Далее рассмотрим различные виды рекурсии, используемые в Лиспе. 1.10.1 Простая рекурсия Рекурсия называется простой, если вызов функции встречается в некоторой ветви лишь один раз. В процедурном программировании простой рекурсии соответствует обыкновенный цикл. Простую рекурсию можно разделить на два класса: • рекурсия по значению, когда рекурсивный вызов функции определяет результат функции; • рекурсия по аргументам, когда результатом функции является значение другой функции, у которой одним из аргументов является рекурсивный вызов определяемой функции. Перечислим наиболее часто встречающиеся ошибки при написании рекурсивных функций: 1. ошибочное условие (например, список не укорачивается), которое приводит к бесконечной рекурсии; 2. неверный порядок условий; 3. отсутствие проверки какого-нибудь случая. При написании рекурсивных функций для предотвращения бесконечной рекурсии условия остановки рекурсии следует ставить в начале тела функции. В этих условиях следует проверить все особые случаи. Пример 1: Определим функцию STEP, возводящую число в целую неотрицательную степень. Воспользуемся рекурсивным определением степени: (defun STEP (x n) (COND ((= n 0) 1) ; Условие остановки рекурсии (t (* x (STEP x (– n 1))) ) ) В данном случае имеем рекурсию по аргументу (рекурсивный вызов STEP является аргументом функции *). Обращение к функции STEP: (STEP 2 3) –> 8 Рассмотрим работу рекурсии для рассмотренного выше обращения к функции STEP. Числами в скобках обозначена последовательность выполнения вычислении. (10) (STEP 2 3)  8 (1) (8) (9) (* 2 (STEP 2 2))  (* 2 4)  8 (2) (6) (7) (* 2 (STEP 2 1))  (* 2 2)  4 (3) (4) (5) (* 2 (STEP 2 0))  (* 2 1)  2 Шаги 1, 2, 3, 4 соответствуют прямому ходу рекурсии, а шаги 5, 6, 7, 8, 9, 10 – обратному. При прямом ходе рекурсии образуется стек прерванных процессов, состоящий из вызовов (STEP 2 3), (* 2 (STEP 2 2)), (* 2 (STEP 2 1)), (* 2 (STEP 2 0)), которые не могут быть вычислены. Пример 2: Определим предикат ATOM_IN_LIST, проверяющий есть ли среди элементов списка атомы. Запишем определение функции словесно: • если голова списка является атомом, то предикат возвращает t, и дальше список не проверяем (условие остановки рекурсии); • в противном случае проверяем наличие атомов в хвосте; • если дошли до конца списка, то атомов нет (условие остановки рекурсии). (defun ATOM_IN_LIST (l) (COND ((NULL l) nil) ((ATOM (CAR l)) t) (t (ATOM_IN_LIST (CDR l))) ) ) В данном случае имеем рекурсию по значению (рекурсивный вызов ATOM_IN_LIST определяет результат функции). Обращение к функции ATOM_IN_LIST: (ATOM_IN_LIST ‘((1 2) (3))) –> nil Рассмотрим работу рекурсии для рассмотренного выше обращения к функции ATOM_IN_LIST. (5) (ATOM_IN_LIST ‘((1 2) (3)))  nil (1) (4) (ATOM_IN_LIST ‘((3)))  nil (2) (3) (ATOM_IN_LIST ‘())  nil Шаги 1, 2, 3 соответствуют прямому ходу рекурсии, а шаги 4, 5 – обратному. При прямом ходе рекурсии образуется стек прерванных процессов, состоящий из вызовов (ATOM_IN_LIST ‘((1 2) (3))), (ATOM_IN_LIST ‘((3))). Заметим, что если в предложении COND поменять порядок проверки условий (переставить первую и вторую строку), то получим (ATOM_IN_LIST ‘()) –> t Это связано с тем, что в Лиспе голова пустого списка – это nil, а nil является атомом. Следовательно, важно в каком порядке проверяются условия в предложении COND в рекурсивной функции. Пример 3: Определим функцию COPY, копирующую список на верхнем уровне (без учета вложенностей). Запишем определение функции словесно: • скопировать список – это значит соединить голову списка со скопированным хвостом; • копией пустого списка является пустой список (условие остановки рекурсии). (defun COPY (l) (COND ((NULL l) l) (t (CONS (CAR l) (COPY (CDR l)) ) ) ) ) В данном случае имеем рекурсию по аргументу (рекурсивный вызов COPY является аргументом функции CONS). Обращение к функции COPY: (COPY ‘((1 2) 3 4)) –> ((1 2) 3 4) Рассмотрим работу рекурсии для рассмотренного выше обращения к функции COPY. (10) (COPY ‘((1 2) 3 4))  ((1 2) 3 4) (1) (8) (9) (CONS ‘(1 2) (COPY ‘((3 4))  (CONS ‘(1 2) (3 4))  ((1 2) 3 4) (2) (6) (7) (CONS 3 (COPY ‘((4))  (CONS 3 (4)) (3 4) (3) (4) (5) (CONS 4 (COPY ‘())  (CONS 4 nil)  (4) Шаги 1, 2, 3, 4 соответствуют прямому ходу рекурсии, а шаги 5, 6, 7, 8, 9, 10 – обратному. Выполнив небольшие изменения, эту функцию можно использовать для различных преобразований списка на верхнем уровне. Пример 4: Определим функцию MEMBER_S, проверяющую принадлежность s-выражения списку на верхнем уровне. В случае, если s-выражение принадлежит списку, функция возвращает часть списка, начинающуюся с первого вхождения s-выражения в список. В Лиспе имеется аналогичная встроенная функция MEMBER (но она использует в своем теле функцию EQ, поэтому не работает для вложенных списков). Запишем определение функции MEMBER_S словесно: • если s-выражение совпадает с головой списка, то возвращаем этот список (условие остановки рекурсии); • в противном случае ищем первое вхождение s-выражения в хвосте списка; • если дошли до конца списка, то s-выражение не входит в список (условие остановки рекурсии). (defun MEMBER_S (x l) (COND ((NULL l) l) ((EQUAL x (CAR l)) l) (t (MEMBER_S x (CDR l)) ) ) ) В данном случае имеем рекурсию по значению. Обращения к функции MEMBER_S: (MEMBER_S 1 ‘(2 (3) 1 5)) –> (1 5) (MEMBER_S 1 ‘(2 (1) 3 5)) –> nil (MEMBER_S ‘(1 2 3) ‘(6 (8) (1 2 3) 1 5)) –> ((1 2 3) 1 5)) Заметим, что встроенная функция MEMBER для последнего примера вернула бы nil, т.к. в теле функции для сравнения используется функция EQ. ( MEMBER ‘(1 2 3) ‘(6 (8) (1 2 3) 1 5)) –> nil Пример 5: Определим функцию MAX_SP ,определяющую максимальный элемент списка. Запишем определение функции словесно: • если список состоит из одного элемента, то его максимальным элементом является этот элемент (условие остановки рекурсии); • в противном случае максимальный элемент списка равен максимальному числу из двух элементов: головы списка и максимального элемента хвоста списка. (defun MAX_SP (l) (COND ((NULL (CDR l)) (CAR l)) (t (MAX (CAR l) (MAX_SP (CDR l)) ) ) ) ) В примере используется встроенная функция MAX, которая находит максимальный элемент из своих аргументов. В примере использовалась рекурсию по значению. Обращения к функции MAX_SP: ( MAX_SP ‘(2 7 6 1) –> 7 ( MAX_SP ‘(6 1 4 9) –> 9 Пример 6: Определим функцию APPEND_TWO от двух аргументов, работающую аналогично встроенной функции APPEND, через обращение к функции CONS . Запишем определение функции словесно: • соединить два списка – это значит соединить голову первого списка с результатом соединения хвоста первого списка и второго списка; • если первый список пуст, то результат соединения – второй список (условие остановки рекурсии). (defun APPEND_TWO (l1 l2) (COND ((NULL l1) l2) (t (CONS (CAR l1) (APPEND_TWO (CDR l1) l2) ) ) ) ) В данном случае имеем рекурсию по аргументу (обращение к APPEND_TWO является аргументом функции CONS) . Обращения к функции APPEND_TWO: (APPEND_TWO ‘(1 2 3) ‘(4 5)) –> (1 2 3 4 5) Пример 7: Определим функцию REMOVE_S, удаляющую все вхождения заданного s-выражения в список на верхнем уровне. Запишем определение функции словесно: • если s-выражение совпало с головой списка, то результат функции – хвост списка с удаленными всеми вхождениями s-выражения; • если s-выражение не совпало с головой списка, то результат функции – соединение головы списка и его хвоста с удаленными всеми вхождениями s-выражения; • если список пуст, то результат удаления – пустой список (условие остановки рекурсии). (defun REMOVE_S (x l) (COND ((NULL l) nil) ((EQUAL x (CAR l)) (REMOVE_S x (CDR l))) (t (CONS (CAR l) (REMOVE_S x (CDR l))) ) ) ) Для этой функции для разных условий предложения COND имеем рекурсию по аргументу и по значению. Обращения к функции REMOVE_S: (REMOVE_S 1 ‘(2 1 1 3)) –> (2 3) Рассмотрим работу рекурсии для рассмотренного выше обращения к функции REMOVE_S. (11) (REMOVE_S 1 ‘(2 1 1 3)  (2 3) (1) (9) (10) (CONS 2 (REMOVE_S 1 ‘(1 1 3))  (CONS 2 ‘(3))  (2 3) (2) (8) (REMOVE_S 1 ‘(1 3))  (3) (3) (7) (REMOVE_S 1 ‘(3))  (3) (4) (5) (6) (CONS 3 (REMOVE_S 1 ‘())  (CONS 3 nil)  (3) Еще одно обращение к функции REMOVE_S: (REMOVE_S ‘(a b) ‘(1 (a b) ((a b)) 3 (a b))) –> (1 ((a b)) 3) Заметим, что встроенная функция REMOVE вернула бы исходный список, т.к. в теле функции для сравнения используется функция EQ. (REMOVE ‘(a b) ‘(1 (a b) ((a b)) 3 (a b))) –> (1 (a b) ((a b)) 3 (a b)) Пример 8: Определим функцию REVERSE1, обращающую список на верхнем уровне (в mulisp имеется встроенная функция REVERSE) . Запишем определение функции словесно: • обратить список – это значит соединить обращенный хвост и голову; • если список пуст, то результат обращения – пустой список (условие остановки рекурсии). (defun REVERSE1 (l) (COND ((NULL l) nil) (t (APPEND (REVERSE1 (CDR l)) (LIST (CAR l)))) ) ) 1.10.2 Использование накапливающих параметров При работе со списками их просматривают слева направо. Но иногда более естественен просмотр справа налево. Например, обращение списка было бы легче осуществить, если бы была возможность просмотра в обратном направлении. В процедурных языках программирования для сохранения промежуточных результатов используют вспомогательные переменные. В функциональном программировании используются вспомогательные функции, у которых вспомогательные переменные являются параметрами. Пример 1: При определении функции обращения списка удобно голову списка перекладывать во вспомогательный список, который сначала пуст. Определим REVERSE2, обращающую список на верхнем уровне, через вспомогательную функцию REVERSE3 с дополнительным параметром для накапливания результата обращения списка. Запишем определение функции REVERSE3 словесно: • обратить список – это значит обратить хвост, добавив голову исходного списка во вспомогательный список; • если список пуст, то результат обращения – вспомогательный список (условие остановки рекурсии). Заметим, что на обратном ходе рекурсии ничего не выполняется. (defun REVERSE2 (l) (REVERSE3 (l nil) ) (defun REVERSE3 (l1 l2) (COND ((NULL l1) l2) (t (REVERSE3 (CDR l1) (CONS (CAR l1) l2))) ) ) Пример 2: Определим функцию COMPARE, возвращающую t, если в числовом списке положительных элементов больше, чем отрицательных. Чтобы не просматривать список два раза для подсчета положительных и отрицательных элементов, определим вспомогательную функцию COMPARE_V с двумя вспомогательными параметрами-счетчиками. Запишем определение функции COMPARE_V словесно: • если головой списка является положительный число, то сравниваем количество положительных и отрицательных элементов в хвосте, при этом увеличив на 1 первый счетчик; • если головой списка является отрицательное число, то сравниваем количество положительных и отрицательных элементов в хвосте, увеличив на 1 второй счетчик; • если головой списка является 0, то сравниваем количество положительных и отрицательных элементов в хвосте списка, не изменяя счетчиков; • если список пуст, то сравниваем накопленные значения счетчиков и возвращаем t в случае, если счетчик положительных чисел больше счетчика отрицательных чисел (условие остановки рекурсии). (defun COMPARE (l) (COMPARE_V (l 0 0) ) (defun COMPARE_V (l np no) (COND ((NULL l1) (> np no) ) ((PLUSP (CAR l)) (COMPARE_V (CDR l) (+ np 1) no)) ((MINUSP (CAR l)) (COMPARE_V (CDR l) np (+ no 1))) (t (COMPARE_V (CDR l) np no)) ) ) В данном примере имеем рекурсию по аргументам. Пример 3: Определим функцию POSITION, определяющую позицию первого вхождения s-выражения в список (на верхнем уровне), через вспомогательную функцию POSITION_V с дополнительным параметром для позиции элемента. Запишем определение функции POSITION_V словесно: • если голова списка совпадает с s-выражением, то результат работы функции – накопленный к этому моменту номер позиции головы (условие остановки рекурсии); • если голова списка не совпадает с s-выражением, то определяется позиция первого вхождения s-выражения в хвост списка, при этом значение счетчика позиций увеличивается на 1; • если список пуст, то данное s-выражение в списке отсутствует (условие остановки рекурсии). (defun POSITION (s l) (POSITION_V (s l 1) ) (defun POSITION_V (s l n) (COND ((NULL l) nil ) ((EQUAL (CAR l) s) n) (t (POSITION_V s (CDR l) (+ n 1))) ) ) В данном примере имеем рекурсию по значению. 1.10.3 Параллельная рекурсия Рекурсия называется параллельной, если рекурсивный вызов встречается одновременно в нескольких аргументах функции. Такая рекурсия встречается обычно при обработке вложенных списков. В операторном программировании параллельная рекурсия соответствует следующим друг за другом (текстуально) циклам. Пример 1: Определим функцию COPY_ALL, копирующую список на всех уровнях. Запишем определение функции словесно: • скопировать список – это значит соединить скопированную голову и скопированный хвост; • копия атома – сам атом (условие остановки рекурсии); • копия пустого списка – пустой список (условие остановки рекурсии). (defun COPY_ALL (l) (COND ((NULL l) nil ) ((ATOM l) l) (t (CONS (COPY_ALL (CAR l)) (COPY_ALL (CDR l)))) ) ) Параллельность рекурсии не временная, а текстуальная. При выполнении тела функции в глубину идет сначала левый вызов (рекурсия «в глубину»), а потом правый (рекурсия «в ширину». Пример 2: Определим функцию MEMBER_A, проверяющую принадлежность атома списку на всех уровнях. Функция возвращает t, если атом встречается в списке на любом уровне, и nil в противном случае. Запишем определение функции словесно: • атом может принадлежать либо голове списка, либо хвосту; • если аргументом функции является атом, то сравниваются два атома (условие остановки рекурсии); • если список пуст, то атом не принадлежит списку (условие остановки рекурсии). (defun MEMBER_A (x l) (COND ((ATOM l) (EQUAL x l) ((NULL l) nil ) (t (OR (MEMBER_A x (CAR l)) (MEMBER_A x (CDR l)))) ) ) Обращения к функции MEMBER_A: (MEMBER_A 1 ‘((4) ((((1) 2) 3) 4) 5)) –> t (MEMBER_A nil ‘(nil)) –> t Заметим, что в данном примере важен порядок условий выхода из рекурсии. Если поменять местами условия остановки рекурсии, то (MEMBER_A nil ‘(nil)) –> nil, т.к. (NULL nil) –>t Пример 3: Определим функцию IN_ONE, преобразующую список в одноуровневый (удаление вложенных скобок). Запишем определение функции словесно: • удалить вложенные скобки в списке – значит соединить два списка: голову исходного списка с удаленными вложенными скобками и хвост с удаленными вложенными скобками; • если аргумент функции – атом, то возвращается список из атома; • если список пуст, то все вложенные скобки удалены (условие остановки рекурсии). (defun IN_ONE (l) (COND ((NULL l) nil ) ((ATOM l) (LIST l) (t (APPEND (IN_ONE (CAR l)) (IN_ONE (CDR l)))) ) ) Обращение к функции IN_ONE: (IN_ONE ‘((4) ((((1) 2) 3) 4) 5)) –> (4 1 2 3 4 5) Пример 4: Определим функцию REVERSE_ALL, обращающую список на всех уровнях. Запишем определение функции словесно: • обратить список – значит соединить два списка: обращенный на всех уровнях хвост и обращенную на всех уровнях голову исходного списка; • если аргумент функции – атом, то возвращается атом (условие остановки рекурсии); • если список из одного элемента, то возвращается список из обращенной головы. (defun REVERSE_ALL (l) (COND ((ATOM l) l) ((NULL (CDR l)) (LIST (REVERSE_ALL (CAR l)))) (t (APPEND (REVERSE_ALL (CDR l)) (REVERSE_ALL (LIST (CAR l) )))) ) ) Обращения к функции REVERSE_ALL: (REVERSE_ALL ‘((a) (((b c) d e) f) r)) –> (r (f (e d (c b))) (a)) Пример 5: Определим функцию MAX_IN_LIST, находящую максимальный элемент в числовом списке, содержащем подсписки. Запишем определение функции словесно: • максимальный элемент в списке является максимальным из двух элементов: максимального элемента в голове списка и максимального элемента в хвосте списка; • если список из одного элемента, то ищется максимальный элемент в голове списка; • если аргумент функции – атом, то он и есть максимальный элемент (условие остановки рекурсии). (defun MAX_IN_LIST (l) (COND ((ATOM l) l) ((NULL (CDR l)) (MAX_IN_LIST (CAR l)))) (t (MAX (MAX_IN_LIST (CAR l)) (MAX_IN_LIST (CDR l)))) ) ) Обращение к функции MAX_IN_LIST: (MAX_IN_LIST ‘((2) (((1 5) 0 4) 8) 3)) –> 8 Пример 6: Определим функцию REMOVE_A, удаляющую все вхождения атома во вложенный список. Запишем определение функции словесно: • удалить атом – соединить голову, из которой удалены все вхождения атома, и хвост, из которого удалены все вхождения атома; • если список пуст, то атом удалять не надо (условие остановки рекурсии); • если голова списка – атом, то если это тот атом, который необходимо удалить, то удаляются все вхождения этого атома из хвоста списка, иначе соединяется голова и хвост со всеми удаленными вхождениями атома; (defun REMOVE_A (x l) (cond ((null l) nil) ((atom (car l)) (cond ((equal (car l) x)( REMOVE_A x (cdr l))) (t (cons (car l)( REMOVE_A x (cdr l)))) ) ) (t (append (list (REMOVE_A x (car l)))( REMOVE_A x (cdr l)))) ) ) Обращения к функции REMOVE_A: (REMOVE_A ‘a ‘((a) (b (a c)) a d)) –> (nil (b (c)) d) Пример 7: Определим функцию FIB_1, вычисляющую n-ый член последовательности Фибоначчи: f1=1, f2=1, fn=fn-1+fn-2. (defun FIB_1 (n) (cond ((OR (= n 1) (= n 2) 1) (t (+ (FIB_1 (­- n 1)) (FIB_1 (­- n 2)))) ) ) Недостатком такой рекурсии является то, что происходит дублирование вычислений. При такой организации рекурсии число вызовов растет как a∙bn-2, где a 1.8, b 1.6, хотя необходим только n-1 вызов. Напишем другой вариант рекурсивной функции FIB_2. Новая функция будет вызывать вспомогательную функцию FIB_V с двумя накапливающими параметрами – соседними членами последовательности, с помощью которых вычисляется следующий член последовательности. (defun FIB_2 (n) (FIB_V (n 1 1)) (DEFUN FIB_V (n a b) (cond ((OR (= n 1) (= n 2) b) (t (FIB_V (­- n 1) b (+ a b))) ) ) В этом случае члены последовательности вычисляются от 3-го к n-му. При вычислении n-го члена последовательности Фибоначчи функция вызывается n-1 раз. 1.10.4 Взаимная рекурсия Рекурсия называется взаимной между двумя или более функциями, если они вызывают друг друга. Пример Напишем функцию обращения списка на всех уровнях с использованием взаимной рекурсии. Функция REVRSE_V для обращения каждого подсписка использует функцию REVERSE_P, которая в свою очередь использует функцию REVERSE_V. (defun REVERSE_V (l) (COND ((ATOM l) l) (t (REVERSE_P l nil) ) ) (DEFUN REVERSE_P (l1 l2) (cond ((NULL l1) l2) (t (REVERSE_P (CDR l1) (CONS (REVERSE_V (CAR l1)) l2))) ) ) 1.10.5 Вложенные циклы Многократные повторения, соответствующие вложенным циклам в процедурных языках программирования, в функциональном программировании осуществляются с помощью нескольких функций, каждая из которых соответствует простому циклу. При этом вызов одной функции используется в качестве аргумента рекурсивного вызова другой функции. Пример Напишем функцию SORT, сортирующую числовой список по неубыванию методом вставки. Опишем ее работу: • отсортировать список – это значит добавить голову списка в нужное место отсортированного хвоста; • пустой список упорядочен (условие окончания рекурсии). Для добавления элемента в отсортированный по неубыванию список напишем функцию ADD, работающую следующим образом: • если добавляемый элемент не больше головы списка, то добавляем элемент перед головой (условие окончания рекурсии); • если добавляемый элемент меньше головы списка, то добавляем его в нужное место хвоста; • если список пустой, то результат добавления – список из добавляемого элемента (условие окончания рекурсии). (defun SORT (l) (COND ((NULL l) l) (t (ADD (CAR l) (SORT (CDR l)))) ) ) (DEFUN ADD (x l) (cond ((NULL l) (LIST x)) ((<= x (CAR l)) (CONS x l)) (t (CONS (CAR l) (ADD x (CDR l)))) )) 1.11. Внутреннее представление s-выражений Каждому атому в программе ставится в соответствие ячейка памяти, называемая информационной ячейкой атома. Сам атом заменяется во внутреннем представлении выражений адресом его информационной ячейки. Через информационную ячейку можно получить доступ к списку свойств атома. Среди прочих свойств в этом списке содержится как внешнее представление этого атома (последовательность символов, представляющая его в программе), так и указатель на его значение. Например, побочным эффектом функции работы SETQ является замещение указателя в поле значений символа. Оперативная память, с которой работает интерпретатор Лиспа, логически разбивается на области – списочные ячейки. Списочная ячейка состоит из двух полей, каждое из которых содержит указатель. Указатель может ссылаться на другую списочную ячейку или на объект Лиспа. Графически списочную ячейку можно представить в следующем виде: Рисунок 3 – Списочная ячейка Список представляется последовательностью списочных ячеек, связанных через указатели в правой части. Правое поле последней списочной ячейки ссылается на пустой список, т.е. атом nil. Графически ссылку на пустой список изображают в виде перечеркнутого поля. Указатели из левых ячеек ссылаются на структуры, являющиеся элементами списка. Пример: Рассмотрим побочный эффект работы функции (SETQ ‘x ‘(a b c)). Этот эффект – создание штриховой стрелки на рисунке. Рисунок 4 – Побочный эффект функции SETQ В графическом представлении становится понятна работа функций CAR, CDR и CONS. Функция CAR возвращает значение левой списочной ячейки (в примере это указатель на атом а), а функция CDR – значение правой списочной ячейки (в примере это указатель на список (b c)). Функция CONS создает новую списочную ячейку, содержимое левого поля которого – это указатель на первый аргумент функции, а содержимое правого поля – это указатель на второй аргумент функции. Таким образом, новая списочная ячейка связывает две существующие структуры в одну новую структуру. Это довольно эффективное решение с точки зрения создания новых структур и их представления в памяти. Заметим, что применение функции CONS не изменяет структур аргументов функции. Пример: Рассмотрим последовательность вызовов: (SETQ ‘x ‘(b c))  (b с), побочный эффект – связывание: x  (b с); (SETQ ‘y ‘(a b c))  (a b с), побочный эффект – связывание: y  (a b с); (SETQ ‘z (CONS x y))  ((b с) a b c), побочный эффект – связывание: z  ((b с) a b c). Структуру, связанную с переменной z, можно представить графически: Рисунок 5 – Созданная в примере структура Из рисунка видно, что логически идентичные атомы содержатся в системе один раз. Однако, логически идентичные списки могут быть представлены различными списочными ячейками. Например, для созданной выше структуры имеем: (CAR z)  (b c); (CDDR z)  (b c). Рисунок 6 – Работа функций (CAR z) и (CDDR z) Полученные списки логически идентичны, а физические адреса для них будут разные, поэтому (EQUAL (CAR z) (CDDR z))  t; (EQ (CAR z) (CDDR z))  nil. Список ((b с) a b c) можно было создать другим способом: (SETQ ‘x ‘(b c))  (b с), побочный эффект – связывание: x  (b с); (SETQ ‘y (CONS ‘a x))  (a b с), побочный эффект – связывание: y  (a b с); (SETQ ‘z1 (CONS x y))  ((b с) a b c), побочный эффект – связывание: z1  ((b с) a b c). Структуру, связанную с переменной z1, можно представить графически: Рисунок 7 - Созданная структура z1 Тогда, (EQUAL (CAR z1) (CDDR z1))  t; (EQ (CAR z1) (CDDR z1))  t. В результате вычислений в памяти могут возникнуть структуры, на которые нельзя сослаться. Такие структуры называются мусором. Образование мусора происходит в тех случаях, когда вычисленная струтура не сохраняется с помощью SETQ или когда теряется ссылка на старое значение в результате побочного эффекта нового вызова SETQ или другой функции. Примеры: 1. Представим графически структуру, созданную следующей функцией: (SETQ spis ‘((a b) c d))  ((a b) c d), побочный эффект – связывание: spis  ((a b) c d). Рисунок 8 - Созданная структура spis После присваивания нового значения переменной spis побочным эффектом функции (SETQ spis (CDR spis))  (с d), побочный эффект – связывание: spis  (с d), уже нельзя будет “добраться” до двух списочных ячеек. Они стали мусором. 2. Значение вызова (CONS a (LIST b)) лишь выводится на экран дисплея, после чего созданная им в памяти структура станет мусором. Для повторного использования ставшей мусором памяти в Лиспе предусмотрен специальный сборщик мусора, который автоматически запускается, когда в памяти остается мало свободного места. Сборщик мусора перебирает все ячейки и собирает являющиеся мусором ячейки в список свободной памяти для того, чтобы их можно было использовать заново. Все рассмотренные до сих пор функции манипулировали выражениями, не вызывая каких-либо изменений в уже существующих структурах. Значения переменных можно было изменить лишь целиком. Единственное, что могло произойти со старым значением – это лишь то, что оно могло пропасть. В Лиспе имеются специальные функции, которые изменяют внутреннюю структуру списков. Такие функции называются структуроразрушающими. В чисто функциональном программировании такие функции не используются. В практическом программировании функции, изменяющие структуры, иногда используют. Например, если нужно сделать небольшие изменения в большой структуре данных. С помощью структуроразрушающих функций можно эффективно менять за один раз несколько структур, если у этих структур есть совмещенные в памяти подструктуры. Но такие изменения могут привести к сюрпризам в тех частях программы, которые не знают об изменениях, что осложняет написание программ и их документирование. Обычно использование структуроразрушающих функций стараются избегать. 1.12 Точечная пара При определении функции CONS, предполагалось, что ее второй аргумент должен быть списком. На самом деле, если второй аргумент атом, результатом работы функции будет так называемая точечная пара, левым элементом которой является первый аргумент функции, а правым – второй аргумент. Пример: (CONS ‘a ‘b)  (a .b). Графически созданную структуру можно представить следующим образом: Рисунок 9 - Точечная пара Тогда функция CAR от точечной пары будет возвращать выражение, стоящее слева от точки, а поле CDR – выражение справа от точки. Точечная нотация позволяет расширить класс объектов Лиспа. Ситуацию можно сравнить с добавлением класса комплексных чисел к имеющемуся классу действительных чисел в математическом анализе. Любой список можно представить в точечной нотации. Преобразования можно осуществить следующим образом: (a1 a2 an)  (a1 . (a2 .  (an . nil)  )). Таким образом, каждый пробел заменяется точкой, за которой ставится открывающаяся скобка. Соответствующая закрывающаяся скобка ставится непосредственно перед ближайшей справа от этого пробела закрывающейся скобкой, не имеющей парной открывающей скобки также справа от пробела. После каждого последнего элемента списка добавляется .nil. Пример: (a b (c d) e)  (a . (b . ((c .(d . nil)) . (e . nil)))). Транслятор может привести записанное в точечной нотации выражение частично или полностью к списочной нотации. Полностью преобразование можно осуществить только тогда, когда правый элемент каждой точечной пары является списком или точечной парой. Переход к списочной записи осуществляется по следующему правилу: если точка стоит перед открывающейся скобкой, то она заменяется пробелом и одновременно убирается соответствующая закрывающаяся скобка. Это же правило позволяет избавиться и от лишних nil, если помнить, что nil эквивалентен (). Примеры: 1. ‘(a . ((b . nil) . (c . nil)))  (a (b) c); 2. ‘(a . (b . c))  (a b . c); 3. ‘((a . b) . (c . d))  ((a .b) c . d); 4. ‘(nil . (a . b))  (nil a . b). Точечная запись списков обладает некоторыми преимуществами по сравнению со списочной записью. Она является более общей, т.к. любой список можно переписать в точечных обозначениях, но уже простейшее точечное выражение (a . b) не может быть представлено списочной записью. Использование точечных пар позволяет сократить объем необходимой памяти. Например, структура данных (a b c), записанная в виде списка требует трех ячеек, тогда как представление тех же данных в виде (a b . c) требует только двух ячеек. Более компактное представление может сократить и объем вычислений за счет меньшего количества обращений к памяти. Когда выражение строится из небольшого заранее известного количества элементов, точечные конструкции предпочтительнее списков. Если же число элементов велико и может изменяться, то целесообразнее использовать списочные конструкции. Точечные пары применяются в теории, книгах и справочниках по Лиспу, системном программировании. Большинство программистов не используют точечные пары, поскольку по сравнению с требуемой в таком случае внимательностью получаемый выигрыш в объеме памяти и скорости вычислений не заметен. 1.13 Функционалы До сих пор во всех примерах аргументами функций были данные, представленные s-выражениями. Однако в Лиспе функции могут выступать в качестве аргументов, точнее аргументом функции может быть определяющее функцию лямбда-выражение или имя другой функции. Такой аргумент называется функциональным, а функция, имеющая функциональный аргумент, называется функционалом. 1.13.1 Аппликативные (применяющие функционалы) Применяющим функционалом называется функционал, который применяет функциональный аргумент к остальным параметрам. Применяющие функционалы похожи на функцию EVAL, которая вычисляет значение произвольной формы. Применяющий функционал вычисляет значение вызова функционального аргумента. В Лиспе имеется два встроенных применяющих функционала: APPLY и FUNCALL. Функционал APPLY является функцией двух аргументов: функционального аргумента и списка данных. Этот функционал вычисляет значение функционального аргумента (функции от n переменных) для фактических параметров, которые являются элементами списка. Вызов функционала имеет вид: (APPLY fn sp), где fn – имя функции или лямбда-выражение, sp – список. Примеры: 1. (APPLY ‘+ ‘(1 2 3)) (+ 1 2 3) 6; 2. (APPLY ‘(LAMBDA (x y z) (+ x y z)) ‘(1 2 3)) (+ 1 2 3) 6; 3. (APPLY ‘CONS ‘(a (b c))) (CONS ‘a ‘(b c)) (a b c). При использовании функционала наблюдается большая гибкость, чем при вызове обычной функции. В зависимости от значения функционального аргумента можно осуществлять различные вычисления над одними и теми же данными. Пример 1: Напишем функциональный предикат ALL, который возвращает t в том и только в том случае, если функциональный аргумент истинен для каждого элемента списка. (DEFUN ALL (p l) (COND ((NULL l) t) ((APPLY p (LIST (CAR l))) (ALL p (CDR l))) (t nil) ) ) Рассмотрим примеры работы функционала ALL. (ALL ‘atom ‘((1 2) 3 4))  nil; (ALL ‘atom ‘(1 2 3 4))  t; (ALL ‘plusp‘(1 2 3 4))  t; (ALL ‘(LAMBDA (x) (<= x 0)) ‘(-1-3 -4))  t. Пример 2: Напишем функционал FUNC_LIST, который имеет два аргумента-списка: список из функциональных аргументов и списка данных. Этот функционал возвращает список из результатов применения каждого элемента списка функциональных аргументов к соответствующему элементу списка данных. (DEFUN FUNC_LIST (f l) (COND ((NULL f) nil) (t (CONS (APPLY (CAR f) (LIST (CAR l))) (FUNC_LIST (CDR f) (CDR l)))) ) ) Рассмотрим пример работы функционала FUNC_LIST. (FUNC_LIST ‘(atom symbolp numberp) ‘(a 1 name))  (t nil nil). Функционал FUNCALL является функцией не менее двух аргументов: функционального аргумента и данных. Этот функционал работает аналогично APPLY, но аргументы функционального аргумента (функции от n переменных) задаются не списком, а как аргументы FUNCALL, начиная со второго. Вызов функционала имеет вид: (FUNCALL fn a1 a2 … an), где fn – имя функции или лямбда-выражение, ai (i = 1,…,n)– значение i-го аргумента для fn. Примеры: 1. (FUNCALL ‘+ 1 2 3) (+ 1 2 3) 6; 2. (FUNCALL ‘(LAMBDA (x y) (+ x y)) 1 2) (+ 1 2) 6; 3. (FUNCALL ‘LIST ‘(a b)) (LIST ‘(a b)) ((a b)). Заметим, что если в последнем примере заменить FUNCALL на APPLY, то получим: (APPLY ‘LIST ‘(a b)) (LIST a b) (a b) Пример 3: Напишем функционал FUNC_LIST1, работающий аналогично функционалу FUNC_LIST из примера2 с использованием применяющего функционала FUNCALL. (DEFUN FUNC_LIST1 (f l) (COND ((NULL f) nil) (t (CONS (FUNСALL (CAR f) (CAR l)) (FUNC_LIST1 (CDR f) (CDR l)))) ) ) ) Рассмотрим пример работы функционала FUNC_LIST1. (FUNC_LIST1 ‘(atom car) ‘(nil (1 2)))  (t 1). Пример 4: Переделаем написанную ранее в п.1.10.5 функцию сортировки числового списка в функционал, у которого функциональный аргумент будет задавать порядок сортировки. (defun SORT1 (l p) (COND ((NULL l) l) (t (ADD_ORD (CAR l) (SORT1 (CDR l) p) p)) ) ) (DEFUN ADD_ORD (x l p) (cond ((NULL l) (LIST x)) ((FUNCALL p x (CAR l)) (CONS x l)) (t (CONS (CAR l) (ADD_ORD x (CDR l) p))) ) ) Рассмотрим примеры работы функционала SORT1. (SORT1 ‘(5 1 3 2 4) ‘<)  (1 2 3 4 5). (SORT1 ‘(5 1 3 1 2 4 2) ‘(LAMBDA (x y) (>= x y)))  (5 4 3 2 2 1 1). (SORT1 ‘(b a d c s) ‘(LAMBDA (x y) (CHAR< x y)))  (a b c d s). (SORT1 ‘(ab sc aefg srt) ‘string>)  (srt sc aefd ab). 1.13.2 Отображающие функционалы или MAP-функции Отображающие функционалы с помощью функционального аргумента преобразуют список в новый список или порождают побочный эффект, связанный с этим списком. Такие функционалы начинаются на MAP. В Лиспе имеются встроенные отображающие функционалы MAPCAR и MAPLIST. Функционал MAPCAR является функцией не менее двух аргументов: функционального аргумента и списков данных. Этот функционал возвращает список, состоящий из результатов последовательного применения функционального аргумента (функции n переменных) к соответствующим элементам n списков. Число аргументов-списков должно быть равно числу аргументов функционального аргумента. Вызов функционала имеет вид: (MAPCAR fn sp1 sp2 … spn), где fn – имя функции или лямбда-выражение, spi – список (i = 1,…,n). Примеры: 1. (MAPCAR ‘atom ‘(a b c))  ((ATOM a) (ATOM b) (ATOM c))  (t t t); 2. (MAPCAR ‘(LAMBDA (y) (LIST y))) ‘(a b c))   ((LIST a) (LIST b) (LIST c))  ((a) (b) (c)); 3. (MAPCAR ‘(LAMBDA (x) (LIST x ‘*)) ‘(a b c))   ((LIST a ‘*) (LIST b ‘*) (LIST c ‘*))  ((a *) (b *) (c *)); 4. (MAPCAR ‘+ ‘(1 2) ‘(2 3) ‘(3 4))  (6 9); 5. (MAPCAR ‘cons ‘(a b c) ‘((1) (2) (3)))  ((a 1) (b 2) (c 3)). Как правило, MAP-функция применяется к одному аргументу-списку, т.е. функциональный аргумент является функцией одной переменной. Использование MAP-функций используется при программировании специальных циклов, поскольку с их помощью можно сократить запись повторяющихся вычислений. Пример 1 Напишем функцию SUM3, вычисляющую сумму кубов элементов списка. (DEFUN SUM3 (l) (EVAL (CONS ‘+ (MAPCAR ‘* l l l)))) Рассмотрим пример работы функции SUM3. (SUM3 ‘(1 2 3))  36. Пример 2 Напишем функцию DECART, вычисляющую декартово произведение двух множеств, через композицию двух вложенных вызовов функционала MAPCAR. (DEFUN DECART (l1 l2) (MAPCAR ‘(LAMBDA (x) (MAPCAR ‘(LAMBDA (y) (LIST x y)) l2)) l1)) Рассмотрим пример работы функции DECART. (DECART ‘(1 2 3) ‘(a b))  (((1 a) (1 b)) ((2 a) (2 b)) ((3 a) (3 b))). Отображающий функционал MAPLIST действует подобно MAPCAR, но действия осуществляются не над элементами списков, а над последовательными хвостами этих списков, начиная с самих списков. Вызов функционала имеет вид: (MAPLIST fn sp1 sp2 … spn), где fn – имя функции или лямбда-выражение, spi – список (i = 1,…,n). Примеры: 1. (MAPLIST ‘reverse ‘(a b c))  ((c b a) (c b) (c)); 2. (MAPLIST ‘(LAMBDA (x) x) ‘(a b c))  ((a b c) (b c) c); 3. (MAPLIST ‘append ‘(a b) ‘(1 2))  ((a b 1 2) (b 2)). Среди отображающих функционалов выделяют объединяющие функционалы MAPCAN и MAPCON. Работа их аналогична соответственно MAPCAR и MAPLIST. Различие заключается в способе построения результирующего списка. Если функционалы MAPCAR и MAPLIST строят новый список из результатов применения функционального аргумента с помощью функции LIST, то функционалы MAPCAN и MAPCON для построения нового списка используют структуроразрушающую псевдофункцию NCONC, соединяющую списки физически. Функция NCONC делает то же самое, что и APPEND с той лишь разницей, что NCONC изменяет указатель в поле CDR последней ячейки списка – первого аргумента на начало списка – второго аргумента. Для того, чтобы функционалы могли применить функцию NCONC, их функциональные аргументы должны возвращать списки. Функционалы MAPCAN и MAPCON удобно использовать в качестве фильтров для удаления нежелательных элементов из списка. Вызов функционала MAPCAN имеет вид: (MAPCAN fn sp1 sp2 … spn), где fn – имя функции или лямбда-выражение, spi – список (i = 1,…,n). Пример: Удаление из числового списка всех элементов, кроме отрицательных. (MAPCAN ‘(LAMBDA (x) (COND ((MINUSP x) (LIST x)) (t nil) )) ‘(-3 1 4 -5 0))  (-3 -5) Заметим, что использование MAPCAR не привело бы к такому результату, т.к. (APPEND ‘(1) nil)  (1), а (LIST 1 nil)  (1 nil). Вызов функционала MAPCON имеет вид: (MAPCON fn sp1 sp2 … spn), где fn – имя функции или лямбда-выражение, spi – список (i = 1,…,n). Примеры: 1. (MAPCON ‘reverse (1 2 3))  (3 2 1 3 2 3). 2. Преобразование одноуровнего списка в множество: (MAPCON ‘(LAMBDA (l) (COND ((MEMBER (CAR l) (CDR l)) nil) (t (LIST (CAR l))) )) ‘(1 2 3 1 1 4 2 3))  (1 4 2 3) Отметим, что функционал MAPCON может легко «зацикливать» списки, поэтому использовать его нужно осторожно. 1.14. Вопросы и задания для самоконтроля 1) Что является атомом в Лиспе? 2) Определить значение выражений: a) '(+ '2 (* 3 4)) b) (+ 2 '(* 3 4)) c) (+ 2 ('* 3 4)) d) (* 2 (* 3 '4)) e) (QUOTE ' QUOTE) 3) Сколько элементов на верхнем уровне содержит списки: a) (((1 f)) (a) x); b) ((((h 7 6)))); c) (); d) (nil)? 4) Определите результаты работы функции CONS: a) (CONS '(a b) '(c d)); b) (CONS (+ 1 2) '(+ 4 6)); c) (CONS '(+ 1 2) (+ 4 6)); d) (CONS '(a (b c)) nil). 5) Напишите сложную функцию, используя композицию из функций CAR и CDR, которая возвращает: a) 3, если она применяется к списку (((4 (6 3)) 8) 7); b) 6, если она применяется к списку (1 (((2 3) (4 5) 6) (7))); c) 12, если она применяется к списку ((5 ((12) 23 34))). 6) Что называется предикатом? 7) Какие значения возвращают следующие функции: a) (atom (car '(() 3 4))); b) (equal '(a b) (cons '(a) '(b))); c) (null (cadr '((1 2) (3 4)))); d) (numberp (cAr '(1 2))); e) (listp (last '(1 2 (3 4) a))). 8) В чем состоит отличие псевдофункции SET от SETQ? 9) Для чего используется функция EVAL? 10) Определите лямбда вызов для вычисления следующих выражений (при x=2, y=4): a) X * Y - X – Y b) X * X - 2 * X * Y + Y * Y 11) Как в ЛИСПе осуществляется работа с файлами? 12) Для чего используются предложения PROG и PROGN? 13) Какая функция используется для разветвления вычислений? 14) Какие виды рекурсии можно использовать в ЛИСПе? 15) Объясните, что возвращают встроенные функции MEMBER, REMOVE, REVERSE? 16) Как организовать вложенный цикл с использованием рекурсии? 17) Почему логически идентичные списки могут иметь разные адреса? 18) Чем отличается точечная пара от списка? 19) Как осуществить преобразование списка к точечной паре и наоборот? 20) Какие функции называются функционалами? 21) Какой функционал называется аппликативным? 22) Какой функционал называется отображающим? Глава 2 Логическое программирование. Основы языка Пролог Логическое программирование базируется на убеждении, что не человека следует обучать мышлению в терминах операций компьютера, а компьютер должен выполнять инструкции, свойственные человеку. В чистом виде логическое программирование предполагает, что инструкции даже не задаются, а сведения о задаче формулируются в виде логических аксиом. Такое множество аксиом является альтернативой обычной программе. Подобная программа может выполняться при постановке задачи, формализованной в виде логического утверждения, подлежащего доказательству (целевого утверждения). Идея использования логики исчисления предикатов I порядка в качестве основы языка программирования возникла в 60-е годы, когда создавались многочисленные системы автоматического доказательства теорем и вопросно-ответные системы. В 1965 г. Робинсон предложил принцип резолюции, который в настоящее время лежит в основе большинства систем поиска логического вывода. Метод резолюций был использован в системе GPS (general problem solver). В нашей стране была разработана система ПРИЗ, которая может доказать любую теорему из школьного учебника геометрии. Язык программирования PROLOG (programming in logic) был разработан и впервые реализован в 1972 г. группой сотрудников Марсельского университета во главе с Колмероэ. Группа занималась проблемой автоматического перевода с одного языка на другой. Основа этого языка - исчисления предикатов I порядка и метод резолюций. Суть Пролога – программирование в терминах целей. Программист описывает условие задачи, пользуясь понятиями объектов различных типов и отношений между ними, и формулирует вопрос. PROLOG-система обеспечивает ответ на вопрос, находя автоматически последовательность вычисления решения, используя встроенную процедуру поиска. До 1981 г. число исследователей, занимавшихся логическим программированием, составляло около сотни во всем мире. В 1981 году PROLOG был выбран в качестве базового языка компьютеров пятого поколения, и количество исследователей логического программирования резко возросло. Одной из наиболее интересных тем исследований является связь логического программирования с параллелизмом. Где же используется Пролог в настоящее время? Это область автоматического доказательства теорем, построение экспертных систем, машинные игры с эвристиками (например, шахматы), автоматический перевод с одного языка на другой. В настоящее время создано достаточно много реализаций языка Пролог: Wisdom Prolog, Micro Prolog, Turbo Prolog, PDS-Prolog, Arity Prolog и т.д. Файлы, содержащие программы, написанные на языке Prolog, имеют расширение pro. В нашем курсе будут использоваться Turbo Prolog. Эта система является компилятором (все остальные – интерпретаторы). У нее имеется оболочка, состоящая из четырех окон и меню, предусмотрена строгая типизация данных. В нижней части оболочки имеется строка, в которой указаны подсказки о назначении функциональных клавиш. Для запуска системы Turbo Prolog необходимо запустить файл prolog.exe. Опишем горячие клавиши при работе с системой Turbo Prolog (знак «+» означает одновременное нажатие клавиш): F2 – сохранение файла, если он уже сохранялся под каким-нибудь именем; F3 – загрузка файла; ALT+R – запуск программы; ALT+E – переход в окно редактора; F5 – развернуть окно на весь экран или свернуть до первоначальных размеров; F6 – переход между окнами; F10 – переход в верхнее меню; ALT+T – включение или выключение трассировки; F8 – повтор ранее введенной цели при запуске программы без раздела goal; ALT+X – выход из Пролога. Команды при работе в окне редактора: CTRL+Y – удаление строки; F5 – нахождение и замена указанного текста; CTRL+K,B – начало выделения блока; CTRL+K,K – конец выделения блока; CTRL+K,C – копирование выделенного блока в место, указанное курсором; CTRL+K,V – перемещение выделенного блока в место, указанное курсором; CTRL+K,Y – удаление выделенного блока; CTRL+K,H –отмена выделения блока; Блочные операции можно выполнить с использованием функциональных клавиш: CTRL+F5 – начало выделения блока, конец выделения блока, копирование выделенного блока в место, указанное курсором (для выполнения операции копирования полностью данную комбинацию клавиш следует нажать 3 раза); SHIFT+F9 – повторная вставка скопированного выделенного блока в место, указанное курсором; ALT+F5 – начало выделения блока, конец выделения блока и копирование его в другой файл (для выполнения операции копирования полностью данную комбинацию клавиш следует нажать 2 раза); ALT+F6 – начало выделения блока, конец выделения блока и перемещение его в место, указанное курсором (для выполнения операции перемещения полностью данную комбинацию клавиш следует нажать 3 раза); ALT+F7 – начало выделения блока, конец выделения блока и удаление его (для выполнения операции удаления данную комбинацию клавиш следует нажать 2 раза); ESC ­­– отмена выделения. 2.1 Факты и правила Как уже отмечалось Пролог использует исчисление предикатов первого порядка. Предикаты определяют отношения между объектами. Рассмотрим дерево родственных отношений: Рисунок 10 - Дерево родственных отношений Пример 1: Это дерево можно описать следующей Пролог-программой. predicates родитель(symbol, symbol) clauses родитель(пам, боб). родитель(том, боб). родитель(том, лиз). родитель(боб, энн). родитель(боб, пат). родитель(пат, джим). Раздел predicates описывает отношения между объектами (имя отношения, его арность и типы объектов). У нас имеется отношение родитель между двумя объектами символьного типа. В разделе clauses описаны 6 фактов наличия отношений между конкретными объектами. Имена объектов начинаются с маленьких букв (они являются константами). В Прологе принято соглашение, что константы начинаются с маленькой буквы, а переменные – с большой. После ввода такой Пролог-программы можно запустить программу на выполнение (ALT+R) и в специальном окне диалога после слова «Цель:» задавать вопросы, касающиеся отношения родитель. Вопросы могут быть простые и сложные (в качестве связки «и» при составлении сложного вопроса используется запятая). Ответы Пролог-системы выводятся сразу после вопроса. При этом могут быть следующие варианты ответов: • Да; • Не (соответствует нет); • Не решен (не найдены значения переменных в вопросе); • Перечисляются все возможные значения переменных в вопросе и указывается количество найденных решений. Вопрос относительно отношения родитель Вопрос в Пролог-системе Ответ Пролог-системы Боб является родителем Пат? родитель(боб,пат) Да Пат – ребенок Лиз? родитель(лиз,пат) Не Кто родители Лиз? родитель(X,лиз) X=том 1 решен. s Кто дети Пат? родитель(пат, X) Не решен. Кто дети Боба? родитель(боб,X) X=энн X=пат 2 решен. s Есть ли дети у Тома? родитель(том,_) Не Кто чей родитель? родитель(X,Y) X=пам, Y=боб X=том, Y=боб X=том, Y=лиз X=боб, Y=энн X=боб, Y=пат X=пат, Y=джим 6 решен. s Кто внуки Тома? родитель(том,X), родитель(X,Y) X=боб, Y=энн X=боб, Y=пат 2 решен. s Кто родители родителей Джима? родитель(X,джим), родитель(Y,X) X=пат, Y=боб 1 решен. s Итак, в простейшем случае Пролог-программа состоит из двух разделов: раздела описания предикатов predicates и раздела clauses. В разделе clauses могут описываться факты и правила. Факт – это безусловное утверждение (всегда истинное), характеризующее объект с некоторой стороны или устанавливающее отношение между несколькими объектами. Факт не требует доказательств. Факт имеет следующий вид: <имя предиката>(O1,O2,…,On). Обратим внимание на то, что в конце факта ставится точка. <имя предиката> должно начинаться со строчной буквы и может содержать буквы, цифры, знаки подчеркивания. Оi (i = 1,..,n) - аргументы предиката могут быть конкретными объектами (константами) или абстрактными объектами (переменными). Если конкретные объекты начинаются с буквы, то эта буква должна быть строчной. Переменные начинаются с прописной буквы или символа подчеркивания. Выделяют особую переменную – анонимную переменную (без имени), которая обозначается символом подчеркивания, значение этой переменной пользователю не сообщается. Правило – утверждение, которое истинно при выполнении некоторых условий. Правило состоит из условной части (тела) и части вывода (головы). Головой правила является предикат, истинность которого следует установить. Тело правила состоит из одного или нескольких предикатов, связанных логическими связками: конъюнкция (обозначается запятой), дизъюнкция (обозначается точкой с запятой) и отрицание (означается not). Правило имеет следующий вид: <голова правила > :–­­­­ <тело правила>. или <голова правила > if <тело правила>. В конце правила так же ставится точка. Можно считать, что факт – это правило, имеющее пустое тело. С помощью правил можно описывать новые отношения. Пример 2: Пусть имеется двуместное отношение родитель и одноместное отношение мужчина. Эти отношения описываются в виде фактов. Опишем новое двуместное отношение дед, используя правила. X является дедом Y, если существует цепочка: X– родитель Z, Z – родитель Y, при этом X должен быть мужчиной. дед(X,Y):–­­­­родитель(X,Z),родитель(Z,Y),мужчина(X). Пример 3: Пусть имеется двуместное отношение родитель, описанное в виде фактов. Опишем новое двуместное отношение предок, используя правила. X является предком Y, если X – родитель Y или существует цепочка людей между Х и Y, связанных отношением родитель. предок(X,Y):–­­­­родитель(X,Y). предок(X,Y):–­­­­родитель(X,Z),предок(Z,Y). Эти правила можно записать по-другому: предок(X,Y):–­­­­родитель(X,Y);­­­ родитель(X,Z),предок(Z,Y). В данном примере получили рекурсивное определение отношения предок. Пример 4 Определим двуместное отношение дальний_родственник с помощью правила, используя имеющееся отношение предок. X является дальним родственником Y, если они связаны отношением предок, но при этом не связаны отношением родитель. дальний_родственник (X,Y):–­­­предок(X,Y),not(родитель(X,Y));­­­ предок(Y,X),not(родитель(Y,X)). В правой части правила можно использовать знаки = и <> для проверки числовых или строковых значений переменных на равенство и неравенство, знаки < и > для сравнения значений. 2.2 Поиск решений Пролог-системой Вопрос к системе – это всегда последовательность, состоящая из одной или нескольких целей. Для ответа на поставленный вопрос Пролог-система должна достичь всех целей, т.е. показать, что утверждения вопроса истинны в предположении, что все отношения программы истинны. Если в вопросе имеются переменные, то система должна найти конкретные объекты, которые, будучи подставлены вместо переменных, обеспечат достижение цели. Если система не в состоянии вывести цель из имеющихся фактов и правил, то ответ должен быть отрицательный. Таким образом, факты и правила в программе соответствуют аксиомам, а вопрос – теореме. При поиске ответа на поставленный вопрос Пролог-система находит факт или правило для содержащегося в вопросе предиката и выполняет операцию сопоставления (унификации) объектов предиката. При этом возможны следующие случаи успешного сопоставления: • сопоставляются две одинаковые константы; • сопоставляется неозначенная переменная с константой (при этом переменная получает значение, равное константе); • сопоставляется означенная переменная с константой, равной значению переменной; • сопоставляется неозначенная переменная с другой неозначенной переменной (при этом переменная цели получает имя переменной предиката). После успешного сопоставления все переменные получают значения и становятся связанными, а предикат считается успешно выполненным (если сопоставление выполнялось с фактом) или заменяется на тело правила (если сопоставление выполнялось с головой правила). Связанные переменные освобождаются, если цель достигнута или сопоставление неуспешно. Процесс сопоставления похож на использование оператора «=». Интерпретация этого оператора Прологом зависит от того, известны ли оба значения, связанные этим оператором или только одно из них. Если оба значения известны, то оператор интерпретируется как оператор сравнения. Если известно только одно значение, то оператор интерпретируется как присваивание, причем присваивание может выполняться как слева направо, так и справа налево в зависимости от того, слева или справа от оператора находится известное значение. Для достижения целей Пролог использует механизм отката. При вычислении цели выполняется сопоставление с фактами и головами правил. Сопоставления выполняются слева направо. Возможно, некоторые подцели будут неуспешны при сопоставлении с некоторыми фактами или правилами, поэтому Пролог должен запоминать «точки», в которых он может поискать альтернативные пути решения. Если цель была неуспешной, то выполняется откат влево к ближайшему указателю отката и выполняется новая попытка достичь цели. Этот откат будет повторяться, пока цель не будет достигнута или исчерпаются все указатели отката. Если все цели были достигнуты, но использовались не все указатели отката, то будет продолжен поиск других решений. Пример: Рассмотрим работу Пролог-системы при вопросе: предок(том,энн). Сначала выполняется сопоставление цели и головы первого правила, сопоставление успешно и переменные X и Y становятся связанными (X получает значение том, а Y – значение энн). При этом Пролог-система запоминает, что имеется второе правило, по которому можно будет продолжить поиск решения. Далее начинает выполняться тело первого правила (новая цель родитель(том,энн)). Опять выполняются все возможные сопоставления с фактами предиката родитель. Сопоставление неуспешно, все связи разорваны. Далее происходит возврат для сопоставления цели и головы второго правила. Сопоставление успешно и переменные X и Y становятся связанными (X получает значение том, а Y – значение энн). Далее начинает выполняться тело второго правила (новая цель родитель(том,Z)). В нем имеется две цели, их достижение проверяется по порядку. Первая цель успешна, т.к. сопоставляется с фактом родитель(том,боб), при этом Z получает значение боб. Новая цель - предок(боб,энн). Опять выполняется составление цели и головы первого правила. Оно успешно, при этом X получает значение боб, а Y – значение энн. Новая цель – правая часть первого правила родитель(боб,энн) успешна. Следовательно, цель успешна и ответ Пролог-системы: да. Представим шаги вычислений графически. Рисунок 11 - Поиск решений Существует два способа просмотреть в окне трассировки, как Пролог-система ищет решения: 1. Включить опцию трассировки всех предикатов, выполнив команды Options - Compiler directives – Trace – Trace. 2. В начале программы ввести директиву компилятору: trace или trace , ,…, где pi (i = 1,…,k) – имена предикатов, которые будут трассироваться (в первом случае будут трассироваться все предикаты). После запуска программы продолжить пошаговое выполнение программы можно клавишей F10. В окне трассировки могут появиться следующие слова: • CALL Далее указывается текущая цель: имя предиката и значения его аргументов. • REDO Возврат в отмеченную точку возврата . • RETURN Указывается подцель, которая успешна. После RETURN стоит «*», если остались неиспользованные указатели откатов. • FAIL Цель не была достигнута. 2.3 Структура программы Турбо-Пролога Программа на Прологе в общем случае имеет следующую структуру: <директивы компилятору> domains <описание доменов> database <описание предикатов динамической базы данных> predicates <описание предикатов> goal <предложение, описывающее внутреннюю цель программы> /*В конце предложения всегда ставится точка*/ clauses <факты и правила> Программа может не содержать всех вышеперечисленных разделов. Комментарии в программе обрамляются символами /* и */, как это показано при описании структуры программы. 2.3.1 Описание доменов и предикатов, объекты данных Раздел domains описывает новые типы данных. Имя домена должно начинаться с маленькой буквы. Турбо–Пролог имеет 6 стандартных доменов (типов данных), которые описывать не нужно: • символы (char). При использовании данных такого домена каждый символ заключается апострофы; • целые числа (integer). Диапазон значений данных от -32768 до 32767; • действительные числа (real). Диапазон значений данных от 10-307 до 10308; • строки (string). Данные такого домена - последовательность символов (не более 250), заключенная в кавычки или последовательность букв, цифр и подчерков, начинающаяся со строчной буквы; • символические имена (symbol). Данные такого домена совпадают с данными string. Отличие будет заключаться в способе хранения данных. Данные типа symbol запоминаются в специальной таблице символов, которая размещается в оперативной памяти и, поэтому, обеспечивает более быстрый поиск. Однако, для построения такой таблицы требуется дополнительное время. • файлы (file). Значением данных этого домена может быть любое допустимое имя файла. Стандартные домены не описываются. Домены, объявленные пользователем, делают предикаты нагляднее, т.к. поясняют смысл предикатов. Описание n-местного предиката имеет вид: <имя предиката>(<домен1>,<домен2>,..,<доменn>), где домен1, домен2,..,доменn – имена доменов (стандартных или определенных программистом) для объектов описанного отношения. Пример 1: Рассмотрим два способа описания одного и того же предиката – наличие в библиотеке определенной книги. 1-ый способ (без использования доменов): predicates книга (string,string,integer,string) 2-ой способ (с использованием доменов): domains автор, заголовок, издательство = string год_издания = integer predicates книга(автор,заголовок,год_издания,издательство) Очевидно, что при наличии описанных доменов, назначение объектов предиката становится более понятным. В соответствии с теорией предикатов первого порядка единственной структурой данных в логических программах являются термы. Определение термов индуктивно. Термом может быть либо простой объект (константа, переменная, список) либо сложным объектом (структурой). Рисунок 12 - Данные в Прологе Составной терм содержит функтор и последовательность из одного или более аргументов, являющихся термами: <имя структуры (функтор)>( <терм1>,<терм2>,…,<термn>) Геометрически все структуры можно изображать в виде деревьев: корнем дерева является функтор, а ветви дерева – компоненты функтора. Если компонентой является структура, то ей соответствует поддерево в дереве всей структуры. Функтор задается своим функциональным именем и арностью (местностью или количеством аргументов). Синтаксически термы выглядят как предикаты, поэтому говорят о единообразии программ и данных в Прологе, т.е. предикат является так же термом. В Турбо-Прологе допускается использование одного и того же предикатного имени с разным количеством аргументов, поскольку каждый функтор определяется своим именем и арностью. При этом следует иметь в виду, что описания этих предикатов и соответствующие им правила должны находиться рядом в разделах predicates и clauses. Пример 2: Опишем предикат сумма, находящий сумму двух, трех или четырех целых чисел. domains слагаемое,сумма=integer predicates сумма(слагаемое,слагаемое,сумма) сумма(слагаемое,слагаемое,слагаемое,сумма) сумма(слагаемое,слагаемое,слагаемое,слагаемое,сумма) clauses сумма(X1,X2,S):-S=X1+X2. сумма(X1,X2,X3,S):-S=X1+X2+X3. сумма(X1,X2,X3,X4,S):-S=X1+X2+X3+X4. При этом можно в качестве цели указать как сумма(1,2,S), так и сумма(1,2,3,S), так и сумма(1,2,3,4,S). В разделе domains так же можно описывать структуры. Пример 3: Пусть у Васи в сумке лежит книга И.Братко “Программирование на языке ПРОЛОГ для искусственного интеллекта”. Этот факт можно описать следующей программой с использованием структуры в разделе domains. domains книга=книга(автор, заголовок) где,автор,заголовок=symbol predicates находится(где,книга) clauses находится(сумка,книга(“И.Братко”,”Программирование на языке ПРОЛОГ для искусственного интеллекта ”). Пусть в сумке у Васи лежит так же синяя ручка. Тогда можно ввести альтернативный домен, вместо того, чтобы описывать новый предикат. domains вещь=книга(автор,заголовок); ручка(цвет) где,автор,заголовок,цвет=symbol predicates находится(где,вещь) clauses находится(сумка,книга(“И.Братко”,”Программирование на языке ПРОЛОГ для искусственного интеллекта ”). находится(сумка, ручка(синий)). 2.3.2 Ввод-вывод в Турбо-Прологе В Турбо-Прологе имеются следующие встроенные предикаты для ввода c текущего устройства чтения (по умолчанию с клавиатуры) различных типов данных: • readchar(<переменная>) – ввод символа (при вводе с клавиатуры ввод идет без отображения на экране вводимого символа); • readint(<переменная>) – ввод целого числа; • readreal(<переменная>) – ввод вещественного числа; • readln(<переменная>) – ввод строки или символического имени; • readterm(<домен>,<переменная>) - ввод структуры указанного домена. Для вывода на текущее устройство вывода (по умолчанию на экран) используются предикаты: • write – вывод констант (должны быть заключены в кавычки) и значений переменных стандартных доменных . Количество аргументов произвольно; • nl – перевод строки. Для очистки экрана используется предикат без параметров: clearwindow. 2.3.3 Внутренние и внешние цели Мы уже видели, что цель можно задавать во время диалога. При этом, если в цели присутствовали переменные, то Пролог-система находит все возможные значения этой переменной. После достижения внешней цели выполнение программы продолжается (можно задавать новую цель). При этом конечно, целевая формулировка не должна быть очень длинной. В Турбо-Прологе имеется возможность описать внутреннюю цель в разделе goal. После достижения внутренней цели выполнение программы прекращается. Если во внутренней цели имеется переменная, то находится только одно возможное значение этой переменной (первое в соответствии с алгоритмом поиска). Значения этой переменной выводится на экран с помощью предиката write. Для получения всех наборов допустимых решений необходимо включение в правила специальных средств управлений поиском решений. Внутренняя цель может содержать достаточно длинную формулировку. Предложение внешней цели должно заканчиваться точкой. Пример: Рассмотрим дерево семейных отношений из примера 1 п.2.1. Зададим внутреннюю цель для ответа на вопрос: Кто родители Боба? В программе следует описать раздел goal. goal clearwindow, родитель(X,боб), write(X,”-родитель боба”), nl. Можно описать то же самое по-другому, с использованием предиката без аргументов и соответствующего правила: predicates родитель_боба goal родитель_боба. clauses родитель_боба:- clearwindow, родитель(X,боб), write(X,”-родитель боба”), nl. Заметим, что внутренняя цель найдет только одного родителя в соответствии с последовательностью описанных фактов отношения родитель, а именно Пам. Для поиска всех родителей следует применить специальные средства поиска решений, о которых речь пойдет в дальнейшем. 2.4 Рекурсия Рекурсия в Прологе может быть алгоритмическая и по данным. Основное отличие от Лиспа заключается в том, что возвращаемое значение должно находиться в аргументе предиката. Т.е., в отличие от Лиспа, где использовались функции, в Прологе используются процедуры. При этом следует помнить, что передача параметров осуществляется по значению. Пример 1: Напишем программу, которая 5 раз выводит на экран строку **********. predicates вывод_строки(integer) goal clearwindow, вывод_строки(5). clauses вывод_строки(N):-N>0, write(“**********”),nl, N1=N–1, вывод_строки(N1). В данной программе недостатком является то, что цель не достигнута. Если бы в разделе goal за предикатом вывод_строки следовало продолжение предложения цели, то это продолжение не стало бы выполняться, не смотря на то, что строка напечаталась бы 5 раз. Это связано с тем, что предикат вывод_строки неудачно завершился при X=0 (не нашлось подходящего факта или правила), т.е. не было правила выхода из рекурсии. Изменим раздел clauses. Добавим правило остановки рекурсии для успешного завершения предиката вывод_строки. clauses вывод_строки(0). вывод_строки(N):-N > 0, write(“**********”),nl, N1=N–1, вывод_строки(N1). Пример 2: Напишем программу, выводит на экран целые числа от 5 до 15 в одну строку. predicates вывод_чисел(integer) goal clearwindow, write(“Числа от 5 до 15”),nl, вывод_чисел(5),nl,nl, write(“Вывод закончен”),nl. clauses вывод_чисел(16). вывод_чисел(N):-write(N, “ “), N1=N+1, вывод_чисел(N1). Пример 3: Напишем программу вычисления n!, где n вводится с клавиатуры. domains число,результат=integer predicates факториал(число,результат) goal clearwindow, write(“Введите число для вычисления факториала ”),nl, readint(N), факториал(N,P), write(N,“!=”,P),nl. clauses факториал(0,1). факториал(N,P):-N>0, N1=N-1, факториал(N1,P1), P=P1*N. Пример 4: Напишем программу размена денежной суммы самыми «крупными» монетами, если имеется ограниченное количество монет достоинством 1, 2 и 5 рублей. Количество наличных разменных монет вводится с клавиатуры. domains кол_1,кол_2,кол_5,итого_1,итого_2,итого_5,сумма=integer predicates размен(сумма,кол_1,кол_2,кол_5,итого_1,итого_2,итого_5) мин(integer,integer,integer) goal clearwindow, write(“Введите сумму для размена ”), readint(S), write(“Введите количество наличных монет для размена”),nl, write(“По 1 рублю - ”), readint(K1), write(“По 2 рубля - ”), readint(K2), write(“По 5 рублей - ”), readint(K3), размен (S,K1,K2,K3,0,0,0). clauses размен(0,_,_,_,N1,N2,N3):-S=5*N3+2*N2+N1, write(S,”=5*,N3,”+2*”,N2,”+”,N1). размен(S,K1,K2,K3,N1,N2,N3):-S>=5,NN=S div 5,K3>0, мин(NN,K3,MIN),S1=S-5*MIN, L3=K3-MIN,M3=N3+MIN, размен(S1,K1,K2,L3,N1,N2,M3). размен(S,K1,K2,K3,N1,N2,N3):-S>=2,NN=S div 2,K2>0, min(NN,K2,MIN),S1=S-2*MIN, L2=K2-MIN,M2=N2+MIN, размен(S1,K1,L2,K3,N1,M2,N3). размен(S,K1,K2,K3,N1,N2,N3):-S>=1,K1>0, min(S,K1,MIN),S1=S-MIN, L1=K1-MIN,M1=N1+MIN, размен(S1,L1,K2,K3,M1,N2,N3). размен(_,_,_,_,_,_,_):-write(“Разменять не удалось”),nl. мин(X,Y,X):-X3,X<=6. f(X,4):-X>6. Рассмотрим поиск решения Пролог-системой при задании в качестве внешней цели f(1,Y),Y>2.предложения: Рисунок 15 – Поиск решения При вычислении первой цели по правилу 1 переменная Y конкретизируется 0 и цель успешна. Далее вторая цель Y>2 терпит неудачу, поэтому весь список целей терпит неудачу. Однако, Пролог-система при помощи возвратов попытается проверить еще две бесполезные в данном случае альтернативы. Все имеющиеся правила являются взаимоисключающими, поэтому только одно из них может быть успешным. Мы знаем (но не Пролог-система), что если одно из правил успешно, нет смысла проверять остальные, поскольку они обречены на неудачу. О том, что правило 1 успешно становится известно в точке, обозначенной словом «отсечение». Для предотвращения бесполезного перебора мы должны явно указать Пролог-системе, что не нужно осуществлять возврат из этой точки. Для запрета возврата используется предикат cut, который можно записать так же как !. Этот предикат всегда успешен, вставляется между целями и предотвращает возврат из тех точек программы, где он стоит. Перепишем программу с использованием отсечения. f(X,0):-X<=3,!. f(X,2):-X>3,X<=6,!. f(X,4):-X>6. Теперь при поиске решения альтернативные ветви, соответствующие правилам 1 и 2, порождены не будут. Программа станет эффективнее. Если убрать отсечения, программа выдаст тот же результат, хотя на его получение она затратит, скорее всего, больше времени. Получается, что в данном случае отсечения изменили только процедурный смысл программы (теперь проверяется только левая часть дерева решений), не изменив ее декларативный смысл. Далее будет показано, что отсечения могут затрагивать и декларативный смысл программы. Рассмотрим поиск решений при цели f(7,Y). Рисунок 16 – Поиск решения Здесь стал заметен еще один источник неэффективности. После того, как выяснилось, что цель 7  3 потерпела неудачу, следующей целью становится проверка 7 > 3. Но эту проверку можно опустить, т.к. известно, утверждение Y > 3 является отрицанием утверждения Y  3. То же самое можно сказать и о цели X > 6 в правиле 3. Эти рассуждения приводят к более эффективной программе: f(X,0):-X<=3,!. f(X,2):-X<=6,!. f(X,4). Но если из этой программы убрать отсечения, то она будет не всегда правильно работать. Например, для цели f(1,Y) будут найдены три решения: Y=0, Y=2, Y=4. Таким образом, теперь отсечения затрагивают декларативный смысл программы. Так же на декларативный смысл программы может повлиять перестановка правил, содержащих отсечения. Отсечения, которые не затрагивают декларативный смысл программы, называются зелеными. Отсечения, меняющие декларативный смысл программы называются красными. Их следует применять с большой осторожностью. Сформулируем более точно, как работает механизм отсечений. Пусть имеется правило вида: . Если цели успешны, то это решение замораживается, и другие альтернативы для этого решения больше не рассматриваются (отсекается правая часть дерева решений, которая находится выше ). Пример 2: Напишем предикат, находящий максимум из двух чисел, с использованием отсечения. predicates max(real,real) clauses max(X,Y,X):-X>=Y,!. max(_,Y,Y). Как видно из приведенных примеров отсечения позволяют описать конструкцию если-то-иначе. 2.6.2 Откат после неудач Встроенный предикат fail всегда неудачен, поэтому вызывает неудачное завершение цели и инициализирует откат в точки поиска альтернативных решений. Пример: Пусть имеются факты относительно предиката кандидат, которые определяют претендентов для участия в выборах депутатов областного совета. Требуется найти всех кандидатов в возрасте до 40 лет. domains фио=symbol возраст=integer predicates кандидат(фио,возраст) все_до_40 goal все_до_40. clauses кандидат(“Иванова Анна Федоровна”,36). кандидат(“Петров Иван Сергеевич”,36). ………………………………………………. все_до_40:- кандидат(X,Y), Y<40, write(X,”-“,Y,”лет”), nl, fail. все_до_40. 2.6.3 Циклы, управляемые откатом Определим предикат повтор без аргументов с помощью двух правил: повтор. повтор:-повтор. Первое правило всегда успешно, поскольку не содержит подцелей. Однако, поскольку имеется второй вариант правила для этого предиката, Пролог-система запоминает в качестве точки отката второе правило. Попытка применить второе правило так же всегда успешна, т.к. первое правило удовлетворяет подцели второго правила. Таким образом, предикат повтор всегда успешен. С помощью этого предиката легко организовать цикл «до тех пор, пока», записав правило вида: <голова правила>:- повтор, <тело цикла>, <условие выхода>,!. Отсечение в качестве завершающей подцели гарантирует остановку цикла в случае выполнения условия выхода из цикла. Пример: Напишем программу, которая считывает слово, введенное с клавиатуры, и дублирует его на экран до тех пор, пока не будет введено слово «stop». domains слово=symbol predicates повтор эхо проверка(слово) goal write(“Введите слово для повтора: ”),nl, эхо. clauses повтор. повтор:-повтор. эхо: - повтор, readln(Slovo), write(Slovo),nl, проверка(Slovo),!. проверка(stop):-write(“Конец”),nl. проверка(_):-fail. Такие циклы используются для описания взаимодействия с внешней системой путем повторяющегося ввода или вывода. В таком цикле обязательно должен быть предикат (в примере – это проверка), приводящий к безуспешным вычислениям. Рекурсивные циклы предпочтительнее циклов, управляемых отказами, поскольку последние не имеют логической интерпретации. Но на практике такие циклы необходимы при выполнении большого объема вычислений, поскольку рекурсия требует много памяти. 2.7 Списки Список – это упорядоченный набор объектов одного доменного типа. Объектами списка могут быть целые числа, действительные числа, символы, строки и структуры. Если структуры принадлежат альтернативному домену, элементы списка могут иметь разный тип. Список может быть объектом списка. Элементы списка разделяются запятой и заключаются в квадратные скобки. Пустой список не содержит элементов и обозначается []. Пример 1: [1,2,-3,4] – список целых чисел; [энн,боб,лиз] – список символических имен; [a,b],[c,g,l],[]] – список из списков символических имен. Для списка всегда описывается домен, при этом после имени домена элементов ставится звездочка. Пример 2: Пусть предикат хор определяет студентов, поющих в хоре. domains фамилия=symbol список_студентов=фамилия * predicates хор(список_студентов) clauses хор([иванова,петров,сидоров,федорова]). Можно ввести следующие внешние цели и получить ответы Пролог-системы: Вопрос в Пролог-системе Ответ Пролог-системы хор(All) All=[иванова,петров,сидоров,федорова] 1 решен. s хор([_,_,_,X]) X = федорова 1 решен. s Заметим, что в данном случае, для определения элемента списка следовало знать количество элементов в списке. 2.7.1 Голова и хвост списка Для более удобной работы со списком, так же как в Лиспе, непустой список делится на хвост и голову. Головой называется первый элемент списка, хвостом – часть списка без первого элемента. Пример 1: Деление списка на хвост и голову. Список Голова Хвост [1,2,3,4] 1 [2,3,4] [a] a [] [] не определена не определен Для деления списка на хвост и голову в Прологе имеется специальная форма представления списка: [Head|Tail]. При сопоставлении конкретного списка с такой формой, Head сопоставляется с головой списка, а Tail – с хвостом списка. Таким образом, одновременно определяются голова и хвост списка. Пример 2: Рассмотрим результаты сопоставления списков. Список 1 Список 2 Результаты сопоставления [X,Y,Z] [1,2,3] X=1, Y=2, Z=3 [5] [X|Y] X=5, Y=[] [1,2,3,4] [X,Y|Z] X=1, Y=2, Z=[3,4] [1,2,3] [X,Y] нет решений [a,X|Y] [Z,a] Z=a, X=a, Y=[] 2.7.2 Операции со списками 2.7.2.1 Принадлежность элемента списку Определим предикат member, определяющий принадлежность целого числа списку целых чисел. Определение будет таким же, как в Лиспе: число совпадает с головой списка, либо принадлежит хвосту списка. domains number=integer list=number* predicates member(number,list) clauses member(X,[X|_]):-!. member(X,[_|Tail]):-member(X,Tail). Предикат member имеет много интересных приложений: проверка принадлежности элемента списку с помощью вопросов вида member(1,[2, 5, 1, 8]), в нахождении элементов списка с помощью вопросов вида member(X,[2, 5, 1, 8]) и списков, содержащих элемент, с помощью вопросов вида member(1,X). Последний вопрос выглядит несколько странным, но, тем не менее, имеется ряд программ, основанных на таком применении отношения member. 2.7.2.2 Соединение двух списков Определим предикат, соединяющий два списка целых чисел в один путем добавления после элементов первого списка всех элементов второго списка. Определим предикат append следующим образом: если в первом списке имеется голова, то она будет являться головой второго списка, хвостом результирующего списка будет результат соединение хвоста первого списка со вторым; если первый список пуст, то результат соединения – второй список. domains list=integer* predicates append(list,list,list) clauses append([],L,L). append([Head|Tail],L,[Head|Tail1]):-append(Tail,L,Tail1). Как и в случае с member существуют разнообразные применения предиката append: • слияние двух списков; • получение всех возможных разбиений списка; • поиск подсписков до и после определенного элемента; • поиск элементов списка, стоящих перед и после определенного элемента; • удаление части списка, начиная с некоторого элемента; • удаление части списка, предшествующей некоторому элементу. Примеры использования предиката append приведены в таблице. Вопрос в Пролог-системе Ответ Пролог-системы append([1,2],[3],L) L=[1,2,3] 1 решен. s append(L1,L2,[1,2,3]) L1=[],L2=[1,2,3] L1=[1],L2=[2,3] L1=[1,2],L2=[3] L1=[1,2,3],L2=[] 4 решен. s append(Before,[3|After],[1,2,3,4,5]) Before=[1,2],After=[4,5] 1 решен. s append(_,[Before,3,After|_],[1,2,3,4,5]) Before=2,After=4 1 решен. s append(L1,[3|_],[1,2,3,4,5]) L1=[1,2] 1 решен. s append(_,[3|L2],[1,2,3,4,5]) L2=[4,5] 1 решен. s 2.7.2.3 Добавление и удаление элемента из списка Определим предикат delete, который будет удалять первое вхождение указанного элемента в список целых чисел. Определим предикат следующим образом: если элемент совпадает с головой списка, то результат удаления – хвост списка, иначе результатом удаления является список, у которого голова совпадает с исходным списком, а хвост - результат удаления указанного элемента из хвоста исходного списка. Определим предикат insert, который будет добавлять указанный элемент в голову списка целых чисел. Определим предикат следующим образом: головой результирующего списка является указанный элемент, а хвостом – исходный список. domains list=integer* predicates insert(integer,list,list) delete(integer,list,list) goal write(“Введите список: ”),readterm(list,L), write(“Добавить элемент: ”),readint(X), insert(X,L,L1), write(“Удалить элемент: ”), readint(Y), delete(Y,L,L2), write(“L1=”,L1,”L2=”,L2),nl. clauses insert(X,L,[X|L]). delete(_,[],[]). delete(Y,[Y|Tail],Tail). delete(Y,[Z|Tail],[Z|Tail1]):-delete(Y,Tail,Tail1). Заметим, что если необходимо удалить все вхождения указанного элемента, то второе правило для предиката delete следует изменить следующим образом: delete(Y,[Y|Tail],L):-delete(Y,Tail,L). 2.7.2.4 Деление списка на два списка по разделителю Определим предикат split, который будет делить список целых чисел на две части, используя разделитель M (целое число). Определим предикат следующим образом: если элемент исходного списка меньше разделителя, то он помещается в первый результирующий список, иначе – во второй результирующий список. domains list=integer* predicates split(integer,list,list,list) clauses split(M,[Head|Tail],[Head|L1],L2):-HeadY,!,insert(X,Sort_list,Sort_list1). insert(X,Sort_list,[X|Sort_list]). 2.7.3.2 Пузырьковая сортировка При пузырьковой сортировке меняем местами соседние элементы до тех пор, пока есть неверно упорядоченные пары. Если таких пар нет, то список отсортирован. Для перестановки пары соседних элементов в списке будем использовать предикат swap (он успешен, если такая пара нашлась). domains list=integer* predicates pu_sort (list,list) swap(integer,list,list) clauses pu_sort(L,Sort_list):-swap(L,L1),!, pu_sort(L1,Sort_list). pu_sort(L,L). swap([X,Y|Tail],[Y,X|Tail]):-X>Y. swap([X|Tail],[X|Tail1]):-swap(Tail,Tail1). 2.7.3.3 Быстрая сортировка Процедуры пузырьковой сортировки и сортировки вставкой просты, но не эффективны. Среднее время сортировки для этих процедур пропорционально n2. Поэтому, для длинных списков используют алгоритм быстрой сортировки. При быстрой сортировке сначала разбиваем список на два списка по разделителю – голове списка, затем упорядочиваем новые списки и соединяем их. Если новые списки получаются примерно одинаковой длины, то временная сложность алгоритма быстрой сортировки будет примерно nlogn. Если же длины списков сильно различаются, то сложность будет порядка n2. В среднем время быстрой сортировки ближе к лучшему случаю, чем к худшему. В программе будем использовать определенные в п.2.8.2.2 и 2.8.2.4 предикатов append и split. domains list=integer* predicates q_sort (list,list) append(list,list,list) split (integer,list,list,list) clauses q_sort([Head|Tail],Sort_list):- split(Head,Tail,Less,More), q_sort(Less,Sort_less), q_sort(More,Sort_more), append(Sort_less,[Head|Sort_more],Sort_list). q_sort([],[]). 2.7.4 Компоновка данных в список Иногда при программировании на Прологе возникает необходимость собрать данные из базы данных в список для их последующей обработки. Для этих целей в Прологе имеется встроенный предикат findall, обращение к которому имеет вид: findall(X,P,L), где X – объект предиката P, L – имя переменной выходного списка. Этот предикат формирует список из объектов X предиката P. Пусть имеются сведения о количестве детей у определенных лиц (предикат data). Требуется найти общее количество детей в этой группе людей. domains family=symbol sum=integer kolvo=integer list=kolvo* predicates data(family,kolvo) all(list,sum) goal findall(Kolvo,data(_,Kolvo),L), /*Элементы списка L – количества детей */ all(L,S), write(“Общее количество детей: ”, S),nl. clauses data(иванов,2). …………………. data(петров,1). all([],0). all([Head|Tail],S):-all(Tail,S1),S=S1+Head. 2.8 Решение логических задач с использованием списков 2.8.1 Задача о фермере, волке, козе и капусте Рассмотрим широко известную логическую задачу о фермере, волке, козе и капусте. Задача заключается в следующем. Фермер (farmer), волк (wolf) , коза (goat) и капуста (cabbidge) находятся на одном берегу. Всем надо перебраться на другой берег на лодке. Лодка перевозит только двоих. Нельзя оставлять на одном берегу козу и капусту (коза съест капусту), козу и волка (волк съест козу). Главная проблема в формировании алгоритма - найти эффективное представление структурой данных информации о задаче. Процесс перевозки может быть представлен последовательностью состояний state с 4 аргументами, каждый из которых может принимать два значения: right – на левом берегу, left – на правом берегу и отражает соответственно нахождение фермера, волка, козы и капусты. Например, state(left,right,left,right) означает, что фермер и коза находятся на левом берегу, а волк и капуста – на правом. Фермер может перевести на другой берег кроме себя либо волка, либо козу, либо капусту. Для описания возможных вариантов перевозки (переходов из одного состояния в другое) напишем предикат move. Для того чтобы можно было переправляться с левого берега на правый и наоборот, определим предикат opposite, который определяет сторону, противоположную исходной. move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y). /* фермер + волк */ move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y). /* фермер + коза */ move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y). /*фермер + капуста */ move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y). /* только фермер */ opposite(right,left). opposite(left,right). С помощью предиката danger определим опасные состояния, когда коза может съесть капусту или волк съесть козу. danger(state(F,_,X,X)):-opposite(F,X). /*коза может съесть капусту*/ danger(state(F,X,X,_)):-opposite(F,X)./*волк может съесть козу*/ Наконец, определим предикат, который path, который сформирует список из последовательности состояний, решающих поставленную задачу. Добавляем в список новое состояние, если в него возможен переход из текущего состояния, оно не опасно и не содержится в уже сформированной последовательности состояний (чтобы не было зацикливания) path(G,G,T,T):-!. path(S,G,L,L1):-move(S,S1), not(danger(S1) ), not(member(S1,L)), path(S1,G,[S1|L],L1),!. Итак, окончательный вариант программы будет иметь вид: domains state=state(symbol,symbol,symbol,symbol) spisok=state* predicates move(state,state) opposite(symbol,symbol) danger(state) path(state,state,spisok,spisok) member(state,spisok) goal S=state(left,left,left,left), G=state(right,right,right,right), path(S,G,[S],L), nl,write('A solution is:'),nl, write(L). clauses move(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y). move(state(X,W,X,C),state(Y,W,Y,C)):-opposite(X,Y). move(state(X,W,G,X),state(Y,W,G,Y)):-opposite(X,Y). move(state(X,W,G,C),state(Y,W,G,C)):-opposite(X,Y). opposite(right,left). opposite(left,right). danger(state(F,_,X,X)):-opposite(F,X). danger(state(F,X,X,_)):-opposite(F,X). path(G,G,T,T):-!. path(S,G,L,L1):- move(S,S1), not(danger(S1) ), not(member(S1,L)), path(S1,G,[S1|L],L1),!. member(X,[X|_]). member(X,[_|L]):-member(X,L). Пролог найдет следующее решение задачи: [state(left,left,left,left), state(right,left,right,left), state(left,left,right,left), state(right,left,right,right), state(left,left,left,right), state(right,right,left,right), state(left,right,left,right), state(right,right,right,right)] Это соответствует следующему алгоритму: 1. Фермер перевозит козу с левого берега на правый. 2. Фермер перемещается с правого берега на левый. 3. Фермер перевозит капусту с левого берега на правый. 4. Фермер перевозит козу с правого берега на левый. 5. Фермер перевозит волка с левого берега на правый. 6. Фермер перемещается с правого берега на левый. 7. Фермер перевозит козу с левого берега на правый. 2.8.2 Решение числовых ребусов Рассмотрим пример числового ребуса:   DONALD   GERALD ROBERT Задача состоит в том, чтобы заменить все буквы цифрами. Одинаковым буквам должны соответствовать одинаковые цифры, а разным буквам – разные цифры. Определим предикат sum(N1,N2,N), который истинен, если существует такая замена букв цифрами в словах N1, N2, N, что N1+N2=N. Числа будем представлять списком цифр, из которых состоит число. Без ограничения общности можно считать, что все три списка, представляющие числа имеют равную длину. Если числа разной длины, то всегда можно приписать нужное количество нулей более «коротким» числам. В правилах для предиката sum необходимо описать правила суммирования в десятичной системе счисления. Суммирование производится слева направо с учетом цифры переноса с предыдущего разряда. Следовательно, при суммировании очередных цифр нужна дополнительная информация о переносе из предыдущего разряда и о переносе в следующий разряд. Поскольку разным буквам должны соответствовать разные цифры, то при суммировании цифр нужна информация о цифрах, доступных до и после сложения (эта информация будет представляться двумя списками). В связи с вышесказанным определим вспомогательный предикат sum1 с дополнительными параметрами: sum1(N1,N2,N, P_before,P_after, Cifri_before,Cifri_after), где P_before – перенос из правого разряда до сложения, P_after - перенос в левый разряд после сложения, Cifri_before – список цифр, которые могут быть использованы для конкретизации переменных до сложения, Cifri_after – список цифр, которые могут быть использованы для конкретизации переменных после сложения. Тогда можно описать связь предиката sum и sum1 следующим образом: sum(N1,N2,N):-sum1(N1,N2,N,0,0,[0,1,2,3,4,5,6,7,8,9],_). Определим отношение sum1 следующим образом: • Если у всех трех чисел имеется хотя бы одна цифра (в списках можно выделить головы), то суммируем числа без самой левой цифры и, используя список оставшихся цифр и перенос из предыдущего разряда, суммируем самые левые цифры и добавляем полученную сумму в результат суммирования без самой левой цифры. Для суммирования цифр определим предикат sumc. • Если все три списка пустые, то переносов разрядов нет, и списки цифр до и после сложения совпадают. Это соответствует правилу остановки рекурсии: sum1([],[],[],0,0,Cifri,Cifri). Получаем следующие правила: sum1([],[],[],0,0,L,L). sum1([D1|N1],[D2|N2],[D|N],C1,C,L1,L):- sum1(N1,N2,N,C1,C2,L1,L2), sumc(D1,D2,D,C2,C,L2,L). Осталось определить правила для предиката sumc. Первые три аргумента предиката должны быть цифрами. Если какая-нибудь из этих переменных не конкретизирована, то ее необходимо конкретизировать какой-нибудь цифрой из списка L2. После конкретизации цифру следует удалить из списка доступных цифр. Если переменная уже имела значение, то удалять из списка доступных цифр ничего не надо. sumc(D1,D2,D,C2,C,L2,L):- delete(D1,L2,L3), delete(D2,L3,L4), delete(D,L4,L), S=D1+D2+C2, D=S mod 10, C=S div 10. Для удаления цифры из списка или для получения значения неозначенной переменной будем использовать предикат delete. Для проверки означенности переменной будет использоваться встроенный предикат bound(<переменная>). delete(X,L,L):-bound(X),!. delete(X,[X|L],L). delete(X,[Y|L],[Y|L1]):-delete(X,L,L1). Итак, окончательный вариант программы будет иметь вид: domains list=integer* predicates sum(list,list,list) sum1(list,list,list,integer,integer,list,list) sumc(integer,integer,integer,integer,integer,list,list) delete(integer,list,list) clauses sum(N1,N2,N):-sum1(N1,N2,N,0,0,[0,1,2,3,4,5,6,7,8,9],_). sum1([],[],[],0,0,L,L). sum1([D1|N1],[D2|N2],[D|N],C1,C,L1,L):-sum1(N1,N2,N,C1,C2,L1,L2), sumc(D1,D2,D,C2,C,L2,L). sumc(D1,D2,D,C2,C,L2,L):-delete(D1,L2,L3), delete(D2,L3,L4), delete(D,L4,L), S=D1+D2+C2, D=S mod 10, C=S div 10. delete(X,L,L):-bound(X),!. delete(X,[X|L],L). delete(X,[Y|L],[Y|L1]):-delete(X,L,L1). Для решения заданного в начале пункта ребуса следует ввести цель: sum([D,O,N,A,L,D],[G,E,R,A,L,D],[R,O,B,E,R,T]) Для данного ребуса получим единственное решение: D=5, O=2, N=6, A=4, L=8, G=1, E=9, R=7, B=3, T=0. 2.9 Строки Строкой называется последовательность символов или их ASCII кодов, заключенный в кавычки. Перед каждым ASCII кодом должен стоять знак обратного слэша (\). Замечание Если строка вводится с клавиатуры, то кавычки не ставятся. Пример 1: “ABC” – строка; “\65\66\67”- та же самая строка в ASCII кодах. Для строк определены следующие предикаты: 1. str_len (<строка>, <длина строки>) – находит длину строки. Пример 2: При задании цели str_len (“Turbo Prolog”,N) переменная N получит значение, равное 12 (длина строки “Turbo Prolog”). Пример 3: При задании цели str_len (“Turbo Prolog”,10) будет неуспешное завершение предиката (предикат будет сравнивать числа 12 и 10). 2. concat (<строка1>, <строка2>, <строка_результат>) – соединение (конкатенация) строки1 и строки2. Пример 4: При задании цели concat (“Turbo ”,”Prolog”, L) переменная L получит значение “Turbo Prolog”. Заметим, что предикат concat можно использовать и для разбиения строки. Пример 5: При задании цели concat (“Turbo ”, L, ”Turbo Prolog”) переменная L получит значение “Prolog”. 3. frontstr (<кол-во символов>, <строка>, <подстрока>, <остаток строки>) – находит подстроку из указанного количества первых символов строки. Пример 6: При задании цели frontstr (6, “Turbo Prolog”,Substring, Rest_string) переменная Substring получит значение “Turbo ”, а переменная Rest_string получит значение “Prolog”. 4. frontchar (<строка>, <символ>, <остаток строки>) – разбивает строку на символьный префикс и оставшуюся часть строки. Символьный префикс заключается в апострофы. Пример 7: Напишем предикат, преобразующий строку в список символов. Декларативное описание предиката: первый символ строки является головой списка, хвост списка получается из подстроки без первого символа строки; если в строке нет символов, то список пуст. domains list=char* predicates string_listc(string,list) clauses string_listc(“”,[]). string_listc(Str,[Head|Tail]):- frontchar(Str,Head,Str1), string_listc(Str1,Tail). 5. fronttoken(<строка>, <атом>, <остаток строки>) – выделяет в строке атом. Атом (token) - особый вид строки. Атомами являются: последовательности из букв, цифр и символа подчеркивания, начинающиеся с букв; специальные символы #, $, ! и т.д.; числа. Пример 8: Напишем предикат, преобразующий строку в список атомов. Декларативное описание предиката: первый атом в строке является головой списка, хвост списка получается из подстроки без первого атома строки; если в строке нет атомов (но могут остаться пробелы), то список пуст. domains list=symbol* predicates string_listt(string,list) clauses string_listt(Str,[Head|Tail]):-fronttoken(Str,Head,Str1),!, string_listt(Str1,Tail). string_listt(_,[]). Пример 9: Напишем предикат, преобразующий строку в список атомов c функторами. Такой предикат может использоваться для записи в базу данных фактов, относящихся к некоторому одноместному предикату, объектами которого могут быть атомы из строки символов. Пусть в качестве функтора выступает имя предиката женщина, а строка состоит из имен женщин. domains fact=женщина(symbol) list=fact* predicates string_listf(string,list) create_fact(symbol,fact) clauses string_listf(Str,[Head|Tail]):- fronttoken(Str,Token,Str1),!, create_fact(Token,Head), string_listf(Str1,Tail). string_listf(_,[]). create_fact(Token,женщина(Token)). Для цели string_ listf(“энн пат лиз джейн”, L) получим решение: L=[женщина(энн),женщина(пат),женщина(лиз),женщина(джейн)] 2.10 Предикаты для работы с файлами Для работы с файлами в разделе domains следует описать файловый домен: file=<имя домена>. Имя домена – это логическое имя файла. Если в программе используется несколько файлов, то они перечисляются через точку с запятой. Пример 1: domains file=data1;data2;data3 В каждый момент времени активными могут быть только два файла: один для ввода и один для вывода. По умолчанию ввод осуществляется с клавиатуры (логическое имя keyboard), а вывод – на экран (логическое имя screen). Предикат existfile(<имя физического файла>) успешно завершается, если файл с указанным именем существует. Для работы с файлом его открывают для чтения, записи или добавления с помощью одного из предикатов: • openread(<логическое имя>,<имя физического файла >); • openwrite(<логическое имя>,< имя физического файла >); • openappend(<логическое имя>,< имя физического файла >). Логическое имя файла объявляется в описании домена file, оно должно начинаться со строчной буквы. Физическое имя файла должно быть строкой, т.е. заключаться в кавычки. При открытии файла происходит связывание логического имени с физическим файлом. При открытии файла предикатом openwrite, файл создается заново. Для чтения и записи в файл используются предикаты из пункта 2.3.2. Обработка файлов осуществляется последовательно. Следует иметь в виду, что предикаты для работы с файлами являются внелогическими, т.к. не дают альтернативных решений при откате (повторно считать то же самое из файла в случае неуспешной обработки данных нельзя). Поэтому чтение из файла и обработка считанного должна производиться отдельно! Пример 2 Пусть целые числа вводятся с клавиатуры и на экран выводятся из квадраты. Завершение ввода – ввод нуля. Рассмотрим вариант программы, когда чтение и обработка данных не разделены. predicates sqr goal write(“Программа находит квадраты чисел, введенных с клавиатуры. Окончание ввода – 0”),nl, sqr. clauses sqr:- write(“Введите целое число “), readint(N),N=0,!. sqr:- write(“Введите целое число “), readint(N), N2=N*N, write(“Квадрат числа “,N,” равен “,N2),nl, sqr. Если с клавиатуры ввести числа 5, 3, 6, 4, 0, то на экране появятся только квадраты чисел 3, 4. Квадраты чисел 5, 6 не вычисляются. Более того, если ввод 0 будет на четном месте во вводимой последовательности, то остановки ввода не произойдет. Правильный вариант программы с разделением ввода и обработки данных будет иметь вид: predicates sqr process(integer) goal write(“Программа находит квадраты чисел, введенных с клавиатуры. Окончание ввода – 0”),nl, sqr. clauses sqr:- write(“Введите целое число “), readint(N), process(N). process(0):-!. process(N):-N2=N*N, write(“Квадрат числа “,N,” равен “,N2),nl, sqr. Предикат eof(<логическое имя>) успешно завершается, если найден конец файла. После окончания работы с файлом его закрывают с помощью предиката closefile(<логическое имя>). Для перенаправления ввода или вывода используют предикаты: readdevice(<логическое имя>), writedevice(<логическое имя>). Находясь в окне редактора с помощью клавиши F8 можно открыть второе окно редактора для просмотра и редактирования файлов. Закрытие этого окна – клавиша Esc. Пример 3: Напишем предикат write_to_file, который записывает вводимый с клавиатуры текст в файл t.txt. Окончание ввода – символ #. domains file=myfile predicates write_to_file write_char(char) goal write(“Введите текст для записи в файл t.txt \n Окончание ввода – #”), nl, write_to_file. clauses write_to_file:-readchar(X), /* Вводимый символ на экране не отображается */ write(X), /* Вывод символа на экран*/ openwrite(myfile,”t.txt”), /* Открытие файла для записи*/ writedevice(myfile), /* Перенаправление вывода в файл*/ write_char(X), /* Запись символа в файл */ closefile(myfile), /* Закрытие файла*/ writedevice(screen), /* Перенаправление вывода на экран*/ nl,write(“Данные записаны в файл”),nl. write_char(‘#’). write_char(‘\13’):- nl, /* Если нажата клавиша Enter, то переход на следующую строку в файле*/ writedevice(screen), /* Перенаправление вывода на экран*/ nl, /* Переход на следующую строку на экране*/ readchar(X), /* Ввод следующего символа*/ write(X), /* Вывод символа на экран*/ writedevice(myfile), /* Перенаправление вывода в файл*/ write_char(X). /* Продолжение ввода*/ write_char(X):-write(X), /* Вывод символа в файл*/ writedevice(screen), /* Перенаправление вывода на экран*/ readchar(Y), /* Ввод следующего символа*/ write(Y), /* Вывод символа на экран*/ writedevice(myfile), /* Перенаправление вывода в файл*/ write_char(Y). /* Запись символа в файл */ Пример 4: Напишем предикат add_to_file, который записывает вводимые с клавиатуры строки в файл, имя которого вводится с клавиатуры. Причем, если файл уже существовал, введенные строки добавляются в конец файла. Окончание ввода – строка “end”. domains file=myfile predicates add_to_file write_string(string) check_exist(string) goal add_to_file. clauses add_to_file:-write(“Введите имя файла: “), readln(Filename), /* Ввод с клавиатуры имени файла */ check_exist(Filename), /* Проверка существования файла*/ write(“Введите строки для добавления в файл”),nl, writedevice(myfile), /* Перенаправление вывода в файл*/ readln(String), /* Ввод с клавиатуры строки*/ write_string(String), /* Запись введенной строки в файл*/ closefile(myfile). /* Закрытие файла*/ check_exist(Filename):-existfile(Filename),!, openappend(myfile,Filename). /* Открытие файла для добавления*/ check_exist(Filename):-write(“Создан новый файл”),nl, openwrite(myfile,Filename). /* Создание нового файла для записи*/ write_string(“end”):-!. write_string(String):- write(String), nl, /* Запись строки в файл с переводом строки*/ readln(String1), /* Ввод с клавиатуры новой строки*/ write_string(String1). /* Запись новой строки в файл*/ Пример 5: Напишем предикат read_file, который выводит на экран строки из файла, начиная с некоторого номера. Имя файла и номер строки вводятся с клавиатуры. domains file=myfile predicates read_file(integer) write_screen check_exist(string) goal write(“Введите имя файла: “), readln(Filename), /* Ввод с клавиатуры имени файла */ check_exist(Filename), /* Проверка существования файла*/ write(“Введите номер строки для вывода строк из файла на экран ”), readint(N), openread (myfile,Filename), /* Открытие файла для чтения*/ readdevice(myfile), /* Перенаправление ввода на файл*/ read_file(N), /* Пропуск в файле N-1 строки*/ write(“Содержимое файла, начиная с ”,N,”-ой строки:”),nl, write_screen, /* Вывод на экран строк, начиная с N-ой*/ closefile(myfile). /* Закрытие файла*/ clauses check_exist(Filename):-existfile(Filename),!. check_exist(_):-write(“Такого файла нет”),nl, fail. read_file(1):-!. read_file(N):-readln(_), /*Пропускаем строку*/ N1=N-1, read_file(N1). read_file(N):-eof(myfile),!, write(“В файле меньше, чем ”,N,” строк”),nl, fail. write_screen:- eof(myfile),!. write_screen:- readln(String), /* Чтение из файла строки*/ write(String),nl, /* Вывод строки на экран и перевод строки*/ write_screen. Иногда бывает полезен предикат file_str(<имя физического файла >,<строка>), который считывает в указанную строку всех символов из файла или наоборот содержимое строки записывает в файл. Размер файла должен быть не больше 64K. Если файл не существовал, то он создастся. 2.11 Динамические базы данных Реляционная модель базы данных описывает множество отношений. Программа на Прологе представляет собой набор фактов и правил, поэтому ее можно рассматривать как реляционную базу данных. Отношения базы данных – это предикаты, атрибутами отношений являются объекты предикатов, элементы отношений присутствуют в виде фактов (явно) и правил (неявно), мощности отношений определяются количеством фактов и правил для каждого предиката. Описанная база данных является статической, она является частью кода программы, и поэтому во время работы программы не может быть изменена. Иногда в процессе работы возникает необходимость изменить, удалить или добавить некоторые факты. Такие факты являются частью динамической базы данных. Предикаты из динамической базы данных описываются в разделе database, который находится после раздела domains. При запуске программы факты из динамической базы данных помещаются в оперативной памяти в виде специальных таблиц отдельно от кода программы, поэтому могут быть изменены во время работы программы. Следует иметь в виду, что динамическая база данных сохраняется в оперативной памяти во время всего сеанса работы с Прологом. Поэтому, если эту память не очищать после работы программы, при повторном запуске программы можно получить неожиданные результаты. Пример: Опишем предикат person динамической базы данных: domains family=symbol age=integer database person(family,age) Отметим особенности динамической базы данных: 1. предложения динамической базы данных могут быть только фактами; 2. факты не могут содержать свободных переменных; 3. если объекты предиката динамической базы данных относятся к типу symbol, то они должны быть заключены в кавычки; 4. имена предикатов динамической базы данных не могут совпадать с именами предикатов, описанных в разделе predicates; 5. имена предикатов динамической базы данных должны быть уникальны, т.е. предикат определяется только своим именем, без учета арности . 6. предложения для динамической базы данных можно загрузить из файла, используя предикат consult. 2.11.1 Добавление и удаление фактов Для добавления факта в начало или конец динамической базы данных используются соответственно предикаты: asserta(<факт>) и assertz(<факт>). Эти предикаты всегда успешны. Для удаления факта, сопоставимого с F, используется предикат retract(F). Пример 1: Напишем предикат delete_person, который будет выводить на экран фамилии тех людей, возраст которых больше 50 лет. Фамилия и возраст человека являются объектами предиката person динамической базы данных. После вывода на экран фамилии, соответствующий факт удаляется из динамической базы данных. domains family=symbol age=integer database person(family,age) predicates delete_person clauses delete_person:-person(Family,Age), Age>50, write(Family),nl, retract(person(Family,Age)), fail. delete_person. Для модификации динамической базы данных можно использовать предложения, содержащие предикаты asserta, assertz и retract. Например, чтобы отредактировать имеющееся в динамической базе данных утверждение, в программе должно составиться отредактированное утверждение, удалиться из базы данных старое утверждение и занестись новое. Для удаления всех фактов, сопоставимых с F, используется предикат retractall(F). Этот предикат всегда успешен, но в отличие от retract(F), не позволяет получить значения объектов из удаленных файлов. Пример 2: Для удаления из динамической базы данных примера2 всех фактов, касающихся 20-летних людей, можно воспользоваться предикатом: retractall(person(_,20)). Для полной очистки динамической базы данных используется retractall(_). 2.11.2 Заполнение динамической базы данных фактами из файла, сохранение динамической базы данных в файле Предикат consult(<имя физического файла>) считывает из файла факты, относящиеся к предикатам, описанных в разделе database, и добавляет их в конец динамической базы данных (аналогично assertz). В случае, если файл будет содержать что-нибудь отличное от фактов динамической базы данных, предикат consult завершится неуспешно и факты из файла в динамическую базу данных добавлены не будут. Имя файла заключается в кавычки. Файлы, содержащие информацию для динамической базы данных, имеют расширение dba. Сохранение динамической базы данных в файле обеспечивает предикат save(<имя физического файла>). При этом если указанный файл уже существовал, то он создается заново. Для просмотра содержимого дополнительных файлов, можно открыть второе окно редактора, перейдя в основное окно редактора и нажав функциональную клавишу F8. Для редактирования в новом окне используются те же комбинации клавиш, что и для основного окна редактора. Пример 1: Определим предикат multiply, который вычисляет все возможные произведения чисел от 1 до 9 (таблица умножения). Таблицу умножения сохраним в файле. domains list=integer* database multiply(integer,integer,integer) count(integer) /* Счетчик количества записей в файл*/ predicates choice_el(integer,list) /* Выбирает из списка значение множителя */ write_table goal retractall(_), /* Очистка динамической памяти */ asserta(count(0)), /* Начальное значение счетчика равно 0 */ write_table, retract(count(_)), /* Удаление значение счетчика из динамической базы данных */ save("tabl.dba"), /* Сохранение содержимого динамической базы данных в файле */ retractall(_). /* Очистка динамической памяти */ clauses choice_el(X,[X|_]). choice_el(X,[_|Tail]):-choice_el(X,Tail). write_table:-L=[1,2,3,4,5,6,7,8,9], choice_el(X,L), /* Выбирает из списка значение первого множителя */ choice_el(Y,L), /* Выбирает из списка значение второго множителя */ Z=X*Y, assertz(multiply (X,Y,Z)), /* Добавление факта в конец базы данных */ count(N), /* Чтение значения счетчика из динамической базы данных */ N1=N+1, /* Новое значение счетчика */ retract(count(N)), /* Удаление старого значения счетчика из динамической базы данных */ asserta(count(N1)), /* Добавление нового значения счетчика в динамическую базу данных */ N1=81. /* Проверка последней записи */ Как видно из примера, в динамической базе данных можно накапливать уже вычисленные ответы на вопросы. Пример 2: Формирование динамической базы данных «Читатель библиотеки» с клавиатуры и сохранение ее в файле. domains фамилия=string число,номер_билета=integer месяц=string дата_посещ=дата_посещ(число,месяц) database читатель(фамилия,номер_билета,дата_посещ) predicates повтор запись_в_базу ответ(char) goal clearwindow, write("Формирование б.д."),nl, retractall(_), /* Очистка динамической памяти */ повтор, write("Будете вводить новые факты? Y/N"), readchar(A), /* Ввод ответа, на экране не отображается */ upper_lower(Answer,A),nl, /* Преобразование маленькой буквы в большую*/ ответ(Answer), /* Определяет дальнейшую работу программы */ save("reader.dba"), /* Сохранение содержимого динамической базы данных в файле */ retractall(_). /* Очистка динамической памяти */ clauses повтор. повтор:-повтор. ответ('N'). ответ('Y'):-запись_в_базу, fail. ответ('_'):-fail. /* Если введен неверный ответ, повторяется вопрос */ запись_в_базу:-write("Фамилия: "), readln(Name), write("Номер билета: "), readint(Number), write("Число посещения: "), readint(Data), write("Месяц посещения: "), readln(Mounth), asserta(читатель(Name,Number,дата_посещ(Data,Mounth))). /* Сохранение введенной записи в динамической базе данных */ Пример 3: Определение количества читателей, посетивших библиотеку в марте, по информации, находящейся в файле reader.dba, сформированном в примере 2. domains фамилия=string число,номер_билета=integer месяц=string дата_посещ=дата_посещ(число,месяц) database читатель(фамилия,номер_билета,дата_посещ) счетчик(integer) predicates счет goal consult("reader.dba"), asserta(счетчик(0)), счет, счетчик(N), write("Число читателей= ",N), retractall(_). clauses счет:-читатель(_,_,дата_посещ(_,”март”)), счетчик(N), N1=N+1, retract(счетчик(N)), asserta(счетчик(N1)), fail. счет. 2.12 Экранные окна и создание меню Окно – это прямоугольная область на экране, ограниченная рамкой. Окно можно создать с помощью предиката makewindow(WN, ScrAttr, FrAttr, Caption, Row, Col, Height, Width), где • WN – целое число, определяет номер окна (нумерация начинается с 1); это число используется для в качестве ссылки в предикате gotowindow и др. • ScrAttr – целое число, определяет атрибут окна, который является суммой трех чисел (цвет текста, цвет фона, мерцание). Цвет текста может изменяться от 0 до 15, цвет фона – от 0 до 112 с шагом 16, мерцание – число 128. • FrAttr – целое число, определяет атрибут рамки. Если рамки нет, то атрибут равен 0. Значения от 1 до 8 соответствуют разным цветам рамки, а значения от -8 до -1 соответствуют разным цветам мерцающей рамки. • Caption – строка, определяет текст заголовка окна в верхней части рамки. Если строка пустая, то заголовок отсутствует. • Row, Col - целые числа, определяют строку и столбец верхнего левого угла создаваемого окна. В текстовом режиме на экране 25 строк и 80 столбцов. Нумерация строк идет слева направо, а столбцов – сверху вниз. • Height, Width - целые числа, высота и ширина окна, включая рамку. При создании окно заполняется цветом фона, а курсор устанавливается в его верхний левый угол. Пример 1: makewindow(1,4,1,“Menu”,4,20,16,40) создаст окно с номером 1, заголовком Menu. Цвет текста в окне будет красным, фон окна - черный (4=4+0+0), рамка – синего цвета (1). Левый верхний угол окна расположен в 4-ой строке и 20-ом столбце экрана, окно занимает 16 строк и 40 столбцов. Если все аргументы предиката makewindow являются неозначенными переменными, то им присваивается значение текущего окна. Когда окно создано, оно становится активным, и вся выводимая информация будет направляться в активное окно. При помощи предиката shiftwindow(WN) активным может быть назначено другое окно. При этом курсор устанавливается в позицию, в которой он был в момент предыдущего обращения к этому окну. Если аргумент предиката неозначен, то определяется номер активного окна. Для более быстрого переключения между окнами, содержащими большое количество текста, используется предикат gotowindow(WN). Этот предикат не сохраняет содержимое активного окна и не обновляет содержимое нового активного окна из буфера, поэтому при ипользовании этого предиката окна должны быть неперекрывающимися. Предикат removewindow удаляет активное окно, при этом активным становится окно, активизированное непосредственно перед удаляемым. При удалении окна содержимое экрана «за окном» автоматически восстанавливается. Предикат clearwindow, который ранее использовали для очистки экрана, очищает так же активное окно. Для перемещения курсора в нужную позицию окна можно использовать предикат cursor(Row,Col), где Row,Col – координаты курсора относительно верхнего левого угла окна. В случае неозначенности аргументов предиката, возвращаются координаты текущего положения курсора в активном окне. Для ввода и вывода текста в окна используются уже известные предикаты: write, nl, readchar, readint, readln, readreal, readterm. Ввод и вывод текста осуществляется в активное окно в текущую позицию курсора. Для задержки окна до нажатия любой клавиши можно в программе после активации окна добавить цели: write(“Для продолжения нажмите любую клавишу”), readchar(_), …………… Пример 2: Напишем предикат show_menu, который создает окно с главным меню, состоящим из трех пунктов. При выборе пользователем соответствующего пункта меню, появляется дочернее окно, в котором выполняются необходимые действия. По окончанию действий дочернее окно закрывается и снова можно выбирать пункты главного меню до тех пор, пока не будет выбран выход. predicates repeat process(integer) show_menu goal show_menu. clauses repeat. repeat:-repeat. show_menu:-repeat, makewindow(1,7,7,“Menu”,4,10,16,36),nl, write(“1 – процесс1”),nl, write(“2 – процесс2”),nl, write(“3 – выход”),nl,nl, write(“Введите Ваш выбор: (1-3)”), readint(X), X<4, process(X), X=0,!. process(3). process(1):- makewindow(2,7,7,“Процесс1”,12,36,10,36), ……………… write(“Для продолжения нажмите любую клавишу”), readchar(_), removewindow. process(2):- makewindow(3,7,7,“Процесс2”,10,40,10,36), ……………… write(“Для продолжения нажмите любую клавишу”), readchar(_), removewindow. 2.13 Операции над структурами данных 2.13.1 Деревья Списки часто используют для представления множеств. Но такое представление множеств имеет недостаток, заключающийся в том, что процедура проверки принадлежности элемента множеству оказывается неэффективной для множеств с большим количеством элементов. Если искомый элемент находится в конце списка или отсутствует в списке, процедуре придется просмотреть весь список. Для увеличения эффективности процедуры поиска применяют представление множеств в виде древовидных структур. Рассмотрим одну из таких структур – двоичное дерево. Дадим рекурсивное определение двоичного дерева. Двоичное дерево либо пусто, либо состоит из трех частей: корень, левое поддерево, правое поддерево. Корень может быть чем угодно, а поддеревья должны быть деревьями. Удобно определить двоичное дерево как функтор с тремя аргументами: корень и два поддерева и ввести обозначение для пустого дерева: nil. Тогда в программе можно описать следующий домен: domains tree=tree(root,tree,tree); nil Пример 1 Напишем предикат, проверяющий принадлежность элемента дереву. Дадим декларативное определение предиката. Элемент либо является корнем дерева, либо принадлежит левому поддереву, либо принадлежит правому поддереву. В программе опишем следующее двоичное дерево: Рисунок 17 – Дерево примера 1 domains tree=tree(root,tree,tree); nil root=integer predicates member_tree(integer,tree) answer(integer,tree) goal Tree=tree(5, tree(4, tree(8, tree(6,nil,nil), tree(2,nil,nil)), tree(3,nil,nil)), tree(1, tree(7,nil,nil), nil)), write("Введите элемент: "), readint(X), answer(X,Tree). clauses answer(X,Tree):-member_tree(X,Tree),!, write("Да"). answer(_,_):-write("Нет"). member_tree(X,tree(X,_,_)). member_tree(X,tree(_,Left,_)):-member_tree(X,Left). member_tree(X,tree(_,_,Right)):-member_tree(X,Right). Очевидно, что если элемент находится в самом низу дерева, процедура поиска становится такой же неэффективной, как и в случае списков. Введем отношение порядка между элементами множества. Тогда элементы множества можно упорядочить слева направо в соответствии с этим отношением. Выберем отношение «меньше» для упорядочивания элементов множества, содержащего целые числа. Двоичным справочником назовем непустое дерево, для которого выполняется: • все вершины левого поддерева меньше корня; • все вершины правого поддерева больше корня; • левое и правое поддеревья являются двоичными справочниками. Пример 2: Приведенное ниже дерево является двоичным справочником: Рисунок 18 – Двоичный справочник Пример 3: Модифицируем предикат поиска для двоичного справочника. Для поиска в двоичном справочнике достаточно просмотреть одно поддерево, предварительно сравнив искомый элемент с корнем. Алгоритм поиска в двоичном дереве будет иметь следующий вид: • если элемент совпадает с корнем дерева, то элемент найден; • если искомый элемент меньше корня, то следует искать в левом поддереве; • если искомый элемент больше корня, то следует искать в правом поддереве; • если справочник пуст, то поиск не удался. member_tree(X,tree(X,_,_)). member_tree(X,tree(Y,Left,_)):-Y>X,!, member_tree(X,Left). member_tree(X,tree(_,_,Right)):-member_tree(X,Right). Поиск элемента в двоичном справочнике эффективнее поиска в списке. Для списка в среднем будет просмотрена примерно половина элементов. Для справочника время поиска пропорционально глубине дерева – длине самого длинного пути между корнем и листом дерева. Для хорошо сбалансированных деревьев (левое и правое поддеревья должны содержать примерно одинаковое количество элементов) глубина дерева пропорциональна log n, где n – количество элементов в справочнике. Если происходит разбалансировка дерева, то фактически дерево превращается в список и его глубина становится близкой к n. 2.13.1.1 Отображение деревьев Если вывести дерево на экран предикатом write, то дерево выведется в виде прологовского терма, который сложно читать. Поэтому лучше написать предикат вывода дерева в специальной форме, чтобы была видна его структура. Проще всего отображать дерево в повернутой на 90 форме и отображать его не сверху вниз, а слева направо. Например, дерево из примера 1 п.2.13.1 отобразится в виде: Рисунок 19 – Отображение двоичного дерева Определим предикат show_tree(tree) для отображения на экране дерева слева направо. Опишем работу предиката: • отображает правое поддерево с отступом вправо; • выводит корень дерева; • отображает левое поддерево с отступом вправо. Для вывода дерева с заданным отступом определим предикат show_tree(tree, space), а для печати нужного количества пробелов – предикат print_blank(space). domains tree=tree(root,tree,tree); nil root=integer space=integer predicates show_tree(tree) show_tree(tree,space) print_blank(space) clauses show_tree(Tree):-show_tree(Tree,0). show_tree(nil,_). show_tree(tree(X,Left,Right),Space):- Space1=Space+4, show_tree(Right,Space1), print_blank(Space), write(X),nl, show_tree(Left,Space1). print_blank(0). print_blank(Space):- write(“ “), Space1=Space-1, print_blank(Space1). Попробуйте написать предикат, печатающий дерево сверху вниз. 2.13.1.2 Обходы деревьев Во многих приложениях, использующих бинарные деревья, требуется доступ к элементам дерева. Основой этого доступа является обход дерева в предписанном порядке. Имеются три возможности линейного упорядочивания при обходе: • сверху вниз (сначала корень дерева, затем вершины левого поддерева, после этого вершины правого поддерева); • слева направо (сначала вершины левого поддерева, затем корень, после этого вершины правого поддерева); • снизу вверх (сначала вершины левого поддерева, затем вершины правого поддерева, после этого корень). Пример 1: Для дерева из примера1 обход сверху вниз даст следующую последовательность вершин: 5, 4, 8, 6, 2, 3, 1, 7; обход слева направо даст: 6, 8, 2, 4, 3, 5, 7, 1; обход снизу вверх даст: 6, 2, 8, 3, 4, 7, 1,5. Опишем предикат uptodownround(tree,list), формирующий список из вершин, полученных при обходе дерева сверху вниз. Для соединения обходов поддеревьев и корня в обход дерева будем использовать предикат append(list,list,list), который соединяет два списка в третий. uptodownround(tree(X,Left,Right),S):- uptodownround(Left,Ls), uptodownround(Right,Rs), append([X|Ls],Rs,S). append([],S,S). append([Head|Tail],S,[Head|Tail1]):- append(Tail,S,Tail1). Очевидно, что все обходы будут отличаться только порядком соединения обходов поддеревьев и корня. Для обхода слева направо соединение обходов будет иметь вид: append(Ls,[X|Rs],S). А для обхода сверху вниз получим: append(Rs,[X],Rs1), append(Ls,Rs1,S). Перечисленные обходы используются для поиска минимального или максимального элемента в дереве, преобразовании дерева. 2.13.2 Графы Во многих приложениях для представления отношений, ситуаций, структур задач используют графы. Граф определяется множеством вершин и ребер. Каждое ребро соединяет две вершины. Если ребра направленные, то их называют дугами. Графы с ребрами – дугами называются направленными. Ребрам могут быть приписаны стоимости, тогда граф называется взвешенным. В Прологе граф можно представить в виде отдельных предложений об имеющихся ребрах или описать граф как список ребер и список вершин, объединенных функтором graph (в случае если каждая вершина соединена хотя бы с оной вершиной, список вершин можно опустить, т.к. он неявно содержится в списке ребер). Пример 1: Рассмотрим различные способы описания графа, представленного следующим рисунком: Рисунок 20 – Граф из примера 1 В первом случае имеем описание: edge(a,b). edge(a,d). edge(a,e). edge(b,e). edge(c,d). edge(c,e). edge(d,e). Во втором случае граф опишется как структура: domains vertex=symbol edge= edge(vertex,vertex) list_vertex=vertex* list_edge=edge* graph= graph(list_vertex,list_edge) Тогда граф из примера 1 можно описать как G=graph([a,b,c,d,e],[edge(a,b), edge(a,d), edge(a,e), edge(b,e), edge(c,d), edge(c,e), edge(d,e)]). Способ представления графа зависит от конкретной задачи и от выполняемых операций над графами. Пример 2: Определим предикат path(A,Z,Path), который будет находить ациклический путь Path (список вершин, в котором каждая вершина присутствует только один раз) из вершины A в вершину Z. Для графа из примера 1 верны следующие предикаты: path(a,c,[a,b,c]) path(a,c,[a,b,e,c]) path(a,c,[a,d,c]) path(a,c,[a,d,e,c]) path(a,c,[a,d,e,b,c]) path(a,c,[a,e,d,c]) path(a,c,[a,e,b,c]) Опишем предикат path: • если вершины A и Z совпадают, то список Path состоит из одной вершины; • в противном случае находим ациклический путь Path1 из какой-нибудь вершины Y в Z, а затем ациклический путь из A в Y, не содержащий вершин из Path1. Рисунок 21 – Поиск ациклического пути domains vertex=symbol path=vertex* predicates member(vertex,path) neighbour(vertex,vertex) edge(vertex,vertex) path(vertex,vertex,path) path1(vertex,path,path) find_path(vertex,vertex) edge(vertex,vertex) goal write("Введите начальную вершину\n"), readln(A), write("Введите конечную вершину\n"), readln(B), find_path(A,B). clauses edge(a,b). edge(a,d). edge(a,e). edge(b,e). edge(c,d). edge(c,e). edge(e,d). edge(d,e). find_path(A,B):-path(A,B,Path),!, write("Путь=",Path). find_path(_,_):-write("Пути нет"). path(A,Z,Path):-path1(A,[Z],Path). path1(A,[A|Path1],[A|Path1]). path1(A,[Y|Path1],Path):- neighbour(X,Y), not(member(X,Path1)), path1(A,[X,Y|Path1],Path). member(X,[X|_]). member(X,[_|Tail]):-member(X,Tail). neighbour(X,Y):-edge(X,Y); edge(Y,X). Заметим, что данная программа находит первый попавшийся путь из вершины A в B. Предикат path можно использовать для решения разнообразных задач. Например, для поиска всех вершин, достижимых из заданной, для поиска пути заданной длины от выделенной вершины, для нахождения диаметра графа (максимального расстояния между двумя вершинами), гамильтонова цикла (цикла, проходящего через все вершины), количества компонент связности графа. При решении этих задач удобно использовать для обмена значениями между предикатами динамическую базу данных. Пример 3: Модифицируем приведенную в примере 2 программу для поиска пути минимальной стоимости между двумя вершинами во взвешенном графе. domains vertex=symbol path=vertex* length_path=integer weigth=integer database bd_path(path,length_path) predicates member(vertex,path) neighbour(vertex,vertex, weigth) edge(vertex,vertex,weigth) path(vertex,vertex,path,length_path) path1(vertex,path, length_path,path,length_path) find_begining(vertex,vertex) find_path(vertex,vertex) edge(vertex,vertex) goal write("Введите начальную вершину\n"), readln(A), write("Введите конечную вершину\n"), readln(B), find_begining(A,B), find_path(A,B), bd_path(Path,Length), write("Путь=",Path,”Длина=”,Length), retractall(_). clauses find_begining(A,Z):- path(A,Z,Path,Length), assertz(bd_path(Path,Length)). path(A,Z,Path,Length):-path1(A,[Z],0,Path,Length). path1(A,[A|Path1],Length,[A|Path1], Length). path1(A,[Y|Path1],Length1,Path,Length):- neighbour(X,Y,Weigth), not(member(X,Path1)), Length2=Length1+1+Weigth; path1(A,[X,Y|Path1],Length2,Path,Length). member(X,[X|_]). member(X,[_|Tail]):-member(X,Tail). neighbour(X,Y):-edge(X,Y); edge(Y,X). find_path(A,B):- bd_path(Path,Length), path(A,B,Path1,Length1), Length10, edge(X,Y), not(member(X,Path1)), Length1= Length-1 path1_depth(A,[X,Y|Path1],Path, Length). 2.14.2 Стратегия поиска в ширину При поиске в ширину в первую очередь осуществляется переход в вершины, наиболее близкие к стартовой. Реализация такого поиска является более сложной задачей, т.к. необходимо сохранять все множество путей-кандидатов. Каждый путь-кандидат будет представлять список вершин в обратном порядке (т.е. стартовая вершина будет последним элементом, а последняя порожденная вершина будет головой списка). Все пути-кандидаты будут храниться в списке. Первоначально список путей-кандидатов содержит один элемент [A], где A – стартовая вершина. Опишем поиск в ширину: • если голова первого пути – это целевая вершина, то этот путь является решением; • в противном случае, удаляем первый путь из множества путей-кандидатов, порождаем множество всех возможных продолжений этого пути на один шаг, добавляем множество продолжений в конец множества-кандидатов и продолжаем поиск в ширину для нового множества- кандидатов. path_breadth(A,Z,Path):-path1_breadth(Z,[[A]],Path). path1_breadth(Z,[[Z|Path1]|_],[Z|Path1]). path1_breadth(Z,[[Y|Path1]|Path2],Path):- findall([Y1,Y|Path1],continue(Y,Y1,Path1),New_path), append(Path2,New_path,Path3),!, path1_breadth(Z,Path3,Path). path1_breadth(Z,[_|Path2],Path):- path1_breadth(Z,Path2,Path). continue(X,Y,Path):- edge(X,Y), not(member(Y,Path)). Стратегия поиска в ширину гарантирует получение кратчайшего пути первым, что не всегда верно в случае поиска в глубину. Однако, для взвешенного графа поиска в ширину будет недостаточно, в этом случае используют поиск с предпочтением. В случае больших пространств состояний существует опасность комбинаторного взрыва, т.к. с увеличением длин путей наблюдается экспоненциальный рост объема множества путей-кандидатов. В этом случае для управления поиском решений используют эвристики – информацию для управления поиском решений в конкретной предметной области. 2.15. Вопросы и задания для самоконтроля 1) Что такое Пролог-программа? 2) Какие типы предложений бывают в ПРОЛОГе? 3) Для дерева семейных отношений из п.2.1 введите отношения "мужчина", "женщина" в форме фактов. С помощью правил определите отношения "отец", "сестра", "тетя", "иметь двух детей". Определите следующие внешние цели для ответов на вопросы: a) Кто отец Лиз? b) Кто сестра Боба? c) Есть ли сестра у Лиз? d) Есть ли тетя у Энн? e) У кого двое детей? 4) Из каких разделов состоит Пролог-программа. 5) Как происходит поиск решений Пролог-системой? 6) Что такое унификация и когда она успешна? 7) Что такое терм? 8) Какие предикаты существуют в ПРОЛОГе для организации ввода-вывода? Почему эти предикаты называются внелогическими? 9) Чем отличается поиск в случаях внешней и внутренней цели? 10) Поясните декларативный и процедурный смысл Пролог-программы. 11) Напишите предикат, который печатает в порядке возрастания все целые числа из диапазона, границы которого вводятся с клавиатуры. 12) Что такое отсечение? Для чего они используются? Какие бывают отсечения? 13) Для чего используется предикат fail? 14) Как можно организовать цикл, управляемый отказом? 15) Что называется списком? Как список представляется в ПРОЛОГе? Как разделить список на хвост и голову? 16) Определите предикат, добавляющий элемент в конец списка целых чисел. 17) Определите предикат, исключающий отрицательные элементы из списка. 18) Определите предикат, обращающий список целых чисел. 19) Что называется строкой? Какие предикаты для работы со строками Вы знаете? 20) Как организовать работу с файлами в ПРОЛОГе? 21) Что такое динамическая база данных? Для чего она используется? Какие предикаты для работы с динамической базой данных Вы знаете? 22) Как организовать цикл со счетчиком, используя динамическую базу данных? 23) Что такое двоичное дерево? Как описать двоичное дерево? 24) Какие существуют обходы двоичного дерева? 25) Как представить граф в ПРОЛОГе? 26) Какие стратегии поиска решения можно использовать при написании программ на ПРОЛОГе? Ответы на задания для самоконтроля Глава 1 2). a) (+ (quote 2) (* 3 4)) b) ошибка, нельзя сложить число и список c) ошибка, знак * не воспринимается как операция d) 24 e) (quote quote) 3). a) 3 b) 1 c) 0 d) 1 4). a) ((a b) c d) b) (3 + 4 6) c) ((+ 1 2) . 10) d) ((a (b c))) 5). a) (cadr (cadaar ‘(((4 (6 3)) 8) 7)) b) (cadr (cdaadr ‘(1 (((2 3) (4 5) 6) (7)))) c) (car (caadar ‘((5 ((12) 23 34)))) 7). a) (atom ‘()) –> nil b) (equal ‘(a b) ‘((a) b)) –> nil c) (null ‘(3 4)) –> ni d) (numberp 1) –>t e) (listp ‘(a)) –> t 10). a) ((lambda (x y) (-(* x y) x y)) 2 4) b) ((lambda (x y) (+ (- (* x x) (* 2 x)) (*y y)) 2 4) Глава 2 3). отец(X,Y):–родитель(X,Y), мужчина(X). сестра(X,Y):–родитель(Z,X), родитель(Z,Y),X<>Y,женщина(X). тетя(X,Y):–родитель(Z,Y),сестра(X,Z). двое_детей(X):– родитель(X,Y),родитель(X,Z), YX,W<>Y. Цели: отец(X,лиз) сестра(X,боб) сестра(_,лиз) тетя(_,энн) двое_детей(X) 11). вывод(A,B):–B>A. вывод(A,B):–write(A, “ ”), A1=A+1,вывод(A1,B). 16). добав_конец([],X,[X]). добав_конец([Head|Tail],X,[Head|Tail1]):– добав_конец(Tail,X, Tail1). 17). удал_отр([],[]). удал_отр([Head|Tail],[Head|Tail1]):-Head>=0, удал_отр(Tail,Tail1). удал_отр([_|Tail],Tail1):– удал_отр(Tail,Tail1). 18). обратить([],L,L). обратить([Head|Tail],L2,L3):– обратить(Tail,[Head|L2],L3). При обращении к предикату на месте второго аргумента находится пустой список, третий аргумент – результат обращения. Рекомендуемая литература 1. Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта. – М.: Мир, 1990.- 569 с. 2. Ин Ц., Соломон Д. Использование Турбо-Пролога. – М.: Мир, 1993. – 608 с. 3. Стерлинг Л., Шапиро Э. Искусство программирования на языке ПРОЛОГ. – М.: Мир, 1990. – 235 с. 4. Хювенен Э., Сеппянен Й. Мир Лиспа. т.1. Введение в язык Лисп и функциональное программирование. – М.: Мир, 1990. – 447 с. 5. Хювенен Э., Сеппянен Й. Мир Лиспа. т.2. Методы и системы программирования. – М.: Мир, 1990. – 319 с.