Sun, 29 Oct 2006

Functions on the Heap

Robert C. Martin says in Modelling the real world, "OO was "discovered" when two guys who were using a block structured language to write a simulation engine played around with moving the stack frame for a block to the heap, thus making the blocks long-lived. Voila: objects!". In other words, functions on the heap. This is the legacy Kristen Nygaard and Ole-Johan Dahl left to the world of computer science and software development, now called Object Orientation. (There was another development related to C.A.R. Hoare's thoughts on records and associated operators, but that leads off in another direction.)

What does it mean for a function to be on the heap? Typically blocks are lexically scoped, and considered functions when they are named and can be called from other parts of the program. Well, ordinarily, in a block-structured language, when you enter a function a stack frame is created, and the parameters are either copied to or referenced from within that frame. Variables local to that block are uninitialized, and so must be assigned a value to be used. When that block, the function, exits, the stack frame is deleted and all the local variables become undefined once again, and the parameters revert back to the values they had before the block was entered. (By-reference parameters can appear to change if the value of the thing referenced was changed, but that's an additional complication we won't go into).

The next time that block is entered (the function is called) all that stack frame creation and initialization must be repeated. What Nygaard and Dahl did was to move that function onto the heap, where it continues to exist after it is created and called. In the next call to the function, the local variables are still at whatever value they were when the last execution of the block finished. What results is variables that retain their values as long as the program executes, but are visible only within the lexical scope where they are defined. That ends up being a very powerful and useful way to structure and organize programs. Once the block is capable of existing beyond a single invocation, it becomes useful to be able to name the blocks and refer to them from multiple places.

In the original Design Patterns book by the "Gang of Four", (Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides), one of the principles is "encapsulate the thing that varies". By using the technique of functions on the heap, this "thing that varies" becomes not only the "variables" within a block, but the operations which are associated with the block as well.

Perhaps the most simplifying insight to be gained from looking at objects this way is that it says nothing about types, certainly not in the strictly defined way that is seen in languages like Java. Abstract data types and hierarchies of abstractions get a lot of attention in current programming practices. It's well worth the time to explore the implications of objects as long-lasting named functions on the heap.

permanent link