I am writing a functional style interpreter for a non-functional programming language that supports both primitive and object values. Primitives are passed by value while objects are passed by reference. I understand how to deal with primitive values but cannot find any good resources on handling mutable object values.

For example, take this ECMAScript inspired language:

var a = {'x': 1};
var b = a;
a.x = 3;

print a.x; // outputs 3
print b.x; // outputs 3

What is not clear to me is where the object's internal representation should live in the interpreter's non-mutable state. I can store non-mutable values in lexical environment records but I believe I need another level of indirection for storing objects because they are mutable.

I have considered having the interpreter state store a record of active objects, with lexical environments then storing a reference to one of these objects. Such references would need to be resolved dynamically against the current state object.

How has this been addressed in other works?

  • $\begingroup$ My initial reaction would be I that the environment immutability and the value mutability don't collide in any way. The interpreter state boils down to book keeping which name is bound to which value, possibily with a context (namespaces, nested blocks, functions). Whether any of these values mutate somehow internally is not related to that indexing. Or am I missing something? $\endgroup$
    – didierc
    Commented Mar 3, 2013 at 1:47

1 Answer 1


The basic way of implementing state is to explicitly implement the state monad. In fact, if you want a pure interpreter, you will be forced to do so one way or another. Since you have objects, and very likely recursion on those, you probably cannot get away with a stack, you need a heap (beware of memory leaks).

Thus, your interpreter shall carry around three things:

  1. The current runtime environment $\eta$, which assigns values to variables, and acts like a stack. When a new variable is declared, you push its initial value onto the runtime environment, and pop it when it goes out of scope.

  2. The current state $s$, which maps locations to values. Thus a location is a primitive value. Since objects are the only mutable values, a location is the same thing as an object id (but not the object itself!). The state may be implemented in any number of ways, but it has to support lookup : state -> location -> object and update : state -> location -> object -> state, i.e., updates return the new state.

  3. The program $p$ to be evaulated.

Because the run-time environment $\eta$ is like a stack whose discipline reflects the recursive calls of the interpreter to itself, you probably won't have any trouble with it (you called it the "lexical environment"). The main point is that you need to carry around the state s explicitly and thread it through the interpreter so that each interpreted command takes in the current state and return the new state. This way a command like

a.x = 3;

can be interpreted as:

  1. In the runtime environment lookup the value of a, expect it to be a location L.
  2. Modify the object at location L so that its field x is set to 3.

The second step is done with update, i.e., it takes in the current state and returns the new state.

You may wonder why the small-step evaluator should take in the whole program p and return a whole program p' yet to be evaluated (as opposed to taking in just one command). This is not strictly necessary (few things are), but it lets you implemented non-local control (exceptions) and loops. For example, to evaluate


we use the fact that this is equivalent to


So you could evaluate a while loop by converting it to the above conditional statement. There are other, more efficient ways of course, but this is the essential insigth about while loops, i.e., they are a form of recursion.

The interpreter for boa in my Programming Languages Zoo is a bit like what you want, but I am cheating because ObjDict in type ob uses mutable references. However, this is the only place where mutable store is used by the interpreter, see lines 149 to 161 of eval.ml where Project dereferences and Assign mutates object attributes. Perhaps it is not too hard to change the source to get what you want.

  • $\begingroup$ Thank you for the detailed explanation. I am indeed building a monadic interpreter. Separating the environment fully from values does indeed seem like the best approach here and it should make adding other language features easier as well. $\endgroup$ Commented Mar 3, 2013 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.