Язык программирования (и ОС) ФОРТ (FORTH) Виртуальный стековый процессор FVM (виртуальная машина)

S050: Краткое описание FVM

--------------------------------------------------------------------------------
Для изучения ассемблера самым лучшим вариантом будет написать эмулятор компьютера

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

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

данных и алгоритмов, машинную графику и т.п. 

С точки зрения просты написания ассемблера/компилятора для начала лучше всего

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

написать кросс-компилятор на Форте. 

Я приведу код интерпретатора (движка) только на С, так как этот язык на самом

деле как раз и предназначен для написания таких низкоуровневых вещей. Прикладные


программы нужно писать на более высокоуровневых языках, хотя бы на Pythonе, а

лучше всего освоить Haskell, Sheme, OCaml. 

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

или ассемблере, ввести дополнительные команды, написать движок для 
малораспространенной операционной системы или сам работающий как операционная

система напрямую с аппаратурой вашего компьютера. 

S051: Модель аппаратных стеков и регистров

--------------------------------------------------------------------------------

Основная память
Размер памяти 64 Kb зададим с помощью директивы препроцессора #define 
#define Msz 0x10000

Определяем байтовый (байту в С соответствует тип char) массив размером Msz: 
char M[Msz];

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

char bfetch(uint addr)             { return M[addr]; }
void bstore(uint addr, int n)      { M[addr]=n; }

// 16-битные числа

short int wfetch(uint addr)        { return M[addr+0]|M[addr+1]<<8; }
void wstore (uint addr, int n)     { M[addr+0]=n; M[addr+1]=n>>8; }

(тип uint задан как короткая запись unsigned int с помощью директивы 
препроцессора). 
Обратите внимание, что 16- и 32-битные числа хранятся в памяти в порядке, когда

младший байт числа находится в памяти по млдадшему адресу (порядок байт в 
процессорах 80x86). Чтобы не привязываться к порядку байт, мы чтение и запись

памяти мы выполняем побайтно. Для разбора чисел на байты и сборки чисел из байт

мы используем битовые операции С(++). 


Стек возвратов
Используется для хранения адресов возврата из вложенных вызовов (шитый код).


#define Rsz 0x100

Используем простейший вариант стека -- массив для данных и указатель (индекс

первого свободного элемента массива): 

uint R[Rsz]; uint Rp=0;


Стек данных

#define Dsz 0x10

 int D[Dsz]; uint Dp=0;


S052: Байт-код

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

тип 0op опкод байт 
тип 1op опкод байт 
    константа cell (машинное слово) 

uint op;       // опкод
uint Ip=0;     // указатель команд


S053: Выполнение одной команды

--------------------------------------------------------------------------------

void step()
{

Перед выполнение каждой команды необходимо проверить корректность регистров --
не 
одно значение указателя не должно выходить за границы массивов. Для каждой 
команды проверяется указатель команд и переполнение/исчерпание стеков. Остальные

проверки делаются внутри функций, реализующих команды ВМ (проверка адресов при

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

     assert(Ip vm program
// # vm program

int main(int argc, char *argv[])
{
     // проверка корректности командной строки
     // (должно быть задано имя файла с байт-кодом)
     assert(argc>1);
     // загрузка байт-кода из файла
     FILE *img=fopen(argv[1],"rb"); assert(img!=NULL);
     assert(fread(M,1,Msz,img)!=NULL); fclose(img);
     // запускаем планировщик задач
     sheduler();
     // фиктивный return чтобы компилятор не ругался что нужно возвращать int
     return 0;
}


S056: Команды стековой машины

--------------------------------------------------------------------------------

команды, используемые в управляющих конструкциях
0x00 0op nop                  \ пустая команда

Пустая команда -- я использовал в движке пустую процедуру, но можно просто 
игнорировать команду байт-кода 0x00. 

void nop()     {}

// step() switch(op):

     case 0x00: nop(); break;

0x01 1op jmp                  \ переход

Безусловный переход по адресу, скомпилированному сразу после опкода. 
void jmp()     { Ip=M[Ip]; }

0x02 1op ?jmp                 \ ( flag -- ) переход если flag=0
0x03 1op call                 \ вызов
0x04 0op ret                  \ возврат

0x05 1op lit   : # lit ;      \ ( -- n ) литерал (поместить в стек константу)

Команда lit используется для компиляции констант -- при ее выполнении константа

помещается в стек данных 

void lit()     { D[Dp++]=M[Ip++]; }

Для циклов со счетчиком используются специализированные команды FVM: 
0x08 0op do
0x09 0op loop
0x0A 0op i
0x0B 0op j
0x0C 0op k

Для хранения параметров циклов используется стековая структура данных: 
struct {
     uint addr;          // адрес первой команды после do
     int count,to;       // счетчик цикла, конечное значение
} L[Lsz]; uint Lp=0;

Команда do 
void zdo()     { assert(Lp
0x42 0op =
0x43 0op !=
0x44 0op not                  \ ( n -- ~n ) побитовая инверсия n
0x45 0op or                   \ ( n1 n2 -- n1|n2 )
0x46 0op and                  \ ( n1 n2 -- n1&n2 )
0x47 0op xor                  \ ( n1 n2 -- n1^n2 )
0x48 0op <<                   \ ( n i -- n<>                   \ ( n i -- n>>i) побитовый сдвиг вправо

ввод/вывод
0x50 0op key                  \ ( -- char ) ввод символа

0x51 0op emit                 \ ( char -- ) вывод символа

void emit()    { putchar(D[--Dp]); }

0x52 0op ?key                 \ ( -- flag ) готовность ввода
0x53 0op ?emit                \ ( -- flag ) готовность вывода
0x54 0op h.                   \ ( n -- ) вывести n в hex виде

отладка
0x60 0op bye                  \ завершение работы ВМ

Команда завершает работу текущего процесса. В случае однозадачного варианта ВМ

завершается работа всей ВМ. 

void bye()     { exit(0); }

0x61 0op s.                   \ вывод дампа стека данных

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

вообще не реализована, или вызывать обновление окна стека данных. 

void sdot()    { printf("\n[ ");
                 for (uint i=0;i @ b, ;
: 1op ( opcode -- )      CREATE , DOES> @ b, d, ;

Слова, созданные с помощью 0op, будут компилировать только свой опкод. Слова,

созданные 1op, кроме опкода будут компилировать cell, взяв его из стека. 
Определяем команды FVM, разделив их на две части. Одна часть команд необходима

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



0x00 0op nop                  \ пустая команда
0x01 1op jmp                  \ переход
0x02 1op ?jmp                 \ ( flag -- ) переход если flag=0
0x03 1op call                 \ вызов
0x04 0op ret                  \ возврат
0x05 1op lit   : # lit ;      \ ( -- n ) литерал (поместить в стек константу)

0x08 0op do                   \ для циклов со счетчиком используем
0x09 0op loop                 \ специализированные команды FVM
0x0A 0op i
0x0B 0op j
0x0C 0op k

Эту часть ЦК см в описании управляющих конструкций. 

Память 


0x10 0op b@                   \ ( addr -- byte ) чтение байта из памяти
0x11 0op b!                   \ ( byte addr -- ) запись байта в память
0x12 0op w@                   \ ( addr -- word ) чтение 16-битного числа
0x13 0op w!
0x14 0op d@                   \ ( addr -- dword ) чтение 32-юитного числа
0x15 0op d!

Стек 


0x20 0op dup                  \ ( n -- n n )
0x21 0op drop                 \ ( n1 n2 -- n1 )
0x22 0op swap                 \ ( n1 n2 -- n2 n1 )
0x23 0op over                 \ ( n1 n2 -- n1 n2 n1 )
0x24 0op rot                  \ ( n1 n2 n3 -- n2 n3 n1 )
0x25 0op -rot                 \ ( n1 n2 n3 -- n3 n1 n2 )
0x26 0op pick                 \ ( ... i -- ... ni ) выборка iго элемента
0x27 0op depth                \ число элементов в стеке

Арифметика 


0x30 0op +
0x31 0op -
0x32 0op *
0x33 0op /

Логика 


0x40 0op <                    \ ( n1 n2 -- flag ) сравнение n1 vs n2
0x41 0op >
0x42 0op =
0x43 0op !=
0x44 0op not                  \ ( n -- ~n ) побитовая инверсия n
0x45 0op or                   \ ( n1 n2 -- n1|n2 )
0x46 0op and                  \ ( n1 n2 -- n1&n2 )
0x47 0op xor                  \ ( n1 n2 -- n1^n2 )
0x48 0op <<                   \ ( n i -- n<>                   \ ( n i -- n>>i) побитовый сдвиг вправо

Ввод/вывод 


0x50 0op key                  \ ( -- char ) ввод символа
0x51 0op emit                 \ ( char -- ) вывод символа
0x52 0op ?key                 \ ( -- flag ) готовность ввода
0x53 0op ?emit                \ ( -- flag ) готовность вывода
0x54 0op h.                   \ ( n -- ) вывести n в hex виде

Отладка 


0x60 0op bye                  \ завершение работы ВМ
0x61 0op s.                   \ вывод дампа стека данных
0x62 0op dump                 \ ( addr n -- ) вывод дампа памяти


S062: Управляющие конструкции

--------------------------------------------------------------------------------
Для того, чтобы писать программы, нам необходимы: 
определение макроподстановок команд 
определение процедур 
цикл со счетчиком DO-LOOP 
структура IF-ELSE-THEN для выполнения блоков кода по условию (флагу в стеке)

бесконечные циклы BEGIN-AGAIN 
циклы по пред-условию BEGIN-WHILE-REPEAT 
цикла по пост-условию BEGIN-UNTIL 
Определение макросов
Для компиляции часто посторяющегося кода традиционно используются макросы --
некое имя (в нашем случае форт-слово), которое заменяется набором команд. Для
нашего целевого компилятора эта возможность обеспечивается самим Фортом. Вот
например определение макро press, которое компилирует несколько команд FVM: 

: press ( n1 n2 n3 -- n1 n3 )
     swap ( n1 n3 n2 )
     drop ( n1 n3 )
;

Как видно из этого примера, при выполнении слова press будут выполнены слова

ассемблера swap и drop, которые компилируют соответствующий байт-код. 
В каком-то смысле это можно назвать и inline-компиляцией для ЦК: вместо вызова

процедуры press в текущую позицию (указываемую THERE) компилируется ее код. Это

приводит к ускорению работы программы (исключаются вызов процедуры и возврат

командами call и ret) и одновременно увеличению ее объема (естественно для 
процедур с размером кода больше размера call и ret). 

Определение процедур
Если ваша программа слишком распухает в объеме при использовании макросов, и
при 
этом вам не требуется максимальная скорость ее выполнения, нужно использовать

процедуры: 

{ press ( n1 n2 n3 -- n1 n3 )
     swap ( n1 n3 n2 )
     drop ( n1 n3 )
}

При выполнении этого кода Фортом 
текущая позиция THERE запоминается 
в целевой байт-код код компилируется код процедуры с ret в конце 
стартовый код в байт-коде корректируется так, чтобы при запуске программы был

выполнен переход (jmp entry) на код последней определенной процедуры 
в Форт-системе создается слово press, которое при своем выполнении будет 
компилировать команду call на запомненный адрес процедуры 

Для выполнения этого действия нам нужно определить слова { и }. Слово } завершает
 определение процедуры, и все его действие заключается всего-лишь в компиляции

команды ret: 

: }       ret ;

Слово { работает через механизм CREATE-DOES> : 
: {
\ { новая-процедура ... }
     THERE M 1+ !        \ модифицируем стартовый jmp entry
     CREATE THERE ,      \ создаем слово новая-процедура и запоминаем THERE
     DOES> @ call        \ при выполнении новая-процедура компилируем call
;

Цикл со счетчиком DO-LOOP
Циклы со счетчиком поддерживаются на уровне команд ВМ.