В форумах я часто вижу вопросы от начинающий программистов на С++: «какую посоветуете литературу?». Обычно я отвечаю набором надежных книг с дополнением: никакое количество прочитанных книг не заменит практику. Нужно на самом деле делать что-то. Но что? Что может быть хорошим проектом? Нужно что-то, что научит многому, но при этом достаточно простое и интересное, чтобы не заскучать. Я недавно задумался над этим вопросом, и, кажется, нашел ответ. Вам несомненно стоит написать интерпретатор байт-кода. Для меня такой проект оказал решающее значение в становлении всей последующей карьеры.
Как все началось
В 200Х году я учился на втором курсе в университете. У меня уже был небольшой опыт в программировании. Я умел использовать абстракции, доступные в С++, я не понимал на самом деле как все работает. Для меня компилятор и операционная система были просто черными коробками, работающими благодаря магическим заклинаниям, и я в целом считал это приемлемым.
Недостаток знаний не мешал мне активно участвовать в войнах языков программирования. Один из таких тредов натолкнул меня на знакомство с виртуальной машиной Java, и я узнал про стековую архитектуру.
Я практически ничего не понимал в архитектуре x86, и не слышал ничего про другие архитектуры. Идея машины без регистров показалась мне очень интересной и необычной. Я подумал в тот день про все это и решил сесть и написать собственную простую стековую виртуальную машину.
Как это выглядело
Stupid Virtual Machine (или SVM для краткости) следовала самой простой возможной идее. Размер слова (word) был 32 бита, и доступ к памяти осуществлялся по словам (нельзя было обращаться к отдельным байтам). Области памяти для программного кода и для данных были полностью изолированы друг от друга (позже я узнал, что это является отличительной чертой Гарвардской архитектуры). Даже стек находился в своей отдельной части памяти.
Набор инструкций был тоже достаточно простым. Стандартные арифметические и логические инструкции, работа с памятью, манипуляции со стеком и переходы (jump). Все работало самым очевидным образом. Например, инструкция ADD брала 2 первых 32-битных значения из стека, складывала их в виде целых чисел со знаком и пушила результат в стек.
Ввод/вывод был примитивным, привязанным к stdin/stdout. Были инструкции IN и OUT. Первая пушила результат чтения в стек, вторая выводила на экран первое значение из стека. Для удобства я добавил специальный флаг: нужно ли считать ввод потоком сырых байтов или строковым представлением целого числа со знаком.
Каково было программировать
Вначале, я писал все программы для SVM на чистом машинном коде, в шестнадцатиричном редакторе. Это быстро надоело, так что я написал ассемблер с поддержкой меток и строковых литералов. Например, "Hello, World" выглядел так:
"Hello, World!n"
print
Когда ассемблер видит строковый литерал, он пушит каждый байт в стек. PRINT — это не инструкция, это просто макрос, который генерирует цикл. Цикл печатает каждый символ из стека пока не дойдет до 0.
Писать и читать код для стековой машины — странный опыт. Вот чуть более продвинутый пример, так выглядел подсчет наибольшего общего делителя:
IN ; прочитать число "A" из стандартного ввода
IN ; прочитать число "B" из стандартного ввода
:GCD ; это метка
DUP ; если B равно 0, то A это gcd
0 ; (значения пушатся в стек)
@END ; (так адрес метки помещается в стек)
JE ; (переход к адресу из начала стека если два предыдущих значения равны)
SWP ; если B не равно 0, то результат равен gcd(B, A modulo B)
OVR
MOD
@GCD
JMP ; рекурсия!
:END
POP ; удалить 0 из начала стека
OUT ; теперь результат в начале стека, напечатать его
Тут продемонстрировано использование меток и условных переходов.
Если хотите увидеть еще более продвинутый пример, то почитайте ассемблерный код для сортировки вставками, но я не обижусь, если вы решите пропустить его. Это довольно длинный листинг, поэтому я не включил его в пост.
Если интересно, то можете также взглянуть на код виртуальной машины и ассемблера, которые я нашел в старых файлах. Там ничего необычного, и вообще, это скорее пример того, как НЕ НУЖНО писать интерпретатор байт-кода. Чтобы заставить стековые машины работать также хорошо, как регистровые машины, требуется реализовать несколько трюков. Конечно, я ничего не знал о них, и мой подход был наивным, что негативно сказалось на производительности.
Почему вам тоже нужно сделать это
Написание даже примитивного интерпретатора байт-кода и нескольких программ для него заставит вас задуматься о таких вещах под капотом, которые обычно принимаются как само собой разумеющееся.
Например, когда я задумался о реализации процедур в SVM, я понял, что вызов функции это ничто иное как переход с дополнительным набором правил, с которыми неявно должны согласится и вызывающий, и вызываемый. Это помогло мне понять концепцию соглашения о вызове, а волшебные штуки вроде _cdecl и WINAPI вдруг стали иметь смысл.
Конечно, такой проект не научит вас всем хитрым нюансам С++ или С, но поможет сформировать правильный образ . В те годы я у меня был определенный ментальный барьер, из-за которого я не решался заглянуть внутрь черных ящиков, полных волшебства. Очень важно сломать этот барьер если вы собираетесь заниматься программированием серьезно, и особенно если вас интересует ~низкоуровневое программирование на языках вроде С++ или С. Такой управляемый контакт с "симулированным низкоуровневым" программированием научило меня не бояться segfault'ов и без страха работать с дизассемблером. Это очень помогло мне в карьере, и я считаю этот проект одним из самых важных в своей жизни.
Еще идеи
- Можно пойти чуть дальше и реализовать какие-нибудь графические возможности в вашей виртуальной машине. Можно даже написать простые игры!
- Попробуйте написать компилятор из простого высокоуровневого языка в ваш байт-код. К сожалению, я так и не написал компилятор для Stupid Virtual Machine (вместо этого я написал компилятор, генерирующий x86-ассемблер в рамках курса о компиляторах). Это было бы отличным упражнением, требующим некоторых дополнительных теоретических знаний.
- Заставить ваш интерпретатор работать максимально быстро — это еще одна интересная, но требующая усилий задача. Это не так уж просто.
Автор: freetonik
