Использование Форт
Это перевод руководства An Introduction to Forth Using StackFlow. Автор написал руководство в 1994 году, опубликовал на сайте в 2004. Оно настолько базовое и простое, что я решил перевести его. С моей точки зрения - это идеальное вводное руководство как для новичка, так и для искушённого в программировании специалиста. Хотя мне трудно представить себе новичка, который решил начать программирование с Форт - хочется надеяться, если такой найдётся - он сможет начать с этого перевода.
Форт - это необычный язык программирования. Его основа - стек. В этом и сила языка и его сложность в начале изучения. Этот учебник использует графическое изображение стековых диаграмм чтобы облегчить ознакомление с Форт. Также это может быть интересно более опытным программистам.
Автор текста: Gordon Charlton – gordon@charlton.demon.co.uk
Автор перевода: Михаил Киселёв – mihail.kiselev@gmail.com
Используем интерпретатор командной строки Форт
Большую часть времени программист на Форт взаимодействует с командной строкой интерпретатора Форт. Команды языка Форт называются «словами». Ниже пример того, как организовано взаимодействие с интерпретатором Форт.
Арифметические операторы – тоже слова форта. Слово + складывает два целых числа. Слова Форт всегда разделяются пробелами. Это единственное правило грамматики языка. Последовательность команд для сложения двух чисел выглядит так:
123 456 + . [cr] 579 ok
Здесь команда [cr] это нажатие на клавишу “Ввод”. А после [cr] приводится ответ интерпретатора Форт на вводимые команды.
Точка . это тоже слово Форт, оно печатает число, находящееся на вершине стека.
В языке программирования Форт содержится множество команд для работы с целыми числами, так как исторически Форт часто используется в системах, где нет хорошей поддержки операций с плавающей точкой. Это всевозможные микроконтроллеры. Один из таких необычных операторов это */, который также называется «оператор масштабирования». Стековая диаграмма1 этого оператора ( n1 n2 n3 -- n4 ), где результат операции n4 это параметр n1 умноженный на n2 и поделённый на n3.
Чтобы проверить, как это работает, введём:
10000 355 113 */ . [cr] *31415 ok*
Кстати, дробь 355/113 даёт хорошее приближение числа Пи. Поэтому вместо использования дробного числа Пи в Форт можно использовать «оператор масштабирования» и дробь 355/113.
Строка на языке Форт может содержать больше одного слова, так что попробуем перевести градусы цельсия в градусы Фаренгейта в одну строку. Для перевода умножим градусы Цельсия на пять девятых и прибавим 32. Проверим, как это работает.
100 9 5 */ 32 + . [cr] 212 ok
Обратную операцию перевода из градусов Фаренгейта в градусы Цельсия можете выполнить в качестве упражнения.
(В качестве подсказки, для вычитания чисел используется слово -. Его стековая диаграмма такая ( n1 n2 -- n3 ), где n3 это n1-n2)
Прочитав эту главу, вы знаете почти всё об интерпретаторе Форт и изучили математические операции.
Операции со стеком
Таким образом слова вроде + and */ могут комбинироваться подобно элементам электрической сети, но иногда приходится менять порядок аргументов на стеке. Для этого используются специальные слова управляющие стеком, которые можно рассматривать как провода, соединяющие компоненты2.
Кроме изменения порядка чисел на стеке возможны и другие операции над ним. Они позволяют делать копии чисел на стеке или убирать их, если в будущем они не понадобятся.
Для всех этих действий в Форт есть большой выбор слов, контролирующих стек. Ниже приведены самые часто используемые слова с их стековыми диаграммами.
- SWAP ( a b -- b a )
- ROT ( a b c -- b c a )
- DUP ( a -- a a )
- OVER ( a b -- a b a )
- DROP ( a-- )
В следующем подразделе мы разберём, как использовать всю эту новую информацию.
Расширение словаря
Выше мы разобрали, как вводить команды в интерпретатор Форт и некоторые стандартные слова Форт. Теперь мы разберём, как добавлять новые слова в словарь Форт.
В добавление к тем слова, что мы уже рассмотрели Форт содержит простой компилятор, который позволяет расширять словарь языка новыми словами.
Самое важное слово для этих целей это : двоеточие. В отличие от других языков программирования, где знаки препинания, вроде: . и ; остаются знаками препинания. Они модифицируют «настоящие» команды языка. Но в Форт любой символ с пробелами до и после него – это полноценное слово-команда.
Вернёмся к предыдущему примеру перевода градусов Фаренгейта в градусы Цельсия. Для этого мы вводили в строку ввода интерпретатора3 Форт следующее:
100 9 5 */ 32 + . [cr] 212 ok
: F>C ( fahrenheit -- celsius ) 9 5 */ 32 + ;
После ввода этой строки и нажатия на клавишу «ввод» появится новое слово Форт F>C.
Попробуем проверить, как это работает.
100 F>C . [cr] 212 ok
Мы видим, что слово F>C работает как другие слова Форт.
Более сложная задача — это нахождение площади поверхности прямоугольного параллелепипеда (a), когда даны его длина (l), ширина (w) и высота (h).
После недолгого обдумывания можно увидеть, что формулу 2(l*w+l*h+w*h) можно переписать в следующем виде 2(l*(w+h)+w*h), таким образом будет меньше манипуляций со стеком.
Мы уже умеем определять слова при помощи двоеточия. Определение слова для расчёта включает некоторые новые слова для управления стеком. То, что они делают легко понять из их стековых диаграмм.
: SURFACE.AREA ( l w h--a)
2DUP * -ROT[^third] + ROT * + 2* ;
Как обычно, первое, что мы сделаем – это проверим работу слова:
3 4 5 SURFACE.AREA . [cr] 94 ok
Это правильный результат, значит слово определено верно. Но в практическом программировании используются более сложные тесты.
Управляющие конструкции
Форт – структурированный язык. Он не предусматривает конструкции GOTO. И даже не содержит скрытой опции для включения GOTO.
Вместо этого он представляет набор слов, которые можно использовать для создания управляющих структур и некоторые более мощные структуры для случаев, когда другие языки предложат вам просто использовать GOTO4.
Самые часто употребляемые управляющие конструкции Форт приведены ниже:
- IF
- ELSE
- THEN
- BEGIN
- UNTIL
- WHILE
- REPEAT
Слова IF, UNTIL и WHILE берут значение (флаг) со стека и если это значение – «ложь» (то есть не нулевое) выполняют новый цикл. То есть эти слова берут верхнее значение стека исползуют его и оно исчезает. Это называется «стековый эффект»». Другие управляющие конструкции не имеют стекового эффекта.
Эти слова можно использовать для создания таких конструкций:
- IF ... THEN
- IF ... ELSE ... THEN
- BEGIN ... UNTIL
- BEGIN ... WHILE ... REPEAT
Или даже для таких эзотерических конструкций как эта:
BEGIN ... WHILE ... WHILE ... REPEAT THEN
Это цикл с двумя точками выхода.
Также как устроено простое соответствие между операциями на стеке и стековыми диаграммами в Форте, работает и сооветствие между управляющими конструкциями и диаграммами потоков демонстрирующими исполнение управляющих конструкций.
Я в долгу у Вил Бадена, который ясно показал это сооветствие и использовал свои диаграммы потоков чтобы продемонстрировать это соответствие.
В следующем разделе мы посмотрим как стековые диаграммы могут использоваться совместно с диаграммами потоков и увидем простые программы использующие управляющие конструкции.
Переходим в третье измерение
Новые слова Форт обычно включают в себя и управляющие конструкции и слова для управления стеком. Чтобы изобразить оба этих аспекта графически придётся перейти от двухмерных диаграмм к трёхмерным. Проиллюстрируем это двумя примерами.
Алгоритм Эвклида
В своей основополагающей работе «Искусство программирования» Дональд Кнут посвящает много места разбора этого алгоритма. На странице 2 тома 1 он объясняет это следующим образом.
Алгоритм E. (Алгоритм Эвклида): пусть дано два положительных целых числа m и n , нужно найти их наибольший общий делитель (НОД). То есть самое большое положительное целое число, на которое делятся [без остатка] оба числа m и n.
Шаг E1. [Найти остаток от деления.] Разделите m на n и пусть r будет остатком от деления. (r находится в диапазоне 0<=r<n.)
Шаг E2. [Проверка на ноль?] Если r = 0, алгоритм прерывается; n - это ответ.
Шаг E3. [Обмен.] Установите m <- n, n <- r , и вернитесь к шагу E1.
Ниже приведён код Форт для этого алгоритма (проверка на ноль выполняется до операции деления, чтобы избежать деления на ноль).
: GCD ( n n -- n ) BEGIN DUP WHILE TUCK MOD REPEAT DROP ;
Комбинации
Существует множество алгоритмов, которые находят количество комбинаций из r элементов от n объектов (nCr). Чаще всего упоминаются алгоритмы:
n!/r!(n-r)!
и теорема Вандермонда
nCr = nC(r-1) + (n-1)Cr
У первого алгоритма проблема заключается в том, что промежуточные результаты вычислений выражаются большими числами даже при малых n и r. Второй алгоритм лишён этого недостатка, но он крайне вычислительно неэффективен.
Следовательно мы выбрали третий алгоритм, который не страдает от обеих этих недостатков.
r = 0 --> nCr = 1
r > 0 --> nCr = nC(r-1)(n-r+1)/r
Это может быть выражено следующим кодом на языке Форт
: (COMBS) ( n r--c) DUP IF 2DUP 1- RECURSE
-ROT TUCK - 1+
SWAP */
ELSE 2DROP 1
THEN ;
Где слово RECURSE означает рекурсивное5 определение.
Можно улучшить код, если заметить, что функция симметрична. То есть nCr = nC(n-r), так что можно уменьшить количество вычислений если заранее решить, что меньше r или (n-r). Поэтому мы вызываем слово COMBS из другого слова, которое и делает эту проверку. Разумеется, сначала нужно протестировать правильную работу слова (COMBS).
: COMBS ( n r--c) 2DUP - MIN (COMBS) ;
Этим завершим введение в использование языка Форт. В последнем разделе мы упомянем некоторые аспекты Форт не упомянутые здесь и дадим некоторые ссылки на другие источники информации про Форт.
-
Диаграмма стека (стековая диаграмма, стековый комментарий)
Стековая диаграмма это общепринятый способ записи состояния стека Форта. Эта запись показвает, какие параметры на стеке слово ожидает и что она вернёт в результате работы. Как правило, слова форта “поглощают” свои аргументы, те они исчезают со стека, а вместо них появляются другие значения. Обычно стековая диаграмма выглдяит так:
( a b c– d e )
Аргументы слова идут перед символом--, а результаты исполнения слова - после. В такой записи аргументы справа (в приведённом примере - e) находятся на вершине стека, а следующие - последовательно под ним. Есть соглашения о том, как обозначать аргументы на стековых диаграммах. Например n1 будет означать целое число со знаком, addr2 - адрес в памяти. ↩ -
Очевидно, имеется в виду знакомая любому радиолюбителю макетная плата. В ней легко можно переключать провода между разными компонентами схемы. Читателя, не имеющего опыта работы с макетными платами, такая аналогия скорее запутает. ↩
-
Важно понимать, что нет разделения между «интерпретатором Форт» и «компилятором Форт». В этом уникальность языка. Для него компиляция и интерпретация – это просто разные режимы работы. Команда
:переключает в режим «компиляция». Есть и другие слова управляющие режимами, которыми, при необходимости можно переключать режимы. В том числе, это можно делать прямо внутри определения нового слова Форт. ↩ -
Очевидно, статья писалось давно, ещё в «золотые времена» Форта. С тех пор крестовый поход, объявленный Эдсгером Дейкстрой против оператора goto ещё в 1968 году привёл к тому, что ни один из современных языков его больше не поддерживает. Сегодня тот довод, что Форт настолько мощен, что не нуждается в goto скорее вызовет улыбку у немолодых программистов и непонимание у молодых программистов. ↩
-
Слово ‘RECURSE’ показывает, что форт-слово, определённое двоеточием в котором встречается слово RECURSE вызывается рекурсивно. Имя определения не используется, пока солово не будет выполнено (то есть до завершающих точки с запятой) это имя не встречается в словаре форт-слов. ↩
