Я хочу, чтобы цель самообразования реализовала простую виртуальную машину для динамического языка, предпочитайте C. Что-то вроде Lua VM или Parrot или Python VM, но проще. Есть ли хорошие ресурсы/учебные пособия для достижения этого, помимо изучения кода и проектной документации существующих виртуальных машин?
Изменить: зачем закрывать голос? Я не понимаю - это не программирование. Прошу прокомментировать, если у меня возникла проблема с моим вопросом.
Я предполагаю, что вы хотите виртуальную машину, а не просто интерпретатор. Я думаю, что они представляют собой две точки континуума. Интерпретатор работает над чем-то близким к исходному представлению программы. VM работает над более примитивными (и автономными) инструкциями. Это означает, что вам нужен этап компиляции, чтобы перевести один в другой. Я не знаю, хотите ли вы работать над этим первым или если у вас еще есть синтаксис ввода.
Для динамического языка вы хотите где-то хранить данные (как пары ключ/значение) и некоторые операции, которые действуют на него. VM поддерживает хранилище. Программа, запущенная на нем, представляет собой последовательность инструкций (включая поток управления). Вам необходимо определить набор инструкций. Я бы предложил простой набор, например:
Вы можете использовать метод вычисления на основе стека для арифметики, как это делают многие виртуальные машины. В приведенном выше обзоре пока нет много динамических изменений. Для этого нам нужны две вещи: способность вычислять имена переменных во время выполнения (это просто означает операции с строкой) и некоторая обработка кода как данных. Это может быть так же просто, как разрешить ссылки на функции.
Вход в виртуальную машину в идеале должен быть в байт-коде. Если у вас еще нет компилятора, это может быть создано из базового ассемблера (который может быть частью виртуальной машины).
Сама ВМ состоит из цикла:
1. Look at the bytecode instruction pointed to by the instruction pointer.
2. Execute the instruction:
* If it an arithmetic instruction, update the store accordingly.
* If it control flow, perform the test (if there is one) and set the instruction pointer.
* If it print, print a value from the store.
3. Advance the instruction pointer to the next instruction.
4. Repeat from 1.
Работа с именами вычисляемых переменных может быть сложной: команде необходимо указать, какие переменные вычисленны в именах. Это можно сделать, разрешив инструкциям ссылаться на пул строковых констант, предоставленных на входе.
Пример программы (в сборке и байт-коде):
offset bytecode (hex) source
0 01 05 0E // LOAD 5, .x
3 01 03 10 // .l1: LOAD 3, .y
6 02 0E 10 0E // ADD .x, .y, .x
10 03 0E // PRINT .x
12 04 03 // GOTO .l1
14 78 00 // .x: "x"
16 79 00 // .y: "y"
Коды команд подразумеваются:
"LOAD x, k" (01 x k) Load single byte x as an integer into variable named by string constant at offset k.
"ADD k1, k2, k3" (02 v1 v2 v3) Add two variables named by string constants k1 and k2 and put the sum in variable named by string constant k3.
"PRINT k" (03 k) Print variable named by string constant k.
"GOTO a" (04 a) Go to offset given by byte a.
Вам нужны варианты, когда переменные называются другими переменными и т.д. (и уровни косвенности становятся сложными для рассуждения). Ассемблер рассматривает аргументы типа "ADD.x,.y,.x" и генерирует правильный байт-код для добавления из строковых констант (и не вычисленных переменных).
Ну, это не о внедрении VM в C, но поскольку это была последняя вкладка, которую я открыл, прежде чем я увидел этот вопрос, мне кажется, что мне нужно указать о реализации компилятора и виртуальной машины QBASIC byteecode в JavaScript с использованием тега <canvas> для отображения. Он включает весь исходный код для получения достаточного количества QBASIC, реализованного для запуска игры "nibbles", и является первым в серии статей по интерпретатору компилятора и байт-кода; этот описывает VM, и он обещает будущие статьи, описывающие компилятор.
Кстати, я не голосовал, чтобы закрыть ваш вопрос, но закрытое голосование было как дубликат вопроса от прошлого года о том, как узнать о внедрении виртуальной машины. Я думаю, что этот вопрос (об учебнике или что-то относительно простое) отличается от того, что он должен оставаться открытым, но вы можете захотеть обратиться к нему за некоторыми советами.
Еще один ресурс, на который нужно обратить внимание - это реализация языка Lua. Это виртуальная машина на основе реестра, которая имеет хорошую репутацию в производительности. Исходный код находится в ANSI C89 и, как правило, очень читаем.
Как и в большинстве высокопроизводительных языков сценариев, конечный пользователь видит читаемый динамический язык высокого уровня (с такими функциями, как замыкания, хвостовые вызовы, неизменяемые строки, числа и хеш-таблицы в качестве основных типов данных, функционирует как значения первого класса, и более). Исходный текст скомпилирован для байт-кода VM для выполнения реализацией VM, схема которого в значительной степени описана в ответе Эдмунда.
Значительные усилия были направлены на то, чтобы реализация самой виртуальной машины была как переносной, так и эффективной. Если требуется еще больше производительности, только в компиляторе времени из байтового кода виртуальной машины в собственные инструкции существует для 32-разрядного x86 и находится в бета-версии релиз для 64-разрядной версии.
Для запуска (даже если не C, но С++) вы можете посмотреть muParser.
Это анализатор математического выражения, который использует простую виртуальную машину для выполнения операций. Я думаю, что даже вам нужно время, чтобы все понять; в любом случае этот код более прост, чем полная виртуальная машина, способная запускать реальную полную программу. (Кстати, я разрабатываю подобный lib на С# - это его ранние этапы, но в следующих версиях разрешена компиляция .NET/VM IL или, может быть, новая простая виртуальная машина, такая как muParser).
Еще одна интересная вещь: NekoVM (она исполняет .n файлы байт-кода). Это проект с открытым исходным кодом написанный на C, и считается, что основной язык (.neko) генерируется источник-источник-компилятор. В духе последней темы см. Haxe от того же автора (с открытым исходным кодом тоже).
Как и я, я также изучал виртуальные машины и компиляторы, и одна хорошая книга, которую я могу порекомендовать, - это Compiler Design: Virtual Machines. Он описывает виртуальные машины для императивных, функциональных, логических и объектно-ориентированных языков, предоставляя набор команд для каждой виртуальной машины вместе с учебником о том, как скомпилировать язык более высокого уровня для этой виртуальной машины. Я только применил виртуальную машину для императивного языка, и это было очень полезным упражнением.
Если вы только начинаете, то другой ресурс, который я могу порекомендовать, PL101. Это интерактивный набор уроков в JavaScript, который поможет вам в процессе реализации парсеров и интерпретаторов для разных языков.