Многие C++ программисты слышали про разработку через тестирование. Но почти все материалы по данной теме касаются более высокоуровневых языков и сосредоточены больше на общей теории, чем на практике. Итак, в данной статье я попробую привести пример пошаговой разработки через тестирование небольшого проекта на C++. А именно, как можно предположить из названия, простого интерпретатора математических выражений. Такой проект также является неплохой code kata, так как на его выполнение затрачивается не более часа (если не писать параллельно статью об этом).
Существует множество библиотек и инструментов, которые могут облегчить разработку интерпретаторов и компиляторов. Начиная от Boost.Spirit и заканчивая ANTLR и Bison. Можно даже запустить канал интерпретатора командной строки через popen и вычислить выражение через него. Целью данной статье является пошаговая разработка достаточно сложной системы с помощью TDD, поэтому будет использоваться только стандартная библиотека C++ и встроенный в IDE тестовый фреймворк.
Для начала, составим список того, что должен уметь наш простой интерпретатор, в порядке убывания приоритета:
Итак, создадим новый проект типа «Native Unit Test Project» и удостоверимся, что всё компилируется.
TEST_CLASS(LexerTests) {
public:
TEST_METHOD(Should_return_empty_token_list_when_put_empty_expression) {
Tokens tokens = Lexer::Tokenize("");
Assert::IsTrue(tokens.empty());
}
};
В CppUnitTestFramework макрос TEST_CLASS генерирует класс, в котором будут размещаться тестовые методы. Макрос TEST_METHOD , соответственно, создаёт сам тестовый метод. Необходимо учесть, что экземпляр класса создаётся только один раз перед запуском всех находящихся в нём тестов. В Boost.Test, к примеру, экземпляр класса создаётся каждый раз заново перед запуском каждого теста. Следовательно, тот, код, который необходимо выполнить перед каждым тестом, будет помещаться в метод, объявленный с помощью макроса TEST_METHOD_INITIALIZE , а тот, который после, в TEST_METHOD_CLEANUP . Все методы утверждений являются статическими и располагаются в классе Assert . Их немного, но основную функциональность они покрывают.
Вернёмся к нашему тесту. Он не то, чтобы не проходит, он даже не компилируется. Создадим функцию Tokenize в пространстве имён Lexer , принимающую строку и возвращающую std::vector, скрытый для удобства за псевдонимом Tokens . Я решил пока что не создавать дополнительные классы и ограничиться обычной функцией.
#pragma once;
#include
Сейчас проект компилируется, но тест, что было ожидаемо, падает. Для определения того, что же писать дальше, можно воспользоваться техникой The Transformation Priority Premise (TPP) авторства Роберта Мартина. Трансформации являются аналогами рефакторингов, но, в отличии от них, используются для изменения поведения кода, тогда как рефакторинг к изменению поведения не приводит. Каждая трансформация ведёт к изменению кода от более конкретного к более общему. Главная их особенность в том, что они имеют разные приоритеты, в зависимости от которых выбирается то, какой код писать для прохождения теста и какой будет следующий тест. А именно, те трансформации, которые проще (располагаются выше в списке) должны быть более предпочтительны, чем те, которые снизу. При намерении создать новый тест, выбирается такой, что для его прохождения нужно применить более простую трансформацию. Это не является строгим правилом, но следование TPP может вести к более простому коду за меньшее количество шагов.
Сам список трансформаций:
Inline Tokens Tokenize(std::string expr) { return{}; }
Посмотрим, что должен уметь лексер для выполнения первого пункта требований. Занесём это в список тестов.
TEST_METHOD(Should_tokenize_single_plus_operator) {
Tokens tokens = Lexer::Tokenize(L"+");
AssertRange::AreEqual({ Operator::Plus }, tokens);
}
Здесь AssertRange - это пространство имён, в которое я поместил функцию утверждения AreEqual , сравнивающую две последовательности, а точнее, список инициализации и последовательность.
AssertRange
namespace AssertRange {
template
Enum class Operator: wchar_t {
Plus = L"+",
};
typedef Operator Token;
Для успешной компиляции тестов, для каждого класса, экземпляр которого передаётся в статические методы класса Assert , необходимо определить функцию ToString , возвращающий его строковое представление.
std::wstring ToString(const Token &)
inline std::wstring ToString(const Token &token) {
return{ static_cast
Inline Tokens Tokenize(std::wstring expr) {
if(expr.empty()) { return{}; }
return{ static_cast
TEST_METHOD(Should_tokenize_single_digit) {
Tokens tokens = Lexer::Tokenize(L"1");
AssertRange::AreEqual({ 1.0 }, tokens);
}
Здесь возникает проблема представления токенов. С одной стороны, они должны хранить коды операторов, с другой - числа. Решений в данном случае, несколько:
Enum class TokenType {
Operator,
Number
};
class Token {
public:
Token(Operator) {}
TokenType Type() const { return TokenType::Operator; }
};
…
TEST_CLASS(TokenTests) {
public:
TEST_METHOD(Should_get_type_for_operator_token) {
Token opToken(Operator::Plus);
Assert::AreEqual(TokenType::Operator, opToken.Type());
}
};
Добавив метод ToString для перечисления TokenType и подправив аналогичный метод для самого токена, заставим всё компилироваться, а тесты проходить. Напишем следующий тест из списка.
TEST_METHOD(Should_get_type_for_number_token) {
Token numToken(1.2);
Assert::AreEqual(TokenType::Number, numToken.Type());
}
Он не проходит. Примени трансформацию (constant → scalar) для класса токена.
Class Token { public: Token(Operator) :m_type(TokenType::Operator) {} Token(double) :m_type(TokenType::Number) {} TokenType Type() const { return m_type; } private: TokenType m_type; };
TEST_METHOD(Should_get_operator_code_from_operator_token) {
Token token(Operator::Plus);
Assert::AreEqual
Для удобства преобразования токена к нужному типу будем использовать оператор неявного приведения.
Class Token {
public:
Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {}
operator Operator() const { return m_operator; }
…
Operator m_operator;
};
Аналогично напишем тест для числового токена.
TEST_METHOD(Should_get_number_value_from_number_token) {
Token token(1.23);
Assert::AreEqual
Так как в токене не может одновременно храниться и оператор, и число, то их поля можно объединить в union . Также добавим проверку на операцию приведения к неверному типу.
Token
class Token {
public:
Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {}
Token(double num) :m_type(TokenType::Number), m_number(num) {}
TokenType Type() const { return m_type; }
operator Operator() const {
if(m_type != TokenType::Operator) throw std::logic_error("Should be operator token.");
return m_operator;
}
operator double() const {
if(m_type != TokenType::Number) throw std::logic_error("Should be number token.");
return m_number;
}
private:
TokenType m_type;
union {
Operator m_operator;
double m_number;
};
};
inline std::wstring ToString(const Token &token) {
switch(token.Type()) {
case TokenType::Number: return std::to_wstring(static_cast
If(expr >= "0" && expr <= "9") {
return{ (double) expr - "0" };
}
return{ static_cast
Выгладит пока что не очень симпатично, но тест проходит.
Inline Tokens Tokenize(std::wstring expr) {
const wchar_t *current = expr.c_str();
if(!*current) return{};
if(iswdigit(*current)) return{ _wtof(current) };
return{ static_cast
После этого можно приступить и к более сложным тестам. Попробуем обработать полюс и число одновременно.
TEST_METHOD(Should_tokenize_plus_and_number) {
Tokens tokens = Lexer::Tokenize(L"+12.34");
AssertRange::AreEqual({ Token(Operator::Plus), Token(12.34) }, tokens);
}
Тест не компилируется, так как не хватает оператора сравнения для токена. Исправим это, теперь тест просто не проходит. Для начала сделаем небольшой рефакторинг. Добавим переменную result , в которую будем помещать токены.
Inline Tokens Tokenize(std::wstring expr) {
Tokens result;
const wchar_t *current = expr.c_str();
if(!*current) return result;
if(iswdigit(*current)) {
result.push_back(_wtof(current));
}
else {
result.push_back(static_cast
Теперь заставить пройти тест довольно просто: применим трансформацию (if → while). Можно было бы использовать рекурсию, но я решил целенаправленно делать не рекурсивный алгоритм.
Inline Tokens Tokenize(std::wstring expr) {
Tokens result;
const wchar_t *current = expr.c_str();
while(*current) {
if(iswdigit(*current)) {
wchar_t *end = nullptr;
result.push_back(wcstod(current, &end));
current = end;
}
else {
result.push_back(static_cast
Функция wcstod делает то же самое, что и _wtof , но также возвращает указатель на следующий за числом символ в строке. Так как все операторы на данный момент состоят из одного символа, то во втором случае просто передвигаем указатель на текущий символ на одну позицию вперёд. Как видим, теперь все тесты проходят.
TEST_METHOD(Should_skip_spaces) {
Tokens tokens = Lexer::Tokenize(L" 1 + 12.34 ");
AssertRange::AreEqual({ Token(1.0), Token(Operator::Plus), Token(12.34) }, tokens);
}
Применим (unconditional → if) добавив проверку на то, что символ является оператором.
While(*current) {
if(iswdigit(*current)) {
wchar_t *end = nullptr;
result.push_back(wcstod(current, &end));
current = end;
}
else if(*current == static_cast
На данном этапе проведём рефакторинг данной функции. Выделим логику в отдельный класс и разобьём на отдельный методы. Поместим этот класс в пространство имён Detail чтобы не засорять публичный интерфейс лексера. Теперь функция Tokenize просто будет служить фасадом для модуля лексера.
Inline Tokens Tokenize(const std::wstring &expr) {
Detail::Tokenizer tokenizer(expr);
tokenizer.Tokenize();
return tokenizer.Result();
}
Класс Detail::Tokenizer
namespace Detail {
class Tokenizer {
public:
Tokenizer(const std::wstring &expr) : m_current(expr.c_str()) {}
void Tokenize() {
while(!EndOfExperssion()) {
if(IsNumber()) {
ScanNumber();
}
else if(IsOperator()) {
ScanOperator();
}
else {
MoveNext();
}
}
}
const Tokens &Result() const { return m_result; }
private:
bool EndOfExperssion() const { return *m_current == L"\0"; }
bool IsNumber() const { return iswdigit(*m_current) != 0; }
void ScanNumber() {
wchar_t *end = nullptr;
m_result.push_back(wcstod(m_current, &end));
m_current = end;
}
bool IsOperator() const { return *m_current == static_cast
TEST_METHOD(Should_tokenize_complex_experssion) {
Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)");
AssertRange::AreEqual({
Token(1), Token(Operator::Plus), Token(2), Token(Operator::Mul), Token(3), Token(Operator::Div),
Token(Operator::LParen), Token(4), Token(Operator::Minus), Token(5), Token(Operator::RParen)
}, tokens);
}
Добавим необходимые операторы к перечислению Operator , чтобы заставить тест компилироваться.
Enum class Operator: wchar_t {
Plus = L"+",
Minus = L"-",
Mul = L"*",
Div = L"/",
LParen = L"(",
RParen = L")",
};
Тест не проходит. Чтобы это исправить необходимо всего лишь изменить метод IsOperator класса Tokenizer .
Bool IsOperator() const {
auto all = { Operator::Plus, Operator::Minus, Operator::Mul, Operator::Div, Operator::LParen, Operator::RParen };
return std::any_of(all.begin(), all.end(), (Operator o) {return *m_current == static_cast
Все тесты проходят и можно приступить к написанию парсера. Ниже приводится весь исходный код на данный момент.
Interpreter.h
#pragma once;
#include
InterpreterTests.cpp
#include "stdafx.h"
#include "CppUnitTest.h"
#include "Interpreter.h"
namespace InterpreterTests {
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
using namespace Interpreter;
using namespace std;
namespace AssertRange {
template
Рассказывает программист Вильям В. Вольд
На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием Pinecone. Я не рискну назвать его законченным, но использовать его уже можно - он содержит для этого достаточно элементов, таких как переменные, функции и пользовательские структуры данных. Если хотите ознакомиться с ним перед прочтением, предлагаю посетить официальную страницу и репозиторий на GitHub .
Я не эксперт. Когда я начал работу над этим проектом, я понятия не имел, что делаю, и всё еще не имею. Я никогда целенаправленно не изучал принципы создания языка - только прочитал некоторые материалы в Сети и даже в них не нашёл для себя почти ничего полезного.
Тем не менее, я написал абсолютно новый язык. И он работает. Наверное, я что-то делаю правильно.
В этой статье я постараюсь показать, каким образом Pinecone (и другие языки программирования) превращают исходный код в то, что многие считают магией. Также я уделю внимание ситуациям, в которых мне приходилось искать компромиссы, и поясню, почему я принял те решения, которые принял.
Текст точно не претендует на звание полноценного руководства по созданию языка программирования, но для любознательных будет хорошей отправной точкой.
«А с чего вообще начинать?» - вопрос, который другие разработчики часто задают, узнав, что я пишу свой язык. В этой части постараюсь подробно на него ответить.
Компилятор анализирует программу целиком, превращает её в машинный код и сохраняет для последующего выполнения. Интерпретатор же разбирает и выполняет программу построчно в режиме реального времени.
Технически любой язык можно как компилировать, так и интерпретировать. Но для каждого языка один из методов подходит больше, чем другой, и выбор парадигмы на ранних этапах определяет дальнейшее проектирование. В общем смысле интерпретация отличается гибкостью, а компиляция обеспечивает высокую производительность, но это лишь верхушка крайне сложной темы.
Я хотел создать простой и при этом производительный язык, каких немного, поэтому с самого начала решил сделать Pinecone компилируемым. Тем не менее, интерпретатор у Pinecone тоже есть - первое время запуск был возможен только с его помощью, позже объясню, почему.
Прим. перев. Кстати, у нас есть краткий обзор - это отличное упражнение для тех, кто изучает Python.
Своеобразный мета-шаг: язык программирования сам является программой, которую надо написать на каком-то языке. Я выбрал C++ из-за производительности, большого набора функциональных возможностей, и просто потому что он мне нравится.
Но в целом совет можно дать такой:
У структуры языка программирования есть несколько ступеней от исходного кода до исполняемого файла, на каждой из которых определенным образом происходит форматирование данных, а также функции для перехода между этими ступенями. Поговорим об этом подробнее.
Строка исходного кода проходит через лексер и превращается в список токенов.
Первый шаг в большинстве ЯП - это лексический анализ . Говоря по-простому, он представляет собой разбиение текста на токены, то есть единицы языка: переменные, названия функций (идентификаторы), операторы, числа. Таким образом, подав лексеру на вход строку с исходным кодом, мы получим на выходе список всех токенов, которые в ней содержатся.
Обращения к исходному коду уже не будет происходить на следующих этапах, поэтому лексер должен выдать всю необходимую для них информацию.
При создании языка первым делом я написал лексер. Позже я изучил инструменты, которые могли бы сделать лексический анализ проще и уменьшить количество возникающих багов.
Одним из основных таких инструментов является Flex - генератор лексических анализаторов. Он принимает на вход файл с описанием грамматики языка, а потом создаёт программу на C, которая в свою очередь анализирует строку и выдаёт нужный результат.
Я решил оставить написанный мной анализатор. Особых преимуществ у Flex я в итоге не увидел, а его использование только создало бы дополнительные зависимости, усложняющие процесс сборки. К тому же, мой выбор обеспечивает больше гибкости - например, можно добавить к языку оператор без необходимости редактировать несколько файлов.
Список токенов проходит через парсер и превращается в дерево.
Следующая стадия - парсер. Он преобразует исходный текст, то есть список токенов (с учётом скобок и порядка операций), в абстрактное синтаксическое дерево , которое позволяет структурно представить правила создаваемого языка. Сам по себе процесс можно назвать простым, но с увеличением количества языковых конструкций он сильно усложняется.
На этом шаге я также думал использовать стороннюю библиотеку, рассматривая Bison для генерации синтаксического анализатора. Он во многом похож на Flex - пользовательский файл с синтаксическими правилами структурируется с помощью программы на языке C. Но я снова отказался от средств автоматизации.
С лексером моё решение писать и использовать свой код (длиной около 200 строк) было довольно очевидным: я люблю задачки, а эта к тому же относительно тривиальная. С парсером другая история: сейчас длина кода для него - 750 строк, и это уже третья попытка (первые две были просто ужасны).
Тем не менее, я решил делать парсер сам. Вот основные причины:
В целесообразности решения меня убедило высказывание Уолтера Брайта (создателя языка D) в одной из его статей :
Я бы не советовал использовать генераторы лексических и синтаксических анализаторов, а также другие так называемые «компиляторы компиляторов». Написание лексера и парсера не займёт много времени, а использование генератора накрепко привяжет вас к нему в дальнейшей работе (что имеет значение при портировании компилятора на новую платформу). Кроме того, генераторы отличаются выдачей не релевантных сообщений об ошибках.
Переход от синтаксического дерева к семантическому графу
В этой части я реализовал структуру, по своей сути наиболее близкую к «промежуточному представлению» (intermediate representation) в LLVM. Существует небольшая, но важная разница между абстрактным синтаксическим деревом (АСД) и абстрактным семантическим графом (АСГ).
Грубо говоря, семантический граф - это синтаксическое дерево с контекстом. То есть, он содержит информацию наподобие какой тип возвращает функция или в каких местах используется одна и та же переменная. Из-за того, что графу нужно распознать и запомнить весь этот контекст, коду, который его генерирует, необходима поддержка в виде множества различных поясняющих таблиц.
После того, как граф составлен, запуск программы становится довольно простой задачей. Каждый узел содержит реализацию функции, которая получает некоторые данные на вход, делает то, что запрограммировано (включая возможный вызов вспомогательных функций), и возвращает результат. Это - интерпретатор в действии.
Вы, наверное, спросите, откуда взялся интерпретатор, если я изначально определил Pinecone как компилируемый язык. Дело в том, что компиляция гораздо сложнее, чем интерпретация - я уже упоминал ранее, что столкнулся с некоторыми проблемами на этом шаге.
Сначала мне понравилась эта мысль - я люблю делать вещи сам, к тому же давно хотел изучить язык ассемблера. Вот только создать с нуля кроссплатформенный компилятор - сложнее, чем написать машинный код для каждого элемента языка. Я счёл эту идею абсолютно не практичной и не стоящей затраченных ресурсов.
Сегодня совместными усилиями мы с вами создадим простенький скриптовый язык программирования. В нем не будет массивов или условных операторов, зато будут целочисленные переменные и множество операций над ними. Писать, как вы уже поняли, будем на замечательном языке Haskell . Также мы познакомимся с «компиляторами компиляторов» Alex и Happy.
Каким образом исходный код программы преобразуется в исполняемый файл? Это происходит в несколько шагов/этапов. Выходные данные, полученные на шаге N, служат входными данными для шага N+1. На вход такому «конвейеру» байт за байтом подается исходный код, а на выходе получается программа. Что же это за этапы?
Первый этап — это лексический анализ . На этом шаге код программы, скажем:
разбивается на лексемы (строки «foo», «=», «+», …), их которых затем получается последовательность токенов :
[ ИДЕНТ "foo", РАВНО, ИДЕНТ "foo", ПЛЮС, 1, ТОЧКА_С_ЗАПЯТОЙ ]
То есть, лексический анализатор разбивает программу на элементарные составные части — операторы, ключевые слова, имена переменных и тп. Также на этапе лексического анализа опционально удаляются комментарии, а запись 0b1101 преобразуется в число 13.
Выход лексического анализатора подается на вход синтаксическому анализатору (или парсеру ), задача которого заключается в проверке синтаксиса (такой штуки, которая не позволяет писать десять знаков равенства подряд) и преобразовании последовательности токенов в дерево синтаксического разбора . На этом этапе мы уже не беспокоимся о том, что в коде программы есть табуляции или переносы строк. Также мы точно знаем, что программа не содержит лексическую ошибку, то есть в ней нет несуществующих операторов или переменной, имя которой начинается с цифры.
Дерево разбора представляет собой структуру наподобие следующих:
Рассмотрим левое дерево. Читая его снизу вверх, получим «взять значение переменной a и число 1, сложить их, а затем присвоить результат переменной a», что в точности описывает поведение программы. Правое дерево наглядно демонстрирует, что при его построении были учтены приоритеты операторов, то есть сначала производятся умножение и деление и только потом сложение.
Также вы можете заметить, что ни одно из деревьев не содержит токена «точка с запятой». Вообще-то, узлы дерева могут содержать не токены, а какие-то другие типы данных. Или токены, но не те, что пришли от лексического анализатора. Скажем, инкремент (оператор ++) может быть преобразован в дерево, представленное слева.
Происходящее за лексическим и синтаксическим анализом зависит от решаемой задачи, реализации компилятора, пестрости рубашек его автора и тп. За ними может следовать (или не следовать) семантический анализ , цель которого состоит в обнаружении обращений к несуществующим переменным, вызовов функций с неверным числом аргументов и тп. Если мы пишем оптимизирующий компилятор, то за семантическим анализом последует оптимизация кода , затем — непосредственно генерация кода и, возможно, его оптимизация на уровне машинных команд.
Наш интерпретатор не будет генерировать никакого кода, работая напрямую с синтаксическим деревом. Семантика будет проверяться прямо во время интерпретации. Оптимизация производиться не будет.
Поскольку редкий компилятор (интерпретатор, транслятор, …) обходится без лексического и синтаксического анализатора, была написана масса генераторов этих самых анализаторов. «Компиляторы компиляторов» экономят время и силы, а также существенно сокращают количество багов в создаваемых с их помощью компиляторах. Мы воспользуемся генераторами Alex и Happy . Устанавливаются они, как и следовало ожидать, с помощью утилиты cabal.
Все исходники к этой заметке вы найдете в этом архиве . Если вас интересует самая свежая версия интерпретатора, доработанная уже после публикации заметки, вы можете скачать ее из репозитория на BitBucket .
Код лексического анализатора находится в файле Lex.x. Он слишком объемен, чтобы приводить его здесь целиком, но при этом не содержит какой-то особой магии. Мы просто определяем тип данных «токен»:
data
Token =
TInt Int
|
TIdent String
|
TPlus |
TMinus |
TMul |
TDiv |
TMod
|
...
instance
Show
Token where
show
x =
case
x of
TInt i ->
show
i
TIdent s ->
s
TModifSet ->
"="
TPlus ->
"+"
TMinus ->
"-"
TMul ->
"*"
TDiv ->
"/"
TMod ->
"%"
...
Примеры кода приведены на Python, однако подробные пояснения позволят читателю использовать для реализации любой другой удобный язык. В качестве интерпретируемого языка выбран Pascal, однако и здесь вы не будете ограничены - можно обратиться к любому другому языку, с семантикой которого вы хорошо знакомы.
Если вы не знаете, как работает компилятор, то вы не знаете, как работает компьютер. И если вы не уверены на 100%, что знаете, как работает компилятор, то вы не знаете, как он работает. - Стив Йиг
Небольшой ликбез перед прочтением. Компилятор - программа, которая переводит (транслирует) исходный код на языке программирования (высокого уровня) на язык, «более понятный компьютеру» (низкоуровневый). При этом программа сначала полностью транслируется, а затем выполняется. Интерпретатор - такой же транслятор, но выполняющий инструкции «на лету» (пооператорно, построчно), то есть без предварительной компиляции всего кода.
Различие между компилятором и интерпретатором
Почему вам нужно создать свой интерпретатор:
Что приятно, статьи подробно иллюстрируются. Создается впечатление, что автор перед вами ведет настоящую лекцию. Вот, например, одна из синтаксических диаграмм:
В конце каждой части руководства дается несколько задач для самостоятельной реализации и список полезных книг для более полного изучения вопроса. Итак, теперь приступайте к чтению:
Часть 1 . Основные понятия, разбиение на токены и сложение однозначных чисел.
Часть 2 . Обработка пробельных символов, многозначные числа.
Часть 3 . Синтаксические диаграммы, одиночные умножение и деление.
Часть 4. Множественные умножения и деления, форма Бэкуса-Наура.
Часть 5 . Калькулятор с произвольным числом операций, ассоциативность и порядок выполнения операторов.
Часть 6 . Заканчиваем калькулятор: произвольный уровень вложенности.
Некоторое время назад мне захотелось написать свой небольшой интерпретируемый скриптовый язык, просто ради фана, не ставя перед собой каких-либо серьезных задач. Я тогда активно читал известную волшебную книгу SICP (Структура и интерпретация компьютерных программ), и мне захотелось реализовать описываемые в ней абстракции - функции как объекты первого класса, замыкания, макросы и т.п. Параллельно я интересовался языком Haskell, и решил совместить приятное с приятным, и написать интерпретатор языка на нем. В моем языке должна была быть строгая семантика с вызовом по значению и мутабельные переменные. Получившийся язык Lisp-семейства я в своем локальном окружении связал с именем Liscript, полная реализация которого уместилась в примерно 250 строк, включая парсер, ядро и консольный/файловый ввод-вывод. Этого более чем хватало, чтобы ради интереса решать любые задачки, какими обычно мучают студентов, которых угораздило изучать Lisp по учебной программе.
По прошествии времени мне захотелось сделать к интерпретатору кроссплатформенный GUI-интерфейс с перспективой портирования на Android, поэтому я реализовал второй вариант интерпретатора на Java, внешний вид которого вы можете видеть на картинке выше. Да, он поддерживает графический вывод и вообще interoperability с Java, и этот Тетрис написан на Liscript, видна часть его кода. Кому интересны подробности - прошу под кат.
В рамках одной статьи сложно уместить все особенности языка и его реализации, а писать сериал из многих статей, начиная с пространного описания реализации парсера с помощью стандартной библиотеки мне скромность не позволит. (К слову сказать, в обоих реализациях - и на Haskell и на Java я не пользовался никакими библиотеками парсинга, а писал все вручную - на Haskell это заняло аж целых 10 строк кода). Поэтому некоторые вещи буду писать в стиле «пришел, увидел, победил». В общем, написал я парсеры текста в AST типов. Единственно, хочу отметить пару моментов - я не фанат скобочек, но легкость парсинга, гомоиконность кода (код как данные) и отсутствие инфиксных бинарных операторов с необходимостью учета приоритета и ассоциативности и разбора через Польшу или сортировочные станции с лихвой перевешивает все претензии к подобному синтаксису. В результате парсинга я получаю список, который передается функции интерпретации. В Java-реализации я не стал пользоваться библиотечными типами списков, а навеловипедил свой - простой, односвязный, потоконебезопасный и т.п.:
Заголовок спойлера
/** тип языка Liscript - односвязный список */
public static class ConsList {
/** объект - значение головы текущего списка */
public Object car;
/** список - значение хвоста текущего списка */
public ConsList cdr;
/** Конструктор со значениями головы и хвоста.
* @param h объект - голова списка
* @param t список - хвост списка
*/
ConsList(Object h, ConsList t) { car = h; cdr = t; }
/** проверяет, является ли список пустым
* @return истина/ложь
*/
public boolean isEmpty() { return this.car == null && this.cdr == null; }
/** возвращает размер списка
* @return размер
*/
public int size() {
int r = 0;
ConsList p = this;
while (!p.isEmpty()) {r += 1; p = p.cdr;}
return r;
}
/** @return строковое представление текущего списка */
@Override
public String toString() { return showVal(this); }
}
Заголовок спойлера
/** тип языка Liscript - функция */
public static class Func {
/** односвязный список имен параметров функции */
public ConsList pars;
/** тело функции */
public Object body;
/** окружение, в котором создана функция */
public Env clojure;
/** Конструктор
* @param p односвязный список имен параметров функции
* @param b тело функции
* @param c окружение, в котором создана функция
*/
Func(ConsList p, Object b, Env c) { pars = p; body = b; clojure = c; }
/** @return строковое представление функции */
@Override
public String toString() { return showVal(this); }
}
Также мне захотелось реализовать переменную арность особых форм прямо в ядре языка, а не потом в стандартной библиотеке. Многие из них допускают передачу ряда параметров и/или работают не совсем так, как их одноименные аналоги в других диалектах Lisp - это не усложняет реализацию интерпретатора. Пример работы с окружением (после => идет ответ интерпретатора):
++ "a1 = " a1 ", b1 = " b1 ", c1 = " c1 => a1 = a1, b1 = b1, c1 = c1 def a1 1 b1 (+ a1 1) (++ "c" a1) (+ a1 b1) => OK ++ "a1 = " a1 ", b1 = " b1 ", c1 = " c1 => a1 = 1, b1 = 2, c1 = 3 set! (++ "a" 1) 5 c1 10 => OK ++ "a1 = " a1 ", b1 = " (get (++ "b" 1)) ", c1 = " c1 => a1 = 5, b1 = 2, c1 = 10
Defn is-even (n) (cond (= n 0) true (is-odd (- n 1)))
=> OK
defn is-odd (n) (cond (= n 0) false (is-even (- n 1)))
=> OK
is-even 10000
=> true
is-even 10001
=> false
Особая форма tray позволяет печатать стек вызовов при применении функции. Вот так, например, происходит вычисление факториала от 3:
Заголовок спойлера
defn f (i) (cond (< i 2) 1 (* i (f (- i 1))))
=> OK
tray f 3
=>
1 (lambda (i) (cond (< i 2) 1 (* i (f (- i 1)))))
2 3
3 > false
3 3
4 (lambda (i) (cond (< i 2) 1 (* i (f (- i 1)))))
5 3
5 > 2
5 2
6 > false
6 2
7 (lambda (i) (cond (< i 2) 1 (* i (f (- i 1)))))
8 2
8 > 1
8 1
9 > true
8 > 1
7 > 1
6 > 2
5 > 2
4 > 2
3 > 6
2 > 6
1 > 6
6
Def m (macro (i r) (cond (<= i 0) "r (m (- i 1) (cons i r)))) => OK m 5 nil => (cons (- (- (- (- 5 1) 1) 1) 1) (cons (- (- (- 5 1) 1) 1) (cons (- (- 5 1) 1) (cons (- 5 1) (cons 5 nil))))) eval (m 5 nil) => (1 2 3 4 5)
Def m (java (class "java.util.HashMap") "new")
=> OK
java m "put" 1 "a"
=> OK
java m "put" "b" 2
=> OK
java m "get" 1
=> a
m
=> {1=a, b=2}
Таким образом мы можем получить доступ ко многим ресурсам языка реализации, в том числе и к графике. Вот такой код открывает отдельное окно с нарисованной красной линией на белом фоне:
(def image (java (class "java.awt.image.BufferedImage") "new" 100 100 1))
(def imageGraphics (java image "createGraphics"))
(java imageGraphics "setBackground" (java (class "java.awt.Color") "new" 255 255 255))
(java imageGraphics "clearRect" 0 0 100 100)
(java imageGraphics "setColor" (java (class "java.awt.Color") "new" 255 0 0))
(java imageGraphics "drawLine" 10 10 90 90)
(def icon (java (class "javax.swing.ImageIcon") "new"))
(java icon "setImage" image)
(def label (java (class "javax.swing.JLabel") "new"))
(java label "setIcon" icon)
(def window (java (class "javax.swing.JFrame") "new"))
(java window "setLayout" (java (class "java.awt.FlowLayout") "new"))
(java window "add" label)
(java window "setVisible" true)
(java window "pack")
Разумеется, можно выделить типичные блоки в отдельные функции или макросы и прописать их один раз в стандартной библиотеке, которая подгружается при старте интерпретатора. А поскольку интерпретатор реализует многопоточное выполнение задач в отдельных закладках с общим мутабельным окружением (да, я знаю, что выбранная в качестве хранилища словаря HashMap не является потокобезопасной и это может создать проблемы при одновременном изменении окружения из параллельных потоков, и лучше было применить HashTable), так вот, это позволяет в одной закладке запустить процедуру, вызывающую саму себя через определенное время ожидания по таймеру, а в другом окне (потоке) - процедуру, запрашивающую пользовательский ввод и выполняющую определенные действия. Так и был реализован Тетрис (с особенностью блокирующего пользовательского ввода - каждую команду надо подтверждать с помощью Ctrl+Enter).
Данный проект доступен на Github по адресу
