Cтраница 1
Наиболее известная реализация Снобола 4 ( макрореализация, описанная Грисволдом [1972]) основана на моделировании виртуальной Снобол-машины полностью программными средствами. Снобол-программы транслируются только во внутреннюю выполняемую цепочку команд в префиксной польской записи, которая декодируется и выполняется программой-интерпретатором. Организация памяти во время выполнения базируется на центральной таблице цепочек литер, которая в любой момент содержит по одному элементу для каждой существующей цепочки, включая имена переменных, метки инструкций и другие идентификаторы наряду с цепочками, используемыми в качестве значений переменных и элементов массивов. Когда во время выполнения создается цепочка литер, она заносится в эту таблицу, если такой цепочки еще не существует. [1]
В реализации Снобола 4, описанной в этой главе, цепочки вносятся в центральную таблицу в момент их создания. Цепочки без ассоциаций могли бы храниться во временной памяти лишь до тех пор, пока они не станут мусором и их можно будет уничтожить, Укажите достоинства и недостатки этого метода. [2]
В обычной реализации Снобола 4 программы транслируются в выполняемую форму, которая декодируется и выполняется программой-интерпретатором. Синтаксическая структура программ на языке Снобол 4 делает эту трансляцию относительно простой. Поскольку в языке отсутствуют ограни чители подпрограмм, декларации и структурные инструкции, каждая инструкция программы может быть странслирована без учета контекста, в котором она встречается. Поэтому можно транслировать строки программы последовательно и независимо одна от другой. Относительно позднее время связывания большинства элементов инструкций Снобола также упрощает трансляцию, поскольку во время трансляции очень мало известно об интерпретации инструкции. Таким образом, процесс трансляции сводится к выполнению простых синтаксических проверок и преобразованию каждой инструкции в блок выполняемых кодов, который в значительной степени представляет собой результат простой перекодировки исходной программы в форму, несколько более удобную для выполнения. В обычной реализации Снобола 4 эти блоки кодов имеют вид последовательности префиксных инструкций, каждая из которых состоит из символа операции и списка операндов. Операнды сами могут быть префиксными ин - j струкциями, подлежащими вычислению, так что вся программа напоминает древовидную Структуру ИЗ операций й операндов. [3]
В большинстве реализаций Снобола 4 множество цепочек литер, существующих в любой момент выполнения программы, хранится в центральной таблице цепочек. Эта таблица организована как хеш-таблица, в которой каждая позиция является указателем на связанный список группы. Чтобы проверить, принадлежит ли множеству данная цепочка X, применяется схема двойного хеширования, X хешируется дважды: для получения хеш-адреса, используемого как индекс в центральной таблице, задающий указатель на соответствующую группу, и для получения порядкового номера в группе. Каждый элемент в списке группы состоит из порядкового номера в группе и указателя на цепочку. Элементы данной группы упорядочены по порядковому номеру. Для того, чтобы определить, хранится ли X в группе, определяемой хеш-адресом X, порядковый номер X последовательно сравнивается с номерами в списке группы до тех пор, пока не произойдет совпадение или пока не будет обнаружен порядковый номер, больший чем у X В последнем случае X немедленно включается в список, в первом требуется политерное сравнение X со всеми цепочками в группе, имеющими тот же самый порядковый номер. Запрограммируйте эту схему двойного хеширования в предположении, что цепочки хранятся в последовательных блоках и имеют дескрипторы, определяющие их длину. Желательно, чтобы в запрограммированной функции в качестве входной информации использовался указатель на некоторую цепочку и чтобы функция, проверяя наличие цепочки в таблице, включала цепочку в таблицу, если ее там не оказалось, возвращала адрес прежней позиции, если цепочка уже была в таблице, или адрес новой позиции, если ее там до этого не было. [4]
Динамическая структура реализации Снобола 4 усложняется тем, что язык допускает сильную динамическую изменчивость. Необходим большой объем программного моделирования независимо от того, что взято за основу реализации - программный интерпретатор с простым транслятором или аппаратный интерпретатор с компилятором. Система, основанная на интерпретации, наиболее проста, и поэтому именно она рассматривается в настоящей главе. [5]
Различие между реализацией Снобола 4, основанной почти полностью на программном моделировании, и реализацией Фортрана, базирующейся на прямое использование аппаратуры, очевидно. [6]
Из вышесказанного должно быть ясно, что поддержание динамических системных данных в реализации Снобола 4 составляет существенную часть структуры динамической виртуальной машины. Память и время, расходуемые на работу с этими системными данными, составляют значительную долю всех расходов по выполнению программы. [7]
Ясно, что исчерпывающий поиск, необходимый для такой операции, занимает очень много времени, если STR достаточно длинна или PAT достаточно сложен. В общем случае для программиста, пишущего на Сдюболе 4, представляет интерес только успех или неудача сопоставления с образцом; поэтому желательно по возможности исключить поиск в тупиковых направлениях. Чтобы не выполнять бесполезный поиск, в реализациях Снобола 4 обычно используется ряд эвристических правил. Иногда возникают особые ситуации, когда нужен полный поиск. Программист может избрать такой режим работы, когда ему это понадобится. Кроме режима сопоставления ( закрепленного или незакрепленного) и режима поиска ( эвристического или неэвристического) операция сопоставления с образцом зависит от того, как программист построил используемый в ней образец. [8]
Во многих важных аспектах Снобол 4 отличается от других языков, рассматриваемых в этой книге. Самое очевидное отличие состоит в том, что центральное место в языке занимают данные в виде цепочек литер и соответствующая операция сопоставления с образцом ( кратко рассмотренная в разд. В Сноболе 4, как и в Лиспе, во время выполнения можно странслировать и выполнить программы, которые были построены или считаны как данные. Снобол 4 сходен с Лиспом также в повсеместном стремлении к общности и гибкости за счет снижения эффективности выполнения - на большинстве ЭВМ реализация Снобола 4 требует значительного программного моделирования. [9]
В отличие от частичного уплотнения полное уплотнение нужно трактовать как особую процедуру так же, как сбор мусора. Вычисления должны приостанавливаться на время уплотнения. Полное уплотнение обладает и другими характерными чертами процедуры сбора мусора ввиду необходимости отмечать активные элементы кучи. Вероятно, проще всего объединить оба действия, применяя единую процедуру маркировки, вслед за которой выполняется уплотнение и переустановка указателей. Одновременно отыскивается и уплотняется мусор. Такой метод используется во многих реализациях Снобола 4 и заслуживает более детального рассмотрения. [10]
В обычной реализации Снобола 4 программы транслируются в выполняемую форму, которая декодируется и выполняется программой-интерпретатором. Синтаксическая структура программ на языке Снобол 4 делает эту трансляцию относительно простой. Поскольку в языке отсутствуют ограни чители подпрограмм, декларации и структурные инструкции, каждая инструкция программы может быть странслирована без учета контекста, в котором она встречается. Поэтому можно транслировать строки программы последовательно и независимо одна от другой. Относительно позднее время связывания большинства элементов инструкций Снобола также упрощает трансляцию, поскольку во время трансляции очень мало известно об интерпретации инструкции. Таким образом, процесс трансляции сводится к выполнению простых синтаксических проверок и преобразованию каждой инструкции в блок выполняемых кодов, который в значительной степени представляет собой результат простой перекодировки исходной программы в форму, несколько более удобную для выполнения. В обычной реализации Снобола 4 эти блоки кодов имеют вид последовательности префиксных инструкций, каждая из которых состоит из символа операции и списка операндов. Операнды сами могут быть префиксными ин - j струкциями, подлежащими вычислению, так что вся программа напоминает древовидную Структуру ИЗ операций й операндов. [11]