Разомнем мозг при помощи Forth?

Порой возникает желание размять свой погрязший в объектно-ориентированном программировании мозг чем-то новеньким и необычным. Конечно, на помощь в этой ситуации может прийти любой функциональный язык программирования, например, Haskell, Erlang, Lisp или OCaml. Но сейчас даже ими уже вряд ли кого-то можно удивить. Нет, хочется чего-то совершенно другого. В такой ситуации на помощь к нам спешит Forth — стековый язык программирования.

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

sudo apt-get install gforth 

Все, как только мы его установили, можно запустить в терминале Форт в интерактивном режиме, выполнив команду:

gforth 

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

1 2 + 

В результате этой операции мы получим 3. Но это далеко не все особенности Форт. Изначально ядро этого языка представляет из себя некий словарь: набор слов, при помощи которых мы можем выполнять некоторый поднабор операций над данными. При этом основной единицей языка собственно и является СЛОВО. Мы можем использовать уже имеющиеся слова (DUP — дублировать лежащий на вершине стека элемент, SWAP — поменять местами два верхних элемента стека, и так далее), так и определять свои собственные. В общем то, именно определение своих слов, через имеющиеся, а затем все более новых и новых слов — это и есть основной механизм программирования на Форте.

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

Ладно, вроде бы вводная озвучена и теперь можно посмотреть на Hello world на этом языке:

." Hello world" 

Если выполнить эту команду в интерактивном режиме, то в ответ мы получим:

Hello world 

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

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

1 2 3 4 

Теперь при помощи оператора извлечения верхнего элемента со стека ("."). Мы вытащим все элементы из стека:

 . . . . 

Получим следующий вывод:

4 3 2 1 ok 

То есть мы увидели в действии принцип FILO: первый элемент, положенный в стек, был вынут из стека последним. Давайте теперь попробуем выполнить следующее арифметическое действие: (2 + 4) * 5 / 10. В результате мы должны получить 3. На Форте мы эту операцию можем записать так:

2 4 + 5 * 10 / . 

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

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

: POW DUP * . ; 

Все, мы определили собственное слово, которым можно воспользоваться вот так:

4 POW 

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

:POW DUP * . ; 

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

В Форте так же есть оператор ветвления (if) и цикл (do… loop), но их можно использовать только в определении слов. И есть одна особенность в использовании if. Давайте попробуем написать что-нибудь с использованием ветвления:

 : testif         dup 1 = if ." One" else     dup 2 = if ." Two" else     dup 3 = if ." Three"  then then then drop ; 

Кстати, Форт — регистронезависим, так что dup и DUP, это одно и то же.

Как видно из кода, каждый раз пред сравнением элемента мы делаем его копию. Это нужно из-за того, что во время сравнения элемент вынимается из стека, то есть повторно мы его уже использовать не можем. Это можно проверить, последовательно выполнив три команды:

1 2 

< 

.S 

Здесь мы сначала кладем два числа в стек, затем выполняем операцию сравнения двух верхних элементов стека. Она их вынимает, сравнивает и кладет результат в стек. Третья команда выводит все содержимое стека, которым будет одно единственное число: -1. Минус единица в Forth является булевой «истиной», а ноль — «ложью».

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

: testif      dup 1 = if ." One" else     dup 2 = if ." Two" else      3 = if ." Three" then then then ; 

то получим тот же самый результат, но этот вариант не принят, так как мы ухудшаем читаемость кода. Хоть мы и сократили код на два слова (dup и drop (удаление верхнего элемента стека)), но ухудшим читаемость.

Теперь давайте рассмотрим цикл:

 : doloop 10 0 do cr ." Some text" loop ; 

Здесь мы распечатываем текст 10 раз. Сначала мы определяем слово, затем в обратном порядке (у нас же стековый язык) указываем границы стека (10 0 do), затем выполняем некоторые действия (в нашем случае каждый раз с новой стоки выводим текст), а затем указываем, что это цикл (loop).

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

Давайте определим слово, которое бы высчитывало факториал заданного числа:

: FACTORIAL recursive dup 1 > if     dup 1 - FACTORIAL * else     drop 1 endif ;   : OURLOOP swap 1 + swap do     i . i ." ! = " i FACTORIAL . cr loop ; 

А теперь попробуем наше слово в действии в действии:

17 0 OURLOOP 

Если этот язык заинтересовал вас, то можете смело вникать в него дальше, изучая литературу и ресурсы посвященные ему. Например, я использовал для подготовки этой статьи книгу «Starting FORTH» от Leo Brodie, которая доступна в виде web-ресурса и, кстати, очень приятно читается.

Этот язык неплохо разминает мозг, раздвигает рамки представления о программировании ничуть не хуже, чем Haskell, например. Ну и напоследок шутка про Forth:

«Йоды джедаев магистра речи тайна раскрыта — на Форте просто старый программер он есть»