Функциональное программирование

(функция аргумент1 аргумент2 ... )

Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций. Вместо конструктора LABEL, описанного в лекции 1, в реальные системы программирования включают ряд средств с разными особенностями подготовки, реализации и применения определений функций. Common Lisp включает в себя конструктор функций DEFUN, первый аргумент которого - имя функции, второй - список аргументов функции, а третий - тело определения функции. Формальным результатом DEFUN является ее первый аргумент, который меняет свой статус - теперь это имя новой функции. Определение функции строится с помощью неявного LAMBDA-конструктора, объединяющего список аргументов функции и тело ее определения.

Пример 7.1. Новая функция "третий".

(DEFUN третий 
            (x) 
       (CAR (CDR (CDR x))) 
   )   
; Атом "третий" связан 
;с выражением " ( LAMBDA (x ) (CAR (CDR (CDR x ))) ) "

имя новой функции 
параметры функции
тело функции

Именование функций работает подобно присваиванию значений переменным, но идентификатору присваивается объект другой категории - структура, символизирующая функциональный объект, содержащая список формальных параметров функции и тело ее определения. Представления функции могут вычисляться и передаваться как параметры или результаты других функций. Соответствие между именем и определением функции может быть изменено, подобно тому, как меняется соответствие между именем переменной и ее значением.

(функция1 (функция2 аргумент21 аргумент22 ... )
                   аргумент2 ... )

Приведенные правила ничего не говорят ни о природе данных и функций, ни о порядке вычисления аргументов и композиций функций. Речь идет исключительно о форме - внешнем виде списков, используемых для записи программы. Такая синтаксическая оболочка, в которой еще не конкретизированы операции над данными, является общей спецификацией реализационной основы для определения аппликативных систем, допускающих специализацию практически в любом направлении. Можно сказать, что Лисп является аппликативной системой, специализированной для обработки списков.

Если объект играет роль константы, то для объявления константы достаточно заблокировать его вычисление, как бы взять его в кавычки (quotation), отмечающие буквально используемые фразы, не требующие обработки. Для такой блокировки вводится специальная функция QUOTE, предохраняющая свой единственный аргумент от вычисления.

(QUOTE (A B C) )    - константа  (A B C) объявлена

Можно сказать, что функция QUOTE выполняет в древовидной структуре программы роль помеченного контейнера. С ее помощью любое выражение может быть заключено в контейнер, а контейнер помечен указанием, что вычислять его содержимое не следует.

Ветвление ( условное выражение ) обеспечивает специальная функция COND (condition), аргументами которой являются двухэлементные списки, содержащие предикаты и соответствующие им выражения. Аргументов может быть сколько угодно, а обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента, и вычисляется его значение, которое и считается значением всего условного выражения.

(COND (p1 e1) (p2 e2) ... (pk ek) )
          |   |_______|__________|_______ ветви условного выражения    
          |_______|___________|__________ предикаты для выбора ветви

Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.

Специальные функции QUOTE, COND, LAMBDA и DEFUN существенно отличаются от обычных функций CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычно функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции. Специальные функции не требуют такой предварительной обработки параметров. Они сами могут выполнять все необходимое, используя представление фактических параметров в виде списков.

(DEFUN премьер (x)(COND ((ATOM x) x)
                                       (T (премьер (CAR x ))) ))

Точные границы применимости функций определяются в виде определения универсальной функции EVAL, позволяющей вычислять значения выражений, представленных в виде списков, - правило интерпретации выражений.

Такая единая структура данных оказалась вполне достаточной для представления сколь угодно сложных программ.

Выполнение программы устроено как интерпретация данных, представляющих выражения, имеющие значение.

Пример 7.7. Определить функцию покомпонентной обработки двух списков с помощью заданной функции fn:

(defun map-comp (fn al vl); fn покомпонентно применить
        ; к соотвественным элементам AL и VL
     (cond
             (xl (cons (funcall fn (car al) (car vl))         
        ; Вызов данного FN как функции от элементов двух списков
                       (map-comp (cdr al) (cdr vl))
)    )  )   )

Теперь покомпонентные действия над векторами, представленными с помощью списков, полностью в наших руках. Вот списки и сумм, и произведений, и пар, и результатов проверки на совпадение:

(map-comp #'+ '(1 2 3) '(4 6 9))      
                                        ; = (5 8 12 ) Суммы
(map-comp #'* '(1 2 3) '(4 6 9))    
                                        ; = (4 12 27 ) Произведения
(map-comp #'cons '(1 2 3) '(4 6 9)) 
                                        ; = ((1 . 4)(2 . 6)(3 . 9)) Пары
(map-comp #'eq '(4 2 3 ) '(4 6 9))
                                       ; = (T NIL NIL ) Сравнения

Достаточно уяснить, что надо делать с элементами списка, остальное довершит функционал map-comp, отображающий этот список в список результатов заданной функции.

Пример 7.8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первый элемент, остальные элементы списка без первого.

(defun mapf (fl el)
     (cond                        ; Пока первый аргумент не пуст,
        (fl (cons (funcall (car fl) el ) 
                                 ; применяем очередную функцию
                                 ; ко второму аргументу

                  (mapf (cdr fl) el)  
                     ; и переходим к остальным функциям,
)    )  )   )        ; собирая их результаты в общий список

(mapf '(length car cdr) '(a b c d ))      ; = (4 a (b c d ))

Композициями таких функционалов можно применять серии функций к списку общих аргументов или к параллельно заданной последовательности списков их аргументов. Естественно, и серии, и последовательности представляются списками.

На практике сложилась традиция в систему функционального программирования включать специальные функции, обеспечивающие иерархию контекстов, в которых переменные обладают определенным значением. Для Clisp это ].

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 -Примечание. Эквивалентность с точностью до побочного эффекта сопоставляет локальным переменным взаимосвязанные выражения. Она позволяет дозировать сложность именуемых подвыражений. Пример:

(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)))  )        ))

Labels - позволяет из списка определений функций формировать контекст, в котором вычисляются выражения.

Flet - специальная функция, позволяющая вводить локальные нерекурсивные функции.

defun - позволяет вводить новые определения на текущем уровне.

Лисп хорошо приспособлен к оптимизации программ. Любые совпадающие подвыражения можно локализовать и вынести за скобки, как можно заметить по передаче значения "(ASSOC e al )" в нижеприведенном определении интерпретатора с явным выделением зависимости от набора встроенных функций. Определения функций хранятся в ассоциативном списке подобно значениям переменных.

В качестве примера повышения гибкости определений приведено упрощенное определение Лисп-интерпретатора на Лиспе, полученное из М-выражения, приведенного Дж. Мак-Карти в описании Lisp 1.5 []. Уменьшена диагностичность, нет предвычислений и формы Prog.

В сравнении с определением в лекции 1 уточнена работа с функциональными аргументами:

(DEFUN EVAL  (e al )
      (COND         ((EQ e NIL ) NIL )   
((ATOM e ) ((LAMBDA (v )
                      (COND (v (CDR v ) )   
                            (T (ERROR 'undefvalue )) )
                      ) (ASSOC e al ) )
                   )

        ((EQ (CAR e) 'QUOTE )    (CAR (CDR e )) )
        ((EQ (CAR e) 'FUNCTION ) (LIST 'FUNARG (CADR fn ) al ) )
        ((EQ (CAR e) 'COND  )    (EVCON (CDR e ) al ) ) 
        (T (apply (CAR e) (evlis (CDR e) al ) al ) )
)  )  
(DEFUN APPLY (fn args al )
      (COND

        ((EQ e NIL ) NIL )   
        ((ATOM fn )
             (COND 

                 ((MEMBER fn '(CAR CDR CONS ATOM EQ )) (SUBR fn agrs al ))
                 (T (APPLY (EVAL fn al ) args al ))
        )    )

        ((EQ (CAR fn ) 'LABEL )
                (APPLY (CADDR fn )
                       args
                       (CONS (CONS (CADR fn ) (CADDR fn )) 
                              al ) ) )

((EQ (CAR fn ) 'FUNARG )
             (APPLY (CDR  fn ) args (CADDR  fn))
        )
        ((EQ (CAR fn ) 'LAMBDA )
                          (EVAL (CADDR fn )
                                (APPEND (PAIR (CADR fn ) args ) al ))
        (T (APPLY (EVAL fn al ) args al ))
 )  )

Определения assoc, append, pair, list - стандартны.

SUBR - Функция, вызывающая примитивы, реализованные другими, обычно низкоуровневыми, средствами.

ERROR - Функция, выдающая сообщения об ошибках и сведения о контексте вычислений, способствующие поиску источника ошибки.