Унификация понятий концептуального минимума (Pure Lisp)

Конструкция	Примеры представле- ния	Трактовка	Пояснение
Данные
Встроенная константа	Nil	Представление функции без параметров, результатом кото- рой является пустой список	Результаты таких функций хранятся непосредственно в памяти. Их полу- чение не требует вычислений
Элементар- ное значе- ние	List X Atom	Представление неопределен- ной функции, которая может быть в дальнейшем использо- вана как значение переменной или представление конкретной функции
Идентифи- катор	A X ATOMIC IDENT	Представление функции, ар- ность, категория и определе- ние которой задаются раз- ными средствами связывания атомов с их смыслом. (Связы- вание аргументов с парамет- рами при вызове функции или именование определения)
Именован- ная кон- станта	A	Представление функции без параметров, в любой позиции программы выдающей ранее заданное значение
Переменная	X	Представление функции без параметров, результат которой может зависеть от контекста, например, от области видимо- сти при вызове других функ- ций

Конструкция	Примеры представле- ния	Трактовка	Пояснение
S-выражение	(A. B) (A B C. D)	Могут представлять вызов функции	Может быть аргу- ментом или резуль- татом функции
Список	NIL (A B) (A (B C) D)		Может быть пред- ставлением любой составной формы
Составное константное значение	‘(A B C) ‘(A (B C) D) ‘(А. В)	Результат унарной функции QUOTE, препятствующей вы- числению своего аргумента: (QUOTE (A B C)) (QUOTE (A (B C) D)) (QUOTE (А. В))	Блокировка вычис- лений, в частности для организации отложенных дей- ствий
Операции	CAR CDR CONS ATOM EQ	Встроенные функции	Базовые средства обработки данных
Организация процессов
Вызов функ- ции	(FN LIST-FRM)	Представление выражения в виде списка из представления функции и представлений ее параметров в виде выражений. При необходимости результат функции вычисляется с помо- щью универсальной функции APPLY	Общая схема вы- числений. При вызове функ- ции происходит ло- кальное связывание аргументов со зна- чениями парамет- ров, сохраняемое в стеке
Выражение (форма)	X FNAME (CAR ‘(a b c))	Представление аргумента уни- версальной функцией EVAL, пригодное для вычисления зна- чения этого аргумента	Вывод значений по представлению вы- ражений
Ветвление	(COND ((EQ X A) Y) ((ATOM X) D) -- -- (T Z))	Специальная мультифункция над произвольным числом аргу- ментов, каждый из которых яв- ляется списком из представле- ний предиката и соответствую- щей ему ветви	Метод организации частичных вычисле- ний

Конструк- ция	Примеры представ- ления	Трактовка	Пояснение
Определе- ние безы- мянной функции	(LAMBDA (x y) (expr x y))	Результат специальной бинар- ной функции LAMBDA, пер- вый аргумент которой – спи- сок аргументов определяемой функции, а второй представ- ляет выражение, задающее ее тело	Конструирование представления функции
Именова- ние локаль- ного опре- деления	(LABEL NAME DEF)	Результат специальной бинар- ной функции LABEL, связы- вающей новое имя, заданное первым аргументом, с пред- ставлением функции, задан- ной вторым аргументом, в ко- тором это связывание локали- зовано	Поддержка много- кратного примене- ния функции
Вычисле- ние	(EVAL expr)	Результат универсальной функции EVAL, анализирую- щей структуру представления выражения и выбирающей ме- тод вычисления значения вы- ражения	Поддержка управ- ления ходом вы- числений, включая возобновление от- ложенных дей- ствий
Примене- ние функ- ции к за- данным ар- гументам	(APPLY fn args ...)	Вспомогательная функция, выполняющая вызов FN при вычисленных аргументах	Часть интерпрета- тора

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

Трактовка основных понятий программирования, расширяющих Lisp

Конструкция	Примеры пред- ставления	Трактовка	Пояснение
Pure Lisp
Вывод данных	(PRINT X)	Представление тож- дественной псевдо- функции PRINT с побочным эффек- том, заключающемся в размещении экви- валентного ее аргу- менту текста на экране или в задан- ном файле	(PRINT X) = X Результат совпа- дает с аргумен- том, поэтому раз- мещение в любой позиции про- граммы вывода данных может не влиять на ход вы- полнения про- граммы
Ввод данных	(READ)	Представление псевдо-функции без параметров READ, побочным эффектом которой является конструирование представления дан- ного, эквивалент- ного строке, набран- ной на консоли или размещенной в за- данном файле	Включение в про- грамму средств ввода данных позволяет управ- лять ходом вы- числений без ре- дактирования текста про- граммы, что поз- воляет повысить удобство и надежность от- ладки
Обработка прерываний, ошибок, исключений, неожиданно- стей и т.п.	(ERROR N “message” continuation)	Представление псевдо-функции, обеспечивающей для заданного номера со- бытия поясняющее сообщение и воз- можное продолже- ние процесса вычис- лений. По умолча- нию – восстанов- ление начального контекста	Поддержка вы- числений в стиле бэктреккинга

Конструкция	Примеры представления	Трактовка	Пояснение
Элементарное значение, псевдо-атом	123 3.14 4/5 «строка»	Представление само- определимой функ- ции без аргументов, результатом которой является ее соб- ственное представле- ние	Результаты такой функции хра- нятся непосред- ственно в памяти. Их получение не требует вычисле- ний
Операции над числами	(+ 1 2 3 4) (* 1 2 3 4) (– 1 2 3 4) (/ 1 2 3 4)	Представление муль- тифункций над про- извольным числом аргументов. Аддитивные опера- ции при пустом списке аргументов вырабатывают число 0. Мультипликатив- ные – число 1	(+ 1 2 3 4) = 1+2+3+4 (* 1 2 3 4) = 1*2*3*4 (– 1 2 3 4) = 1–2–3–4 (/ 1 2 3 4) = 1/2/3/4
Арифметиче- ские выраже- ния	(+ (* 3 5 D) (– A 8) (/ 1 2 X))	Представление ре- зультатов вычисле- ний не требует опре- деления типов реа- лизуемых чисел, зависящих от фор- мата кода или длины машинного слова	(/ 1 2) = ½ Длина целых чи- сел не ограни- чена, результат целочисленного деления может быть представлен как дробь без по- тери точности, точность веще- ственных может быть задана
Lisp 1.5
Компиляция функций	(COMPILE …)	Специальная функ- ция, побочный эф- фект которой заклю- чается в создании кода функции, оттес- няющего ее символь- ное определение	Оптимизация от- лаженных функ- ций ради скоро- сти выполнения

Конструкция	Примеры представления	Трактовка	Пояснение
Структуро- разрушающие функции	(RPLACA X Y) (RPLACD X Y) (CONC AL BL)	Представление функций с побоч- ными эффектами, вызванными исполь- зованием памяти ар- гументов при кон- струировании ре- зультата, при наличии их чисто функциональных эк- вивалентов: (RPLACA X Y) = (CONS Y (CDR X)) (RPLACD X Y) = (CONS (CAR X) Y) (CONC AL BL) = (APPEND AL BL)	Реализационный базис раскрутки СП. Поддержка опти- мизации и син- хронизации неза- висимых участ- ков программы, возникающих при вычислении рекурсивных функций, незави- симых парамет- ров, выполнении итераций и т. п.
Именование глобальной функции	(DEFINE NAME DEF)	Результат специаль- ной бинарной функ- ции DEFINE, связы- вающей новое имя, заданное первым ар- гументом, с глобаль- ным определением функции, представ- ленным вторым ар- гументом	Поддержка ком- бинаторики неза- висимых опреде- лений функций
Императив- ные вычисле- ния	(PROG (V..)….)	Специальная функ- ция, выполняющая последовательное вычисление выраже- ний, рассматривае- мых как операторы. Результат выделен функцией RETURN или определен по- следним оператором

Конструкция	Примеры представления	Трактовка	Пояснение
Clisp
Конструиро- вание пред- ставления именованной глобальной функции	(DEFUN NAME ARGS DEF)	Результат специаль- ной функции DE- FUN, конструирую- щей по списку аргу- ментов и определяю- щему выражению новое глобальное определение функ- ции и связывает его с именем	Области действия имен и поддержка иерархии наследуемых определений
Область видимости рабочих переменных	(LET LIST EXPR)	Специальная функ- ция LET строит об- ласть видимости, в которой опреде- лены значения рабо- чих переменных со- гласно списку LIST, используемых при вычислении выраже- ния EXPR
Область видимости рабочих переменных	(LET* LIST EXPR)	Допускает взаимную рекурсию
Область видимости вспомогатель- ных функций	(FLET LIST REXPR)	Специальная функция FLET строит область видимости, в которой определены вспомо- гательные функции согласно списку LIST, используемых при вычислении выраже- ния EXPR
Конструиро- вание специ- альных функ- ций	(MACRO...)	Специальная функ- ция MACRO создает определения новых специальных функ- ций, обрабатываю- щих представления своих параметров без их предваритель- ного вычисления	Поддержка альтернативных методов вычислений

Конструкция	Примеры представления	Трактовка	Пояснение
Цикл	(LOOP …)	Специальная функ- ция, один из пара- метров которой яв- ляется предназна- ченным для многократного вы- числения телом цикла, а остальные используются при управлении кратно- стью вычисления тела цикла	Поддержка традиционных схем представле- ния программ
Параллельные вычисления	(MULTIPLY …)	Специальная функ- ция, выполняющая вычисление своих параметров в произ- вольном порядке, не заданном заранее. Значения всех ре- зультатов доступны объемлющим функ- циям	Подготовка па- раллельных вы- числений

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

Внимание к идеям функционального программирования привлек в 1977 году Джон Бэкус в своей Тьюринговской лекции. Руководитель разра- ботки языка Fortran и соавтор формул Бэкуса – Наура (БНФ) призвал к пре- одолению узости «бутылочного горлышка» императивно-процедурного стиля программирования и привел в качестве примера проект функциональ- ного языка программирования FP [19], поддерживающего лаконичные формы представления обработки многомерных векторов, содержательно напоминающие отдельные конструкции языков Lisp и APL¹⁹.

19 Магариу Н. А. Язык программирования АПЛ. М.: Радио и связь. 96 с.

 

 

Следует отметить некоторую разницу в понимании принципов ФП, сло- жившуюся в теории и практике программирования. Эта разница четко про- явилась при стандартизации языка Lisp в 1980-е годы в виде принятия двух стандартов: LISP1 – академический и LISP2 – производственный. Scheme, ML, Hope, Haskell – типичные представители академического стандарта LISP1, Common Lisp, Clisp, Sisal, Cmucl – производственного стандарта LISP2.

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

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

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

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

Изучение функционального программирования начинается с овладения техникой работы с так называемыми «чистыми», идеальными функциями в области константных вычислений. Для реализации таких функций характе- рен отказ от необоснованного использования присваиваний и низкоуровне- вого управления вычислениями в терминах передачи управления. Такие функции удобны на начальных стадиях отладки и тестирования благодаря не-

 

 

зависимости от контекста описания и предпочтения явно выделенного чи- стого результата. Трудоемкость отладки композиций из хорошо определен- ных функций растет аддитивно, а не мультипликативно. Кроме того, системы из таких функций могут развиваться в любом направлении: сверху вниз и снизу-вверх (а также расширяясь и сужаясь, если понадобится). Можно быстро продвинуться по сложности решаемой задачи, не отвлекаясь на син- таксическое разнообразие и коллизии при обработке общих данных. Для обу- чения такому стилю программирования на языке Lisp был создан язык Pure Lisp и определен его интерпретатор. Концептуально близкие идеи «структур- ного программирования» были сформулированы более чем через десять лет. Если в качестве данных допускать не только значения, но и символьные формы для вычисления этих значений, то вопрос о времени вычисления ар- гументов можно решать не столь категорично. Кроме обычных функций, ар- гументы которых вычисляются предварительно, в ряде случаев можно рас- сматривать и реализовывать специальные функции, способные обрабатывать аргументы нестандартным способом по любой заданной схеме, определять

отложенные действия (lazy evaluation).

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

Здание функционального программирования получает логическое завер- шение на уровне определения функций высших порядков, удобных для син-

 

 

таксически управляемого конструирования программ на основе специфика- ций, типов данных, визуальных диаграмм, формул и т. п. Функциональные программы могут играть роль спецификации обычных императивно-проце- дурных программ. Иногда такой переход не вызывает затруднений. Факто- риал можно определить рекурсивно как сведение к значению функционала от предыдущего числа, но столь же понятно и определение в виде цикла от одного до N. На языке Sisal для этого не требуется даже цикла, достаточно задать границы области, элементы которой перемножаются (* 1,,N). Ко- нечно, числа Фибоначчи легко порождать с помощью рекурсивного восходя- щего процесса, но и цикл с заданной границей заработает вполне практично. Однако встречаются несложные задачи, для которых такой переход не столь прост. Отнюдь не любая обработка произвольной последовательности легко излагается в терминах векторов, и многие задачи на больших графах могут весьма сложно приводиться к итеративной форме. Заметные трудности в про- цесс сведения рекурсии к итерации создает динамика данных и конструируе- мые функции. Даже реализация равенства для произвольных структур дан- ных при неизвестной размерности и числе элементов является не простым делом.

Известно, что лаконизм рекурсии может скрывать нелегкий путь. А. П. Ершов в предисловии к книге П. Хендерсона привел поучительный пример не поддавшегося А. Черчу решения задачи о рекурсивной формуле, сводящей вычитание единицы из натурального числа к прибавлению еди- ницы {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)	Сведение к вызову вспомогательной функции.     Вспомогательная функция. Объявление значения от 1. Проверка достижения предыдущего числа.   Шаг рекурсии с наращиванием параметров

Пример 19. Выражение «–1» через «+1»

 

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

20 Клини С. К. Введение в метаматематику. М.: Изд-во ИЛ, 1957.

 

 

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

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

Важно отметить, что преимущества ФП обусловлены не только семанти- кой используемых языков программирования, но и особенностями его под- держки в системах программирования:

– представления данных (чисел, строк, имен, списков) обычно не ограни- чены по длине;

– полностью автоматизировано первичное и повторное распределение па- мяти – «сборка мусора»;

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

– встроены средства управления вычислениями, расширяющие возмож- ности СП в направлении основных парадигм программирования.