globalf5-240972240972 (850810), страница 31
Текст из файла (страница 31)
ГородняяОсновы функционального программирования(funcall (manyfun '(CAR CDR length))'(1 f (2 T)(3 D e)) ) ;= (1 (f (2 T)(3 D e)) 4)Таким образом можно как бы "просачивать" определения функций надпростыми данными, распределять их по структурам данных и темсамым распространять простые функции на сложные данные подобноматричной арифметике. Похожие построения предлагаются Бэкусом вего программной статье о функциональном стиле программирования[20] и в языке APL, ориентированном на обработку матриц.Существует ряд языков функционального программирования,требующих или допускающих спецификацию объектов, что, кромедисциплины программирования, дает средства для корректной работы спакетами, сопряжения с модулями на других языках, оптимизирующихпреобразований, распараллеливания и верификации программ (Sisal,ML и др.).Конструирование распознавателейРезультативность функций высших порядков Хендерсон показывает намодельной задаче построения распознавателя контекстно-свободногоязыка [3].В качестве примера такого языка рассмотрен синтаксис понятия "слог",образованный по правилам из гласных и согласных букв, что можнопредставить грамматикой вида:<а-гр> ::= А | А <а-гр><в-гр> ::= В | В <в-гр><слог> ::= <а-гр> <в-гр>| <в-гр> <а-гр>| <в-гр> <а-гр> <в-гр>В этой грамматике " А " и " В " — терминальные символы, "слог", "а-гр"и "в-гр" — нетерминальные символы (метапонятия), "слог" — основноепонятие.
Необходимо быстро построить предикат is-syllable,выделяющий списки, представляющие правильно построенные слоги в213Л.В. ГородняяОсновы функционального программированиясоответствии с приведенными правилами.Такое построение можно выполнить с помощью ряда функций высокогопорядка, конструирующих распознаватели для альтернатив и цепочек изпонятий, к которым сводится определение грамматики языка.Предполагается, что каждому правилу будет соответствовать свойраспознающий предикат.
Для простоты ограничимся случаями из паральтернатив и двухзвенных цепочек.Пусть тексты этого языка представляются списками из однобуквенныхатомов 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))->Bool214Л.В. ГородняяОсновы функционального программированияМожно использовать эквивалент:(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))); сдвиг границы разбиения вправо)))215Л.В.
ГородняяОсновы функционального программированияИз данного распознавателя 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 (carx)'A)(is-a-tl (cdr x )) )))); хвост цепочки из AНо использование конструкторов is-alt и is-chain, показанное напримере распознавателя is-b-gr, позволяет построить определение,синтаксически подобное правилу грамматики:(DEFUN is-b-gr (x ) (funcall (is-alt #'is-bis-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))216Л.В.
ГородняяОсновы функционального программирования(is-syllable '(b a))(is-syllable '(b a b ))(is-syllable '(b b b b a a b b ))Сопоставляя правила и полученное определение распознавателя,можно убедиться, что собственно конструирование распознавателяосуществляется и модернизируется сравнительно быстро: достаточносвести распознаваемый язык к композиции альтернатив и цепочек.Таблица 13.1.
Сопоставление грамматики слога и распознавателя issyllableГрамматикаРаспознаватель<слог>::=(defun is-syllable (x ) (funcall<в-гр> <а(is-alt (is-chain #'is-b-gr #'is-aгр>gr)<а-гр> <в(is-alt (is-chain #'is-a-gr #'is-bгр>gr)<в-гр>(is-chain #'is-b-gr<а-гр> <в-гр>(is-chain #'is-a-gr #'is-b-gr))) ) x ))Результат сопоставления показывает, что достигнуто синтаксическоеподобие определения грамматики и построенного распознавателя. Этозначит, что определение можно автоматически отобразить в такойраспознаватель .
Отображение — функция высокого порядка,вырабатывающая в качестве результата распознаватель языка,порождаемого исходной грамматикой.Преобразование определенийКонечно,построенноевышеопределениенеотличаетсяэффективностью. Обычно синтаксические формулы приводят кнормализованной форме, гарантирующей полезные свойствараспознавателей и удобство их построения.
Выбор нормализованнойформы и процесс нормализации обосновывается доказательнымипостроениями, на практике воспринимаемыми как эквивалентные217Л.В. ГородняяОсновы функционального программированияпреобразования . Преобразования формул — еще один интересныйкласс задач символьной обработки. Для демонстрации рассмотриммодель реализации функций свертки текстов. При подходящем выбореобозначений такие функции можно применять для преобразованиясинтаксических формул с целью приведения к нормализованной форме .Пусть свертки системы текстов представлены в стиле самоописанияподобно формам Бекуса-Наура списком вида:( (Тексты (Имя Вариант ...)...); первое имя — обозначение системы текстов; за ним следуют варианты поименованных текстов(Вариант Элемент ...); Вариант представляет собой; последовательность Элементов(Элемент Имя Лексема (Варианты)); Элемент — это или Имя, или Лексема,; или Варианты в скобках)Для системы текстов "((м а ш и н а)(м а ш а)(ш и н а))" можно датьсвертку вида:( (пример (ма ((ш н)(ш а))( шн ) )(н ина))Построение свертки системы текстов выполняется функциями unic,ass-all, swin, gram, bnf:(DEFUN unic (vac) (remove-duplicates (mapcar 'CAR vac) ));; список уникальных начал(DEFUN ass-all (Key Vac);; список всех вариантов продолжения;; что может идти за ключом(COND((Null Vac) NIL)218Л.В.
ГородняяОсновы функционального программирования((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, d219Л.В. ГородняяОсновы функционального программирования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);; подстановка голов220Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
