Язык Форт и его реализации

       

Стек возвратови реализация структур управления


Один из важных принципов языка Форт состоит в том, чтобы предоставить программисту максимальный доступ ко всем средствам его реализации. В соответствии с этим принципом собственные данные адресного интерпретатора — стек возвратов — были сделаны доступными, для чего введены специальные слова: >R A -->, R> --> А и R@ --> A. Буква R (от RETURN — возврат) в имени этих слов напоминает о том, что они работают со стеком возвратов. Все эти слова можно использовать только внутри компилируемых определений. Во время исполнения любого такого определения, представленного в шитом коде как подпрограмма верхнего уровня, на вершине стека возвратов находится адрес того места, откуда данное определение было вызвано (адрес возврата). Это значение было помещено туда действием CALL при входе в данное определение. Адрес возврата будет снят со стека возвратов и использован для продолжения интерпретации действием RETURN, составляющим семантику слова EXIT.

Перечисленные слова позволяют программисту вмешиваться в описанный механизм вызова, реализуя свои собственные схемы передач управления, и, кроме того, использовать стек возвратов для хранения временных данных в пределах одного определения (все положенные на стек возвратов значения должны быть сняты с него перед выходом из определения). Однако неосторожное манипулирование стеком возврата может вызвать непредсказуемые последствия, вплоть до разрушения форт-системы. Слово >R (читается «на эр») переносит значения с вершины стека данных на стек возвратов. Обратное действие выполняет слово R> (читается «с эр»). Слово R@ (читается «эр разыменовать») копирует вершину стека возвратов на стек данных, сохраняя это значение на стеке возвратов.

С помощью описанных слов легко определить, например, приведенное выше слово LIT, компилируемое в шитый код вместе со следующим за ним значением, чтобы во время счета положить это значение на стек данных:

: LIT ( --> A ) R@ @ R> 2+ >R ;


Во время работы данного определений слово R@ кладет на стек адрес возврата, указывающий в этот момент на следующий после адреса статьи LIT элемент в интерпретируемой последовательности адресов (см. рис. 2.4). Слово @ разыменовывает этот адрес, таким образом на стеке оказывается скомпилированное в шитый код число. Слова R> 2+ >R увеличивают адрес возврата на 2, чтобы обойти значение числа, т.е. чтобы оно не было воспринято как адрес некоторой статьи. Таким образом, в приведенном определении слова LIT реализован интересный способ передачи параметра через адрес возврата, невозможный в традиционных языках программирования.

Рассмотренные ранне структуры управления — условный оператор и циклы — также легко выражаются через эти понятия. По их образцу программист может создавать собственные структуры управления, совершенствуя свой инструментарий. Реализация условного оператора и циклов с проверкой опирается на следующие слова, аналогичные рассмотренному выше слову LIT:

: COMPILE ( ---> ) R@ @ , R> 2+ >R ; : BRANCH ( ---> ) R> @ >R ; : ?BRANCH ( A ---> ) R> SWAP IF 2+ ELSE @ THEN >R ;

Слово COMPILE (компилировать) комлилирует (т.е. добавляет) на вершину словаря значение, находящееся в шитом коде непосредственно за данной ссылкой на статью COMPILE. Слово BRANCH (переход) переустанавливает указатель интерпретации по адресу, скомпилированному вслед за данной ссылкой на статью BRANCH. Наконец, слово ?BRANCH снимает значение со стека и анализирует его: если это ЛОЖЬ (нуль), то оно работает, как BRANCH, — указатель интерпретации устанавливается по адресу, скомпилированному вслед за данной ссылкой на статью ?ВRANCH, а если это ИСТИНА (не нуль), то при интерпретации данной последовательности скомпилированный адрес перехода будет обойден. То обстоятельство, что в определении слова ?BRANCH используется условный оператор, для реализации условного оператора несущественно, потому что на практике слова BRANCH и ?BRANCH реализуются в форт-системах как подпрограммы нижнего уровня.


Приведенные определения лишь иллюстрируют выразительные возможности языка, показывая, что даже такие, самые элементарные действия можно задать машиннонезависимым способом в виде высокоуровневых определений.

Вот еще пример определения важного стандартного слова:

: LITERAL ( A ---> A/ ) STATE @ IF COMPILE LIT , THEN ; IMMEDIATE

Слово LITERAL анализирует текущее состояние текстового интерпретатора: если это компиляция, то компилирует значение, находящееся на вершине стека, как литерал в шитый код; в противном случае это значение остается на стеке.

Теперь у нас достаточно средств, чтобы выразить стандартные структуры управления, как обычные определения, через двоеточие. Например, слова для условного оператора можно определить так:

: IF ( ---> A ) COMPILE ?BRANCH HERE 2 ALLOT ; IMMEDIATE : THEN ( A ---> ) HERE SWAP ! ; IMMEDIATE : ELSE ( A1 ---> A2 ) COMPILE BRANCH HERE 2 ALLOT HERE ROT ! ; IMMEDIATE



Все эти слова имеют признак немедленного исполнения, который придается им словом IMMEDIATE, исполненным сразу после завершения каждого определения. Это означает, что данные слова будут исполняться, а не компилироваться, как остальные, во время обработки тела определений текстовым интерпретатором форт-системы.

На рис. 2.5 показана последовательность состояний словаря и стека в разные моменты обработки фрагмента A B IF C D THEN E F в теле определения через двоеточие. Эту обработку выполняет текстовый интерпретатор, находящийся в состоянии компиляции. В результате строится последовательность адресов словарных статей в соответствии с принятой техникой шитого кода.



Рис. 2.5. Компиляция условного оператора

Пусть слова A, B, ..., F являются обычными форт-словами, не имеющими признака немедленного исполнения. Тогда соответствующие им адреса будут компилироваться на вершину словаря.

Состояние I на рис. 2.5. соответствует моменту обработки непосредственно перед вводом слова IF. На вершине словаря скомпилированы адреса статей A и B и указатель вершины HERE указывает на следующий адрес.


Слово IF имеет признак немедленного исполнения, поэтому будет не скомпилировано, а исполнено.

Состояние II показывает результат исполнения слова IF. На вершину словаря скомпилирована ссылка на статью ?BRANCH, вслед за которой отведено еще 2 байта под адрес перехода, и адрес зарезервированного места сохранен на стеке данных.

Дальнейшие слова C и D будут опять компилироваться. Состояние III соответствует моменту перед вводом слова THEN.

Слово THEN, как и IF, имеет признак немедленного исполнения, поэтому будет исполняться; в результате возникнет состояние IV. В этот момент определяется адрес перехода для скомпилированной словом IF ссылки на статью ?BRANCH; это текущее значение указателя вершины словаря HERE, которое и вписывается в зарезервированные ранее 2 байта. Результат дальнейшей компиляции приводит к состоянию V.

Аналогичным образом исполняется и определение слова ELSE, которое компилирует обход части «иначе» и вписывает адрес ее начала в качестве адреса перехода для ссылки ?BRANCH. В свою очередь, адрес перехода для скомпилированного обхода будет вписан завершающим условный оператор словом THEN.

Можно повысить надежность программирования условного оператора введением контроля за соответствием слов IF, THEN и ELSE с помощью вспомогательного слова ?PAIRS:

: ?PAIRS ( A1,A2 ---> ) - ABORT" НЕПАРНЫЕ СКОБКИ" ;

которое снимает два значения со стека и, если они не равны между собой (их разность не нуль), выдает сообщение об ошибке с пояснительным текстом «Непарные скобки». Стандартное слово ABORT" (выброс и кавычка) А --> (исполнение) по своему употреблению аналогично слову ." (точка и кавычка): оно снимает значение со стека и, рассматривая его как логическое, сигнализирует об ошибке, печатая следующий за ним текст до кавычки, если это значение ИСТИНА (не нуль). Усиленные таким контролем определения слов условного оператора выглядят следующим образом:

: IF ( ---> A,1 ) COMPILE ?BRANCH HERE 2 ALLOT ; IMMEDIATE : THEN ( A,1 ---> ) 1 ?PAIRS HERE SWAP ! ; IMMEDIATE : ELSE ( A1,1 ---> A2,1 ) 1 ?PAIRS COMPILE BRANCH HERE 2 ALLOT HERE ROT ! ; IMMEDIATE



В этих определениях для контроля вместе с адресом зарезервированного места передается число 1, которое проверяется с помощью слова ?PAIRS в словах, использующих переданный адрес. Такой простой способ контроля на практике оказывается вполне достаточным. При этом программист может встроить любой другой контроль по своему желанию.

Приведенное определение условного оператора связано с реализацией стандартных слов BRANCH и ?BRANCH, выполняющих переходы в шитом коде. Из соображений эффективности эти слова обычно задают как подпрограммы нижнего уровня в машинном языке. Тогда в зависимости от архитектуры ЭВМ может оказаться предпочтительней не абсолютный, как в приведенной реализации, а относительный адрес перехода, компилируемый в шитый код сразу после ссылки на статью BRANCH или ?BRANCH. Чтобы сделать определения, использующие эти слова, машиннонезависимыми, стандарт предусматривает следующие слова для организации таких ссылок:

>MARK ---> A >RESOLVE A ---> <MARK ---> A <RESOLVE A --->

Слово >MARK (от MARK — отметить) резервирует место для ссылки вперед и оставляет адрес зарезервированного места на стеке. Слово >RESOLVE (от RESOLVE — разрешить) снимает этот адрес со стека и вписывает в него ссылку на текущую вершину словаря в соответствии с принятой реализацией переходов в шитом коде, согласованной с реализацией слов BRANCH и ?BRANCH. Аналогично слова <MARK и <RESOLVE предназначены для организации ссылок назад. Слово <MARK кладет на стек текущий адрес вершины словаря, а слово <RESOLVE компилирует ссылку на переданную точку. Окончательно определения слов условного оператора можно задать следующим образом (как они и выглядят в большинстве практических реализаций):

: IF ( ---> A,1 ) COMPILE ? BRANCH >MARK 1 ; IMMEDIATE : THEN ( A,1 ---> ) 1 ?PAIRS >RESOLVE ; IMMEDIATE : ELSE ( A1,1 ---> A2,1 ) 1 ?PAIRS COMPILE BRANCH >MARK SWAP >RESOLVE 1 ; IMMEDIATE

Аналогичным образом реализуются слова для циклов с проверкой (рис. 2.6):



: BEGIN ( ---> A,2 ) <MARK 2 ; IMMEDIATE : UNTIL ( A1,2 ---> ) 2 ?PAIRS COMPILE ?BRANCH <RESOLVE ; IMMEDIATE : WHILE ( A1,2 ---> A1,A2,3 ) 2 ?PAIRS COMPILE ?BRANCH >MARK 3 ; IMMEDIATE : REPEAT ( A1,A2,3 ---> ) 3 ?PAIRS COMPILE BRANCH SWAP <RESOLVE >RESOLVE ; IMMEDIATE

Очевидно, что реализованные таким образом стандартные структуры управления могут произвольно глубоко вкладываться друг в друга; несоответствие скобочных структур будет немедленно замечено, и программист получит сообщение об ошибке.



Рис. 2.6. Компиляция циклов

Циклы со счетчиком (рис. 2.6) реализуются аналогичным образом через вспомогательные слова (DO), (LOOP) и (+LOOP), компилируемые в шитый код вместе с адресом перехода:

: DO ( ---> A1,A2,4 ) COMPILE (DO) >MARK <MARK 4 ; IMMEDIATE : LOOP ( A1,A2,4 ---> ) 4 ?PAIRS COMPILE (LOOP) <RESOLVE >RESOLVE ; IMMEDIATE : +LOOP ( A1,A2,4 ---> ) 4 ?PAIRS COMPILE (+LOOP) <RESOLVE >RESOLVE ; IMMEDIATE

Слово (DO), с которого начинается исполнение скомпилированного цикла со счетчиком, переносит на стек возвратов следующий за ним адрес конца цикла (он нужен для немедленного выхода из цикла по слову LEAVE) и параметры данного цикла — начальное и граничное значения счетчика, снимая их с вершины стека данных. Эти значения находятся на вершине стека возвратов в течение всего времени исполнения тела цикла.

Слово (LOOP), завершающее скомпилированный цикл, продвигает текущее значение счетчика и в случае повторения цикла переводит указатель интерпретации на начало тела по скомпилированному вслед за ним адресу перехода, а при завершении цикла сбрасывает стек возвратов в исходное состояние.

Аналогично работает и слово (+LOOP), которое дополнительно снимает со стека данных значение шага цикла. Разумеется, реализация этих слов должна соответствовать принятому способу задания переходов в шитом коде. Для прямых адресов перехода соответствующие определения можно задать так:

: (DO) ( A2:ГРАНИЧНОЕ,A1:НАЧАЛЬНОЕ ---> ) R> ( A2,A1,R:ВОЗВРАТ) DUP @ >R ( ДЛЯ LEAVE) ROT >R ( ГРАНИЧНОЕ) SWAP >R ( НАЧАЛЬНОЕ) 2+ >R ( ОБОЙТИ АДРЕС В ШИТОМ КОДЕ) ) : (LOOP) ( ---> ) R> R> R@ ( R:ВОЗВРАТ,I:ТЕКУЩЕЕ,A2:ГРАНИЧНОЕ) - 0 1.


D+ ( R,I-A2+1,F:ПРИЗНАК ЗАВЕРШЕНИЯ) IF ( ЗАКОНЧИТЬ) DROP R> R> 2DROP 2+ ( ОБОЙТИ АДРЕС ) ELSE ( ПРОДОЛЖИТЬ) R@ + >R ( НОВОЕ ЗНАЧЕНИЕ СЧЕТЧИКА) @ ( АДРЕС НАЧАЛА ТЕЛА ЦИКЛА) THEN >R ;

Определение (+LOOP) выглядит аналогично.

Во всех приведенных примерах доступ к адресу возврата в шитом коде осуществляется через стек возвратов из данного определения. Этот адрес модифицируется словами 2+ или @, тем самым обеспечивая обход скомпилированной ссылки или переход по ее значению. Слова I и LEAVE, которые используются внутри тела цикла для получения текущего значения счетчика и немедленного выхода из цикла, можно задать так:

: I ( ---> A ) R> R@ SWAP >R ; : LEAVE ( ---> ) R> DROP R> DROP R> DROP ;

Для повышения быстродействия практические реализации языка Форт обычно определяют все эти слова, как и BRANCH, в виде подпрограмм нижнего уровня в машинном коде. В этом случае, например, слово I полностью эквивалентно слову R@.

Описанная реализация циклов со счетчиком через использование стека возвратов накладывает ограничения при программировании. Неосмотрительное включение слов >R, R>, R@ и EXIT в тело цикла со счетчиком может привести к непредсказуемому результату.

Вместе с тем отстутствие какого-либо контроля является еще одной характерной чертой языка Форт. Благодаря этому программист может реализовать любые конструкции (включая и средства контроля).


Содержание раздела