ПРОСТЕЙШИЕ ОПЕРАЦИИ НАД СПИСКАМИ

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

40

0 \ СЛОВА ПОСТРОЕНИЯ СПИСКОВ ЛИСПА НА ФОРТЁ-83
1

2 VARIABLE НУЛЬ НУЛЬ НУЛЬ! \ ПУСТОЙ СПИСОК
3

4 ( #ЭЛЕМЕНТОВ -> ) \ #ЭЛЕМЕНТОВ = МАКСИМ. ЧИСЛУ

5                   \ ЭЛЕМЕНТОВ СПИСКА

6: НОВСПИСОК CREATE HERE 2+, НУЛЬ, 2* ALLOT;

7 ( @СПИСОК -> ©ПЕРВЫЙ) \ @ПЕРВЫЙ-УКАЗАТ. НА ПЕРВЫЙ

8                        \ ЭЛЕМ.СПИСКА

9: ПЕРВЫЙ @;

10 ( @СПИСОК: НУЛЬ -> ФЛАГ) \ ФЛАГ = ИСТИНА, ЕСЛИ

11                              \ СПИСОК ПУСТОЙ

12: НОЛЬ @ НУЛЬ =;

13 ( ©СПИСОК -> @ХВОСТ) \ (ЭХВОСТ - УКАЗАТЕЛЬ НА ОСТАТОК

14 СПИСКА

15: ХВОСТ DUP НОЛЬ IF @ ELSE 2- THEN;

Экран 40. Слова построения списков: НОВСПИСОК, ПЕРВЫЙ и

ХВОСТ

ХВОСТ все еще по традиции используются слова CAR и CDR, со-
ответственно.) Слово ХВОСТ заносит в стек указатель на оставшу-
юся часть списка:

( ВС )

Если мы снова активируем слово ХВОСТ, то получим в ре-
зультате (С), а при повторной активации - НУЛЬ. Таким образом,
применив к исходному списку выражение

хвост хвост хвост

мы получим В веРшине стека нуль- Слова ПЕРВЫЙ и ХВОСТ позволяют нам перемещаться по спискам. Всякий раз, применяя

 

158

159

слово ХВОСТ, мы укорачиваем текущий список на один элемент
а с помощью слова ПЕРВЫЙ получаем указатель на первый эле-
мент текущего списка. Например, если нужно установить указа-
тель на второй элемент

ХВОСТ ПЕРВЫЙ

то будет получен указатель на В.

В Лиспе некоторые комбинации операций CAR и CDR объеди-
нены в одну операцию:

Операция

Последова- тельность!

Последова-
тельность!

CAAR CDDR CADR CDAR

CAR CAR CDR CDR CDR CAR CAR CDR

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

CADR помещает на вершину стека второй элемент списка, в то
время как CDAR - указатель на второй элемент головы исходного
списка. Например, CADR применительно к ((А В)С D) даст С, а
если применить к тому же выражению CDAR, то получим (В).

Конструирование списков осуществляется с помощью слова
СВЯЗЬ (CONS). В Лиспе для выполнения этого слова требуются
два аргумента: @ЭЛЕМЕНТ и I - идентификатор списка. СВЯЗЬ
получает свободную ячейку и устанавливает ее голову на
©ЭЛЕМЕНТ, а хвост - на I. В данной реализации ячейки связи не
используются. Они заменены ячейками списка, головы которых за-
носятся в некоторый массив в обратном порядке, как показано на
рис. 7.3. Адрес pfa переменной списка указывает на голову списка,
которая расположена по самому старшему адресу. Указатели на-j
элементы списка (головы его ячеек) располагаются в порядке I
уменьшения адресов до последней ячейки (она же начальная), ес-
ли считать от pfa. Завершает список указатель на НУЛЬ. На
рис. 7.3 приведен список (ABC).

Поскольку не используется аппарат ячеек связи, слово СВЯ31
должно всегда воспринимать список в памяти как переменную. В
отличие от Лиспа здесь нельзя получать свободные ячейки (кото-:
рые могут быть разбросаны в памяти произвольно). В Лиспе ячей-
ка связи помещает на стек указатель на голову результирующего
списка. А слово СВЯЗЬ, определенное на экране 41, указатель в
стек не заносит, так как оперирует непосредственно областью
размещения списка в памяти. Следовательно, имя списка I в стеке
является переменной-списком в словаре Форта.

160

Под такие списки (определяемые через НОВСПИСОК) выде-
ляется фиксированный объем памяти, поэтому их максимальная
длина, т.е. максимальное число членов списка, заранее определена

41                                                                                                            ;

0 \ ЛИСПОПОДОБНЫЕ СЛОВА ПОСТРОЕНИЯ СПИСКОВ

1 \ НА ФОРТЕ-83

2 ( I -> ) \ СПИСОК ДЕЛАЕТСЯ НУЛЕВЫМ (ПУСТОЙ СПИСОК)

3: ПУСТОЙ DUP 2+ DUP ROT! НУЛЬ SWAP! ;
4

5 ( I ©СПИСОК - > ) \ УСТАНОВКА ИМЕНИ СПИСКА I НА ©СПИСОК

6: УСТАНОВИТЬ DUP НУЛЬ = I F DROP ПУСТОЙ ELSE SWAP! THEN ■
7

8 ( ©ЭЛЕМЕНТ I -> ) \ ДОБАВЛ. ©ЭЛЕМЕНТ К ГОЛОВЕ СПИСКА I

9: СВЯЗЬ 2 OVER +! ©! ;
10

11 \ СЛОВО, ОСУЩЕСТВЛЯЮЩЕЕ РЕКУРСИЮ

12: РЕКУРСИЯ LAST© NAME> , ; IMMEDIATE
13

14
15

Экран 41. Слова построения списков: УСТАНОВИТЬ,
СВЯЗЬ и РЕКУРСИЯ

СВЯЗЬ присоединяет новый элемент к списку, продвигая указа-
тель списка (в pfa) вперед на один элемент и помещая на выделен-
ное место указатель на новый объект - ©ЭЛЕМЕНТ. Для удале-
ния элемента из головы списка нужно всего лишь переместить
указатель списка (pfa) в противоположном направлении. Если вы
хотите присоединить список (А В С) к списку с именем II, чтобы
тот предварял список II, достаточно ввести следующее:

С 11 СВЯЗЬ В 11 СВЯЗЬ А 11 СВЯЗЬ

⇐ Предыдущая16171819202122232425Следующая ⇒

Поделиться: