September 2012
« Aug   Oct »




Stack Storage and Garbage Collection

Recently, I ran across Mike Vanier’s page containing his opinions on Scalable Computer Programming Languages. I agree almost entirely with his list:

  • garbage collection
  • no pointers or pointer arithmetic
  • a foreign function interface to the C language
  • static type checking with type inference
  • support for exception handling
  • run-time error checking for errors that can’t be caught at compile time, like array bounds violations and division by zero
  • support for assertions and design by contract
  • a powerful, statically checked module system
  • support for object-oriented programming
  • support for functional programming
  • structural macros
  • support for components
  • a simple, consistent and readable syntaxn

But I do want to pick on garbage collection.

A couple weeks back I was implementing the Parser for the compilers class I’ll be teaching in fall. I want the Parser to print out which grammar rules it called during recursive descent, so that I can use that output as a check on student implementations.

Because the implementation is in Java, I resorted to calling two functions in each grammar method: enterRule(String rule) and exitRule(String rule). The call to exitRule is necessary for tracking indentation level in the output.

What I really wanted was a decorator, that would automatically intercept calls to the grammar methods inserting an enterRule and exitRule. I attempted to accomplish this via reflection, but gave up when I discovered that the compiler optimizes the self-dispatch to recursive methods (when one grammar rule calls another).

Had this been C++ I would have implemented a scope guard object. It’s constructor would make a call to enterRule, and the destructor would call exitRule. I don’t trust this pattern in Java though, because it doesn’t provide a distinction between heap-allocated and stack-allocated objects. The call to exitRule, must be made at the time the grammar rule exits, which happens to coincide with the time a function-scope stack-allocated object destructs.

So I would add some detail to the above list: Either I need compile-time, type-checked decorators, or I need the language to distinguish between allocations on the stack vs heap. I’m fine if the garbage collector non-deterministically destructs heap-allocated objects, but I want stack-allocated objects to destruct at the time their scope pops.

Even better: maybe the ideal language would provide some statically verified mechanism for aspect-oriented crosscuts.

Leave a Reply