Виртуальная стековая байт-машина

Pingvin

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

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

Начал с изучения статьи "Пишем интерпретатор скрипта и стековую машину" на хабре https://habrahabr.ru/post/223887/

dev

Сама ВМ вообще за час пишется. А вот с компилятором могут быть проблемы.

А надо ли это вообще? Не проще ли компилировать сразу для МК?

Reflector

Pingvin писал(а):

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

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

Я делал компилятор и декомпилятор под байт-код, с сишным синтаксисом, а в 2004 даже написал на D компилятор для PIC18, но уже обычный, что-то среднее между С и ассмом :) А насчет советов даже не знаю, если у тебя опыта написания подобных вещей совсем нет, то начни в чего-то относительно простого, да хоть программу разбора выражений для калькулятора напиши, потом ее можно развить и сделать основой для всего компилятора. У меня, в случае байт-кода, так и было, только выражение - это не a+b, там могут встречаться практически все допустимые операторы, включая присваивание, приведение типов и вызовы функций в аргументах которых вызываются другие функции.

Pingvin

Принцип работы мне понятен.
Думаю - первым делом нужно определиться с набором псевдокоманд нашей стековой машины, нашёл вот такой наборчик:

Цитата:

PUSH - поместить значение в стек
POP - удалить значение с вершины стека
DUP - сделать копию верхнего элемента стека
SWAP - обмен местами 2 верхних параметров в стеке
ROT - циклически переставляет 3 верхних элемента в стеке по-часовой стрелке
OVER - продублировать на вершину второй элемент стека
PICK - дублирует n-ый элемент стека на вершину
ROLL - циклически переставляет n-верхних элементов в стеке по-часовой стрелке
RVALUE - поместить в стек содержимое объекта, адрес которой лежит на вершине стека
LVALUE - поместить в стек адрес в памяти, по которому расположен объект лежащий на вершине стека
LET - rvalue-значение на вершине стека размещено по адресу предоставленному lvalue- значением, следующим за ним в стеке

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

dev

Можно порешать вот эту задачку - https://www.codewars.com/kata/tiny-three-pass-compiler
Там и код ВМ приведен.

Reflector

dev писал(а):

Можно порешать вот эту задачку - https://www.codewars.com/kata/tiny-three-pass-compiler
Там и код ВМ приведен.

Там трехпроходный и не стековый компилятор, это совсем другое...

dev

Компилятор - не стековый, а ВМ - стековая.

Pingvin

Тестить идеи можно и на ПК.

Reflector

dev писал(а):

Компилятор - не стековый, а ВМ - стековая.

Посмотри внимательнее, если там есть команды PU и PO(push и pop), это еще не значит, что VM там стековая. Там даже команды выполняющие математические операции работают с парой регистров r0/r1 и результат будет в r0, а должны брать два значения с вершины стека и результат класть туда же.

_pv

там где нужны скрипты обычно скорость не особо важна, соответственно хватит и интерпретатора, без компиляции в байт-код.
можно легко допилить что-нибудь вроде http://www.stroustrup.com/Programming/S ... 7/e7-1.cpp добавив функции, условный оператор ?,...
либо просто взять готовый PAWN https://www.compuphase.com/pawn/pawn.htm там и компилятор есть.

ну и как же можно было забыть про форт.

arm999

_pv писал(а):

ну и как же можно было забыть про форт.

https://github.com/zevv/zForth

Pingvin

Нужен простой "как тапок" язык.
Скрипты будут писать "домохозяйки", грубо говоря.
Они Фортом последний мозг себе поломают.

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

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

Но начать можно с интерпретатора, да...

aamonster

Pingvin, imho стОит выбрать один из двух вариантов:
1. Впихнуть что-нибудь стандартное (LUA, к примеру)
2. Написать специализированный движок, удобно заточенный именно под вашу задачу. Соответственно, команды в нём будут "жирные", и о быстроте интерпретации самого байт-кода можно не заботиться. И, соответственно, не нужно явно делать стековую машину - обойдётесь рекурсией.

Пример варианта 2: когда у меня возникла задача что-то считать по снятым юзером кривым - я сделал простенький движок с функциями max/min/avg/len - позволяющий считать выражения вроде 2*pi*c*avg((v-avg(v))^2), где v - массив, c - внешняя переменная.

Да, опять же для варианта 2: проще всего байт-код формировать в порядке прямой польской записи: команда для функции, потом её аргументы. При этом интерпретатор становится тривиальным.

KPG

arm999 писал(а):

_pv писал(а):

ну и как же можно было забыть про форт.

https://github.com/zevv/zForth

На Github можно и просто для поиска ввести слово Forth (ещё есть Topic:Forth) :)

P.S. Поверх Форта можно наложить какой нибудь Бейсик в качестве расширения языка.
Один из интересных проектов http://d2lang.chat.ru/ (D2 Language 2002г. автор делал его по материалу уроков Креншоу "Пишем компилятор"

Код:

Д2 - это язык программирования высокого уровня. Предками языка, оказавшими на него наибольшее влияние, можно назвать Forth, Pascal (Modula-2, Oberon) и С. Язык был задуман как обладающий намеренно простым синтаксисом и возможно большей расширяемостью. Первое было достигнуто за счет сокращения до реального минимума управляющих конструкций, и отказа от такого понятия современных языков алголоидного типа как тип данных, однако же, был оставлен "классический" синтаксис языка типа Pascal. Формально язык содержит единственный тип данных - указатель. Косвенно поддерживаются такие типы как числа и строки символов. Второе, т.е. расширяемость, было достигнуто за счет введения понятия библиотеки или модуля, а также, в основном за счет внутреннего устройства ядра языка идею которого он позаимствовал у Forth ( http://www.forth.org.ru ), хотя это скорее вопросы реализации, чем синтаксиса... Язык поддерживает такие понятия как процедура (векторная процедура), локальные и глобальные переменные, параметры. В языке нет каких либо предопределенных операций и функций кроме, как я уже отмечал, операций управления процессом исполнения. Все функции ввода-вывода, математические, процедуры работы с графикой и т.д. поставляются в виде библиотек и в исходных текстах.

По поводу расширяемости:
 1). стандартный императивный подход
     создание новых процедур которые могут выступать в роли
     постфикс/инфиксных операторв (с учетом приоритетов)
     процедуры могут переопределятся (как статически, так и
     динамически)
 2). открытые исходные тексты компилятора
     пользователь может перетранслировать транслятор с
     целью получения нового синтаксиса
Хочется добавить:
 3). полный полиморфизм процедур (необходимо будет ввести
     типизацию данных)
 4). настраиваемый под пользователя синтаксис (ЯАП - язык,
     адаптируемый пользователем)

+ стековый генератор был рассмотрен в книге В.А.Серебряков " Лекции по конструированию компиляторов"

Уроки Креншоу есть также в варианте применения iForth :)
на Форте есть и парсеры BNF нотации и всякие лексеры, но современной литературы всего что можно сделать на Форт основе нету :)
Есть даже такой IEEE стандарт с байт-кодами (применённый в OpenFirmware и имеющий разный доп инструментарий поддержки типа Си компиляторов, детокенайзеров и др.)
А голову, да, лучше поберечь и не ломать всякими Форт языками. Вдруг ещё понравится. :) (как сделали некоторые производители в своих изделиях Strobotics, Mosaic Industries, ForthLogic ... да и некоторое количество HP калькуляторов с RPL, RPN языками)

KPG

aamonster писал(а):

Да, опять же для варианта 2: проще всего байт-код формировать в порядке прямой польской записи: команда для функции, потом её аргументы. При этом интерпретатор становится тривиальным.

Почти это сделано в TCL языке или Лого.

Pingvin

Да я не против Форта.
1. Но скрипты буду писать не я.
2. Я не представляю, как я его подружу с основной прошивкой? Он же на ассемблере пишется, как я понял. Всё свою прошивку на ассемблере переписывать, что ли?

Как периферию инициализировать?
Как прерывания обрабатывать?

Для меня тут темный лес.

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

Reflector

aamonster писал(а):

Да, опять же для варианта 2: проще всего байт-код формировать в порядке прямой польской записи: команда для функции, потом её аргументы. При этом интерпретатор становится тривиальным.

Пока у нас есть простейшие выражения типа a + b, которые трансформируется в +ab, то все просто, но уже для выражения a + b * c и соответствующего ему *+abc не получится просто взять "*" и ее аргументы, т.к. один из них на этот момент еще не рассчитан, тут уже потребуется более сложный рекурсивный алгоритм обхода. То же выражение в обратной польской нотации будет иметь вид abc*+ и его разбор действительно тривиален: встретившиеся переменные кидаем на стек, столкнувшись с "*" умножаем два значения на вершине стека, потом то же проделываем для "+".

Pingvin

Если делать стек-машину, то с обратной польской нотацией.

KPG

Pingvin писал(а):

Да я не против Форта.
1. Но скрипты буду писать не я.
2. Я не представляю, как я его подружу с основной прошивкой? Он же на ассемблере пишется, как я понял. Всё свою прошивку на ассемблере переписывать, что ли?

Как периферию инициализировать?
Как прерывания обрабатывать?

Для меня тут темный лес.

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

Он Пишется не обязательно на ассемблере (полно и С реализаций и на других языках)
Можно даже так F minus (проект с sourceforge) часть генерится через Форт и включается в Си проект с возможостью вызова кода в обеих направлениях.
на sourceforge есть и проект простой кодогенерации Форт листинга и другие проекты. Подходов много и разных.

P.S. Например для генерации ядра amForth применяется отдельная утилита по формированию тела высокоуровневых Форт слов в ассемблер AVR,
но там часть слов ядра написаны на ассемблере.
Один из примеров реализации маленького Бейсика на Форт http://www.nicholson.com/rhn/files/Tiny ... _Forth.txt

Pingvin

Ну вот Pawn заинтересовал, но опять не найду ни описания языка, ни как прикрутить его к своему проекту!

KPG

Pingvin писал(а):

Ну вот Pawn заинтересовал, но опять не найду ни описания языка, ни как прикрутить его к своему проекту!

Знаете, что такое синдром Блаба? :)
Грэм, Пол "Lisp: побеждая посредственность"

aamonster

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

Код:

eval: case get_token()
  '+': return eval()+eval()
  '*': return eval()*eval()
  number: return number_value()

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

aamonster

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

_pv

Pingvin писал(а):

Ну вот Pawn заинтересовал, но опять не найду ни описания языка, ни как прикрутить его к своему проекту!

http://we.easyelectronics.ru/STM32/prik ... stm32.html

ну и интерпретаторы:
https://github.com/zsaleeba/picoc
https://github.com/pmachapman/LittleC

PRC

Сделать эмулятор МК-61)))) И просто и команд достаточно много. На нем даже почти шашки делать умудрялись)))

Easyelectronics.ru

Виртуальная стековая байт-машина

Кто сейчас на конференции