Mutable Object Values in a Functional Interpreter
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:


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.
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 -&gt; location -&gt; object and update : state -&gt; location -&gt; object -&gt; state, i.e., updates return the new state.
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:


In the runtime environment lookup the value of a, expect it to be a location L.
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

WHILE B DO C DONE
P


we use the fact that this is equivalent to

IF B THEN
   (C ; WHILE B DO C DONE)
ELSE
   P


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.