globalf5-240972240972 (850810), страница 17
Текст из файла (страница 17)
Существует большое число чисто теоретическихработ, исследовавших соотношения между потенциалом того и другогоподхода и пришедших к заключению о формальной сводимости в обестороны при некоторых непринципиальных ограничениях на техникупрограммирования. Методика сведения императивных программ вфункциональные заключается в определении правил разметки илипереписывания схемы программы в функциональные формы.
Переходот функциональных программ к императивным технически сложнее:используется интерпретация формул над некоторой специальноустроенной абстрактной машиной [3, 4]. На практике переложениефункциональных программ в императивные выполнить проще, чемнаоборот — может не хватать близких понятий.С практической точки зрения любые конструкции стандартных языковпрограммирования могут быть введены как функции, дополняющиеисходную систему программирования, что делает их вполнелегальными средствами в рамках функционального подхода.
Надо лишьчетко уяснить цену такого дополнения и его преимущества, обычно109Л.В. ГородняяОсновы функционального программированиясвязанные с наследованием решений и привлечением пользователей. Впервых реализациях Лиспа были сразу предложены специальныеформы и структуры данных, служащие мостом между разными стилямипрограммирования, а заодно смягчающие недостатки исходной,слишком идеализированной, схемы интерпретации S-выражений,выстроенной для учебных и исследовательских целей.
Важнейшеетакого рода средство, выдержавшее испытание временем — prog-форма,списки свойств атома и деструктивные операции, расширяющие языкпрограммирования так, что становятся возможными оптимизирующиепреобразования структур данных, программ и процессов, а главное —раскрутка систем программирования [1].Применение prog-выражений позволяет писать "паскалеподобные"программы, состоящие из операторов, предназначенных дляисполнения. (Точнее "алголоподобные", т.к.
появились лет за десять допаскаля. Но теперь более известен паскаль.)Для примера prog-выражения приводится императивное определениефункции ( LENGTH *), сканирующей список и вычисляющей числоэлементов на верхнем уровне списка. Значение функции >LENGTH —целое число. Программу можно примерно описать следующимисловами (Стилизация примера от МакКарти [1].):"Это функция одного аргумента L. Она реализуетсяпрограммой с двумя рабочими переменными u и v.Записать число 0 в v.Записать аргумент L в u.A: Если u содержит NIL, то программа выполнена изначением является то, что сейчас записано в v.Записать в u cdr от того, что сейчас в u.Записать в v на единицу больше того, чтосейчас записано в v.Перейти к A"Эту программу можно записать в виде Паскаль-программы снесколькими подходящими типами данных и функциями.
Строкамописанной выше программы в предположении, что существуетбиблиотека Лисп-функций над списками на Паскале, соответствуютстроки определения функции:110Л.В. ГородняяОсновы функционального программированияfunction LENGTH (L: list) : integer;label A;var U: list;V: integer;beginV := 0;U := L;A: if null (U) then LENGTH := V;U := cdr (U);V := V+1;goto A;end;Переписывая в виде S-выражения, получаем программу:((DEFUN LENGTH (L)(PROG (U V)(SETQ V 0)(SETQ U L)A (COND ((NULL U)(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)))Последние две строки содержат тесты. Их значения четыре и пять,соответственно. Prog-форма имеет структуру, подобную определениямфункций и процедур в Паскале: ( PROG, список рабочих переменных,последовательность операторов и атомов ...) Атом в списке являетсяметкой, локализующей оператор, расположенный вслед за ним. Вприведенном примере метка A локализует оператор, начинающийся сCOND .Первый список после символа PROG называется списком рабочихпеременных. При отсутствии таковых должно быть написано NIL или111Л.В. ГородняяОсновы функционального программирования().
С рабочими переменными обращаются примерно как сосвязанными переменными, но они не могут быть связаны ни с какимизначениями через LAMBDA. Значение каждой рабочей переменной естьNIL, до тех пор, пока ей не будет присвоено что-нибудь другое.Для присваивания рабочей переменной применяется форма SET .Чтобы присвоить переменной pi значение 3.14 пишется (SET(QUOTE PI)3.14). SETQ подобна SET, но она еще и блокируетвычисление первого аргумента. Поэтому (SETQ PI 3.14) — записьтого же присваивания. SETQ обычно удобнее. SET и SETQ могутизменять значения любых переменных из а-списка более внешнихфункций. Значением SET и SETQ является значение их второгоаргумента.Обычно операторы выполняются последовательно.
Выполнениеоператора понимается как его вычисление при текущем а-списке иотбрасывание его значения. Операторы программы часто выполняютсяв большей степени ради действия, чем ради значения.GO -форма, используемая для указания перехода (GO A) указывает, чтопрограмма продолжается оператором, помеченным атомом A, причемэто A может быть и из внешнего выражения PROG .Условные выражения в качестве операторов программы обладаютполезными особенностями.
Если ни одно из пропозициональныхвыражений не истинно, то вместо указания на ошибку, происходящегово всех других случаях, программа продолжается оператором,следующим за условным выражением. Это справедливо лишь дляусловного выражения, находящегося на верхнем уровне PROG.RETURN — нормальный конец программы. Аргумент RETURNвычисляется, что и является значением программы. Никакиепоследующие операторы не вычисляются.Формы GO, SET, RETURN могут применяться как операторы лишь наверхнем уровне PROG или внутри COND, находящегося на верхнемуровне PROG.Если программа прошла все свои операторы, она оканчивается со112Л.В. ГородняяОсновы функционального программированиязначением NIL.Prog-выражение, как и другие Лисп-функции, может быть рекурсивным.Функция REV, обращающая список и все подсписки, столь жеестественно пишется с помощью рекурсивного Prog-выражения.function rev (x: list) :List;label A, B;var y, z: list;beginA: if null (x) then rev := y;z := cdr (x);if atom (z) then goto B;z := rev (z);B: y := cons (z, y);x := cdr (x);goto A;end;Функция rev обращает все уровни списка, так что rev от (A ((B C)D)) даст ((D (C B))A).(DEFUN REV (X)(PROG (Y Z)A (COND ((NULL X)(RETURN Y)))(SETQ Z (CDR X))(COND ((ATOM Z)(GOTO B)))(SETQ Z (REV Z))B(SETQ Y (CONS Z Y))(SETQ X (CDR X))(GOTO A)))Для того чтобы форма PROG была полностью законна, необходимавозможность дополнять а-список рабочими переменными.
Кроме того,113Л.В. ГородняяОсновы функционального программированияоператоры этой формы требуют специального расширения языка — внего включаются формы GO, SET и RETURN, не известные вне PROG.Атомы, играющие роль меток, работают как указатели помеченногоблока.Кроме того, уточнен механизм условных выражений: отсутствиеистинного предиката не препятствует формированию значения COND оператора, т.к. все операторы игнорируют выработанное значение. Этопозволяет считать, что значением является NIL. Такое доопределениеусловного выражения приглянулось и в области обычных функций, гдеоно часто дает компактные формулы для рекурсии по списку.В принципе, SET и SETQ могут быть реализованы с помощью a-спискапримерно так же, как и поиск значения, только с копированием связей,расположенных ранее изменяемой переменной (см.
функцию ASSIGNиз лекции 3). Более эффективная реализация будет описана ниже.(DEFUN SET (X Y) (ASSIGN X Y Alist))Обратите внимание, что введенное таким образом присваиваниеработает разнообразнее, чем традиционное: обеспечена вычисляемостьлевой части присваивания, т.е. можно в программе вычислять именапеременных, значение которых предстоит поменять.(SETQ X 'Y)(SET X 'NEW)(PRINT X)(PRINT Y)Пример 6.1.Напечатается Y и NEW (традиционно атомы печатаются заглавнымибуквами).Списки свойств атомов и структура списковДо сих пор атом рассматривался только как уникальный указатель,обеспечивающий быстрое выяснение различимости имен, названийили символов. В настоящем разделе описываются списки свойств,114Л.В. ГородняяОсновы функционального программированиякоторые начинаются или находятся в указанных ячейках.Каждый атом имеет список свойств.
Когда атом читается (вводится)впервые, тогда для него создается пустой список свойств, которыйпотом можно заполнять. Список свойств устроен как специальнаяструктура, подобная записям в Паскале, но указатели в такой записисопровождаются тэгами,символизирующимитипхранимойинформации. Первый элемент этой структуры расположен по адресу,который задан в указателе. Остальные элементы доступны по этому жеуказателю с помощью ряда специальных функций. Элементы структурысодержат различные свойства атома. Каждое свойство помечаетсяатомом, называемым индикатором, или расположено в фиксированномполе структуры.В первых реализациях Лиспа все системные свойства объектоврасполагались по единой схеме.
Перечислим некоторые из индикаторовтаких свойств.PNAME — печатное имя атома для нужд ввода-вывода.EXPR — S-выражение, определяющее функцию с именем атом, всписке свойств которого встречается EXPR.SUBR — функция, определенная подпрограммой на машинномязыке.APVAL — постоянное значение атома, рассматриваемого какпеременная.В списке свойств атома NIL было два индикатора, PNAME и APVAL, созначением NIL.Более детально диаграммы списков свойств приведены в описании Lisp1.5. [1].Здесь достаточно принять к сведению, что реализация атомарныхобъектов — это сложная структура данных, в свою очередьпредставленная списками.С помощью функции GET в форме (GET x i) можно найти для атомаx свойство, индикатор которого равен i .115Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
