kt97679 Dec 27 2020 at 04:39

Сколько нужно примитивов для реализации форт системы?

3 min

+26

Comments 30

Celsius Dec 27 2020 at 09:09

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

kt97679 Dec 27 2020 at 09:17

Если нужна производительность, то вся базовая система может быть реализована на ассемблере: github.com/nornagon/jonesforth/blob/master/jonesforth.S

Celsius Dec 27 2020 at 10:39

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

Можно сделать внешний интерпретатор и интерфейс, который будет взаимодействовать с пользователем через оболочку скриптового языка (только не понятно, как и зачем), тогда придется написать интерпретаторы под разные архитектуры (x86, x64, arm, risc), форт хоть и примитивен, его легко будет реализовать, но тащить бесполезные зависимости это сомнительная идея.

kt97679 Dec 28 2020 at 08:19

Если у вас уже есть встраиваемый скриптовый язык, то зачем вам форт?

Celsius Dec 28 2020 at 09:54

В целях безопасности и переносимости. Языки в разных версиях могут быть разные, а форт всегда один.

kt97679 Dec 28 2020 at 19:36

Может быть можно встроить сам форт? Тот же sod32 можно достаточно просто интергировать в любой С проект.

sev Dec 31 2020 at 20:02

Я как-то на С делал нечто подобное. Код выложил на github: github.com/sev-/forth_sev

UFO just landed and posted this here

ultrazoom Dec 27 2020 at 15:14

… вы знаете как можно избавиться от бОльшего количества примитивов — пожалуйста напишите...

Можно, сократив набор примитивов до уровня необходимого для реализации машины Тюринга. А для этого много вообще не требуется — двух команд достаточно: Mov is Turing-Comlete

Vort123 Dec 27 2020 at 17:41

Не уверен насчёт Форта, но вообще одной команды достаточно: One-instruction set computer.

kt97679 Dec 27 2020 at 19:31

Прошу прощения, я плохо сформулировал вопрос. Меня интересует минимальное количество именно форт примитивов, через которые можно определить все остальные слова. В случае one instruction set computer мы начинаем с ассемблера, у которого всего одна команда. Для реализации форт системы нам надо написать все те же примитивы используя эту единственную команду. Это безусловно можно сделать, но эта команда не является примитивом форта. В частности, она не умеет работать со стеком.

ultrazoom Dec 28 2020 at 16:22

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

kt97679 Dec 28 2020 at 19:48

Мне кажется нет принципиальной разницы для какой платформы искать минимальный набор примитивов: для виртуальной машины на С или для Тьюринг машины. Исходно у меня было 32 примитива, я сократил их до 7. Вы пишете:

изначально вы реализуете только набор Форт-примитивов для такой минимальной машины (может двух или трёх будет достаточно)

Я не вижу как это можно сделать и с благодарностью приму любые идеи как мой набор из 7 примитивов можно сократить еще сильнее. На данный момент единственными кандидатами на мой взгляд являются слова для работы с памятью, но идей как можно тот же lit выразить через "@" и "!" у меня нет.

qw1 Dec 29 2020 at 22:08

0 можно выразить как DUP DUP XOR
1 может ещё как-то хитро?
А имея 0 и 1 арифметикой можно получить любое LIT-число.

kt97679 Dec 29 2020 at 22:15

А как положить что-то на стек, с чем будет работать dup?

qw1 Dec 30 2020 at 10:08

А есть слово, проверяющее, что стек пуст?
Я думаю, в первых Фортах (ещё на 8-битных системах), не могло быть page fault, и DUP прочитал бы хоть что-то по указателю стека. То есть, значение не определённое, но ошибки чтения нет.

kt97679 Dec 30 2020 at 20:18

Да, действительно, даже в системе с page fault можно оставить место, чтобы этот трюк сработал. Но в этом случае примитивом становится DUP. LIT можно выразить через сгенерированные числа, но количество примитивов останется тем же. Правда производительность просядет еще сильнее.

qw1 Dec 31 2020 at 01:06

Я исходил из того, что есть набор примитивов, через который выражается всё (т.е. DUP как-то выразим), и в него включен LIT. Задача избавиться от LIT

rogoz Dec 27 2020 at 20:09

Для Тюринг-полноты на x86 достаточно ноль команд.

amarao Dec 27 2020 at 23:25

Есть тонкая разница между "инструкцией процессора" и "командой Тьюринг-машины". По ссылке как раз показано, что можно сделать командны для Тьюринг-машины, используя процессор как странный конечный автомат, игнорируя при этом инструкции процессора.

Но это не отменяет того, что у них Тьюринг-машина имеет команды.

ЗЫ Тьюринг-машина без команд никогда не остановится, т.е. как вычислитель бесполезна.

nckma Dec 27 2020 at 17:45

А зачем ставить целью именно сокращение набора примитивов?
Наоборот, если система команд процессора позволяет, то желательно закодировать как можно больше команд в физические специфические команды аппаратного процессора.
Вот здесь я запускал аппаратный Forth в FPGAL habr.com/ru/post/523348

kt97679 Dec 27 2020 at 19:35

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

FForth Dec 27 2020 at 19:22

Aндрей Зубинский, 24 августа 1998 г. FORTH — вперед, в четвертое измерение компьютерных архитектур

Philip J. Koopman, Jr. Стековые компьютеры: новая волна

kt97679 Dec 27 2020 at 19:37

Странно, что среди этого набора команд нет булевских операций.

qw1 Dec 29 2020 at 22:09

Если ветвления. На псевдокоде, вместо
R := A and B;
пишем
if A then begin if B then R := 1 else R := 0 end else R := 0;

kt97679 Dec 29 2020 at 22:16

Прошу прощения, плохо сформулировал. Я имел в виду побитовые операции.

qw1 Dec 30 2020 at 10:13

Их можно выразить арифметикой.
Например, для 4-битных чисел
bit0 = bit1 = bit2 = bit3 = 0;
if (val >= 8) { bit3 = 1; val -= 8; }
if (val >= 4) { bit2 = 1; val -= 4; }
if (val >= 2) { bit1 = 1; val -= 2; }
if (val >= 1) { bit0 = 1; val -= 1; }
…
а дальше bit3..bit0 обрабатываются логикой и обратно складываются в число.

для 32-битных чисел копипасты будет побольше…

kt97679 Dec 30 2020 at 20:25

Согласен, так можно, но это означает, что нам нужно иметь в качестве примитивов операции сравнения и ветвления. У меня вот такая реализация 0BRANCH. Мне кажется, что ваш подход потребует больше примитивов?

qw1 Dec 31 2020 at 01:08

Я исходил из того, что есть набор примитивов с обычной арифметикой, но без битовых операций. Задача ввести битовые операции, не заводя новые примитивы.

shuhray Dec 27 2020 at 22:50

Переходите на Factor, мне кайф от Фактора
andreaferretti.github.io/factor-tutorial
rosettacode.org/wiki/Category:Factor
dxdy.ru/topic138111.html