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

       

Стек данных и вычисления


Как уже говорилось, в основе вычислительной модели для языка Форт лежит стековая машина. Ее команды (слова в языке Форт) обычно используют в качестве своих операндов верхние элементы стека, убирая их со стека и возвращая результаты (если они есть) на место операндов Как правило, слова используют одно-два верхних значения на стеке. Для их описания будем применять следующую диаграмму:

имя вершина стека до ---> вершина стека после слова исполнения слова исполнения слова

При этом считаем, что самое верхнее значение в стеке (последнее добавленное) находится справа.

Для работы с собственно вершиной стека имеются следующие слова:

DUP A ---> A,A DROP A ---> OVER A,B ---> A,B,A ROT A,B,C ---> B,C,A SWAP A,B ---> B,A

Слово DUP (от DUPLICATE — дублировать) дублирует вершину стека, добавляя в стек еще одно значение, равное тому, которое было до этого верхним. Слово DROP (сбросить) убирает верхнее значение. Слово OVER (через) дублирует значение, лежащее на стеке непосредственно под верхним. Слово ROT (от ROTATE — вращать) циклически переставляет по часовой стрелке три верхних значения в стеке. Наконец, слово SWAP (обменять) меняет местами два верхних значения.

Можно работать с любым элементом стека с помощью слов

PICK An,An-1,...Ao,n ---> An,An-1,...Ao,An ROLL An,An-1,...Ao,n ---> An-1,...Ao,An

Слово PICK (взять) дублирует n-й элемент стека (считая от нуля), так что 0 PICK равносильно DUP, а 1 PICK равносильно OVER. Слово ROLL (повернуть) циклически переставляет n верхних элементов стека (тоже считая от нуля) по часовой стрелке, так что 2 ROLL равносильно ROT, 1 ROLL равносильно SWAP, а 0 ROLL является пустой операцией.

Чтобы «увидеть» верхнее значение на стеке, используется слово . (точка) А -->, которое снимает значение с вершины стека и печатает его на терминале как целое число в свободном формате (т.е. без ведущих нулей и со знаком минус, если число отрицательное). Вслед за последней цифрой числа слово-точка выводит один пробел, чтобы выводимые подряд числа не сливались в сплошной ряд цифр.
Если программист хочет, чтобы напечатанное значение осталось на стеке, он должен исполнить текст DUP .. Слово DUP создаст копию верхнего значения, а точка ее распечатает и уберет со стека.

Перечисленные выше слова работают со значениями, уже находящимися в стеке. А как занести значение в стек? Язык Форт имеет следующее замечательное правило умолчания: если введенное слово форт-системе не известно, то прежде чем сообщать программисту об ошибке, форт-система пытается понять это слово как запись числа. Если слово состоит из одних цифр с возможным начальным знаком минус, то ошибки нет: слово считается известным и его действие состоит в том, что данное число кладется на вершину стека.

Теперь у нас достаточно средств, чтобы привести примеры диалога. Рассмотрим следующий протокол работы:

> 5 6 7 OK > SWAP . . . 6 7 5 ОК

В ответ на приглашение к вводу (знак >, печатаемый системой) программист вводит три числа: 5, 6 и 7. Обрабатывая введенный текст, форт-система кладет эти числа в указанном порядке на стек и по завершении обработки выводит подтверждающее сообщение OK и вновь приглашает программиста к вводу. Далее программист вводит текст из четырех слов: SWAP и три точки. Исполняя эти слова-команды, форт-система меняет местами два верхних элемента стека (5, 6, 7 -> 5, 7, 6) и затем поочередно три раза снимает верхнее значение со стека и печатает его. В результате на терминале появляется текст 6 7 5 и сообщение ОК, указывающее на завершение обработки, после чего система вновь выдает программисту приглашение на ввод.

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

DECIMAL ---> десятичная HEX ---> шестнадцатеричная OCTAL ---> восьмиричная

Первоначально устанавливается десятичная система. Если в процессе работы будет исполнено, например, слово HEX (от HEXADECIMAL — шестнадцатиричная), то при дальнейшем вводе и выводе чисел будет использоваться шестнадцатиричная система с цифрами от 0 до 9 и от A до F до тех пор, пока основание системы счисления не будет вновь изменено.


Внутренним же представлением чисел является обычный двоичный дополнительный код, применяемый в большинстве существующих ЭВМ.

Слова-команды, выполняющие арифметические операции над числами, являются общепринятыми математическими обозначениями:

+ A,B ---> сумма A+B - A,B ---> разность A-B * A,B ---> произведение A*B / A,B ---> частное от A/B MOD A,B ---> остаток от A/B /MOD A,B ---> остаток от A/B, частное от A/B ABS A ---> абсолютная величина A NEGATE A ---> значение с обратным знаком -A 1+ A ---> A+1 1- A ---> A-1 2+ A ---> A+2 2- A ---> A-2 2/ A ---> частное от A/2

При сложении, вычитании и умножении не учитывается возможность переполнения, в случае его возникновения используются младшие 16 разрядов результата. Такая арифметика называется арифметикой по модулю 65536 (2 в степени 16); ее основное достоинство состоит в том, что она дает одинаковые в двоичном представлении результаты независимо от того, как понимаются операнды: как числа со знаком в диапазоне от -32768 до +32767 или как числа без знака в диапазоне от 0 до 65535.

Операции деления / , MOD и /MOD рассматривают свои операнды как числа со знаком. Из нескольких известных математических определений деления с остатком (которые по-разному трактуют случаи, когда операнды имеют разные знаки или оба отрицательны) язык Форт использует так называемое деление с нижней границей: остаток имеет знак делителя или равен нулю, а частное округляется до его арифметической нижней границы («пола») []. Во многих ЭВМ, имеющих аппаратную реализацию деления, применяются другие правила для определения частного и остатка, однако это обычно не вызывает трудностей при программировании, поскольку самый важный случай с неотрицательными операндами все определения трактуют одинаково.

При выполнении деления возможно возникновение ошибочной ситуации, если делитель — нуль или частное не умещается в 16 разрядов (переполнение, возникающее при делении -32768 на -1).

Одноместные операции ABS и NEGATE игнорируют переполнение, возникающее в том единственном случае, когда операндом является число -32768, возвращая в качестве результата 0.



Наконец, одноместные операции 1+, 1-, 2+, 2- выполняют действие, отраженное в их мнемонике: увеличение или уменьшение значения на вершине стека на 1 или 2; аналогично слово 2/ возвращает частное от деления своего параметра на 2. Эти слова включены в стандарт ввиду частого использования соответствующих действий.

Использование стека для хранения промежуточных значений естественным образом приводит к так называемой «обратной польской форме» — одному из способов бесскобочной записи арифметических выражений, подразумевающему постановку знака операции после операндов. Например, выражение (A/B+C)*(D*E-F*(G-H)) записывается следующим образом: A B / C + D E * F G H - * - *. Очевидно, что этот текст выполним для Форта, если A, B и т.д. — слова, которые кладут на стек по одному числу. Таким образом, форт-систему можно использовать как калькулятор. Чтобы вычислить, например, значение (25+18+32)*5, достаточно ввести такой текст: 25 18 + 32 + 5 * .. В ответ система напечатает (исполняя точку) ответ: 375.

Чтобы повысить точность вычислений в последовательности умножение-деление, стандарт предусматривает два необычных слова:

*/ A,B,C ---> частное от (A*B/C) */MOD A,B,C ---> остаток, частное от (A*B/C)

Особенность этих слов состоит в том, что промежуточный результат А*В вычисляется с двойной точностью, и в качестве делимого для С используются все его 32 разряда. Окончательные же результаты являются 16-разрядными числами.

Наряду с описанной выше 16-разрядной арифметикой, язык Форт имеет полный набор средств для работы с 32-разрядными целыми числами через стандартное расширение двойной точности. Внутренним представлением таких чисел является 32-разрядный двоичный дополнительный код, представляющий их как числа со знаком в диапазоне от -2147483648 до +2147483647 или как числа без знака в диапазоне от 0 до 4294967295. При размещении в стеке числа двойной точности занимает два элемента: верхний — старшая половина, предыдущий — младшая.


Такое расположение делает простым переход от двойной точности к обычной через слово DROP. Расширение двойных чисел включает следующие слова:

2DROP AA ---> 2DUP AA ---> AA,AA 2OVER AA,BB ---> AA,BB,AA 2ROT AA,BB,CC ---> BB,CC,AA 2SWAP AA,BB ---> BB,AA D. AA ---> D+ AA,BB ---> сумма AA+BB D- AA,BB ---> разность AA-BB DABS AA ---> абсолютная величина AA DNEGATE AA ---> число с обратный знаком -AA

Здесь обозначение типа AA подчеркивает, что значение занимает два элемента стека. Хотя стандартное расширение этого не предусматривает, во многих реализациях языка Форт этот ряд продолжают операции умножения и деления:

D* AA,BB ---> произведенме AA*BB D/ AA,BB ---> частное от AA/BB DMOD AA,BB ---> остаток от AA/BB

Операндами и результатами перечисленных слов являются значения двойной длины, занимающие по два элемента стека каждый; это обстоятельство отражено в мнемонике, начинающейся с цифры 2, когда два элемента стека выступают как одно целое, или с буквы D (от слова DOUBLE — двойной), когда речь идет арифметическом значении двойной длины.

Следующие два слова являются переходными между арифметическими операциями одинарной и двойной точности; их мнемоника включает букву M (от слова MIX — смесь) и U (от слова UNSIGNED — беззнаковый):

UM* A,B ---> CC UM/MOD AA,B ---> C,D

Слово UM* перемножает операнды A и B как 16-разрядные числа без знака, возвращая все 32 разряда получившегося произведения. Слово UM/MOD рассматривает 32-разрядное делимое AA и 16-разрядный делитель B как числа без знака и возвращает получающиеся 16-разрядные остаток C и частное D. Если делитель нуль или частное превышает 65535, то это рассматривается как ошибка. Для перехода к двойной точности с учетом знака многие реализации имеют слово S>D  A --> AA, которое расширяет исходное число A до числа двойной точности распространением знакового разряда.

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

> 1234567. 7654321. D+ D. 8888888 ОК

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


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







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий