Календарь на Май 2024 года: calendar2008.ru/2024/may/
Навигация
 Главная »  Новости 

LISP-интерпретатор на чистом C


Источник: habrahabr
ababo
Я люблю язык 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). Для вызова макроса порядок вычисления несколько иной. Фактические параметры не вычисляются, а передаются в неизменном виде. Кроме того, результирующее выражение макроса (макроподстановка) подвергается дополнительному вычислению. Числа, строки, функции и макросы вычисляются сами в себя.
Полный текст файла int.c

Я решил ввести более лаконичные названия для базовых и произвольных функций и макросов. В классическом 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)))

Обратите внимание, что в последнем блоке определений явно используется замыкание.
Полный тест файла lib.l
;/ 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 ассемблера. Буду пробовать…



 

 Проектный офис. Часть первая: "что это и чем он занимается"?.
 Системно-онтологический анализ предметной области.
 "1С" готовит новую версию ERP-системы.
 Туннельный синдром: заболевание офисного сотрудника.
 Проектная группа (SADT).


Главная »  Новости 
© 2024 Team.Furia.Ru.
Частичное копирование материалов разрешено.