?

Log in

No account? Create an account

Forth - Fj's LJ

Sep. 14th, 2006

03:16 am - Forth

Previous Entry Share Next Entry

Читаю Goedel, Escher, Bach (всё ещё), про активные символы етс, по поводу чего решил наконец написать про язык программирования Форт, потому что есть в нём что-то такое.

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

А для программистегов и программисточег - must read абсолютно точно, потому что плох тот программист, кто не мечтает написать собственный язык.

И тут же углубляюсь в необходимые детали =)

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

В ядре, то есть начальном словаре, определены слова для работы с условно-виртуальной стековой машиной (арифметические действия, drop/dup/rotate и всё такое), Слово, выдирающее следующее Слово из входного потока, Слово, создающее новую Словарную Статью для данного слова, Слово, находящее в Словаре статью с данным именем, Слово, передающее управление коду в Статье с данным именем и некоторые другие (немного, порядка сотни, с кодом килобайт эдак на 8 для 8х86, точной цифры не знаю).

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

Допустим, очередное встреченное слово было ":" (двоеточие). Это слово, получив управление, считывает следующее слово, создаёт новую словарную статью с таким именем и начинает компилировать в неё все дальнейшие слова до слова ";". "Компилировать" в простейшем случае означает вставлять инструкции вызова соответствующих слов.

В конце концов на выполнение запускается какое-нибудь слово типа "Поехали!", которое делает то, что нужно сделать. Или в интерактивном режиме пользователь даёт какие-нибудь команды. Или текущий словарь скидывается на диск.


Объединение компилятора, интерпретатора и, собственно, программы (включая необходимые данные) в одну гомогенную структуру красиво само по себе, но предоставляемые таким подходом возможности стократ интереснее.


Дело в том, что абсолютно весь код компилятора/интерпретатора, все составляющие его слова, весь служебный стек и внутренние структуры данных доступны интерпретируемой программе. Можно написать собственное слово "::", которое будет компилировать код Особым Образом (например, с оптимизацией), а можно подменить уже существующее слово ":". Более того, само стандартное слово ":" распознаёт ключевые слова, которые позволяют переходить из режима компиляции в режим интерпретации и обратно. То есть компилируемое слово может активно вмешиваться в процесс компиляции себя (учитывая текущее состояние системы) и следующих слов. Например, слово ";" завершает компиляцию, начатую словом ":", совершенно самостоятельно.

Ещё можно создать новый Словарь, введя в нём слова для ассемблера другой target machine, и перекомпилить текущий буквально парой команд.

Именно это делает форт мета-языком: мало того, что можно не включать в ядро всякие циклы, условные переходы и определение переменных, это всё прекрасно пишется, так ещё можно быстро научить систему понимать инфиксную запись математических выражений (вместо дефолтной постфиксной, вытекающей из свойств underlying стековой машины) и pascal-style объявление переменных.

Возможность подстраивать синтаксис языка под текущую задачу кажется мне Добром сама по себе, но и это ещё не всё.

Конечно, можно писать прямо на голом базовом форте как на каком-нибудь макроассемблере, воспринимая введение новых слов как объявление процедур. Можно с большим или меньшим трудом написать интерпретатор какого-нибудь С-подобного языка, после чего наслаждаться возможностью встроить в foreach автоматически генерируемый счётчик цикла, но это тоже остановка на полдороге.

Дело в том, что форт фактически предлагает другую, не побоюсь этого слова, парадигму программирования. В стандартной парадигме есть фиксированный интерпретатор, который интерпретирует программу, в которой и заключена суть алгоритма. Тут же всё наоборот - постепенно строится сложный интерпретатор, который в результате должен проинтерпретировать единственное слово "поехали!" и данные произвольной структуры. И если строить этот интерпретатор именно как интерпретатор, с постоянно меняющимся и усложняющимся интерпретируемым языком, то удаётся достичь удивительной ёмкости изложения, по крайней мере в некоторых задачах. Такое ощущение, что если в случае процедурного подхода каждая строчка увеличивает мощность программы на константу, то здесь мощность умножается на константу.

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

create ops here 2+ , 40 allot
2) определяются слова ">ops", "ops>" и "ops@", которые перемещают данные между этим конкретным стеком ops и основным стеком данных (типа >ops = push, ops> = pop, ops@ = peek)
: >ops ops @ ! 2 ops +! ;
: ops@ ops @ 2- @ ;
: ops> ops@ -2 ops +! ;
3) предполагая, что в стеке ops лежат пары "адрес операции":"приоритет" пишется слово >ops>, которое засовывает текущую операцию в этот стек, исполняя/компилируя (в зависимости от текущего состояния интерпретатора) все операции с меньшим приоритетом.
: >ops> >r begin ops@
   r@ < not while ops> drop ops>
state @ if , else execute then repeat r> drop;
(да, выглядит как КОД ИЗ АДА, не спорю. Но, наверное, можно привыкнуть. Как к регулярным выражениям, например)
4) определяется слово 2-op, которое берёт со стека приоритет, из входного потока следующее слово и переопределяет его, следующее слово, как вызов >ops> с этим приоритетом и указателем на предыдущий код этого слова, причём с аттрибутом IMMEDIATE, то есть эти новые слова всегда исполняются, даже в режиме компиляции - поскольку они, собственно, и должны компилировать/интерпретировать код. Определяется 1-op - как вызов 2-op c приоритетом 9.
: 2-op >in @ >r ' 
   r> >in ! create IMMEDIATE , ,
   >r >r r@ >ops> r> r> >ops >ops ;
: 1-op 9 2op ;
5) системе скармливается последовательность
2 2-op or     2 2-op xor    3 2-op and    4 2-op *
5 2-op <      5 2-op >      6 2-op +      6 2-op -
7 2-op *      7 2-op /      7 2-op mod
1-op not      1-op abs      1-op negate
Которая всё и переопределяет.
6) определяются круглые скобки: открывающая кладёт на стек ops ограничитель 0, закрывающая выталкивает (исполняет/компилирует) всё до ограничителя
: ( 0 >ops ; IMMEDIATE
: ) 1 >ops> ops> drop ; IMMEDIATE


Вот, собственно, и всё. Теперь код "( 2 + 3 * ( 4 + 6 ) ) / 2 " оставляет на стеке 16.
Это иллюстрирует фортопарадигменный подход, следуя которому мы во-первых ничтоже сумняшеся определяем специальные слова для доступа к определённому стеку, а во-вторых шаги 3 и 4 создают интерпретатор простенького языка, код на котором скармливается на пятом шаге.


Так, к чему я это всё. Лично мне нравятся нормальные языки, типа С#, и, хотя от возможности править синтаксис я бы не отказался, в Парадигму Форта не очень верю. Написать же интерпретатор шарпа непосредственно на форте – это довольно таки адская работа: нужно обучить его распознавать регулярные выражения и переписать лексический генератор (базовый разделяет лексеммы по пробелам), написать распознавалку БНФ и построить по ней какой-нибудь LALR парсер, написать, собственно, оптимизирующий кодогенератор, а затем придумать способы удобно вклиниваться в распознавалку БНФ и кодогенератор.
Причём делать это совершенно некому, поскольку фортопрограммеры в большинстве своём не любят контекстно-свободные грамматики, зато любят писать нитроглицериновый код (типа приведённого, одна ошибка – и привет).
Однако делать это и не нужно, поскольку если не принимать Парадигму, то можно обойтись гораздо меньшей кровью: взять компилятор шарпа и сделать только последний шаг – программируемый парсер. Я надеюсь, что кто-нибудь это сделает, причём скоро.

Тем не менее сама идея – красива безумно, на мой вкус. Оно какое-то замкнутое на себя и почти живое получается.
Это одна из вещей, про которые хочется сказать, что люди их не придумали, а открыли - типа как простые числа.

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

Я знаю слова Лисп, Хаскелл и Схема. Насколько их коннотаты похожи на Форт - не знаю.

Форт я тоже не знаю, кстати. Так, прочитал одну книжку, но зато несколько раз.

Причём тут когнитивная психология? Ну как, там Активные Символы, тут Слова, влияющие на компиляцию дальнейшего текста, фактически придающие этому тексту смысл. Можно использовать Форт в качестве источника вдохновения.

Current Music: Primordial - Cast To The Pyre (Storm Before Calm)

Comments:

[User Picture]
From:zeinul
Date:September 14th, 2006 02:05 am (UTC)
(Link)
привет.
ты в москве?
(Reply) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 14th, 2006 02:48 am (UTC)
(Link)
привет.
Нет и неопределённо долго не буду.
(Reply) (Parent) (Thread)
[User Picture]
From:zeinul
Date:September 14th, 2006 01:24 pm (UTC)
(Link)
видимо ты где-то в США...
(Reply) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 14th, 2006 07:25 pm (UTC)
(Link)
Нет, я в Латвии =)
(Reply) (Parent) (Thread)
[User Picture]
From:yurri
Date:September 14th, 2006 05:07 am (UTC)
(Link)
Ну да, т.е. программирование заменено обучением. Принципиально в итоге одно и то же, но подход разный.
(Reply) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 14th, 2006 07:28 pm (UTC)
(Link)
Принципиально это всё машины Тьюринга.

Однако удобство выражения своих мыслей разного вида у разных языков разное, как ни странно.
(Reply) (Parent) (Thread)
From:migmit
Date:September 14th, 2006 08:25 am (UTC)
(Link)
В реальной жизни, в основном, используется PostScript (диалект Форта).
Что до всего остального - ВСЕ положительные моменты Форта наличествуют в Лиспе, и большинство - в Схеме; единственное исключение - размер рантайма. В Форте рантайм минимален, в Лиспе - весьма и весьма приличный. Зато дохрена отрицательных моментов Форта в Лиспе отсутствуют - жёсткая привязка к стековой организации, например (откуда, как следствие - невозможность серьёзной оптимизации). Синтаксис Лиспа меняется в ГОРАЗДО более широких пределах, нежели синтаксис Форта (ключевое слово - макросы). Более того, стандарт Common Lisp УЖЕ содержит несколько специфических языков (например, язык форматирования строк (гораздо мощнее C-шного printf), язык описания циклов и т.п.)
Что смешно, аналогичные возможности есть, например, в C++. Это не что иное как шаблоны.
А вот Haskell - не в тему. Это удивительно красивый язык, но возможностей метапрограммирования в нём, считай, нету.
(Reply) (Thread)
[User Picture]
From:meanab
Date:September 14th, 2006 11:49 am (UTC)
(Link)
Что смешно, аналогичные возможности есть, например, в C++. Это не что иное как шаблоны.

Если хотите, то можете посмотреть тут (и в статье на которую там идет ссылка).
Разумеется, то, какие усилия приходится прилагать, чтобы добиться жалкого нечитабельного подобия Лисповских макро, немного веселит :)

(Насчет того, что PostScript - диалект Форта, это, наверное, крутовато. Так можно и C++ диалектом Алгола назвать ;)
(Reply) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 14th, 2006 07:30 pm (UTC)
(Link)
Где-то в сети валяется работающая штуковина, которая реализует на шаблонах произвольную машину Тьюринга, типа при компиляции оттуда летят ошибки undefined class или что-то такое, которые описывают текущее состояние ленты.
(Reply) (Parent) (Thread)
[User Picture]
From:primaler
Date:September 14th, 2006 05:27 pm (UTC)
(Link)
>> Возможность подстраивать синтаксис языка под текущую задачу кажется мне Добром сама по себе

WRONG


ты живёшь в удивительном мире, Володенька
(Reply) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 14th, 2006 07:38 pm (UTC)
(Link)
Мы с тобой уже на эту тему спорили, причём неоднократно.

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

У меня был на него ответ: точно так же для осознания ОО кода нужно прочитать описания используемых классов (а то и всего дерева, если у них там полиморфизм, оверлоаднутые операторы етс), да в общем для осознания чистого С со структурами тоже было бы неплохо прочитать описания структур для начала. И макросы, макросы!
Проблема поиска при правильной организации тоже решается достаточно просто, в общем ничем не отличаясь от проблемы поиска классов.

А аргументы вида "так ведь тогда можно написать ващеее нечитаемый код" мне не кажутся хоть сколько-нибудь убедительными.
(Reply) (Parent) (Thread)
From:migmit
Date:September 15th, 2006 07:11 am (UTC)
(Link)
Кста, в некоторых учебниках (по-моему, даже у Страуса) по "обычным" языкам (типа C++) встречаются фразы типа "таким образом, определяя новые функции, программист создаёт собственный язык, что облегчает ему работу с предметной областью".
(Reply) (Parent) (Thread)
[User Picture]
From:primaler
Date:September 15th, 2006 07:44 pm (UTC)
(Link)
как вы думаете, почему разрешается переопределять оператор + для собственных классов — и запрещается, например, для int'а?

ответ: потому что на плюсах прогать можно, а на форте — нет.
(Reply) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 15th, 2006 08:00 pm (UTC)
(Link)
Если бы мне было не влом, я бы взял какую-нибудь достаточно высокоуровневую прогу на шарпе и посчитал там количество доступов к объектам базовых типов (типа инта или стринга) и к теоретически оверлоадабельным. Но поскольку ответ я и так приблизительно знаю, а ошибка в пару процентов меня не очень волнует, то делать этого я не буду.

Второе: твой аргумент опять сводится к "а если дать чуваку возможность переопредилить + для интов, то он обязательно это сделает в совершенно неподходящей ситуации и пиздец". Ну да, пиздец. А если он аллокатор перепишет криво, то ваще пиздец всему, зачем же нужна такая возможность, интересно? И пойнтеры, пойнтеры тоже совершенно зря можно использовать в языке С++, ведь это какие богатые возможности открываются - хуячишь 0 в случайное место памяти в какой-нибудь невинной процедуре и всё, пиздец проекту!
(Reply) (Parent) (Thread)
[User Picture]
From:primaler
Date:September 15th, 2006 08:18 pm (UTC)
(Link)
>> "а если дать чуваку возможность переопредилить + для интов, то он обязательно это сделает в совершенно неподходящей ситуации и пиздец"

нет для этого подходящей ситуации
как нет такой ситуации, когда правильно писать по-русски неправильно

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

ну это как если бы у тебя текст модуля состоял бы внарезку из вставок на C#, перле, вба, ассемблере и руби — всё под булочкой с кунжутом в обрамлении собственного приготовления динамически подгружаемых иксемельных шаблонов

как представлю себе такой листинг, так сразу энтузиазм разбираться с фортом куда-то и улетучивается
хотя идея, конечно, красива до чёртиков
сексуальна привлекательна, я бы даже сказал
(Reply) (Parent) (Thread)
[User Picture]
From:primaler
Date:September 15th, 2006 08:20 pm (UTC)
(Link)
>> >> "а если дать чуваку возможность переопредилить + для интов, то он обязательно это сделает в совершенно неподходящей ситуации и пиздец"

>> нет для этого подходящей ситуации
>> как нет такой ситуации, когда правильно писать по-русски неправильно


я просто хотел обратить внимание общественности на тот факт, что фраза «это программа написана на форте» содержит в себе ровно ноль единиц полезной информации
(Reply) (Parent) (Thread)
From:migmit
Date:September 16th, 2006 06:24 am (UTC)
(Link)
Неверно. Она, как минимум, содержит информацию о том, что эта программа плохо поддаётся оптимизации.
(Reply) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:September 15th, 2006 09:04 pm (UTC)
(Link)
> нет для этого подходящей ситуации
Ну хууй знает. Оператор + для интов, может, переопределять и не нужно, а вот в int64 их превратить - как нехуй. Сейчас компилятор С++ это сам делает, между прочим.

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

Я тебе ещё страшнее штуку скажу: две разные плюсовые библиотеки практически наверняка будут написаны с использованием разных классов!!!111
Понимаешь, это всё вопрос привычки - что ты считаешь незыблемым.

Когда ты видишь строчку "for (int i = 0; i < n; i++)", ты в ней не знаешь значения n, плюс i может меняться внутри цикла.

Когда ты видишь строчку "foreach (Node node in someTree)", ты знаешь только то, что это какой-то перебор, наверное даже по всем узлам дерева. Конкретный вид обхода спрятан в дефолтном итераторе Tree.

Ничего особо страшного в том, что реализацию форыча тоже можно будет подправить, я не вижу. Я же буду точно знать, что она может быть подправлена! Это не станет для меня неожиданностью!

> ну это как если бы у тебя текст модуля состоял бы внарезку из вставок на C#, перле, вба, ассемблере и руби
Я тебе сейчас открою Страшную Тайну: насколько я знаю в третьем шарпе можно будет писать куски на SQL, прям в виде кода, с подсветкой, автодополнением и всем таким. А возможно и хмл с регексами тоже включат.

Ассемблерные вставки меня уже давно не пугают, как и куски unmanaged кода.

А ещё я хочу тебе напомнить Женечкену депломбную работу, в которой, конечно, код писался на шарпе, но параметры-то в результате прозрачно гонялись непосредственно между шарпокодом и шейдерами!

В самом смешивании кода ничего страшного же нет на самом деле, это удобно! Главное, чтобы можно было всё время точно знать, на чём написан именно этот кусок кода.

> фраза «это программа написана на форте» содержит в себе ровно ноль единиц полезной информации
Not true. Видишь ли, если ты знаешь, что некая программа разбирает текст регексами, ты не без оснований рассчитываешь увидеть в ней System.Text.RegularExpression.Regex, которому причём скармливаются регулярные выражения. А программа, пишущая что-нибудь в консоль, наверняка использует словосочетание Console.WriteLine, причём это именно System.Console. Я это к тому, что нормальный программер вряд ли будет писать выделение кусков из строки на скуэле, а поиск минимального элемента массива на регексах, так что используемые им суб-языки вряд ли окажутся для тебя очень уж неожиданными.
(Reply) (Parent) (Thread)
From:migmit
Date:September 16th, 2006 06:23 am (UTC)
(Link)
> как нет такой ситуации, когда правильно писать по-русски неправильно
Зачем ви тгавите?
> как если бы у тебя текст модуля состоял бы внарезку из вставок на C#, перле, вба, ассемблере и руби
Когда-то, когда я не знал слова "Лисп" я о чём-то таком мечтал. Шоп в одном файле писать, например, код работы с деревьями через C-шные указатели, критические по скорости куски оформлять ассемблером и одновременно разбирать строки регэкспами с перловским синтаксисом.
(Reply) (Parent) (Thread)
From:migmit
Date:September 16th, 2006 06:15 am (UTC)
(Link)
На форте, конечно, "прогать" нельзя, это ты (ничего, что я на "ты"?) правильно подметил. Только на плюсах тоже умеют оччень немногие. Потому что правильное программирование на форте - это то самое злосчастное изменение семантики. При помощи шаблонов.
(Reply) (Parent) (Thread)
[User Picture]
From:mantycore
Date:September 16th, 2006 12:46 pm (UTC)
(Link)
DASH.
На руби вон можно переопределить любой метод для любого класса,
в том числе и "стандартного", в том числе и + для Integer, и что? Один из удобнейших и моднейших языков.

Следовательно?
Неудобство форта заключается вовсе не в возможности оверлоадинга чего угодно.
(Reply) (Parent) (Thread)
[User Picture]
From:109
Date:October 6th, 2006 08:08 am (UTC)
(Link)
всё нормально, http://en.wikipedia.org/wiki/Language_Oriented_Programming, за этим будущее. вот, например, совершенно не экзотический, а, наоборот, мэйнстримно-коммерческий FireAnt превращает сишарпные классы в джаваскрипт, который интерпретируется в браузере (превращаясь, таким образом, в машинные коды - хорошо, если без промежуточного представления), каковые машинные коды запускаются и, в свою очередь, вызывают методы тех самых сишарпных классов (скомпилированных компилятором в IL, который, в свою очередь, скомпилирован дотнетом just-in-time в native code), с которых всё и началось.
(Reply) (Parent) (Thread)
From:(Anonymous)
Date:October 8th, 2006 08:49 pm (UTC)
(Link)
Ухты, пачетаю, спасибо.
(Reply) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:October 8th, 2006 08:54 pm (UTC)
(Link)
Разлогинило =)
(Reply) (Parent) (Thread)
[User Picture]
From:chip33
Date:September 15th, 2006 02:50 am (UTC)
(Link)
Круто. Но также наглядно показывает, почему форт не пошел. ;)
(Reply) (Thread)
[User Picture]
From:mantycore
Date:September 16th, 2006 12:39 pm (UTC)
(Link)
Бог программирует на Лиспе ;)
(Reply) (Thread)