DeadEnds Interpreter, Memory Management

The DeadEnds interpreter is written in Objective-C using Apple's Foundation framework, part of the Cocoa platform. Two dynamic memory management models are supported in this environment, retain/release and garbage collection. I opted to use the retain/release model because it forces a more careful analysis of dynamic memory usage. In the retain/release model each allocated object has a retain count associated with it. As long as the retain count is greater than zero the object remains in existence. When the retain count drops to zero the system will reclaim the object. Any software that needs to maintain access to an object should increment its retain count (though see description of weak references below), and is responsible for decrementing (releasing) the retain count when access is no longer required. Simple rules are used for managing retain/release objects:

1. Allocation methods (alloc) and copy methods (name starts with copy) create objects that come into existence with a retain count of one. Code that calls these methods are responsible for releasing the object.
2. If software creates an object on behalf of a caller, it calls autorelease on the object before returning the object. This causes a release to occur in the future, giving the caller a chance to retain the object before it disappears.

When one object refers to a second object, and the first object retains a reference to the second object, the reference is called a strong reference. This is the usual convention. When the first object is released, it is responsible for first releasing its strongly referenced objects. If an object refers to a second object, but does not retain the reference to second object, the reference is called a weak reference. Weak references are used in situations where there are specific conventions in use for memory management that can assure that the second object will not be released while the first object still requires access to it. As we will see below, this convention is used by one of the object sets employed by the DeadEnds interpreter.

During interpretation there are two sets of objects created. The first are the semantic values that make up the internal format of the program modules. These are the objects created by the parser when reading the program files. Object creation occurs within semantic actions, snippets of Objective-C code that runs whenever a grammar rule is recognized and reduced. These objects are allocated and initialized by the semantic actions so they have a retain count of one. As parsing proceeds trees of these semantic objects are built up and ultimately each program module is represented by a single semantic object (a TWInterpModule) that has a tree of semantic objects below it representing the body of the module. Because each semantic object is created by the parser, and because there is no need for any other object to retain these objects, the references between all semantic objects and the objects they refer to are weak references. Therefore the initializer methods for semantic objects never retain references to other semantic objects. In fact, in the current version of the interpreter, once a module has been parse and converted to semantic tree form it is never released.

The second set of objects are the values created by evaluating expressions while methods are being actively interpreted (executed/run). There are a number of expression classes, all sub-classes of TWInterpExpression. Each of these classes implements an evaluate: method that takes a symbol table (TWInterpSymbolTable) as an argument. Each evaluate: methods returns an r-value (TWInterpRValue) object. The memory management rule used in this case is r-values returned by evaluate: methods are already retained with a count of one. So evaluate: methods use the same rules as alloc and copy methods do: it is the responsibility of the callers of evaluate: methods (which are often evaluate: methods higher in a recursive evaluation of a complex expression) to release all TWInterpRValue objects it receives from the evaluate: methods it calls.

To give an example of this second approach in action, here is psuedo code for the evaluate: method for a binary expression.

1. Call evaluate: on the left sub-expression resulting in a retained left r-value object.
2. Call evaluate: on the right sub-expression resulting in a retained right r-value object.
3. Create a new r-value (using alloc) with value computed from the values of the two just computed r-values. This new r-value has a retain count of one.
4. Release the two r-values computed in steps 1 and 2.
5. Return the resultant r-value computed in step 3.

The details are more complex that indicated here, but this gives a good introduction to the convention used.