Я люблю язык C за его простоту и эффективность. Тем не менее, его нельзя назвать гибким и расширяемым. Есть другой простой язык, обладающий беспрецедентной гибкостью и расширяемостью, но проигрывающий C в эффективности использования ресурсов. Я имею в виду LISP. Оба языка использовались для системного программирования и имеют давнюю и славную историю.
Уже достаточно долго я размышляю над идеей, объединяющей подходы обоих этих языков. Её суть заключается в реализации языка программирования на основе LISP, решающего те же задачи, что и C: обеспечение высокой степени контроля над оборудованием (включая низкоуровневый доступ к памяти). На практике это будет система LISP-макросов, генерирующая бинарный код. Возможности LISP для препроцессирования исходного кода, как мне кажется, обеспечат небывалую гибкость, в сравнении с препроцессором C или шаблонами C++, при сохранении исходной простоты языка. Это даст возможность на базе такого DSL надстраивать новые расширения, повышающие скорость и удобство разработки. В частности, на этом языке может реализовываться и сама LISP-система.
Написание компилятора требуют наличие кодогенератора, а в конечном итоге - ассемблера. Поэтому практические изыскания стоит начинать с реализации ассемблера (для подмножества инструкций целевого процессора). Мне было интересно минимизировать какие-либо зависимости от конкретных технологий, языков программирования и операционной системы. Поэтому я решил с нуля реализовать на C простейший интерпретатор импровизированного LISP-диалекта, а также написать к нему систему макрорасширений, позволяющих удобно кодировать на подмножестве ассемблера x86. Венцом моих усилий должен стать результирующий загрузочный образ, выводящий "Hello world!" в реальном режиме процессора.
На текущий момент мною реализован работающий интерпретатор (файл int.c, около 900 строк C-кода), а также набор базовых функций и макросов (файл lib.l, около 100 строк LISP-кода). Кому интересны принципы выполнения LISP-кода, а также подробности реализации интерпретатора, прошу под кат.
Базовой единицей LISP-вычислений является точечная пара (dotted pair). В классическом лиспе Маккарти точечная пара и символ - единственные два типа данных. В практических реализациях этот набор приходится расширять, как минимум, числами. Кроме того, к базовым типам также добавляют строки и массивы (первые являются разновидностью вторых). В стремлении к упрощению есть искушение рассматривать строки в качестве списка чисел, но я сознательно отказался от этой идеи, как от резко ограничивающей возможности языка в реальном мире. В качестве контейнера для чисел решил использовать double.
Итак мы имеем следующие базовые типы данных: точечная пара, символ, число, строка (pascal style, т.к. это даст возможность хранения произвольных бинарных данных в неизменном виде). Поскольку я работаю над интерпретатором (а не над компилятором), можно было ограничиться этим набором (функции и макросы могут быть представлены обычными s-выражениями), но для удобства реализации были добавлены 4 дополнительных типа: функция, макрос, встроенная функция и встроенный макрос. Итак, имеем следующую структуру для s-выражения:
struct l_env;
typedef struct s_expr *(*built_in) (struct s_expr*, struct l_env*,
struct file_pos*);
struct s_expr {
enum {
DOTTED_PAIR, STRING, SYMBOL, NUMBER, FUNCTION, MACRO,
BUILT_IN_FUNCTION, BUILT_IN_MACRO
} type;
union {
struct {
struct s_expr *first, *rest;
} pair;
struct {
char *ptr;
size_t size;
} string;
struct {
struct s_expr *expr;
struct l_env *env;
} function;
char *symbol;
double number;
built_in built_in;
} u;
};
struct l_env {
char *symbol;
struct s_expr *expr;
struct l_env *next;
};
Данная структура не оптимальна с точки зрения экономии ресурсов и производительности, но я не ставил себе цели построить эффективную реализацию. Прежде всего, была важна простота и лаконичность кода. Пришлось даже отказаться от управления памятью: вся память выделяется без освобождения. На самом деле, для моей практической задачи это решение допустимо: интерпретатор не будет работать длительное время: его задача заключается лишь в трансляции кода в бинарную форму.
Как видно из вышеприведённого кода, функция (и макрос) ссылаются на структуру l_env. Она является базовым элементом лексического окружения, хранимого в виде списка. Конечно, это неэффективно, поскольку предполагает последовательный доступ к символам. Зато это очень простая и удобная структура для поддержки локальных переменных: они добавляются в голову списка, когда как глобальные - в хвост. От локальных переменных очень легко избавляться (при выходе из функции или из блока let), просто игнорируя переднюю часть этого списка. Собственное лексическое окружение у функции позволяет реализовывать замыкания.
На базе вышеприведённой структуры s-выражения легко построить функцию его вычисления:
struct s_expr *eval_s_expr (struct s_expr *expr, struct l_env *env,
struct file_pos *pos) {
struct s_expr *first, *in = expr;
struct l_env *benv;
trace_put("%s -> ...", in, NULL, env);
if (expr)
if (expr->type == SYMBOL)
if (find_symbol(expr->u.symbol, &env))
expr = env->expr;
else
error(UNBOUND_SYMBOL_MSG, pos, expr->u.symbol);
else if (expr->type == DOTTED_PAIR) {
first = eval_s_expr(expr->u.pair.first, env, pos);
if (!first // first->type == DOTTED_PAIR // first->type == SYMBOL //
first->type == STRING // first->type == NUMBER)
error(NON_FUNC_MACRO_MSG, pos, s_expr_string(first, env));
expr = first->type == FUNCTION // first->type == BUILT_IN_FUNCTION ?
map_eval(expr->u.pair.rest, env, pos) : expr->u.pair.rest;
if (first->type == FUNCTION // first->type == MACRO) {
assert(first->u.function.expr->type == DOTTED_PAIR);
benv = apply_args(first->u.function.expr->u.pair.first, expr,
first->u.function.env, pos);
expr = eval_list(first->u.function.expr->u.pair.rest, benv, pos);
if (first->type == MACRO) {
trace_put("%s ~> %s", in, expr, env);
expr = eval_s_expr(expr, env, pos);
}
}
else
expr = first->u.built_in(expr, env, pos);
}
trace_put("%s -> %s", in, expr, env);
return expr;
}
Если вычислимое выражение является символом, мы просто ищем его значение в текущем лексическом окружении (find_symbol). Если вызов функции: вначале вычисляем фактические параметры, используя текущее лексическое окружение (map_eval), затем привязываем их к символам формальных параметров (apply_args) уже в лексическом окружении самой функции. Далее последовательно вычисляем элементы тела на основе полученного лексического окружения, возвращая значение последнего выражения (eval_list). Для вызова макроса порядок вычисления несколько иной. Фактические параметры не вычисляются, а передаются в неизменном виде. Кроме того, результирующее выражение макроса (макроподстановка) подвергается дополнительному вычислению. Числа, строки, функции и макросы вычисляются сами в себя.
Я решил ввести более лаконичные названия для базовых и произвольных функций и макросов. В классическом LISP (и, особенно, в Common Lisp) меня немного напрягает многословность базовых примитивов. С одной стороны, я не хотел усложнять парсер, потому quote и backquote синтаксис им не поддерживается, только скобочная нотация. С другой стороны, стремился компенсировать избыточную скобочность широким использованием специальных символов для лаконичности. Кому-то это покажется весьма спорным решением.
Имена я старался подбирать в соответствии с их ассоциативным рядом:
- _ - заменяет nil
- ! - заменяет lambda
- # - аналогично !, но объявляет безымянный макрос
- ? - заменяет if с обязательным третим параметром
- ^ - заменяет cons
- @ - заменяет car
- % - заменяет cdr
- = - заменяет setq
Соответственно, имена производных функций и макросов во многом стали производными от имён базовых:
- !! - заменяет defun
- ## - заменяет defmacro
- ^^ - заменяет list
- @% - заменяет cadr
- %% - заменяет cddr
- : - заменяет let для одной переменной
- :: - заменяет let без избыточных скобок
- & - заменяет and
- / - заменяет or
Теперь рассмотрим производные определения. Вначале определим базовые сокращения:
(= @% (! (list) (@ (% list)))) ; cadr
(= %% (! (list) (% (% list)))) ; cddr
(= ^^ (! (_ . elts) elts)) ; list
(= ## (# (name fargs . body) ; defmacro
(^^ = name (^ # (^ fargs body)))))
(## !! (name fargs . body) ; defun
(^^ = name (^ ! (^ fargs body))))
Обратите внимание на точечную нотацию списка формальных аргументов. Символ после точки захватывает оставшиеся фактические параметры. Случай, когда все аргументы необязательны, описывается специальной нотацией: (_ . rest-args). Далее определим классический map и два парных разбиения списка:
(!! map (func list)
(? list (^ (func (@ list)) (map func (% list))) _))
(!! pairs1 (list) ; (a b c d) -> ((a b) (b c) (c d))
(? (% list) (^ (^^ (@ list) (@% list)) (pairs1 (% list))) _))
(!! pairs2 (list) ; (a b c d) -> ((a b) (c d))
(? list (^ (^^ (@ list) (@% list)) (pairs2 (%% list))) _))
Определяем два варианта let:
(## : (name value . body) ; simplified let
(^^ (^ ! (^ (^^ name) body)) value))
(## :: (vars . body) ; let without redundant braces
(= vars (pairs2 vars))
(^ (^ ! (^ (map @ vars) body)) (map @% vars)))
Классический reverse и левую свёртку:
(!! reverse (list)
(: reverse+ _
(!! reverse+ (list rlist)
(? list (reverse+ (% list) (^ (@ list) rlist)) rlist))
(reverse+ list _)))
(!! fold (list func last) ; (fold (' (a b)) f l) <=> (f a (f b l))
(? list (func (@ list) (fold (% list) func last)) last))
Теперь логические операторы на основе if:
(= t (' t)) ; true constant
(!! ~ (bool) (? bool _ t)) ; not
(## & (_ . bools) ; and
(: and (! (bool1 bool2) (^^ ? bool1 (^^ ? bool2 t _) _))
(fold bools and t)))
(## / (_ . bools) ; or
(: or (! (bool1 bool2) (^^ ? bool1 t (^^ ? bool2 t _)))
(fold bools or _)))
И, наконец, операторы сравнения на основе встроенного > (greater):
(: defcmp (! (cmp)
(# (_ . nums)
(: cmp+ (! (pair bool)
(^^ & (cmp (@ pair) (@% pair)) bool))
(fold (pairs1 nums) cmp+ t))))
(= == (defcmp (! (num1 num2) (^^ & (^^ ~ (^^ > num1 num2))
(^^ ~ (^^ > num2 num1))))))
(= >= (defcmp (! (num1 num2) (^^ ~ (^^ > num2 num1))))))
(## < (_ . nums) (^ > (reverse nums)))
(## <= (_ . nums) (^ >= (reverse nums)))
Обратите внимание, что в последнем блоке определений явно используется замыкание.
;/
Formal argument list notation:
([{arg1 [arg2 [arg3 ...]] / _} [. args]])
Number notation:
${double / ooctal / hhex} ; $4 $-2.2e3 $o376 $h7EF
Built-in symbols:
_ ; nil
Built-in functions:
@ (list) ; car
% (list) ; cdr
^ (first rest) ; cons
+ (_ . nums)
Built-in macros:
trace (_ . body)
' (expr)
? (cond texpr fexpr) ; if with mandatory fexpr
! (args . body) ; lambda
# (args . body) ; creates anonymous macro
> (_ . nums)
/;
(= @% (! (list) (@ (% list)))) ; cadr
(= %% (! (list) (% (% list)))) ; cddr
(= ^^ (! (_ . elts) elts)) ; list
(= ## (# (name fargs . body) ; defmacro
(^^ = name (^ # (^ fargs body)))))
(## !! (name fargs . body) ; defun
(^^ = name (^ ! (^ fargs body))))
(!! map (func list)
(? list (^ (func (@ list)) (map func (% list))) _))
(!! pairs1 (list) ; (a b c d) -> ((a b) (b c) (c d))
(? (% list) (^ (^^ (@ list) (@% list)) (pairs1 (% list))) _))
(!! pairs2 (list) ; (a b c d) -> ((a b) (c d))
(? list (^ (^^ (@ list) (@% list)) (pairs2 (%% list))) _))
(## : (name value . body) ; simplified let
(^^ (^ ! (^ (^^ name) body)) value))
(## :: (vars . body) ; let without redundant braces
(= vars (pairs2 vars))
(^ (^ ! (^ (map @ vars) body)) (map @% vars)))
(!! reverse (list)
(: reverse+ _
(!! reverse+ (list rlist)
(? list (reverse+ (% list) (^ (@ list) rlist)) rlist))
(reverse+ list _)))
(!! fold (list func last) ; (fold (' (a b)) f l) <=> (f a (f b l))
(? list (func (@ list) (fold (% list) func last)) last))
(= t (' t)) ; true constant
(!! ~ (bool) (? bool _ t)) ; not
(## & (_ . bools) ; and
(: and (! (bool1 bool2) (^^ ? bool1 (^^ ? bool2 t _) _))
(fold bools and t)))
(## / (_ . bools) ; or
(: or (! (bool1 bool2) (^^ ? bool1 t (^^ ? bool2 t _)))
(fold bools or _)))
(: defcmp (! (cmp)
(# (_ . nums)
(: cmp+ (! (pair bool)
(^^ & (cmp (@ pair) (@% pair)) bool))
(fold (pairs1 nums) cmp+ t))))
(= == (defcmp (! (num1 num2) (^^ & (^^ ~ (^^ > num1 num2))
(^^ ~ (^^ > num2 num1))))))
(= >= (defcmp (! (num1 num2) (^^ ~ (^^ > num2 num1))))))
(## < (_ . nums) (^ > (reverse nums)))
(## <= (_ . nums) (^ >= (reverse nums)))
Итак, интерпретатор и большая часть примитивов готовы для того, чтобы писать DSL ассемблера. Буду пробовать…