A fast interpreter in < 90 lines

У меня новая игрушка. Недавно в рамках праздных раздумий о языкостроении пошел я с пустым ведром зачерпнуть мудрости у лиспоакадемиков. Стал смотреть на Racket (который вырос из PLT Scheme), почитал книжку Beautiful Racket и немного поигрался с описанными там инструментами. А тут еще как раз Racket 8 вышел с новым бэкендом. В предыдущих версиях там компилятор делал байткод, а тот уже в рантайме JITился. А в 8.0 они перешли на компилятор и бэкенд от Chez Scheme, где сразу нативный код генерится.
Сам Racket преподносится как платформа для создания языков. И стандартный рецепт, которому придерживается Beautiful Racket, это если захотел ты сделать свой бэйсик, то регистрируешь свой пакет basic из двух определенных частей (парсер и экспандер), потом пишешь исходник на бейсике, ставишь в нем первой строчкой #lang basic и используешь компилятор Racket. Тот видит первую строчку, достает твой пакет, скармливает остаток файла твоему парсеру (тут у тебя полная свобода по синтаксису), твой парсер производит parse tree, которое передается второй части твоего пакета, которая то дерево преобразует в дерево кода на самом Рэкете. Полученный код на Рэкете уже компилируется, и вот твой бэйсик и скомпилирован.
Но есть один момент, который та книжка почти не упоминает, но который позволяет не опираться на компилятор Рэкета. Дело в том, что в Рэкете есть eval, и вся машинерия компилятора уже содержится в твоем бинарнике. Можно сделать свой один бинарник, который будет парсить новый язык, также разворачивать его в конструкции Рэкета, и тут же выполнять через eval. Под капотом там генерация нативного кода, и скорость получается ничуть не хуже.
В качестве proof of concept сделаем интерпретатор, который сможет выполнять код такого вида:

fac(n) => if n < 2 then 1 else n * fac(n-1);

fib(n) => 
  if n < 2 then 1 
  else {
    a = fib(n-1);
    b = fib(n-2)
    in a + b 
  };

loop(x) => 
  if x < 20 then {
    print(fib(x), fac(x))
    in loop(x+1)
  } else 0;

loop(1)

( Read more... )