Виртуальные машины / Forth
От: voidlizard  
Дата: 25.07.08 05:43
Оценка:
Для одного из проектов с использованием GSM/GPS трекеров, пришлось разработать виртуальную машину
для исполнения скриптов на самих устройствах.

Сами трекеры построены на базе Microchip PIC18 — если кто не знает — около 3Kb RAM, 40 Kb Program Flash ну и в нашем
случае есть еще дополнительно 32Kb EEPROM, куда и пишутся байткоды скриптов, тк больше некуда — при питании от батарейки
устройство не сможет, например, само себе прошить program flash. Исходя из ограниченных ресурсов, ASM в качестве языка
разработки прошивки, отсутствия внятной документации по теме — было принято решение разработать Fort-машину, которая бы
исполняла на байткод, скомпилированный вовне и залитый в EEPROM, что и было сделано. Операции и переменные — в основном
8-битные, адреса — от 8 до 24 бит, но в принципе можно поднатужиться и реализовать 16-разрядную арифметику (это все специфика PIC-а).

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

Вопрос, собственно, вот в чем:

0) Есть ли какие-то языки, которые можно успешно компилировать в байткоды для форт-машины ( двухстековая машина, произвольного доступа к
элементам стека — нет, доступ к памяти есть, но дороговато обходится) ?

1) Есть ли какие-то хорошо специфицированные, несложные (в принципе любая несложная, если в ней не более сотни инструкций) виртуальные машины,
с компактными опкодами? Желательно, что бы были готовые компиляторы, которые генерировали для них код. LUA5, Python — некомпактны, Java — хороша,
но писать компилятор и VM сложно (много инструкций, разрядность и тп) ?

2) Может быть есть хотя бы какие-то заготовки, в виде парсера языка в AST, или просто язык с компактной VM которую несложно портировать.

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

В качестве программы-минимума, хотя бы какой-нибудь неплохой язык и парсер его в AST, но отдельно стоящий, т.е. что бы не приходилось выдирать его из LUA,
а можно было просто взять и использовать, в этом случае хорошо бы что бы язык и компилятор были реализованы на каком-нибудь человеческом языке, а не С/С++/Java,
тк придется дописывать трансляцию в байткоды, и нет столько времени, что бы ковыряться с чужим кодом на вышеозначенных языках.


Бэкграунд: смотрел PyPy, за отведенное время не осилил (вероятно, к нему еще вернусь, тк выглядит как почти то, что надо, но непонятно как это использовать).
Смотрел LLVM, не портируемо (куда нам надо). Смотрел Parrot, сложно и не портируемо.


Мнения?

---
dmz

если модераторы восстановят пароль от моего старого аккаунта, я буду совсем не против
Re: Виртуальные машины / Forth
От: Cyberax Марс  
Дата: 25.07.08 05:48
Оценка:
Здравствуйте, voidlizard, Вы писали:

V>0) Есть ли какие-то языки, которые можно успешно компилировать в байткоды для форт-машины ( двухстековая машина, произвольного доступа к

V>элементам стека — нет, доступ к памяти есть, но дороговато обходится) ?
Scheme?

V>1) Есть ли какие-то хорошо специфицированные, несложные (в принципе любая несложная, если в ней не более сотни инструкций) виртуальные машины,

V>с компактными опкодами? Желательно, что бы были готовые компиляторы, которые генерировали для них код. LUA5, Python — некомпактны, Java — хороша,
V>но писать компилятор и VM сложно (много инструкций, разрядность и тп) ?
JVM можно не всю реализовывать. Посмотри на http://en.wikipedia.org/wiki/Java_Card — оно очень близко.
Sapienti sat!
Re[2]: Виртуальные машины / Forth
От: voidlizard  
Дата: 25.07.08 05:58
Оценка:
V>>0) Есть ли какие-то языки, которые можно успешно компилировать в байткоды для форт-машины ( двухстековая машина, произвольного доступа к
V>>элементам стека — нет, доступ к памяти есть, но дороговато обходится) ?

C>Scheme?


Хотелось бы для начала увидеть компиляцию Scheme во что-нибудь вообще. Честно говоря, не слишком представляю как устроен лисп — он
точно нормально ляжет на двухстековую машину? Или придется писать какой-то менеджер хипа для работы со списками, а стек данных
будет просто простаивать?


V>>1) Есть ли какие-то хорошо специфицированные, несложные (в принципе любая несложная, если в ней не более сотни инструкций) виртуальные машины,

V>>с компактными опкодами? Желательно, что бы были готовые компиляторы, которые генерировали для них код. LUA5, Python — некомпактны, Java — хороша,
V>>но писать компилятор и VM сложно (много инструкций, разрядность и тп) ?

C>JVM можно не всю реализовывать. Посмотри на http://en.wikipedia.org/wiki/Java_Card — оно очень близко.


Вроде смотрел, посмотрю еще раз. Если JVM реализовать не всю, но как быть с консистентностью компилятора и VM? Как ее хотя бы проверять при компиляции?
Свой компилятор писать не хочется, а если уж его писать, то уж не джаву точно.
Re[3]: Виртуальные машины / Forth
От: Cyberax Марс  
Дата: 25.07.08 06:11
Оценка:
Здравствуйте, voidlizard, Вы писали:

C>>Scheme?

V>Хотелось бы для начала увидеть компиляцию Scheme во что-нибудь вообще. Честно говоря, не слишком представляю как устроен лисп — он
V>точно нормально ляжет на двухстековую машину? Или придется писать какой-то менеджер хипа для работы со списками, а стек данных
V>будет просто простаивать?
У NASA это вроде получалось

C>>JVM можно не всю реализовывать. Посмотри на http://en.wikipedia.org/wiki/Java_Card — оно очень близко.

V>Вроде смотрел, посмотрю еще раз. Если JVM реализовать не всю, но как быть с консистентностью компилятора и VM? Как ее хотя бы проверять при компиляции?
Есть верификаторы того, что в байт-коде ничего левого не будет.

V>Свой компилятор писать не хочется, а если уж его писать, то уж не джаву точно.

Компилятор используется стандартный, просто нужно определённых конструкций избегать будет.
Sapienti sat!
Re[4]: Виртуальные машины / Forth
От: voidlizard  
Дата: 25.07.08 06:25
Оценка:
C>>>Scheme?
V>>Хотелось бы для начала увидеть компиляцию Scheme во что-нибудь вообще. Честно говоря, не слишком представляю как устроен лисп — он
V>>точно нормально ляжет на двухстековую машину? Или придется писать какой-то менеджер хипа для работы со списками, а стек данных
V>>будет просто простаивать?
C>У NASA это вроде получалось

Что именно? Где посмотреть? Просто если они на форт-подобную машину спортировали Scheme, то может какое-то подобие руби-питона-луа туда тоже
спортируется, а для скриптинга оно более человечное, нежели лисп-подобие...

Просто у меня сейчас затык, как организовать локальные переменные, имея 128 байт стека (ну в крайнем случае стек можно расширить за счет хипа, конечно),
не имея произвольного доступа к индексным регистрам стека, а форт-машина, понятное дело перестанет ей быть, если даст возможность коду рулить
указателями стека. Доступ к хипу достаточно дорогой, то есть устраивать "софтварный" (реализованный на самом форте) стек для локальных переменных
очень не хочется (хотя и можно)


C>>>JVM можно не всю реализовывать. Посмотри на http://en.wikipedia.org/wiki/Java_Card — оно очень близко.

V>>Вроде смотрел, посмотрю еще раз. Если JVM реализовать не всю, но как быть с консистентностью компилятора и VM? Как ее хотя бы проверять при компиляции?
C>Есть верификаторы того, что в байт-коде ничего левого не будет.

V>>Свой компилятор писать не хочется, а если уж его писать, то уж не джаву точно.

C>Компилятор используется стандартный, просто нужно определённых конструкций избегать будет.

Звучит не очень прикольно, и, насколько я понимаю, JavaCard — не опенсорц, то есть подкрутить компайлер если что — нельзя?
Re: Виртуальные машины / Forth
От: FR  
Дата: 25.07.08 08:26
Оценка:
Здравствуйте, voidlizard, Вы писали:


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

V>которые в нормальной жизни обычно не возникают. Грубо говоря, бывают языки, которые стремятся сократить побочные эффекты,
V>а бывают языки, которые строятся из побочных эффектов (это про форт). Соответственно, в следующем поколении устройств
V>хочется переехать с форта на что нибудь еще.

Может проще поднатужится и нормально разобратся с фортом?
То есть сделать нормальный DSL на форте и использовать только его для прикладного кодирования.

V>То есть, что хотелось бы иметь в идеале: язык, компилятор с него в байткоды (компактность не хуже форта) и четкая спецификация виртуальной машины, которую надо реализовать, что бы эти байткоды исполнять. Управление памятью должно быть за счет компилятора (что вполне возможно, кмк)


У Ocaml'а достаточно несложный и компактный байт код, но боюсь у вас жестковаты ограничения.
http://pauillac.inria.fr/~lebotlan/docaml_html/english/index.html

V>В качестве программы-минимума, хотя бы какой-нибудь неплохой язык и парсер его в AST, но отдельно стоящий, т.е. что бы не приходилось выдирать его из LUA,


Тут http://www.cminusminus.org/code.html#luaml есть старенькая версия lua, с ast и раздельной компиляцией.

Из скриптов еще есть более компактный чем lua Squirrel http://squirrel-lang.org/default.aspx
Re: Виртуальные машины / Forth
От: Tilir Россия http://tilir.livejournal.com
Дата: 25.07.08 08:48
Оценка:
Здравствуйте, voidlizard, Вы писали:

V>Исходя из ограниченных ресурсов, ASM в качестве языка

V>разработки прошивки, отсутствия внятной документации по теме — было принято решение разработать Fort-машину, которая бы исполняла на байткод, скомпилированный вовне и залитый в EEPROM, что и было сделано.

Поправьте меня если я ошибаюсь -- вместо того, чтобы написать нормальный компилятор C для вашей архитектуры, вы, при таких-то ограничениях, разрабатываете какие-то VM? А если не секрет -- зачем?
Re[2]: Виртуальные машины / Forth
От: voidlizard  
Дата: 25.07.08 09:18
Оценка:
T>Поправьте меня если я ошибаюсь -- вместо того, чтобы написать нормальный компилятор C для вашей архитектуры, вы, при таких-то ограничениях, разрабатываете какие-то VM? А если не секрет -- зачем?

Что бы дистанционно заливать скрипты в устройства, причем скрипты должны быть managed — те косяки в скриптах не должны вешать устройство — если оно
вдруг заткнулось из-за скрипта, то должна быть возможность дистанционно-же вывести его из ступора и перезалить скрипт — т.е. прошивка работает как супервайзер,
типичный kernel mode (а скрипт — user mode). И кстати, отлично все работает — т.е скорость работы устройства пока ограничивается скоростью коммуникаций, а не
скоростью исполнения скрипта.

А компиляторы C под PIC18 есть, правда довольно отстойные (но не думаю, что я написал бы лучше, особенно за те две полторы недели, которые ушли на разработку
VM на пике и транслятора форта и эмулятора на PC)
Re[2]: Виртуальные машины / Forth
От: voidlizard  
Дата: 25.07.08 09:23
Оценка:
FR>Может проще поднатужится и нормально разобратся с фортом?

Да куда уж нормальнее, даром что сам его написал.

FR>То есть сделать нормальный DSL на форте и использовать только его для прикладного кодирования.


Фактически — так оно сейчас и есть; но хотелось бы большего (в будущем).

Тут фишка в том, что ядро прошивки пришлось сделать на ASM по разного рода соображениям, и соответственно у
нас будет очень плохо с его поддержкой; пока не переедем на другую платформу и не перепишем ядро на C. В общем, чем меньше мы будем
лазить в ядро — тем будет лучше, кроме того, на асме очень уныло делать разные прикладные вещи (которые можно было бы биндить потом в форт) —
например, парсинг строк. На форте и то веселее, затраты времени не сравнимы.

FR>Тут http://www.cminusminus.org/code.html#luaml есть старенькая версия lua, с ast и раздельной компиляцией.


FR>Из скриптов еще есть более компактный чем lua Squirrel http://squirrel-lang.org/default.aspx


Спасибо, посмотрю.
Re[5]: Виртуальные машины / Forth
От: palm mute  
Дата: 25.07.08 09:56
Оценка: 7 (2)
Здравствуйте, voidlizard, Вы писали:

V>Просто у меня сейчас затык, как организовать локальные переменные, имея 128 байт стека (ну в крайнем случае стек можно расширить за счет хипа, конечно),

V>не имея произвольного доступа к индексным регистрам стека, а форт-машина, понятное дело перестанет ей быть, если даст возможность коду рулить
V>указателями стека. Доступ к хипу достаточно дорогой, то есть устраивать "софтварный" (реализованный на самом форте) стек для локальных переменных
V>очень не хочется (хотя и можно)

Первое — последний раз, когда я смотрел на Форт, там были слова для прямого доступа к стеку по смещению от вершины.

Второе — я не копенгаген в компиляторах, потому мой совет, скорее всего, окажется непрактичным, но все же выскажусь:
а) чисто-функциональные программы тривиально компилируются в код для стековой машины (аргументы функций запихиваются в стек, функция их съедает и оставляет на вершине стека результат). Под функциональной чистотой в данном случае понимается только отсутствие мутабельных локальных переменных, глобальные переменные в куче, ввод-вывод и т.д. не запрещены.
б) SSA-преобразование превращает любую процедуру в чисто-функциональную.
Re[3]: Виртуальные машины / Forth
От: merk Россия  
Дата: 25.07.08 10:14
Оценка:
Здравствуйте, voidlizard, Вы писали:

T>>Поправьте меня если я ошибаюсь -- вместо того, чтобы написать нормальный компилятор C для вашей архитектуры, вы, при таких-то ограничениях, разрабатываете какие-то VM? А если не секрет -- зачем?


V>Что бы дистанционно заливать скрипты в устройства, причем скрипты должны быть managed — те косяки в скриптах не должны вешать устройство — если оно

V>вдруг заткнулось из-за скрипта, то должна быть возможность дистанционно-же вывести его из ступора и перезалить скрипт — т.е. прошивка работает как супервайзер,

мы подобную задачу решали насколько я помню ватчодогом и перезапуском заливки. то есть если программа застряла ватчдог запускает загрузчик, тот плюет в канал запрос на перезагрузку, и смотрит идут ли байты в ответ. если идут — читает их в пямять и пускает снова. осталось только придумать, как у вас обеспечить работу ватчдога.
Re[4]: Виртуальные машины / Forth
От: merk Россия  
Дата: 25.07.08 10:23
Оценка:
Здравствуйте, merk, Вы писали:

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


гм. когда прочел подробней первый пост..увидел, что устройство принципиально не может само себя прошить.
это плохо. могло б прошить — проблем бы не было.
Re: Виртуальные машины / Forth
От: merk Россия  
Дата: 25.07.08 10:32
Оценка: -1 :)
Здравствуйте, voidlizard, Вы писали:


V>Для одного из проектов с использованием GSM/GPS трекеров, пришлось разработать виртуальную машину

V>для исполнения скриптов на самих устройствах.
V>Мнения?
V>---
V>dmz

а вы берете во внимание, что любой интерпертируемый язык на таком батарейном устройстве, будет грубо говоря на операцию тратить кулонов(мера измерения заряда), на порядок-полтора боьше на нативном коде? аккумуляторы будут садиться со страшною силой?
есть сомнения в практической пригодости продукта или расширяемости спектра задач на нем.
я бы по любому уходил от виртмашины в данном случае.
Re[2]: Виртуальные машины / Forth
От: dmz Россия  
Дата: 25.07.08 10:57
Оценка:
M>а вы берете во внимание, что любой интерпертируемый язык на таком батарейном устройстве, будет грубо говоря на операцию тратить кулонов(мера измерения заряда), на M>порядок-полтора боьше на нативном коде? аккумуляторы будут садиться со страшною силой?

Пик потребляет минимум на порядок на порядок меньше, чем GSM и GPS модули. Кроме того, предшественник данного устройства, сделанный бестолковыми швейцарско-бельгийско-венгерско-китайскими разработчиками вообще не знал команды sleep и молотил все время — а раз так, то какая разница, какие именно команды ему молотить? В общем, думаю, вы ошибаетесь в данном вопросе.

M>есть сомнения в практической пригодости продукта или расширяемости спектра задач на нем.

M>я бы по любому уходил от виртмашины в данном случае.

Сомнения, безусловно, ваше право — но лично я считаю, что на самом деле все обстоит с точностью до наоборот, т.е. пока мы не
разработали данную прошивку на это устройство, оно было непригодным ни для каких практических применений, в т.ч.
и по соображениям расхода энергии, теперь же у нас есть возможность тонко настраивать режимы работы, добиваясь наименьшего
потребления энергии для данного конкретного режима эксплуатации. В общем-то, тему практичности предлагаю не развивать — вы не знаете
нашей ситуации в любом случае, так что спор все равно будет ни о чем.
Re[5]: Виртуальные машины / Forth
От: dmz Россия  
Дата: 25.07.08 11:00
Оценка:
M>>мы подобную задачу решали насколько я помню ватчодогом и перезапуском заливки. то есть если программа застряла ватчдог запускает загрузчик, тот плюет в канал запрос на перезагрузку, и смотрит идут ли байты в ответ. если идут — читает их в пямять и пускает снова. осталось только придумать, как у вас обеспечить работу ватчдога.

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

M>это плохо. могло б прошить — проблем бы не было.

Проблема бы была, так как это очень опасно для функционирования устройства. В текущем виде скрипт ни при каком раскладе
не может прострелить голову прошивке своей работой, т.к. сидит в песочнице и имеет доступ только к тем функциям, которые ему предоставила
прошивка. А скрипты планируется заливать пользовательские.
Re: Виртуальные машины / Forth
От: Holden Claulfield  
Дата: 25.07.08 11:39
Оценка:
Здравствуйте, voidlizard, Вы писали:


V>Для одного из проектов с использованием GSM/GPS трекеров, пришлось разработать виртуальную машину

V>для исполнения скриптов на самих устройствах.

Не смотрели тут?
Re[6]: Виртуальные машины / Forth
От: merk Россия  
Дата: 25.07.08 11:59
Оценка:
dmz>Проблема бы была, так как это очень опасно для функционирования устройства. В текущем виде скрипт ни при каком раскладе
dmz>не может прострелить голову прошивке своей работой, т.к. сидит в песочнице и имеет доступ только к тем функциям, которые ему предоставила
dmz>прошивка. А скрипты планируется заливать пользовательские.
ну если таки нужна VM для микроконтроллера, нужно гуглить
virtual machine microcontroller.
http://www.scribd.com/doc/2784076/Virtual-Machines-Running-on-Microcontrollers
проц вроде правда avr, но там какой-то опен сорсе. в детали не вникал.
можно погуглить VM microcontroller, virtual machine PIC...
кстати интересно чем кончатся ваши поиски.
если не трудно, сообщите потом о результатах.
Re[2]: Виртуальные машины / Forth
От: mkizub Литва http://symade.tigris.org
Дата: 25.07.08 13:36
Оценка: +2 :)
Здравствуйте, Holden Claulfield, Вы писали:

V>>Для одного из проектов с использованием GSM/GPS трекеров, пришлось разработать виртуальную машину

V>>для исполнения скриптов на самих устройствах.

HC>Не смотрели тут?


На 40kb запускать? Оптимистично то как!
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[3]: Виртуальные машины / Forth
От: FR  
Дата: 25.07.08 16:07
Оценка: +2
Здравствуйте, mkizub, Вы писали:

M>На 40kb запускать? Оптимистично то как!


Самое место для форта
Re: Виртуальные машины / Forth
От: FR  
Дата: 25.07.08 16:09
Оценка:
Здравствуйте, voidlizard, Вы писали:

V>1) Есть ли какие-то хорошо специфицированные, несложные (в принципе любая несложная, если в ней не более сотни инструкций) виртуальные машины,

V>с компактными опкодами? Желательно, что бы были готовые компиляторы, которые генерировали для них код. LUA5, Python — некомпактны, Java — хороша,
V>но писать компилятор и VM сложно (много инструкций, разрядность и тп) ?

Вспомнил еще вариант, наверно самый легкий из функциональщины, http://caml.inria.fr/caml-light/index.en.html но похоже тоже не влезет.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.