Основные понятия: программа, функции и выражения
Гипотезу об универсальности символьных данных, прежде всего, следует проверить при выборе представления форм, возникающих при написании программы и ее основного конструктива — переменных, констант, выражений, определений, ветвлений, вызовов функций:
1) Самая простая форма выражения — это переменная. Она может быть представлена как атом.
X Y n Variablel LongSong
2) Более сложные формы могут пониматься как применение функции к ее аргументам (вызов функции). Аргументом функции может быть любая форма. Вызов функции можно строить как список, первый элемент которого — представление функции, остальные элементы — аргументы функции.
(функция аргумент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) Имена функций, как и переменных, лучше всего изображать с помощью атомов, для наглядности можно выбирать заглавные буквы.
Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций LABEL (отсутствует в Common Lisp), первый аргумент которого — имя функции, второй — собственно именуемое определение функции. Формальным результатом LABEL является ее первый аргумент, который становится объектом другой категории. Он меняет свой статус — теперь это имя новой функции.
(LABEL третий ; имя новой функции (LAMBDA (x) ; параметры функции (CAR (CDR (CDR x))) ; тело функции ) )
Пример 2.1.
Новая функция "третий" действует так же, как "Cadadr" в таблице 2.4. Именование функций работает подобно присваиванию значений переменным, но идентификатору присваивается объект другой категории — структура, символизирующая функциональный объект, содержащая список формальных параметров функции и тело ее определения.
По отношению к процессам обработки данных разница между константами и переменными заключается лишь в том, что значение переменной может быть в любой момент изменено, а константа изменяется существенно реже. Обычно в рассуждениях о переменных и константах подразумевается, что речь идет лишь о данных. Поскольку функциональное программирование рассматривает представления функций как данные, постольку и функции могут быть как константными, так и переменными. Представления функции могут вычисляться и передаваться как параметры или результаты других функций. Соответствие между именем функции и ее определением может быть изменено, подобно тому, как меняется соответствие между именем переменной и ее значением.
4) Композиции функций можно строить с помощью вложенных скобок.
(функция1 (функция2 аргумент21 аргумент22 ... ) аргумент2 ... )
Приведенные правила ничего не говорят ни о природе данных и функций, ни о порядке вычисления аргументов и композиций функций. Речь идет исключительно о форме — внешнем виде списков, используемых для записи программы. Такая синтаксическая оболочка, в которой еще не конкретизированы операции над данными, является общей спецификацией реализационной основы для определения аппликативных систем, допускающих специализацию практически в любом направлении. Можно сказать, что Лисп является аппликативной системой, специализированной для обработки списков или 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) Традиция при изучении функционального программирования избегать знакомства с явными средствами объявления значений переменных ради формирования навыков задания таких значений как аргументов функций малосостоятельна, т.к. изменение переменных легко моделируется переопределением функций без аргументов. Поэтому признаем сразу, что значение переменной можно объявить специальной функцией SET.
(Set 'PI 3.1415926)
6) Обычно в системы программирования встраивают наиболее часто используемые константы. Некоторые атомы изначально имеют определенный смысл, например, базовые функции, представление пустого списка Nil и тождественно истинная константа T
В зависимости от контекста одни и те же объекты могут играть роль переменных или констант, причем значения и того, и другого могут быть произвольной сложности. Если объект играет роль константы, то для объявления константы достаточно заблокировать его вычисление, то есть как бы взять его в кавычки (quotation), отмечающие буквально используемые фразы, нетребующие обработки. Для такой блокировки вводится специальная функция QUOTE, предохраняющая свой единственный аргумент от вычисления.
(QUOTE A) ; константа атом A (QUOTE (A B C) ) ; константа список (A B C) (ATOM (QUOTE A)) ; = T — аргумент предиката - атом A (ATOM (QUOTE (A B C) )) ; = Nil — аргумент предиката - список (A B C) (ATOM A) ;— значение не определено
Оно зависит от вхождения переменной A, а ее значение зависит от контекста и должно быть определено или задано до попытки выяснить, атом ли это.
Можно сказать, что функция QUOTE выполняет в древовидной структуре программы роль помеченного контейнера. С ее помощью любое выражение может быть заключено в контейнер, а контейнер помечен указанием, что вычислять его содержимое не следует. Потом, при выполнении функции QUOTE, пометка и контейнер исчезают, и выражение может обрабатываться по общей схеме.
Например: (третий (QUOTE (A B C))) — применение функции "третий" к значению, не требующему вычисления.
7) Некоторые определения функций могут быть хорошо определены на одних аргументах, но зацикливаться на других, подобно традиционному определению факториала при попытке применить его к отрицательным числам. Результат может выглядеть как исчезновение свободной памяти или слишком долгий счет без видимого прогресса. Такие функции называют частичными. Их определения должны включать в себя ветвления для проверки аргументов на принадлежность фактической области определения функции — динамический контроль. Точнее, вычисление ряда форм в определении может быть обусловлено заранее заданными предикатами.
Ветвление (условное выражение) характеризуется тем, что ход процесса зависит от некоторых предикатов (условий), причем условия следует сгруппировать в общий комплект и соотнести с подходящими ветвями. Такую организацию процесса вычисления обеспечивает специальная функция COND (condition), аргументами которой являются двухэлементные списки, содержащие предикаты и соответствующие им выражения. Аргументов может быть сколько угодно, а обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента, и вычисляется его значение, которое и считается значением всего условного выражения.
(COND (p1 e1) (p2 e2) ... (pk ek) )
pi - предикаты для выбора ветви,
ei - ветви условного выражения
Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.
Обычное условное выражение (if Predicate Then Else) или (если Predicate то Then иначе Else) может быть представлено с помощью функции COND следующим образом:
(COND (Predicate Then)(T Else))
Разумеется, можно повышать наглядность подбором геометрии текста:
(COND (Predicate Then) (T Else) )
(COND ((EQ (CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x)) ) (T x) )
Пример 2.2.
Атом T представляет тождественную истину. Значение всего условного выражения получается путем замены первого элемента из значения переменной x на B в том случае, если (CAR x) совпадает с A
Содержательно функции QUOTE, COND, LAMBDA образуют базовый комплект средств управления программами и процессами, поддерживающий стиль программирования, идеологически близкий структурному программированию [18].
Такие специальные функции QUOTE, COND, LAMBDA существенно отличаются от элементарных функций CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычные функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции. Специальные функции не требуют такой предварительной обработки параметров. Они сами могут выполнять все необходимое, используя представление фактических параметров в виде S-выражений.
