- •Функциональное и логическое программирование
- •Глава 1. Классификация языков и стилей программирования 3
- •Глава 2. Программирование на языКе лисп 16
- •Глава 3. Программирование на языке пролог 89
- •Глава 1. Классификация языков и стилей программирования
- •Основные парадигмы программирования
- •Процедурное (императивное, директивное) программирование.
- •Объектно-ориентированное программирование.
- •Декларативное программирование
- •Логическое программирование.
- •Функциональное программирование.
- •Классификация языков программирования
- •Функциональные языки
- •Логические языки
- •Глава 2. Программирование на языКе лисп
- •История создания языка Лисп
- •Диалекты языка Лисп
- •Лисп-машины
- •Область применения языка Лисп
- •Особенности языка Лисп Одинаковая форма данных и программ
- •Хранение данных, не зависящее от места
- •Автоматическое и динамическое управление памятью
- •Функциональная направленность
- •Динамическая проверка типов
- •Интерпретирующий и компилирующий режимы работы;
- •Пошаговое программирование
- •Единый системный и прикладной язык программирования
- •Основы языка Лисп
- •Понятие функции.
- •Quote блокирует вычисления
- •Базовые функции языка.
- •Функция car возвращает в качестве значения первый элемент списка.
- •Функция cdr - возвращает в качестве значения хвостовую часть списка, т. Е. Список, получаемый из исходного списка после удаления из него головного элемента:
- •Функция cons включает новый элемент в начало списка:
- •Предикат equal проверяет идентичность записей:
- •Предикат equalp проверяет наиболее общее логическое равенство:
- •Другие простейшие встроенные функции Лиспа. Функция null проверяет, является ли аргумент пустым списком:
- •Комбинации вызовов car и cdr позволяют получить любой элемент списка:
- •Наиболее общая функция, выделяющая n-й элемент списка (при этом индексация начинается с 0):
- •Функция last позволяет выделить последний элемент списка:
- •Функция list - создает список из элементов:
- •Функция setq – невычисляющее присваивание:
- •Функция setf - обобщенная функция присваивания:
- •Функции, обладающие побочным эффектом, называются псевдофункциями.
- •С символом можно связать именованные свойства:
- •Функция get - возвращает значение свойства, связанного с символом:
- •Псевдофункция remprop удаляет свойство и его значение:
- •Вызов интерпретатора eval вычисляет значение выражения.
- •Ввод и вывод.
- •Использование файлов.
- •Определение функций
- •Задание параметров в лямбда-списке.
- •Передача параметров и область их действия.
- •Вычисления в лисПе.
- •Предложение let создает локальную связь внутри формы:
- •Последовательные вычисления.
- •Разветвление вычислений.
- •Циклические вычисления.
- •Передача управления.
- •Другие циклические структуры.
- •Динамическое управление из другого контекста
- •Внутреннее представление списков
- •Функциональное программирование Рекурсия. Различные виды рекурсии.
- •Функции более высокого порядка.
- •Применяющие функционалы.
- •Отображающие функционалы.
- •Макросы
- •Типы данных
- •Основные типы данных:
- •Глава 3. Программирование на языке пролог
- •Общие сведения о языке Пролог. Язык Пролог как система, реализующая логический вывод в исчислении предикатов первого порядка.
- •Фразы Хорна как средство представления знаний.
- •Синтаксис языка Пролог.
- •Фразы, термы, факты, правила.
- •Константы:
- •Простейшая программа на Прологе
- •Выполнение запроса в Прологе.
- •Неудача запроса и возврат назад.
- •Декларативная и процедурная семантика Пролога.
- •Рекурсивные процедуры.
- •Списки.
- •Операторы.
- •Средства управления ходом выполнения программы. Предикат сократить (отсечение).
- •Отрицание как неудача запроса.
- •Встроенные предикаты.
- •Типы отношений.
- •Ограничения, обеспечивающие целостность отношений.
- •Свойства отношений.
- •Подходы к программированию на языке Пролог.
Неудача запроса и возврат назад.
Если активный запрос достигнет конца соответствующего множества фраз, то он завершится неудачей. Если активный запрос является подцелью составного запроса и не является первой подцелью, то интерпретатор возвратится назад, чтобы повторно проанализировать предыдущую подцель составного запроса. Когда интерпретатор возвращается назад, то ликвидируются все конкретизации переменных, выполненные последним активным запросом. Если же активный запрос является первой подцелью составного запроса, то неудача активного запроса приводит к неудаче всего составного запроса.
Указание интерпретатору вернуться назад - ввод символа «;». Вод символа «;» означает отказ от только что полученного ответа. Это заставляет интерпретатор возвратиться назад и приступить к поиску другого ответа, т.е. ввод этого символа приводит к неудаче запроса, активированного самым последним (запроса, расположенного в вершине стека). Интерпретатор приступает к повторной обработке последнего запроса, начиная со следующей фразы, причем отменяются предыдущие конкретизации переменных.
В нашем примере в этом случае подцель «отец», стоящая в вершине стека, принудительно делается неудачной, а конкретизация переменной X, осуществленная при последнем успехе этой цели, теряет свою силу. Интерпретатор делает попытку согласовать данную подцель со следующей доступной фразой «отец». В результате X конкретизируется значением «саша». Выводится новое значение X=саша. При поиске третьего ответа данная конкретизация переменной отменяется. Но теперь подцель «отец» достигла конца множества фраз «отец». В этом месте запрос «отец» терпит неудачу и удаляется из стека.
Затем интерпретатор возвращается назад к предыдущей подцели составного запроса, т.е. к «брат(вася, С)». Возврат вызывает замену последнего успеха подцели «брат» на неудачу, при этом конкретизация переменной С теряет свою силу. Однако же теперь запрос «брат» достиг конца множества фраз «брат». Поэтому подцель «брат» удаляется из стека. Поскольку это была первая подцель в теле правила «дядя», то и все правило терпит неудачу. Интерпретатор возвращается назад и ищет другую фразу «дядя». Но он достиг конца множества фраз «дядя». В итоге запрос «дядя» терпит неудачу и удаляется из стека. Интерпретатор выдает ответ «нет». Это означает, что он больше не может отыскать позитивного ответа на запрос.
Декларативная и процедурная семантика Пролога.
Смысл фразы языка Пролог может быть понят либо с позиций декларативного подхода, либо с позиций процедурного подхода. Декларативный смысл подчеркивает статическое существование отношений.
Порядок следования подцелей в правиле не влияет на декларативный смысл этого правила. Декларативная семантика Пролога определяет, является ли целевое утверждение истинным, исходя из данной программы, и если оно истинно, то для какой конкретизации переменных. Запятая между целями означает их конъюнкцию, а точка с запятой - дизъюнкцию целей. Запятая связывает сильнее, чем точка с запятой. Правило, содержащее операции дизъюнкции, можно разбить на несколько правил.
При процедурной трактовке Пролог программы подчеркивается последовательность шагов, которые выполняет интерпретатор при обработке запроса. Таким образом, приобретает значение порядок следования подцелей в правиле.
Множество фраз, имеющих одно и то же имя и одинаковое количество аргументов, можно рассматривать как процедуру, при этом запрос (или подцель правила) является вызовом процедуры. Когда интерпретатор обрабатывает запрос к процедуре, он анализирует фразы, образующие процедуру, в том порядке, как они в ней представлены. Порядок целей и предложений может существенно повлиять на эффективность программы; неудачный порядок может привести к бесконечным рекурсивным вызовам.
Эффективность декларативно правильной программы можно улучшить, изменяя порядок предложений и целей при сохранении ее декларативной правильности.
Переупорядочивание - один из методов предотвращения зацикливания. Кроме переупорядочивания существуют и другие, более общие методы предотвращения зацикливания, способствующие получению процедурно правильных программ.