14 Stack Interp

In this assignment you’ll implement an interpreter with an explicit stack, called ParetK.

The language you’ll implement is a subset of the language from the functions interpreter, with single-argument lambdas and let expressions, no lists, and fewer operators.

The AST is:

data Op:
  | op-plus
  | op-minus
  | op-less
  | op-greater
end

data Expr:
  | e-num(n :: Number)
  | e-bool(b :: Boolean)
  | e-op(op :: Op, left :: Expr, right :: Expr)
  | e-if(cond :: Expr, consq :: Expr, els :: Expr)
  | e-let(x :: String, bind :: Expr, body :: Expr)
  | e-lam(arg :: String, body :: Expr)
  | e-app(f :: Expr, arg :: Expr)
  | e-id(x :: String)
end

There are a few new data definitions for this interpreter. First, there are contexts, which describe slices of pending computation. Above each variant is the notation, in terms of the class notes, that the variant represents.

data Context:

  # (<op> ∙ <expr>)
  | c-op-left(op :: Op, right :: Expr)

  # (<op> <value> ∙)
  | c-op-right(op :: Op, left :: Value)

  # (if ∙ <exp> <exp>)
  | c-if-cond(thn :: Expr, els :: Expr)

  # (∙ <exp>)
  | c-app-f(arg :: Expr)

  # (<value> ∙)
  | c-app-arg(f :: Value)

  # (let (x ∙) <exp>)
  | c-let-bind(x :: String, body :: Expr)

  # x = v
  | c-binding(x :: String, v :: Value)
end

In terms of the class notes’ notation, programs are always either are either returning a value, or evaluating an expression, and also keep track of a stack. This picture gives an example of mapping the data structures in this assignment to the notation in the notes:

You will implement a step-based interpreter for this language that evaluates programs one operation at a time, always maintaniing an explicit stack. You will implement only the step function, which can be used, in combination with iteration, to build a full evaluator.

The step function is defined in terms of program configurations, which capture the difference between the two cases (value vs. expression) in the Program datatype. They also rely on a definition of Stacks, which are lists of Contexts:

data Program:
  | p-return(stack :: Stack, v :: Value)
  | p-eval(stack :: Stack, e :: Expr)
end

type Stack = List<Context>

fun step(p :: Program) -> Program:
  ...
end

The lists are printed in the opposite order of the picture, because the bottom of the stack as drawn is the first element in the list. So, one of the examples above, written out fully with a concrete stack would look like:

Some steps require adding to the stack. For example, the step immediately following the program state above would look like:

Here, there’s a new frame representing the context of the + operation.

We discussed in class that sometimes we can remove frames right before a function call, if there are binding frames as the most recent frames on the stack. The rule looked like:

These are referred to as proper tail calls, and your step function needs to implement them. You can test if you implement them correctly by, for example, writing an infinite loop in ParetK, and checking that the stack size remains under a fixed bound even after many steps.

To test, you may find it helpful to write one or more of the following functions:

• eval, which takes an expression and performs steps on the expression until it has completed running with an answer.

• step-n, which takes a program and a number n, and performs n steps on it.

• steps, which takes a program and produces a list of Programs representing the steps that expression takes.

To summarize:

• Write a step function that takes single steps by producing a new Program.

• Implement proper tail calls by popping unnecessary stack frames before function calls, when possible.

• Provide tests that demonstrate that your step function works correctly.

You can start with this template file:

https://code.pyret.org/editor#share=0B32bNEogmncOTHBvU3lEUFBMUzA&v=v0.5r852

There is no test review, reference solution, or explicit bad solutions for this assignment. If a program steps all the way to a value and empty stack, the value should be the same as the answer to interpreting the same program under the functions interpreter (with the obvious mapping between closure representations).

You are allowed to work in pairs if you want, mark partners clearly in the files you hand in. You still need to test all aspects of your step function (you’re welcome to test in the same file as your implementation, or use a separate file), and will be graded on your test cases as well as your implementation as usual. This lab is due midnight Monday, April 20.

Extra Credit:

For a small amount of extra credit, try the following:

• In what way does this step-based interpreter exhibit a very limited form of dynamic scope? How would you fix it? Identify the problem, and submit a second interpreter (with a clear comment at the top explaining the difference) that fixes the problem. Change data definitions as necessary.

• The implementation of identifiers and closures as given is slow, because it requires walking the whole stack. Can you think of a more efficient representation of Contexts that leverages environments? Submit a more efficient step function that uses an environment and avoids any operations that are O(n) in the size of the stack. Change data definitions as necessary.

• Write a function stepper that takes a program string and produces a function that, when called, produces the next step the program takes. So the signature is

  stepper :: (s :: String) -> (-> Program)

  When called repeatedly, stepper should produce the steps the program takes in order. This is the essence of a stepping debugger.

If you do both of the interpreter extension extra credits, just submit one extra interpreter that handles both cases.