Environments and memories (Programming Languages)

Our definitional interpreter for FunMem uses two explicit mappings: an environment that maps identifiers to values, with one kind of value being a location; and a memory that maps locations to storable values. One the other hand, some languages that have assignable variables seem to be explained in terms of a single mapping from identifiers to values, at least when no arrays are involved; the languages TCL, Python and Lua spring to mind. (What about Ruby?) Why are two mappings needed in our treatment of assignment, when seemingly a single mapping is enough in these other languages?

First, let's dispose of two trivial cases. First, in a language with no assignable variables, like our first language Fun, there's no need for the memory, and we can get away with interpreting each expression of the language in the context of a single environment that maps identifiers to values. Second, in a language with no nested scopes, such as a simple 'flowchart' language of statements without parametrised procedures, there's no need for an environment. The state of the program can be taken as a simple mapping from identifiers to values, with assignment replacing one value with another in this mapping. Such a language might omit variable declarations, or treat them as a special kind of assignment to a previously non-existent variable.

[Another trivial case: interpreters that use mutable cells in the metalanguage – a good implementation idea, but one that implicitly involves two mappings]

Setting these trivial cases aside, we can turn to languages that combine assignable variables with multiple, possibly nested scopes. These scopes might be created by a block construct with local variables, or more commonly in practice, by means of subroutines that take parameters and have their own local variables. In this context, it becomes possible for multiple variables to exist in the program with the same name; that happens deliberately in the case of recursive procedures, where the formal parameters of all recursive invocations of the procedure have the same name, but the parameters take different values in different invocations. It also happens in a more accidental way when one procedure calls another and they happen to have local variables with identical names.

[No access to global variables allows single mapping]

[Environments discarded on subroutine return, but memories persist]

[Global declarations a la TCL, Python, ?Ruby, ?Lua are actually a more complex mechanism]