SPARD и генерация кода
Вчера я опубликовал на сайте серьёзное обновление интерпретатора SPARD, которое, в том числе, включает в себя первую версию механизма кодогенерации. Что это значит и зачем это нужно?
Одна из целей языка - дать обычным людям (не программистам) возможность писать несложные программы. Произвольный человек должен быть способен без особых усилий разобраться в языке и описать решение собственной задачи. Лично у меня бывают ситуации, когда нужно в тексте выполнить несколько замен или структурных перестановок, ну или возникает необходимость произвести сложный поиск. Наконец, у лингвистов может быть потребность писать программы по обработке текстов. Код программ наподобие "ab* => 1" или "[X] => [X][X]" понятен практически каждому.
Здесь возникает проблема зависимости от интерпретатора SPARD и встраивания SPARD-программы в бОльшую программу. Поскольку язык интерпретируемый, для его работы нужен испольнитель. Испольнителя нужно "брать с собой", включать в итоговый проект. Это не всегда удобно. Кроме того, интерпретируемый язык работает достаточно медленно (каждая инструкция анализируется).
Поэтому я разработал компилятор SPARD (пока обрабатывается лишь небольшое число конструкций), точнее преобразователь для табличного преобразователя. Рассмотрим схему преобразования программы на SPARD:
Исходный текст программы на SPARD с помощью парсера переводится в древовидную форму. Каждая строка программы превращается в дерево из шаблонов. Этот основной вид преобразовтаеля - интерпретатор SPARD, выполняющий программу так, как она записана.
Мы уже разбирали ситуацию, при которой в программе есть правила "abcd1 => 1" и "abcd2 => 2". Древовидный преобразователь, обрабаывая строку "abcd2", сначала пройдется по первому правилу (найдя "abcd"), затем увидит "1", споткнется, вернётся к началу и уже затем двинется по второму правилу. А если таких правил с общими частями много? А если ещё и каждое правило содержит подобную многозначность? Возвратов может быть очень много, и именно поэтому возникают задержки выполнения.
Для решения проблем достаточно вынести общие левые части правил за скобки, записав как-то так: abcd(1 => 1|2 => 2). Это псевдокод, на SPARD'е так писать нельзя. Но суть вы поняли: проверить всё за один раз и никогда не возвращаться. Так и работает табличный преобразователь: он никогда не возвращается обратно по тексту. Всю нужную информацию о прочитанных ранее символах он "берёт с собой". По мере чтения символов преобразователь переходит из одного состояния в другое, постепенно выдавая наружу результат. Очень удобно. Единственно но: построить табличный преобразователь по древовидному - задача крайне нетривиальная. Поэтому в настоящий момент поддерживаются лишь некоторые конструкции SPARD - символы, конкатенация, ИЛИ, переменные, => и шаблон _.
Переводом одного преобразователя в другой занимается третий преобразователь :) (Любую серьёзную задачу можно рассматривать как преобразование). Он назван на схеме "Генератором диаграмм", т.к. строит по деревьям диаграммы перехода. Сил на него ушло весьма много - месяц вечеров и выходных работы.
Табличный преобразователь работает, естественно, гораздо быстрее древовидного. Но и он требует наличие исполнителя - интерпретатора SPARD.
Поэтому и возникла задача сгенерировать на основе преобразователя код, который способен выполняться самостоятельно. То есть программа, в которой уже нет SPARD'а, а есть просто набор инструкций. Как видно на схеме, генерировать код можно из любой из преобразователей, но, поскольку табличный эффективнее, за основу был выбран именно он.
На выходе кодогенератора можно получить: исходный код на другом (более распространённом) языке программирования (чтобы вставить его в свой проект или сразу же скомпилировать), исполняемый код в виде .dll и .exe (если преобразование самодостаточно, например, если это стеммер языка) или функцию в памяти (это оносится только к .NET решениям, использующим интерпретатор SPARD as a service). Последний вариант специфичен и был отложен. Генерация исполняемого кода - вещь неблагодарная: зачем соревноваться в эффективности с существующими компиляторами (например, того же C++)? Они всё равно знают своё дело лучше. Поэтому и было принято решения заняться на данном этапе генерацией исходного кода (скомпилировать его потом можно и самостоятельно).
Выбранный путь превращения кода на SPARD в код на другом ЯП показан на схеме красными стрелками. При последовательности преобразований сама суть преобразования не меняется, но меняется способ, которым оно достигается.
Далее встал вопрос о типе языка, на который нужно будет переводить SPARD-программу. Должен ли он быть декларативным или императивным? Так как SPARD является сам по себе декларативным языком, а императивные языки позволяют генерировать более эффективную программу, то не было смысла генерирвать преобразование из декларативного ЯП в декларативный ЯП. Поэтому была избрана императивная парадигма.
В качестве целевого языка в конечном итоге был выбран C# (так как он мне роднее). В перспективе планируется поддержка C++ (для высокоэффектиных решений) и JavaScript (для осуществления преобразований в вебе).
Надо понимать, что к генерируемому коду предъявляются другие требования, нежели к коду рукописному. Генериуемый код обычно не будут править; важна лишь его эффективность. Поэтому можно не чураться, например, операции goto и других запретных прелестей - важно лишь, чтобы получался эффективнфй код.
Итак, могу заявить, что задача кодогенерации на C# успешно решена. Возникли проблемы с обработкой табличных преобразователей, имеющих более 65535 состояний (класс на C# не может иметь бОльшее число функций, чем это), но в реальных задачах это число обычно недостижимо. На решение ушло ещё полмесяца.
А теперь рассмотрим реальные примеры.
Сразу же вопрос: зачем тогда писать на SPARD'е и компилировать программу в C#, если можно сразу же писать на C#? Ответ: некоторые преобразования очень тяжело описать руками. А тут раз - и получается работающая программа.
Предположим, вам нужно заменить в тексте все вхождения символа "a" на символ "b". Вы можете напистаь преобразование на C# в виде:
public string Transform(string text)
{
return text.Replace("a", "b");
}
Для одного символа легко. А если у вас текст - не строковая переменная, а это поток (скажем, получаемый из LINQ-запроса)?
public IEnumerable Transform(IEnumerable text)
{
foreach (var c in text)
{
if (c == 'a')
yield return 'b';
else
yield return c;
}
}
Какой же код создаст кодогенератор?
Смотрим:
public IEnumerable Transform(IEnumerable input)
{
foreach (var item in input)
{
if (item == 'a')
{
yield return 'b';
}
else
{
yield return item;
}
}
}
Абсолютно такой же, не правда ли? А вы всего-то и написали, что "a => b". А тут вам уже готовая программа. Удобно ведь, не правда ли?
Пока было очень легко. А если нужно выполнить несколько замен? Такой код руками писать уже гораздо труднее.
По ссылке вы можете перейти к странице табличного преобразователя, самостоятельно нагенерить код для разных конструкций и убедиться в том, что многие преобразования запрограммировать руками нелегко.
Рассмотрим пример посложнее: "a|b|c => 1":
public IEnumerable Transform(IEnumerable input)
{
foreach (var item in input)
{
switch (item)
{
case 'a':
yield return '1';
break;
case 'b':
yield return '1';
break;
case 'c':
yield return '1';
break;
default:
{
yield return item;
break;
}
}
}
}
Здесь уже есть некоторая неоптимальность (три case'а можно было бы объединить в один), но оптимизация подобного - дело будущего.
Ну и наконец пример "abc => 1". Код здесь получается немного сложнее (с несколькими состояниями и контекстом преобразования):
using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;
namespace Spard.Output
{
public sealed class Transformer
{
private bool error;
public bool Error { get { return this.error; } }
private sealed class Context: Dictionary { }
private sealed class Result
{
internal IEnumerable Data { get; set; }
internal Context Vars { get; set; }
internal Result(IEnumerable data)
{
this.Data = data;
this.Vars = new Context();
}
}
private Context vars = new Context();
private List results = new List();
private bool beforeStart = true;
public IEnumerable Transform(IEnumerable input)
{
this.error = false;
this.results.Clear();
this.vars = new Context();
var state = 0;
foreach (var item in input)
{
this.beforeStart = false;
switch (state)
{
case 0:
{
if (item == 'a')
{
AppendVar("Y", item);
InsertResult(context => context["Y"].ToString());
state = 1;
}
else
{
yield return item;
Reset();
}
break;
}
case 1:
{
switch (item)
{
case 'b':
AppendVar("Y", item);
InsertResult(context => context["Y"].ToString());
state = 2;
break;
case 'a':
AppendVar("Y", item);
InsertResult(context => context["Y"].ToString());
foreach (var r in ReturnResult(1))
yield return r;
state = 1;
break;
default:
{
AppendVar("Y", item);
foreach (var r in ReturnResult())
yield return r;
{
var context = this.results.Count == 0 ? this.vars : this.results[this.results.Count - 1].Vars;
foreach (var r in context["Y"].ToString())
yield return r;
}
state = 0;
Reset();
break;
}
}
break;
}
case 2:
{
switch (item)
{
case 'c':
InsertResult(-1);
yield return '1';
state = 0;
Reset();
break;
case 'a':
AppendVar("Y", item);
InsertResult(context => context["Y"].ToString());
foreach (var r in ReturnResult(1))
yield return r;
state = 1;
break;
default:
{
AppendVar("Y", item);
foreach (var r in ReturnResult())
yield return r;
{
var context = this.results.Count == 0 ? this.vars : this.results[this.results.Count - 1].Vars;
foreach (var r in context["Y"].ToString())
yield return r;
}
state = 0;
Reset();
break;
}
}
break;
}
}
if (state == -1)
{
foreach (var r in this.results)
{
foreach (var rItem in r.Data)
{
yield return rItem;
}
}
this.error = true;
yield break;
}
}
if (this.beforeStart)
yield break;
switch (state)
{
case 1:
{
foreach (var r in ReturnResult())
yield return r;
state = 0;
Reset();
break;
}
case 2:
{
foreach (var r in ReturnResult())
yield return r;
state = 0;
Reset();
break;
}
default:
state = -1;
break;
}
if (state == -1)
{
foreach (var r in this.results)
{
foreach (var rItem in r.Data)
{
yield return rItem;
}
}
this.error = true;
yield break;
}
}
private void Reset()
{
this.vars.Clear();
this.results.Clear();
this.beforeStart = true;
}
private void InsertResult(int remove, Func> result)
{
if (remove == -1)
this.results.Clear();
else
this.results.RemoveRange(results.Count - remove, remove);
var context = this.results.Count == 0 ? this.vars : this.results[this.results.Count - 1].Vars;
this.results.Add(new Result(result(context)));
}
private void InsertResult(int remove, IEnumerable result = null)
{
if (remove == -1)
this.results.Clear();
else
this.results.RemoveRange(results.Count - remove, remove);
if (result != null)
{
this.results.Add(new Result(result));
}
}
private void InsertResult(Func> result)
{
var context = this.results.Count == 0 ? this.vars : this.results[this.results.Count - 1].Vars;
this.results.Add(new Result(result(context)));
}
private void InsertResult(IEnumerable result)
{
this.results.Add(new Result(result));
}
private void InsertResult()
{
this.results.Add(new Result(""));
}
private IEnumerable ReturnResult(int left = 0)
{
var count = this.results.Count;
var take = count - left;
var res = this.results.Take(take).ToArray().SelectMany(r => r.Data);
if (take > 0)
{
this.vars = this.results[take - 1].Vars;
this.results.RemoveRange(0, take);
}
return res;
}
private void AppendVar(string name, char item, int depth = 0)
{
var contextIndex = this.results.Count - depth;
var context = contextIndex == 0 ? this.vars : this.results[contextIndex - 1].Vars;
StringBuilder var;
if (context.TryGetValue(name, out var))
var.Append(item);
else
context[name] = new StringBuilder(item.ToString());
}
private void CopyVar(string source, string target, int depth = 0)
{
var contextIndex = this.results.Count - depth;
var context = contextIndex == 0 ? this.vars : this.results[contextIndex - 1].Vars;
StringBuilder var;
if (context.TryGetValue(source, out var))
context[target] = new StringBuilder(var.ToString());
}
private void RenameVar(string source, string target)
{
Rename(this.vars, source, target);
foreach (var result in this.results)
{
Rename(result.Vars, source, target);
}
}
private void Rename(Context context, string source, string target)
{
StringBuilder var;
if (context.TryGetValue(source, out var))
{
context[target] = var;
context.Remove(source);
}
}
}
}
Здесь ещё есть что причёсывать (но решает задачу верно). Работы впереди много. Вы же уже можете пользоваться тем, что существует.