Сколько нужно примитивов для реализации форт системы?
В 1992-м году проходил очередной конкурс по обфусцированному программированию на языке С. Один из представленных проектов был небольшой форт системой. Меня поразило, что виртуальная машина была реализована всего в 794 байтах С кода. Остальная часть форт системы загружалась из исходника на форте. После изучения проекта первоначальный восторг уступил место разочарованию, так как автор использовал не совсем «честный» трюк: для парсинга фортового исходника он использовал функцию scanf (). С этого момента меня терзал вопрос — сколько нужно примитивов для реализации форт системы без подобных трюков?
Через некоторое время я познакомился с форт системой sod32 написанной Lennart Benschop. У этой форт системы виртуальная машина написана на С, а двоичный образ, который загружается в виртуальную машину, не зависит от порядка байтов в слове хост системы. sod32 имеет 32 примитива, вот они:
Я понял, что у меня появился шанс найти ответ на свой вопрос и я начал превращать примитивы в высокоуровневые определения. Хочу сразу отметить, что вся эта деятельность имеет чисто академический смысл. Применить полученные результаты на практике вряд ли получится из-за потери производительности. В процессе своих экспериментов я отслеживал изменения размера двоичного образа форт системы и время выполнения набора тестов за авторством John Hayes. Новый двоичный образ я строил командой
echo 'S" extend-cross.4" INCLUDED '|./sod32 kernel.img
а тесты запускал вот так:
time ./sod32 kernel.img <<< $(echo -e 'S" tester.fr" INCLUDED\n12345\nBYE')
В таблице ниже вы можете увидеть как каждое изменение повлияло на размер и производительность. Ссылки из колонки «изменение» ведут на соответствующий коммит в гитхабе.
В итоге размер двоичного образа форт системы увеличился с 10164 до 15912 (+57%), производительность упала в 708 раз (почти 3 порядка). Возможно производительность можно было бы улучшить если отпрофилировать код и оптимизировать узкие места, но я уверен, что результат все равно будет очень медленным по сравнению с исходной sod32.
С 32-х примитивов плюс дополнительной логики во внутреннем интерпретаторе я пришел к 7: nop, nand, !, @, um+, special, lit. Во внутреннем интерпретаторе осталась логика для исполнения примитивов и высокоуровневых определения (call), а также логика для завершения высокоуровневого определения (next). Ответ на свой вопрос я нашел: форт систему можно построить на базе 9-ти примитивов (или 8-ми, если nop не обязательно должен быть примитивом). Меня смущает то, что для доступа к памяти присутствует целых 3 примитива: @,! и lit, но я не придумал, как этого можно избежать. Я вполне мог что-то упустить, так что если вы знаете как можно избавиться от бОльшего количества примитивов — пожалуйста напишите в комментариях.
