Lisp-1 vs Lisp-2
Как я понял, существуют две конь-цепции, различающиеся вроде бы не слишком сильно: Lisp-1 построен вокруг общего пространства имён для переменных и функций (представитель этого вида - Scheme), Lisp-2 построен вокруг раздельных (одно для переменных и совершенно другое для функций) пространств имён, Common Lisp - пример такого подхода.
Я думаю, что в целях упрощения реализации воспользуюсь первым вариантом и сделаю так, что можно будет объявлять переменные при помощи следующей конструкции:
(setf foo (cons '(x y) '(+ x y) ) )
Создаётся символ, которому присваивается значение точечной пары, содержащей список аргументов как первый элемент и список инструкций как второй элемент. Ессно, можно сделать (точнее даже, надо будет) "синтаксический сахар", оборачивающий эту запись в более удобную форму классического defun:
(defun foo (x y) (+ x y) )
Макросов у меня пока нет (ибо REPL тупейший), такшта придётся немного поизвращаться.
И если мы сделаем..
(foo 1 2)
..то движок пороется в списке имён, вытащит оттуда foo и увидит, что это CONS. После чего извлечёт обе половинки, попытается проанализировать список аргументов - вычислить их значения и занести в контекст исполнения соответствующие символы, после чего попытается вычислить список инструкций. Если всё зашибись, нажмём на кнопку и получим результат.
Оптимизация рекурсии, наверное, должна опираться на анализ контекста - если мы вызываем функцию foo из контекста, в котором она уже была вызвана (где-то надо будет сохранять некое однозначное состояние), то НОВЫЙ контекст не создаётся, а вместо этого обновляются значения символов на текущем уровне. Этот приём будет работать в таких случаях:
(defun iter (x)
(if (< x 10)
(iter ( + x 1 ) )
)
)
Тут iter "увидит", что её уже вызывали в этом же контексте, поэтому новое значение будет отображено прям по месту старого, сэкономив нам немного памяти.
Т.к. код исполняется буквально, то избавиться от вложенных вызовов сишных функций пока не получится. В будущем, возможно, перепишу движок так, чтобы превратить вложенные вызовы в последовательные (и тут не обойтись без компиляции - без разложения высокоуровневого кода на некие примитивные операции), но пока об этом не хочу думать.
А вот в таком примере примитивная "оптимизация" работать уже не будет:
(defun bar (x)
(if (< x 10)
(iter ( + x 1 ) )
)
)
(defun iter (x)
(bar x)
)
iter вызвана изнутри контекста bar, поэтому она "не видит", что это просто вложенный вызов её самой, и каждая из итераций создаст свой контекст, засрав память. Здесь проблему уже не решить никак иначе, кроме как либо продумывая сам код, чтобы в нём не встречалось подобных вывертов, либо реализовать механизм, который при проходе по скомпилированному коду как-то увидит, что на самом деле нет необходимости создавать новый контекст.
Чем дальше в лес, тем всё чудесатее и чудесатее.
Пока вот так:
> (setf func (cons (quote (x)) (quote (display x))))
( ( X ) DISPLAY X )
> (func 1)
1
>