Д ЛЯ Ч ЕГО Н УЖНО Э МУЛИРОВАТЬ Л ИСП?
Лисп представляет собой простой элегантный язык обработки
списков, и поэтому естественно, что выбор пал на него. Однако
1)орт по сравнению с Лиспом обладает определенными преимуще-
.твами, и нашу разработку следует рассматривать как попытку
объединить лучшие свойства этих языков путем расширения Форта
лиспоподобными средствами. Предлагаемые слова обработки спис-
ков не являются транслятором с Лиспа, написанным на Форте:
интерпретатор Форта не был заменен циклом EVAL-APPLY (так
называется интерпретатор Лиспа). Тем не менее Форт и Лисп во
многом схожи:
* Оба языка расширяемы в том смысле, что можно определять
новые функции. Однако в Лиспе нет понятия словаря; он не позво-
ляет, в отличие от Форта, использовать имя одной и той же функ-
ции в различных контекстах. В Лиспе также отсутствует возмож-
ность расширения средств компиляции.
* Как Форт, так и Лисп ориентированы на вызовы функций.
При передаче параметров в Форте применяется постфиксная (или
обратная польская) запись, в то время как в Лиспе - префиксная
(имя функции должно предшествовать аргументам). Чтобы выдер-
жать единообразие, мы приняли порядок следования аргументов,
соответствующий Лиспу. Для передачи параметров между слова-
ми-функциями в Форте имеется стек. Работа со стеком в Форте
осуществляется явно. Лисп также имеет аналогичный стек, но он
скрыт от пользователя.
* Идентификаторами в Форте служат переменные, располо-
женные в словаре - статически распределенном списке. OBLIST в
Лиспе несет ту же функциональную нагрузку.
* И в Форте, и в Лиспе широко используется рекурсия - при-
ем программирования (см. гл.8), в котором разрешается произво-
дить вызов функции из тела этой же функции с запоминанием со-
стояния исходного экземпляра функции. Стековый механизм та-
кую возможность допускает, так как прежние параметры при но-
вом обращении к. той же функции не затираются новыми парамет-
рами, а проталкиваются в глубь стека.
* И Форт, и Лисп имеют простой синтаксис, что частично вы-
текает из реализации вычислений вызовами функций.
154
155
? Оба языка компактны. Транслятор с чистого Лиспа занимает
приблизительно такой же объем памяти, что и Форт-система без
расширений.
? И Форт, и Лисп являются не просто языками, а сис т е ма м и
программирования. Каждый из них наделен функциями операци-
онной системы и может использоваться автономно как полноправ-
ная вычислительная среда. Они снабжены механизмами расшире-
ния динамического окружения и возможностей прикладного уров-
ня. Некоторые расширения Лиспа послужили основанием для того
чтобы ошибочно считать его громоздким языком, занимающим па
мять объемом в мегабайты.
? Эти языки обеспечивают удобную интерактивную среду из
терпретирующего типа, что хорошо согласуется с восходящим сти-
лем программирования, принятым в области ИИ, упрощает экспе-
риментирование с программами и их " расчленение". Поскольку
восходящий стиль программирования не рекомендуется для боль-
ших проектов, в которых занято много людей и требуется строгая
дисциплина программирования, программы, выдержанные в стиле
ИИ, сравнительно малы. И в Форте, и в Лиспе очень многое мож-
но сделать с помощью программы небольшого размера, но эта
программа должна быть тщательно продумана. Стиль ИИ подходит
для тех случаев, когда вырабатываются новые понятия, так как
проработка общей структуры (сверху вниз) невозможна без доста-
точных знаний о программах нижнего уровня, или когда область
применения программы уточняется в ходе ее создания и эксплуа-
тации. Поскольку лиспоподобное расширение Форта, рассматрива-
емое в книге, очень похоже на сам Лисп, при программировании
рекомендуется пользоваться пособиями по Лиспу. Ссылки на соот-
ветствующую литературу приводятся в приложении.
мают фиксированное место в области памяти и доступ к ним осу-
ществляется по значению индекса. Переопределить порядок эле-
ментов массива или сделать число элементов в массиве неограни-
ченным довольно трудно. Чтобы освободить память для добавляе-
мых к массиву элементов, требуется сдвинуть все, что расположе-
но в памяти за ним, и обновить указатели на перемещенные объ-
екты. Очевидно, что это не выполнимо. Списки делают динамичес-
кое управление памятью концептуально проще, а с точки зрения
вычислений - и эффективней.
ЧТО ТАКОЕ СПИСОК?
В Лиспе список строится из множества соединенных между
собой так называемых ячеек связи (CONS-cells), или точечных
пар. Эти ячейки представляют собой элементарные структуры, из
которых составляются списки. Ячейка связи представляет собой
тип данных, состоящий из двух основных компонент. Возможное
графическое представление такой ячейки показано на рис. 7.1.
Указательна ячейку
СВЯЗИ
Первый
Рис. 7.1. Ячейка связи, элементарная структура данных, из которых
строятся списки
СТАТИЧЕСКОЕ И ДИНАМИЧЕСКОЕ
УПРАВЛЕНИЕ ПАМЯТЬЮ
Слова Форта состоят из последовательности адресов шитого
кода, ссылающихся на другие слова. Будучи однажды скомпилиро-
ванными, эти слова имеют постоянное местоположение. Следовате-
льно, при определении таких структур данных, как константы, пев
ременные и массивы, за ними закрепляется фиксированная области
памяти. Для многих прикладных программ подобное статическо й
распределение памяти приемлемо. Однако существует ряд прилов
жений, где требуется динамическое распределение памяти, такое
распределение, при котором память, выделенная под заданную
структуру данных, не фиксируется во время компиляции и ее
местоположение может меняться во время выполнения программы
Если мы рассмотрим возможности распределения памяти под
такие структуры Форта, как массивы, то сразу же столкнемся со
сложными схемами управления памятью. Элементы массива зани-
156
Левый компонент - это голова, или первый (CAR), а правый -
хвост, или остаток (CDR). Ничего не значащие имена CAR и
CDR сложились исторически. В свое время так обозначались ма-
шинные регистры, используемые в реализациях Лиспа. Как голова,
так и хвост служат указателями. Голова указывает на элемент
списка, а хвост - на следующую ячейку связи. Пример построения
списка из трех элементов показан на рис. 7.2.
Указатель на список - это всего лишь адрес. Список может
быть представлен в стеке данных Форта в виде указателя на пер-
вую ячейку связи (или голову) списка. (Список в стеке представ-
лен проще, чем строка Форта, поскольку она требует наличия в
стеке двух элементов: адреса начала строки и ее длины.) Список,
" оказанный на рис. 7.2, состоит из трех элементов, ка которые
ссылаются соответствующие головы ячеек связи, - списки А, В и С
(по порядку обхода списка). Хвост последней ячейки связи указы-
15 7
вает на НУЛЬ, что означает конец списка. У нас НУЛЬ является
переменной Форта.
Для списков существует и другая (даже более подходящая)
так называемая скобочная запись, согласно которой список просто
заключается в круглые скобки. В скобочной записи список, пока-
занный на рис. 7.2, будет выглядеть следующим образом:
(А В С)
Рис. 7.2. Список из трех элементов: (А, В, С)
Реализация лиспоподобных слов на Форте, обсуждаемая в нас-
тоящей главе, показана на экранах с 40 по 49, а также в приложе-
нии А, где приводятся листинги исходных текстов. В такой реали-
зации списки создаются несколько иным способом, отличным от
рассмотренного выше. Здесь применяется более общая структура
использования ячеек связи - с динамическим управлением списка-
ми. Во избежание необходимости динамического управления памя-
тью списки создаются в виде переменных Форта, для которых па-
мять выделяется статически. Список идентифицируется именем пе-
ременной, а собственно список находится в теле этой переменной.
ее pfa содержит указатель на выделенный участок памяти под го-
лову списка.
Слово НОВСПИСОК (NEWLIST) является определяющим
словом, создающим переменную с именем, которое следует за|
НОВСПИСОК во входном потоке. Кроме того, оно берет из стека
число, задающее максимальное количество элементов для данного
списка. Это число используется для выделения памяти следом за
переменной. Полученное в результате выполнения слово действует
как переменная периода выполнения, поскольку CREATE в НОВ-
СПИСОК построит cfa, указывающий на процедуру периода выпо-
лнения, соответствующую переменной. НОВСПИСОК инициирует
вновь созданный список как пустой. Переменная Форта с выделен-
ной дополнительной памятью называется расширенной перемен-
ной. Под списками мы подразумеваем расширенные переменные.
