Forth, циклы и стек возвратов

Наверное для начала нужно уточнить для какой реализации вм идет речь

Так вроде бы циклы везде одинаково реализованы. По крайней мере у Семенова (Программирование на языке Форт / Семенов) не сказано о различиях в реализации.

А чем вызван интерес к форту?

Просто как зарядка для мозгов. К тому же он не выглядит сложным в реализации.

Если как зарядка, то советую лучше тратить время на haskell.

К тому же он не выглядит сложным в реализации.

Сложным в реализации чего? Программ или виртуальной машины? Если в реализации виртуальной машини то зарядка действительно серьезная, советую начинать с чего то более простого. Например с интерпретатора бейсика, а потом (по желанию) плавно расширить его до форта

haskell пробовал, он пока что знаний не хватает. Для меня бейсик сложнее будет реализовать. С фортом проще, если число - в стек, слово - на выполнение, иначе ошибка. :)

Бейсик сложнее? Шутишь наверно?

Чисто в плане реализации парсера и подобного. Теоретически я знаю как, но лень шевелиться. в форте попроще с этим.

Хорошо. А как ты планируешь реализовать хранение/добавление/удаление/поиск не стандартных слов?

Я если что буду писать на objc. NSMutableDictionary для новых слов, где ключ - новое слово, а объект NSArray список токенов для выполнения. Удаление через removeLastObject.

По моему в форте для словаря нужно использовать т.н. связанный список. Точно не помню почему но хешмассивом не обойтись.

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

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

NSDictionary *userDefined1= NSDictionary object:@"DUP . " forKey:@"PRINT-LAST"]
NSDictionary *userDefined2= NSDictionary object:@"DUP + . " forKey:@"PRINT-SUMMARY"];
NSMutableArray *userDefined = [NSMutableArray arrayWithObjects:userDefined1, userDefined2 nil];

Потом пройтись от конца к началу по массиву и остановиться на первом же найденном варианте.

Если надо будет стереть слово достаточно просто будет удалить элемент массива.

Точно не помню почему но хешмассивом не обойтись

Обходятся, если забить на forget.

ТС, что такое у вас «стек параметров»? Стек данных что ли? Почему вы решили, что что-то будет мешать его использовать? Читайте тут: http://www.forth.com/starting-forth/sf6/sf6.html

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

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

http://www.forth.org.ru/forth/dpans94_ru.rar (270Kb)

Русский перевод стандарта ANS FORTH 94 (выполнен Сергеем Кадочниковым)

 
...

    do-sys             do-loop структуры             определяемое реализацией

...

Зависящие-от-реализации данные, сгенерированные после начала компиляции do-loop 
структуры типа DO ... LOOP и использованные при её завершении обозначены 
символом do-sys повсюду этом Стандарте.

...

6.1.1240   DO                                                              CORE
        Интерпретация: Семантика интерпретации для этого слова не определена.

        Компиляция: ( C: -- do-sys )
            Помещает do-sys на стек потока управления. Добавляет семантику 
            времени-выполнения данную ниже к текущему определению. Семантика не 
            завершена, пока do-sys не разрешена потребителем типа LOOP.

        Время-выполнения: ( n1|u1 n2|u2 -- ) ( R: -- loop-sys )
            Устанавливает параметры управления цикла с индексом n2|u2, и 
            границей n1|u1. Неопределенная ситуация существует, если оба n1|u1 
            и n2|u2- не одного типа. Что-либо уже имеющееся на стеке возвратов 
            становится недоступным до удаления параметров управления циклом.

        См.: 3.2.3.2 Стек потока управления, 6.1.0140 +LOOP, 6.1.1800 LOOP.


6.1.1680   I                                                               CORE
        Интерпретация: Семантика интерпретации для этого слова не определена.

        Выполнение: ( -- n|u )  ( R:  loop-sys -- loop-sys )
            n|u - копия текущего (самого внутреннего) индекса цикла. 
            Неопределенная ситуация существует, если параметры управления 
            циклом недоступны.

6.1.1730   J                                                               CORE
        Интерпретация: Семантика интерпретации для этого слова не определена.

        Выполнение:( -- n|u )( R: loop-sys1 loop-sys2 -- loop-sys1 loop-sys2 )
            n|u - копия следующего-внешнего индекса цикла. Неопределенная 
            ситуация существует, если параметры управления цикла следующего-
            внешнего цикла, loop-sys1, недоступны.


6.1.1800   LOOP                                                            CORE
        Интерпретация: Семантика интерпретации для этого слова не определена.

        Компиляция: ( C: do-sys -- )
            Добавляет семантику времени-выполнения, данную ниже к текущему 
            определению. Разрешает назначения для всех неразрешенных ссылок 
            LEAVE между адресом ячейки определенным do-sys и следующим за LOOP 
            адресом ячейки для передачи управления к выполнению слова после 
            LOOP.

        Время-выполнения: ( -- )  ( R:  loop-sys1 --  | loop-sys2 )
            Неопределенная ситуация существует, если параметры управления цикла 
            недоступны. Добавляет один к индексу цикла. Если после этого индекс 
            цикла равен пределу цикла, снимает параметры цикла, и продолжает 
            выполнение непосредственно после цикла. Иначе продолжает выполнение 
            с начала цикла.

        См.: 6.1.1240 DO, 6.1.1680 I, 6.1.1760 LEAVE.

...и, если хочешь понять циклы, смотри адресную реализацию словаря и реализации слов ?BRANCH и BRANCH

Собственно, эти два слова (?BRANCH и BRANCH) - всё, что необходимо для циклов и условных операторов,
а конкретные реализации (DO ... LOOP,DO ... n +LOOP,?DO ... LOOP,BEGIN ... AGAIN,BEGIN ... UNTIL,BEGIN ... WHILE ... REPEAT,IF...ELSE...THEN,CASE ... OF ... ENDOF ... ENDCASE)
- частные примеры привычного использования, т.н. синтаксический сахар

При этом, никто не запрещает тебе придумать собственные структуры управления на их основе

При выполнении цикла, команды внутри него вообще не взаимодействуют со стеком параметров?

В классическом Forth есть «Data Stack» и «Return Stack». Что ты понимаешь, говоря «стек параметров»?

Т.е. внутри цикла создается новый стек и единственная связь между внешним стеком и внутренним происходит с помощью операторов типа I?

что такое «новый стек»?
что такое «внешний стек»?
что такое «внутренний стек»?

помощью операторов типа I

В классическом Forth оператор цикла немного нестандартно использует «Return Stack» для хранения своего счётчика. Оператор «I» умеет правильно доставать значение этого счётчика.

При выполнении цикла, команды внутри него вообще не взаимодействуют со стеком параметров?

Э... В Форте два основных стека — стек данных (просто стек) и стек возвратов. Все обычные слова работают со стеком данных, все вызовы слов из слов осуществляются через стек возвратов. Никаких кадров стека и т.п. нет.

При работе в условных циклах стеки никак не задействуются, фактически они разворачиваются в условия и переходы. При работе со стеком с параметром (DO .. LOOP) традиционно значение переменной цикла и значение окончания цикла кладутся на стек возвратов, который выполняет роль запасного стека, когда стек данных трогать нельзя. Соответственно, в цикле можно как угодно работать со стеком данных, снимать или класть значения, а переменная цикла I лезет на вершину стека возвратов. Выйти просто так по EXIT из цикла нельзя, предварительно нужно сбросить параметры цикла по команде UNLOOP.

Бейсик сложнее? Шутишь наверно?

Транслятор Бейсика НАМНОГО сложнее фортовского. Проще, чем у Форта, транслятор и ВМ придумать очень сложно. Ядро с виртмашиной в 512 байт умещали, полноценные Форт-системы от килобайта-другого размером. Бейсики же, вроде бы, килобайт от восьми начинаются :)

В классическом Forth оператор цикла немного нестандартно использует «Return Stack» для хранения своего счётчика. Оператор «I» умеет правильно доставать значение этого счётчика.

...имеются ввиду циклы типа DO ... LOOP, DO ... n +LOOP, ?DO ... LOOP и ?DO ... n +LOOP

По моему в форте для словаря нужно использовать т.н. связанный список. Точно не помню почему но хешмассивом не обойтись.

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

Точно не помню почему но хешмассивом не обойтись.

Реализация не обязана быть общепринятой. Можно сделать 100%-й стандартный Форт использую произвольную свою обвязку над словарями. В т.ч. и хешмапы.

А можно и стандартов на 100% не соблюдать. Я в JBForth делал работу с нормальными Java String вместо (addr u), отдельные структуры вместо словарных записей. И со сборкой мусора для всего этого. Так что можно было код произвольно изменять, наращивать, вычищать. Это уже не был чистый Форт с точки зрения ANS-стандартов и даже с точки зрения форт-машины, но тем не менее был всё тот же Форт с точки зрения идеологии и работы основных слов. В JBForth2 я, вообще, собирался отказываться от отдельной логики словарей, переводя её в плоскость объектов и методов, но за ненадобностью эта реализация так пока и не родилась :)

Я в JBForth делал работу с нормальными Java String вместо (addr u), отдельные структуры вместо словарных записей.

Ну, при явном различии количества битов на число (2-байта) и на символ (1-байт), (addr u) имело практическое значение. При использовании же UTF-8 или UTF-32 логика EMIT и TYPE безусловно меняется.

В JBForth2 я, вообще, собирался отказываться от отдельной логики словарей, переводя её в плоскость объектов и методов, но за ненадобностью эта реализация так пока и не родилась :)

Вообще, сложно представить, как словари и контексты смогут быть заменены объектами и методами.

Да, это стек данных. Назвал его «стек параметров», потому что читал книгу, там его называли так.

Признаться, вопрос у меня возник от неполного понимания форта.

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

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

Спасибо, я в начале не понял, зачем в цикле используется стек возвратов

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

Впереди видмо меня ждет много чудных открытий

Обязательны к прочтению книги Броуди: Starting Forth и Thinkig Forth :) На русском старые переводы очень адекватные, так как писались фортерами с душой за идею, а не за деньги :) Автора перевода первой не знаю, но ещё при СССР издавалась, у меня на бумаге. Автор второго перевода — Сергей Дмитренко.

Вторая книга, кстати, вообще любым программистам полезна. Я многие идеи и подходы из неё во всех языках практикую, даже в PHP :)

Два чая вам.