OF НУЛЬ FALSE ENDOF ASCII )

8 OF R@ СПИСОК TRUE ENDOF ASCII @

9 OF @ FALSE ENDOF

10       -1 > IN +! 7 CREATE EXECUTE FALSE ROT

ENDCASE

12 UNTIL R> DROP
13;

14
15

Экраны 45, 4 6. Слова построения списков: ЧТСИМ,
7 CREATE и ЧТСП

 

164

165

Если определить (В С) как II, то приведенный выше список можно
ввести как 12:

1 2 ЧТСП (А 1 1 @ D )

Обратите внимание на символ @, следующий за II, и знак
пробела после каждого имени элемента, включая последний, за D.
Для сканирования слов применяется сканер Форта, который в
качестве ограничителя требует символа пробела. Знак @ исполь-
зуется для получения указателя списка II, а не его идентифи-
катора. При выводе 12 результат будет таким же, как показано
выше, но если мы вместо прежнего запишем

1 2 ЧТСП (А И D )
а затем

1 2 @ ВЫДАТЬ,
то получим

(А 1 1 D )

ТИПЫ ДАННЫХ ПРИ РАБОТЕ СО СПИСКАМИ

В приводимых выше примерах головы списков ссылались на
другие списки или элементы, в частности на А, В, С или НУЛЬ.
Такие элементы называются атомами. В лиспоподобном расшире-
нии Форта атом представлен в стеке как pfa некоторой перемен-
ной. Идентификатор списка - тоже вид атома. Атомами считаются
либо имя списка, либо переменные, на которые указывают головы
списков. В Лиспе атомами являются типы данных, во многом схо-
жие с константами и переменными Форта. Это объекты, на кото-
рые ссылаются списки, но не сами списки.

Слово Форта АТОМ? на экране 41 идентифицирует указатели
как атомы, если они служат адресами pfa переменных. Поскольку
идентификаторы списков представляют собой расширенные пере-
менные Форта, то и они - атомы. Указатели же списков атомами
назвать нельзя: они отображают списки в большей степени, чем
атомы, потому что указывают на фактическую списковую структу-
ру. Так называемое С-ВЫРАЖЕНИЕ (символьное выражение) -
либо атом, либо список и в стековой нотации обозначается симво-
лом С. Иерархия списковых типов данных представлена на рис.7.4.

С-выражения

50

0 \ ОТДЕЛЬНЫЕ СПИСКИ
1

НОВСПИСОК 1 1

НОВСПИСОК 1 2

4 20 НОВСПИСОК 1 3
5

 

VARIABLE S1

VARIABLE S2

8 VARIABLE S3
9

 

И ЧТСП (S1 S2 S3 )

11 1 2 ЧТСП (S1 1 1 @ S2 S3 )

12 1 3 ЧТСП (S3 )
13

14
15

Атомы   Ячейки связи

Списки

НУЛЬ

Идентификатор
списка

Рис. 7.4. Иерархия типов данных Лиспа, используемых в книге.
Идентификатор списка представляет собой pfa переменной Форта,
именующей список

 

Экран 50. Отдельные списки

При использовании переменной Форта в стеке оказывается
Указатель на ее значение, а не само значение. Этот указатель в
стековой нотации обозначен символом I в том случае, если пере-
менная является идентификаторм списка. Указатели на списки
обозначаются сокращенно СП или @СПИСОК, а на них самих

 

166

167

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

ЧТО ТАКОЕ НУЛЬ?

Нуль - единственный в своем роде атом, который в то же вре-
мя представляет собой и список (пустой список). НУЛЬ в стековой
нотации аналогичен (). Кроме того, НУЛЬ ссылается сам на себя.
Выражение НУЛЬ @ помещает на стек НУЛЬ. По определению за-
головок НУЛЯ и хвост НУЛЯ - НУЛИ.

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

С ПИСКИ С ВОЙСТВ

Атомы могут ссылаться на уже упоминавшиеся выше списки
свойств. Список свойств отличается от обычного списка наличием
в голове символа -1 (или другого специального символа). Он созда-
ется таким образом, что имена свойств и их значения в нем чере-
дуются. Для списка СП заголовок СП равен -1, второй элемент
отображает первое свойство, а третий - его значение (рис. 7.5).

Рис. 7.5. Структура списка свойств с двумя свойствами БРУСКА

Слова, оперирующие со списками свойств, представляют собой ос-
новные функции доступа к базе данных. Одно из этих слов
ПОЛУЧИТЬ (GET) описывается следующей стековой нотацией:

( I СВ -> ЗН)

 ЗН - значение свойства СВ (С-выражение), СВ -имя свойства
у^я _м) для того чтобы получить на стеке значение свойства ЦВЕТ
атома БРУСОК, нужно ввести

БРУСОК ЦВЕТ ПОЛУЧИТЬ

В стек при этом помещается указатель на значение свойства
TIBET. Затем, если мы введем слово ВЫДАТЬ, то получим значе-
ние КРАСНЫЙ. Слово ПОМЕСТИТЬ (PUT), или его синоним
ПОМЕСТСВ (PUTPROP), помещает в список свойство и его зна-
чение. Если ввести

| ЗН СВ ПОМЕСТИТЬ

то свойство СВ со значением ЗН помещается в список как атом I.
В том случае, когда свойство СВ со значением ЗН уже есть в дан-
ном списке, прежнее значение будет замещено ЗН. Слово
ПОМЕСТИТЬ оставляет на стеке ЗН. Чтобы удалить некоторое
свойство, достаточно ввести

I СВ УДАЛСВ

(REMPROP). При этом, помимо прочего, в стек помещается еще и
флаг истина, если заданное свойство удалено, или ложь - если
такого свойства в списке не оказалось. Наконец, имеется слово
ПОЛУЧСП (GETL), формат использования которого следующий:

I СП ПОЛУЧСП

Это слово просматривает список свойств I в поисках первого эле-
мента СП, представляющего собой свойство из I. Оно доставляет
оставшуюся часть списка свойств, включая имя свойства, а в про-
тивном случае возвращает НУЛЬ.

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

 

168

169

АССОЦИАТИВНЫЕ СПИСКИ

Списки свойств представляют собой один из видов структуры
баз данных. Ассоциативные списки, или А-списки, имеют особую
структуру, где пары значение/ с войство размещаются в двух поло-
винках ячейки связи внутри А-списка. (На голову и хвост ячеек
связи иногда ссылаются как на " точечные пары".) Например, А -
список с двумя свойствами ЦВЕТ и ФОРМА показан на рис. 7.6.
Его структура отличается от приведенной на рис. 7.7:

((ФОРМА ПРЯМОУГОЛЬНИК) (ЦВЕТ КРАСНЫЙ))

Рис.7. 6. Ассоциативный список, или А-список, с теми же данными,
что и список свойств, изображенный на рис. 7.5

В А-списках ячейки связи используются более эффективно,
чем во вложенных списках, так как в первых реже применяются
НУЛИ. В результате они не являются списками свойств.

Слова АССОЦ (ASSOC) и АССОЦ# (ASSOC#) осуществля-
ют доступ к А-спискам. АССОЦ реализует просмотр списка СП в
поисках пары свойство/значение, имя свойства которой такое же,
как X. Если затем ввести выражение

X СП АССОЦ

то в стек будет помещена пара с именем X. Не обнаружив такой
пары, АССОЦ занесет в стек НУЛЬ. ААСОЦ# действует аналоги-
чным образом, только при сравнении заголовков пар использует
слово РАВНО (EQUAL) вместо РАВ (EQ). Исходный текст функ-
ции доступа к А-спискам АССОЦ приведен на экране 51.

170

ФУНКЦИИ РАВНО И РАВ

Функция РАВ (EQ) в Лиспе адекватна операции " =" в Форте.
Если два указателя в стеке арифметически равны, то как РАВ, так
и = помещает в вершину стека истинное значение. Однако два спи-
ска, построенные по одной и той же схеме, могут быть разными.
Равны ли эти списки? Их указатели не РАВ, хотя сами списки по-
строены идентично. Выведенные операцией ВЫДАТЬ, они похожи.

51

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

1 \ НА ФОРТЕ-83
2(ССП1-> СП2)

3: АССОЦ DUP НОЛЬ

4 IF NIP

5 ELSE 2DUP ПЕРВЫЙ ПЕРВЫЙ =

 

6 IF ПЕРВЫЙ NIP

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

8 THEN

9 THEN
10;

11
12
13
14
15

Экран 51. АССОЦ - слово для построения списков
Чтобы определить, имеют ли одну и ту же структуру два раз-
личных списка, применяют слово РАВНО (EQUAL). По отноше-
нию к атомам РАВ и РАВНО действуют одинаково, поскольку
идентификаторы атомов (в отличие от списков их свойств) не об-
ладают списковой структурой. Они расположены в некоторой обла-
сти памяти, на которую ссылается указатель (pfa). Итак, различия
между этими двумя функциями состоит в следующем: РАВ поме-
щает в вершину стека истину, если одинаковы указатели списков,
а РАВНО - если идентична списковая структура. Таким образом,
функция РАВНО выполняет больше действий, чем РАВ, поскольку
должна сравнить еще и структуры списков. Алгоритм РАВНО по-
казан на рис. 8.4 и будет разъяснен ниже.

Различие между РАВ и РАВНО ведет к различию и между не-
которыми словами. АССОЦ и АССОЦ# аналогичны, за исключе-
нием того, что АССОЦ при просмотре списка применяет функцию
РАВНО, а АССОЦ# - РАВ. Слово ЧЛ (МЕМВ) использует РАВ, в
то время как ЧЛЕН (MEMBER) - РАВНО. Еще одной функцией
сравнения, помимо РАВ и РАВНО, является НОЛЬ. Если в верши-
не стека НУЛЬ, это слово доставляет истину. Поскольку несколько
функций в Лиспе в случае неудачи оставляют на стеке НУЛЬ,

171

ФОРМА

ЦВЕТ

КРАСНЫЙ

ПРЯМОУ-
ГОЛЬНИК

Рис. 7.7. Вложенный список свойств, содержащий данные А-списка,

изображенного на рис. 7.6. Наклонная черта в хвостовой части

ячейки связи означает НУЛЬ

данная функция весьма удобна. Например, если УДАЛСВ не мо-
жет найти заданное свойство, чтобы удалить его из списка, оно по-
мещает в стек НУЛЬ. НУЛЬ во многих случаях действует как
ложь, а НОЛЬ используется для того, чтобы проверить наличие
лжи на стеке и выдать соответствующее значение флага в терми-
нах Форта. Так как структуры управления взяты из Форта, значе-
ния флагов проверяются словами типа IF, WHILE и UNTIL.

НУЛЬ содержит значение НУЛЬ, так что представляет ли
НУЛЬ список или идентификатор списка, он все равно будет рас-
познан как НУЛЬ. На самом деле НОЛЬ выбирает значение, на
которое ссылается указатель, находящийся на стеке, и сравнивает
его с НУЛЕМ, а поскольку это НУЛЬ, то и указывает он тоже на
НУЛЬ, т.е. выражение " НУЛЬ @" также дает нуль.

ОПЕРАЦИИ ПРЕОБРАЗОВАНИЯ СПИСКОВ

Список создается при вызове слова СВЯЗЬ. В Лиспе СВЯЗЬ
используется некоторыми функциями для построения новых спис-
ков путем преобразования исходных. Часто применение функции к
существующему списку заключается в изменении указателей в
ячейках связи этого списка, что экономит время и память. Напри-
мер, функция ОБРАТНЫЙ (REVERSE) располагает списки в об-
ратном порядке, выстраивая другой список (с помощью СВЯЗИ),
перевернутый по отношению к исходному. Если исходный список
можно не сохранять, то больший эффект в таком случае даст опе-

рация НОБРАТНЫЙ (DREVERSE), которая меняет направление
хвостов исходного списка непосредственно на месте.

В Лиспе существует несколько операций преобразования спис-
ков. Основные из них - ЗАМЕНАГ (RPLACA) и ЗАМЕНАХ
(RPLACD). Выражение

X Y ЗАМЕНАГ

меняет заголовок X на Y и возвращает модифицированный список.
Выражение

X Y ЗАМЕНАХ

аналогичным образом меняет хвост X на Y и возвращает модифи-
цированный список. Похожими по своим действиям словами яв-
ляются HKOHK(NCONC), НОБРАТНЫЙ, НУДАЛИТЬ
(DREMOVE) и ПРИСОЕД (ATTACH), рассматриваемые в следую-
щей главе. Там же мы обсудим и слова преобразования списков,
которые наиболее трудны для понимания (поэтому они описывают-
ся после изучения деталей реализации).

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

Поделиться: