Лекции в ворде

33

СОДЕРЖАНИЕ

1. Рабочая программа курса 4

2. Содержание курса 5

3. Основная и дополнительная литература 5

4. Конспект лекций 6

5. Ответы к некоторым упражнениям 39

6. Приложение1. Краткое введение в систему muLISP.

Команды редактора 43

1. Приложение2. Краткое описание функций muLISP 46

Рабочая программа курса для студентов заочной формы обучения

специальности 22.02.03 "Функциональное программирование. Аппликативный язык ЛИСП”.

Структура курса:

Семестр 4

Всего часов

Всего: ауд./с.р. /20

Лекции 8/–

Лабораторная работа 4/ 12

Курсовая работа –/–

Формы контроля зачет

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

Задачи курса.

Студент должен усвоить:

– суть и смысл функционального подхода к решению сложных задач и его отличие от процедурной парадигмы;

– композицию функции высокого порядка, аргументами которой являются функции более низкого порядка;

– принципы рекурсивного определения функций;

– основные принципы программирования на языке ЛИСП

– понятие программирования, управляемого данными.

Студент должен научиться:

– декомпозировать задачу на подзадачи, связывать их с примитивными функциями и синтезировать исходную задачу;

– использовать библиотечные примитивы и создавать собственные библиотеки примитивов для использования их при проектировании внешних приложений;

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

– Алгебра функций, отображения.

– Основы программирования.

– Информатика.

Содержание курса

Тема 1.Функции и программы (2 часа)

Процедурный подход, функциональное и логическое программирование. Введение в функции. Императивность языков высокого уровня. Нефункциональность императивных языков.

Тема 2. Строго функциональный язык (2 часа)

Символьные данные, элементарные селекторы и конструкторы. Рекурсивные функции. Функции высших порядков.

Тема 3. Математические основы -исчисления

Определения. Вычисление -выражений. Редукция -выражений, порядок редукций и нормальные формы. Теорема Черча-Россера.

Тема 4. Основы языка ЛИСП. (4 чача).

Символы и структуры. Префиксная форма записи. Базовые функции. Имя и значение функции. Определение функций.

Тема 5. Передача параметров и область их действия. (2 часа).

Передача параметров по значению. Динамическая и статическая области действия. Вычисления в ЛИСП’е:

- работа с контекстом;

- последовательное исполнение;

- разветвление;

- итерации;

Тема 6. Внутреннее представление списков. (2 часа).

Представление лисповской памяти из списочных ячеек. Представление значения указателем. Свойства функций CAR, CDR и CONS. Управление памятью и сборка мусора.

Тема 7. Свойства символа. Ввод и вывод. (2 часа).

Системные и определяемые свойства. Чтение свойства. Присваивание свойства . Удаление свойства.

Функции ввода и вывода в Лиспе, организация диалога.

Тема 8. Формы рекурсии. (2 часа).

Параллельная рекурсия. Взаимная рекурсия. Рекурсия более высокого порядка.

Практические занятия

Лабораторная работа №1. Лисп-интерпретатор. Среда Mulisp. Использование встроенных функций CDR, CAR. (4 часа)

Лабораторная работа №2. Рекурсия. Параллельная рекурсия. (4 часа).

Лабораторная работа №3. Функции высокого порядка (4 часа).

Лабораторная работа №4. Структуры данных. Ввод/вывод. (4часа).

Основная и дополнительная литература

Основной список:

1.. Хендерсон П. Функциональное программирование. -М.: Мир, 1983,-349 с.

1. Филд А., Харрисон П. Функциональное программирование. -М: Мир, 1993.

2. Вольфенгаген В.Э., Горюнова И.А. Методы и средства построения систем знаний. -М.: МИФИ, 1992.

Дополнительный список:

1. Хювенен Э., Сеппянен Й. Мир Лиспа. -М.: Мир, т.т.1,2, 1990.

Конспект лекций

Тема 1. Функции и программы

 Императивность языков высокого уровня.

Традиционные вычисления основаны на последовательном выполнении инструкций, которые, возможно являются иерархически упорядоченными, с хранением промежуточных результатов. Скрывая многие низкоуровневые детали машинной архитектуры, традиционные языки высокого уровня облегчают программисту задачу концентрировать внимание на проблемах более высокого уровня абстракции. Однако остается в силе тот факт, что традиционные языки все-таки предоставляют технику программирования, которая основана на обеспечении того, как данная проблема должна быть решена на компьютере. Иными словами, программист должен помнить об организации вычислений, и тогда он сможет написать правильную последовательность инструкций для решения задачи. Это значит, что основная идея процесса программирования сводится к правильному описанию решения проблемы, а не к проблеме как таковой. Такие языки называются императивными, поскольку каждое утверждение в программе является указанием того, что необходимо выполнить на каждом последующем шаге.

Другое направление развития языков программирования более основано на абстрактной спецификации проблем, чем на описании методов их решения. К таким языкам относят функциональные языки, или аппликативные. Функциональная программа строится из "чистых" функций, которые лишены побочных эффектов, присущих императивным программам. Это значит, что их вычисления не могут изменить среду вычисления: величина, которая должна быть вычислена программой и сама программа сводятся к одному и тому же результату. Выполнение программы становится процессом изменения формы требуемой итоговой величины. В этом смысле "2+5" можно заменить на 7, при этом обе формы будут обозначать одну и ту же величину.

 Функции и программы.

Функция – правило, сопоставляющее элементы одного множества одному элементу из другого множества Функции и программы

Примеры представления функции:

квадрат(x) =х*х;

Можно переопределить функцию как результат применения некоторого правила (f) к своим аргументам. С позиций программирования использование функции означает вызов некоторой процедуры с передачей фактических параметров (аргументов) и возвратом результата. С другой стороны, если принять некоторую функцию, ранее построенную, в качестве базовой, то в соответствии с хорошим тоном программирования на базе такого примитива можно построить более сложную программную конструкцию. Приведенная выше функция макс определена как функция двух аргументов. Поставим вопрос, возможно ли определить наибольшее из трех или более чисел с помощью заданной функции макс. Введем следующее очевидное определение

наиб(x,y,z) макс(макс(x,y),z).

Ясно, что степень вложения может быть любой. Таким образом композиция осуществляется функцией самой собой. Например, наибольшее из шести вещественных чисел a,b,c,d,e,f может осуществляться из следующей композиции:

макс(наиб(a,b,c),наиб(d,e,f)),

наиб(макс(a,b),макс(c,d),макс(e,f)),

макс(макс(макс(a,b),макс(c,d)),макс(e,f)).

Можно в число базовых функций включить арифметические операции, определенные следующим образом:

плюс(х,у)х+у;

умн(х,у)х*у;

минус(х,у)х–у;

дел(х,у)х/у.

Теперь вычислить заданное арифметическое выражение (2х+3у)/(х–у) можно с помощью следующей композиции функций:

дел(плюс(умн(2,х), умн(3,у)), минус(х,у)).

Такая запись называется аппликативной структурой выражений. Каждое выражение является либо операцией, либо операндом. Важно заметить, что значение выражения единственным образом определяется значениями составных частей. Нас будут интересовать только "чистые" математические функции, то есть функции, значение которых для одного и того же параметра не зависит от условий вычислений. Поясним на примере. Значение выражений z=f(1)+f(2) и z=f(2)+f(1) должно быть одинаково. Покажем, что это не так, если вычисление такого выражения реализуется на языке высокого уровня, для которого возможно неоднозначное значение. #include <iostream.h>

int flag=1; %глобальная переменная

int f(int n) %описание функции

{ int res;

if(flag) res=n;

else res+2*n;

flag=-flag;

return(res);

}

void main()

{ int f(int);

cout<<"\n результат1= '<<f(1)+f(2);

cout<<"\n результат2= '<<f(2)+f(1);

}

/****Результат выполнения************

результат1=5

результат2=4

**************************************/

Функциональное свойство математических функций заключается в возможности композировать сложные функции из примитивов. Это означает, что каждое выражение определяет единственную величину, которую нельзя изменить ни путем ее вычисления, ни предоставлением различным частям программы возможности совместно использовать это выражение. Побочные эффекты, которые сопровождают императивные языки программирования (ссылки на глобальные переменные, разрушающее присваивание в рассмотренном примере, использование динамических переменных и т.д.)

Ћ! Функциональное программирование основывается на важном положении:

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

2. единственный способ объединения простых конструкций в сложные программы – это суперпозиция функций. Суперпозиция – основной метод функционального программирования.

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

4. понятие "функция" используется и в традиционных языках программирования; однако в функциональном программировании оно является единственным базовым понятием;

5. определение новых, заранее неизвестных процессору функций в виде суперпозиции примитивных и ранее определенных функций – универсальный прием функционального программирования.

Преимущества функционального подхода.

Функциональное программирование (ФП) основывается на математическом понятии "функция". Это позволяет описывать программы на универсальном языке математики. Возможно построение алгебры программ, которая упрощает их верификацию. ФП предполагает определение зависимостей между объектами предметной области, т.е. функциональный подход является декларативным, а не процедурным.

Операция суперпозиции позволяет легко использовать ранее созданные функции при построении новых.

Аппарат рекурсивного программирования обеспечивает большую вычислительную мощность функциональных подхода.

Вопросы для самопроверки

1. В чем основные отличия функционального и процедурного программирования?

2. Перечислите основные свойства функциональных программ

Тема 2. Строго функциональный язык

2.1. Символьные данные

Рассмотрим следующие символьные выражения, которые отнесем к так называемому классу S-выражениий:

(БАНАН) (а)

(Б А Н А Н) (б)

(Д. Петров 33 года) (в)

((Дима 17)(Маша 20)(Лиза 6)) (г)

((Мой дом) имеет (Большие (светлые окна) (д)

Внимание в этих S-выражениях привлекает использование скобок. Изменение использования скобок приводит к изменению структуры выражения. Выражение состоит также из атомов:

Д.

Петров