Skip to main content

Блог инженера

Блог о минимализме, инжинерии и программировании.



Введение в язык программирования Форт с использованием стековых диаграмм.

  | #Форт#программирование#unfinished

Использование Форт

Intro

Это перевод руководства An Introduction to Forth Using StackFlow. Автор написал руководство в 1994 году, опубликовал на сайте в 2004. Оно настолько базовое и простое, что я решил перевести его. С моей точки зрения - это идеальное вводное руководство как для новичка, так и для искушённого в программировании специалиста. Хотя мне трудно представить себе новичка, который решил начать программирование с Форт - хочется надеяться, если такой найдётся - он сможет начать с этого перевода.


Форт - это необычный язык программирования. Его основа - стек. В этом и сила языка и его сложность в начале изучения. Этот учебник использует графическое изображение стековых диаграмм чтобы облегчить ознакомление с Форт. Также это может быть интересно более опытным программистам.

Автор текста: Gordon Charlton – gordon@charlton.demon.co.uk

Автор перевода: Михаил Киселёв – mihail.kiselev@gmail.com

Используем интерпретатор командной строки Форт

Большую часть времени программист на Форт взаимодействует с командной строкой интерпретатора Форт. Команды языка Форт называются «словами». Ниже пример того, как организовано взаимодействие с интерпретатором Форт.

Adding

Арифметические операторы – тоже слова форта. Слово + складывает два целых числа. Слова Форт всегда разделяются пробелами. Это единственное правило грамматики языка. Последовательность команд для сложения двух чисел выглядит так:

123 456 + . [cr]  579 ok

Здесь команда [cr] это нажатие на клавишу “Ввод”. А после [cr] приводится ответ интерпретатора Форт на вводимые команды.

Точка . это тоже слово Форт, оно печатает число, находящееся на вершине стека.


В языке программирования Форт содержится множество команд для работы с целыми числами, так как исторически Форт часто используется в системах, где нет хорошей поддержки операций с плавающей точкой. Это всевозможные микроконтроллеры. Один из таких необычных операторов это */, который также называется «оператор масштабирования». Стековая диаграмма1 этого оператора ( n1 n2 n3 -- n4 ), где результат операции n4 это параметр n1 умноженный на n2 и поделённый на n3.

Adding

Чтобы проверить, как это работает, введём:

10000 355 113 */ . [cr] *31415 ok*

Кстати, дробь 355/113 даёт хорошее приближение числа Пи. Поэтому вместо использования дробного числа Пи в Форт можно использовать «оператор масштабирования» и дробь 355/113.


Строка на языке Форт может содержать больше одного слова, так что попробуем перевести градусы цельсия в градусы Фаренгейта в одну строку. Для перевода умножим градусы Цельсия на пять девятых и прибавим 32. Проверим, как это работает.

Adding

100 9 5 */ 32 + . [cr] 212 ok

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

(В качестве подсказки, для вычитания чисел используется слово -. Его стековая диаграмма такая ( n1 n2 -- n3 ), где n3 это n1-n2)


Прочитав эту главу, вы знаете почти всё об интерпретаторе Форт и изучили математические операции.

Операции со стеком

Таким образом слова вроде + and */ могут комбинироваться подобно элементам электрической сети, но иногда приходится менять порядок аргументов на стеке. Для этого используются специальные слова управляющие стеком, которые можно рассматривать как провода, соединяющие компоненты2.

Stack operations

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

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

- 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 Форт следующее:

Stack operations

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).

Stack operations

После недолгого обдумывания можно увидеть, что формулу 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.

Control structures

Вместо этого он представляет набор слов, которые можно использовать для создания управляющих структур и некоторые более мощные структуры для случаев, когда другие языки предложат вам просто использовать 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

Control structures 2

Это цикл с двумя точками выхода.


Также как устроено простое соответствие между операциями на стеке и стековыми диаграммами в Форте, работает и сооветствие между управляющими конструкциями и диаграммами потоков демонстрирующими исполнение управляющих конструкций.

Я в долгу у Вил Бадена, который ясно показал это сооветствие и использовал свои диаграммы потоков чтобы продемонстрировать это соответствие.

В следующем разделе мы посмотрим как стековые диаграммы могут использоваться совместно с диаграммами потоков и увидем простые программы использующие управляющие конструкции.


Переходим в третье измерение

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


Алгоритм Эвклида

В своей основополагающей работе «Искусство программирования» Дональд Кнут посвящает много места разбора этого алгоритма. На странице 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.


Ниже приведён код Форт для этого алгоритма (проверка на ноль выполняется до операции деления, так что аргумент “0” периодически, перебирает 0.

GCD ( n n – n ) BEGIN DUP WHILE TUCK MOD REPEAT DROP ;



Стековая диаграмма это общепринятый способ записи состояния стека Форта. Эта запись показвает, какие параметры на стеке слово ожидает и что она вернёт в результате работы. Как правило, слова форта “поглощают” свои аргументы, те они исчезают со стека, а вместо них появляются другие значения. Обычно стековая диаграмма выглдяит так:

( a b c-- d e )

Аргументы слова идут перед символом --, а результаты исполнения слова - после. В такой записи аргументы справа (в приведённом примере - e) находятся на вершине стека, а следующие - последовательно под ним. Есть соглашения о том, как обозначать аргументы на стековых диаграммах. Например n1 будет означать целое число со знаком, addr2 - адрес в памяти.

  1. Диаграмма стека (стековая диаграмма, стековый комментарий) 

  2. Очевидно, имеется в виду знакомая любому радиолюбителю макетная плата. В ней легко можно переключать провода между разными компонентами схемы. Читателя, не имеющего опыта работы с макетными платами, такая аналогия скорее запутает. 

  3. Важно понимать, что нет разделения между «интерпретатором Форт» и «компилятором Форт». В этом уникальность языка. Для него компиляция и интерпретация – это просто разные режимы работы. Команда : переключает в режим «компиляция». Есть и другие слова управляющие режимами, которыми, при необходимости можно переключать режимы. В том числе, это можно делать прямо внутри определения нового слова Форт. 

  4. Очевидно, статья писалось давно, ещё в «золотые времена» Форта. С тех пор крестовый поход, объявленный Эдсгером Дейкстрой против оператора goto ещё в 1968 году привёл к тому, что ни один из современных языков его больше не поддерживает. Сегодня тот довод, что Форт настолько мощен, что не нуждается в goto скорее вызовет улыбку у немолодых программистов и непонимание у молодых программистов. 

About Mikhail Kiselev

Photo of Mikhail Kiselev

Приветствую в моём блоге! 😄 Меня зовут Михаил. Я инженер и программист. Живу в Сибири, работаю на Сахалине, путешествую где придётся. Я предпочитаю пост в блог посту в твиттер. Описание полезной технологии или гаджета предпочитаю описанию заката или посиделок в кафе.