1. Функциональное программирование. Основы Лиспа
| Вид материала | Документы |
- Рабочая программа по курсу "Функциональное программирование" Специальность, 144.38kb.
- Федеральное агентство по образованию, 124.95kb.
- В. А. Давыденко программирование и основы алгоритмизации лабораторный практикум, 1951.1kb.
- Петербургский Гуманитарный Университет Профсоюзов (СПбгуп), с-петербург учебный курс, 20.72kb.
- Программа дисциплины Математическое программирование Семестры, 10.84kb.
- Методические указания и задания к курсовому проекту по дисциплине «Функциональное, 73.42kb.
- Программа дисциплины Функциональное программирование и интеллектуальные системы для, 148.26kb.
- Методические рекомендации для студентов по изучению курса «Функциональное программирование», 49.76kb.
- Рабочая программа по дисциплине "Функциональное и логическое программирование, 152.21kb.
- Программа элективного курса «Алгоритмизация и программирование», 95.38kb.
Оглавление
1. Функциональное программирование. Основы Лиспа. 2
Особенности функционального программирования 2
Основные понятия 2
Общее представление о языке Лисп 7
2. Списки в Лиспе 9
Списки. Функции для работы со списками 9
Управляющие структуры (предложения) 12
1.предложение let – служит для одновременного присваивания значений нескольким символам; 12
2.предло жения prog1, prog2, prong – используются для организации последовательных вычислений; 12
3.предложение cond – используется для организации ветвления, и, следовательно, очень важно для организации рекурсии; 12
4.предложение do – традиционный цикл. 12
Простая рекурсия 14
Другие виды рекурсии 16
1.параллельная рекурсия – тело определения функции function_1 содержит вызов некоторой функции function_2, несколько аргументов которой являются рекурсивными вызовами функции function_1. 17
5.взаимная рекурсия – в теле определения функции function_1 вызывается некоторая функции function_2, которая, в свою очередь, содержит вызов функции function_1. 17
6.рекурсия более высокого порядка – в теле определения функции аргументом рекурсивного вызова является рекурсивный вызов. 17
3. Функционалы 19
Функционалы и отображения 19
Применяющие функционалы 20
Встроенные функционалы 22
Лямбда выражения 23
Композиции функционалов, фильтры, редукции 24
Выводы по применимости функционалов 26
^
1. Функциональное программирование. Основы Лиспа.
Особенности функционального программирования
Функциональный стиль программирования сложился в практике решения задач символьной обработки данных в предположении, что любая информация для компьютерной обработки может быть сведена к символьной. Информация представляется символами, смысл которых может быть восстановлен по заранее известным правилам. Методы функционального программирования основаны на формальном математическом языке представления и преобразования формул. Функциональное программирование отличается от большинства подходов к программированию тремя важными принципами:
^
1) Природа данных
Все данные представляются в форме символьных выражений. В Лиспе Дж. Мак-Карти назвал их S-выражениями. Состав S-выражений и типы их элементов не ограничиваются, что позволяет его использовать как древообразные структуры. Это позволяет локализовывать любые важные подвыражения. Система программирования над такими структурами обычно использует для их хранения всю доступную память, поэтому программист освобожден от распределения памяти под отдельные блоки данных.
^
2) Самоописание обработки символьных выражений
Важная особенность функционального программирования состоит в том, что описание способов обработки S-выражений представляется программами, рассматриваемыми как символьные данные. Программы строятся из рекурсивных функций над S-выражениями. Определения и вызовы этих функций, как и любая информация, имеют вид S-выражений, то есть формально они могут обрабатываться как обычные данные, получаться в процессе вычислений и преобразовываться как значения.
^
3) Подобие машинным языкам
Система функционального программирования допускает, что программа может интерпретировать и/или компилировать программы, представленные в виде S-выражений. Это сближает методы функционального программирования с методами низкоуровнего программирования и отличает от традиционной методики применения языков высокого уровня.
Наиболее очевидные следствия из выбранных принципов:
- процесс разработки программ разбивается на две фазы: построение базиса и его пошаговое расширение;
- рассмотрение программы как реализации алгоритма естественно дополняется табличной реализацией функций, т.е. допустимо использование хранимых графиков функций в виде структур из аргументов и соответствующих результатов наряду с процедурами;
- прозрачность ссылок обеспечена совпадением значений одинаково выглядящих формул, вычисляемых в одинаковом контексте;
- нацеленность на универсальные функции и функционально полные системы, трудоемкость первичной реализации которых компенсируется надежностью определений и простотой применения.
Функциональное программирование активно применяется для генерации программ и выполнения динамически конструируемых прототипов программ, а также для систем, применяемых в областях с низкой кратностью повторения отлаженных решений (например, в учебе, проектировании, творчестве и научных исследованиях), ориентированных на оперативные изменения, уточнения, улучшения, адаптацию и т.п.
^
Основные понятия
Функцией называется правило, по которому каждому значению одного или нескольких аргументов ставится в соответствие конкретное значение результата.
Способы определения правила и методов получения результата функции по заданному правилу при известных аргументах могут быть различны, например:
- Алгоритм (поиск наибольшего общего делителя).
- Таблица (сложение или умножение для целых чисел).
- Процесс (взвешивание или измерение).
- Устройство (вольтметр, термометр, часы)
- Формализованный текст (процедура, подпрограмма, макрос и т.п.).
Различаются обозначения и определения соответствия между аргументами и результатами. Интуитивно понятие функции содержит концепцию времени: сначала вычисляются аргументы в порядке перечисления, затем строится значение функции - ее результат. Процессы обработки информации организуются как применение функций к их аргументам - вычисления.
Концепция функции является одним из фундаментальных понятий математики. Чтобы задать функцию y=f(x), связывающую две переменные величины х и у, необхо димо указать: 1) множество А значений, которые может принимать x (область опреде ления функции), 2) множество В значений, которые может принимать v (область зна чения функции), 3) правило/(.у), по которому значениям x из А соотносятся значения v из В Каждому элементу из области определения однозначная функция ставит в соот ветствие а точности один элемент из области значения. Правило в простейшем случае можно изобразить с помощью графа или с помощью таблицы (рис. 1).
Рис. 1
Чаще всего правило задается формулой, устанавливающей, какие вычислительные операции надо произвести над х, чтобы найти у: квадрат(х)=хг. В этом определении область определения и область значений функции даны неявно и не всегда очевидны. Например, функция квадрат отображает множество вещественных чисел во множест во неотрицательных вещественных чисел, а целые числа в неотрицательные целые числа.
Если есть элементы из области определения, для которых отображение посредст вом этой функции не определено, то функция называется частичной или частично оп ределенной. Например, функция обратное(х)=1/х является частично определенной над множеством вещественных чисел. Функция, не являющаяся частичной, называется общей или всюду определенной.
Функцию нескольких аргументов можно рассматривать как функцию одного аргу мента (кортежа), множество значений которого является декартовым произведением множеств значений всех аргументов функции. Другая интерпретация функции несколь ких аргументов заключается в том, что применение функции f к аргументам (а, b) рас сматривается как выражение (f(a))(b), где результатом вызова функции f с аргументом а является новая функция с одним аргументом, которая затем вычисляется для ар гумента b.
Некоторые функции на разных частях своей области определения задаются раз личными формулами, например:
Это правило удобнее записывать как:
max(х,у) = если х>у то х, иначе у
Условное предложение "если то иначе" позволяет выбрать одну из двух формул для вычисления результата функции в зависимости от некоторого условия. Часть предложения "иначе` не может быть опущена. При применении функции max к аргументам (1,3) вычисление по данному правилу происходит так. параметрам функции х и у сопоставляются значе ния 1 и 3, затем вычисляется значение выражения х>у (т.е. 1>3), что дает ложь, и в ка честве результата функции возвращается значение у (т.е. 3). Таким образом, вызов функции макс(1 ,3) дает результат 3.
Важнейшим приемом в функциональном программировании является композиция функций, позволяющая определять одни функции через другие, например:
max3(x,y,z)= max(max(х,у),z).
Результат вызова функции max(х,у) используется в ка честве аргумента для функции max.
Функциональная программа состоит из совокупности определений функций. Функ ции, в свою очередь, представляют собой вызовы других функций и предложения, управляющие последовательностью вызовов. Вычисления начинаются с вызова неко торой функции, которая, в свою очередь, вызывает функции, входящие в ее определе ние и т. д. в соответствии с иерархией определений и структурой условных предложе ний. Функции часто либо прямо, либо косвенно вызывают сами себя. В конечном итоге при вычислении функции должны ссылаться на основные базовые функции. Каждый вызов возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор, пока запустившая вы числения функция не вернет конечный результат пользователю.
Рассмотрим следующую программу на языке Си:
double max(double x, double у) {
if(x>=y)
return x;
else
return y;
}
С помощью данной функции легко найти максимум из трех значений, используя композицию: m=max(max(a,b),c);
Можно определить функцию max и другим способом:
void max(double x, double у, double *z) {
if(x>=y)
*z=x;
else
*z=y;
}
Понятие функции при этом не нарушается, но результат возвращается через один из аргументов. В этом случае для вычисления максимума из трех чисел невозможно использовать композицию, результат может быть вычислен с помощью по следовательности вызовов:
max(a,b,&m);
max(m,с,&m);
То же самое произойдет, если результат функции будет возвращаться через гло бальную переменную. Такие особенности работы функции называются "побочными эффектами". Функция, не имеющая побочных эффектов, называется строгой.
Строго функциональный язык не допускает побочных эффектов, не признает при сваивание и передачу управления. Разветвление вычислений основано на механизме обработки частей условного предложения. Повторяющиеся вычисления осуществля ются через рекурсию. Единственным "эффектом" выполнения любой функции является вычисленный результат.
Так как нет присваивания, переменные, получив значение в начале блока вычисле ний, например, при вызове функции, больше никогда его не меняют. Таким образом, переменные - это просто сокращенная запись их значений, и на место переменных в программе всегда можно вставить выражения, по которым они вычисляются. Порядок проведения вычислений становится несущественным. Так как на результат вычислений не влияют никакие побочные эффекты, то неважно, когда вычислять этот резуль тат.
Кроме того, функциональный язык обладает двумя мощными механизмами, позво ляющими писать более краткие и универсальные программы. Во-первых, аргументами или результатом функции могут быть сложные структуры данных. Однажды построен ная структура не может изменяться, но может включаться в другие Во-вторых, можно определить функцию высшего порядка, аргументами или результатом которой являет ся функции.
Функция называется рекурсивной, если ее определение прямо или косвенно (через другие функции) содержит обращение к самой себе.
^ Система программирования – это комплекс средств и методов, используемых при подготовке и применении программ на одном или нескольких языках программирования. Система программирования может быть задана как правило интерпретации или компиляции программ.
Вычисление – процесс решения задачи, сводимой к обработке чисел, кодов или символов, рассматриваемых как модели реальных объектов.
Соответствие между моделью и объектом часто называют интерпретацией.
Список – основная структура данных в ФП. Список может быть пустым или содержать произвольное число объектов любой природы. Пустой список используется в качестве значения "ложь" - все, что отлично от пустого списка может выполнять роль значения "истина".
Символ в ФП аналогичен переменной в традиционном языке программирования – это имя, состоящее из букв латиницы, цифр и некоторых специальных литер. Символ, как и переменная, может иметь какое-либо значение, то есть представлять какой-либо объект. Наряду с символами, в ФП используются также: числа (целые и вещественные); специальные константы t и nil, обозначающие логические значения true (истина) и false (ложь); списки.
Символы, числа и специальные константы представляют простейшие объекты, на основе которых строятся все прочие объекты данных. Поэтому для них используется обобщающее название – атомы. Атомы являются элементарными S-выражениями (последовательность из букв и цифр, начинающаяся с буквы). Атомы могут иметь вид имен, чисел или других объектов, неделимых базовыми средствами языка. Атомы, выглядящие как имена, могут обладать свойствами, задаваемыми системой или программой. Значения переменных и определения функций – примеры свойств.
^ Истинностные значения – конечный набор различимых данных, используемых как характеристика логического высказывания, сравнения, успешности процесса, актуальности события, соответствия допустимым границам и т.п.
Кроме списков имеются более общие структуры данных – символьные выражения (S-выражения), реализуемые как двоичные деревья, а Лисп-системы поддерживают обработку различных специальных структур данных, таких как вектора, массивы, строки, хэш-таблицы, файлы, потоки ввода-вывода и др. Все вышеперечисленные объекты (атомы и списки) в совокупности называют символьными выражениями. Областью определения и областью значений для функций в функциональном про граммировании являются S-выражения. Отношения между различными символьными выражениями можно представить следующим образом:
Список из функции и перечня ее аргументов называется "форма" - синоним термина "выражение". Программа – это последовательность вычисляемых форм. Рекурсия – сведение к себе – позволяет такие правила записывать достаточно лаконично и ясно.
Стек - набор данных, в котором элементы обрабатываются согласно дисциплине "Первым пришел – последним ушел." (англ. Stack пачка, стопка). Стек обеспечивает работу с рекурсивными функциями.
Переменная – именованная часть памяти, предназначенная для многократного доступа к изменяющимся данным.
Константа – именованная часть памяти, предназначенная для многократного доступа к фиксированным, не изменяющимся данным.
^ Тип данных – множество данных с соответствующим ему набором допустимых операций.
В языках программирования, ориентированных на компиляцию, принято переменные классифицировать по типам данных, а значения в памяти хранить без информации о типе данных.