Add a step-by-step interpreter / debugger

[joews]

Right now the interpreter has one mode: run a peach program from start to finish. I would like to to also have debug operations - step into, step over, run until breakpoint.

That will need some refactoring. The most likely design is a stack-based interpreter. That means, roughly, a change from evaluating child nodes and consuming the result to adding child nodes to an execution stack and somehow accessing the result once that evaluation has finished.

// Before:
// rough algorithm for visiting a `def` node:
// traverse the AST node's `value` node and assign the result to a name in the environment
Def(node, env) {
  const value = evaluate(node.value);
  env[node.name] = value;
  return value;
}

// After:
Def(node, env) {
  // when the `def` node is first visited
  stack.push(/* operation to evaluate the node's value /*)

  // when the `value` node has been evaluated
  // 1. get the value from *somewhere*
  // 2. do *something* with the value
  // 3. return *something*
}

There are a few ways I can see of implementing this. The first is a pattern where wrapped AST nodes are pushed onto a stack when they are first accessed. Visitors work as state machines, where items on the stack are annotated with their current state.

For example a Function node could be in the state PRE_EVALUATE_ARGS or POST_EVALUATE_ARGS to denote where its argument children have been evaluated yet. Once the children have been evaluated, the results are also set onto the node. This is how Neil Fraser's JavaScript interpreter works (see stepCallExpression).

Pseudocode for visiting a Def:

Def(env, stack) {
  // the `def` node is already on the stack; its parent node put it there
  // maybe we change things so that the wrapper is passed into this function
  // - but I think purity is quite hard with this design anyway.
  const { node, state, value } = stack.peek();


  switch (state) {
    case "valueIsEvaluated":
      // RHS is evaluated; this node is done so remove it from the stack
      //  and pass the value of this expression (the RHS value) up to the parent
      stack.pop();
      stack.peek().value = value;

    case "valueIsNotEvaluated":
    default:
      // RHS is not yet evaluated; queue it for evaluation
      stack.push({ node: node.value, state: {} })
  }

This is a proven pattern but there are some things I don't like:

• stack is mutable, so visitors are not pure
• Return values rely on side-effects; children update their callers.
• Evaluating n children (e.g. a function with > 1 arguments) involves n visits. The node tracks this with state like wrapper.nthArg = 2.

I think these can be refined with something like:

// We maintain two stacks: value and execute. Executing a node
// from the `execute` stack results in a value being pushed to the `value`
// stack. Multi-child expressions can queue all of their  children on a single
// visit, and read all of their values on the next visit.
// The `visit` function handles the stack boilerplate. Visitors are called with 
//  the results of executing their children, and return declarative actions.
// This keeps visitors pure.
// This impl doesn't have the arbitrary state tracking of the JS interpreter - I think the
//  simpler semantics of peach mean the only states we need are _"children have not yet been executed"_  and _"children have been evaluated"_.
Def(node, childValue, env) {
  // Visitors return their state and, when ready, their result.
  switch (childValue != null) {
    case "valueIsEvaluated":
      return { value: childValue  }
    default:
      // execute can take a single value or an array. If it's an array,
      // `childValue` will be an array of the same length on the next visit. 
      return { execute: node.rhs }
  }  
}

My other idea involved pushing fragments for parts of a Node visit onto a stack. Having thought it through some more I don't think it solves the problem of dealing with multiple children.