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

Я люблю язык 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;
}

Имена я старался подбирать в соответствии с их ассоциативным рядом:

• _ - заменяет 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))))

(!! 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)))

;/
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)))

Ссылки по теме

• Купить лицензионную версию Windows 7
• Купить программу Microsoft: Visual Studio 2010
• Каталог программ Microsoft: Visual Studio 2010
• Задать вопрос ONLine по покупке программ в интернет магазине ITShop