Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп

Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп, страница 18

Описание файла

PDF-файл из архива "Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп", который расположен в категории "книги и методические указания". Всё это находится в предмете "искусственный интеллект" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 18 страницы из PDF

Заметим, то макросредства невстроены в MuLisp, однако возможность их определения и использованияпоявляется после загрузки файла common.lsp.Определение макроса похоже на определение функции:(defmacro М (x1 … xk) e1 … en) , n ≥ 0где М – имя макроса,x1 … xk – его параметры, k ≥ 0 ,а e1 … en – тело.95Однако вычисление макровызова (М p1 … pk) с фактическимипараметрами p1 … pk отлично от вычисления функционального вызова.Опишем этапы вычисления макровызова для случая n=1, когда в телемакроса стоит одно выражение:(defmacro М (x1 … xk) e)1) Связывание: формальные параметры макроса x1 … xk попарносвязываются с фактическими параметрами макровызова p1 … pk,т.е.

x1 = p1, ... , xk = pk.2) Расширение (раскрытие): вычисляется форма e (тело макроса), приэтом всюду в качестве значений форм x1 … xk берутся связанные сними значения p1 … pk . В результате этого вычисления строитсяновая форма (вычислимое лисповское выражение), и связиформальных параметров x1 … xk с фактическими разрываются.3) Вычисление: построенная на предыдущем этапе форма вычисляется,и результат её вычисления становится значением макровызова.Отличие вызова макроса от вызова обычной функции состоит,во-первых, в том, что фактические параметры макроса не вычисляются.Во-вторых, вычисление тела макроса происходит как бы дважды, в дваэтапа: сначала его вычисление с использованием локальных связей xi с piи получение расширенной формы (она называется так, потому что, какправило, больше и сложнее исходной формы), затем вычислениеполученной формы уже вне контекста макровызова.

Таким образом,содержащее макровызов выражение эквивалентно выражению, в котороммакровызов заменён на его расширенную форму.Укажем также различие макросов и функций, строящих ивычисляющих выражение с помощью базовой функции eval. Обавычисления, выполняемые функцией eval, происходят в контексте вызовафункции, вычисление же расширенной формы макровызова происходитуже вне контекста его вызова.Макросы, так же как и функции, могут быть рекурсивными. В такомслучае на этапе макрорасширения может быть получена форма,содержащая макровызовы.

Тогда на этапе вычисления расширеннойформы содержащиеся в ней макровызовы будут вычисляться по тем же(описанным выше) правилам.Макросы – удобное средство расширения языка Лисп, поскольку сих помощью несложно определить новые синтаксические конструкции.Приведём пример определения макрофункции (If C E1 E2),встроенной в MuLisp и Common Lisp, которая вычисляет значение96выражения E1, если значение выражения C отлично от NIL, в ином случаеона вычисляет значение E2:(defmacro If (C E1 E2)(list 'cond (list C E1)(list T E2)) )Этот макрос строит и вычисляет условное выражение cond, вкотором в качестве условия первой ветви берётся выражение С (первыйаргумент If), а выражения E1 и E2 (второй и третий аргумент If)размещаются соответственно на первой и второй ветви cond.К примеру, для макровызова (If(numberp K)(+ K 10) K) наэтапе макрорасширения будет построена конструкция(cond ((numberp K)(+ K 10)(T K)), а на этапе её вычисления вслучае K=5 будет получено значение 15.Поскольку для построения вычислимой формы в макросах обычноиспользуется довольно большое количество вложенных друг в другавызовов функций cons, list и append, определение макросов частостановится громоздким и не очень понятным.

Для упрощения описаниямакросов в Лиспе применяется специальное средство блокировкивычислений, которое называют обратной блокировкой. В отличие отобычной блокировки вычислений функцией quote (или ') обратнаяблокировка вычислений записывается с помощью апострофа,наклонённого в другую сторону: ` (этот знак иногда называется обратнойкавычкой от англ. back quote).Отличие выражений, к которым применена обратная блокировка, отпросто заквотированных выражений в том, что в них можно локальноотменять блокировку вычислений, т.е.

осуществлять вычислениенекоторых подвыражений. Отмена блокировки помечается запятой (,),которая ставится перед каждым вычисляемым подвыражением. Каждоепомеченное запятой подвыражение на этапе макрорасширениявычисляется и заменяется на его значение. Такое использование запятойназывают обычно замещающей отменой блокировки.Запятую можно использовать также вместе со знаком @, тогда вместоподвыражения,помеченногодвумязнаками,@,наэтапемакрорасширения подставляется его значение без внешних скобок.

Такуюотмену блокировки называют присоединяющей.Приведём примеры. Пусть переменные имеют следующие значения:x=>Ay=>(A S D)z=>(F (C (V)) G (7))тогда`(z x (,x 5) ,y) => (Z X (A 5)(A S D))`((1 2) ,x 3 4 ,@y (5 6) ,@z 7) =>((1 2) A 3 4 A S D (5 6) F (C (V)) G (7) 7)97`(,x (z ,(cadr z))(,(caddr y) ,@(cdr z))) =>(A (Z (C (V)))(D (C (V)) G (7)))Использование обратной блокировки и её отмены (замещающей иприсоединяющей) позволяет компактно и более понятно записатьмакроопределение. К примеру, определение макроса If можно записатьтак: (defmacro If (C E1 E2) `(cond (,C ,E1)(T ,E2)) ).Обратную блокировку вычислений допускается использовать нетолько при определении макросов, но и при определении функций.Например, данное для диалекта MuLisp в разделе 3.5 определениефункционала Twice с функциональным значением (он возвращаетфункцию, которая дважды применяет его функциональный аргумент)можно существенно упростить:; определение Twice при помощи обратной блокировки,; требует предварительной загрузки файла common.lsp(defun Twice (F)`(lambda (X)(funcall (quote ,F)(funcall (quote ,F) X))))Приведём ещё один пример, демонстрирующий изменениевычислительного контекста при обработке макровызова.

Пусть описанмакрос ASD:(defmacro ASD (X Y)`(cons (list ,(car X) ,@(cdr X)) (list Y ,@Y)))Вычисление выражения(let ((X 12) (Y '(A B)) (Z '(1 2 3)))(ASD (X Y)(X Y Z)))будет происходить следующим образом:1. При вызове конструкции let вычислительный контекст будетпополнен связями X=12, Y =(A B), Z =(1 2 3) , после чего будетвызван макрос ASD: (ASD (X Y)(X Y Z)).2. На этапе макрорасширения этого вызова формальные параметрымакроса (X и Y) будут связаны с фактическими параметрами вызова:X=(X Y), Y= (X Y Z), и при вычислении тела макроса вместовыражения ,(car X) будет подставлено X, вместо выражения,@(cdrX) подставится Y, а вместо выражения ,@Y –последовательностьX Y Z. Таким образом будет построеновыражение(cons (list X Y)(list Y X Y Z)), после чегосвязи между фактическими и формальными параметрами макросаразрываются.983.

Восстанавливаются прежние значения переменных X и Y: X=12,Y =(A B), и в этом контексте будет вычислено полученное на этапемакрорасширения выражение. Результатом вычисления макровызова, атакже всей конструкции let будет выражение((12 (A B))(A B) 12 (A B)(1 2 3)).Макросы часто используются для определения особых функций,которые не вычисляют или не всегда вычисляют свои аргументы. Вкачестве такого примера приведём рекурсивные макроопределениявстроенных функций or и and. В предыдущем разделе их определениябыли даны для MuLisp с помощью конструкции nlambda. Поскольку вCommon Lisp эта конструкция отсутствует, указанные функции в этомдиалекте могут быть описаны только в виде макросов:; макроопределение в Common Lisp функции or(defmacro or(&rest X)(cond ((null X) NIL)((eval (car X)) (car X))(T (cons 'or (cdr X))))); макроопределение в Common Lisp функции and(defmacro and(&rest X)(cond ((null X) T)((null (cdr X)) (car X))((eval (car X)) (cons 'and (cdr X))) ))Заметим, что для обработки произвольного количества аргументов вопределениях этих макрофункций используется ключевое слово &rest, ипоэтому с формальным параметром X связывается список невычисленныхаргументов функции (т.е.

фактических параметров). В результатемакрорасширения по второй ветви функции будет выдан первыйневычисленный аргумент, который на следующем этапе обработкимакровызова будет вычислен. Аналогично, при макрорасширении потретьей ветви будет сформирован рекурсивный вызов or или and(аргументами функции служат элементы списка X, за исключениемпервого), и на следующем этапе этот вызов будет вычисляться – при этомопять будут повторены описанные этапы обработки макровызова.Рекурсия завершится, когда сработает первая или вторая ветвьмакрофункции, т.е.

когда список X станет пуст или когда значение первогоего элемента отлично от NIL.Рассмотрим, к примеру, последовательность этапов вычислениямакровызова (or (eq 'A 'B)(+ 2 3) NIL (atom 'C)):991) В результате макрорасширения этого вызова (проработает третья ветвьcond) будет получено выражение(or (+ 2 3) NIL (atom 'C)) .2) Поскольку полученная форма сама является макровызовом, она врезультате макрорасширения (сработает вторая ветвь cond) будетзаменена на выражение (+ 2 3).3) Этовыражениебудетвычислено(наэтапевычислениямакрорасширения), и его значение (число 5) будет возвращено какрезультат вычисления исходного макровызова.4.6.Циклы, блоки и присваиванияВо многих диалектах Лиспаимеютсяфункции-аналогиширокоупотребительных операторов традиционных императивных языковпрограммирования: операторов присваивания, цикла, перехода и др.Особенность этих функций в том, что в основном они опираются напобочный эффект вычислений, а значит, их использование не вписываетсяв рамки строго функционального программирования.Кратко опишем некоторые из этих функций.Для присваивания переменной значения используется особаявстроенная функция setq с обращением (setq имя_переменной e).Первый аргумент функции setq не вычисляется, он должен быть именемпеременной (символьным атомом).

Второй аргумент функции –лисповское выражение-форма e, оно вычисляется, и его значениеприсваивается указанной переменной. Значением функции setq являетсявычисленное значение второго аргумента.Функция set отличается от setq тем, что вычисляет оба своихаргумента, т.е. является обычной. Значением первого аргумента должнобыть имя переменной, которой и присваивается значение второгоаргумента.Обе описанные функции есть в диалектах MuLisp и Common Lisp.Примеры использования функций присваивания:(setq Var '(12 8 67.5))(set (cadr '(A S D)) (mapcar 'add1 Var))В Common Lisp для программирования повторяющихся вычисленийприменяется конструкция-цикл do, обращение к ней имеет вид:(do (v1 v2 … vm)(p t1 t2 … tк)e 1 e2 … en )m≥0, k≥0, n≥0где (v1 v2 … vm) – список переменных цикла (может быть пуст);100(p t1 t2 … tк) задаёт условие p окончания цикла и выражения ti,вычисляемые при выходе из цикла;e1 e2 … en – тело цикла.Более точно, vi – это либо имя переменной, либо список вида(имя_переменной начальное_значение [следующее_значение] ),в котором в качестве начального и следующего значения могут братьсялюбые вычислимые лисповские выражения (формы); квадратные скобкиуказывают на необязательность соответствующего выражения.Вычисление функции do начинается с одновременногоприсваивания переменным цикла начальных значений; если начальноезначение не задано, то переменной присваивается NIL.

Свежие статьи
Популярно сейчас