globalf5-240972240972 (850810), страница 15
Текст из файла (страница 15)
Программа из файла может быть загружена псевдофункцией LOAD.(LOAD 'TEST.LST)(PRINT (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) )(PRINT (UNION '(X Y Z) '(U V W X)) )(PRINT (UNION (READ) '(1 2 3 4)) ); объединение вводимого списка со списком; '(1 2 3 4)Именование значений и подвыражений94Л.В. ГородняяОсновы функционального программированияПеременныеПеременная — это символ, который используется для представленияаргумента функции.Таким образом, возвращаясь к Дж.Маккарти [1]:"Можно написать "a + b, где a = 341 и b = 216". В такой ситуации неможет быть недоразумений, и все согласятся, что ответ есть 557. Чтобыполучить этот результат, необходимо заменить переменныефактическими значениями, и затем сложить два числа (на арифмометре,например).Одна из причин, по которой в этом случае не возникает недоразумений,состоит в том, что "a" и "b" не есть приемлемые входы для арифмометра,и следовательно, очевидно, что они только представляют фактическиеаргументы.
При символьных вычислениях ситуация может быть болеесложной. Атом может быть как переменной, так и фактическимаргументом. К дальнейшему усложнению приводит то обстоятельство,что некоторые из аргументов могут быть переменными, вычисляемымивнутри вызова другой функции. В таких случаях интуитивный подходможетподвести.Дляэффективногопрограммированиявфункциональном стиле необходимо более точное пониманиеформализмов.Чтобы не обескураживать читателей, следует заметить, что здесь ничегопринципиально нового нет.
Все, что сейчас рассматривается, можетбыть логически выведено из правил представления программ в виде Sвыражений или из определения универсальных функций eval/apply, иявляется их непосредственным следствием, возможно, не вполнеочевидным.Любой формализм для переменных сводится к лямбда-обозначению.Часть интерпретатора, которая при вычислении функций связываетпеременные, называется APPLY.
Когда APPLY встречает функцию,начинающуюся с LAMBDA, список переменных попарно связывается сосписком аргументов и добавляется к началу а-списка. При вычислениифункции могут быть обнаружены переменные. Они вычисляются95Л.В. ГородняяОсновы функционального программированияпоиском в а-списке. Если переменная встречается несколько раз, тоиспользуется последнее или самое новое значение.
Частьинтерпретатора,котораяделаетэто,называетсяEVAL.Проиллюстрируем данное рассуждение на примере. Предположим, чтоинтерпретатор получает следующее S-выражение:((LAMBDA (X Y) (CONS X Y)) 'A 'B)Функция: ((LAMBDA (X Y) (CONS X Y)) 'A 'B)Аргументы: (A B)EVAL через EVAL-A передает эти аргументы функции APPLY. (См. лек.3).(APPLY #'(LAMBDA (X Y) (CONS X Y)) '(A B) Nil )APPLY свяжет переменные и передаст функцию и удлинившийся асписок EVAL для вычисления.(EVAL '(CONS X Y) ' ((X . A) (Y . B) . Nil))EVAL вычисляет переменные и сразу передает их консолидации функции CONS, строящей из них бинарный узел.(Cons 'A 'B) = (A . B)EVAL вычисляет переменные и сразу передает их консолидации,строящей из них бинарный узел.Реальный интерпретатор пропускает один шаг, требуемый формальнымопределением универсальных функций".На практике сложилась традиция включать в систему функциональногопрограммирования специальные функции, обеспечивающие иерархиюконтекстов, в которых переменные обладают определенным значением.Для Clisp это LET и LET *.96Л.В.
ГородняяОсновы функционального программированияLET сопоставляет локальным переменным независимые выражения. Сее помощью можно вынести из сложного определения любыесовпадающие подвыражения.(DEFUN UNION (x y)(LET ( (a-x (CAR x))(d-x (CDR x))) ; конец списка локальных именованных значений(COND ((NULL x) y)((MEMBER a-x y) (UNION d-x y) ) ; использование локальных(T (CONS a-x (UNION d-x y)) ) ; значений из контекста) ) ; завершение контекста LET)LET * — сопоставляет локальным переменным взаимосвязанныевыражения.
Она позволяет дозировать сложность именуемыхподвыражений.(DEFUN MEMBER (a x)(LET* ( (N-X (NULL x))(a-x (CAR x))(d-x (CDR x))(e-car (EQ a a-x))) ; список локально именованных выражений(COND (N-X Nil); использование(E-CAR T); именованных(T (MEMBER A D-X)) ; выражений) ) ; выход из контекста именованных выражений)(Эквивалентность с точностью до побочного эффекта.)Глобальные переменные можно объявить с помощью специальнойфункции DEFPARAMETER.(DEFPARAMETER GLOB '(a b c))97Л.В. ГородняяОсновы функционального программированияЗначение такой переменной доступно в любом контексте, оно можетбыть переопределено. Возможно оттеснение одноименнымилокальными переменными с восстановлением при выходе изсоответствующих контекстов. При выполнении кода программ:(LET ((GLOB 12))(PRINT GLOB))(PRINT GLOB)напечатано будет:12(A B C)КонстантыДж.Маккарти обращает внимание [1]:"Иногда говорят, что константыпредставляют сами себя, в противоположность переменным,представляющим что-то другое.
Это не вполне точно, посколькуобычно константы представляют как a, b, c, ..., а переменные как x, y, z,... — но и то, и другое выглядит как атом. Удобнее говорить, что однапеременная ближе к константам, чем другая, если она связана на болеевысоком уровне и ее значение изменяется не столь часто.Обычно переменная считается связанной в области действия лямбдаконструктора функции, который связывает переменную внутри телаопределения функции путем размещения пары из имени и значения вначале а-списка. В том случае, когда переменная всегда имеетопределенное значение независимо от текущего состояния а-списка, онабудет называться константой.
Такую неизменяемую связь можноустановить, помещая пару (a . v) в конец a-списка. Но в реальныхсистемах это организовано с помощью так называемого списка свойстватома, являющегося представлением переменной. Каждый атом имеетсвой p-список (property list), доступный через хэш-таблицуидентификаторов, что действует эффективнее, чем a-список. С каждыматомом связана специальная структура данных, в которой размещаетсяимя атома, его значение, определение функции, представляемой этимже атомом, и список произвольных свойств, помеченныхиндикаторами. При вычислении переменных EVAL исследует эту98Л.В. ГородняяОсновы функционального программированияструктуру до выполнения поиска в а-списке.
Такое устройствопеременных не позволяет им служить в а-списке".Константы могут быть заданы программистом. В системе Clisp чтобыпеременная X стала обозначением для (A B C D), надо воспользоватьсяпсевдо-функцией DEFCONSTANT.(DefConstant X '(A B C D))Особый интерес представляет тип констант, которые всегда обозначаютсебя, Nil — пример такой константы. Такие константы как T, Nil и другиесамоопределимые константы (числа, строки) не могут использоваться вкачестве переменных.
Cмысл чисел и строк не может быть изменен спомощью DEFCONSTANT.ФункцииСитуация, когда атом обозначает функцию, реализационно подобна той,в которой атом обозначает аргумент. Если функция рекурсивна, то ейнадо дать имя. Теоретически это делается с помощью формы LABEL,которая связывает название с определением функции в ассоциативномсписке (а-списке). Название связано с определением функции точно также, как переменная связана со своим значением.
На практике LABELиспользуется редко. Удобнее связывать название с определением другимспособом. Это делается путем размещения определения функции всписке свойств атома ( р-список ), символизирующего ее название.Выполняет данную операцию псевдо-функция DEFUN, описанная вначале этой лекции. Когда APPLY интерпретирует функцию,представленную атомом, она исследует р-список до поиска в а-списке.Таким образом, DEFUN будет опережать LABEL.Тот факт, что большинство функций — константы, определенныепрограммистом, а не переменные, изменяемые программой, вызванотнюдьнекаким-либонедостаткомфункциональногопрограммирования.
Напротив, он указывает на потенциал подхода,который мы не научились использовать лучшим образом. (Работы потеории компиляции, оптимизации и верификации программ,смешанным вычислениям, суперпрограммированию и т.п. активноиспользуют средства функционального программирования.)99Л.В. ГородняяОсновы функционального программированияСистемыфункциональногопрограммированияобеспечиваютвозможность манипулирования функциональными переменными также, как и обычными. Но организуется это с помощью ряда специальныхфункций, осуществляющих переход от символов, изображающихфункции, к функциональным объектам, представленным этимисимволами.
Такой переход может быть реализован в рамках любогоязыка программирования, но на Лиспе он выглядит естественно иподдерживается в любой Лисп-системе. Рассмотрим средства Clisp,обеспечивающие структурирование функциональных объектов.LABELS — позволяет из списка определений функций формироватьконтекст, в котором вычисляются выражения.FLET — специальная функция, позволяющая вводить локальныенерекурсивные функции.DEFUN — позволяет вводить новые определения на текущем уровне.(LABELS ( (INTERSECTION (x y)(LET* ( (N-X (NULL x))(MEM-CAR (MEMBER (CAR x) y))(INT #'INTERSECTION)) ; конец списка локальных выражений let*(FLET ((F-TAIL (FN sx sy)(APPLY FN (LIST (CDR sx) sy)) )(CONS-F-TAIL (FN sx sy)(CONS (CAR sx)(APPLY FN (LIST (CDR sx) sy)))) ) ; конец списка нерекурсивных функций FLET(COND (N-X NIL); выражение, использующее(MEM-CAR (cons-f-tail INT x y) ) ; локальные определения функц(T (f-tail INT x y)) ); из контекстов FLET и; LABELS) ; выход из контекста FLET) ; выход из контекста LET*) ; завершено определение INTERSECTION100Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
