MULISP5

File: MULISP4.LES (c) 24/10/96 СПбЭТУ

CLRSCRN

Это пятая лабораторная работа из последовательности работ, которые

проводятся в диалоговом режиме и предназначены для освоения учащимися ос-

нов ЛИСПа с использованием его диалекта muLISP. В течение данной лабора-

торной работы Вы увидите примеры описания функций, которые используют ре-

курсию, и сами попробуете свои силы в написании программ на ЛИСПе.

CONTINUE

Функции, определенные пользователем, как и примитивные функции, вы-

зываются с определенными значениями фактических параметров (аргументов) и

возвращают единственное значение, которое определяется значениями факти-

ческих параметров. Вы уже знаете, что функция должна быть определена

пользователем с помощью функции defun прежде, чем к ней можно будет обра-

титься. Поэтому внутри определения функции должно быть обеспечено

средство ссылки на каждый из аргументов функции перед тем, как будут из-

вестны конкретные значения этих аргументов. Это средство обеспечивается

введением ФОРМАЛЬНЫХ АРГУМЕНТОВ. Список формальных аргументов задается в

скобках после имени функции. На следующем слайде Вы увидите, как исполь-

зуются формальные параметры при задании определения функции.

CONTINUE

В muLISP используется определение функций программистом с помощью

задания функции DEFUN в следующем виде:

(DEFUN имя_функции (арг1 арг2 ...)

форма1

форма2

... )

Это определение задает функцию с именем имя_функции. Атомы арг1,

арг2 и так далее - имена формальных параметров, которые обеспечивают воз-

можность ссылки на фактические аргументы функции. Тело функции может со-

держать одну или несколько форм. Название функции DEFUN представляет со-

бой сокращение двух английских слов DEfine FUNction (Определить функцию).

На следующем слайде мы покажем, как можно использовать функцию опре-

деления функции, при рассмотрении простого примера.

CONTINUE

Некоторые программисты могут предпочесть использовать для определе-

ния первого элемента списка функцию, название которой более понятно, чем

аббревиатура CAR, например FIRST (английское слово ПЕРВЫЙ). Это можно

легко сделать, использую следующее определение функции FIRST.

$ (DEFUN FIRST (LST)

(CAR LST) )

Обратите внимание на то, что в приведенном определении FIRST задает

имя определяемой функции, эта функция имеет единственный аргумент, кото-

рый используется в теле функции, а само тело функции состоит из

единственной формы, которая возвращает значение функции CAR от этого ар-

гумента.

Функции, определенные пользователем, вызываются точно так же, как и

другие функции ЛИСПа. Например:

$ (FIRST '(DOG CAT COW PIG))

CONTINUE

Не останавливайтесь на создании определения функции FIRST, которая

выделяет первый элемент списка. Давайте определим функцию SECOND, выделя-

ющую второй элемент списка:

$ (DEFUN SECOND (LST)

(CAR (CDR LST)) )

Во время следующей паузы определите функцию THIRD, которая выделяет

третий элемент списка, используя функции CAR и CDR, и придумайте ряд при-

меров на использование функций FIRST, SECOND и THIRD. Примените эти функ-

ции к одному и тому же аргументу-списку. При вводе функции ЛИСПа, занима-

ющей несколько строк, Вы не сможете отредактировать предыдущую строку,

если Вы уже нажали на клавишу <Enter>, поэтому будьте внимательны и про-

веряйте текст на каждой из строк прежде, чем Вы перейдете на следующую

строку. Когда Вы захотите вернуться в среду лабораторной работы, наберите

вызов функции RETURN и нажмите на клавишу ввода.

BREAK

А вот наше определение функции THIRD:

$ (DEFUN THIRD (LST)

(CAR (CDR (CDR LST))) )

$ (THIRD '(DOG CAT COW PIG))

CONTINUE

Во время первого урока Вы узнали, что атом NIL используется для

обозначения пустого списка. Значение NIL возвращается также при вызове

функций EQL и ATOM, если в результате вычислений получается логическое

значение "ложь". Поскольку NIL - это действительно специфический атом

muLISPа, важно иметь средства для его распознавания.

Нам будет полезна функция с названием NULL, которая возвращает логи-

ческое значение T, если ее аргументом является пустой список (то есть

NIL); в противном случае она возвращает логическое значение NIL. (С этого

момента мы вместо термина "пустой список" будем чаще использовать обозна-

чение "null-список".)

Во время следующей паузы напишите определение функции NULL (для это-

го Вам потребуется только одна из базовых функций обработки списка) и

примените функцию NULL к произвольным атомам и спискам.

BREAK

А вот наше определение функции NULL. Заметьте, что в тексте этого

определения у нас не появилось необходимости использовать апостроф перед

NIL, так как значение NIL есть NIL. Если Вы используете обозначение ()

вместо NIL в определении функции, перед () также не нужно ставить апост-

рофа.

$ (DEFUN NULL (OBJ)

(EQL OBJ NIL) )

$ (NULL '(A B C))

$ (NULL ())

CONTINUE

До этого момента мы рассматривали определения таких пользовательских

функций, у которых имя однозначно определяет выполняемое при обращении к

функции действие. Но реальная польза употребления функций обычно связана

со способностью выбрать нужное действие в зависимости от значения аргу-

ментов вызова функции.

В нашем распоряжении есть три функции, которые позволяют выяснить с

помощью тестов, какие мы имеем значения аргументов при данном вызове. Это

функции EQL, ATOM и NULL. Функции, которые тестируют значения аргументов,

называются предикатами (PREDICATES).

На следующем слайде Вы увидите, как использовать предикаты для

тестирования значения аргументов.

CONTINUE

Как Вы должно быть уже заметили, тело функции состоит из одной или

более лисповских форм. В muLISPе различают простые и условные формы (или

предложения). Если форма представляет собой атом либо список, первый эле-

мент которого (то есть CAR) является атомом, то это простая форма.

Например:

(CONS ATM LST)

До этого момента Вы сталкивались в процессе ознакомления с материа-

лами уроков лишь с простыми формами. Форма, представляющая собой список,

первый элемент которого СAR не является атомом, называется условным

(CONDITIONAL) предложением. Например:

((ATOM EXPN) (CONS EXPN LST))

Первый элемент (CAR) условного предложения представляет собой предикатную

функцию. Если при вычислении значения предиката возвращается NIL, то зна-

чение всего условного предложения будет также NIL, и оценивание значения

тела функции продолжается; если в теле функции имеется следующая форма,

то производится оценивание ее значения. Если при вычислении значения пре-

диката получается результат отличный от NIL, то оставшаяся часть тела

функции игнорируется и производится оценивание значения CDR условного

предложения.

Примеры на нескольких последующих слайдах помогут Вам понять это ут-

верждение.

CONTINUE

У нас уже есть функция АТОМ, которая возвращает значение "истина"

(Т), если ее аргумент является атомом. Однако в muLISPе нет подобной

функции для распознавания списка. Почему ? Потому, что в случае необходи-

мости пользователь может написать такую функцию.

Давайте сделаем это. Поскольку новая функция будет предикатной функ-

цией для работы со списком, назовем ее LISTP. Если при вызове аргументом

этой функции будет являться атом, LISTP возвратит значение NIL. Если ар-

гумент не является атомом, это должен быть список, и функция LISTP возв-

ратит значение T.

$ (DEFUN LISTP (OBJ)

((ATOM OBJ) NIL)

T )

Вы можете воспринимать определение, находящееся в теле этой функции,

следующим образом: "Если аргумент OBJ есть атом, возвратить NIL; в другом

случае возвратить T".

После того, как Вы попробуете применить функцию LISTP к различным

объектам, включая и null-список, переопределите LISTP так, чтобы она

возвращала значение T, когда аргумент представляет собой null-список.

BREAK

Вот модифицированное определение функции LISTP, которая правильно

обрабатывает null-список:

$ (DEFUN LISTP (OBJ)

((NULL OBJ))

((ATOM OBJ) NIL)

T )

$ (LISTP 'DOG)

$ (LISTP '())

$ (LISTP '(DOG CAT COW))

Заметим, что поскольку при обращении к функции NULL сначала происхо-

дит вычисление формы на первой строке определения функции LISTP, и при

этом возвращается T в качестве значения вызова, то нет необходимости ста-

вить значение "истина" (T) вслед за списком (NULL OBJ).

CONTINUE

Представьте, что у Вас есть длинный список имен, и Вы хотите узнать,

является ли какое-нибудь имя элементом этого списка. Используя компаратор

EQL, Вы можете сравнить отыскиваемое имя с элементами списка. Вы могли бы

начать определение функции, осуществляющей поиск, следующим образом:

(DEFUN MBR (NAM LST)

((EQL NAM (FIRST LST)))

((EQL NAM (SECOND LST)))

((EQL NAM (THIRD LST)))

((EQL NAM (THIRD (CDR LST))))

...

Однако тело такого определения бесконечно. Мы хотели бы иметь воз-

можность применить функцию MBR к списку произвольной длины. Поэтому да-

вайте попробуем написать другое определение.

CONTINUE

Заметим следующее:

1. Если список пуст, то есть не имеет никаких элементов, то искомое

имя не является элементом этого списка.

2. Если имя равно (EQL) первому элементу (CAR) заданного списка,то

имя является элементом списка.

3. Если имя не равно первому элементу (CAR) заданного списка (EQL

возвращает значение NIL),то это имя является элементом списка в том и

только в том случае, когда оно является элементом хвоста (CDR) заданного

списка.

Очень важно, чтобы Вы полностью поняли и приняли перечисленные три

утверждения. Первые два из них более или менее очевидны. Третье утвержде-

ние можно истолковать несколько по-другому. Это утверждение означает, что

если имя не совпадает с первым элементом списка, то для выяснения, явля-

ется ли это имя элементом списка, все, что Вы должны сделать, это прове-

рить, входит ли это имя в хвост (CDR) исходного списка.

CONTINUE

Давайте используем сформулированные три утверждения для создания

трехшаговой процедуры выяснения, является ли некоторое имя элементом

списка:

1. Если список пуст (значение функции NULL есть Т), возвратить NIL.

2. Если имя равно (EQL) первому элементу (CAR) списка, возвратить T.

3. В противном случае нужно использовать эту процедуру для выясне-

ния, является ли имя элементом хвоста (CDR) списка, и возвратить вы-

численное значение как значение вызова.

Такая процедура называется рекурсивно определенной процедурой,

поскольку на третьем шаге для выяснения, является ли имя элементом хвоста

списка, применяется та же самая процедура, которую мы и хотим определить.

Описанные соображения легко выразить на muLISPе в виде определения

функции следующим образом:

$ (DEFUN MBR (NAM LST)

((NULL LST) NIL)

((EQL NAM (CAR LST)) T)

(MBR NAM (CDR LST)) )

Используйте созданное определение функции MBR для выяснения, явля-

ется ли имя DOG элементом списка (CAT COW DOG PIG).

BREAK

CLRSCRN

При изучении материала первого урока Вы выяснили, что предикатная

функция EQL хорошо подходит только для сравнения атомов, поскольку при

сравнении даже одинаковых списков она возвращает NIL. Например:

$ (EQL '(DOG CAT COW) '(DOG CAT COW))

Используя прием, который Вы изучили на примере функции MBR, опреде-

лите новую функцию с именем EQLIST, которая возвращает значение T, если

два списка, состоящие из атомов, равны; в противном случае функция EQLIST

должна возвращать значение NIL. Рассмотрите следующую рекурсивную проце-

дуру для определения функции EQLIST и убедитесь в ее правильности:

1. Если первый список пуст (значение функции NULL "истина"), возвра-

тить значение функции NULL с аргументом - вторым списком.

2. Если второй список пуст (значение NULL "истина"), возвратить зна-

чение NIL.

3. Если голова (CAR) первого списка не равна (NOT EQL) голове (CAR)

второго списка, возвратить NIL.

4. Возвратить результат оценивания EQLIST хвоста (CDR) первого спис-

ка и хвоста (CDR) второго списка.

Во время следующей паузы определите функцию EQLIST и рассмотрите

несколько примеров ее применения. Если Вы будете использовать описанную

выше процедуру, то Вам понадобится определить функцию NOT, предикатную

функцию, которая возвращает значение T, если ее единственный аргумент

есть NIL.

BREAK

А вот наше определение функций EQLIST и NOT :

$ (DEFUN EQLIST (LST1 LST2)

((NULL LST1) (NULL LST2))

((NULL LST2) NIL)

((NOT (EQL (CAR LST1) (CAR LST2))) NIL)

(EQLIST (CDR LST1) (CDR LST2)) )

$ (DEFUN NOT (OBJ)

(EQL OBJ NIL) )

$ (EQLIST '(DOG CAT COW) '(DOG CAT COW))

Заметим, что определение функции NOT идентично определению NULL, ко-

торое мы сделали ранее. Это происходит потому, что muLISP использует одно

и то же обозначение NIL для null-списка и логического значения "ложь".

CONTINUE

Те пользовательские функции, которые мы описывали до этого момента,

были либо селекторными, либо предикатными функциями. Давайте попробуем

написать определение функции-конструктора, а именно - функции для объеди-

нения двух списков.

При упоминании функции-конструктора на ум приходит функция CONS, ко-

торая используется для построения списка. Однако, вот какой будет резуль-

тат, если мы "наивно" используем функцию CONS, задав в качестве аргумен-

тов два списка.

$ (CONS '(DAVE JOAN AL) '(KAREN ANN JOE))

Вместо того, чтобы получить список из 6 элементов, мы обнаружим, что

результатом является список, содержащий 4 элемента; первым элементом ре-

зультирующего списка будет список, состоящий из 3 элементов. Для того,

чтобы получить список из 6 элементов, используя функцию CONS, нужно на-

писать следующую форму:

$ (CONS 'DAVE (CONS 'JOAN (CONS 'AL '(KAREN ANN JOE))))

Хотя много раз повторенное обращение к функции CONS действительно

обеспечивает получение искомого результирующего списка, этот способ нас

не может удовлетворить, так как мы хотели бы иметь одну такую функцию,

которую можно применить к аргументам, являющимся списками произвольной

длины, и получить список, содержащий суммарное число элементов.

CONTINUE

Рассмотрим задачу определения функции APPEND в терминах 5 базовых

функций muLISPа и функций, определенных пользователем к моменту вызова

функции APPEND. Вспомним, что сама функция APPEND квалифицируется как

функция, определенная пользователем к тому моменту, когда она потребуется

(другими словами, APPEND может быть определена с использованием ре-

курсии).

Давайте начнем решение задачи с рассмотрения самых простых частных

случаев.

Для заданных списков LST1 и LST2:

1. Если LST1 null-список, нужно возвратить LST2.

2. В противном случае сконструируем (применив функцию CONS) резуль-

тирующий список из головы (CAR) списка LST1 и результата применения функ-

ции APPEND к хвосту (CDR) первого списка и второму списку LST2.

На следующем слайде Вы увидите определение функции APPEND и пример

ее применения, а также познакомитесь с дополнительными разъяснениями. Од-

нако, если Вы хотите испытать свои силы, попробуйте дать определение

функции APPEND во время этой паузы.

BREAK

CLRSCRN

$ (DEFUN APPEND (LST1 LST2)

((NULL LST1) LST2)

(CONS (CAR LST1) (APPEND (CDR LST1) LST2)) )

$ (APPEND '(DAVE JOAN AL) '(KAREN ANN JOE))

Для того, чтобы хорошо понять приведенное выше рекурсивное определе-

ние, обратите внимание на аргументы функции CONS на последней строке тела

функции. Первый аргумент, (CAR LST1), это просто первый элемент списка

LST1. В приведенном выше примере первым аргументом функции CONS будет

атом DAVE.

Второй аргумент функции CONS, (APPEND (CDR LST1) LST2), есть список,

который получается присоединением всего первого списка, за исключением

его первого элемента, к списку LST2. Заметим, что это вполне корректное

употребление рекурсии, так как при каждом следующем повторном обращении

APPEND вызывает саму себя с более коротким списком LST1, чем в предыдущий

раз, а потому через некоторое время LST1 превратиться в null-список и ре-

курсивный процесс остановится. В приведенном выше примере вторым аргумен-

том функции CONS будет список (JOAN AL KAREN ANN JOE).

CONTINUE

Теперь Ваша очередь написать определение функции-конструктора с

использованием рекурсии. Определите функцию REMBER (REMove memBER), кото-

рая удаляет только первое вхождение заданного атома в список.

Например, при вызове этой функции

(REMBER 'DOG '(CAT DOG COW DOG))

должен возвратиться список (CAT COW DOG). Определение может иметь следую-

щую структуру:

(DEFUN REMBER (OBJ LST)

((NULL LST) ...)

((... OBJ ...) ...)

(CONS ... (REMBER ... ...)) )

BREAK

CLRSCRN

REMBER может быть определена следующим образом:

$ (DEFUN REMBER (OBJ LST)

((NULL LST) NIL)

((EQL OBJ (CAR LST)) (CDR LST))

(CONS (CAR LST) (REMBER OBJ (CDR LST))) )

$ (REMBER 'DOG '(CAR DOG COW DOG))

Если у Вас возникли трудности с функцией REMBER, Вы можете попробо-

вать описать функцию REMBER-ALL, которая удаляет не только первое, но и

все следующие вхождения заданного элемента в список. Поэтому при вызове

(REMBER-ALL 'DOG '(CAT DOG COW DOG))

результатом должен быть список (CAT COW). Подсказка: Вам нужно сделать

лишь небольшие изменения в функции REMBER, чтобы превратить ее в

REMBER-ALL.

BREAK

CLRSCRN

REMBER-ALL может быть определена следующим образом:

$ (DEFUN REMBER-ALL (OBJ LST)

((NULL LST) NIL)

((EQL OBJ (CAR LST))

(REMBER-ALL OBJ (CDR LST)) )

(CONS (CAR LST) (REMBER-ALL OBJ (CDR LST))) )

$ (REMBER-ALL 'DOG '(CAR DOG COW DOG))

Заметьте, как расположен текст описания функции. Отступы в начале

каждой строки сделаны таким образом, чтобы было легче понять алгоритм ре-

шения задачи. Хотя об этом еще не было речи, Вы, должно быть, уже замети-

ли, что muLISP допускает свободный формат написания лисповских форм. Для

этого языка существенно лишь соблюдать правильный баланс круглых скобок !

CONTINUE

Последняя функция, которую мы обсудим в течение настоящего урока -

это функция реверсирвования списка REVERSE. Ее действие легко понять:

(REVERSE '(DOG CAT COW PIG))

возвращает в качестве результата список (PIG COW CAT DOG). Но описание

функции REVERSE содержит "маленькие хитрости".

Во время этой паузы посмотрите, можете ли Вы сами написать определе-

ние этой функции. Если Вас постигнет неудача, на следующем слайде Вы уви-

дите подсказку, как можно справиться с решением такой задачи.

BREAK

Не забудьте, что кроме 5 базовых функций Вы можете использовать и

другие, определенные к данному моменту, включая функцию APPEND.

На следующем экране подсказа будет более основательной.

BREAK

Если Вы еще не догадались, как определить функцию REVERSE, Вам надо

постараться повысить свой РК (рекурсивный коэффициент) ! С использованием

рекурсии вы можете реверсирвовать хвост (CDR) списка LST при помощи вызо-

ва

(REVERSE (CDR LST))

Теперь для того, чтобы осуществить реверс всего списка LST, Вам

остается лишь добавить (APPEND) результат реверса (REVERSE) хвоста (CDR)

списка LST к одноэлементному списку

(CONS (CAR LST) NIL)

Во время этой паузы попытайтесь в последний раз написать определение

функции REVERSE.

BREAK

REVERSE может быть определена следующим образом:

$ (DEFUN REVERSE (LST)

((NULL LST) NIL)

(APPEND (REVERSE (CDR LST)) (CONS (CAR LST) NIL)) )

$ (REVERSE '(DOG CAT COW PIG))

Хотя с точки зрения логики это вполне корректное определение функции

REVERSE, оно чрезвычайно неэффективно. APPEND вызывается столько раз,

сколько элементов в реверсируемом списке.

Давайте попытаемся создать более эффективное определение функции

REVERSE с использованием стека. Представьте себе, как можно изменить по-

рядок расположения книг в стопке на обратный.

CONTINUE

Самый простой способ - повторно выполнять одну и ту же процедуру:

брать верхнюю книгу из первой стопки (то есть CAR списка) и класть ее на

вершину второй стопки книг до тех пор, пока первая стопка книг не из-

расходуется. При этом перед началом этого процесса вторая стопка книг бу-

дет "пустой".

Для заданных двух списков, исходного и первоначально "пустого",

описанная ниже процедура обеспечит реверсирование исходного списка.

1. Если первый список пуст (NULL возвращает Т), возвратите в качест-

ве результата второй список.

2. В противном случае сконструируйте (CONS) список из головы (CAR)

первого списка и второго списка и примените функцию REVERSE к хвосту пер-

вого списка.

На основании использования описанной процедуры Вы должны суметь во

время этой паузы создать определение функции REVERSE более эффективным

способом.

BREAK

Функция REVERSE может быть эффективно определена следующим образом:

$ (DEFUN REVERSE (LST1 LST2)

((NULL LST1) LST2)

(REVERSE (CDR LST1) (CONS (CAR LST1) LST2)) )

$ (REVERSE '(DOG CAT COW PIG))

Заметьте, что хотя функция REVERSE определена с двумя формальными

аргументами, при вызове мы употребили лишь один фактический аргумент. При

этом, как правило, оставшиеся формальные аргументы получают значения NIL,

что часто удобно использовать.

CONTINUE

Во время этого урока Вы узнали, как можно расширить muLISP с помощью

определения новых функций. Сформулируем основные положения этого урока:

1. Определение функции включает в себя имя функции, список формаль-

ных аргументов и тело функции.

2. Тело состоит из форм. Форма может представлять собой простую или

сложную, например, условное предложение. В зависимости от значения, воз-

вращаемого предикатной фукнцией, условное предложение осуществляет то или

иное действие при оценке значения функции.

3. Рекурсивные определения - это чрезвычайно мощный и вместе с тем

элегантный инструмент. При реализации рекурсии аргумент вызова должен ме-

няться в сторону ситуации, сформулированной в условии выхода из рекурсив-

ного процесса.

CONTINUE

Поздравляем Вас с завершением работы над материалом четвертого уро-

ка! Теперь Вы можете попытаться самостоятельно создать рекурсивные опре-

деления новых функций. Мы предлагаем Вам 5 примеров:

1. (EQUAL list1 list2) - компаратор списков <list1> и <list2>,кото-

рый, в отличие от функции EQLIST, работает и в том случае, когда элементы

списков не являются атомами.

Например, он мог бы использовать в качестве аргумента список

((A B (C D)) (E F)).

2. (SUPER-REVERSE list) реверсирует список <list> на всех его уров-

нях. Например, он превращает список

((A B (C D)) (E F)) в список ((F E) ((D C) B A)).

3. (UNION set1 set2) возвращает в качестве значения результат теоре-

тико-множественное объединения множеств <set1> и <set2>.

(Множество задается списком, в котором не могут встречаться одинако-

вые элементы.)

4. (INTERSECTION set1 set2) возвращает пересечение двух множеств.

5. (SUBST new old list) заменяет все вхождения элемента <old> в

список <list> на элемент <new>.

CONTINUE

$ (RDS)