Реализация Lisp eval со стеком вместо рекурсии
Я смотрю на howtowriteaprogram.blogspot.com/2010/11/lisp-interpreter-in-90-lines-of-c.html и хотел бы увидеть, как я мог бы реализовать функцию eval () без рекурсии, а вместо этого как итеративную функцию, использующую стек.
Вот код для eval (), взятый из статьи:
////////////////////// eval
cell eval(cell x, environment * env)
{
if (x.type == Symbol)
return env->find(x.val)[x.val];
if (x.type == Number)
return x;
if (x.list.empty())
return nil;
if (x.list[0].type == Symbol) {
if (x.list[0].val == "quote") // (quote exp)
return x.list[1];
if (x.list[0].val == "if") // (if test conseq [alt])
return eval(eval(x.list[1], env).val == "#f" ? (x.list.size() < 4 ? nil : x.list[3]) : x.list[2], env);
if (x.list[0].val == "set!") // (set! var exp)
return env->find(x.list[1].val)[x.list[1].val] = eval(x.list[2], env);
if (x.list[0].val == "define") // (define var exp)
return (*env)[x.list[1].val] = eval(x.list[2], env);
if (x.list[0].val == "lambda") { // (lambda (var*) exp)
x.type = Lambda;
// keep a reference to the environment that exists now (when the
// lambda is being defined) because that's the outer environment
// we'll need to use when the lambda is executed
x.env = env;
return x;
}
if (x.list[0].val == "begin") { // (begin exp*)
for (size_t i = 1; i < x.list.size() - 1; ++i)
eval(x.list[i], env);
return eval(x.list[x.list.size() - 1], env);
}
}
// (proc exp*)
cell proc(eval(x.list[0], env));
cells exps;
for (cell::iter exp = x.list.begin() + 1; exp != x.list.end(); ++exp)
exps.push_back(eval(*exp, env));
if (proc.type == Lambda) {
// Create an environment for the execution of this lambda function
// where the outer environment is the one that existed* at the time
// the lambda was defined and the new inner associations are the
// parameter names with the given arguments.
// *Although the environmet existed at the time the lambda was defined
// it wasn't necessarily complete - it may have subsequently had
// more symbols defined in that environment.
return eval(/*body*/proc.list[2], new environment(/*parms*/proc.list[1].list, /*args*/exps, proc.env));
}
else if (proc.type == Proc)
return proc.proc(exps);
std::cout << "not a function\n";
exit(1);
}
Первое, на что я наткнулся, это интересно, как бы вы реализовали логику «если» со стеком. Если вы поместите условие (первую ячейку) в стек и перейдете к следующей итерации, как вы узнаете, чтобы вернуться к точке, в которой вы затем решили, следует ли переходить к ячейке / узлу «then» или «else»?
То же самое применимо к любой другой логике: если, например, я помещу ячейку для «определения» в стек и перейду к следующей итерации, как только она будет оценена, как я узнаю, чтобы вернуться к той же самой место?
Решение
Я сделал это дважды. однажды в Common Lisp и однажды в Brainfuck.
Основная идея состоит в том, чтобы сделать примитивы и элементы приложения или push стеками. У каждой части есть цель, поэтому процесс eval сильно зависит от мутирующих конс-клеток по адресу. Пример. # фактический адрес, а не символ:
(cons 'a 'b)
#result ->
cons
#x
(#preapply #x 'a 'b)
#result ->
(#preapply #cons 'a 'b) ->
'a
#a
'b
#b
(#apply #cons #a #b)
#result ->
quote
#r
(#preapply #r a)
#a
'b
#b
(#apply #cons #a #b)
#result ->
'b
#b
(#apply #cons #a #b)
#result ->
'b
#b
(#apply #cons a #b)
#result ->
quote
#r
(#preapply #r b)
#b
(#apply #cons a #b)
#result ->
(#preapply #quote b)
#b
(#apply #cons a #b)
#result ->
(#apply #cons a b)
#result ->
<empty stack>
Результат (a. B) находится в машине минусов с адресом #result.
#Preapply — это примитив, который обрабатывает специальные формы, такие как if, lambda а также flambda, Он также выдвигает структуру так, что он оценивает каждый аргумент, когда он является функцией. #apply прост для примитивов, а также для манипуляций со стеком и средой для лямбд.
В моих реализациях специальные формы и примитивные функции имеют самые низкие адреса, поэтому примитивы — это просто особое место в памяти.
Другие решения