Forth

Forth

Forth

Семантика:	императивный
Тип исполнения:	интерпретатор/компилятор
Появился в:	1971 г.
Автор(ы):	Чарльз Х. Мур
Основные реализации:	gForth, pForth, kForth, SP-Forth[1], win32forth[2]
Диалекты:	FORTH-79, FORTH-83, ANSI FORTH 1994 года, ColorForth, RetroForth.
Испытал влияние:	АПЛ, Лисп
Повлиял на:	PostScript, Factor и другие конкатенативные языки

Форт (Forth) — язык программирования, в котором программы записываются в постфиксной записи и в стековой нотации. Поддерживает механизмы метарасширения для изменения семантики и синтаксиса языка при настройке на предметную область. Синтаксис базового уровня в Форте прост и состоит из единственного правила: «все определения разделяются пробелами». Определения Форта могут иметь любое сочетание символов.

Ряд свойств, а именно интерактивность, гибкость и простота разработки делают Форт эффективным языком в прикладных исследованиях и при создании инструментальных средств. Очевидными областями применения этого языка являются встраиваемые системы управления. За счёт простоты транслятор, а зачастую и компилятор Форта легко реализуется для подавляющего числа микроконтроллеров. Также находит применение при программировании компьютеров под управлением различных операционных систем.

История

Создание

Язык Форт был создан Чарльзом X. Муром в конце 1960-х — начале 1970-х годов. Мур назвал свой язык Fourth, считая, что это будет язык для ЭВМ четвёртого (англ. fourth) поколения. Но так как он работал на машине IBM 1130 (англ.), которая допускала имена, составленные не более чем из пяти прописных букв, название было преобразовано в FORTH (англ. forth — вперёд). Впрочем первые эксперименты Мура по созданию простого интерпретатора, облегчающего написание программ управления астрономическим оборудованием относятся ещё к концу 1950-х годов.^[3]

С 1971 года Мур работал в Национальную радиоастрономическую обсерваторию (англ.) для разработки программ сбора и обработки получаемых радиотелескопом данных. Именно тогда появилась первая реализация языка Форт. В этой работе также участвовала сотрудница Мура Элизабет Ратер (англ. Elizabeth Rather), которую можно считать вторым в мире форт-программистом.

Вновь созданный язык был принят в качестве основного языка программирования в Американском астрономическом обществе (англ.). Позднее, в 1973 году, Чарльз Мур и Элизабет Ратер основали компанию FORTH, Inc^[4], в ходе работы которой в течение следующего десятилетия язык был портирован на множество платформ.

В конце 1970-х годов программистами, заинтересованными в развитии языка была создана группа FORTH Interest Group (FIG). Этой группы разработана концепция FIG Forth Model — общедоступной форт-системы, которая может быть легко перенесена на популярные компьютерные архитектуры. Эту эталонную форт систему — FIG-FORTH, часто рассматривают как первоначальный стандарт языка.

Стандартизация

Идея официальной стандартизации форта первоначально возникла в рамках Международного объединения астрономов англ. Astronomical Sciences, AST. В мае 1977 года на встрече в Национальной обсерватории Китт-Пик (англ.) (США) был выработан глоссарий языка Форт, обозначенный как AST.01.

В феврале 1978 года в Утрехте был принят стандарт FORTH-77, ориентированный на реализацию на микрокомпьютеры.

В октябре 1979 года встреча на острове Санта-Каталина (Калифорния) закончилась разработкой стандарта FORTH-79, который распространяется на ЭВМ всех типов.

Осенью 1983 года состоялась встреча по разработке следующего стандарта, утверждённого в 1984 году как FORTH-83. Стандарт Форт-83 отличается от стандарта Форт-79 некоторыми деталями, но не по существу.

В 1988 году составе ACM была организована группа SIGFORTH^[5]; была и соответствующая Российская группа ACM (председатель — проф. С. Н. Баранов (Санкт-Петербург, СПИИРАН)). Сейчас SIGFORTH существует в составе более общей группы SIGPLAN (англ.).

Наконец в 1994 году после продолжительного согласования, в котором участвовали многие заинтересованные фирмамы был принят ANSI стандарт языка Форт.^[6]

Дальнейшее развитие и примеры использования

Известный пример успешного применения Форта — его использование в программном обеспечении глубоководного спускаемого аппарата, при поисках «Титаника» в 1985 году.

Диалект языка Форт используется в OpenBoot — базовом программном обеспечении ЭВМ на базе процессоров SPARC и PowerPC.

В начале 1980-x на основе языка Форт Джоном Уорнок и Чак Гешке из Adobe Systems создали язык PostScript^[7], широко используемый для управления устройствами печати и послуживший основой для создания формата PDF.

Существуют процессоры и контроллеры, поддерживающие вычислительную модель языка на аппаратном уровне. Создано множество открытых реализаций Форта для различных аппаратных платформ. Отдельные фирмы (среди которых следует отметить прежде всего основанную Чаком Муром FORTH, Inc и британскую компанию MicroProcessor Engineering Ltd.^[8]) поставляет различные по своим возможностям коммерческие версии языка.

Ежегодно проводятся конференции ЕвроФорт (EuroForth), в том числе в Санкт-Петербурге (Россия), Англии, Австрии, Германии, Испании, Чехии (и Чехословакии).^[9]

Основные понятия классической Форт-системы

Основная часть Форт-системы — это связный список слов, или словарь, из которого слово вызывается по имени для выполнения специфических функций. Программирование на Форте состоит в определении новых слов на основе слов, определённых в словаре ранее. Как только новые слова скомпилированы в словарь, они не отличаются по форме от слов, которые в нём уже имелись. Описание слова в словаре называется статьёй.

Структура «типичной» статьи словаря Форта:

• поле имени — содержит имя статьи (идентификатор слова) в виде строки со счётчиком, а также несколько флагов.
• поле связи — указатель на предыдущую статью.
• поле кода — указатель на код для интерпретации статьи.
• поле параметров — семантика слова (в зависимости от поля кода).

Условно статьи Форта можно разделить на две категории: низкоуровневые статьи и форт-статьи. Статьи первого типа содержат в поле кода указатель на процедуру в кодах целевого процессора, непосредственно выполняющую семантику слова. В поле параметров таких статей располагаются передаваемые процедуре параметры, либо сам её код. Форт-статьи содержат в поле параметров указатели на другие статьи, а поле кода указывает на специальную процедуру, называемую интерпретатором ссылок. На практике структура статьи зависит от реализации, но, как правило, похожа на рассмотренную выше. Принцип, используемый внутри форт-статьи, называется шитый код (англ. threaded code), а интерпретатор ссылок — виртуальной Форт-машиной.

Грамматически текст, обрабатываемый транслятором Форта, представляет собой последовательность лексем (англ. token), разделённых пробелами и символами конца строки. Транслятор входной строки выбирает очередной токен и производит его поиск в текущем словаре, причём поиск ведётся от более новых слов к старым. Если слово не найдено, предпринимается попытка интерпретировать токен в качестве записи числа, которое, в случае успеха, помещается на вершину стека. Если же токен соответствует слову Форта, анализируется текущее состояния флага compile Форт-системы. Если флаг сброшен, то слово исполняется — управление передаётся по указателю поля кода найденной статьи. Если флаг установлен, слово компилируется, то есть указатель на его поле кода дописывается в текущую создаваемую статью. Если было оттранслировано число, оно снимается со стека и компилируется в литеральный код, исполнение которого внутри словарной статьи помещает число на вершину стека. Кроме того, слова могут содержать флаг immediate («немедленный»), в этом случае они всегда исполняются.

Механизм передачи параметров между словами:

• через стек данных;
• через ячейки памяти;
• через именованные локальные переменные (стандарт 1994 года).

Язык предоставляет способ работы с памятью системы, как с линейной областью.

Обязательным компонентом системы является также стек возвратов. Доступен программно для изменения потока управления программы.

Всё вышесказанное относится к понятию Форт только в первом приближении. Форт — это не совсем язык программирования; вернее, он перекрывает понятие языка программирования. Форт в большей степени является виртуальной машиной и операционной системой ForthOS.^[10]

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

Типы кода Форта

В качестве машинного представления скомпилированной форт-программы используется тот или иной вид шитого кода.

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

При использовании шитого кода, отличающегося от подпрограммного, определения Форта, состоящие только из машинного кода, называются примитивы. В таком шитом коде часто стараются использовать основной стек процессора в качестве стека данных, а обращения к данным, лежащим на нём, в виде машинных команд pop и push.

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

Форт системы могут так же использовать байт-код, как логическое завершение развития косвенного шитого кода и свёрнутого шитого кода с адресной таблицей. В этом случае код программы (Форта) представляет собой последовательность байтов, или код некоторого придуманного виртуального процессора. Для исполнения этого кода должна существовать таблица на 256 адресов (2-байтовых, 4- или 8-байтовых), по которым расположены примитивы Форта или сложные определения.

Этот вариант сильно отличается от других видов кода и заслуживает особого внимания.

• Как и в косвенном шитом коде, примитивы Форта могут быть расположены в едином сегменте кода, защищённом от вмешательства, прошитом в ПЗУ. Примитивы зависят от конкретной платформы и могут быть выполнены в виде отдельного блока. Вся остальная часть Форта является платформонезависимой и переносимой на любую машину.
• Вокруг таблицы на 256 определений группируется отдельный словарь, лексикон, предназначенный для конкретной задачи или группы задач. Эти 256 определений занимают места не более 64К, то есть таблица может содержать 2-байтовые адреса (смещения относительно начала словаря).
• Байтовый код позволяет расширить количество определений за счет древовидной структуры словарей до любой величины, сохраняя минимальные размеры программы.
• Байтовый код может быть стандартизован. Как и для Java, такой код может быстро пересылаться по сети и исполняться на машинах с любой платформой.

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

." Привет Мир"

Пример определения слова SIGN, печатающего соответствующую фразу в зависимости от знака числа на вершине стека:

: SIGN  ( n -- )
    DUP 0> IF ." ПОЛОЖИТЕЛЬНОЕ ЧИСЛО" DROP
           ELSE 0=
             IF ." НОЛЬ"
             ELSE ." ОТРИЦАТЕЛЬНОЕ ЧИСЛО"
             ENDIF
           ENDIF ;

С учётом принятых в языке Форт норм оформления и написания, это должно быть, скорее, слово .SIGN и определяться так:

\ Напечатать знак числа
: .SIGN ( n -- )
   ?DUP 0= IF
     ." НОЛЬ"
   ELSE
     0> IF
     ." ПОЛОЖИТЕЛЬНОЕ ЧИСЛО"  ELSE
     ." ОТРИЦАТЕЛЬНОЕ ЧИСЛО"  ENDIF
   ENDIF
;

Пример реального кода, создающего строчную константу в принятом в Форт виде (со счётчиком):

\ Создать "константу" из строки
: S-CONSTANT ( c-addr u "<spaces>name" -- )
   CREATE 
     DUP , 0 ?DO
       DUP C@ C, CHAR+
     LOOP DROP 0 C,
   DOES>
     DUP CELL+ SWAP @
;

В этом примере создаётся определение слова name с помощью слова CREATE. При исполнении слова name на стек будет ложиться адрес указателя области памяти, который был во время компиляции слова. Для того, чтобы его можно было как-то использовать, туда записывается («компилируется» строка). При выполнении слова выполняются слова, указанные после слова DOES>.

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

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

Примеры таких стандартных слов:

[ — Временное переключение в режим исполнения (фактически, часто просто записывает 0 в переменную STATE).

] — Переключиться обратно в режим компиляции.

LITERAL — Компилировать число, в данный момент лежащее на вершине стека, как константу. Также является словом немедленного исполнения.

Пример кода, где используются эти слова:

\ Некоторый размер данных в килобайтах
16 CONSTANT size
 
\ Напечатать отчёт о пересчёте килобайтов в байты
: report ( -- )
   size . ."  килобайт эквивалентны "
   [ size 1024 * ] LITERAL . ." байтам"
;

Место Forth среди других языков программирования

Одна из постоянных тем споров вокруг языка Форт — это место, которое он занимает среди «классических» императивных языков. Программы на Форте имеют крайне непривычный вид:

• Программа состоит из необычной последовательности слов, среди которых отсутствуют так называемые «ключевые» слова, которые распознаются и обрабатываются, в других языках программирования, специальным образом.
  С выходом сериала «Звёздные войны» по этому поводу появилась шутка, ставшая ныне классической, которая хорошо иллюстрирует данную особенность Форта:

ЙОДЫ МАГИСТРА РЕЧИ ТАЙНА ОТКРЫТА: НА ФОРТЕ ПРОГРАММЕР СТАРЫЙ ОН ПРОСТО ЕСТЬ. Оригинальный текст (англ.)   The mistery of Yoda’s speech uncovered is: Just an old Forth programmer Yoda was.[11]

• Приведённый пример заодно указывает на уникальную особенность Форта: отсутствие списка параметров в скобках и возможность программировать на родном языке. Использование словарных конструкций родного языка позволяет сделать программу понятной, что повышает её надёжность.
• «Обратная польская запись» арифметических выражений и наличие нескольких стеков.
• Двойственная природа компилятора Форта. Нельзя утверждать однозначно, является ли Форт компилятором или интерпретатором. Практически всегда его можно использовать в двух режимах, за исключением редких случаев вроде «целевой компиляции» (трансляции в машинный код программы для системы с иной архитектурой).
• Отсутствие системы типов. Подобно многим «скриптовым» языкам, в Форте нет встроенной системы типов. Нет возможности узнать, что лежит на вершине стека — число со знаком, число без знака, указатель на строку, символ, или два числа, рассматриваемых как одно длинное число. Эта проблема разрешается двумя основными путями — использованием специальных наборов слов (например, запись и чтение ячеек памяти производят словами ! и @, а символов — словами C! и C@) и вынесением некоторых сущностей в специальные стеки (например, стек чисел с плавающей запятой, согласно стандарту ANSI FORTH 94; он может быть, а может и не быть, реализован с помощью основного стека).

Эти особенности и определяют преимущества и недостатки языка Форт:

• Простота идеи, заложенной в Форт, позволяют написать ядро Форт-системы за день.
• Свобода, предоставляемая программисту, требует сильного самоконтроля. Входной порог для программирования на Форте ниже, чем у языков типа C++, но требует привыкания и понимания не только возможностей и особенностей синтаксиса Форта, но, также, понимания философии, лежащей в его основе.
• Форт не поддерживает никакую парадигму программирования и поддерживает их все одновременно. Написать набор слов для организации ООП в программе на Форте (а их может быть одновременно несколько и они будут отлично уживаться вместе) гораздо проще, чем решить, какие возможности от этого набора слов требуются.
• Разбиение программы на множество мелких слов позволяет легко и быстро проверять их по отдельности, передавая им нужные наборы входных параметров и контролируя то, что остаётся на стеке. Фактически, это означает, что для тестирования какого-то компонента программы можно не загружать все зависимые компоненты целиком.
• Форт не скрывает ошибки. Этот факт установлен опытным путём. «Отложенные» ошибки в программе на Форте — большая редкость. Ошибки, которые, в обычных языках программирования, скрываются стандартным преобразованием типов (например, int в char в C++ (хотя большинство современных компиляторов выдаст, конечно, предупреждение) или строки в число в каком-нибудь скриптовом языке), практически мгновенно, при следующем же тестовом запуске, «обрушивают» программу.
• Форт позволяет сделать декомпиляцию программы. Полученный текст мало отличается от исходного.
• Форт позволяет реализовать любой «выкрутас» и технологию, которой овладели другие языки и системы. В то же время, он может сделать то, что не под силу другим системам. В нём допустимы приёмы, запрещённые в других языках (например — самомодификация кода). Грамотная методика использования и правильный лексикон могут устранить негативные последствия этих приёмов.
• В интерпретаторе легко реализовать все проверки на границы диапазона адресов, а это при создании ОС позволяет отказаться от защищенного режима процессора. Получается существенный выигрыш в скорости работы.
• Размер кода Форта для 16-разрядных систем, при грамотном написании программы, иногда в 10-20 раз меньше кода, скомпилированного из программы на Си. Для 32-разрядных систем этот разрыв еще больше. В операционных системах общий выигрыш может составлять уже сотни, а то и тысячи крат. Причина очень простая — готовая задача на Форте имеет размер несколько байт, все вспомогательные подпрограммы реализованы в виде определений, доступных всем. Система на Форте вместится в процессор, в который другие системы влезть в принципе не способны.
• Синхронизация процессов и потоков в многозадачных системах, переключение контекста, реализация доступа к ограниченным ресурсам — сложнейшие проблемы при написании ОС. Для поддержки этих возможностей даже создаются специальные команды в микропроцессорах. Для интерпретатора это вообще не проблема, поскольку он эмулирует любой процессор и любую необходимую команду.

Возможно, что на самом деле больше всего развитию Форта препятствует «тяжёлое наследство», пришедшее от машин с низкими возможностями, для которых он изначально создавался. В последнем стандарте (ANSI FORTH 94), существуют, например, следующие особенности:

• Переносимая программа должна предполагать, что стек чисел с плавающей запятой может быть реализован с использованием основного стека. К счастью, для большинства современных компиляторов это не так. Но сам факт наличия такого пункта в стандарте создаёт определённые неудобства. При программировании с активным использованием арифметики с плавающей точкой, эту норму стандарта традиционно игнорируют.
• Аналогичная норма существует относительно стека потока управления. Здесь всё не так просто, так как часто это именно так и есть — в процессе компиляции стек используется самим компилятором. В абсолютном большинстве случаев никакого влияния на программу это не оказывает, но про саму особенность надо помнить. Например, если вы хотите в процессе компиляции вычислить какое-то число, за пределами начала определения, а потом вставить его в слово как константу, то для этого придётся использовать какой-либо обходной путь.
• Определения многих слов в стандарте слишком низкоуровневые. Например, слово 2* производит не умножение на два, как следует из его названия, а «смещает число на один бит к старшему двоичному разряду, заполняя младший бит нулём». Конечно, на большинстве современных машин — это одно и то же, но сам факт использования особенностей конкретной архитектуры настораживает. (Существуют также более очевидные стандартные слова для сдвига битов — LSHIFT и RSHIFT.)

Многие из этих особенностей — следствие того, что на момент принятия стандарта существовало множество плохо совместимых Форт-систем, которые базировались на двух частично различающихся стандартах 79 и 83 года. В настоящий момент (июль 2009 года?) происходит обсуждение принятия европейского стандарта Форта. Перспективы этого начинания пока не ясны.

См. также

• Стандартный словарь Forth

Диалекты

• colorForth
• RetroForth
• Factor (язык программирования)

Российские программы, написанные на SPF

• Eserv (почтовый и прокси-сервер, www, ftp, nntp сервер)
• nnCron (планировщик)

Примечания

1. ↑ Проект SP-Forth на сайте SourceForge.net
2. ↑ http://win32forth.org/
3. ↑ C. H. Moore, E. D. Rather, D. R. Colburn. The Evolution of Forth. ACM SIGPLAN Notices, Volume 28, No. 3. March, 1993 / History of Programming Languages Conference (апрель 1993).
4. ↑ http://forth.com
5. ↑ 22nd EuroForth Conference
6. ↑ http://forth.sourceforge.net/standard/dpans
7. ↑ http://www.adobe.com/products/postscript/resources.html
8. ↑ http://www.mpeforth.com/
9. ↑ http://www.complang.tuwien.ac.at/anton/euroforth/
10. ↑ http://wiki.forth.org.ru/ForthOS
11. ↑ Ориджин пользователя Aquatix

Литература

• Баранов С. Н., Колодин М. Ю. Феномен форта // Системная информатика. — Новосибирск: ВО «Наука». Сибирская издательская фирма, 1995. — В. 4. — С. 193—291. — ISBN 5-02-030678-9.
• Баранов С. Н., Ноздрунов Н. Р. Язык Форт и его реализации. — Л.: Машиностроение, 1988. — 157 с. — (ЭВМ в производстве). — 100 000 экз. — ISBN 5-217-00324-3
• Броуди Л. Начальный курс программирования на Форте = Starting Forth. An introduction to the Forth language and operating system for beginners and professionals / Пер. с англ.; предисл. И. В. Романовского. — М.: Финансы и статистика, 1990. — 352 с. — 40 000 экз. — ISBN 5-279-00252-6
• Броуди Л. Способ мышления — Форт.
• Дьяконов В. П. Форт-системы программирования персональных ЭВМ. — М.: Наука, 1992. — 352 с. — ISBN 5-02-014460-6
• Келли М., Спайс Н. Язык программирования Форт / Пер. с англ. — М.: Радио и связь, 1993. — 320 с. — ISBN 5-256-00438-7
• Семёнов Ю. А. Программирование на языке Форт. — М.: Радио и связь. — 240 с. — 50 000 экз. — ISBN 5-256-00547-2
• Таунсенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ / Пер. с англ. В. А. Кондратенко, С. В. Трубицына. — М.: Финансы и статистика, 1990. — 320 с. — ISBN 5-279-00255-0 (СССР) ISBN 0-8306-2692-1 (США)
• Leo Brodie. Thinking Forth. — ISBN 0-9764587-0-5

Ссылки

• Сайт-коллекция ссылок на ресуры по Форт
• Сайт русскоязычных пользователей языка Forth
• Ссылки на Форт-ресурсы
• Web Ring Форта
• Активный Форум по языку Форт на winglion
• Форум по языку Форт на Airbase
• StasisForth — компилятор основанного на Форте низкоуровневого языка
• Fith — The Alien Language With A LIFO Grammar
• American National Standard for Information Systems Programming Languages Forth Secretariat Computer and Business Equipment Manufacturers Association(англ.)
• Русский перевод стандарта ANS FORTH 94 (выполнен Сергеем Кадочниковым, в этом переводе известны несколько ошибок, например в описании слова SEARCH)
• http://forth.ru/
• описание в wapedia.mobi
• История языка Форт(рус.)
• Сайт А.Ларионова
• Коммерческий сайт
• Конференция ЕвроФорт, есть все доклады