ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
, списки свойств атома и деструктивные операции, расширяющие язык программирования так, что становятся возможными оптимизирующие преобразования структур данных, программ и процессов, а главное – раскрутка систем программирования. Prog-форма языка Lisp 1.5 может рассматриваться как абстрактная модель ИП, в которой при интерпретации используются отдельные ассоциативные таблицы для хранения параметров доступа к значениям переменных и определениям функций и процедур в памяти. Это позволяет независимо задавать механизмы доступа к именам переменных и наименованиям процедур. Применение возможностей prog-выражений позволяет писать «паскалеподобные» программы, состоящие из операторов, предназначенных для исполнения (точнее, «алголоподобные» (Algol-like), т. к. они появились за десять лет до Паскаля. Теперь более известен Pascal). Для примера prog-выражения приводится императивное определение функции LENGTH , сканирующей список и вычисляющей число элементов на верхнем уровне списка. Значение функции LENGTH – целое число. Программу можно примерно описать следующими словами (Стилизация примера от Маккарти.): Русский язык Примечание Это функция одного аргумента L. Она реализуется программой с двумя переменными u и v. Записать число 0 в v. Записать аргумент L в u. A: Если u содержит NIL, то функция выполнена и еѐ значением является то, что сейчас записано в v. Записать в u cdr от того, что сейчас в u. Объявление функции. Объявление рабочих переменных. Инициирование рабочих переменных. Меткой «А» помечена проверка завершения и формирования результата. Шаг продолжения функции. 94 Записать в v на единицу больше того, что сейчас записано в v. Перейти к A" Переход на метку «А». Пример 15. Описание алгоритма на естественном языке Эту программу можно написать в виде Pascal-программы. Строкам описанной выше программы в предположении, что существует библиотека функций над списками на Pascal-е, соответствуют строки определения функции: Pascal Примечание function LENGTH (L: list) : integer; label A; var U: list; V: integer; begin V := 0; U := L; A: if null (U) then LENGTH := V; U := cdr (U); V := V+1; goto A; end; Объявление функции LENGTH, выдающей целое число. Объявление метки и рабочих переменных. Инициирование рабочих переменных. Меткой «А» помечена проверка завершения и выработка результата функции. Шаг продолжения функции. Переход на метку «А». Пример 16. Представление программы на языке Pascal Переписывая это определение в виде лисповского S-выражения, получаем программу: Lisp Примечание defun LENGTH (L) (prog (U V) (setq V 0) (setq U L) A (cond ((null U) Объявление функции LENGTH, реализуемой в императивном стиле с двумя рабочими переменными. Инициирование рабочих переменных. Меткой «А» помечена проверка завершения и выработка результата функции. 95 (return V))) (setq U (cdr U)) (setq V (+ 1 V)) (go A) ) ) (LENGTH '(A B C D)) (LENGTH '((X . Y) A CAR (N B) (X Y Z)) ) Шаг продолжения функции. Переход на метку «А». Применение функции даѐт 4. Применение функции даѐт 5. Пример 17. Представление программы на языке Lisp Последние две формы представляют применение функции. Их значения - четыре и пять, соответственно. Prog-форма имеет структуру, подобную определениям функций и процедур в Паскале: ( PROG , список рабочих переменных, последовательность операторов и атомов ...). Атом в списке выполняет роль метки, локализующей оператор, расположенный вслед за ним. Метка A, как и в примерах 2 и 3, локализует оператор, начинающийся с ветвления. Первый список после символа PROG называется списком рабочих переменных. При отсутствии таковых должно быть написано NIL или () С рабочими переменными обращаются примерно как со связанными переменными, но они не могут быть связаны ни с какими значениями через LAMBDA . Значение каждой рабочей переменной есть NIL до тех пор, пока ей не будет присвоено что-нибудь другое. Для присваивания рабочей переменной применяется форма SET. Чтобы присвоить переменной pi значение 3.14 пишется (SET (QUOTE PI)3.14) . SETQ подобна SET, но она еще и блокирует вычисление первого аргумента. Поэтому (SETQ PI 3.14) – запись того же присваивания. SETQ обычно удобнее. SET и SETQ могут изменять значения любых переменных из более внешних функций. 14 Значением SET и SETQ является значение их второго аргумента. Обычно в программе действия выполняются последовательно. Выполнение действия понимается как его вычисление и отбрасывание его значения. Действие программы обычно выполняются в большей степени ради эффекта действия, чем ради вычисленного значения. 14 Clisp – действуют на любом уровне. 96 GO-форма, используемая для указания перехода (GO A) указывает, что программа продолжается действием, помеченным атомом A , причем это A может быть и из внешнего выражения PROG Условные выражения в качестве действий программы являются базовым средством представления ветвлений. Если ни одно из пропозициональных выражений не истинно, то программа продолжается действием, следующим за условным выражением. 15 RETURN – нормальное завершение программы. Аргумент RETURN вычисляется, что и является значением программы. Никакие последующие действия не вычисляются. Prog-выражение может быть рекурсивным. Функция REV , обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивного Prog-выражения. Pascal Примечание function REV (x: list) :list; label A, B; var y, z: list; begin A: if null (x) then REV := y; z := car (x); if atom (z) then goto B; z := REV (z); B: y := cons (z, y); x := cdr (x); goto A; end; Определение функции REV, вырабатывающей список. Объявлены метки и локальные переменные. Меткой «A» помечена проверка завершения и результат. Выбор очередного элемента для реверсирования. Для атома переход на метку «В» в обход реверсирования. Замена элемента на его реверс. Меткой «В» помечена сборка результата. Шаг продвижения по списку. Переход на метку «А» для дальнейшего реверсирования. Пример18. Представление программы на языке Pascal. Функция rev обращает все уровни списка так, что rev от (A ((B C) D)) даст ((D (C B))A) 15 В Clisp все ветвления работают так. 97 Lisp Примечание (defun REV (X) (prog (Y Z) A (cond ((null X)(return Y))) (setq Z (car X)) (cond ((atom Z)(goto B))) (setq Z (rev Z)) B (setq Y (cons Z Y)) (setq X (cdr X)) (go A) )) Определение функции REV, реализуемая императивно с переменными. «A» помечает завершение и дан результат. Выбор очередного элемента для реверсирования. Для атома переход на метку «В» в обход реверсирования. Замена элемента на его реверс. «В» помечает сборка реверсируемого списка. Шаг продвижения по списку. Переход на метку «А» для дальнейшего реверсирования. Пример 19. Представление программы на языке Lisp В принципе, SET и SETQ могут быть реализованы с помощью ассоциативного списка примерно так же, как и поиск значения, только с сохранением связей, расположенных ранее изменяемой переменной: (defun SET (X Y) (cons (cons X Y) Alist)) ) Введенное таким образом присваивание обеспечивает вычислимость левой части присваивания, т. е. можно в программе вычислять имена переменных, значение которых предстоит поменять. 4.4. Спецификация Таб л иц а 2 8 Парадигматическая характеристика языков, поддерживающих процедурно-императивную парадигму программирования Параметр Конкретика Эксплуатационная прагматика ЯП Программирование решений задач, обладающих точной постановкой задачи и практичным алгоритмом без претензий на тщательное исследование. Регистры абстрактной машины S E C M S – стек операндов и промежуточных результатов. E – стек локальных переменных и аргументов. C – поток программы. 98 M – вектор памяти. Категории команд абстрактной машины Засылка в стек. Вычисления над стеком. Пересылки в глобальную и локальную память. Передачи управления. Ветвления. Вызов процедуры. Возврат из процедуры. Реализационная прагматика Предпочтение статического распределения памяти по блокам для векторов заданного размера, контроля типов данных при выполнении операций и вызове процедур, операций над машинными словами. Программируемое освобождение памяти. Стеки реализованы как векторы. Парадигматическая специфика Процедурно-императивный стиль программирования обычно дополнен простыми средствами функционального программирования. 99 ЛЕКЦИЯ 5. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ Функциональный стиль программирования сложился в практике решения задач символьной обработки данных в предположении, что любая информация для компьютерной обработки может быть сведена к символьной (существование аналоговых методов принципиально не противоречит этой гипотезе). Слово «символ» здесь близко понятию «знак» в знаковых системах. Информация представляется символами, смысл которых может быть восстановлен по заранее известным правилам. Функциональное программирование рассматривает процесс обработки данных как композицию их отображений с помощью универсальных функций. Программа при таком подходе – не более чем одна из разновидностей данных. Функциональное программирование сумело преодолеть синтаксический разнобой независимо развиваемых средств и методов организации информационных процессов. Это удалось благодаря нацеленности на проявление и ортогонализацию семантических подсистем в организации программируемых процессов. Не менее важна развиваемость представления унифицируемых структур данных и комплектов функциональных объектов. Все это позволяет языки функционального программирования рассматривать как средство сопряжения разнородных конструкций. На их основе можно осуществлять любые интегрированные построения, представимые в машинно-независимом стиле. Языки функционального программирования (ЯФП) используют гибкие списки и абстрактные атомы. ЯФП нацелены на полный контроль типов значений при исполнении программ, допускающих динамический анализ и управление с откладыванием вычислений, автоматизацию повторного использования памяти – «сборки мусора». Методы функционального программирования основаны на формальном математическом языке представления и преобразования формул, поэтому можно дать точное, достаточно полное описание основ функционального программирования и специфицировать систему программирования для поддержки и разработки разных парадигм программирования, моделируемых с помощью функционального подхода к организации деятельности. Функциональное программирование отличается от большинства подходов к программированию тремя важными принципами. 1. Природа данных. Все данные представляются в форме символьных выражений. Данные реализуются как древообразные структуры, что позволяет локализовывать 100 любые важные подвыражения. Система программирования с такими структурами обычно использует для их хранения всю доступную память, поэтому программист может быть освобожден от распределения памяти под отдельные блоки данных. 2. Самоописание обработки символьных выражений. Важная особенность функционального программирования состоит в том, что описание способов обработки данных представляется программами, рассматриваемыми как символьные данные. Программы строятся из рекурсивных функций. Определения и вызовы этих функций, как и любая информация, могут обрабатываться как обычные данные, получаться в процессе вычислений и преобразовываться как значения. 3. Подобие машинным языкам. Система функционального программирования допускает, что программа может интерпретировать и/или компилировать программы, представленные в виде структур данных. Это сближает методы функционального программирования с методами низкоуровневого программирования и отличает от традиционной методики применения языков высокого уровня. Не все языки функционального программирования в полной мере допускают эту возможность, но для языка Lisp она характерна. В принципе, такая возможность достижима на любом стандартном языке, но так делать не принято. Функциональное программирование активно применяется для генерации программ и выполнения динамически конструируемых прототипов программ, а также для систем, применяемых в областях с низкой кратностью повторения отлаженных решений (например, в учебе, проектировании, творчестве и научных исследованиях), ориентированных на оперативные изменения, уточнения, улучшения, адаптацию и т. п. 5.1. Основы Внимание к идеям функционального программирования привлѐк в 1977 году Джон Бэкус в своей Тьюринговской лекции. Руководитель разработки языка Fortran и соавтор формул Бэкуса-Наура (БНФ) призвал к преодолению узости «бутылочного горлышка» императивно-процедурного стиля программирования и привѐл в качестве примера проект функционального языка программирования FP, поддерживающего лаконичные формы представления обработки многомерных векторов, содержательно напоминающие отдельные конструкции языков Lisp и APL. 101 Сформулированная Джоном Маккаpти (1958) концепция символьной обработки информации восходит к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов прошлого века. Выбирая лямбда-исчисление как теоретическую модель, положенную в основу языка Lisp, Маккарти предложил рассматривать функции как общее базовое понятие, к представлению и реализации которого достаточно естественно могут быть сведены все другие понятия, возникающие в практике программирования. Такое сведение вовсе не означает, что все понятия сваливаются в одну кучу, что исчезают границы между понятиями. Сведение выполнено так, что при сохранении всех понятийных границ выстроено более общее пространство, в рамках которого эти понятия упорядочены и могут взаимодействовать согласно формальным определениям разных категорий функций. Т а б л и ц а 2 9 Унификация понятий концептуального минимума (Pure Lisp) для безмашинного обучения методам символьной обработки представлений функций, включая отображения, отложенные действия, и другие функции высших порядков, использующие исключительно чистые функции без побочных эффектов Конструкц ия Примеры представл ения Трактовка Пояснение Встроенна я константа Nil Представление функции без параметров, результатом которой является пустой список. Результаты таких функций хранятся непосредственно в памяти. Их получение не требует вычислений Элемента рное значение List X A Представление неопределѐнной функции, которая может быть в дальнейшем определена как значение переменной или представление конкретной функции. 102 Идентифи катор A X ATOMIC IDENT Представление функции, арность, категория и определение которой задаются разными средствами связывания атомов с их смыслом. (Связывание аргументов с параметрами при вызове функции или именование определения.) Именованна я константа A Представление функции без параметров, в любой позиции программы выдающей ранее заданное значение. Переменная X Представление функции без параметров, результат которой может зависеть от контекста, например, от области видимости при вызове других функций. Составное значение „(A B C) „(A (B C) D) „(А . В) Результат унарной функции QUOTE, препятствующей вычислению своего аргумента: (QUOTE (A B C)) (QUOTE (A (B C) D)) (QUOTE ( А . В)) Блокировка вычислений, в частности для организации отложенных действий. Вызов функции (FN LIST-FRM) Представление выражения в виде списка из представления функции и представлений еѐ параметров в виде выражений. При необходимости результат функции вычисляется с помощью универсальной функции APPLY. Общая схема вычислений. При вызове функции происходит локальное связывание аргументов со значениями параметров, сохраняемое в стеке. Выражение (форма) X FNAME (CAR „(a b c)) Представление аргумента универсальной функцией EVAL, пригодное для вычисления значения этого аргумента. Вывод значений по представлению выражений. Ветвление (COND ((EQ X A) Y) ((ATOM X) D) Специальная мультифункция над произвольным числом аргументов, каждый из которых является списком из представлений предиката и Метод организации частичных вычислений. 103 -- -- (T Z)) соответствующей ему ветви. При пустом списке – результат Nil. Определени е безымянно й функции (LAMBDA (x y ) (expr x y)) Результат специальной бинарной функции LAMBDA, первый аргумент которой – список аргументов определяемой функции, а второй представляет выражение, задающее еѐ тело. Конструирование представления функции. Именовани е локального определени я (LABEL NAME DEF) Результат специальной бинарной функции LABEL, связывающей новое имя, заданное первым аргументом, с представлением функции, заданной вторым аргументом, в котором это связывание локализовано. Поддержка многократного применения функции. Вычислени е (EVAL expr) Результат универсальной функции EVAL, анализирующей структуру представления выражения и выбирающей метод вычисления значения выражения. Поддержка управления ходом вычислений, включая возобновление отложенных действий. Практическое программирование обычно выходит за круг константно определѐнных программ, поддерживаемых чистыми функциями. Для целей решения новых задач, отладки и оптимизации программ на компьютере возникает расширение пространства используемых категорий функций, обладающих разными побочными эффектами. Таб л иц а 3 0 |