Функциональное и логическое программирование (2 семестра, 2 экзамена) Мурашко Игорь Александрович

Мурашко Игорь Александрович 215

Функциональное и логическое программирование (2 семестра, 2 экзамена)

Литература

1. Хендерсон Н. Функциональное программирование. Применение и реализация.

Москва Мир 1888 г.

2. Хювененд Р., Сеппянен Й. Мир LISPа в 2 т. 1990 г.

3. Приобретение знаний под ред. Осуга С., Саэка Ю. Мир 1990 г.

4. Tourzetsky David S. Common LISP.

5. Ктицкий С. В. Программирование на языке LISP. РТИ 1991 г. Методичка

6. Прихожий А.А. Функциональное и логческое программирование. Минск БГУИР, 1998г.

7. www.lisp.org

8. www.cons.org, www.franz.com

ТЕМА 1. ВВЕДЕНИЕ В ФУНКЦИОНАЛЬНОЕ И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

LISP разработан в 8 г .Джоном Маккарти (Mc Carthy). Название происходит от слов List Processing. Представляет собой язык функционального программирование. Основан на алгебре списочных структур лямбда-исчислении и теории рекурсивных функций. На нем написаны программа управления космическим телескопом, программа автоматического уста=ранения неполадок и реконфигурации сети спутников Deep Space, система планирования воздушных атак министерства обороны США, АСУ сборочных конвейеров FORD MOTOR. В мин обороны США исполэуются только Ада и Лисп. В САПР AutoCad обработка математики реализована на Лисп.

Особенности языка LISP:

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

программы строятся из логически расчлененных определений функций.

наиболее эффективен при проведении рекурсивных вычислений

кроме функционального программирования в Лиспе можно использовать обычное.

2. язык изначально являлся интерпретатором. В настоящее время все коммерческие версии имеют оптимизирующие компиляторы. Скорость исполняемого кода, как правило, ниже, чем у обычных языков. Однако код получается более компактным.

3. Лисп – язык с динамической инициализацией. В нем типы привязываются к значению переменной, а не к её имени. Это позволяет подставлять различные списки и массивы. Типов очень много. Функции могут передаваться как параметры, модифицироваться и изменяться как значения. Компилятор можно вызывать из исполняемой программы на лету. Это свойство было использовано при обновлении системы электронной коммерции.

4. Объектная система Лиспа CLOS (Common Lisp Object System). Методы могут привязываться сразу к нескольким различным классам.

5. Автоматическое и динамическое управление памятью. Память освобожнается по мере надобности.

Предназначен для создания систем ИИ, ввод-вывод речи и изображений, экспертные ситемы.

НЕМНОГО ИСТОРИИ

Языки программирования искуственного интеллекта.

Классификация языков и стилей программирования.

1. процедурные

2. декларативные

Прцедурная программа состоит из последовательности операторов (присваивания, передачи управления, условные, цикла) и предложений. Значения сохраняются в некоторой переменной.

В логическом программировании используется логика предикатов в форме фраз Хорна.

Функциональная программа состоит из совокупности определений функций. Функции представляют собой вызовы других функций и предложений, управляющих последовательностью вызовов. Вычисления начинаются с вызова некоторой функции, которая в свою очередь вызывает другие функции, входящии в её определение. Часту, функции прямо или косвенно вызывают сами себя. Каждый вызов возвращает некоторое значение в вызвавшую её функцию. Теоретически , функциональное управление не признает присваиваний и передачу управления. Ветвление вычислений основано на механизме обработки аргументов условного предложения. Повторное многократное вычисление осуществляется через рекурсию, которая является основным средством.

ЯЗЫКИ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ

Лисп разраьотан в Стэнфорде Джоном Маккарти. Первоначально он должен был включить в себя средства работы с матрицами, указателями и т.д. Рассматривался как ассемблер для работы сос списками. С момента своей разработки было много попыток модифицировать язык. В начале 70-ч были созданы мощные Лисп-системы: МакЛисп, ИнтерЛисп, после чего прекратились попытки создания нового языка.

Развитие языка пошло по 2 основным направлениям – стандартизация и создание коцептуально новых языков для представления и манипулирования знаниями в Лисп-среде. В настоящее время Лисп реализован на всех классах ЭВМ. От персональной до суперкомпьютеров.

Кроме Лиспа разрабатывались языки Снобол и Рефал, также предназначенные для символьной обработки информации. Группа языков, ориентированных на решение проблем (ИИ) – Планер, КюА-4,КюЛисп,Конивер. Они обладают усложненной структурой представления знаний. Сам Лисп разрабатывался различными учреждениями и имеет несколько диалектов.

Диалекты языка Лисп:

1. MacLisp. Кроме символьной обработки широко развиты числовые вычисления. На нем написана алгебраическая система Maxima. Матричная и битовая обработка. Широкий набор арифметических функций. Возможность вычислений с неограниченной точностью. MacLisp был первой системой, для которой создан хороший транисляор. Особое внимание сосредоточено на эффективности. Скорость работы в 2 раза выше, чем у ИнтерЛиспа. MacLisp был исследовательской системой и не предназначался для коммерческого использования.

2. Мю-Лисп. MuLisp-85 разработан специально для IBM PC. Посравнению с CommonLisp не имеет такого широкого спектра доступных типов данных. В нем обеспечивается работы только с целыми числами с любым основанием и рациональными числами. Отсутствуют средства работы со структурами, массивами, потоками. Однако, он имеет возможность подключения подпрограмм для пополнения набора. Не имеет редактора текста.

3. InterLisp. Появился в 1972 г. К 1978 г. он представлял интегрированную среду программирования, в которую вошло множество вспомогательных средств. Этот язык стал классическим примером хорошо развитых программных средств в системах разделения времени. В 1974 г. компания Xerox начала разработку для InterLisp специальной рабочей станции Alta. Аппаратура проектировалась под систему программирования.

4. TransLisp. Предназначен для рабочих станций

5. -Lisp . Создан в MIT. В 79 году на основе проекта появились две фирмы, изготавливавшие Lisp-машины – Simbolic, Lisp mashine.