Я давно хотел рассказать об одном моем старом эксперименте, который косвенно связан с функциональным программированием, но все никак не мог решиться на детальное объяснение всех деталей, но все равно очень хочется поведать о моем первом и неудачном опыте создания своего собственного языка программирования…
Прежде чем я поведаю об очередном творении своей мысли, я должен сделать важную ремарку — я так и не довел проект до состояния хотя бы минимальной готовности и многие вещи в рассматриваемом далее коде очень слабо проработаны. Именно это обстоятельство, а также некоторые иные причины заставили меня прекратить на время дальнейшую разработку своего «языка программирования».
Идея, которую я хотел реализовать тесно связана с одним из старейших из используемых языков программирования, а именно, с языком программирования Lisp. Этот язык меня покорил тем, что он действительно элегантен, хотя и обладает весьма специфическим синтаксисом, в основу которого положена идея выражений, заключенных в «контейнер» из скобок. Из-за этой особенности, а также из-за префиксной нотации для абсолютно всех выражений, код на Lisp выглядит весьма своеобразно.
Вот взгляните на простой пример Lisp-подобного кода:
(add (sqr 4) 5 (incr 2))
Ничего понятного, особенно, если браться за разбор этого кода без привычки к обилию скобок, обрамляющих каждое выражение, а также без знания того, что весь код программы на Lisp чаще всего представляет собой единое выражение — некоторую функцию, которая обрабатывает поступившие ей на вход аргументы.
Однако, если внимательно приглядеться, то можно увидеть, что программа в данном случае представляет собой список (именно об этом говорят скобки), в котором на первом месте стоит некая функция (либо встроенная, либо уже где-то определенная программистом), которой поступают некие аргументы, разделенные пробелами. Также несложно отметить тот факт, что в качестве данных для функции могут использоваться и другие функции (посмотрите еще раз на пример — вы непременно увидите, что каждая функция «отмечена» своей парой скобок), а поскольку код программы выглядит точно также, как и данные (они разделены пробелом и представляют собой ничто иное, как список), то потенциально есть возможность модифицировать код программы из себя самой !
Как видите, имея достаточно легкий синтаксис списка и совместив его с префиксной нотацией (сначала идет функция, а затем список аргументов), можно получить компактный, но вместе с тем и легко расширяемый скриптовый язык.
Но, вернемся к нашему примеру кода, который я перепишу в «традиционном» и более привычном стиле для того, чтобы вы смогли оценить разницу и при необходимости возвращаться к этой мини-шпаргалке по перевода с Lisp на «человеческий» по ходу прочтения этой статьи. Итак, после перевода наш код выглядит совсем просто:
(4 ^^ 2) + 5 + (2 + 1)
Теперь, можно начинать реализацию простого Lisp-подобного языка, для чего будем считать, что в качестве средства обрамления выражений мы будем использовать всем знакомые круглые скобки:
enum char OPEN_BRACKET = '(';
enum char CLOSED_BRACKET = ')';
(ничто, однако, не запрещает вам использовать иные виды скобок, например, квадратные. К слову, в первоначальной версии проекта, обрамляющим элементом были именно такие скобки)
После этого, представим, что код на изобретенном нами языке представляет собой единое «выражение», возможно, поступившее из стандартного ввода или одной строки некоторого файла, а потому создадим класс с рабочим названием Sentence.
Этот класс будет хранить в себе все «формы» (т.е отдельные элементы «выражения», помещенные в скобки) и набор индексов для всех скобок:
class Sentence
{
private
{
string form;
int[] positionsOfBrackets;
}
}
Теперь, когда есть заготовка класса, будем продумывать его основные методы, которые я буду приводить в форме отдельных функций, выполняющих свои задачи по обработке данных «выражения».
Представим, что «выражение» для разбора у нас уже имеется, и он уже доступно как аргумент, тогда нам необходимо внести его в объект Sentence, поскольку оно уже по определению является «формой», а также вычислить позиции всех скобок в этой форме.
Это можно осуществить создав конструктор класса, в который передается в качестве аргумента исходное «выражение», после чего происходит моментальный вызов функции indexesOfBrackets, которая производит необходимое вычисление позиций:
this(string form)
{
this.form = form;
indexesOfBrackets;
}
Функция indexesOfBrackets является закрытой (поскольку не используется извне Sentence) и выглядит следующим образом:
void indexesOfBrackets()
{
foreach (element; form.stride(1).enumerate(0))
{
switch(element[1])
{
case OPEN_BRACKET:
positionsOfBrackets ~= element[0] + 1;
break;
case CLOSED_BRACKET:
positionsOfBrackets ~= -(element[0] + 1);
break;
default:
break;
}
}
}
Алгоритм ее работы прост: с помощью stride производим элементарную итерацию по строке-«форме» с шагом в единицу, после чего с помощью enumerate присваиваем каждому итерируемому элементу свой цифровой индекс (отсчет элементов начинаем с нуля). Так как производиться проход циклом по строке, то очевидно, что element будет представлять собой одиночный символ строки. Далее, если символ является открывающей скобкой, то мы помещаем в массив позиций его номер со знаком плюс (т.е положительное число); если же символ является закрывающей скобкой, то помещаем его в тот же массив, но со знаком минус.
Такая схема учета скобок пригодиться как для разбора «выражения», так и для его проверки, а использование stride позволит избежать проблем при использовании символов, занимающих больше одного байта (т.е в принципе, функция универсальна для символов из любых алфавитов, поддерживаемых в Unicode).
Определившись с первоначальной «формой» и вычислив индексы скобок, перейдем к определению открытых функций класса, и первой из них будет функция проверки корректности «формы».
Корректной будем считать такую «форму», в которой количество открывающих и закрывающих скобок совпадает (исходя из этого, можно придти к выводу, что общее количество скобок, как минимум, четно), и которая при этом начинается с открывающей скобки и заканчивается с закрывающей.
При таком критерии проверки можно испытание на корректность выразить так:
bool isCorrect()
{
bool correctnessFlag;
if (positionsOfBrackets.length > 0)
{
size_t numberOfOpenBrackets, numberOfCloseBrackets;
for (size_t i = 0; i < positionsOfBrackets.length; i++) { if (positionsOfBrackets[i] >= 0)
{
numberOfOpenBrackets += 1;
}
else
{
numberOfCloseBrackets += 1;
}
}
if (numberOfOpenBrackets == numberOfCloseBrackets)
{
if ((positionsOfBrackets[0] > 0) && (positionsOfBrackets[$-1] < 0))
{
correctnessFlag = true;
}
}
}
return correctnessFlag;
}
Просто и прямолинейно: считаем количество открытых и количество закрытых скобок, а затем проверяем их равенство и используя введенную схему обозначения индексов типов скобок положительными и отрицательными значениями, убеждаемся в том, что самый первый символ — открывающаяся скобка, а самый последний — закрывающаяся.
А теперь, начинается самый важный этап в работе проекта — подготовка к выделению основных элементов нашего языка…
Введем еще одно понятие - «примитив», которым мы будем обозначать «форму», имеющую только одну пару скобок (первая скобка в начале «формы», а вторая — в конце) и представляющую собой встроенную функцию языка с аргументами или без них.
Определить является ли «выражение» «примитивом» очень легко:
bool isPrimitive()
{
bool primitiveFlag;
if ((positionsOfBrackets.length / 2) < 2)
{
primitiveFlag = true;
}
return primitiveFlag;
}
После этого, можно приступить к осуществлению процедуры выделения всех «форм» из «выражения», которое в нашем случае выглядит так:
Sentence[] allForms()
{
Sentence[] termsOf;
int[] workedCopy = positionsOfBrackets.dup;
while (workedCopy.length > 1)
{
size_t position = 0;
for (int i = 0; i < workedCopy.length; i++)
{
if (workedCopy[i] <= 0)
{
position = i;
break;
}
}
size_t begin = workedCopy[position-1] - 1;
size_t end = abs(workedCopy[position]);
string currentTerm = form[begin..end];
termsOf ~= new Sentence(currentTerm);
workedCopy = removeNth(workedCopy,position);
workedCopy = removeNth(workedCopy,position-1);
}
return termsOf;
}
Поскольку, любая «форма» является самостоятельным «выражением» (такие «выражения» в составе «формы» принято называть «термами»), то функция возвращает массив типа Sentence[]. Для того, чтобы сохранить массив позиций скобок нетронутым, мы копируем его, создавая его изменяемую копию встроенным методом массивов dup.
Дальше, исходя из того, что при обработке «выражения» производиться извлечение «термов» (с последующим их удалением), можно предположить, что фаза разбора заканчивается пока не останется всего лишь один «терм» в «выражении». Для того, чтобы осуществить эту идею, сначала определяем позицию текущего «терма» на основе того, что «терм» имеет в своем составе закрывающую скобку (получаем ее позицию и исходя из этого рассчитываем местоположение «терма» в «выражении»). После того, как «терм» найден, упрощаем «выражение», удаляем позиции найденного «терма» при помощи вспмогательной функции removeNth, которая выглядит так:
T[] removeNth(T, U)(T[] array, U index)
{
auto newIndex = cast(size_t) index;
if (array.length > 0)
{
return array[0..newIndex] ~ array[newIndex+1..$];
}
return array;
}
(На самом деле, не все так запутанно, как представлено в описании работы функции — достаточно просто посмотреть код и один раз проверить на тестовом «выражении»)
Когда уже все «термы» известны легко осуществить выделение всех «примитивов», входящих в состав выражения:
Sentence[] allPrimitives()
{
return this
.allForms
.filter!(a => a.isPrimitive)
.array;
}
Завершая построение класса Sentence, добавим два удобных метода, которые могут пригодиться при отладке и для некоторых иных целей:
string getForm()
{
return form;
}
override string toString()
{
return format("Sentence(%1$s)", form);
}
Рассмотрим теперь механизм исполнения «выражений», предполагая, что наш самописный язык является функциональным — т.е все его базовые элементы представляют собой набор функциональных «форм» с аргументами.
Создадим структуру, которая будет в себе содержать имя исполняемой функции и ее аргументы:
struct FunctionalForm
{
string functor;
string[] arguments;
}
Произведем перевод выражения из обычного «выражения» в более удобную форму — структуру, содержащую функцию с аргументами:
FunctionalForm functorAndArguments(Sentence sentence)
{
FunctionalForm functionalForm;
auto parsedForm = sentence
.getForm[1..$-1] // avoid brackets
.split;
switch (parsedForm.length)
{
case 0:
break;
case 1:
functionalForm.functor = parsedForm[0];
break;
default:
functionalForm.functor = parsedForm[0];
functionalForm.arguments = parsedForm[1..$];
break;
}
return functionalForm;
}
Работает это так: удаляем пробелы с начала и с конца строки «выражения», а затем удаляем открывающую и закрывающую скобку, после чего разбиваем строку по разделителю « « (пробел). Если длина получившегося массива нулевая, то ничего не делаем (так как «выражение» в этом случае не содержит никаких «форм» и является пустым); если же длина равна единице — то перед нами «форма» без аргументов, соответственно помещаем в структуру FunctionalForm имя «формы», иначе — получаем «форму» со множеством аргументов, и в этом случае, нулевой элемент списка — имя функции, а остальное — ее аргументы.
А теперь, представим, что помимо чисел (и, возможно, строк), в нашем языке есть переменные… Соответственно, переменную можно определить как простейший процесс подстановки значения через некоторое имя, связанное с неким значением.
Это можно представить так:
string[string] VariableTable;
Осуществим применение функции к аргументам:
string applyFunctor(FunctionalForm functionalForm)
{
string result;
string[] accumulator;
float[] operands;
if (functionalForm.arguments.length > 0)
{
accumulator = functionalForm.arguments;
float convert(string a)
{
float result;
if (a.isNumeric)
{
result = parse!float(a);
}
else
{
if (a in VariableTable)
{
result = parse!float(VariableTable[a]);
}
else
{
// do nothing
}
}
return result;
}
operands = accumulator
.map!(a => convert(a))
.array;
}
template addOperational(string operation)
{
const char[] addOperational = format(`
result = operands[0]
.reduce!((a,b) => a %1$s b)(operands[1..$])
.to!string;`,
operation);
}
switch (functionalForm.functor)
{
case "add":
mixin(addOperational!"+");
break;
case "sub":
mixin(addOperational!"-");
break;
case "mul":
mixin(addOperational!"*");
break;
case "div":
mixin(addOperational!"/");
break;
case "mod":
mixin(addOperational!"%");
break;
case "pow":
mixin(addOperational!"^^");
break;
case "incr":
result = (operands[0] + 1)
.to!string;
break;
case "decr":
result = (operands[0] - 1)
.to!string;
break;
case "sqr":
result = (operands[0] * operands[0])
.to!string;
break;
case "sqrt":
result = sqrt(operands[0])
.to!string;
break;
case "define":
result = "";
VariableTable[accumulator[0]] = accumulator[1];
break;
case "print-form":
result = "";
writeln(functionalForm);
break;
case "quit":
assert(0);
default:
break;
}
return result;
}
Работает это так: разбираем список аргументов и переводим их в числовой формат (я предполагал, что работать буду пока только с числами), а также осуществляем подстановку переменных если это необходимо. Когда конверсия аргументов закончена, производиться опознание функции, которая будет применена к аргументам, для чего определяется вспомогательный шаблон addOperational, вставляющий свертку нужной функции с аргументами (в этом помогает замечательный алгоритм reduce) и превращение нужного аргумента в строку. Результат выполнения функцияи при этом будет помещен в переменную result.
Исходя из такого описания применения в нашем языке будут доступны следующие «формы»:
(add <аргументы>) Сложение (sub <аргументы>) Вычитание (mul <аргументы>) Умножение (div <аргументы>) Деление (mod <аргументы>) Остаток от деления (pow <аргументы>) Возведение в степень (incr <аргумент>) Увеличение аргумента на 1 (decr <аргумент>) Уменьшение аргумента на 1 (sqr <аргумент>) Возведение в квадрат (sqrt <аргумент>) Корень (define <имя_переменной> <значение_переменной>) Определение переменной (print-form) Распечатать форму (quit) Выход из интерпретатора
Осуществить цикл интерпретации «выражения» теперь очень и очень просто: проинтерпретируем (выполним) «примитив», а на основе исполнения «примитивов» «выражения» сделаем исполнение всего «выражения» просто выполняя подстановку результата выполнения «приитива» в само «выражение», продолжая такой цикл исполнения до тех пор пока не останется одна единственная «форма» с простым результатом:
string interpretatePrimitive(Sentence sentence)
{
string result;
if (sentence.isCorrect)
{
result = sentence
.functorAndArguments
.applyFunctor;
}
else
{
throw new Exception("Incorrect sentence !");
}
return result;
}
string interpretate(Sentence sentence)
{
Sentence currentSentence = sentence;
string result;
while (!currentSentence.isPrimitive)
{
Sentence[] primitives = currentSentence.allPrimitives;
string currentForm = currentSentence.getForm;
foreach (primitive; primitives)
{
string valueOfPrimitive = primitive.interpretatePrimitive;
string formOfPrimitive = primitive.getForm;
currentForm = currentForm.replace(formOfPrimitive, valueOfPrimitive);
currentSentence = new Sentence(currentForm);
}
}
result = interpretatePrimitive(currentSentence);
return result;
}
Все довольно наглядно: осуществляется циклическая замена «форм» результатами их работы (с помощью функции replace), а затем исполнение единственного оставшегося «выражения» (по определению, являющегося «примитивом»).
Объединяем теперь все построенные нами объекты в единый цикл считывания-выполнения-печати (Read-Eval-Print-Loop, REPL):
void main()
{
auto exampleExpression =
`(div
(define denominator
(add
(sqrt
(decr (pow 2 8))) (sqr 4)))
(define numerator
(sub
(mul 12 5)
(sqrt 2)))
denominator
numerator
)`;
//while (!stdin.eof)
//{
// char[] expression;
// stdin.readln(expression);
// Sentence sentence = new Sentence(to!string(expression));
// writeln("primitive : ", sentence.isPrimitive);
// writeln("-> ", sentence.interpretate);
//}
while (!stdin.eof)
{
char[] expression;
write("<-- "); stdin.readln(expression); string cmd = to!string(expression); Sentence sentence = new Sentence(chomp(cmd)); writeln("--> ", sentence.interpretate);
}
}
А вот так это выглядит при запуске:
Прикольно, получилось, а ???
Резюмируя все вышеописанное, я могу сказать, что по сути удалось создать зачаточное ядро Lisp-подобного языка, которое поддерживает в основном математические функции и простейшее объявление переменных.
Однако, в данной реализации очень много нерешенных проблем: прежде всего, данный интерпретатор, ориентирован на математические операции (причем, самые простые), а значит, некоторые по-настоящему интересные возможнеости до сих пор не реализованы. Кроме того, я нашел ряд существенных недостатков через довольно большой промежуток времени, самым главным из которых была использованная методика исполнения элементов языка. Дело в том, что код далеко не является чистым и очевидным, а при использовании переменных порой возникают досадные ошибки, которые весьма непросто исправить — и лучшим вариантом в данном случае будет пересмотр всего алгоритма…
P.S: Lisp был моим первым языком программирования именно это сыграло свою роль в реализации плана по построению своего языка.
Кроме того, я выкладываю эту статью еще и по причине того, что опыт был не только занимательным, но и полезным, особенно в том плане, как не стоит делать свои проекты...
[accordion][panel intro="Полный код затеи под спойлером"]
import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.regex;
import std.stdio;
import std.string;
T[] removeNth(T, U)(T[] array, U index)
{
auto newIndex = cast(size_t) index;
if (array.length > 0)
{
return array[0..newIndex] ~ array[newIndex+1..$];
}
return array;
}
enum char OPEN_BRACKET = '(';
enum char CLOSED_BRACKET = ')';
class Sentence
{
private
{
string form;
int[] positionsOfBrackets;
void indexesOfBrackets()
{
foreach (element; form.stride(1).enumerate(0))
{
switch(element[1])
{
case OPEN_BRACKET:
positionsOfBrackets ~= element[0] + 1;
break;
case CLOSED_BRACKET:
positionsOfBrackets ~= -(element[0] + 1);
break;
default:
break;
}
}
}
}
this(string form)
{
this.form = form;
indexesOfBrackets;
}
bool isCorrect()
{
bool correctnessFlag;
if (positionsOfBrackets.length > 0)
{
size_t numberOfOpenBrackets, numberOfCloseBrackets;
for (size_t i = 0; i < positionsOfBrackets.length; i++) { if (positionsOfBrackets[i] >= 0)
{
numberOfOpenBrackets += 1;
}
else
{
numberOfCloseBrackets += 1;
}
}
if (numberOfOpenBrackets == numberOfCloseBrackets)
{
if ((positionsOfBrackets[0] > 0) && (positionsOfBrackets[$-1] < 0))
{
correctnessFlag = true;
}
}
}
return correctnessFlag;
}
bool isPrimitive()
{
bool primitiveFlag;
if ((positionsOfBrackets.length / 2) < 2) { primitiveFlag = true; } return primitiveFlag; } string getForm() { return form; } Sentence[] allForms() { Sentence[] termsOf; int[] workedCopy = positionsOfBrackets.dup; while (workedCopy.length > 1)
{
size_t position = 0;
for (int i = 0; i < workedCopy.length; i++)
{
if (workedCopy[i] <= 0) { position = i; break; } } size_t begin = workedCopy[position-1] - 1; size_t end = abs(workedCopy[position]); string currentTerm = form[begin..end]; termsOf ~= new Sentence(currentTerm); workedCopy = removeNth(workedCopy,position); workedCopy = removeNth(workedCopy,position-1); } return termsOf; } Sentence[] allPrimitives() { return this .allForms .filter!(a => a.isPrimitive)
.array;
}
override string toString()
{
return format("Sentence(%1$s)", form);
}
}
struct FunctionalForm
{
string functor;
string[] arguments;
}
FunctionalForm functorAndArguments(Sentence sentence)
{
FunctionalForm functionalForm;
auto parsedForm = sentence
.getForm[1..$-1] // avoid brackets
.split;
switch (parsedForm.length)
{
case 0:
break;
case 1:
functionalForm.functor = parsedForm[0];
break;
default:
functionalForm.functor = parsedForm[0];
functionalForm.arguments = parsedForm[1..$];
break;
}
return functionalForm;
}
string[string] VariableTable; // variables
string applyFunctor(FunctionalForm functionalForm)
{
string result;
string[] accumulator;
float[] operands;
if (functionalForm.arguments.length > 0)
{
accumulator = functionalForm.arguments;
float convert(string a)
{
float result;
if (a.isNumeric)
{
result = parse!float(a);
}
else
{
if (a in VariableTable)
{
result = parse!float(VariableTable[a]);
}
else
{
// do nothing
}
}
return result;
}
operands = accumulator
.map!(a => convert(a))
.array;
}
template addOperational(string operation)
{
const char[] addOperational = format(`
result = operands[0]
.reduce!((a,b) => a %1$s b)(operands[1..$])
.to!string;`,
operation);
}
switch (functionalForm.functor)
{
case "add":
mixin(addOperational!"+");
break;
case "sub":
mixin(addOperational!"-");
break;
case "mul":
mixin(addOperational!"*");
break;
case "div":
mixin(addOperational!"/");
break;
case "mod":
mixin(addOperational!"%");
break;
case "pow":
mixin(addOperational!"^^");
break;
case "incr":
result = (operands[0] + 1)
.to!string;
break;
case "decr":
result = (operands[0] - 1)
.to!string;
break;
case "sqr":
result = (operands[0] * operands[0])
.to!string;
break;
case "sqrt":
result = sqrt(operands[0])
.to!string;
break;
case "define":
result = "";
VariableTable[accumulator[0]] = accumulator[1];
break;
case "print-form":
result = "";
writeln(functionalForm);
break;
case "quit":
assert(0);
default:
break;
}
return result;
}
string interpretatePrimitive(Sentence sentence)
{
string result;
if (sentence.isCorrect)
{
result = sentence
.functorAndArguments
.applyFunctor;
}
else
{
throw new Exception("Incorrect sentence !");
}
return result;
}
string interpretate(Sentence sentence)
{
Sentence currentSentence = sentence;
string result;
while (!currentSentence.isPrimitive)
{
Sentence[] primitives = currentSentence.allPrimitives;
string currentForm = currentSentence.getForm;
foreach (primitive; primitives)
{
string valueOfPrimitive = primitive.interpretatePrimitive;
string formOfPrimitive = primitive.getForm;
currentForm = currentForm.replace(formOfPrimitive, valueOfPrimitive);
currentSentence = new Sentence(currentForm);
}
}
result = interpretatePrimitive(currentSentence);
return result;
}
void main()
{
auto exampleExpression =
`(div
(define denominator
(add
(sqrt
(decr (pow 2 8))) (sqr 4)))
(define numerator
(sub
(mul 12 5)
(sqrt 2)))
denominator
numerator
)`;
//while (!stdin.eof)
//{
// char[] expression;
// stdin.readln(expression);
// Sentence sentence = new Sentence(to!string(expression));
// writeln("primitive : ", sentence.isPrimitive);
// writeln("-> ", sentence.interpretate);
//}
while (!stdin.eof)
{
char[] expression;
write("<-- "); stdin.readln(expression); string cmd = to!string(expression); Sentence sentence = new Sentence(chomp(cmd)); writeln("--> ", sentence.interpretate);
}
}
[/panel][/accordion]