0
$\begingroup$

I'm in the designing of an interpreter for a stack based concatenative language, and I'm currently stuck with a problem about recursion of some of my concatenative program to calculate factorial:

fac =
    dup 1 <=             // Returns True or False depending on whether the argument if lower or equal to 1
        [pop 1]          // If True, unquote on the stack and push 1
        [dup 1 - fac *]  // If False, unquote and compute another recursion by decrement the value of 1 and multiplying the result
    if

// And I can compute x! correctly by:

x fac

So it's the only way to approach and finally compute algorithms needing some iterations to work, because concatenative style (in my language at least) don't have the loop concept, but so the interpreter design will have an impact on the result computed depending on the recursions done, depending on the argument in this case. So it will cause segmentation faults sometime, when the recursion begin to be deep.

Thus, I would like to know how can could resolve this problem by enabling a lot of more recursion, or even an "infinity".

To do this, I would probably need to review my interpretation model, which works as follows:

I first have the interpreter program entry:

void compute(Program program) {
    Stack runtime_stack;

    for (int i = 0; i < program.op_nbr; i++)
        eval_operation(&runtime_stack, &program.operations[i]);
}

I also have, of course, an operation evaluator that work on each operation, and that push / take / work on the given stack:

void eval_operation(Stack* stack, Operation* op) {
    switch (op->kind) {
        ...
        case Word:
            return eval_word(stack, &op->word);
        case Unquote:
            return unquote(stack, &op->quote);
        ...
    }
}

Especially, I have the Word operation, that is a simply name of "something" (for example a stack combinator, or here, in this factorial example, the name of the function).

There is too an Unquote operation, that work with a quotation, is like an anonymous function that can so be unquoted, it's mean that its result will be computing on the stack it is unquoted.

void eval_word(Stack* stack, String word) {
    ...
    if (is_function(word))
        return eval_function(stack, &function_infos);
    ...
}

So I eval functions here:

void eval_function(Stack* stack, Function_infos* function_infos) {
    for (int i = 0; i < function_infos.op_nbr; i++)
        eval_operation(stack, &function_infos.operations[i]);
}

And I eval unquotations here:

void unquote(Stack* stack, Quote quote) {
    for (int i = 0; i < quote.op_nbr; i++)
        eval_operation(stack, &quote.operations[i]);
}

You will probably notice that each function (except the entry point of course) will call each other when evaluating a recursive function, which, after several recursions, will cause a stack overflow. For example, I can only perform the factorial function 1500 times recursively, which is really very little.

My design seemed relatively logical to me when I built it, but it is not at all effective for recursions; how could I allow such a recursive function, as presented above, to run without stack overflow and if possible, infinitely (undefined = undefined for example, in Haskell)? Is there a particular way of doing things? Algorithms (I tried tail-optimization, but that doesn't change the problem)?

Note: I pass all value by reference, to keep interpreter stack "clean".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.