globalf5-240972240972 (850810), страница 5
Текст из файла (страница 5)
ATOM2 )Таблица 2.1. Операции над списками. Примеры соответствияаргументов и результатовФункциияАргументыРезультатКонструирование структур данныхCONSA и NIL(A )CONS(A B) и NIL((A B) )CONSA и (B)(A B)(Результат предыдущего CONS ) и (C)((A B) C)24Л.В. ГородняяCONSОсновы функционального программирования(Результат предыдущего CONS ) и (C)((A B) C)A и (B C)(A B C)CDRCARCARCARCONSДоступ к компонентам структуры данных:Слева(A B C)A(A (B C))A((A B) C)(A B)Aне определенСправа(A )NIL(A B C D)(B C D)(A (B C))((B C))((A B) C)(C)Aне определенСмешанная обработка данных:(A B C)(B C)результат предыдущего CDRB(A C)Aрезультат предыдущего CARне определенA и (B)(A B)CARCONSрезультат предыдущего CONSA и (B)A(A B)CDRрезультат предыдущего CONSПредикаты:Атомарность — неделимостьVeryLongStringOfLetters(A B)результат предыдущего CDRNIL( )РавенствоA A(B)CARCARCARCARCDRCDRCDRCDRCDRATOMCDRATOMATOMATOMEQ25T(B)NILTTTЛ.В.
ГородняяEQEQEQEQОсновы функционального программированияA BA (A B)(A B) (A B)NIL и ( )NILNILне определенTЕсли вместо атомовATOM1, ATOM2 рекурсивно подставлятьпроизвольные атомы, затем построенные из них пары и так далее, тополучим множество всех возможных S-выражений. Можно сказать, чтоS-выражение — это или атом или заключенная в скобки пара из двух Sвыражений, разделенных точкой. Все сложные данные выстраиваютсяиз одинаково устроенных блоков — бинарных узлов, содержащих парыобъектов произвольного вида.
Каждый бинарный узел соответствуетминимальному блоку памяти.ATOM(A . B)(C . (A . B))((A . B) . C)((A . B) . (D . C))((A . B) . (D . (C . E)))Любое S-выражение может быть построено из атомов с помощьюCONS, и любая его часть может быть выделена с помощью CAR-CDR.Расширение типа данных, допускаемых в качестве второго аргументаCONS, ни в малейшей степени не усложняет реализацию этой функции,равно как и реализацию функций CAR и CDR, зато их описаниястановятся проще. Функция CONS строит бинарный узел и заполняетего парой объектов, являющихся значениями пары ее аргументов.Первый аргумент размещается в левой части бинарного узла, а второй— в правой. Функция CAR обеспечивает доступ к объектам,расположенным слева от точки, а функция CDR — справа.Таблица 2.2. Операции над произвольными S-выражениямиФункцияАргументыРезультатКонструирование структурданных26Л.В.
ГородняяОсновы функционального программированияAиBCONSCONSCONSCARCARCDRCDRCONSCARCONSCDRCDRCARCDRCARCONSCARCONSCDR(A . B) и CA B(результат предыдущегоCONS ) и C((A . B) . C)(A . B)((A . B) . C)Доступ к компонентамструктуры данных:Слева(A . B)((A . B) . C)Справа(A . B)(A . (B . C))Смешанная обработкаданных:AиBA(A . B)B(B . C)(A .
B)результат предыдущего CONS AAиB(A . B)результат предыдущего CONS B(A . (B . C))(B . C)результат предыдущего CDR B(A . C)Cрезультат предыдущего CDR не определенТождества: (на произвольныхобъектах)два произвольных объекта x(x . y)иyисходный объект x (первыйрезультат предыдущего CONSаргумент CONS )два произвольных объекта x(x . y)иyисходный объект y (второйрезультат предыдущего CONS27Л.В.
ГородняяОсновы функционального программированияаргумент CONS )CARCDRCONSATOMCDRATOMEQпроизвольный составнойобъект xтот же самый объект x - неатом(CAR x)(CDR x)результаты предыдущих CARисходный объект xи CDRПредикаты:Атомарность — неделимостьNIL - выполняет роль ложного(A . B)значения(A .
B)Bрезультат предыдущего CDR TРавенство:(A . B) (A . B)не определенТочечная нотация точнее, чем списки, представляет логику храненияданных в памяти и доступа к компонентам структур данных, но длянепосредственного представления и обработки символьных выраженийона оказалась менее удобной. Практически сразу была предложенаболее лаконичная запись наиболее употребимого подкласса Sвыражений в виде списков произвольной длины вида (A B C D E FG H ). В виде списков можно представить лишь те S-выражения, вкоторых при движении вправо в конце концов обнаруживается атомNIL, символизирующий завершение списка.Атом NIL, рассматриваемый как представление пустого списка (),играет роль ограничителя в любом списке.
Одноэлементный список(A) идентичен S-выражению (A . NIL). Список (A1 A2 ...Ak) может быть представлен как S-выражение вида:(A1 . (A2 . ( ... . (Ak . NIL) ... ))).В памяти это фактически одна и та же структура данных. (Запятая вкачестве разделителя элементов списка в первых реализациях Лиспаподдерживалась, но не прижилась. Пробел оказался удобнее.)28Л.В.
ГородняяОсновы функционального программированияДля многошагового доступа к отдельным элементам такой структурыудобно пользоваться мнемоничными обозначениями композиций измногократных CAR-CDR. Имена таких композиций устроены какцепочки из "a" или "d", задающие маршрут движения из шагов CAR иCDR, соответственно, расположенный между "c" и "r". Указанные такимспособом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. впорядке, обратном записи.Таблица 2.3. Соответствие списков и равнозначных им S-выраженийList-notation — списочнаяDot-notation — точечная нотация тогозапись объектаже объекта(A B C)(A . (B . (C . NIL)))((A .
(B . NIL)) . (C .((A B) C)NIL))(A . (B . ((C . (E .(A B (C E))NIL)). NIL)))(A)(A . NIL)((A))((A . NIL) . NIL)(A (B . C))(A . ((B . C) . NIL))(())(NIL. NIL)Таблица 2.4. Примеры многошагового доступа к элементам структурыВычисляются в порядке, обратномМногократные CARCDRзаписи:Caar((A) B C)ACadr(A B C)B — CDR затем CARCaddr (A B C)C — (дважды CDR ) затем CARCadadr (A (B C) D)C — два раза ( CDR затем CAR )Основные понятия: программа, функции и выраженияГипотезу об универсальности символьных данных, прежде всего,следует проверить при выборе представления форм, возникающих принаписании программы и ее основного конструктива — переменных,констант, выражений, определений, ветвлений, вызовов функций:29Л.В.
ГородняяОсновы функционального программирования1) Самая простая форма выражения — это переменная. Она может бытьпредставлена как атом .XYnVariablelLongSong2) Более сложные формы могут пониматься как применение функции кее аргументам ( вызов функции ). Аргументом функции может бытьлюбая форма. Вызов функции можно строить как список, первыйэлемент которого — представление функции, остальные элементы —аргументы функции .(функция аргумент1 аргумент2 ... )Обычно S-выражение — это или атом, или список ; значит,неатомарное S-выражение можно понимать как вызов функции, есливсе остальные понятия свести к применению некоторыхфункциональных объектов.Теперь можно записывать формы для получения результатов операцийиз таблиц 2.1 и 2.2 в виде списков:(ATOM NIL)(CONS NIL NIL)((LAMBDA (Y X) (CONS X Y)) NIL(ATOM NIL));= (T)((LAMBDA (X Y) (CONS X Y)) NIL(ATOM NIL));= (() .
T)";" - начало строчного комментария. Последние два примерапоказывают роль порядка аргументов функции, задаваемого с помощьюспециального LAMBDA-конструктора.3) Имена функций, как и переменных, лучше всего изображать спомощью атомов, для наглядности можно выбирать заглавные буквы.Соответствие между именем функции и ее определением можно задать30Л.В. ГородняяОсновы функционального программированияс помощью специального конструктора функций LABEL (отсутствует вCommon Lisp), первый аргумент которого — имя функции, второй —собственно именуемое определение функции .
Формальнымрезультатом LABEL является ее первый аргумент, который становитсяобъектом другой категории. Он меняет свой статус — теперь это имяновой функции.(LABEL третий;; имя новой функции(LAMBDA (x) ;; параметры функции(CAR (CDR (CDR x))) ; тело функции) )Пример 2.1.Новая функция "третий" действует так же, как "CADDR" в таблице 2.4.Именование функций работает подобно присваиванию значенийпеременным, но идентификатору присваивается объект другойкатегории — структура, символизирующая функциональный объект,содержащая список формальных параметров функции и тело ееопределения. По отношению к процессам обработки данных разницамежду константами и переменными заключается лишь в том, чтозначение переменной может быть в любой момент изменено, аконстанта изменяется существенно реже.
Обычно в рассуждениях опеременных и константах подразумевается, что речь идет лишь оданных. Поскольку функциональное программирование рассматриваетпредставления функций как данные, постольку и функции могут бытькак константными, так и переменными. Представления функции могутвычисляться и передаваться как параметры или результаты другихфункций. Соответствие между именем функции и ее определениемможет быть изменено, подобно тому, как меняется соответствие междуименем переменной и ее значением.4) Композиции функций можно строить с помощью вложенных скобок.(функция1 (функция2 аргумент21 аргумент22 ...
)аргумент2 ... )Приведенные правила ничего не говорят ни о природе данных ифункций, ни о порядке вычисления аргументов и композиций функций.Речь идет исключительно о форме — внешнем виде списков,31Л.В. ГородняяОсновы функционального программированияиспользуемых для записи программы. Такая синтаксическая оболочка, вкоторой еще не конкретизированы операции над данными, являетсяобщей спецификацией реализационной основы для определенияаппликативных систем, допускающих специализацию практически влюбом направлении.
Можно сказать, что Лисп является аппликативнойсистемой, специализированной для обработки списков или Sвыражений. (Язык функционального программирования Sisal [11]специализирован для обработки многомерных векторов и организациипараллельных процессов, выполняемых на суперкомпьютерах.)Этих правил достаточно, чтобы более ясно выписать основныетождества Лиспа, формально характеризующие элементарные функцииCAR, CDR, CONS, ATOM, EQ над S-выражениями:(CAR (CONS x y));=x(CDR (CONS x y));=y(ATOM (CONS x y)) ; = NIL(CONS (CAR x) (CDR x)) ; = x - для неатомарных x.(EQ x x); = T - если x атом(EQ x y); = NIL - если x и y различимыЛюбые композиции заданного набора функций над конечныммножеством произвольных объектов можно представить такимспособом, но класс соответствующих им процессов весьма ограничен имало интересен. Организация более сложного класса процессов требуетболее детального представления в программах соответствия междуименами и их значениями или определениями, изображения ветвленийи объявления констант.5) Традиция при изучении функционального программированияизбегать знакомства с явными средствами объявления значенийпеременных ради формирования навыков задания таких значений какаргументов функций малосостоятельна, т.к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
