Cтраница 3
Центральная таблица устроена так, что в любой момент по время выполнения программы она содержит все активные в этот момент ассоциации идентификаторов независимо от того, локальные они или нет. Если принять, опять-таки для простоты, что множество всех идентификаторов, на которые ссылаются подпрограммы, может быть определено при трансляции, то при начальной установке центральной таблицы в нее следует включить по одному элементу для каждого идентификатора, независимо от числа подпрограмм, в которых встречается этот идентификатор. Каждый элемент таблицы содержит также флаг активности, указывающий, имеет ли данный идентификатор активную ассоциацию, и, кроме того, в элементе отведено место для указателя на объект ассоциации. [31]
Статическая область и стек не требуют подробных комментариев. Активационные записи подпрограмм, находящиеся в стеке, содержат значения деактивированных формальных параметров, локальных переменных и идентификаторов имен подпрограмм, поскольку для представления текущей среды ссылок используется метод центральной таблицы среды ссылок. Таким образом, стек является скрытым и не участвует непосредственно в обработке ссылок. [32]
Метка, используемая в поле перехода инструкции, может быть произвольной вычисленной цепочкой. Такая структура требует динамической таблицы, содержащей метки инструкций и указатели на позиции выполняемых кодов. Поскольку цепочки всегда заносятся в центральную таблицу цепочек, в таблице меток необходимо для каждой метки иметь указатель на элемент в таблице цепочек и указатель на позицию кода. Возможность во время выполнения транслировать в выполняемую форму новые программные элементы, содержащие метки, означает, что таблица меток может расти динамически непредсказуемым образом и поэтому должна располагаться в куче. [33]
Наиболее известная реализация Снобола 4 ( макрореализация, описанная Грисволдом [1972]) основана на моделировании виртуальной Снобол-машины полностью программными средствами. Снобол-программы транслируются только во внутреннюю выполняемую цепочку команд в префиксной польской записи, которая декодируется и выполняется программой-интерпретатором. Организация памяти во время выполнения базируется на центральной таблице цепочек литер, которая в любой момент содержит по одному элементу для каждой существующей цепочки, включая имена переменных, метки инструкций и другие идентификаторы наряду с цепочками, используемыми в качестве значений переменных и элементов массивов. Когда во время выполнения создается цепочка литер, она заносится в эту таблицу, если такой цепочки еще не существует. [34]
В обоих языках для нелокальных ссылок используется правило последней ассоциации. Считая, что для моделирования обработки нелокальных ссылок используется метод центральной таблицы, опишите, как введение новых идентификаторов влияет на структуру и использование центральной таблицы. [35]
Таблицы в языке Снобол 4 - это неоднородные линейные массивы переменного размера, для доступа к которым в качестве индексов могут использоваться не только целые числа, но и произвольные цепочки. Таким образом, таблицы представляют собой некую разновидность списка свойств. Каждый элемент таблицы состоит из индекса, являющегося указателем на цепочку в центральной таблице цепочек, и значения, которое является числом или указателем на цепочку, массив или иной элемент данных. Для создания таблиц используется примитивная функция TABLE, аргументы которой определяют начальный размер таблицы и величину приращения. [36]
Прежде чем создать базу данных со схемой типа звезды, необходимо проанализировать бизнес-правила предметной области с целью выяснения центрального вопроса, ответ на который наиболее важен. Все прочие вопросы должны быть объединены вокруг этого основного вопроса, и моделирование должно начинаться с этого основного вопроса. Данные, необходимые для ответа на этот вопрос, должны быть помещены в центральную таблицу модели - таблицу факта. [37]
Цепочка всегда представляется ссылкой на описывающий ее элемент центральной таблицы. Так, если X - простая переменная, имеющая значением цепочку ABY, то значением X будет на самом деле указатель на элемент ABY в центральной таблице. Но, кроме того, поскольку X тоже цепочка, она сама является элементом центральной таблицы. Если Y - другая переменная, значение которой - цепочка X, то значением Y будет указатель на элемент X в центральной таблице. [38]
Сразу после этого изменения в цен-тральной таблице управление передается на первую инструкцию подпрограммы ( в нашем случае это инструкция с меткой SUB), как при обычном переходе. После этого переход на одну из специальных меток RETURN, NRETURN или FRETURN сигнализирует об окончании выполнения тела подпрограммы. Из скрытого стека выбирается верхняя активационная запись, чтобы извлечь точку возврата и найти в центральной таблице все пары цепочка-значение, требующие восстановления значения. [39]
В обоих языках для нелокальных ссылок используется правило последней ассоциации. Считая, что для моделирования обработки нелокальных ссылок используется метод центральной таблицы, опишите, как введение новых идентификаторов влияет на структуру и использование центральной таблицы. [40]
В большинстве реализаций Снобола 4 множество цепочек литер, существующих в любой момент выполнения программы, хранится в центральной таблице цепочек. Эта таблица организована как хеш-таблица, в которой каждая позиция является указателем на связанный список группы. Чтобы проверить, принадлежит ли множеству данная цепочка X, применяется схема двойного хеширования, X хешируется дважды: для получения хеш-адреса, используемого как индекс в центральной таблице, задающий указатель на соответствующую группу, и для получения порядкового номера в группе. Каждый элемент в списке группы состоит из порядкового номера в группе и указателя на цепочку. Элементы данной группы упорядочены по порядковому номеру. Для того, чтобы определить, хранится ли X в группе, определяемой хеш-адресом X, порядковый номер X последовательно сравнивается с номерами в списке группы до тех пор, пока не произойдет совпадение или пока не будет обнаружен порядковый номер, больший чем у X В последнем случае X немедленно включается в список, в первом требуется политерное сравнение X со всеми цепочками в группе, имеющими тот же самый порядковый номер. Запрограммируйте эту схему двойного хеширования в предположении, что цепочки хранятся в последовательных блоках и имеют дескрипторы, определяющие их длину. Желательно, чтобы в запрограммированной функции в качестве входной информации использовался указатель на некоторую цепочку и чтобы функция, проверяя наличие цепочки в таблице, включала цепочку в таблицу, если ее там не оказалось, возвращала адрес прежней позиции, если цепочка уже была в таблице, или адрес новой позиции, если ее там до этого не было. [41]
Все ссылки в подпрограммах обрабатываются при помощи этой таблицы по описанной ранее сх ме базовый адрес смещение. Это простое вычисление пригодно в данном случае ввиду того, что текущая ассоциация для X всегда находится в одном и том же месте центральной таблицы независимо ог подпрограммы, в которой встретилась ссылка, и от того, является ли эта ссылка локальной или нет. Каждая ссылка требует только проверки флага активности в элементе таблицы, чтобы убедиться, что находящаяся в таблице ассоциация в дан ный момент активна. Применив центральную таблицу, мы достигли нашей цели - относительно эффективного выполнения операции обработки ссылки без поиска. [42]
Тот факт, что любая цепочка может быть без дополнительных указаний использована в качестве переменной и, следовательно, должна входить в текущую среду ссылок, позволяет использовать центральную таблицу цепочек также в роли центральной таблицы среды ссылок. При последующих ссылках ей может быть присвоено непустое значение или выбрано ее значение. В конце концов те цепочки, которые находятся в таблице, но недоступны из остальных мест, могут быть собраны как мусор, а занимаемая ими память может быть использована повторно. Новые цепочки всегда вносятся в центральную таблицу как глобальные переменные, поэтому на их существование не влияют последующие входы в подпрограммы и выходы из подпрограмм. [43]
Цепочка всегда представляется ссылкой на описывающий ее элемент центральной таблицы. Так, если X - простая переменная, имеющая значением цепочку ABY, то значением X будет на самом деле указатель на элемент ABY в центральной таблице. Но, кроме того, поскольку X тоже цепочка, она сама является элементом центральной таблицы. Если Y - другая переменная, значение которой - цепочка X, то значением Y будет указатель на элемент X в центральной таблице. [44]
Имя SUB вносится в динамическую таблицу имен подпрограмм. В нашем примере X и Y - это имена формальных параметров, a U и V - имена локальных переменных. Имя подпрограммы, SUB, также служит локальной переменной, значение которой возвращается в качестве результата подпрограммы. Когда во время выполнения программы вызывается подпрограмма SUB, центральная таблица цепочек таким образом модифицируется, чтобы учесть нужную для выполнения SUB среду ссылок. Сначала следует сохранить существующие на данный момент в центральной таблице значения цепочек SUB, X, Y, U и V. Они сохраняются ( вместе с точкой возврата и другими системными данными) в виде активацион-ной записи в скрытом стеке. Затем в центральную таблицу заносятся новые значения для всех этих цепочек. [45]