WiLang – виртуальная машина для экспериментального языка программирования

Введение

WiLang – это компактная экспериментальная виртуальная машина (VM) для исполнения байткода простого языка программирования. Проект нацелен на энтузиастов-разработчиков, интересующихся внутренним устройством интерпретаторов и виртуальных машин. WiLang реализует собственный набор инструкций (байткод) и модель выполнения, позволяющую выполнять базовые арифметические операции, управление потоком исполнения, работу с переменными, простейший ввод-вывод и даже поддерживает функции. Цель виртуальной машины – предоставить простую платформу, на которой можно изучать принципы работы стековых машин и создавать программы на игрушечном языке WiLang в байткоде. Проект находится в стадии разработки, но уже демонстрирует ключевые идеи архитектуры виртуальной машины и исполнения пользовательских программ.

Установка

WiLang написан на языке C# и требует установленной платформы .NET для сборки и запуска. Проект нацеливается на современные версии .NET (например, .NET 8.0 и выше). Для запуска виртуальной машины выполните следующие шаги:

1. Получение исходного кода: Убедитесь, что у вас есть файлы проекта WiLang (репозиторий содержит решение Visual Studio и исходники).

2. Сборка проекта: Откройте файл решения WiLang.sln в Visual Studio 2022 (или более новой) либо соберите проект с помощью командной строки. Для сборки через CLI перейдите в директорию WiLang/WiLang и выполните команду:

   dotnet build

   Убедитесь, что установлен соответствующий SDK .NET (проект может требовать .NET 8.0 или .NET 9.0 в зависимости от конфигурации). При успешной сборке появится исполняемый файл WiLang.dll (или exe) в директории WiLang/WiLang/bin/Debug/net8.0/ (или аналогичной под вашу целевую платформу .NET).

3. Запуск виртуальной машины: После сборки вы можете запустить примеры. Проект содержит точку входа (класс Program), которая демонстрирует работу VM. Выполните:

   dotnet run --project WiLang/WiLang/WiLang.csproj

   По умолчанию запускается встроенный пример (подробно о нем в следующем разделе). Вы должны увидеть вывод в консоли, например измерение времени выполнения цикла.

При необходимости вы можете изменить или добавить собственный код, вызывающий виртуальную машину, и снова выполнить сборку. Внешних зависимостей у проекта нет – достаточно установленного .NET SDK.

Пример использования

На данный момент WiLang не имеет полного высокоуровневого синтаксического фронтенда (парсера языка), поэтому программы для этой VM задаются непосредственно в виде последовательности инструкций байткода. Проще говоря, чтобы выполнить "программу", нужно вручную подготовить массив инструкций Instruction и передать его виртуальной машине на исполнение.

Рассмотрим минимальный пример: сложение двух чисел и вывод результата. Мы создадим набор инструкций, которые складывают 5 и 3, печатают сумму и останавливают выполнение:

using WiLang;

Instruction[] program = {
    new Instruction(It.PUSH, 5),       // Поместить число 5 на стек
    new Instruction(It.PUSH, 3),       // Поместить число 3 на стек
    new Instruction(It.ADD),           // Снять два верхних числа со стека, сложить и результат положить на стек
    new Instruction(It.PRINT),         // Взять верхнее значение со стека и вывести на консоль
    new Instruction(It.HALT)           // Остановить выполнение программы
};

var vm = new VM();
vm.Execv(program);

Запустив такой код, виртуальная машина выполнит следующие шаги:

• PUSH 5: кладет число 5 в стек VM. Сейчас на вершине стека значение 5.
• PUSH 3: кладет число 3 в стек. Теперь стек содержит 5 (внизу) и 3 (на вершине).
• ADD: снимает со стека два верхних значения (5 и 3), складывает их (получается 8) и результат 8 помещает обратно в стек. Теперь вершина стека равна 8.
• PRINT: берет верхнее значение из стека (8) и выводит его на экран (консоль). Стек при этом обычно остаётся с этим значением (команда PRINT заглядывает в вершину без удаления либо удаляет – в данной реализации значение просто считывается без необходимости повторного использования). Вы увидите в консоли напечатанное число 8.
• HALT: останавливает работу виртуальной машины. Цикл исполнения прерывается, программа завершена.

Этот простой пример показывает, как можно вручную задать последовательность команд для VM WiLang. Несмотря на отсутствие парсера, подобным образом можно конструировать и более сложные "программы" – например, циклы или условия – оперируя на уровне байткода. Ниже мы рассмотрим, как именно виртуальная машина работает внутри, и какие инструкции доступны.

Архитектура и внутреннее устройство

Виртуальная машина WiLang реализована по классической схеме стековой машины. Ниже описаны основные компоненты и принципы работы VM:

• Байткод и инструкции: Программа для WiLang представляется массивом структур Instruction. Каждая инструкция содержит код операции (opcode), определенный в перечислении It (Instruction Type), и необязательный аргумент. Аргумент (операнд) может быть значением (числом, строкой и т.д.), адресом перехода или именем переменной – в зависимости от конкретной инструкции. В текущей реализации байткод хранится в виде объектов C# (а не бинарного формата), но концептуально это последовательность команд виртуального процессора.
• Цикл исполнения: VM читает и выполняет инструкции последовательно с помощью счетчика инструкций (ip – instruction pointer). Внутри метода исполнения (Execv) организован цикл: пока указатель ip не достиг конца программы или явной остановки, VM берет очередную инструкцию, декодирует ее и выполняет соответствующее действие. Для реализации выбора действия используется большой switch по коду операции. После выполнения команды ip обычно увеличивается на 1, переходя к следующей инструкции, либо изменяется явным образом в случае команд перехода/вызова.
• Стек операций: Основной механизм вычислений – стек. WiLang VM имеет внутренний стек (структура WiStack<Variable>) для хранения временных значений во время исполнения программы. Инструкции типа PUSH помещают данные на стек, арифметические и логические операции снимают операнды со стека и кладут результат обратно. Стек работает по принципу LIFO (последним пришел – первым вышел). Размер стека по умолчанию ограничен (например, 1024 элементов), что можно изменить в коде, но при переполнении или недоступности нужного количества элементов VM выбросит исключение.
• Представление данных: WiLang поддерживает несколько типов значений: целые числа, числа с плавающей запятой, строки и списки. Все значения в стеке и переменных хранятся в унифицированном формате Variable – это структура, содержащая поле типа (VarType – код типа из enum Types, например TInteger, TFloat, TString, TList) и собственно значение (поле object Value, которое указывает на реальный объект, например int, float, string или List<Variable>). Такой вариант можно считать простой динамической типизацией на уровне VM: каждое значение несет информацию о своем типе, и операции в рантайме проверяют типы операндов. Для удобства, в коде определены обобщенные типы-обертки (WiNumber, WiFloat, WiString, WiList<T>) и соответствующие производные от WiValue (например, WiNumberValue, WiStringValue и т.д.) с перегрузкой операторов неявного преобразования. Благодаря этому, при создании инструкции можно просто передать стандартный тип (например, int или строку) – он автоматически будет упакован в соответствующий WiLang-тип. Внутри VM же вся логика оперирует через структуру Variable и перечисление типов.
• Арифметика и логика: Виртуальная машина реализует основные арифметические операции над числами. Интересной особенностью является автоматическое приведение типов при некоторых операциях. Например, если сложить целое и число с плавающей точкой, VM приведет целое к дробному и получит результат как float. Операция сложения (ADD) перегружена также для строк и списков: сложение строк приводит к их конкатенации, а сложение списка с чем-либо добавляет элемент в список (или объединяет два списка). Такие возможности заложены перегрузкой операторов для структуры Variable – например, operator+ проверяет типы операндов и выполняет соответствующее действие. В случае недопустимой операции (например, попытка поделить строку на число) VM выбросит исключение с сообщением об ошибке.
• Память переменных: Помимо стека, VM имеет простейшую память для хранения переменных. Это словарь Dictionary<string, Variable> – по сути, ассоциативный массив, где ключом выступает имя переменной (строка), а значением – структура Variable (значение с типом). Инструкция STORE сохраняет верхнее значение из стека в переменную с заданным именем (берет имя как аргумент), а инструкция LOAD загружает значение переменной в стек (по имени из аргумента). Переменные в WiLang являются глобальными и типизируются динамически по значению (то есть можно в одну переменную присвоить число, потом строку – тип хранится вместе со значением). Если попытаться загрузить неинициализированную переменную, VM сообщит об ошибке.
• Вызовы функций: Для поддержки подпрограмм WiLang предоставляет инструкции CALL и RET. Реализован простой механизм без параметров вызова: инструкция CALL принимает в качестве аргумента адрес (индекс) начала функции в массиве байткода и осуществляет переход на этот адрес, предварительно сохранив адрес возврата (текущий ip + 1) в специальном стеке возвратов. Стек вызовов (callStack) хранит номера инструкций, на которые нужно вернуться после окончания функции. Инструкция RET выполняет возврат – извлекает последний сохраненный адрес из стека вызовов и устанавливает его как текущий ip, продолжая выполнение уже после места вызова. Таким образом, можно организовывать простые функции: например, основная программа вызывает CALL на набор инструкций, оканчивающихся RET. Аргументы и возвращаемое значение функции можно передавать через основной стек: поместив требуемые данные перед вызовом и прочитав результат из стека после возврата (аналогично соглашению вызова через стек). Следует отметить, что локальных переменных или изолированного пространства имен для функций нет – используется общий стек и общие глобальные переменные.
• Управление потоком (переходы): В VM имеются инструкции условных и безусловных переходов для реализации логики ветвлений и циклов. JUMP выполняет безусловный переход на указанный в аргументе номер инструкции (изменяет ip на новое значение, продолжая исполнение оттуда). JZ и JNZ – условные переходы, зависящие от флага/значения на вершине стека. Эти инструкции извлекают верхнее значение из стека (обычно это результат какого-то сравнения или вычисления) и интерпретируют его как условие: JZ (Jump if Zero) прыгает на заданный адрес, если извлеченное значение равно нулю (или эквивалентно "false"), а JNZ (Jump if Not Zero) – если значение ненулевое ("true"). Таким образом реализуются конструкции вроде if (проверкой значения и переходом через блок кода) или while (прыжком назад к началу цикла). В текущей реализации булевых типов как таковых нет, поэтому за ложь/истину отвечают числовые значения (0 как ложь, 1 или любое ненулевое как истина), получаемые, например, результатом сравнения. Инструкции сравнения (LT, GT и пр.) как правило оставляют на стеке 0 или 1, подходящие для последующего JZ/JNZ. При некорректном использовании (например, если аргумент перехода не указан или не число) VM бросит исключение. Команда HALT безусловно останавливает выполнение программы, мгновенно выходя из цикла исполнения.

Архитектура WiLang довольно минималистична: в ней отсутствуют сложные оптимизации или JIT-компиляция – каждая инструкция интерпретируется последовательно. Тем не менее, благодаря использованию неявных преобразований и агрессивногоInlining (атрибуты MethodImplOptions.AggressiveInlining в коде) выполнение работает достаточно быстро для учебных примеров. Главным выигрышем простоты архитектуры является ее прозрачность – разработчики могут легко проследить, как управляются данные через стек, как хранятся переменные и выполняются функции.

Возможности

Несмотря на статус "work in progress", виртуальная машина WiLang уже поддерживает существенный набор возможностей, позволяющий создавать нетривиальные программы. Ниже перечислены основные инструкции байткода и их назначение (разбитые по категориям):

• Арифметические операции: – ADD – сложение: снимает два верхних числа со стека, складывает и помещает результат обратно. Поддерживает целые и вещественные числа, а также конкатенацию строк и объединение списков. – SUB – вычитание: вычитает второе число в стеке из первого (то есть выполняет a - b, где a было ниже b в стеке). – MUL – умножение двух чисел (аналогично, берет два верхних числа). – DIV – деление одного числа на другое. Если оба операнда целые, выполняется целочисленное деление. При наличии дробного операнда выполняется деление с плавающей точкой. Деление на ноль не обрабатывается специально (приведет к исключению .NET). – MOD – остаток от деления (только для целых чисел). – POW – возведение в степень. (Эта инструкция объявлена в коде, но пока не реализована в VM.) – SQRT – извлечение квадратного корня: берет число (int или float) с вершины стека, вычисляет sqrt и кладет результат (тип результата всегда дробный, TFloat). Если попытаться взять корень из строкового или другого недопустимого типа, возникнет ошибка.

• Инкремент/декремент: – INC – увеличить на 1: снимает верхний элемент-число, добавляет 1 (сохраняя тип – целые увеличиваются как целые, вещественные как вещественные) и возвращает в стек. – DEC – уменьшить на 1: аналогично, вычитает 1 из числа.

• Операции сравнения: – LT, GT – сравнение "<" (меньше) и ">" (больше). Берут два значения из стека (a и b) и сравнивают a с b. Если условие выполняется, на стек кладется 1 (истина), иначе 0 (ложь). Например, после LT вершиной стека будет 1, если a < b. Поддерживается сравнение чисел (целых и дробных; при необходимости целые автоматически сравниваются как дробные). Для строк сравнение выполняется лексикографически. Если сравнение неприменимо (например, список с числом), может быть ошибка. – LE, GE – сравнение "≤" (меньше либо равно) и "≥" (больше либо равно). Работают аналогично, возвращая 1 или 0 на вершину стека. – EQ, NE – проверка равенства и неравенства. Сравнивают два верхних значения на стеке. Возвращают 1, если равны (EQ) или если не равны (NE). Для разных типов значений неявного приведения нет – разные типы считаются не равными (например, число 5 и строка "5" будут не равны без предварительного приведения).

• Работа со стеком: – PUSH – поместить значение в стек. Аргументом может быть литерал (число, строка и т.д.) или сложный объект. Например, PUSH 10 кладет 10, PUSH "hello" кладет строку, PUSH с аргументом-списком кладет список. Без аргумента использование недопустимо. – POP – удалить верхнее значение из стека (без использования его). Применяется, например, чтобы отбросить ненужный результат. Если стек пуст, возникает ошибка. – DUP – дублировать вершину стека. Берет текущий верхний элемент и помещает его копию наверх. После DUP стек увеличится на один элемент, причем два верхних будут идентичны. Это полезно, например, для повторного использования значения без его удаления.

• Переменные и память: – STORE – сохранение переменной. Берет верхнее значение из стека и сохраняет его в переменную с именем, указанным в аргументе инструкции. Пример: STORE "x" вынимает из стека значение и кладет его в переменную x. После этого стек на единицу короче, а переменная x хранит сохраненное значение (с его типом). – LOAD – загрузка переменной. Аргументом является имя переменной. Инструкция находит значение переменной в словаре и помещает копию этого значения на вершину стека. Например, LOAD "x" найдет переменную x и загрузит ее значение в стек. Если переменная не определена, выполнение прерывается с ошибкой.

• Управление потоком выполнения: – JUMP – безусловный переход. Аргумент – индекс инструкции (обычно рассчитывается от начала программы, начиная с 0). Когда VM встречает JUMP, она устанавливает счетчик ip на заданное значение, и следующий шаг исполнения продолжится с этой инструкции. Используется для переходов (goto) или организации циклов. – JZ – условный переход (Jump if Zero). Проверяет состояние вершины стека: если значение равно 0 (либо считается ложным), то выполняется переход на адрес, указанный в аргументе. Иначе исполнение просто продолжается со следующей командой. Обычно перед JZ ставится инструкция сравнения или вычисления условия, оставляющая 0 или 1 на стеке. Обратите внимание: JZ потребляет значение условия из стека (оно извлекается). – JNZ – условный переход (Jump if Not Zero). Противоположность JZ: переходит по указанному адресу, если снятое со стека значение не равно 0 (истина). Если значение 0, переход не выполняется. Эта инструкция позволяет организовать, например, циклы while (прыжок назад, пока условие истинно). (В текущей версии VM инструкция JNZ присутствует в enum, однако реализация может быть не завершена, поэтому для условного перехода используется в основном JZ с инверсией логики условия.) – HALT – останов. Безусловно завершает выполнение программы. При выполнении этой инструкции VM прерывает цикл интерпретации независимо от ip. Рекомендуется всегда ставить HALT в конец программы (если, конечно, программа не заканчивается переходом в другое место), чтобы гарантировать корректный выход.

• Вызовы функций: – CALL – вызов подпрограммы. Аргументом служит адрес (индекс) начала функции в байткоде. При выполнении CALL виртуальная машина помещает в стек вызовов адрес следующей инструкции (то есть точку, куда нужно вернуться), затем устанавливает ip на значение аргумента – начинается выполнение кода функции. По сути, CALL – это прыжок с сохранением точки возврата. – RET – возврат из подпрограммы. Берет последний сохраненный адрес из стека вызовов и устанавливает его как текущий ip. Таким образом, после RET выполнение продолжится с инструкции, следующей за тем CALL, из которого произошел переход. Если стек вызовов пуст (нет адреса для возврата), происходит ошибка. Обычно каждая функция должна завершаться инструкцией RET, чтобы вернуть управление.

• Ввод-вывод: – PRINT – вывести значение. Берет верхний элемент стека (не удаляя его) и печатает его на консоль. Для чисел происходит вывод числа, для строки – вывод текста без кавычек, для списка – выводится его текстовое представление (например, [1, 2, 3]). После PRINT значение остается на стеке (в реализации WiLang оно просто читается). – INPUT – ввод строки. Останавливает исполнение, ожидая ввод текста пользователем (из стандартного ввода, консоли). Считанная строка (без символа новой строки) помещается как значение типа TString на вершину стека. Если пользователь просто нажал Enter, вернется пустая строка "". С помощью INPUT можно организовать простейшие интерактивные программы, где, например, введенное значение потом преобразуется в число (через CASTI) и участвует в вычислениях.

• Преобразование типов: – CASTI – (cast to int) преобразовать в целое. Снимает верхнее значение стека и пытается привести его к типу Integer. Если значение было числом с плавающей точкой, оно округляется/отсекается до целого; если строка – парсится как число (поддерживается только формат целого числа); если список или несовместимый тип – произойдет ошибка. Результат (целое число) кладется на стек. – CASTF – преобразовать в число с плавающей запятой (Float). Работает аналогично: например, строку пытается разобрать как число с десятичной точкой, целое преобразует к дробному (5 -> 5.0). – CASTS – преобразовать в строку. Любое значение превращается в строковое представление. Числа станут строками их десятичного представления, булевые 0/1 – "0" или "1", списки – форматом вроде [elem1, elem2, ...]. Эта операция удобна для вывода на печать сложных значений или конкатенации через ADD (сложение строк).

• Операции со списками: (Поддержка списков находится в начальной стадии, и инструкции могут быть недоработаны.) – LISTGET – получить элемент списка по индексу. Предполагается, что эта инструкция возьмет из стека индекс (целое число) и сам список, и вернет запрошенный элемент. Например, LISTGET при вершине стека 0 и под ним списке [10,20,30] должна поместить в стек число 10 (элемент под индексом 0). На данный момент реализация может отсутствовать или работать не полностью. – LISTPUT – поместить элемент в список по индексу. Ожидаемое действие: взять из стека значение и список, поместить значение в список по заданному индексу (из аргумента или из стека) или в конец. В текущей версии не реализовано. – LISTRM – удалить элемент из списка. Должна удалять элемент по индексу или совпадающий со значением. Также, скорее всего, пока не реализовано.

Как видно, набор возможностей достаточно широк для экспериментов: можно создавать арифметические вычисления, использовать условия (EQ/JZ и прочие), циклы (JUMP назад и условие), хранить и считывать переменные, определять простейшие функции и вызывать их, работать со строками (ввод/вывод, конкатенация) и даже начинать работу со структурами данных (списки).

Стоит подчеркнуть, что WiLang – стековая виртуальная машина: большинство команд берут операнды из стека и возвращают результат в стек, что упрощает модель исполнения (не нужно адресовать регистры напрямую). Это приближает WiLang к классическому байткоду, наподобие байткода JVM или .NET IL, хотя набор команд гораздо проще.

Ограничения и планы развития

Проект WiLang находится в стадии разработки, поэтому имеются определенные ограничения и области для будущего улучшения:

• Отсутствие полноценного языка и парсера: На данный момент нет реализованного компилятора или интерпретатора высокого уровня для WiLang. Пользователь не может писать код на специальном синтаксисе и запускать его напрямую. Существуют заделы под лексер/токенайзер (в коде есть пространство имен Tokenizer), но они помечены как TODO. В планах разработчиков – реализовать разбор исходного текста языка WiLang (возможно, синтаксис будет похож на Си-подобный или псевдокод), который будет транслироваться в байткод для виртуальной машины. Пока этого нет, программы приходится составлять вручную в виде последовательности инструкций, как показано в примерах.

• Не полностью реализованные инструкции: Некоторые инструкции, заявленные в перечислении opcode, еще не имеют реализации или не отлажены. Например, JNZ упомянут, но логика условия "не ноль" может не обрабатываться (в текущей версии можно обходиться комбинацией EQ и JZ для аналогичного эффекта). Также POW (возведение в степень) и операции со списками (LISTGET, LISTPUT, LISTRM) пока фактически не работают или не проверены. Эти инструкции обозначены на будущее – очевидно, планируется добавить поддержку операций над списками (доступ по индексу, модификация) и математическую функцию возведения в степень. В текущей версии при попытке их использования VM скорее всего выбросит исключение "неизвестная инструкция" или просто не имеет соответствующего кейса обработки.

• Ограниченный набор типов: WiLang поддерживает лишь четыре базовых типа данных (integer, float, string, list). Отсутствуют, например, булевый тип (вместо него используются числовые 0/1), символы/char, словари/ассоциативные массивы (хотя списки могут частично заменить). Расширение набора типов возможно в будущем – например, введение отдельного boolean-типа или поддержка пользовательских структур – но это потребует изменений в системе Variable и инструкциях. Пока упор сделан на минимально достаточный набор типов для демонстрации работы VM.

• Глобальные переменные и отсутствие областей видимости: Все переменные хранятся в одном глобальном словаре. Виртуальная машина не разделяет область видимости между функциями или блоками – любой STORE/LOAD всегда относится к глобальному имени. Это упрощение, подходящее для малого языка, но в будущем, с развитием проекта, возможно появление локальных переменных или передачи параметров в функции через стек. Это может потребовать реализации активационных записей (stack frame) или другой модели, если проект усложнится.

• Обработка ошибок и стабильность: В текущем состоянии WiLang в основном полагается на выбрасывание исключений при неверном использовании (например, стек пуст, неправильный тип операнда, неизвестное имя переменной и т.д.). Эти сообщения полезны разработчику, но пользовательского механизма обработки ошибок нет. В планах может быть улучшение сообщений об ошибках, ввод проверок (например, предотвращение выхода за границы списка, проверка деления на ноль) и, возможно, реализация инструкций для безопасных операций.

• Производительность и оптимизации: Хотя VM уже способна выполнять миллионы инструкций (цикл на 10 млн итераций демонстрируется в примере Program.cs и работает довольно быстро), есть пространство для оптимизации. Например, можно реализовать более эффективную технику диспетчеризации команд (вместо большого switch, который JIT-компилятор .NET, правда, уже оптимизирует, можно рассмотреть таблицу делегатов или прямую адресацию – т.н. threaded code). Также, возможно, планируется оптимизация работы со стеком (например, динамическое расширение вместо фиксированного размера, или использование Span<T> для операций) и с переменными (введение адресации переменных по индексу вместо имени для ускорения, хотя для маленьких программ это не критично). В исходном README проекта упомянуты "Some optimizations" в списке TODO – вероятно, автор рассматривает подобные улучшения производительности.

• Документация и примеры: Как и многие молодые проекты, WiLang пока не имеет обширной документации. Данный README призван заполнить этот пробел. В будущем, по мере добавления новых функций (например, когда появится парсер языка), необходимо будет описать синтаксис WiLang, добавить больше примеров использования, возможно, написать подробное руководство или wiki. На данный момент энтузиастам предлагается изучать исходный код VM (который достаточно компактный и читаемый) и экспериментировать, создавая собственные последовательности инструкций.

В заключение, WiLang – это увлекательный учебный проект, демонстрирующий принципы построения виртуальной машины. Несмотря на текущие ограничения, структура проекта позволяет легко расширять функциональность. План развития очевиден: завершение поддержки всех задуманных инструкций, разработка фронтенда для удобного написания программ, и улучшение надежности. Для разработчиков, интересующихся тем, "как это сделано", WiLang предоставляет отличную возможность заглянуть под капот виртуальной машины и даже поучаствовать в ее совершенствовании. Проект открыт под лицензией MIT, так что вы можете экспериментировать с кодом, вносить улучшения и использовать VM WiLang в своих учебных целях. Удачного погружения во внутреннее устройство виртуальных машин!

Tokens, Lexer, Some optimizations.