- •Функциональное и логическое программирование
- •Глава 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. Программирование на языке пролог
- •Общие сведения о языке Пролог. Язык Пролог как система, реализующая логический вывод в исчислении предикатов первого порядка.
- •Фразы Хорна как средство представления знаний.
- •Синтаксис языка Пролог.
- •Фразы, термы, факты, правила.
- •Константы:
- •Простейшая программа на Прологе
- •Выполнение запроса в Прологе.
- •Неудача запроса и возврат назад.
- •Декларативная и процедурная семантика Пролога.
- •Рекурсивные процедуры.
- •Списки.
- •Операторы.
- •Средства управления ходом выполнения программы. Предикат сократить (отсечение).
- •Отрицание как неудача запроса.
- •Встроенные предикаты.
- •Типы отношений.
- •Ограничения, обеспечивающие целостность отношений.
- •Свойства отношений.
- •Подходы к программированию на языке Пролог.
Фразы Хорна как средство представления знаний.
Конечной целью составления любой компьютерной программы является создание инструмента для решения задачи из некоторой прикладной области. Прикладная область - это некоторая абстрактная часть мира, или область знаний. Структура прикладной области состоит из значимых для этой области сущностей, функций и отношений.
Процесс составления программы, моделирующей структуру прикладной области, состоит из описания этой структуры в виде логической спецификации данной области и собственно написания программы, реализующей эту логическую спецификацию. Причем отношение, существующее между некоторыми объектами прикладной области, должно соблюдаться и для обозначений, которые представляют эти объекты в программе.
Написание программы на Прологе состоит в следующем:
анализ значимых сущностей, функций и отношений из прикладной области и выбор обозначений для них, по возможности, отражающих их смысл;
семантическое определение значимых функций и отношений (для отношений указывается, какие конкретные их реализации дают «истину», а какие - «ложь»);
аксиоматическое определение каждого отношения при помощи фраз Пролога. Программа на Прологе, моделирующая структуру предметной области, является множеством аксиоматических определений всех значимых для заданной предметной области отношений;
для выполнения запросов к множеству фраз программы применяется интерпретатор Пролога, который выполняет логические выводы из декларативной части программы.
Таким образом, алгоритм решения задач из прикладной области представляет собой совокупность из запроса, множества фраз программы и интерпретатора языка.
При составлении Пролог-программы мы реализуем представление знаний о данной области, а фразы Пролога можно рассматривать как язык представления знаний.
Синтаксис языка Пролог.
На Прологе фразы Хорна записываются следующим образом:
заключение:-
условие1,
условие2,...,
условие N,
где «:-» - это «если», а «,» - это логическое «И» (конъюнкция).
Главным компонентом интерпретатора языка Пролог является универсальный механизм решения задач, основанный на правиле резолюции Робинсона.
Программист описывает задачу с помощью фраз Хорна, выраженных на языке Пролог. В каждой фразе формулируется некоторое отношение между термами. Терм - это обозначение, представляющее некоторую сущность предметной области.
Чтобы привести в действие данный механизм решения задач, программист должен написать запрос, согласно которому необходимо выяснить, является ли конкретная атомарная формула следствием текущего множества фраз, представленных в программе.
Простейшей фразой Хорна может служить некоторый факт, состоящий из заключения, за которым не следуют никакие условия, например «Оля – здорова»:
здоров (Оля).
Правило - это иная форма записи фразы Хорна, показывающая зависимость одного факта от других, например «Оля получает мороженое, если она здорова»:
получать_мороженое(оля):-
здоров(оля).
Направление вывода: если уже известно, что Оля здорова, то правило дает дополнительное знание о том, что она получает мороженое. Слово «оля» - это обозначение константы, представляющей некоторый конкретный объект в мире данной программы. Приведенные правило и факт содержат явные знания, относящиеся к человеку по имени «Оля».
Переменная в Прологе записывается как слово, начинающееся с большой буквы. Правило «получать_мороженое» можно обобщить на всех здоровых, если константу «оля» заменить на переменную:
получать_мороженое(X):-
здоров(X). (Все здоровые получают мороженое).
Переменная X согласуется с любой константой, поэтому данное правило можно применять для доказательства того, что любой здоровый человек получает мороженое.
Это правило содержит переменные и поэтому выражает неявные знания, относящиеся ко всем здоровым людям.
Заметим, что приведенные правила являются объявлениями отношений между объектами. Пролог-программы почти полностью состоят из таких объявлений. В программах , написанных на языке Пролог, не употребляются управляющие структуры, задающие порядок выполнения программы.
Программист перекладывает на интерпретатор многие решения, касающиеся хода выполнения программы. В этом заключается декларативный смысл Пролога. Некоторые из языков запросов к базам данных (SQL) также декларативны: пользователь лишь указывает, какой тип ответа требуется, а интерпретатор языка запросов сам решает, как получить ответ.