Non Recursive Interpreter

A non-recursive interpreter implements TheStack of the interpreted language in a manner that is independent of TheStack implementation that the interpreter itself is written in. The interpreted environment may have many such stacks, allowing the use of multiple CoRoutines without the interpreter itself needing to use NativeThreads? or other OperatingSystem level facilities. This results in a way for programs to abstract their state of execution that is more flexible, more portable, and often times more efficient than what could be provided by a compiler or an interpreter bound by recursion.

In other words, the interpreter reifies the stack rather than absorbing it.

Examples of language implementations:

(moved from InterpreterVsComposite)

Interpreter can be nonrecursive.

One can remove recursion from interpreter by replacing hardware function call stack with stack emulated by software (for example std::stack<T> in C++) After this interpreter is just cycle, which works while stack is not empty Each operation can add items to stack, remove items from stack and do main processing.

Removing recursion allows to implement changes in execution with greater flexibility.

Example. Let’s examine some interpreter for language with return statement

 int fn(bool a)
 {
  if (a)
  {
return 1;
  }
  return 2;
 }

We will have classes CFunction, CIfOperator, CReturnOperator. Each class will have function “Interpret”

In recursive implementation of interpreter CFunction::Interpret will call CIfOperator::Interpret and CIfOperator::Interpret will call CReturnOperator::interpret. In this case CReturnOperator::interpret not able to return control directly to end of CFunction::Interpret (yes, we can use exceptions for this, but this violates design principle “newer use exceptions for flow control”)

In nonrecursive implementation function CReturnOperator::interpret can remove items from stack until it reaches CFunction.

For creating items in software stack we can use MementoPattern or something else. I am use a special hierarchy of classes which mirrors hierarchy of classes for interpreting.

Another way to avoid a stack is to use ContinuationPassingStyle.