учебники, программирование, основы, введение в,

 

Функции высших порядков

Ранжирование функций
Применение функций высших порядков естественным образом завершает освоение функционального программирования как логической системы, допускающей конструирование функциональных объектов при решении задач регулярной обработки формализованной информации. Подобные задачи возникают при реализации и настройке сложных информационных систем, таких как операционные системы, системы программирования, текстовые и графические процессоры, системы управления базами данных, поддержки проектов и т.п.
Функции высших порядков используют другие функции в качестве аргументов или вырабатывают их как результат.
(defun mul-N (N) #'(lambda (x) (* x N)))
; конструктор семейства функций, множащих
; аргумент на N
(funcall (mul-N 25) 7)
; применение частной функции, умножающей на 25
Правильность выражений с такими функциями требует корректной подстановки параметров и учета ранга функции, определяющего возможность манипулирования функциональными значениями. Функции можно ранжировать на основе так называемых типовых выражений, представляющих области определения и значения функций. Например,
x+1 : Number -> Number

x+y : (Number Number) -> Number
Отсутствие таких средств в языке можно компенсировать соответствующими комментариями.
Суперпозицию функций можно характеризовать следующими типовыми выражениями:
S(h,g) = { при h: X -> Y, g: Y -> Z строит f=g(h)
— суперпозиция }
: (X->Y Y->Z) -> (X->Z)

(defun super (f g)
#'(lambda (x) (funcall f (funcall g x)) ))
; конструктор суперпозиции функций

(funcall (super #'car #'cdr) '(1 2 3))
; применение суперпозиции CAR и CDR
Двойное применение функции можно определить независимо или через суперпозицию — типовое выражение от этого не зависит, но оно представляет собой параметризованное выражение.
W f = ((lambda x)(f (f x))) = S (f,f)
{ дважды применяется функция }
: (Number->Number) -> (Number->Number)
или более точно:
: (X->X) -> (X->X),
где X — произвольный тип значения. Типовое выражение представляет зависимость от этого типа — параметризованный тип значения.
(defun duble (f)
#'(lambda (x) (funcall f(funcall f x)) ))
; конструктор двойного применения функции

(funcall (duble #'car) '(((1) 2) 3))   ;= (1)

(defun duble (f) (funcall #'super f f))
; двойное применение функции через суперпозицию

(funcall (duble #'car) '(((A B) B) C))
; = (A B)
Можно ввести обозначения:
Atom — атомы,
Number — число,
List (X) — NIL или списки из элементов типа X
Bool — NIL или T,`
Some — любой объект.
Соответственно пишутся типовые выражения для элементарных функций:
cons      : (X List (X)) -> List (X)
car        : List (X) -> X
cdr        : List (X) -> List (X)
eq         : (Atom Atom) -> Bool
atom     : Some -> Bool
: (Atom -> T) & (List (X) -> NIL)
null       : Some -> Bool
: (NIL -> T) & (Atom \=NIL -> NIL)
& (List(X)\=NIL -> NIL) 
Таким же образом можно специфицировать и универсальную функцию:
eval [e, al]:(Some List( (Atom . Some ) )) -> Some
|   |
|   List( (Atom . Some) )
Some{ могут попасть и неправильные выражения }

apply [fn, (a1 a2 …), al]:(List( Some ) -> Some
List( Some )
List((Atom . Some) ))
|   |         |      -> Some
|   |      List((Atom . Some))
|   List(Some)
(List(Some) -> Some
Отображающий функционал также может характеризоваться типовым выражением:
map [x, f]
:( List(X) (X->Y) ) -> List(Y)

(defun map (x f)
(cond (x (cons (funcall f (car x))
(map (cdr x) f )))))
(map '((1) (2) (3)) #'car )
Можно построить функцию, непосредственно преобразующую свой функциональный аргумент в новую функцию.
mapf [f]
: List(X->Y) ->( List(X) -> List(Y))

(defun mapf (f) #'(lambda (x)
(cond (x (cons (funcall f (car x))
(funcall (mapf f ) (cdr x)) ))) ))
(funcall (mapf #'car ) '((1) (2) (3)) )
Аргумент может быть списком функций, результаты которых следует собрать в общий список.
manyfun [lf] :  List(X->Y) ->  (X ->  List(Y))
|              |      |_____список
|              | результатов функций
|              |_____тип аргумента
| отдельной функции
|____________________список функций
(defun manyfun (lf) #'(lambda (x)
(cond (lf (cons (funcall (car lf) x)
(funcall (manyfun (cdr lf)) x) ))) ))
(funcall (manyfun '(car cdr length)) '(1 f (2 T)
(3 D e)) ) 
Таким образом можно как бы «просачивать» определения функций над простыми данными, распределять их по структурам данных и тем самым распространять простые функции на сложные данные подобно матричной арифметике. Такой стиль работы характерен для теории комбинаторов и языка FORTH.
Похожие построения предлагаются Бэкусом в его программной статье о функциональном стиле программирования и в языке APL, ориентированном на обработку матриц.
Существует ряд языков функционального программирования, требующих или допускающих спецификацию объектов, что, кроме дисциплины программирования, дает средства для корректной работы с пакетами, сопряжения с модулями на других языках, оптимизирующих преобразований, распараллеливания и верификации программ (Sisal, ML и др.).

Конструирование распознавателей
Результативность функций высших порядков Хендерсон показывает на модельной задаче построения распознавателя   контекстно-свободного языка.
В качестве примера такого языка рассмотрен синтаксис понятия «слог», образованный по правилам из гласных и согласных звуков, что можно представить грамматикой вида:
<а-гр> ::= А | А <а-гр>

<в-гр> ::= В | В <в-гр>

<слог> ::= <а-гр> <в-гр>
| <в-гр> <а-гр>
| <в-гр> <а-гр> <в-гр>
В этой грамматике «А» и «В» — терминальные символы, «слог», «а-гр» и «в-гр» — нетерминальные символы (метапонятия), «слог» — основное понятие. Необходимо быстро построить предикат is-syllable, выделяющий списки, представляющие правильно построенные слоги в соответствии с приведенными правилами.
Такое построение можно выполнить с помощью ряда функций высокого порядка, конструирующих распознаватели для альтернатив и цепочек из понятий, к которым сводится определение грамматики языка. Предполагается, что каждому правилу будет соответствовать свой распознающий предикат. Для простоты ограничимся случаями из пар альтернатив и двухзвенных цепочек.
Пусть тексты этого языка представляются списками из однобуквенных атомов A и B. Допустим, имеются предикаты is-A и is-B, выделяющие одноэлементные списки (A) и (B), соответственно.
(defun is-a (x)(cond ((eq(car x) 'a)
(null (cdr x))) ))
; распознаватель A
(defun is-b (x)(cond ((eq(car x) 'b)
(null (cdr x))) ))
; распознаватель B
Типовые ранги этих функций одинаковы: List (X) -> Bool. Таким же должен быть и ранг результирующей функции is-syllable. При ее построении будет применена вспомогательная функция более высокого порядка is-alt, которая из произвольных предикатов конструирует новый предикат, перебирающий варианты правил и выдающий Nil, если ни одно из них не подходит. Функция is-alt может быть определена следующим образом:
(defun is-alt (p q)
#'(lambda (x)
(cond ((funcall p x )T)
; конструктор распознавателя альтернатив
((funcall q x) T)
(T Nil))))
Ее типовый ранг имеет вид:
(List(X)->Bool List(X)->Bool ) -> List(X)->Bool
Можно использовать эквивалент:
(defun is-alt (p q)
#'(lambda (x)
(if (funcall p x) T (funcall q x))
)  
Предикат both, работающий как логическая связка «и», можно реализовать как обычную функцию с типовым рангом (Bool Bool) -> Bool.
(defun both (x y) (cond ( x y)(T Nil)) )
; проверка одновременности условий
Еще одна вспомогательная функция высокого порядка is-chain из произвольных предикатов конструирует новый предикат, выясняющий, не выделяют ли исходные предикаты смежные звенья цепочки. Типовый ранг этой функции должен быть таким же, как у is-alt, т.к. их результаты используются при разборе и анализе текста в одинаковых позициях.
(defun is-chain (p q) #'(lambda (x )
; конструктор распознавателя цепочек
(cond ((null x) (both (funcall p x)
(funcall q nil)) )
; пустая цепочка
((both (funcall p x) (funcall q nil)) T)
; префикс без суффикса
((both (funcall p Nil) (funcall q x)) T)
; суффикс без префикса
((both (funcall p (cons (car x)Nil))
(funcall q (cdr x)) ) T)
; допустимое разбиение
(T(funcall (is-chain (lambda(y)
(funcall p(cons(car x)y)))
q ) (cdr x) )) )))
; сдвиг границы разбиения вправо
Из данного распознавателя is-a можно бы и без функций высших порядков построить распознаватель is-a-gr, распознающий группу из любого числа символов A:
(defun is-a-gr (x ) (if x
; распознаватель цепочек из A
(cond ((eq (car x) 'a) (is-a-tl (cdr x)) )
; <а-гр> ::= А | А <а-гр>
(t nil) ) Nil))

(defun is-a-tl (x)(cond ((null x)T)((eq (car
x)'A)(is-a-tl (cdr x )) ))))
; хвост цепочки из A
Но использование конструкторов is-alt и is-chain, показанное на примере распознавателя is-b-gr, позволяет построить определение, синтаксически подобное правилу грамматики:
(defun is-b-gr (x ) (funcall (is-alt #'is-b
is-chain #'is-b #'is-b-gr)) x ))
; распознаватель цепочек из B
; <в-гр> ::= В | В <в-гр>
Теперь опробованные приемы конструирования распознавателей применяем к построению функции is-syllable, активно опираясь на чисто внешнее, синтаксическое подобие определению заданной грамматики:
(defun is-syllable (x )
; распознаватель слога
(funcall (is-alt (is-chain #'is-b-gr #'is-a-gr)
; BA
(is-alt (is-chain #'is-a-gr #'is-b-gr)
; AB
(is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr))
; BAB
) ) x ))

(is-syllable '(a b))
(is-syllable '(b a))
(is-syllable '(b a b ))
(is-syllable '(b b b b a a b b ))
Сопоставляя правила и полученное определение распознавателя, можно убедиться, что собственно конструирование распознавателя осуществляется и модернизируется сравнительно быстро: достаточно свести распознаваемый язык к композиции альтернатив и цепочек.
<слог> ::= <в-гр> <а-гр>
| <а-гр> <в-гр>
| <в-гр> <а-гр> <в-гр>

(defun is-syllable (x )
; распознаватель слога
; <слог> ::=
(funcall (is-alt (is-chain #'is-b-gr #'is-a-gr)
; BA
;         <в-гр> <а-гр>
(is-alt (is-chain #'is-a-gr #'is-b-gr)
; AB
;      |   <a-гр> <b-гр>
(is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr))
; BAB
;      |   <в-гр> <а-гр> <в-гр>

      ) ) x ))
Результат сопоставления показывает, что достигнуто синтаксическое подобие определения грамматики и построенного распознавателя. Это значит, что определение можно автоматически отобразить в такой распознаватель. Отображение — функция высокого порядка, вырабатывающая в качестве результата распознаватель языка, порождаемого исходной грамматикой.
(defun is-alt (p q) #'(lambda (x)
(cond
((funcall p x )T) ((funcall q x) T) (T Nil))))

(defun is-chain (p q) #'(lambda (x )
(cond ((null x) nil)
; пустая цепочка недопустима
((both(funcall p x) (funcall q nil)) T)
; префикс допустим
((both(funcall p Nil) (funcall q x)) T)
; суффикс допустим
((both(funcall p (cons (car x)Nil))
(funcall q (cdr x)) ) T)
; допустимое разбиение
(T(funcall (is-chain (lambda(y)
(funcall p(cons(car x)y)))
; сдвиг вправо границы разбиения
(lambda(y)(funcall q y)) ) (cdr x))) )))

(defun is-syllable (x )
; распознаватель слога
(funcall (is-alt (is-chain #'is-b-gr #'is-a-gr)
; BA
(is-alt (is-chain #'is-a-gr #'is-b-gr)
; AB
(is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr))
; BAB
) ) x ))

<слог> ::= <в-гр> <а-гр>
| <а-гр> <в-гр>
| <в-гр> <а-гр> <в-гр>

Преобразование определений
Конечно, построенное выше определение не отличается эффективностью. Обычно синтаксические формулы приводят к нормализованной форме, гарантирующей полезные свойства распознавателей и удобство их построения. Выбор нормализованной формы и процесс нормализации обосновывается доказательными построениями, на практике воспринимаемыми как эквивалентные преобразования. Преобразования формул — еще один интересный класс задач символьной обработки. Для демонстрации рассмотрим модель реализации функций свертки текстов. При подходящем выборе обозначений такие функции можно применять для преобразования синтаксических формул с целью приведения к нормализованной форме.
Пусть свертки   системы текстов представлены в стиле самоописания подобно формам Бекуса-Наура списком вида:
( (Тексты (Имя Вариант ...)...)
      ; первое имя — обозначение системы текстов
      ; за ним следуют варианты поименованных текстов
   (Вариант Элемент ...)
      ; Вариант представляет собой
      ; последовательность Элементов
   (Элемент Имя Лексема (Варианты))
      ; Элемент — это или Имя, или Лексема,
      ; или Варианты в скобках
)
Для системы текстов «((м а ш и н а)(м а ш а)(ш и н а))» можно дать свертку вида:
( (пример (ма ((ш н)
                      (ш а))
                     ( ш н ) )
   (н ина)
)
Построение свертки   системы текстов выполняется функциями unic, ass-all, swin, gram, bnf :
(defun unic (vac) (remove-duplicates (mapcar 'car
   vac) ))
;; список уникальных начал
 
(defun ass-all (Key Vac)
;; список всех вариантов продолжения
;; что может идти за ключом
   (cond
   ((Null Vac) Nil)
   ((eq (caar Vac) Key) (cons (cdar Vac)
         (ass-all Key (cdr Vac)) ))
   (T (ass-all Key (cdr Vac)) )
) )
 
(defun swin (key varl) (cond
;; очередной шаг свертки или снять скобки при
;; отсутствии вариантов
   ((null (cdr varl))(cons key (car varl)))
   (T (list key (gram varl)) )
))
 
(defun gram (ltext)
;; левая свертка, если нашлись общие начала
   ( (lambda (lt) (cond
      ((eq (length lt)(length ltext)) ltext)
      (T (mapcar
         #'(lambda (k) (swin k (ass-all k ltext )
               ))
            lt )
   ) ) ) (unic ltext)
) )
 
(defun bnf (main ltext binds) (cons (cons main
   (gram ltext)) binds))
В результате синтаксические формулы можно приводить к нормализованному виду, пригодному для конструирования эффективного распознавателя с грамматикой текста. Организованные таким образом свернутые формы текстов могут играть роль словарей, грамматик языка, макетов программ и других древообразных структур данных, приспособленных к обработке рекурсивными функциями. обратные преобразования представляют не меньший интерес. Их можно использовать как генераторы тестов для синтаксических анализаторов или перечисления маршрутов в графе и других задач, решение которых сводится к обходу деревьев.
Построение развертки, т.е. системы текстов по их свернутому представлению, выполняется функциями names, words, lexs, d-lex, d-names, h-all, all-t, pred, sb-nm, chain, level1, lang.
Функции names, words и lexs задают алфавит и разбивают его на терминальные и нетерминальные символы на основе анализа их позиций в определении.
(defun names (vac) (mapcar 'car vac))
;; определяемые символы
 
(defun words (vac) (cond
;; используемые символы
   ((null vac) NIL)
   ((atom vac) (cons vac NIL ))
   (T (union (words(car vac))
   (words (cdr vac)))) ))
 
(defun lexs (vac) (set-difference (words vac)
   (names vac)))
;; неопределяемые лексемы
Функции d-lex и d-names формируют нечто вроде встроенной базы данных, хранящей определения символов для удобства дальнейшей работы.
(defun d-lex ( llex)
;; самоопределение терминалов
   (mapcar #'(lambda (x) (set x x) ) llex) )
 
(defun d-names ( llex)
;; определение нетерминалов
   (mapcar #'(lambda (x) (set (car x )(cdr x )) )
      llex) )
Функции h-all, all-t и pred раскрывают слияния общих фрагментов системы текстов.
(defun h-all (h lt)
;; подстановка голов
   (mapcar #'(lambda (a)
      (cond
         ((atom h) (cons h a))
         (T (append h a)) )
      ) lt) )
(defun all-t (lt tl)
;; подстановка хвостов
   (mapcar #'(lambda (d)
      (cond
         ((atom d) (cons d tl))
      (T(append d tl))
) ) lt) )
 
(defun pred (bnf tl)
;; присоединение предшественников
(level1 (mapcar #'(lambda (z) (chain z tl )) bnf)
))
Функции sb-nm, chain и LeveL1 строят развернутые, линейные тексты из частей, выполняя подстановку определений, сборку и выравнивание.
(defun sb-nm (elm tl)
;; подстановка определений имен
   (cond
      ((atom (eval elm)) (h-all (eval elm) tl))
      (T (chain (eval elm) tl))
) )
 
(defun chain (chl tl)
;; сборка цепочек
   (cond
      ((null chl) tl)
      ((atom chl) (sb-nm chl tl))
 
      ((atom (car chl))
         (sb-nm (car chl) (chain (cdr chl) tl) ))
 
      (T (pred (all-t (car chl) (cdr chl)) tl)) ))
(defun level1 (ll)
;; выравниваие
   (cond
      ((null ll)NIL)
      (T (append (car ll) (level1 (cdr ll)) )) ))
На основе приведенных вспомогательных функций общая схема развертки языка по заданному его определению (свертке) может быть выполнена функцией lang:
(defun lang ( frm )
;; вывод заданной системы текстов
(d-lex (lexs frm))
(d-names frm)
(pred (eval (caar frm)) '(())
) )
Вот и тесты к этой задаче, предложенные И.Н. Скопиным, справедливо предположившим, что для решения задач синтаксически управляемой обработки текстов хорошо подходит функциональный стиль программирования на Лиспе:
(lang (print (bnf 'vars
   '((m a s h a)(m a s h i n a)(s h i n a))
      '((n (i n a))) )))
 
(lang '((vars (m a ((s h a)(s h n))) (s h n) )
   (n (i n a)) ) )
Цель преобразования  синтаксических формул при определении анализаторов и компиляторов можно проиллюстрировать на схеме рекурсивного определения понятия «Идентификатор»:
Идентификатор ::= БУКВА
               | Идентификатор БУКВА
               | Идентификатор ЦИФРА
Удобное для эффективного синтаксического разбора определение имеет вид:
Идентификатор ::= БУКВА | БУКВА КонецИд
 
КонецИд ::= БУКВА КонецИд
         | ЦИФРА КонецИд
         | ПУСТО
Синтаксическая диаграмма анализатора
Этот пример показывает, что удобные для анализа формулы приведены к виду, когда каждую альтернативу можно выбрать по одному текущему символу. Система CLOS поддерживает ООП с выделением методов для одноэлементных классов, распознаваемых простым сравнением. Тем самым обеспечено удобное построение программ над структурами, подобными нормализованным формам.
Например, определение:
<а-гр> ::= А | А <а-гр>
 
<в-гр> ::= В | В <в-гр>
 
<слог> ::= <а-гр> <в-гр>
         | <в-гр> <а-гр>
         | <в-гр> <а-гр> <в-гр>
можно привести к виду, не требующему возвратов при анализе:
<а-гр>    ::= А <а-кон>
<а-кон>   ::= <пусто> | A <а-кон>
 
<в-гр>    ::= B <в-кон>
<в-кон>   ::= <пусто> | B <в-кон>
 
<слог>    ::= A <а-кон> B <в-кон>
            |B <в-кон> A <а-кон> <в-кон> 
Если программирование сводит алгоритм решения задачи к программе из определенной последовательности шагов, то конструирование строит программу решения задачи из решений типовых вспомогательных задач. Для задачи реализации языка программирования ключевой (но не единственной) типовой задачей является определение реализуемого языка. Ее решение открывает возможности автоматизированного конструирования анализаторов и компиляторов. Автоматизацию конструирования системы программирования обеспечивают методы синтаксического управления обработкой информации и методы смешанных/частичных вычислений, позволяющие выводить определение компилятора программ из определения интерпретатора.

Все это хорошо изученные задачи, имеющие надежные решения, знания которых достаточно для создания своих языков программирования и проведения экспериментов с программами на своих языках. Существует ряд программных инструментов, поддерживающих автоматизацию процесса создания и реализации языков программирования и более общих информационных систем обработки формализованной информации, например YACC, LEX, Bison, Flex, основные идеи применения которых достаточно близки изложенным выше методам обработки формул и текстов. Очередной этап в этом направлении открывают технологии типа .Net и DotGNU.
 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика