globalf5-240972240972 (850810), страница 14
Текст из файла (страница 14)
ГородняяОсновы функционального программирования;;=== Лексикон****) - проверка корректности ==;; Предполагается, что из теста уже;; отфильтрованы строки,;; т.к. они не влияют на логику анализа корректности(DEFUN NAMES (VAC) (MAPCAR 'CAR VAC));; определяемые имена - список левых частей(DEFUN WORDS (VAC) (COND;; используемые имена - список правых частей((NULL VAC) NIL)(T (UNION (CDAR VAC) (WORDS (CDR VAC))))))(DEFUN UNDEF (VAC) (SET-DIFFERENCE (WORDS VAC)(NAMES VAC)));; неопределенные имена - список висячих ссылок(DEFUN CIRCLE (V);; проверка термина на явный цикл(COND ((NULL (CDR V)) NIL)((MEMBER (CAR V) (CDR V)) (CAR V))(T NIL)))(DEFUN CIRC-V (VAC) (MAPCAR 'CIRCLE VAC));; список явных циклов с NIL-ами на нециклах(DEFUN MASKA (ARG XXX) (COND (XXX NIL) (T ARG)));; ВЫБОР, ЕСЛИ NIL(DEFUN DEL-CIR (AL XL) (DELETE NIL(MAPCAR 'MASKA AL XL)));; стирание непомеченных определений, т.е.
циклов(DEFUN SKOBKI (LL) (COND((NULL LL)NIL)((NULL (CAR LL)) (SKOBKI (CDR LL)) )((ATOM (CAR LL))(CONS(CAR LL)(SKOBKI(CDR LL))) )(T (UNION (CAR LL) (SKOBKI (CDR LL)) ))87Л.В. ГородняяОсновы функционального программирования));; раскрыть скобки на один уровень(DEFUN ONESTP (VC)(SETQ VAC VC);; однократная постановка всего словаря(MAPCAR '(LAMBDA (X) (CONS (CAR X)(SKOBKI (SUBLIS VAC (CDR X))))) VC ))(DEFUN CLEAN-S (LINE XL)(COND ((NULL XL) LINE)(T (CLEAN-S (DELETE (CAR XL) LINE)(CDR XL) ))))(DEFUN CLEAN-U (VC XL) (SETQ WL XL);; стирание заданного списка слов => висячих ссылок(MAPCAR '(LAMBDA (XX) (SETQ X XX)(CONS (CAR X)(CLEAN-S (CDR X) WL))) VC ))(DEFUN CVR (VAC)(DELETE NIL (CVR-D(DEL-CIR VAC (CIRC-V VAC))(DELETE NIL(UNION (CIRC-V VAC) NIL)))));; список всех циклов полного словаря - без;; висячих ссылок(DEFUN CVR-D (VC CCL)(PROG (VAC CL CV DCV CLEANV)(SETQ VAC (CLEAN-U VC CCL))(SETQ CL CCL);; пополнение списка циклов со второго шагаLAB (COND ((WORDS VAC)(SETQ CV (CIRC-V VAC))(SETQ DCV (DELETE NIL CV))88Л.В.
ГородняяОсновы функционального программирования(SETQ CLEANV (CLEAN-U (DEL-CIR VAC CV) DCV))(SETQ VAC (ONESTP CLEANV))(SETQ CL (APPEND DCV CL))(GO LAB)))(RETURN CL)))(DEFUN VAC-OK (VAC) (PROG (VC UL CL);; ПРОВЕРКА СЛОВАРЯ НА КОРРЕКТНОСТЬ(SETQ VC VAC)(SETQ UL (UNDEF VC))(SETQ CL (CVR (CLEAN-U VAC UL)))(COND ((EQ UL CL) (RETURN(PRINT 'OK)) ); = лишь если пусты <> корректность словаря( CL (PRINT (LIST 'CIRCLES CL))) )(COND (UL (RETURN (PRINT (LIST 'UNDEFINED UL))) )(T (RETURN (LIST 'CIRCLE CL))) )))*) Символ ";" - начало комментария.**) На Lisp 1.5 это определение выглядит изящнее, не требуетвстроенной функции FUNCALL, при отладке примеров на Clisp-е [7]:(DEFUN map-el (fn xl)(COND(xl (CONS (fn (CAR xl) ); применяем первый аргумент как функцию; к первому элементу второго аргумента(map-el fn (CDR xl) )))))***) Эта задача была предложена участникам Открытой Всесибирскойстуденческой олимпиады в 2000 году и оказалась в числе никем нерешенных.
Многих смутило отсутствие численных ограничений надопустимые данные. При решении задач на Паскале и Си такие89Л.В. ГородняяОсновы функционального программированияограничения обычно подсказывают выбор структур данных, поэтомуотсутствие ограничений было воспринято как риск. Немногочисленныепопытки решить задачу привели к отбраковке на минимальных тестах,вызванной тем, что программы не допускали пустой словарь илисловарь, выглядящий как перечень терминов без определений.(Впрочем, возможно, это ошибка разработчика тестов. Видимо,первыми должны располагаться тесты на наиболее типичные,естественные случаи.)****) Решение этой задачи может быть сведено к задаче <Проверкаацикличности графа>.1)Здесь и далее, следуя CLISP, (COND NIL) = NIL, т.е.
допускаетсяотсутствие предиката со значение "истина".90Л.В. ГородняяОсновы функционального программированияИмена, определения и контекстыРассматриваются основные методы расширения функциональныхсистем с помощью иерархии разнородных контекстов определений.Изучаются приемы достижения удобочитаемости функциональныхпрограмм при определении сложных функций и анализируютсяособенности типовых схем связывания имен переменных с ихзначениями, принятых в системах программирования. Знакомство сметодом неподвижных точек в системах рекурсивных определенийлогически завершает схему выбора решений по взаимодействию имен сопределениями.Интерпретирующаясистема.уточнение интерпретацииРеализационноеЭта глава предназначена для реализационного уточнения ужеизвестных теоретических рассуждений.
Ряд уточнений показан напримере, представляющем программу, которая определяет три функцииUNION, INTERSECTION и MEMBER, а затем применяет эти функции кнескольким тестам [1]. На этом примере будут рассмотрены средства иметоды, обеспечивающие удобочитаемость функциональных программи удобство их развития при отладке. Как правило, удобство достигаетсявключением в систему дополнительных функций для решения проблем,принципиальное решение которых уже обеспечено на уровне теории.Функции UNION и INTERSECTION применяют к множествам, каждоемножество представлено в виде списка атомов. Заметим, что всефункции рекурсивны, а UNION и INTERSECTION используютMEMBER.
Схематично работу этих функций можно выразитьследующим образом:member = lambda [a;x][ null[x] >> Nil ][ eq[a;car[x]] >> T ][ T >> member[a;cdr[x]] ]union = lambda[x;y][ null[x] >> y ]91Л.В. ГородняяОсновы функционального программирования[ member[car[x];y] >> union[cdr[x];y] ][ T >> cons[car[x];union[cdr[x];y]] ]intersection = lambda [x;y][ null[x] >> NIL ][ member[car[x];y] >>cons[car[x];intersection[cdr[x];y]] ][ T >> intersection[cdr[x];y] ]Определяя эти функции на Лиспе, мы используем дополнительнуюпсевдо-функцию DEFUN, объединяющую эффекты LAMBDA и LABEL.Программа выглядит так:(DEFUN MEMBER (A X)(COND((NULL X) Nil)((EQ A (CAR X)) T)(T (MEMBER A (CDR X)) )))(DEFUN UNION (X Y)(COND((NULL X) Y)((MEMBER (CAR X) Y) (UNION (CDR X) Y) )(T (CONS (CAR X) (UNION (CDR X) Y))) )) )) )(DEFUN INTERSECTION (X Y)(COND((NULL X) NIL)((MEMBER (CAR X) Y)(CONS (CAR X) (INTERSECTION (CDR X) Y)) )(T (INTERSECTION (CDR X) Y))) )(INTERSECTION '(A1 A2 A3) '(A1 A3 A5))(UNION '(X Y Z) '(U V W X))Эта программа предлагает вычислить пять различных форм.92Л.В.
ГородняяОсновы функционального программированияПервые три формы сводятся к применению псевдо-функции DEFUN.Псевдо-функция — это функция, которая выполняется ради еевоздействия на систему, тогда как обычная функция — ради еезначения. DEFUN заставляет функции стать определенными идопустимыми в системе равноправно со встроенными функциями. Еезначение — имя определяемой функции, в данном случае — MEMBER,UNION, INTERSECTION. Более точно можно сказать, что полнаяобласть значения псевдо-функции DEFUN включает в себя некоторыедоступные ей части системы, обеспечивающие хранение информации офункциональных объектах, а формальное ее значение — атом,символизирующий определение функции.Значение четвертой формы — (A1 A3). Значение пятой формы — (Y Z CB D X).
Анализ пути, по которому выполняется рекурсия, показывает,почему элементы множества появляются именно в таком порядке.В этом примере продемонстрировано несколько элементарных правилнаписания функциональных программ, сложившихся при реализацииинтерпретатора Лисп 1.5 в дополнение к идеализированным правилам,сформулированным в строгой теории Лиспа. (С точностью до разницымежду EVALQUOTE — EVAL.)1. Программа состоит из последовательности вычисляемых форм.Если форма список, то ее первый элемент интерпретируется какфункция.
Остальные элементы списка — аргументы для этойфункции. Они вычисляются с помощью EVAL, а функцияприменяется к ним с помощью APPLY, и полученное значениевыводится как результат программы.2. Особого формата для записи программ не существует. Границыстрокигнорируются.Форматпрограммы,включаяидентификацию, выбран просто для удобства чтения.3. Любое число пробелов и концов строк можно разместить в любойточке программы, но не внутри атома.4.
Не используются (QUOTE T), (QUOTE NIL). Вместо нихприменяется T, NIL, что влечет за собой соответствующееизменение определения EVAL.5. Атомы должны начинаться с букв, чтобы их можно было легкоотличать от чисел.93Л.В. ГородняяОсновы функционального программирования6. Может использоваться точечная нотация. Любое число пробеловперед или после точки, свыше одного, будет игнорироваться (одинпробел нужен обязательно при соседстве с атомом).7. Точечные пары могут появляться как элементы списка, и спискимогут быть элементами точечных пар.((A .
B) X (C . (E F D)))— допустимое S-выражение. Оно может быть записано как((A . B) . ( X . ((C . (E . ( F . (D . Nil)))) . Nil)))или((A . B) X (C E F D))8. Форма типа (A B C . D) есть сокращение для (A . ( B .( C . D) )). Любая другая расстановка точек на одном уровнеесть ошибка, например (A. B C).9.
Набор основных функций предоставляется системой. Другиефункции могут быть введены программистом. Порядок введенияфункций не имеет значения. Любая функция можетиспользоваться в определении другой функции.Вывод S-выражений на печать и в файлы выполняет псевдофункция PRINT, чтение данных обеспечивает псевдо-функцияREAD.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
