И ыный

174

175

cm cn2 чл

(В Лиспе для слова ЧЛ есть синоним ЧЛРАВ - MEMQ.) ЧЛ воз- вращает остаток от СП2, начинающийся с первого встретившегося элемента, равного (РАВ) СП1. В противном случае на стек поме- щается НУЛЬ. Слово ЧЛЕН аналогично слову ЧЛ, за исключени- ем того, что оно для сравнения элементов списка СП1 с элемента- ми списка СП2 использует не РАВ, а РАВНО (см. разд. "Функции РАВНО и РАВ").

Наконец, фрагмент

С1 С2 СЗ ПОДСТ

4 9

0. \

1. \

2 (

3

4

5 :

6

7

8

9

10 11 12 ; 13 14 15

ЛИСПОПОДОБНЫЕ СЛОВА ПОСТРОЕНИЯ СПИСКОВ НА ФОРТЕ-83

ЭЛЕМЕНТ ©СПИСОК -> @ХВОСТ) \ ЕСЛИ ЭЛЕМЕНТ В СПИСКЕ \ ПРИСУТСТВ. ТО @ХВОСТ БУДЕТ ОСТАТКОМ СПИСКА, \ НАЧИНАЮЩЕГОСЯ С ЭЛЕМЕНТА; ИНАЧЕ НУЛЬ ЧЛ SWAP OVER НОЛЬ IF2DR0P НУЛЬ ELSE OVER ПЕРВЫЙ OVER = IF DROP

ELSE SWAP ХВОСТ РЕКУРСИЯ THEN THEN

Э кран 49. Слово ЧЛ работы со списками

осуществляет подстановку С-выражения С1 вместо всех вхождений С2 в С-выражении СЗ и возвращает СЗ. ПОДСТ сравнивает эле- менты списка СЗ с элементами списка С2 с помощью функции РАВНО. Атомы возвращаются неизмененными.

Слова ПОДСТ (SUBST), УДАЛИТЬ и ОБРАТНЫЙ в Лиспе имеются, но здесь они не реализованы.

а) ХВОСТ

б) ХВОСТ ПЕРВЫЙ

в) ПЕРВЫЙ ПЕРВЫЙ

г) ХВОСТ ХВОСТ ПЕРВЫЙ ХВОСТ

д) ХВОСТ ХВОСТ ХВОСТ ПЕРВЫЙ

е) ХВОСТ ХВОСТ ПЕРВЫЙ ХВОСТ ХВОСТ ПЕРВЫЙ

ж) ХВОСТ ХВОСТ ПЕРВЫЙ ХВОСТ ХВОСТ ПЕРВЫЙ ХВОСТ ХВОСТ ПЕРВЫЙ

з) ХВОСТ ХВОСТ ХВОСТ ПЕРВЫЙ

2. Объясните, почему в слове ХВОСТ (экран 40) мы не уменьшаем @СПИСОК безусловно. Что случится, если мы это сделаем?

3. Постройте схему, аналогичную приведенной на рис. 7.5, для списка из упр.1, давая подспискам имена.

4. Для всех приведенных ниже списков:

СП1: (С1 (С2 СЗ) С4) СП2: НУЛЬ СПЗ: (С2 СЗ)

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

а) С1 СПп ЧЛ ВЫДАТЬ

б) СПп ДЛИНА

в) СПп АТОМ?

г) СПЗ @ ЧЛ

д) СПЗ ЧЛ

5. Напишите определение слова ОБРАТНЫЙ, располагающего элементы списка в обратном порядке.

6. Напишите определение слова СГЛАЖИВАНИЕ, которое выбирает элементы подсписков и помещает их в список верхнего уровня, например:

(А (В C)(D (E F) G)) --> (А В С D E F G)

7. Напишите определения функций доступа к спискам свойств ПОЛУЧСВ ' (GETPROP) и ПОМЕСТСВ (PUTPROP).

УПРАЖНЕНИЯ

1. Для следующего списка: (А В(С D (E F (G) Н) О) определите результат выполнения следующих операций:

176

Глава 8 методы программирования

: ПОСЛЕДНИЙ DUP ХВОСТ НОЛЬ NOT IF ХВОСТ РЕКУРСИЯ THEN ;

Слово ПОСЛЕДНИЙ берет с вершины стека указатель списка и осуществляет проверку на завершение. При этом проверяется, не пуст ли хвост списка. Если хвост - НУЛЬ, выполнение слова заканчивается. В противном случае выбирается хвост списка и вновь вызывается слово ПОСЛЕДНИЙ. Для этого применяется слово РЕКУРСИЯ, так как в Форте не предусмотрено нахождение в словаре слова, определяемого в данный момент. Для иллюстра- ции выполнения рекурсивных слов предположим, что слово ПОС- ЛЕДНИЙ было вызвано с указателем в вершине стека, ссылаю- щимся на список: (А В). Последовательность выполнения слов по- казана стрелками на рис. 8.1.

В Лиспе как данные, так и команды выражаются в форме спи- сков и взаимозаменяемы. Мы же будем использовать списки толь- ко в качестве данных (в прямом их смысле), поскольку интерпре- татор Форта не интерпретирует списки - он интерпретирует шитые код. Управляющая логика программы отрабатывается соответству- ющими традиционными словами на Форте. Форт на самом деле имеет более обширный набор управляющих слов, чем Лисп. Уни- версальный оператор Форта CASE аналогичен функции COND Ли- спа. Но в Лиспе отсутствуют такие конструкции, имеющиеся Форте, как IF-THEN-ELSE, BEGIN-UNTIL, BEGIN-WHILE- REPEAT. Последние две конструкции являются примитивами пос- троения циклов. Они заставляют последовательность команд по- вторяться неоднократно за счет передачи управления назад, на начало последовательности.

РЕКУРСИЯ

Несмотря на то что Форт предоставляет удобные средства для программирования рекурсивных процессов, к ним очень редко об- ращаются. Программирование, основанное на списках, составляет исключение. Рекурсия имеет место в тех случаях, когда какое-то | слово вызывает само себя. Если параметры, используемые данным словом, при этом находятся в стеке, то они во время вызова оче- редного экземпляра этого слова остаются неизменными. Рекурсию можно представить как вызов копии исходного слова. Рекурсивный вызов может выполняться несколько раз и всякий раз параметры предыдущего вызова будут проталкиваться в глубь стека. В конце концов некоторое условие должно завершить последовательность

: ПОСЛЕДНИЙ DUP ХВОСТ НОЛЬ NOT IF ХВОСТ РЕКУРСИЯ

■: ПОСЛЕДНИЙ DUP ХВОСТ НОЛЬ NOT IF THEN ;

THEN

Рис. 8.1. Схема передачи управления в рекурсивном слове

ПОСЛЕДНИЙ. РЕКУРСИЯ вызывает копию слова ПОСЛЕДНИЙ (вторая

строка), которая завершает рекурсию

Обратите внимание на то, что здесь две строки содержат опре- деление слова ПОСЛЕДНИЙ. Верхняя строка соответствует исход- ному вызову со списком (А В) в стеке. Поскольку хвостом (А В) является (В) , т.е. хвост не пустой, то выполняется ветвь, следую- щая за IF. ХВОСТ от (А В) помещает в стек (В), а затем выполня- ется слово РЕКУРСИЯ. Оно вновь вызывает слово ПОСЛЕДНИЙ, при этом стрелка ведет ко второй строке. Это слово начинает вы- полняться, на сей раз с (В) в стеке. Хвост (В) является НУЛЕМ, поэтому ветвь за IF пропускается до THEN и ; , что приводит к выходу из данной копии слова ПОСЛЕДНИЙ и переходу к той, которая представлена верхней строкой, а именно к варианту, выз- вавшему копию. Выполнение продолжается с того места, откуда вызывалась РЕКУРСИЯ. Выход из этого варианта осуществляется обычным образом и в стеке остается (В) - последний элемент из (А В).

178

Если бы список был длиннее, то последовательность списков, остававшаяся в стеке после каждого вызова слова ПОСЛЕДНИЙ, была бы следующей:

(А В С D) (BCD) (CD) (D)

Поскольку всякий раз, когда рекурсивно вызывается слово ПОСЛЕДНИЙ, в стек возвращается хвост заданного списка, у это- го списка последовательно отсекаются головы до тех пор, пока не останется один элемент. Такая рекурсия называется хвостовой, так как слово последовательно обрабатывает хвост списка. Кроме рассмотренных, хвостовую рекурсию осуществляют слова ДЛИНА и ЧЛ. При использовании ЧЛ ему передаются два параметра, но при каждом рекурсивном вызове ЧЛ ЭЛЕМЕНТ остается прежним, а от списка ©СПИСОК - только хвост.

При первом знакомстве рекурсия, как правило, вызывает не- доумение. Однако она так же естественна, как любой циклический процесс. Недоумение зачастую происходит от того, что одна и та же процедура обращается сама к себе несколько раз. Однако пред- ставьте себе, что всякий раз вызываются отдельные копии, а если это необходимо, то можно называть каждую копию (скажем слова ПОСЛЕДНИЙ) своим именем, например: ПОСЛЕДНИЙ 1, ПОС- ЛЕДНИЙ2 и т.д. Напоминаем, что управление в любую копию пе- редается дважды: первый раз при ее вызове, а второй - при возврате в нее после рекурсивного вызова. В определении слова ПОСЛЕДНИЙ выполняется проверка словом НОЛЬ, а затем сло- вом ХВОСТ из оператора IF-THEN, после чего РЕКУРСИЯ вызы- вает слово ПОСЛЕДНИЙ в очередной раз. Управление снова воз- вращается в данную копию, причем в то место определения, от- куда произошел рекурсивный вызов, т.е. происходит выход из оператора IF-THEN и из самого определения этой копии слова ПОСЛЕДНИЙ.

Для того чтобы понять, что происходит между рекурсивными вызовами, нужно проследить за изменением содержимого стека (рис. 8.2). Начиная с верхнего левого угла, мы имеем в стеке список (А В С). Каждый последующий вызов слова ПОСЛЕДНИЙ спускает нас на один уровень ниже по левой стороне рисунка. При первом вызове слова ПОСЛЕДНИЙ в момент рекурсии в стеке ос- танется (В С).

После второго рекурсивного вызова в стеке останется (С). Заметьте, что управление все время "крутится" вокруг первой части слова ПОСЛЕДНИЙ - от его начала до слова РЕКУРСИЯ. При рекурсии повторяется одно и то же действие. Список как бы обрезается всякий раз на один элемент. Останавливает такой рекурсивный спуск выполнение условия завершения: если хвост

180

списка, переданного очередной копии слова ПОСЛЕДНИЙ НУЛЬ, то рекурсия завершается.

THEN

(С)

/I

: ПОСЛЕДНИЙ DUP ХВОСТ НОЛЬ NOT IF ХВОСТ РЕКУРСИЯ (А В С)

Вызов слова

Результат после первого • вызова

(С)

i 1

(ВС)

П ОСЛЕДНИЙ

(С)

Завершающий вызов: ПОСЛЕДНИЙ DUP ХВОСТ NOT IF THEN

Р ис. 8.2. Состояние стека при рекурсивном вызове слова

ПОСЛЕДНИЙ и исходном списке в стеке (А В С) . Выполнение

фрагментов Форт-программы, помещенных над вертикальными

линиями, для каждого уровня отмечается стрелкой. Фрагмент,

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

показан внизу

Когда в третий раз слову ПОСЛЕДНИЙ передается (С), хвост этого списка оказывается НУЛЕМ, что означает пустой список и та часть оператора IF-THEN, которая вызывает рекурсию будет обойдена. Третий вызов слова ПОСЛЕДНИЙ (показан в нижней части рис. 8.2) осуществляет возврат. Управление передается фраг-менту следующему за словом РЕКУРСИЯ, в копии слова ПОСЛЕДНИЙ, из которой был произведен рекурсивный вызов. На схеме рассматриваемая копия находится на следующем относи- тельно дна уровне. Здесь выполняется фрагмент THEN ; и проис- ходит очередной выход из определения. Множественный выход из

181

: ДЛИНА DUP НОЛЬ

IF ELSE ХВОСТ РЕКУРСИЯ (ABC)

1 +THEIM ; 3

(ВС)

копий слова ПОСЛЕДНИЙ продолжается до тех пор, пока не за- вершится выход из копии самого верхнего уровня.

Во время рекурсивного подъема по стрелкам в правой части рис. 8.2 список не изменяется. Он просто передается с самого нижнего уровня наверх. Изменяется только стек возвратов, из которого при выходе из очередной копии слова ПОСЛЕДНИЙ пос- ледовательно убираются адреса возвратов.

В качестве второго, чуть более сложного, примера рассмотрим определения слова ДЛИНА (экран 48). Для сравнения здесь приве- дены оба варианта - и итерационный, и рекурсивный. В реализа- ции итерационного алгоритма цикл BEGIN-WHILE неоднократно исполняется до тех пор, пока список не будет усечен до НУЛЯ. На каждом шаге выполнения цикла счетчик, значение которого внача- ле было равно нулю, увеличивается. Состояние стека перед выпол- нением BEGIN следующее:

(список счетчик)

Рекурсивный вариант действует по аналогичной схеме, но вместо цикла внутри одной и той же копии слова ДЛИНА в нем вызываются последовательные копии, как показано на рис. 8.3. Части определения слова ДЛИНА, соответствующие рекурсивному спуску и подъему, расположены над вертикальными стрелками. Во время спуска выполняется начальный фрагмент определения слова ДЛИНА до слова РЕКУРСИЯ. Результатом выполнения этого фра- гмента является усечение списка посредством слова ХВОСТ. При каждом последующем вызове слова ДЛИНА ему передается спи- сок, укороченный на один элемент. В конце спуска условие завер- шения истинно, а список пуст.

В этом последнем вызове слова ДЛИНА (ему соответствует текст в нижней части рисунка) последовательность команд уже иная, так как здесь выбирается ветвь IF, а не ELSE. Операторы данной ветви удаляют из стека пустой список и вместо него поме- щают начальное значение счетчика, равное нулю, после чего осу- ществляется возврат из нашей копии слова ДЛИНА в вызываю- щую копию, которая на рис.8.3 расположена уровнем выше. По- скольку управление возвращается фрагменту, следующему за словом РЕКУРСИЯ, происходит увеличение числа на стеке и воз- врат. Количество таких увеличений равно количеству уровней. Так как каждый уровень соответствует рекурсивному вызову, во время которого при рекурсивном спуске из списка удаляется один элемент, число прибавлений на обратном пути будет совпадать с числом вызовов.

Другой вид рекурсии - так называемая двойная рекурсия, В этом случае слово РЕКУРСИЯ вызывается дважды. Обычно при одном вызове передается голова списка, а при втором - хвост. Примером тому может служить определение слова РАВНО. Его алгоритм показан на рис. 8.4, а исходный текст приведен на экра-

182

Выбирается НУЛЬ, заносится О

Выбирается НУЛЬ, заносится О

: ДЛИНА DUP НОЛЬ IF DROPOTHEN

Р ис. 8.3. Схема рекурсивных обращений к слову ДЛИНА. При завер- шающем вызове стек очищается от списка, а счетчик обнуляется

не 53. Стековая нотация данного определения следующая: ( С1 С2 -> F)

Если С1 и С2 - атомы, то они сравниваются, на стек помещается соответствующий флаг и рекурсия при этом не выполняется. Если же они представляют собой списки, то головы и хвосты С1 и С2 Должны совпадать. Первая рекурсия осуществляется по головам всех С-выражений. Она продолжается до тех пор, пока не будут получены атомы, при условии, что сравниваемые головы сами являются списками, после чего исходный вариант слова РАВНО начинает рекурсивное выполнение по хвостам всех списков. Зна- чения флагов от двух рекурсий логически умножаются (операция

Рис. 8.4. Алгоритм выполнения слова РАВНО (пример двойной