Tree-walk interpretation

A tree-walk interpreter is the simplest possible interpreter architecture: to evaluate an AST, recursively evaluate each node by switching on its tag and calling the appropriate helper. There is no compilation step, no bytecode, no virtual machine.

The central dispatch

RuntimeValue *interpreter_evaluate(AST *ast, Environment *env) {
  switch (ast->tag) {
    case AST_BINARY_EXPRESSION:
      return eval_binary_expression(ast, env);
    case AST_NUMBER:
      return eval_number(ast, env);
    case AST_IDENTIFIER:
      return eval_identifier(ast, env);
    case AST_CONDITIONAL:
      return eval_conditional(ast, env);
    case AST_BLOCK:
      return eval_block(ast, env);
    // ...
    default:
      return eval_unhandled(ast, env);
  }
}

Each eval_* helper recursively calls interpreter_evaluate() on child nodes. For a binary expression, both operands are evaluated first, then the operator is applied to the results. eval_conditional is a good example of the pattern doing real work: it evaluates each when arm's predicate in order and short-circuits to that arm's consequent the moment one comes back true, falling through to otherwise if none do.

The RuntimeValue

The return type is RuntimeValue* — a heap-allocated tagged union over INTEGER (int), FLOAT (float), STRING (char*), BOOLEAN (bool), and ERROR. The last-evaluated expression's value is what gets printed to stdout.