Предисловие
Случается, что навязчивая идея так прочно заседает в голове, что ты возвращаешься к ней снова и снова на протяжении многих лет. Пытаешься подойти к проблеме с другой стороны, воспользоваться новыми знаниями, или же просто начать все еще раз с чистого листа — и так до тех пор, пока вопрос не будет исчерпан раз и навсегда. Для меня такой идеей-фикс стали языки программирования. Сам факт того, что одна программа позволяет создавать другие программы, в моих глазах наделял ее непостижимой фрактальной красотой. Написание такой программы самому стало лишь вопросом времени.
В первый раз время наступило после второго курса. Я был уверен, что полученных знаний языка C мне хватит, чтобы в одиночку написать и компилятор, и виртуальную машину, и всю стандартную библиотеку к нему. Задумка была элегантна и дышала романтикой юношеского максимализма, но вместо этого результатом двух лет прилежной работы стало монструозное нечто. Даже несмотря на то, что виртуальная машина подала признаки жизни и смогла исполнить довольно несложные скрипты на псевдоассемблере, который помог написать боевой товарищ fornever, проект был вскоре заброшен. Вместо этого было решено написать язык для платформы .NET, чтобы нахаляву получить автоматическую сборку мусора, jit-компилятор и все прелести огромнейшей библиотеки классов. Компилятор был реализован всего за полгода, исходный код выложен на CodePlex, и с ним я успешно защитил диплом.
Однако чего-то по-прежнему не хватало. При всех своих преимуществах, разработанный для диплома язык требовал явного объявления всех типов и функций, не имел никакой поддержки generic'ов, не умел создавать анонимные функции, да и вообще область его применения была неясна. Решение изобрести еще один велосипед пришло спустя год, когда мне написал знакомый, учившийся на моей же кафедре на два года младше. Он предложил «помочь» ему в написании дипломной работы, и я согласился. К новому языку были поставлены следующие требования:
- Взаимодействие с любыми доступными типами .NET без явного импорта
- Поддержка generic'ов
- Поддержка анонимных функций и замыканий
- Наличие хоть какой-нибудь практической ценности
Вышеупомянутый fornever изъявил желание поучаствовать, и работа закипела. Он принимал активное участие в создании дизайна языка и написал парсер на F#, а я занялся описанием синтаксического дерева и внутренней инфраструктуры.
На днях знакомый защитил-таки свой диплом, поэтому репозиторий проекта на Github теперь открыт для всех желающих. Дальше в статье я расскажу о том, что в результате получилось, какие подводные камни встретились на пути, и почему у статьи такой желтый заголовок.
Кому нужен очередной велосипед?
Почти три года назад в какой-то из тем на хабре мы выяснили, что языков программирования в мире по-прежнему больше 2500. Зачем кому-то может пригодиться еще один? Что в нем вообще может быть такого, чего нет в других?
Ошеломляющий успех JavaScript и Lua стал поводом сделать язык встраиваемым, с упором на интеграцию с хост-приложениями под .NET. Отсюда же появилось название проекта — LENS — сокращение от Language for Embeddable .NET Scripting. Под «интеграцией» понимается возможность объявить в скрипте тип или функцию, а также обмен непосредственно объектами между внешней и встроенной программами во время выполнения. Например, вот так:
public void Run()
{
var source = "a = 1 + 2";
var a = 0;
var compiler = new LensCompiler();
compiler.RegisterProperty("a", () => a, newA => a = newA);
try
{
var fx = compiler.Compile(source);
fx();
Console.WriteLine("Success: {0}", a);
}
catch (LensCompilerException ex)
{
Console.WriteLine("Error: {0}", ex.FullMessage);
}
}
Как видно из примера, подключить поддержку LENS очень просто: достаточно добавить сборку в Reference'ы проекта, создать экземпляр и скормить ему исходный код. Вся «магия» заключается в методе RegisterProperty — с его помощью любое значение из программы-хоста может стать доступно в скрипте как на чтение, так и на запись. Для типов и функций существуют методы RegisterType и RegisterFunction соответственно.
Возможности языка
С точки зрения синтаксиса язык LENS почерпнул многое из языков Python и F#. За десять лет работы с C-подобными языками точки с запятой и фигурные скобки набили оскомину, поэтому тут выражения завершаются переносом строки, а блоки выделяются отступами.
Базовые типы
Базовыми типами считаются bool, int, double и string. Константы этих типов записываются так же, как в C#.
Объявление переменных
Переменные объявляются с помощью ключевых слов var и let. Первое объявляет изменяемую переменную, второе — переменную только для чтения.
let a = 42
var b = "hello world"
Управляющие конструкции
Условие записывается с помощью блока if, циклы — с помощью while:
var a = 1
while(a < 10)
if(a % 2 == 0)
print "{0} is even" a
else
print "oops, {0} is odd" a
a = a + 1
Управляющие конструкции возвращают значение. Это значит, что if может также использоваться по правую сторону от знака присваивания:
let description = if(age < 21)
"child"
else
"grown-up"
Функции
Как видно из примера чуть выше, вызов функции print осуществляется в функциональном стиле: сначала имя функции или объект-делегат, а следом аргументы, разделенные пробелами. Если в качестве аргумента нужно передать выражение сложнее литерала или имени переменной, оно берется в скобки.
print "test"
print a b c
print "result is: " (1 + 2)
Для вызова функции без параметров используется пара пустых скобок. Дело в том, что в функциональной парадигме нет такого понятия, как «функция без параметров». Тру-функциональщики предпочитают оперировать только чистыми функциями, а чистая функция без аргументов по сути является константой. Пара пустых скобок в данном случае — литерал типа unit (синоним void), который обозначает отсутствие аргументов. Аналогичным образом вызывается конструктор без параметров.
Объявление функции начинается с ключевого слова fun:
fun launch of bool max:int name:string ->
var x = 0
while(x < max)
println "{0}..." x
x = x - 1
print "Rocket {0} name is launching!" name
let rocket = new Rocket ()
rocket.Success
countdown 10
В LENS нет ключевого слова return. Возвращаемым значением функции является ее последнее выражение. Если функция не должна ничего возвращать, но последнее выражение имеет какой-то тип, используется уже знакомый литерал (). Ключевые слова break и continue также не предусмотрены.
В версии, над которой работаем в данный момент, функцию будет можно автоматически сделать мемоизируемой. Для этого используется ключевое слово pure перед описанием функции. Мемоизируемые функции кешируют свои значения в словаре: если функция уже однажды была вызвана с таким набором параметров, ее значение будет получено из этого словаря, а не вычислено заново:
pure fun add of int x:int y:int ->
print "calculating..."
x + y
add 1 2 // output
add 2 3 // output
add 2 3 // no output!
Пользовательские структуры и алгебраические типы
С помощью ключевого слова record можно описать структуру и список ее полей.
record Point
X : int
Y : int
let zero = new Point ()
let one = new Point 1 1
Алгебраические типы объявляются ключевым словом type и списком вариантов, которые этот тип может принимать. Вариант может также иметь метку произвольного типа:
type Card
Ace
King
Queen
Jack
ValueCard of int
let king = King
let ten = ValueCard 10
print (ten is Card) // true
Для структур создается конструктор по умолчанию и конструктор, инициализирующий все поля сразу. Также для встроенных типов автоматически создаются методы Equals и GetHashCode, позволяющие использовать их в качестве ключей в словарях.
Контейнеры
Для инициализации часто используемых контейнеров используется особый синтаксис оператора new:
let array = new [1; 2; 3; 4; 5]
let list = new [[ "hello"; "world" ]]
let tuple = new (13; 42.0; true; "test")
let dict = new { "a" => 1; "b" => 2 }
Для контейнеров автоматически выводится наиболее подходящий общий тип. Например:
let a = new [1; 2; 3.3] // double[]
let b = new [King; Queen] // Card[]
let c = new [1; true; "hello"] // object[]
Extension-методы
Если в настройках не отключен соответствующий флаг, компилятор будет также искать подходящие методы-расширения:
let a = Enumerable::Range 1 10
let sum = a.Product ()
С помощью несколько хитроумного синтаксиса поддерживается LINQ:
let oddSquareSum = Enumerable::Range 1 100
|> Where ((x:int) -> x % 2 == 0)
|> Select ((x:int) -> x ** 2)
|> Sum ()
Кроме того
В компиляторе реализовано еще много любопытных вещей:
- Константные выражения вычисляются во время компиляции
- Поддерживаются переопределенные операторы
- Поддерживается классическая обработка исключений в виде trycatch
- Сгенерированную сборку можно сохранить в .exe, если в нее ничего не импортировано
- Описанные в коде функции можно использовать как extension-методы
Так что там про Липперта?
Многие из дочитавших статью аж досюда наверняка томятся в ожидании — где же обещанная драма? Помню-помню, но сначала лирическое отступление.
Backend'ом для компилятора является замечательная библиотека Reflection.Emit, входящая в состав .NET Framework. Она позволяет на лету создавать типы, методы, поля и прочие сущности, а код методов описывается с помощью команд языка MSIL. Однако наряду с широкими возможностями в ней есть и изрядное количество досадных подводных камней.
Первая проблема, с которой я столкнулся, заключалась в невозможности инспектировать создаваемые типы:
var intMethods = typeof(int).GetMethods(); // все работает
var myType = ModuleBuilder.DefineType("MyType");
myType.DefineMethod("Test", MethodAttributes.Public);
myType.GetMethods(); // NotSupportedException
На stackoverflow мне доходчиво объяснили, что хранение списка созданных методов, равно как и поиск по ним, придется реализовывать ручками. Трудоемко, зато не сложно.
Но дальше — больше.
Оказалось, что инспектировать нельзя не только созданные типы, но и встроенные generic-типы, которые используют созданные в качестве параметров! Вот пример класса, попытка создать который на Reflection.Emit вызовет проблему:
class A
{
public List<A> Values = new List<A>();
}
Получается замкнутый круг: получить конструктор типа List<A> можно только тогда, когда сборка уже финализирована и он больше не нужен.
На мой очередной вопрос на Stackoverflow мне ответили Джон Скит (автор книги C# in Depth) и Эрик Липперт (до недавнего времени ведущий разработчик C#). Вердикт Эрика был неутешителен и бесповоротен:
Reflection.Emit is too weak to use to build a real compiler. It's great for little toy compilation tasks like emitting dynamic call sites and expression trees in LINQ queries, but for the sorts of problems you'll face in a compiler you will quickly exceed its capabilities.
Reflection.Emit слишком слаба, чтобы строить на ней настоящий компилятор. Она подходит для «игрушечных» задач компиляции вроде создания динамических вызовов или деревьев выражений в запросах LINQ, но для решения проблем настоящего компилятора ее возможностей быстро перестанет хватать.
По словам Эрика, правильнее всего было бы переписать компилятор с использованием Common Compiler Infrastructure, но этот вариант я даже не рассматривал. Первым пришедшим в голову решением было исключить из языка возможность объявлять собственные типы, но это было бы неспортивно. Чутье подсказывало, что обязательно должен быть какой-то неочевидный способ, позволяющий обойти данное ограничение.
И такой способ действительно был! Он даже оказался куда более очевидным, чем я ожидал.
Как мне подсказали на том же stackoverflow, у класса TypeBuilder есть статические методы, позволяющие получить метод, поле или свойство следующим образом:
var myType = createType("MyType");
var listType = typeof(List<>);
var myList = listType.MakeGenericType(myType);
var genericMethod = listType.GetMethod("Add");
var actualMethod = TypeBuilder.GetMethod(myList, genericMethod);
Тут, однако, есть существенный недостаток: в возвращаемом методе не подставлены типы аргументов. Результатом будет дескриптор метода List<MyType>.Add(T item): тип аргумента будет именно T (generic parameter), а не ожидаемый MyType.
Устранение этого недостатка потребовало реализовать алгоритм, который бы вычислял значения типов аргументов из описаний содержащего типа и базового метода, а потом подставлял их на нужные места. Вместе с методами TypeBuilder эти два механизма позволили обойти замкнутый круг.
Вывод — даже великие иногда ошибаются, а на Reflection.Emit можно сделать полнофункциональный компилятор. Правда, придется как следует попариться.
Если кому-то любопытно узнать больше об ограничениях Reflection.Emit, советую почитать статью в блоге MSDN, написанную еще в 2009 году. Там приводится несколько примеров топологий классов, которые нельзя сгенерировать. Осторожно, примеры на VB!
Чудеса мемоизации
Впилив в язык поддержку мемоизации, я вдруг задумался — не может ли эта практика улучшить скорость работы самого компилятора? Одной из наиболее часто используемых в компиляторе является функция TypeDistance. Она вычисляет относительное расстояние наследования или преобразования между двумя типами, которое требуется для:
- Проверки возможности приведения выражения к типу
- Поиска наиболее подходящего overload'а метода
- Определения наиболее подходящего общего типа для коллекции
Метод этот содержал в себе больше десятка всевозможных проверок и занимал немалую долю от времени компиляции. Но расстояние между двумя типами не меняется со временем, поэтому его вполне можно закешировать в словарь типа Dictionary<Tuple<Type, Type>, int>. Мемоизация трех ключевых методов заняла где-то полчаса и сократила время компиляции нескольких сложных скриптов примерно в 60 раз.
Будущее проекта
В данный момент компилятор работает стабильно и проходит более двухсот тестов. Его уже можно применять в реальных проектах, но это отнюдь не значит, что работа завершена. Основная задача — переписать парсер с F# на C#. Использование библиотеки FParsec для построения парсеров себя не оправдало, и поддерживать изменения в грамматике стало невыносимо. Кроме того, она предоставляет довольно скудные возможности для вывода сообщений об ошибках и тащит за собой весь F# runtime и 500 килобайт зависимостей. Если учесть, что весь код компилятора занимает 250 кб, это очень много.
По этой причине некоторые возможности уже реализованы в компиляторе, однако до сих пор не поддерживаются в парсере — малейшие изменения в грамматике вызывают лавинообразную волну обрушения тестов. Среди таких «фишек» — цикл for/foreach, раздел finally при обработке исключений и мемоизация функций, а также небольшие облагораживания синтаксиса.
В остальном фронт работ примерно следующий:
- Добавить поддержку сопоставления с образцом (pattern matching)
- Добавить поддержку инициализаторов объектов
- Разрешить объявлять обобщенные методы и, возможно, структуры
- Добавить поддержку подписки на события
- Описать все возможности в документации
Пока мы работаем над проектом только вдвоем, но возможно среди читателей найдутся единомышленники — тогда работа пойдет быстрее. В более далеких планах — поддержка языка в Visual Studio и генерация отладочных символов.
Где можно попробовать?
Весь исходный код доступен в репозитории на гитхабе:
В проекте есть три тестовых программы-хоста, на которых можно проверить работу компилятора. Для их работы потребуется F# Redistributable. Если у вас установлена Visual Studio 2010 и старше, ничего ставить не нужно.
Консоль
Самый простой хост для компилятора. Программа вводится построчно или грузится из файла. Для запуска нужно поставить в конце строки символ #.
Графопостроитель
Позволяет построить график двухмерной функции по ее формуле в виде y = f(x). Можно задать диапазон и шаг.
(Картинки кликабельны)
Графическая песочница
Наиболее функциональное хост-приложение. Оно предоставляет скрипту типы Circle и Rect, которые можно отображать на экране и описывать логику их поведения. В комплекте есть несколько демонстрационных скриптов.
