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;
}


Якщо вичіслімості вираз є символом, ми просто шукаємо його значення в поточному лексичному оточенні (find_symbol). Якщо виклик функції: спочатку обчислюємо фактичні параметри, використовуючи поточне лексичне оточення (map_eval), потім прив’язуємо їх до символів формальних параметрів (apply_args) вже в лексичному оточенні самої функції. Далі послідовно обчислюємо елементи тіла на основі отриманого лексичного оточення, повертаючи значення останнього виразу (eval_list). Для виклику макросу порядок обчислення дещо іншою. Фактичні параметри не обчислюються, а передаються в незмінному вигляді. Крім того, результуюче вираз макросу (макропідстановки) піддається додатковому обчисленню. Числа, рядки, функції і макроси обчислюються самі в себе.


Повний текст файлу int.c
Я вирішив ввести більш лаконічні назви для базових і довільних функцій і макросів. У класичному LISP (і, особливо, в Common Lisp) мене трохи напружує багатослівність базових примітивів. З одного боку, я не хотів ускладнювати парсер, тому quote і backquote синтаксис їм не підтримується, тільки скобочной нотація. З іншого боку, прагнув компенсувати надлишкову скобочной широким використанням спеціальних символів для лаконічності. Комусь це здасться вельми спірним рішенням.

Імена я намагався підбирати відповідно до їх асоціативним рядом:


Відповідно, імена похідних функцій і макросів в чому стали похідними від імен базових:

Тепер розглянемо похідні визначення. Спочатку визначимо базові скорочення:

(= @% (! (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 асемблера. Буду пробувати …

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*