Особенности языка Форт

Министерство образования Республики Беларусь Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет Кафедра МПУ Курсовая работа Особенности языка Форт Исполнитель:

Пахоменко А.К.

Гомель 2007

• Введение
• 1 Краткое описание языка
• 2 Работа со стёком данных
• 3 Константы, переменные и работа с памятью
• 4 Логические операции
• 5 Примеры программ
• 6 Организация диалога в Форте
• 7 Определяющие слова
• Заключение

Любой язык программирования начинается с идеи определяющей его функциональную структуру, набор команд и отличительные особенности от других языков. Главная идея языка Форт — это стёковая организация памяти. Для Форта стёк, не дополнительный вид памяти, как например, для языка Паскаль, а основной. Вспомним, что стёк это что-то вроде трубы, в которую можно бросать мячики. Мячик, который брошен последним, будет вынут первым. Чтобы вынуть десятый мячик, нужно вынуть девять первых. Это может показаться несколько сложным и неэкономичным, но давайте вспомним, что существует большой класс задач, которые легко решаются с помощью рекурсивных механизмов. А рекурсия как раз и предполагает наличие стековой памяти. Конечно, организация рекурсии не достаточно веский аргумент для создания специального языка. Существуют и достаточно обычные задачи, решение которых удобно с применением стёка. Например, попробуем упорядочить массив чисел в порядке возрастания. Для этого определим каким-либо образом процедуру ротации значений стека. При выполнении этой процедуры все значения, лежащие в стеке поднимаются на одну позицию вверх, а верхний элемент занимает место нижнего (такая операция имеется в языке Форт).

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

Ротация стека.

Взять с вершины два значения А, В

Если А>В то положить на вершину А, В Иначе положить В, А.

Примечание. Процедура ротации заключается в смещении всех элементов стёка, таким образом, что каждый элемент становится на место соседа. Например, каждый элемент занимает место предыдущего элемент, а первый становится на место последнего. Конечно, это не проще чем работа с массивами, но и не сложнее.

1. Краткое описание языка

Вычислительная модель, лежащая в основе языка Форт, состоит из адресного пространства, языка, оперативной памяти до 64 Кб, терминала и поля внешней памяти на магнитных дисках объёмом до 32 Кб блоков по 1 Кб. каждый. В пределах имеющегося адресного пространства располагаются стёк данных, словарь, буфер для ввода с терминала и буфер для обмена с внешней памятью. Примечание. Описанные выше ограничения по памяти не принципиальны. Просто в то время были такие машины. По меркам истории вычтехники ФОРТ достаточно старинный язык.

Стёк данных обычно располагается в старших адресах оперативной памяти и используется для передачи параметров и результатов между исполняемыми словами. Его элементами являются двухбайтные значения, которые в зависимости от ситуации могут рассматриваться различным образом: как целые числа со знаком в диапазоне от -32 768 до +32 767, как адреса оперативной памяти в диапазоне от 0 до 65 535, как коды литер для обмена с терминалом, как номера блоков внешней памяти в диапазоне от 0 до 32 767 или просто как 16-ти разрядные двоичные значения. В процессе исполнения слов значения перемещаются на стёк и снимаются с него. Переполнение и исчерпание стёка, как правило, не проверяется; его максимальный объём устанавливается реализацией. Стандарт предусматривает, что стёк растёт в сторону убывания адресов.

Примечание. Обратите внимание, что стёк имеет свое расположение в ОЗУ. Это означает, что не все ОЗУ есть стёк. Часть ОЗУ выделяется под различные системные потребности, и часть ОЗУ представляет собой обычную статическую память, в которой можно хранить обычные переменные. Для стековых данных понятие переменной отсутствует. Есть только понятие слова, которое может оказаться как командой, так и словом данных. Начальную часть адресного пространства обычно занимает словарь — хранилище слов и данных. По мере расширения исходного набора слов словарь растёт в сторону увеличения адресов. Специальные слова из обязательного набора позволяют управлять вершиной словаря — поднимать и опускать её.

Примечание. Поясню термин «словарь». Любой язык имеет возможности создавать подпрограммы, процедуры, функции, модули, переменные, константы и т. д. Любой из этих объектов характеризуется значением и именем. То есть, любой язык предполагает, что в процессе работы программист может создать новый объект языка имени для которого нет в языке. Вот СЛОВАРЬ Форта и занимается хранением таких новых имён.

2 Работа со стёком данных

Команды обработки стёка

DUP — дублирует верхнее значение стёка и добавляет его копию на вершину.

DROP — убирает верхнее значение стёка

OVER — дублирует значение, лежащее на стёке непосредственно под верхним.

ROT — переставляет по часовой стрелке три верхних значения стёка.

SWAP — меняет местами два верхних значения стёка.

PICK N — дублирует N-ый элемент стёка.

ROLL N — прокручивает по часовой стрелке N верхних элементов стёка.

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

Арифметические операции

+ сложение

— вычитание

* умножение

/ деление

mod остаток от деления

abs абсолютная величина числа

negate значение с обратным знаком.

Использование стёка для хранения промежуточных значений приводит к так называемой «обратной польской записи» — одному из способов бесскобочной записи арифметических выражений, подразумевающему постановку знака операции после операндов. Например, выражение (А/В + С) * (D * E — F * (G — H)) записывается следующим образом A B/C+D E * F G H — *-*.

Наряду с описанной выше 16-ти разрядной арифметикой, язык Форт имеет полный набор средств для работы с 32 — разрядными целыми числами через стандартное расширение двойной точности. Внутренним представлением таких чисел является 32 — разрядный двоичный дополнительный код, представляющий их как числа со знаком в диапазоне от -2 147 483 648 до +2 147 483 647 или как числа без знака в диапазоне от 0 до 4 294 967 295. При размещении в стёке число двойной точности занимает два элемента: верхний — старшая половина, предыдущий — младшая. Такое расположение делает простым переход от двойной точности к обычной. Расширение двойных чисел включает слова, работающие с одинарной точностью к которым добавляется цифра два: 2DROP, 2DUP и т. д. Примечание. Из сказанного выше ясно, почему в языке в принципе можно обойтись без констант и переменных. Дело в том, что программист нуждаётся в механизме обозначения используемых величин. Выдача имён переменным и константам просто один из возможных механизмов такого обозначения. Форт, тоже даёт такой механизм. Каждый элемент обозначается просто номером своего расположения в стеке. Здесь, однако, есть небольшое неудобство. А именно проблема добраться до часто используемой величиной можно только перебрав все значения стека, а это может замедлять процесс работы программы и усложнять её логику. Поэтому Форт все-таки предоставляет и механизм создания обычных переменных.

3. Константы, переменные и работа с памятью

Программисту часто бывает удобно работать не с анонимными значениями, а с именованными. По аналогии с другими языками эти средства называются константами и переменными. Слово CONSTANT, А работает следующим образом. Со стёка снимается верхнее значение, а из входного текста выбирается очередное слово и запоминается в словаре как новое очередное слово и запоминается в словаре как новая команда. Её действие состоит в следующем: поместить на стёк значение А, снятое со стёка в момент её определения. Например, 4 CONSTANT XOP. В дальнейшем при исполнении слова XOP число 4 будет положено на стёк.

Слово VARIABLE A резервирует в словаре два байта, а из входного потока выбирает очередное слово и вносит его в словарь как новую команду, которая кладёт на стёк адрес зарезервированной двухбайтной области. Можно сказать, что переменная работает как константа, значением которой является адрес зарезервированной двухбайтной области. Работа с переменной помимо получения её адреса состоит в получении текущего значения и присваивании нового. Для этого язык Форт имеет следующие слова: @ и !.

Слово @ (читается «разыменовать») снимает со стёка значение и, рассматривая его как адрес области оперативной памяти, кладёт на стёк двухбайтное значение, находящееся по этому адресу. Обратное действие выполняет слово ! (восклицательный знак, читается «присвоить»), которое снимает со стёка два значения и, рассматривая верхнее как адрес области оперативной памяти, засылает по нему второе снятое значение. Эти слова можно использовать не только для переменных, но и для любых адресов оперативной памяти. Следующий протокол работы показывает порядок использования переменной в сочетании с этими словами:

VARIABLE x 1 x !

Ok

x @ .

1 ok

x @ NEGATE x ! x @ .

— 1 ok

В первой строке определяется переменная x и ей присваивается начальное значение 1. Затем текущее значение переменной x распечатывается. После этого текущее значение меняется на противоположное по знаку и вновь распечатывается.

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

4. Логические операции

В языке Форт имеется только один тип значений — 16-ти разрядные двоичные числа, которые, рассматриваются в зависимости от ситуации как целые числа со знаком, как адреса и т. д. Точно также подходят и к проблеме представления логических значений ИСТИНА и ЛОЖЬ: число 0 в двоичном представлении которого все разряды нули, представляет значение ложь, а любое другое 16-ти разрядное значение понимается как ИСТИНА. Вместе с тем стандартные слова, которые должны в качестве результата иметь логическое значение, из всех возможных представлений значения ИСТИНА используют только одно: число -1 (или, что-то же самое, 65 535), в двоичном представлении которого все разряды единицы. Такое соглашение связано с тем, что традиционные логические операции конъюнкции, дизъюнкции и отрицания выполняются в Форте поразрядно над всеми шестнадцатью разрядами операндов:

AND — логическое И

OR — логическое ИЛИ

XOR — исключающее ИЛИ

NOT — логиечское НЕ

Нетрудно увидеть, что для принятого в Форте стандартного представления значений ИСТИНА и ЛОЖЬ все эти слова работают, как обычные логические операции.

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

< A, B —> A < B меньше

= A, B —> A = B равно

> A, B —> A > B больше

Эти операции снимают со стёка два верхних значения, сравнивают их как числа со знаком и возвращают результат сравнения как значение ИСТИНА или ЛОЖЬ в описанном выше стандартном представлении. Возврат результата означает, что на стёк ложится соответствующее целое число.

Структуры управления

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

IF A исполнение

ELSE исполнение

THEN исполнение

Внутри определения через двоеточие отрезок текста IF <�часть то> ELSE <�часть иначе> THEN задаёт следующую последовательность действий: Слово IF снимает значение с вершины стёка и рассматривает его как логическое. Если это ИСТИНА (любое не нулевое значение), то выполняется часть «ТО» — слова, находящегося между IF и ELSE, а если ЛОЖЬ (равно нулю), то исполняется часть «иначе» — слова между ELSE и THEN.

В стандарт языка Форт включены циклы с условием и циклы со счётчиком. Циклы первой группы образуются с помощью слов:

BEGIN исполнение

UNTIL A исполнение

WHILE A исполнение

REPEAT исполнение

И имеют две формы

BEGIN <�тело цикла> UNTIL

BEGIN <�тело — 1> WHILE <�тело -2> REPEAT

В обоих случаях цикл начинается словом BEGIN которое служит открывающей скобкой, отмечающей начало цикла, и во время счёта не выполняет никаких действий.

Цикл BEGIN — UNTIL называется циклом с проверкой в конце. После исполнения слов, составляющих его тело, на стёке остаётся логическое значение — условие завершения цикла. Слово UNTIL снимает это значение со стёка и анализирует его. Если это ИСТИНА, то исполнение цикла завершается, а если это ложь, то управление возвращается к началу цикла от слова BEGIN.

Цикл с проверкой в начале BEGIN — WHILE — REPEAT используется если, в цикле есть действия, которые не надо выполнять в заключительной итерации. Исполнение слов, составляющих тело — 1, оставляет на стёке логическое значение — условие продолжения цикла. Слово WHILE снимает это значение со стёка и анализирует его. Если это ИСТИНА, то исполняются слова составляющие тело — 2 данного цикла до ограничивающего слова REPEAT, после чего вновь выполняется тело — 1 от слова BEGIN. Если же значение условия ЛОЖЬ то исполнение данного цикла завершается и начинают выполняться слова, следующие за REPEAT. В отличие от предыдущей формы цикла по условию, значение ИСТИНА соответствует продолжению цикла.

Для организации циклов с целочисленной переменной — счётчиком цикла — используются слова:

DO A, B исполнение

LOOP исполнение

+LOOP A исполнение

I A исполнение

J A исполнение

LEAVE исполнение

Такие циклы записываются в одной из следующих двух форм: DO <�тело> LOOP или DO <�тело> + LOOP. В обоих случаях цикл начинается словом DO, которое снимает со стёка два значения: начальное и конечное и запоминает их. Текущее значение счётчика полагается равным начальному значению, после чего исполняются слова, составляющие тело цикла. Слово LOOP увеличивает текущее значение счётчика на единицу и проверяет условие завершения цикла. В отличие от него слово +LOOP прибавляет к текущему значению счётчика значение шага, которое вычисляется на стёке телом цикла и рассматривается как число со знаком. В обоих случаях условием завершения цикла является пересечение границы между А-1 и, А при переходе от прежнего значения счётчика к новому, где, А — конечное значение, снятое со стёка словом DO. Если пересечения не произошло, то тело цикла исполняется вновь с новым значением счётчика в качестве текущего.

Внутри тела цикла слово I кладёт на стёк текущее значение счётчика. Слово LEAVE, употреблённое внутри цикла вызывает прекращение исполнения его тела; управление переходит к словам следующим за словом LOOP или +LOOP. В программировании часто применяется конструкция цикл в цикле. Чтобы во внутреннем цикле получить текущее значение счётчика объемлющего цикла, используется слово J.

5 Примеры программ

Пример 1: Вычисление факториала

Пример 2: Вычисление наибольшего общего делителя

Пример 3: Вычисление суммы квадратов

6 Организация диалога в Форте

Из предыдущих примеров не видно, откуда машина возьмёт те числа над которыми будут выполняться действия программы. Данные как бы уже предполагаются введёнными. Дело в том, что ввод данных — это не проблема языка Форт, это проблема Форт-системы. Этот язык не есть язык программирования в чистом виде, как например язык Паскаль который работает под управлением той или иной внешней операционной системы. Форт нуждается в собственной операционной системе, которая организует пошаговый диалог с пользователем. Работа пользователя заключается во вводе фрагмента текста, который Форт система пытается интерпретировать в соответствии с несложными правилами. Она вводимый текст разделяет на команды отделяющиеся друг от друга пробелами и пытается распознать их как команды языка Форт. Если это ей не удаётся, то она пытается их распознать их как числа и положить на стёк. Если и это ей не удаётся, то Форт-система выдаёт сообщение об ошибке. Таким образом, ввод данных осуществляется как ввод внешнего текста состоящего из записи чисел раздёленных пробелами. Точно так же вводятся фрагменты форт программы, и стало быть пользователь в процессе диалога с Форт-системой сам определяет порядок обработки данных форт программами. Пользователь на каждом шаге работы программы просто вводит некоторый текст, а что этот текст из себя представляет, данные или программу решает форт-система. Это нарушает наше обычное представление о работе программы. Обычно, ввод программы и данных разделяется. Сначала полностью вводится программа, а уж затем данные. Система Форт в этом отношении намного гибче.

Пример 4: Упорядочение массива по возрастанию

Это пример, мы разберём подробно.

Выше уже было разъяснено, как организуется ввод. Поэтому договоримся о том, что перед вводом текста программы, мы уже осуществили ввод данных таким образом, что на вершине стека лежит число — количество элементов массива и под ним лежат все элементы массива.

Мы воспользуемся циклом DO. Для него на вершине стека должны лежать два значения начальное значение параметра и его конечное значение. Запишем команды, которые создадут необходимую структуру стёка.

DUP

SWAP

Запишем изменения вершины стека, которые происходят в процессе выполнения этих команд.

Команда 1: N N

Команда 2: 1 N N

Команда 3: N 1 N

Команда 4: 1 N 1 N

Таким образом, требуемая структура сформирована и можно записать заголовки цикла

DO

DO

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

2DUP

>

Первый оператор дублирует одно двойное слово или что-то же самое два одинарных, то есть дублирует на вершине стёка два значения. Затем операция «больше» снимает два значения, назовём их А, В и если, А > В то кладёт на вершину стёка единицу иначе кладёт ноль. Если на вершине стека единица, то, А и В находятся в нужном порядке и ничего делать не надо, иначе их нужно поменять местами

IF

ELSE

SWAP

THEN

Оператор IF снимает со стека 1 или 0 (результат операции сравнения), если снята единица то ничего не происходит иначе два верхних элемента, а это опять, А и В меняются местами. И теперь осталось провернуть стёк. Для этого необходимо выполнить команду N ROLL. Если N — количество элементов массива, то команда осуществит необходимый нам сдвиг стёка. Ясно, что нам опять нужно значение N, но оно было безвозвратно снято со стёка и забыто (о нём сейчас помнят только заголовки циклов). Вот тут мы сможем с пользой применить понятие переменной. Чтобы запомнить в оперативной памяти значение N мы в самом начале программы должны выполнить следующее

DUP

VARIABLE N

!

Это фрагмент дублирует значение N лежащее на стёке, следующая команда (Variable) резервирует в необходимое количество ячеек памяти и старший адрес зарезервированной области кладёт на стёк. Восклицательный знак снимает два значения со стека (адрес и значение N) и значение пересылает по адресу. Если теперь нам необходимо получить значение переменной N мы должны выполнить следующее:

N @

N — теперь воспринимается как команда языка Форт с её выполнением на стек ложится значение адреса памяти по которому хранится значение переменной. Знак собачки снимает со стека значение адреса, затем пересылает значение, взятое по этому адресу, на вершину стека и теперь мы можем выполнить команду ROLL. Она снимет со стека значение N и осуществит требуемый сдвиг массива.

И осталось завершить циклы

LOOP

LOOP

Если есть потребность просмотреть массив, необходимо вывести все элементы стека на экран циклическим повторением команды точка.

N @ (кладем на стек количество элементов массива)

1 (Кладем на стёк начальное значение параметра цикла)

DO (Снимаем со стека параметры цикла и начинаем работу)

. (Снимаем очередной элемент стека)

LOOP (Переходим к новому шагу цикла)

Запишем полученную программу целиком

(Создание переменной)

DUP

VARIABLE N

!

(Создание необходимой структуры данных для организации циклов)

DUP

SWAP

(Обработка массива)

DO

DO

2DUP

>

IF

ELSE

SWAP

THEN

N @

ROLL

LOOP

LOOP

(Вывод массива для просмотра)

N @

DO

.

LOOP

7. Определяющие слова

Тип данных это не только указание на необходимый объём памяти, но и перечень допустимых операций. Эти самые допустимые операции выглядят так очевидно, что наверное не сразу возникает идея, что допустимые операции также можно определять.

Конечно, те операции, которые приклеиваются к базовым типам, реализуются разработчиком компилятора и они для изменения недоступны, и конечно, нельзя допустить, чтобы программист — пользователь компилятора имел возможность менять код компилятора, но операцию можно реализовать и средствами самого языка высокого уровня. Это будет почти та же самая процедура или функция языка, с той лишь разницей, что она будет жёстко привязана к конкретным данным. Если таким образом к стандартному типу данных (такому как мы рассматривали в первой лекции) добавить набор процедур и функций, то получится совершенно новая языковая структура именуемая объектом. Объект хорошо тем, что в нём полностью описывается всё, что нужно для понимания его смысла, обработки, размещения в памяти, поэтому программа, построенная из объектов, становится более понятной и более прозрачной для восприятия. Такой подход широко распространён. Это сейчас называется объектным программированием, а язык Форт — это один из первых языков, где прозвучала идея объектного программирования. Правда в Форте нет терминов используемых ныне: объект, класс, инкапсуляция и т. д., но ведь это одна из первых попыток! А теперь перейдём к Форту.

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

Синтаксис определяющего слова

CREATE > СОЗДАВАЕМАЯ ЧАСТЬ

DOES > ИСПОЛНЯЕМАЯ ЧАСТЬ

Рассмотрим в качестве примера определение понятия вектор. При создании вектора будем указывать размер (число элементов), а при обращении к нему — индекс элемента, в результате чего получается адрес данного элемента. Этот адрес можно разыменовать и получить значение элемента или можно заслать по этому адресу новое значение. Если желательно контролировать правильность индекса при обращении к вектору, то определение может выглядеть так:

; Вектор CREATE DUP, 2*ALLOT

DOES >

OVER 1- OVER U< (Проверка индекса)

IF SWAP 2 * + EXIT THEN

. «Ошибка в индексе»

Рассмотрим, как работает данное определение при создании вектора 10 вектор Х.

Создающая часть компилирует размер вектора и вслед за этим отводит память на 10*2 байт. Таким образом, в словаре для вектора Х отводится размером 22 байта, в первых двух байтах хранится число 10 — размер вектора. При обращении к вектору Х на стеке должно находиться значение индекса. Слово DOES> кладёт сверху адрес области сформированной создающей частью, после чего работает исполняющая часть определения. Проверив, что индекс лежит в диапазоне между 1 и 10, она оставляет на стёке адрес, равный начальному адресу области плюс I*2 то есть адрес I — го элемента вектора, если считать, что элементы располагаются в зарезервированной области подряд. Если окажется, что индекс не положителен или больше числа элементов, то будет напечатано сообщение «Ошибка в индексе» и исполнение закончится через слово ABORT.

Заключение

Вспомним, что первые компьютеры обладали очень ограниченной памятью. Это было так не только из-за дороговизны оперативной памяти и даже не столько из-за неё, сколько из-за ограниченной возможности процессора адресовать память. Разрядность процессора налагает на величину максимального адреса очень жесткое ограничение. Если же основная масса памяти организована в виде стека, то проблема адресации уходит, так как запоминать необходимо только одну ячейку — вершину стека. Ещё одна крайне интересная особенность Форта видна в первых трёх примерах. Достаточно сложные вычислительные процессы идут совершенно без использования понятия переменной. Такая организация памяти, как уже упоминалось, существенным образом влияет на организацию подпрограмм. В некотором смысле их нет, а есть поток заданий, каждое из которых может представлять собой подпрограмму с точки зрения пользователя, чтобы понять механизм такого действа, нужно более тщательно рассмотреть работу Форт системы в целом, что уже выходит за рамки данной работы.

Вострикова З.П. и др. «Программирование на языке „БЕЙСИК“ для персональных ЭВМ». Машиностроение, 1993 г.

Гохман А.В. и др. «Сборник задач по математической логике и алгебры множеств», издательство Саратовского Университета, 1969 г.

Гусев В. В. Основы импульсной техники. М. Советское радио, 1975

Касаткин В.Н. «Информация, алгоритмы, ЭВМ», М. Просвещение, 1991 г.

Машовцев В. А. Вступительные экзамены по информатике//Информатика. 1997, № 13

Орлов В.А. О вступительных экзаменах по информатике//Информатика, 1997, № 15

Яснева Г. Г. Логические основы ЭВМ//Информатика и образование, 1998, № 2

Лыскова В.Ю., Ракитина Е. А. Логика в информатике, М. Информатика и образование 1999

Шауцкова Л.З. «Решение логических задач средствами алгебры логики», газета Информатика 1999, № 5.