ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Трактовка основных понятий программирования, унифицированных как функции, для практичного расширения средств отладки и оптимизации программ и решения новых задач Конструкция Примеры представления Трактовка Пояснение Вывод данных (PRINT X) ?X Представление тождественной псевдо-функции (PRINT X) = X Результат совпадает с 104 PRINT с побочным эффектом, заключающемся в размещении эквивалентного еѐ аргументу текста на экране или в заданном файле. аргументом, поэтому размещение в программе вывода данных может не влиять на ход выполнения программы. Ввод данных (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) Представление мультифункций над произвольным числом аргументов. (+ 1 2 3 4) = 1+2+3+4 (* 1 2 3 4) = 1*2*3*4 105 Аддитивные операции при пустом списке аргументов вырабатывают число 0. Мультипликативные – число 1. (- 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) = ½ Длина целых чисел не ограничена, результат целочисленного деления может быть представлен как дробь без потери точности, точность вещественных может быть задана. Именование глобальной функции (DEFINE NAME DEF) Результат специальной бинарной функции DEFINE, связывающей новое имя, заданное первым аргументом, с глобальным определением функции, представленным вторым аргументом. Поддержка комбинаторики независимых определений функций. Конструировани е представления именованной глобальной функции (DEFUN NAME ARGS DEF) Результат специальной функции DEFUN, конструирующей по списку аргументов и определяющему выражению новое глобальное определение функции и связывает его с именем. 106 Область видимости рабочих переменных (LET LIST EXPR) Специальная функция LET строит область видимости, в которой определены значения рабочих переменных согласно списку LIST, используемых при вычислении выражения EXPR. Поддержка иерархии наследуемых определений. Область видимости вспомогательны х функций (FLET LIST REXPR) Специальная функция FLET строит область видимости, в которой определены вспомогательные функции согласно списку LIST, используемых при вычислении выражения EXPR. Конструировани е специальных функций (MACRO ) Специальная функция MACRO создает определения новых специальных функций, обрабатывающих представления своих параметров без их предварительного вычисления. Поддержка альтернативных методов вычислений. 107 Цикл (LOOP … ) Специальная функция, один из параметров которой является предназначенным для многократного вычисления телом цикла, а остальные используются при управлении кратностью вычисления тела цикла. Поддержка традиционных схем представления программ. Императивные вычисления (PROG (V ..)….) Специальная функция, выполняющая последовательное вычисление выражений, рассматриваемых как операторы. Результат выделен функцией RETURN или определѐн последним оператором. Параллельные вычисления (MULTIPLY …) Специальная функция, выполняющая вычисление своих параметров в произвольном порядке, не заданном заранее. Значения всех параметров доступны объемлющим функциям. Подготовка параллельных вычислений. Компиляция функций ( COMPILE …) Специальная функция, побочный эффект которой заключается в создании кода функции, Оптимизация отлаженных функций по скорости выполнения. 108 оттесняющего еѐ символьное определение. Структуро- разрушающие функции (RPLACA X Y) (RPLACD X Y) (CONC AL BL) (MAPCON FN AL) Представление функций с побочными эффектами, вызванными использованием памяти аргументов при конструировании результата, при наличии их чисто функциональных эквивалентов: (RPLACA X Y) = (CONS Y (CDR X)) (RPLACD X Y) = (CONS (CAR X) Y) (CONC AL BL) = (APPEND AL BL) (MAPCON FN AL) = (MAPLIST FN AL) Поддержка синхронизации независимых участков программы, возникающих при вычислении рекурсивных функций, независимых параметров, выполнении итераций и т. п. Управление обработкой информации в лямбда-исчислении осуществляется в рамках иерархии свободных и связанных переменных, реализуемых с помощью таблицы соответствия символов и их смысла. Обработка представляется посредством правил интерпретации выражений, построенных из всюдуопределенных функций, аргументы которых могут быть упорядочены. По степени общности такое построение сравнимо с аксиоматической теорией множеств. Следует отметить некоторую разницу в понимании принципов ФП, сложившуюся в теории и практике программирования. Эта разница чѐтко проявилась при стандартизации языка Lisp в 1980-е годы в виде принятия двух стандартов: LISP1 – академический и LISP2 – производственный. Теоретически достаточно исследовать чисто функциональные лаконичные представления программ, поведение которых не зависит от побочных эффектов. Результат программы может быть получен системой редукций еѐ представления. Процессы применения редукций можно выбирать в зависимости от стратегии вычислений. На практике основная трудоѐмкость связана с отладкой программы на базе конкретной системы 109 программирования, поддерживающей определѐнную стратегию вычислений или дающей возможность явного управления ходом выполнения программы в зависимости от данных. Чисто функциональная программа при оптимизирующей компиляции может быть сведена к еѐ формальному результату без генерации исполнимого кода. По отношению к проблемам определения языков и систем программирования (СП) основные идеи ФП сложились при реализации языка Lisp и в работах Венской лаборатории IBM в начале 1960-ых годов. Эти идеи оказались трудными для восприятия в пионерскую эпоху программирования, но в настоящее время их популярность растет, что и обуславливает целесообразность фундаментальных исследований в сфере функционального программирования, проектирования и моделирования. С конца 70-х годов появились Lisp-процессоры, доказавшие, что неэффективность функционального программирования обусловлена характеристиками оборудования, а не стилем программирования. Функциональные мини-языки хорошо показали себя и при решении задач аппаратного уровня. Все это превращает ФП в практичный и перспективный инструментарий. Такая схема подтверждается самой историей развития диалектов языка Lisp и родственных ему языков программирования. Изучение функционального программирования начинается с овладения техникой работы с так называемыми «чистыми», строго математическими, идеальными функциями в области константных вычислений. Для реализации таких функций характерен отказ от необоснованного использования присваиваний и низкоуровневого управления вычислениями в терминах передачи управления. Такие функции удобны при отладке и тестировании благодаря независимости от контекста описания и предпочтения явно выделенного чистого результата. Трудоемкость отладки композиций из хорошо определенных функций растет аддитивно, а не мультипликативно. Кроме того, системы из таких функций могут развиваться в любом направлении: сверху вниз и снизу-вверх (а также расширяясь и сужаясь, если понадобится). Можно быстро продвинуться по сложности решаемой задачи, не отвлекаясь на синтаксическое разнообразие и коллизии при обработке общих данных. Для обучения такому стилю программирования на языке Lisp был создан язык Pure Lisp и определѐн его интерпретатор. Концептуально близкие идеи «структурного программирования» были сформулированы более чем через десять лет. Если в качестве данных допускать не только значения, но и символьные формы для вычисления этих значений, то вопрос о времени вычисления аргументов можно решать не столь категорично. Кроме обычных функций, 110 аргументы которых вычисляются предварительно, в ряде случаев можно рассматривать и реализовывать специальные функции, способные обрабатывать аргументы нестандартным способом по любой заданной схеме, отложенные действия (lazy evaluation). Функции могут быть частично определѐнными, отображающими часть множества, и многозначными, хотя бы одному значению аргумента соответствует два или более значений функции. Прежде всего, понятие «функция» обогащается представлением о псевдо-функциях, которые используются с целью предоставления аппаратных, зависимых от устройств действий (ввод/вывод, сообщения, рисование и т. п.). Они фактически осуществляют известный побочный эффект в результате работы конкретного оборудования и ОС – минимального контекста исполнения любой практически полезной программы. Формально все псевдо-функции обязательно выполняют и отображение аргументов в результаты, что позволяет им равноправно участвовать в любой позиции формулы, задающей вычислительный процесс. Формальный результат сопровождается дополнительными эффектами. Этот переход обеспечивает, при необходимости, корректное моделирование всей традиционной программотехники, включая присваивания, передачи управления, системные вызовы, обработку файлов и доступ к любым устройствам. Все эти непредсказуемо сложные машинно-зависимые реалии при функциональном стиле программирования локализованы, наращиваются на ранее отлаженный каркас функционирования программы, их представления могут быть четко отделены от сущности решаемой задачи. Функциональное программирование снижает трудоѐмкость отладки программ благодаря созданию коллекций абстрактных лаконичных универсальных функций, приспособленных к многократному применению в разных программах. Здание функционального программирования получает логическое завершение на уровне определения функций высших порядков, удобных для синтаксически управляемого конструирования программ на основе спецификаций, типов данных, визуальных диаграмм, формул и т. п. Функциональные программы могут играть роль спецификации обычных императивно-процедурных программ. Иногда такой переход не вызывает затруднений. Факториал можно определить рекурсивно как сведение к значению функционала от предыдущего числа, но столь же понятно и определение в виде цикла от одного до N . На языке Sisal для этого не требуется даже цикла, достаточно задать границы области, элементы которой перемножаются (* 1, ,N) . Конечно, числа Фибоначчи легко порождать с помощью рекурсивного восходящего процесса, но и цикл с 111 заданной границей заработает вполне практично. Однако встречаются несложные задачи, для которых такой переход не столь прост. Отнюдь не любая обработка произвольной последовательности легко излагается в терминах векторов, и многие задачи на больших графах могут весьма сложно приводиться к итеративной форме. Заметные трудности в процесс сведения рекурсии к итерации создает динамика данных и конструируемые функции. Даже реализация равенства для произвольных структур данных при неизвестной размерности и числе элементов является не простым делом. Известно, что лаконичность рекурсии может скрывать нелегкий путь. А. П. Ершов в предисловии к книге П. Хендерсона привел поучительный пример не поддавшегося А. Чѐрчу решения задачи о рекурсивной формуле, сводящей вычитание единицы из натурального числа к прибавлению единицы {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. Проверка достижения предыдущего числа. Шаг рекурсии с наращиванием параметров. Пример. 20. Выражение «-1» через «+1» Решение получилось через введение формально усложненной функции F со вспомогательными параметрами, которое противоречит интуитивному стремлению к монотонности при движении от простого к сложному. Возможны ограничения на типы данных, допускаемых в качестве аргументов, в таком случае речь идет о частичных функциях. Эти функции должны выяснять допустимость фактических параметров и сообщать о несоответствии. Удобно, если часть такой работы берет на себя компилятор в классической традиции статического контроля правильности типов данных, но динамический контроль типов данных в условиях, характерных для современных информационных сетей, может быть надежнее, чем традиционный статический анализ, сложившийся для замкнутых, защищенных от несанкционированного доступа конфигураций, 112 обеспечивающий гарантии сохранения скомпилированного кода программы при его использовании. (Имеется в виду вероятность искажения скомпилированного кода при его эксплуатации на компьютере в сетях.) Это приводит к компромиссу в виде объектно-ориентированного программирования, допускающего динамический контроль типов данных. Важно отметить, что преимущества ФП обусловлены не только семантикой используемых языков программирования, но и особенностями его поддержки в системах программирования: – представления данных (чисел, строк, имѐн, списков) не ограничены по длине; – полностью автоматизировано первичное и повторное распределение памяти – «сборка мусора»; – выделен комплекс базовых средств для программирования без побочных эффектов в памяти программы, достаточный для представления ленивых вычислений, отображений и других функций высших порядков; – встроены средства управления вычислениями, расширяющие возможности СП в направлении основных парадигм программирования. 5.2. Функциональные ЯП Идеи ФП достаточно полно поддержаны в проекте Lisp 1.5, выполненном Дж. Маккарти и его коллегами. В этом исключительно мощном языке не только реализованы основные средства, обеспечившие практичность и результативность ФП, но и впервые опробован целый ряд поразительно точных построений, ценных как концептуально, так и методически и конструктивно, понимание и осмысление которых слишком отстает от практики применения. Понятийно функциональный потенциал языка Lisp 1.5 в значительной мере унаследован стандартом Common Lisp. Языки ФП достаточно разнообразны. Существует и активно применяется более трехсот диалектов Lisp-а и родственных ему языков: Interlisp, muLisp, Clisp, Sсheme, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и др. При сравнении языков и парадигм программирования часто классифицируют функциональные языки по следующим критериям: «ленивый» или аппликативный, последовательный и параллельный. Например, ML является аппликативным и последовательным, Erlang – аппликативным и параллельным, Haskell – «ленивым» и последовательным, а Clean – параллельным и «ленивым». Scheme, ML, 113 Hope, Haskell – типичные представители академического стандарта LISP1, а Common Lisp, Clisp, Sisal, Cmucl – производственного стандарта LISP2. В рамках проекта .Netвыполнено большое число реализаций различных языков программирования, в числе которых Haskell, Sml, Scheme, Mondrian, Mercury, Perl, Oberon, Component Pascal, Разработан F# – новый язык ФП. Еще большее разнообразие предлагает проект DotGNU, пытающийся отстоять приоритет в области разработки переносимого ПО. Развиваются линии учебного и любительского программирования и методично осваивается техника выстраивания иерархии абстрактных машин при определении языков программирования. Разработка языков функционального программирования (ЯФП) и приспособленность средств ФП к быстрой отладке, верификации, их лаконизм, гибкость, конструктивность и моделирующая сила позволяют рассматривать ФП как основу информационной среды обучения современного программирования на всех уровнях проблематики от алгоритмизации до включения в социальный контекст приложений разрабатываемых ИС. 5.3. Отображения и функционалы Выразительная сила ЯФП наиболее результативно проявляется в программировании отображений. Отображенияобычно используются при анализе и обработке данных, представляющих информацию разной природы. Вычисление, кодирование, трансляция, распознавание – каждый из таких процессов использует исходное множество цифр, шаблонов, текстов, идентификаторов, по которым конкретная отображающая функция находит пронумерованный объект, строит закодированный текст, выделяет идентифицированный фрагмент, получает зашифрованное сообщение. Так работает любое введение обозначений – от знака переход к его смыслу. Определение отображений – ключевая задача информатики. Построение любой информационной системы сопровождается реализацией большого числа отображений. Сначала выбираются данные, с помощью которых представляется информация. В результате по данным можно восстановить представленную ими информацию – извлечь информацию из данных (по записи числа восстановить его величину). Потом конструируется набор структур, достаточный для размещения и обработки данных и программ в памяти компьютера (по коду команды можно выбрать хранимую в памяти подпрограмму, которая построит новые коды чисел или структур данных). 114 Говорят, что отображение существует, если задана пара множеств и отображающая функция, для которой первое множество – область определения, а второе – область значения. При определении отображений, прежде всего, должны быть ясны ответы на следующие вопросы: – что представляет собой отображающая функция; – как организовано данное, представляющее отображаемое множество; – каким способом выделяются элементы отображаемого множества, передаваемые в качестве аргументов отображающей функции. Это позволяет задать порядок перебора множества и метод передачи аргументов для вычисления отображающей функции. При обходе структуры, представляющей множество, отображающая функция будет применена к каждому элементу множества. Проще всего выработать структуру множества результатов, подобную исходной структуре. Но возможно, что не все полученные результаты нужны, или требуется собрать их в иную структуру, поэтому целесообразно заранее прояснить еще ряд вопросов: – где размещается множество полученных результатов; – чем отличаются нужные результаты от полученных попутно; – как строятся итоговые данные из отобранных результатов. При функциональном стиле программирования ответ на каждый из таких вопросов может быть дан в виде отдельной функции, причем роль каждой функции в схеме реализации отображениячетко фиксирована. Схема реализации отображения может быть представлена в виде определения, формальными параметрами которого являются обозначения функций, выполняющих эти роли. Такое определение называют функционалом. Говоря более точно, функционал может оперировать представлениями функций в качестве аргументов или результатов. Функции, выполняющие конкретные роли, могут быть достаточно общими, полезными при определении разных отображений, – они получают имена для многократного использования в разных системах определений. Но они могут быть и разовыми, нужными лишь в данном конкретном случае, – тогда можно обойтись без их имен и использовать определение непосредственно в точке вызова функции. Таким образом, определение отображенияможет быть разбито на части (функции и функционалы) разного назначения, типичного для многих схем информационной обработки. Это позволяет упрощать отладку систем определений, повышать коэффициент повторного использования 115 отлаженных функций. Можно сказать, что отображения – эффективный механизм абстрагирования, моделирования, проектирования и формализации крупномасштабной обработки информации. Возможности отображенийв информатике значительно шире, чем освоено практическим программированием, но их применение требует дополнительных пояснений. Отказ от барьера между представлениями функций и значений дает возможность использовать символьные выражения как для изображения заданных значений, включая любые структуры над числами и строками, так и для представления функций, обрабатывающих любые данные. (Напоминаем, что определение функции представляется как данное.) Таким образом, функционалы в ЯФП – это функции, которые используют в качестве аргументов или результатов представления других функций, а не собственно функции как принято говорить. При построении функционалов переменные могут играть роль имен функций, представления которых находятся во внешних формулах, использующих функционалы. Рассмотрим технику использования функционалов на упражнениях с числами и покажем, как от простых задач перейти к более сложным. Определение Примечание (DEFUN map-el(fn xl) (COND (xl (CONS (FUNCALL fn (CAR xl)) (map-el fn (CDR xl)) ) ) ) ) Поэлементное преобразование XL с помощью функции FN. Пока XL не пуст, присоединяем результат FN от головы XL к списку преобразованных остальных элементов. (map-el #'1+ xl) 16 Следующие числа (map-el #'CAR xl) «головы» элементов = CAR (map-el #'length xl) Длины элементов Пример 21. Отображение элементов списка с помощью заданной функции Числа представляются в Lisp-е как специальный тип атома. Атом такого типа состоит из указателя с тэгом, специфицирующим слово как число, тип этого числа и адрес собственно числа произвольной длины. В отличие от обычного атома, одинаковые числа при хранении не совмещаются. 16 #’x – эквивалент (FUNCTION x), что является представлением функции в качестве аргумента. 116 Определить функцию покомпонентной обработки двух списков с помощью заданной функции FN. Определение Примечание (DEFUN map-comp (fn al vl) (COND (al (CONS (FUNCALL fn (CAR al) (CAR vl)) (map-comp (CDR al) (CDR vl)) ) ) ) ) fn покомпонентно применить к соответственным элементам al и vl Пока AL не пуст Присоединяем результат FN от голов AL и VL к списку преобразованных остальных элементов (map-comp #'+ '(1 2 3) '(4 6 9)) = (5 8 12) Суммы (map-comp #'* '(1 2 3) '(4 6 9)) = (4 12 27) Произведения (map-comp #'CONS '(1 2 3) '(4 6 9)) = ((1 . 4) (2 . 6) (3 . 9)) Пары (map-comp #'EQ '(4 2 3) '(4 6 9)) = (T NIL NIL) Сравнения Пример 22. Покомпонентные действия над векторами, представленными с помощью списков Определение Примечание (DEFUN mapf (fl el) (COND (fl (CONS (FUNCALL (CAR fl) el) (mapf (CDR fl) el) ) ) ) ) Пока FL не пуст, присоединяем результат очередной функции от EL к списку результатов остальных функций (mapf '(length CAR CDR) '(a b c d)) = (4 a (b c d)) Пример 23. Применение списка функций к общему аргументу Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками. Такие формулы удобны при моделировании множеств, графов и металингвистических формул, а к их обработке сводится широкий класс задач не только в информатике. Показанные построения достаточно разнообразны, чтобы можно было сформулировать, в чем преимущества применения техники функционального программирования: 117 – отображающие функционалыпозволяют строить программы из крупных действий; – функционалы обеспечивают гибкость отображений; – определение функции может совсем не зависеть от конкретных имен; – с помощью функционалов можно управлять выбором формы результатов; – параметром функционала может быть представление любой функции, преобразующей элементы структуры; – функционалы позволяют формировать серии функций от общих данных; – встроенные в Clisp функционалы приспособлены к покомпонентной обработке произвольного числа параметров; – любую систему взаимосвязанных функций можно преобразовать к одной функции, используя вызовы безымянных функций. 5.4. Отложенные действия Императивная организация вычислений по принципу немедленного и обязательного выполнения каждой очередной команды не всегда результативна. Существует много неимперативных моделей управления процессами, позволяющих прерывать и откладывать процессы, а потом восстанавливать их и запускать или отменять. Организация такого управления, достаточного для оптимизации и программирования параллельных процессов, реализуется с помощью так называемых «замедленных» или «ленивых» вычислений (lazy evaluation). Основная идея таких вычислений заключается в сведении вызовов функций к представлению рецептов их вычисления, содержащих замыкания функций в определенном контексте: (λ () fn) – заблокировать вычисление «fn», превратив его в тело функции без аргументов; (fn) – разблокировать выражение «fn» в форме вызова функции без параметров. Непосредственное применение таких формул влечѐт многократное вычисление «fn», поэтому в инструментальном ядре используется реализационная структура данных, названная «рецепт», хранящая варианты представления выражения: { [F (fn . e)] | [T x]} 118 Сначала рецепт представлен как «(F (fn . e))», где «(fn . e)» – это замыкание выражения «fn» в пределах контекста «e». Попытка вычисления рецепта приводит к замене его результатом. По прежнему адресу размещается структура «(T x)», в которой «x» равен результату вычисления «fn» в контексте «e». Таб л иц а 3 1 |