Основы функционального программирования

Основы функционального программирования

2-е издание, исправленное

Городняя Л.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Основы функционального программирования/ Л.В. Городняя - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

В курсе изложены основы функционального программирования и методы его применения при
решении сложных задач на стыке искусственного интеллекта и системного программирования.
Студенты познакомятся с основами символьной обработки информации, слабо отраженными в
отечественной литературе, а также с эффективными методами преобразования информации,
реализация которых требует многоуровневого обобщения и абстрагирования, что наиболее
естественно выражается в терминах функционального программирования. Функциональное
программирование зарекомендовало себя как гибкая методика с практически неограниченными
возможностями информационного моделирования, способствующего решению задач
исследовательского и технического характера, актуальность которых резко возрастает.
Традиционные средства слишком нацелены на кодирование битов-байтов, тогда как основная работа
переместилась на более крупные формирования, такие как системы файлов, маршрутизация,
многоканальный обмен, многопроцессорные комплексы, многоуровневые протоколы и т.п. Переход
к результативной обработке столь сложно устроенных данных требует более глубокого
абстрагирования, что может быть изучено прототипированием в функциональном стиле.Техника
функционального программирования иллюстрируется на языке Лисп, послужившем основой
широкого спектра исследований и прикладных разработок, оказавших существенное влияние на
расширение и распространение компьютерных и информационных технологий, по существу
являющихся ключевыми для анализа и формирования многих сфер деятельности. Изучение языка
Лисп является важной составляющей образования в области информатики еще и по той причине, что
в настоящее время происходит рост популярности скриптовых, интерпретируемых языков, для
понимания которых знакомство с Лиспом и функциональным программированием весьма полезно.
Лисп также представляет собой ключ и базовую модель для изучения основных задач системного
программирования и искусственного интеллекта. Именно определение Лиспа и раскрутку системы
программирования на его основе следует рассматривать как первый полномасштабный эксперимент
в области применения функционального программирования для решения весьма сложной задачи:
организации инструментальной поддержки для исследования и разработки нового класса задач
информационной обработки с высоким уровнем новизны.При отладке примеров использован GNU
Clisp.Курс предназначен для студентов, интересующихся перспективами информационных
технологий и предпочитающих понимать задачи, с которыми приходится сталкиваться в разных
областях применения информационных систем.

(c) ООО “ИНТУИТ.РУ”, 2004-2016
(c) Городняя Л.В., 2004-2016

3

Основные идеи

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

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

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

Функциональный стиль объединяет разные подходы к определению процессов
вычисления на основе достаточно строгих абстрактных понятий и методов символьной
обработки данных. Связь функционального программирования с математическими
основами позволяет в тексте программы наследовать доказательность построения
результата, если она достигнута, причем с использованием разных методов
абстрагирования решаемой задачи [2] [3].

Сложность решения задач с помощью функциональных определений преодолевается
чисто алгебраически: нацеленностью на формализацию основного множества объектов
и определения полной семантической системы операций над ними. Это позволяет
представлять классы задач и их решений строгими формулами, для наглядности
упрощаемыми введением дополнительных функциональных символов. При
необходимости такие символы вносятся в опpеделение алгебраической системы, что
приводит к ее расширению. Вводятся новые функции, подобные леммам и другим
вспомогательным построениям в математике. Активно используется рекурсия и
символьные обозначения как данных, так и действий и любых формул, удобных при
определении функций.

Формально такое расширение является консервативным (новый символ определен с

4

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

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

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

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

Джон Маккарти предложил проект языка Лисп (LISP - LISt Processing) в качестве
средства исследования границ применимости компьютеров, в частности, методом
решения задач искусственного интеллекта. Идеи этого языка вызвали не утихающие
по сей день дискуссии о приоритетах в программировании и сущности
программирования. Лисп послужил эффективным инструментом экспериментальной
поддержки теории программирования и развития сферы его применения. Рост
интереса к Лиспу коррелирует с улучшением элементной базы, повышением
эксплуатационных характеристик оборудования и появлением новых сфер применения
ИТ.

Существует и активно применяется более трехсот диалектов Лиспа и родственных ему
языков: Interlisp, muLisp, Clisp, Scheme, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и
др.

Математические основы функционального программирования

5

Сформулированная Джоном Маккаpти (1958) концепция символьной обработки
информации компьютером восходит к идеям Черча и других математиков, известным
как лямбда-исчисление с конца 20-х годов прошлого века. Выбирая лямбда-исчисление
как теоретическую модель, Маккарти предложил рассматривать функции как общее
базовое понятие, к которому достаточно естественно могут быть сведены все другие
понятия, возникающие при программировании [1].

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

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

Понятие “функция” связано с понятиями аргумента функции, области ее
существования и значения, соответствия между ее аргументами и результатами, а
также применения функции к ее аргументам. Существуют различные точки зрения на
природу всех этих терминов, на границы определяющих их множеств, на возможность
их взаимодействия в более общих построениях. Наиболее явные разночтения,
связанные с трактовкой однозначности результата функции, могут быть устранены
при рассмотрении структурных значений. Например, два разных значения при
извлечении квадратного корня можно рассматривать как один результат из двух
элементов. Еще более естественна такая точка зрения на однозначность результата
для целочисленного деления: cуществует общая функция, которая выполняет деление
одного целого числа на другое и вырабатывает результат, содержащий два элемента —
частное и остаток от деления. Кроме того, имеется две частных функции, каждая из
которых выбирает из этого результата тот элемент, который нужен для объемлющей
формулы. Не менее серьезная трудность связана с границами множеств разносортных
объектов, таких как скаляры, структуры, представления функций. Функциональное
программирование поддерживает универсальные методы обработки разносортных
объектов.

Изучение функционального программирования начинается с овладения техникой
работы с так называемыми “чистыми”,  строго математическими, идеальными
функциями. Для реализации функций характерен отказ от необоснованного
использования присваиваний и низкоуровневого управления вычислениями в терминах
передачи управления. Такие функции удобны при отладке и тестировании благодаря
независимости от контекста описания и предпочтения явно выделенного чистого
результата. Трудоемкость отладки композиций из хорошо определенных функций
растет аддитивно, а не мультипликативно. Кроме того, системы из таких функций
могут развиваться в любом направлении: сверху вниз и снизу вверх (а также
расширяясь и сужаясь, если понадобится) [23]. Можно быстро продвинуться по
сложности решаемой задачи, не отвлекаясь на синтаксическое разнообразие и

6

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

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

Далее понятие “функция” обогащается представлением о псевдо-функциях,
используемых с целью представления аппаратных, зависимых от устройств действий
(ввод/вывод, сообщения, рисование и т.п.), фактически осуществляющих известный
побочный эффект в результате работы конкретного оборудования. Но формально все
псевдо-функции обязательно выполняют и отображение аргументов в результаты, что
позволяет им равноправно участвовать в любой позиции формулы, задающей
вычислительный процесс. Формальный результат сопровождается дополнительными
эффектами. Этот переход обеспечивает при необходимости корректное моделирование
всей традиционной программотехники, включая присваивания, передачи управления,
системные вызовы, обработку файлов и доступ к любым устройствам. Но все эти
непредсказуемо сложные машинно-зависимые реалии при функциональном стиле
программирования локализованы, наращиваются на ранее отлаженный каркас
функционирования программы, их представления могут быть четко отделены от
сущности решаемой задачи. Исследовательская и проектная работа обычно проходит
фазу поиска оптимального решения. Функциональное программирование для
поддержки этой фазы предлагает еще одно отступление от чистых функций: в качестве
результата функции допускаются варианты значений, равноправно выбираемые из
конечного множества значений, подобно псевдослучайным числам. Равноправие не
распространяется лишь на тупиковую ситуацию, когда ни один предложенный вариант
не может быть вычислен. Именно эта идея составляет одну из привлекательных
особенностей логического программирования, выделившегося в самостоятельную
парадигму.

Императивная организация вычислений по принципу немедленного и обязательного

7

выполнения каждой очередной команды не всегда эффективна. Существует много
неимперативных моделей управления процессами, позволяющих прерывать и
откладывать процессы, а потом восстанавливать их и запускать или отменять.
Организация такого управления, достаточного для оптимизации и программирования
параллельных процессов, реализуется с помощью так называемых “замедленных” или
“ленивых” вычислений (lazy evaluation). Основная идея таких вычислений заключается
в сведении вызовов функций к представлению рецептов их вычисления в
определенном контексте. Вычисляться каждый такой рецепт может не более чем один
раз и то если его результат действительно нужен.

Здание функционального программирования получает логическое завершение на
уровне определения функций высших порядков, удобных для синтаксически
управляемого конструирования программ на основе спецификаций, типов данных,
визуальных диаграмм, формул и т.п. Функциональные программы могут играть роль
спецификации обычных итеративно-императивных программ. Иногда такой переход не
вызывает затруднений. Факториал можно определить рекурсивно как сведение к
значению функционала от предыдущего числа, но столь же понятно и определение в
виде цикла от одного до N. На языке Sisal [11] и цикла для этого не требуется,
достаточно задать границы области, элементы которой перемножаются (* 1, ,N).
Конечно, числа Фибоначчи легко порождать с помощью рекурсивного восходящего
процесса, но и цикл с заданной границей заработает вполне практично. Однако бывают
несложные задачи, для которых такой переход не столь прост. Вовсе не любая
обработка произвольной последовательности легко излагается в терминах векторов, и
многие задачи на больших графах могут весьма сложно приводиться к итеративной
форме. Заметные трудности в процессе сведения рекурсии к итерации создает
динамика данных и конструируемые функции. Даже реализация равенства для
произвольных структур данных при неизвестной размерности и числе элементов —
дело непростое. Известно, что лаконичность рекурсии может скрывать нелегкий путь.
А.П.Ершов в предисловии к книге П.Хендерсона [3] привел поучительный пример не
поддавшегося А.Чёрчу решения задачи о рекурсивной формуле, сводящей вычитание
единицы из натурального числа к прибавлению единицы {1 –1 = 0 | ( n +1 ) -1 =

n}, полученного С.Клини лишь в 1932 году:

n–1  = F (n, 0, 0)

где

F (x, y, z) = если (x = 1) то 0
                    иначе если ((y +1) = x) то z
                              иначе F (x, y +1, z +1)

Решение получилось через введение формально усложненной функции F со
вспомогательными аргументами, что противоречит интуитивному стремлению к
монотонности и движению от простого к сложному. Универсальность понятия
“функция” и разнообразие видов его применения позволяет унифицировать
используемые при описании процессов понятия “действие”, “значение”, “формула”,
“переменная”, “выбор варианта” и пр. Все это — разные категории функций с
различными формами унифицированного представления (записи, изображения) в

8

тексте программы и правилами интерпретации (выполнения, вычисления),
обеспечивающими получение результата функции при исполнении программы.
Аргументами функции могут быть готовые данные или результаты других функций.
Возможны ограничения на типы данных, допускаемых в качестве аргументов — тогда
речь идет о частичных функциях. Такие функции должны выяснять допустимость
фактических параметров и сообщать о несоответствии. Удобно, если часть такой
работы берет на себя компилятор в классической традиции статического контроля
правильности типов данных,но динамический контроль типов данных в условиях,
характерных для современных информационных сетей, может быть надежнее, чем
традиционный статический анализ, сложившийся для замкнутых, защищенных от
несанкционированного доступа конфигураций, обеспечивающий гарантии сохранения
скомпилированного кода программы при его использовании. (Имеется в виду
вероятность искажения скомпилированного кода при его эксплуатации на компьютере
в сетях.) Это приводит к компромиссу в виде объектно-ориентированного
программирования, допускающего динамический контроль типов данных.

Лисп и принципы технической поддержки

История Лиспа насыщена жаркими спорами, противоречивыми суждениями, яркими
достижениями и смелыми изобретениями. От первых сообщений Джона Маккарти о
замысле языка символьной обработки (1958) и авторских проектов первых Лисп-
систем (1960–1962) — через демонстрацию принципиальной решаемости проблем
искусственного интеллекта (1964), разрешение теоретических парадоксов (1972–1974)
[5], разработку признанных стандартов (1972–1980), построение специализированных
диалектов и создание практичных реализаций для широкого спектра различных
применений — до появления Лисп-компьютеров (1978), систем математической
обработки информации (1965–1990), визуальных и сверхэффективных Лисп-систем
(1992–2002) идеи Лиспа выдержали многогранную шлифовку, достойную самой
высокой оценки специалистов. Написанная Дж.Вейценбаумом на Лиспе программа-
собеседник “Элиза”, имитирующая речевое поведение психоаналитика, дала
положительный ответ на вопрос о возможности искусственного разума.

Этого более чем достаточно для того чтобы утверждать, что Лисп — гениальное
творение, но тем не менее, потенциал данного языка еще предстоит раскрыть.
Выразительная сила Лиспа обретает новое дыхание на каждом эволюционном витке
развития информационных технологий. При сравнительном анализе информационных
систем моделирование их семантики на Лиспе позволяет классифицировать
функционирование по уровню сложности, зрелости, полноты, точности и
организованности. Универсальность Лиспа достаточна для изучения на его основе
любой парадигмы информатики и программотехники. Можно сказать, что Лисп
содержит в себе эталонную семантическую систему, пригодную для измерения
функциональности других систем.

Информационный мир становится все более динамичным — Лисп приспособлен к
программированию развивающихся построений и реорганизуемых конфигураций из
разносортных компонентов. Многие реализационные находки Лиспа, такие как
ссылочная организация памяти, “сборка мусора” для повторного использования

9

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

Общеизвестно, что Лисп — язык искусственного интеллекта и исследования
наукоемких и новых направлений информационной обработки. Но этим влияние Лиспа
не ограничено. Диалекты Лиспа (Logo, ML, MuLisp, Scheme, Hope, AutoLisp,
CommonLisp, Reduce и др.) заняли обширную нишу в области учебно-
экспериментального программирования , связанного с развитием теории
программирования, системного программирования, разработки и прототипирования
новых компьютерных комплексов и архитектур, конструирования и исследования
систем построения оптимизирующих компиляторов и организации особо точных и
высокопроизводительных вычислений.

Многообразие откликов на Лисп не случайно. На первый взгляд, идеи Лиспа
противоречат традиционным подходам к программированию. Но это противоречие
отступает перед строгой логикой языка, гармонично уравновешенной полнотой и
ясностью реализационных решений. Определение Лиспа дает гибкую основу для
развития, варьирования и расширения Лисп-систем средствами как самого Лиспа, так и
его окружения. Объем такого определения не превышает одной страницы.

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

Базис Лиспа предельно лаконичен — атомы и структуры из простейших бинарных
узлов плюс несколько базовых функций и функционалов . Базис содержит встроенные
(примитивные) функции, которые анализируют, строят и разбирают любые
структурные значения ( atom, eq, cons, car, cdr ), и встроенные специальные функции и
функционалы, которые управляют обработкой структур, представляющих вычисляемые
выражения ( quote, cond, lambda, label, eval ). Над базисом строятся предельно
простые формулы в виде круглоскобочных списков, где первый элемент — функция,
остальные — ее аргументы, в том числе переменные, реализуемые с помощью разных
вариантов стека или ассоциативного списка. Все остальные механизмы вычисления и
преобразования формул могут сводиться к этому базису, рассматриваться как его
вариант или расширение. Такой лаконизм сродни алгебре, способствующей
проявлению общих закономерностей в работе с формулами над объектами разной
природы. Подробнее с идеями Лиспа и его математическими основами можно
ознакомиться на страницах журнала “Компьютерные инструменты в образовании”, №
2–5 за 2002 год.

Синтаксис Лиспа не требует особых ресурсов для запоминания разделителей и/или
ограничителей и напряженного внимания на распознавание синтаксических позиций в
разных рамочных конструкциях. Универсальный разделитель — пробел, ограничители

10