globalf5-240972240972 (850810), страница 10
Текст из файла (страница 10)
ГородняяОсновы функционального программирования(DEFUN sublis (al y)(COND((ATOM y) (sub2 al y))((QUOTE T)(CONS(sublis al (CAR y))(sublis al (CDR y))) ) ))(sublis '((x . Шекспир)(y . (Ромео и Джульетта)) )'(x написал трагедию y) ); = (Шекспир написал трагедию (Ромео и Джульетта))Пример 3.1.INSERT — вставка z перед вхождением ключа x в список al .(DEFUN insert (al x z)(COND((null al) NIL)((equal (CAR al) x) (CONS z al) )((QUOTE T) (CONS (CAR al)(insert (CDR al) x z) ))) )(insert '(a b c) 'b 's) = (a s b c)ASSIGN — модель присваивания переменным, хранящим значения вассоциативном списке .
Замена связанного с данной переменной впервой паре значения на новое заданное значение. Если пары не быловообще, то новую пару из переменной и ее значения помещаем в конеца-списка, чтобы она могла работать как глобальная.(DEFUN assign (x v al)(COND((Null al) (CONS(CONS x v) NIL ) )((equal x (CAAR al)) (CONS(CONS x v)(CDR al)) )((QUOTE T) (CONS (CAR al)(assign x v (CDR al)) )))57Л.В. ГородняяОсновы функционального программирования)(assign 'a 111 '((a . 1)(b . 2)(a .
3))); = ((a . 111)(b . 2)(a . 3))(assign 'a 111 '((c . 1)(b . 2)(a . 3))); = ((c . 1)(b . 2)(a . 111))(assign 'a 111 '((c . 1)(d . 3))); = ((c . 1)(d . 3) (a . 111))REVERSE — обращение списка — два варианта, второйнакапливающим параметром и вспомогательной функцией :с(DEFUN reverse (m)(COND ((null m) NIL)(T (append(reverse(CDR m))(list(CAR m)) ))) )(DEFUN reverse (m) (rev m NIL))(DEFUN rev (m n)(COND ((null m)N)(T (rev(CDR m)(CONS (CAR m) n))) ))Определение универсальной функцииУниверсальная функция EVAL, которую предстоит определить, должнаудовлетворять следующему условию: если представленная аргументомформа сводится к вычислению функции, имеющей значение на спискеаргументов из этой же формы, то данное значение и являетсярезультатом функции eval.(EVAL '(fn arg1 ... argK)); = результат применения fn к аргументам arg1, ..., argK.Явное определение универсальной58функциипозволяетдостичьЛ.В.
ГородняяОсновы функционального программированиячеткости механизмов обработки Лисп-программ.(EVAL '((LAMBDA (x y) (CONS (CAR x) y))'(A B) '(C D) )); = (A C D)Вводим две важные функции EVAL-А и APPLY для обработки форм иобращения к функциям, соответственно. Пусть каждая из этих функцийиспользует ассоциативный список для хранения связанных имен —значений переменных и определений функций.Сначала этот список пуст.Вернемся к синтаксической сводке вычислимых форм.форма ::= переменная| (QUOTE S-выражение)| (COND (форма форма) ...
(форма форма))| (функция аргумент ...)аргумент ::= формапеременная ::= идентификаторфункция ::= название| (LAMBDA список_переменных форма)| (LABEL название функция)список_переменных ::= (переменная ... )название ::= идентификаторидентификатор ::= атомВетвям этой сводки будут соответствовать ветви универсальнойфункции:Кроме того работа с идентификаторами использует ассоциативныйсписок для хранения связанных имен - значений переменных иопределений функций.59Л.В. ГородняяОсновы функционального программирования(DEFUN EVAL (e) (eval-a e '((NIL .
NIL)(T . T))))Вспомогательная функция APPLY понадобилась для выделенияобращений к функциям. Вспомогательная функция EVAL-Aпонадобилась, чтобы для EVAL завести накапливающий параметр —ассоциативный список , в котором будут храниться связи именпеременных с их значениями и названий функций с их определениями.Здесь его значение ((NIL . NIL)(T . T)) обеспечивает, чтоатомы NIL и T обозначают сами себя.(DEFUN eval-a(e a)(COND((ATOM e) (CDR(assoc e a)) )((EQ (CAR e) 'QUOTE) (cadr e))((EQ (CAR e) 'COND) (evcon (CDR e) a))( T (apply (CAR e) (evlis (CDR e) a) a) )) )(defun apply (fn x a)(COND((ATOM fn)(COND((EQ fn 'CAR) (caar x))((EQ fn 'CDR) (cdar x))((EQ fn 'CONS) (CONS (CAR x)(cadr x)) )((EQ fn 'ATOM) (ATOM (CAR x)) )((EQ fn 'EQ) (EQ (CAR x)(cadr x)) )(T (apply (eval-a fn a) x a))) )((EQ (CAR fn)'LAMBDA) (eval-a (caddr fn)(pairlis (cadr fn) x a) ))((EQ (CAR fn) 'LABEL) (apply (caddr fn) x(CONS(CONS(cadr fn) (caddr fn)) a)) )))ASSOC и PAIRLIS уже определены ранее.60Л.В.
ГородняяОсновы функционального программирования(DEFUN evcon (c a)(COND((eval-a (caar c) a) (eval-a (cadar c) a) )( T (evcon (CDR c) a) )) )(Не допускается отсутствие истинного предиката, т.е. пустого C.)(DEFUN evlis (m a)(COND((null m) NIL )( T (CONS(eval-a (CAR m) a)(evlis(CDR m) a)) ) ) )При(DEFUN EVAL (e) (eval-a e ObList ))определения функций могут накапливаться в системной переменнойObList, то есть работать как глобальные определения.
ObListобязательно должна содержать глобальное определение встроеннойконстанты "NIL", можно и сразу разместить в ней константу "T",выполняющую роль значения "истина".Поясним ряд пунктов этих определений.Аргумент EVAL — форма. Если она — атом, то этот атом может бытьтолько именем переменной, а значение переменной должно уженаходиться в ассоциативном списке.Если CAR от формы — QUOTE, то она представляет собой константу,значение которой выделяется как CADR от нее самой.Если CAR от формы — COND, то форма — условное выражение.Вводим вспомогательную функцию EVCON (определение ее будет данониже),котораяобеспечиваетвычислениепредикатов(пропозициональных термов) по порядку и выбор формы,соответствующей первому предикату, принимающему значение"истина". Эта форма передается EVAL для дальнейших вычислений.61Л.В.
ГородняяОсновы функционального программированияВсе остальные случаи рассматриваются как список из функции саргументами, который обрабатывается функцией APPLY.Вспомогательная функция EVLIS обеспечивает вычисление аргументов,затем представление функции и список вычисленных значенийаргументов передаются функции APPLY.Первый аргумент APPLY — функция. Если она — атом, то существуетдве возможности. Атом может представлять одну из элементарныхфункций (CAR CDR CONS ATOM EQ). В таком случаесоответствующая ветвь вычисляет значение этой функции на заданныхаргументах.
В противном случае, этот атом — название ранее заданногоопределения функции. Определение можно найти в ассоциативномсписке , подобно вычислению переменной.Если функция начинается с LAMBDA, то ее аргументы попарносоединяются со связанными переменными, а тело определения (формаиз лямбда-выражения) передается как аргумент функции EVAL-A длядальнейшей обработки.Если функция начинается с LABEL, то ее название и определениесоединяются в пару, и полученная пара размещается в ассоциативномсписке, чтобы имя функции стало определенным при дальнейшихвычислениях.
Они произойдут как рекурсивный вызов APPLY, котораявместо имени функции теперь работает с ее определением при болееполном ассоциативном списке — в нем уже размещено определениеимени функции. Поскольку определение размещается "наверху" стека,оно становится доступным для всех последующих использований, тоесть работает как локальный объект.
Глобальные объекты, которыеобеспечиваются псевдо-функцией DEFUN, устроены немного иначе,что будет рассмотрено в лекциях 5 и 6.Определение универсальной функции является важным шагом,показывающимодновременноимеханизмыреализациифункциональныхязыков,итехникуфункциональногопрограммирования на любом языке. Пока еще не описаны многиедругие особенности языка Лисп и функционального программирования,которые будут рассмотрены позднее.
Но все они будут увязаны в единуюкартину, основа которой согласуется с этим определением.62Л.В. ГородняяОсновы функционального программирования1. В строгой теории аппликативного программирования всефункции следует определять всякий раз, когда они используются.На практике это неудобно. Реальные системы имеют большойзапас встроенных функций (более тысячи в Clisp-е), известныхязыку, и возможность присоединения такого количества новыхфункций, какое понадобится. Во многих реализациях Лиспа всеэлементарные функции вырабатывают результат и на списках, ина атомах, но его смысл зависит от системных решений, чтоможет создавать трудности при переносе программ на другиесистемы.
Базисный предикат EQ всегда имеет значение, но смыслего на неатомарных аргументах будет более ясен после знакомствасо структурами данных, используемыми для представлениясписков в машине.2. В чистом языке Лисп базисные функции CAR и CDR неопределены для атомарных аргументов. Такие функции, имеющиеосмысленный результат не на всех значениях естественнойобласти определения, называют частичными.
Отладка иприменение частичных функций требует большего контроля, чемработа с тотальными, всюду определенными функциями. Вомногих реализациях функциональных языков программированиявсе функции всегда вырабатывают значение. При необходимостикаждый существенный класс объектов пополняется значениемкласса ERROR, символизирующим исключительные ситуации.3. Для функциональных языков характерно большое разнообразиеусловных форм, конструкций выбора, ветвлений и циклов,практически без ограничений на их комбинирование. ФормаCOND выбрана для начального знакомства как наиболее общая. Заредким исключением в Лиспе нет необходимости писать вусловных выражениях (QUOTE T) или (QUOTE NIL).
Вместоних используются встроенные константы T и NIL,соответственно.4. В реальных системах функционального программированияобычно поддерживается работа с целыми, дробными ивещественными числами в предельно широком диапазоне, а такжеработа с битовыми и текстовыми строками. Такие данные, как иатомы, являются минимальными объектами при обработкеинформации, но отличаются от атомов тем, что их смысл заданнепосредственно их собственным представлением. Их понимание63Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
