globalf5-240972240972 (850810), страница 32
Текст из файла (страница 32)
ГородняяОсновы функционального программирования(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) ))221Л.В. ГородняяОсновы функционального программирования(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)) ) )Цель преобразованиясинтаксических формул при определениианализаторов и компиляторов можно проиллюстрировать на схемерекурсивного определения понятия "Идентификатор":Идентификатор ::= БУКВА| Идентификатор БУКВА| Идентификатор ЦИФРАУдобное для эффективного синтаксического разбора определение имеет222Л.В.
ГородняяОсновы функционального программированиявид:Идентификатор ::= БУКВА | БУКВА КонецИдКонецИд ::= БУКВА КонецИд| ЦИФРА КонецИд| ПУСТОСинтаксическая диаграмма анализатораРис. 13.1.Этот пример показывает, что удобные для анализа формулы приведенык виду, когда каждую альтернативу можно выбрать по одному текущемусимволу.
Система CLOS поддерживает ООП с выделением методов дляодноэлементных классов, распознаваемых простым сравнением. Темсамым обеспечено удобное построение программ над структурами,подобными нормализованным формам.Например, определение:<а-гр> ::= А | А <а-гр><в-гр> ::= В | В <в-гр><слог> ::= <а-гр> <в-гр>| <в-гр> <а-гр>| <в-гр> <а-гр> <в-гр>можно привести к виду, не требующему возвратов при анализе:<а-гр> ::= А <а-кон><а-кон> ::= <пусто> | A <а-кон>223Л.В. ГородняяОсновы функционального программирования<в-гр> ::= B <в-кон><в-кон> ::= <пусто> | B <в-кон><слог> ::= A <а-кон> B <в-кон>|B <в-кон> A <а-кон> <в-кон>Если программирование сводит алгоритм решения задачи к программеиз определенной последовательности шагов, то конструированиестроит программу решения задачи из решений типовыхвспомогательныхзадач.Длязадачиреализацииязыкапрограммирования ключевой (но не единственной) типовой задачейявляется определение реализуемого языка.
Ее решение открываетвозможности автоматизированного конструирования анализаторов икомпиляторов.Автоматизациюконструированиясистемыпрограммирования обеспечивают методы синтаксического управленияобработкой информации и методы смешанных/частичных вычислений,позволяющие выводить определение компилятора программ изопределения интерпретатора.Все это хорошо изученные задачи, имеющие надежные решения, знаниякоторых достаточно для создания своих языков программирования ипроведения экспериментов с программами на своих языках. Существуетряд программных инструментов, поддерживающих автоматизациюпроцесса создания и реализации языков программирования и болееобщих информационных систем обработки формализованнойинформации, например YACC, LEX, Bison, Flex, основные идеиприменения которых достаточно близки изложенным выше методамобработки формул и текстов.
Очередной этап в этом направленииоткрывают технологии типа .Net и DotGNU.224Л.В. ГородняяОсновы функционального программированияМакеты программ и тестыТехникафункциональногопрограммированияиллюстрируетсяпримерами поддержки полного жизненного цикла программ с помощьюбыстрого прототипирования и спецификации программ. В этом планесущественна возможность введения частично определенных функций,варьируемых и уточняемых определений, а также специализацияинтерпретатора программ с целью учета уровня достоверностирешений.
Рассматриваются примеры построения прототипов системы,опережающего детальную разработку алгоритмов и отладку программ.Основой является процесс уточнения информации о решаемой задаче,продемонстрированный на отдельных примерах и схемах спривлечением частичных функций на доступных типах данных сдоведением до полных функций, приспособленных к обработкепроизвольных данных.Построение теорий при разработке программПринимая аксиоматическую теорию множеств за образец грамотноразработанной теории, попробуем проанализировать доказательныеположения,полезныеприобоснованииивыполнениипрограммистских проектов.Многие построения в теории множеств выполнены над кумулятивнойиерархией множеств, инициированной некоторым множествомобъектов не множественной природы и пустого множествапосредством операции объединения множеств. Кроме того, надмножествами определены операции пересечения, дополнения,равенства, вхождения и включения, удовлетворяющие небольшомунабору аксиом разной сложности.Аналогично, структуры, такие как S-выражения, выстроены надатомами, не структурируемыми на компоненты, и пустого списка NIL,посредством операции CONS — консолидации.
Над S-выражениямиопределены операции, позволяющие разбирать структуры накомпоненты, сравнивать и анализировать структуры, отличать атомы отструктур и пустой список от других данных. Элементарные операцииподчинены аксиомам, обеспечивающим обратимость информационной225Л.В.
ГородняяОсновы функционального программированияобработки, и техника программирования на уровне строгих функцийподдерживает прозрачность определений и скорость отладки.Рассматривая программы и программные системы как формыпредставления знаний, трудно удержаться от попытки исследованиядинамики представления знаний на основе аналогии с развитиемпрограмм и программных систем.Движущими силами этого развития являются: необходимость разныхвидов эффективной деятельности, потребность в уточнениипредставления знаний и установление новой информации, котораяраньше не попадала в поле зрения или наблюдатель не был готов еепонять. Динамика представления знаний сводится к переходу от одногопредставления к другому.Успешность эффективной деятельности ограничена "пропускнойспособностью" поля зрения.
Это ограничение систематическипреодолеваетсяпосредствомобобщения,приводящегокпредставлениям более высокого порядка — представлениям болеемощным, более организованным, например к процедурам, функциям,фреймам, шаблонам, макросам. Последовательность шагов обобщенияможно называть индуктивным развитием представления знаний.
Вметодике программирования индуктивное развитие соответствуетвосходящим методам, "снизу вверх". Как правило, индуктивное развитиеимеет некоторые пределы. Такие пределы при возрастании мерыинформативности используемых средств рассматриваются Д.Скоттом[5]. Интересен случай, когда пределом является теория, достаточная дляпорождения всей достоверной информации, установленной на данныймомент времени. При разработке программ роль такого предела играетсистема программирования.В результате индуктивного развития представления знаний наблюдаетсятенденция к возрастанию доли средств декларативного характера (такихкак описания, отношения, формирователи, типы, фреймы,семантические сети, иерархии понятий, аксиоматические системы) всравнении с долей средств процедурного характера (таких как действия,операции, операторы, процедуры, интерпретаторы, задания). Этатенденция обуславливает рост эффективности применения дедуктивныхметодов и может рассматриваться как стимул к переходу от226Л.В.
ГородняяОсновы функционального программированияиндуктивного развития к дедуктивному. Дедуктивный выводосуществляет переход от потенциальных знаний к актуальным.Традиционно для этих целей в системах искусственного интеллектаиспользуется метод резолюций, системы продукций и другие средства.Чередование стадий индуктивного и дедуктивного развития можнорассматривать как обоснование выбора метода программирования взависимости от уровня развития знаний о решаемой задаче (зрелость,уровень изученности ).Применение развиваемых таким образом представлений можетпотребовать возврата к менее структурированным средствам(например, для упрощения обратной связи с областью, породившейрешаемые задачи или для более тонкой детализации реализационныхрешений).
Такой переход является конкретизацией представлениязнаний. В методике программирования конкретизация соответствуетнисходящим методам "сверху вниз".Независимо осуществляемое развитие приводит к задаче установленияэквивалентности между различными системами представления знаний.Прирешенииэтойзадачивозникаютпредпосылкидляцеленаправленного дедуктивного развития, что приводит квыравниванию потенциала систем (вводятся недостающие понятия,выполняются аналогичные построения, реализуются подобныеинструменты).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
