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

Конструирование распознавателей

Результативность функций высших порядков Хендерсон показывает на модельной задаче построения распознавателя   контекстно-свободного языка .

В качестве примера такого языка рассмотрен синтаксис понятия "слог", образованный по правилам из гласных и согласных букв, что можно представить грамматикой вида:

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

В этой грамматике " А " и " В " — терминальные символы, "слог", "а-гр" и "в-гр" — нетерминальные символы (метапонятия), "слог" — основное понятие. Необходимо быстро построить предикат 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 ))

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

<в-гр>
      <а-гр> <в-гр>

(is-chain #'is-b-gr 
    (is-chain #'is-a-gr #'is-b-gr))

Результат сопоставления показывает, что достигнуто синтаксическое подобие определения грамматики и построенного распознавателя. Это значит, что определение можно автоматически отобразить в такой распознаватель . Отображение — функция высокого порядка, вырабатывающая в качестве результата распознаватель языка, порождаемого исходной грамматикой.

Преобразование определений

Конечно, построенное выше определение не отличается эффективностью. Обычно синтаксические формулы приводят к нормализованной форме, гарантирующей полезные свойства распознавателей и удобство их построения. Выбор нормализованной формы и процесс нормализации обосновывается доказательными построениями, на практике воспринимаемыми как эквивалентные преобразования . Преобразования формул — еще один интересный класс задач символьной обработки. Для демонстрации рассмотрим модель реализации функций свертки текстов. При подходящем выборе обозначений такие функции можно применять для преобразования синтаксических формул с целью приведения к нормализованной форме .

Пусть свертки   системы текстов представлены в стиле самоописания подобно формам Бекуса-Наура списком вида:

( (Тексты (Имя Вариант ...)...) 
      ; первое имя — обозначение системы текстов
      ; за ним следуют варианты поименованных текстов
   (Вариант Элемент ...) 
      ; Вариант представляет собой 
      ; последовательность Элементов
   (Элемент Имя Лексема (Варианты)) 
      ; Элемент — это или Имя, или Лексема, 
      ; или Варианты в скобках
)

Для системы текстов "((м а ш и н а)(м а ш а)(ш и н а))" можно дать свертку вида:

( (пример (ма ((ш н)
                      (ш а))
                     ( ш н ) )
   (н ина) 
)

Построение свертки   системы текстов выполняется функциями 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.