В форумах я часто вижу вопросы от начинающий программистов на С++: «какую посоветуете литературу?». Обычно я отвечаю набором надежных книг с дополнением: никакое количество прочитанных книг не заменит практику. Нужно на самом деле делать что-то. Но что? Что может быть хорошим проектом? Нужно что-то, что научит многому, но при этом достаточно простое и интересное, чтобы не заскучать. Я недавно задумался над этим вопросом, и, кажется, нашел ответ. Вам несомненно стоит написать интерпретатор байт-кода. Для меня такой проект оказал решающее значение в становлении всей последующей карьеры.
Как все началось
В 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-ассемблер в рамках курса о компиляторах). Это было бы отличным упражнением, требующим некоторых дополнительных теоретических знаний.
- Заставить ваш интерпретатор работать максимально быстро — это еще одна интересная, но требующая усилий задача. Это не так уж просто.
Комментарии (24)
xuexi
23.09.2016 12:23+1Раз в год где-то в течение человекомесяца я делаю компилятор для нового языка программирования.
Безудержное веселье...DmitryKoterov
23.09.2016 13:26+3Есть такой замечательный язык Forth, который представляет собой квинтэссенцию стекового подхода. Распространялся он, например, в виде небольшого com-файла (даже не exe), который содержал в себе одновременно и компилятор, и IDE, и саму исполняемую программу. Т.е. запускаем его — открывается командная строка, в ней можно писать код программы и отлаживать, а по готовности — вызывается процедура, которая все написанное сбрасывает в этот же самый com-файл.
FForth
23.09.2016 16:45Современные реализации Forth (Форт) создают оптимизированный под архитектуру процессора код.
mxms
24.09.2016 14:02Как раз хотел написать, что для понимания как всё работает каждый программист должен написать однажды свой Forth :-)
Antikiller
23.09.2016 14:10+1У меня дважды был подобный опыт выхода «за скобки».
Первый — учебник Зубкова, рассылка уроков с wasm.ru (ох, тогда e-mail-рассылки были как хабра), и ночи неуклюжего программирования под DOS. Иногда я ностальгирую на один из немногих сохранившихся с того времени исходников, и прекрасно понимаю, что за те несколько ночей узнал об архитектуре вычислительных машин не меньше, чем за институтский курс. Впечатления сопоставимы с описываемыми автором: раньше компьютер был «чёрным ящиком», после стал понятным, хотя и сложным, устройством.
Второй раз — когда я открыл для себя Logisim. Меня захлестнуло: я залип, и запилил себе процессор, и ассемблер к нему. До сих пор жалею, что не хватило свободного времени довести штуку до желаемого состояния, но как же было увлекательно!MacIn
23.09.2016 17:32Меня захлестнуло: я залип, и запилил себе процессор, и ассемблер к нему. До сих пор жалею, что не хватило свободного времени довести штуку до желаемого состояния, но как же было увлекательно!
Круто. Меня тоже как-то захлестнуло, закончилось приличной дипломной работой: эмулятор процессора, архитектура которого тоже разработана мной. Вместе с микрокодом, транслятором для него, демонстрационной реализацией системы команд и ассемблера для этой системы.
MacIn
23.09.2016 17:31Например, когда я задумался о реализации процедур в SVM, я понял, что вызов функции это ничто иное как переход с дополнительным набором правил, с которыми неявно должны согласится и вызывающий, и вызываемый. Это помогло мне понять концепцию соглашения о вызове, а волшебные штуки вроде _cdecl и WINAPI вдруг стали иметь смысл.
Вы извините, но для этого достаточно просто пописать немного код на самом обычном языке ассемблера для x86, например. Также руками заполняется стек, регистры, в зависимости от конвенции.
A-Stahl
Возможно написание интерпретатора и будет полезным, но также это будет и весьма скучным занятием.
В чём основное веселье программирования? В получении полезного результата. Как можно получать удовольствие от выполнения изначально бесперспективной работы? А без веселья нет энтузиазма. А без энтузиазма нет результата. Замкнутый круг. А без результата любая работа — просто потраченное время.
Когда я был маленьким и только начинал писать код, то ассемблерные вставки в сишном коде не считались ещё чем-то дурацким. А ковыряние с ассемблером вполне даст те же знания и навыки, о которых вы говорите. И при этом можно не ограничивать себя унылейшей «академической» задачей. Я писал игры (я и сейчас пишу игры).
А от вашего проекта на километр несёт курсовой работой:)
AndreySu
«Веселье программирования» не обязательно должно вести к полезному результату. Это как разгадываение нового кроссворда, весело.
igor_suhorukov
Верно, в университете для этого самое время. Помню с трепетом читал в библиотеке «Компиляторы: принципы, технологии и инструменты» (Книга дракона)
poxu
Да, я неоднократно слышал эти слова от энергичных менеджеров. Однако ж лучшим программистам из тех, которых я видел на результат нередко откровенно наплевать. Результат это для них побочный продукт процесса, от которого они получают искреннее удовольствие.
SerCe
Это скорее может быть про очень хороших. Лучшие же как раз и лучшие, потому что они получают удовольствие как от процесса, так и от результата.
Хотя, конечно, все зависит от смысла слова "лучший" :)
poxu
Или от смысла слова "программист" :). Смешно, но не все понимают его одинаково.
Аналогии лживы, но я приведу одну. Вот есть у нас спортсмен, который любит ходить на тренировки и получает от этого искреннее удовольствие. А соревнования он не любит, скучные они, смысла в них особого нет, кроме как продемонстрировать окружающим правильную методику. Но иногда участвует, потому что за это можно получить приз. И, собственно, регулярно получает, без особого напряга.
Veliant
Стоит заметить, что в большинстве серьезных коммерческих защит (Themida, VMProtect, и прочие) как раз используются виртуальные машины с динамическим байт-кодом
NeoCode
Ну а как еще изучать что-то? Пока не попробуешь сам написать — не поймешь.
Я помню, в институте была курсовая, писали эмулятор процессора (правда регистровый). Сразу с GUI, чтобы отображались все регистры, память команд и данных, стек.
А в реальной практике был проект, когда писал виртуальную машину (эмуляция процессора, памяти и доступ к периферии), работающую внутри микроконтроллера, и компилятор с языка высокого уровня для этого виртуального процессора. Представляете, какое это удовольствие — написать
программу на собственном языке программирования в собственной среде разработки, скомпилировать собственным компилятором и запустить на собственном процессоре в реальном железе!
A-Stahl
>Ну а как еще изучать что-то? Пока не попробуешь сам написать — не поймешь.
Разумеется. Я с этим не спорю. Но писать интерпретатор? Серьёзно? Что может быть унылей? Интерпретаторы и парсеры это, вероятно, самые рутинные и грустные задачи с которыми может столкнуться программист.
Во всяком случае для меня это так.
MacIn
Сам процесс — да, уныл, но результат — нет.
Visseri
да.это лампово) до сих пор помню, как писали программы на ассемблере на занятиях по Архитектуре ЭВМ
MacIn
Нам довелось писать в машинных кодах под VAX, совсем, кстати, недавно.
Wladimir83
Пусть и "несёт", как вы выразились курсовой, но написана она блестяще :-)
Visseri
Все относительно и зависит от интереса и любопытства самого человека. Кому-то скучно писать программы, которые только принесут какой-то там результат, потому что в них может быть не так много развития на самом деле. Кто-то хочет развиваться и для него это как раз весело, а кто-то — нет.
xuexi
Игрострой, в свою очередь, как предметная область известен, практически, весь, в шесть слоёв покрыт каким-то диким количеством движков, делающих хорошо даже без нажатия кнопки. Весь интерес программиста — написать посредственный glue-код для ассетов из unity store и заплатить дизайнеру с композитором. Скука.
То ли дело из ничего создать full stack (процессор, ассемблер, компилятор ЯВУ, ОС), да на какой-нибудь хитрой аппаратной платформе.