On Simulation of Nested Procedures by Nested Classes

Wolfgang Goerigk, Universität zu Kiel


Nested blocks and procedures are common in classical imperative programming
languages like Algol, Pascal or Modula 2. From a programming viewpoint,
procedure nesting allows for information hiding, which is one the key
principles in software engineering. However, in modern object oriented
languages like C++ or Java, like in C, procedure nesting has been dropped in
favor of open subroutines and flat program structure. This is very often seen
as a major drawback of OO-languages. The more recent Java versions reintroduce
nesting on class level as a principle feature; we still do not find procedure
nesting, though.

On the other hand we know that procedure nesting has an important impact on
the expressive power of an Algol-like procedure concept, at least from a
theoretical point of view. It enables irregular calling trees if we assume the
usual static scoping discipline. Uninterpreted programs can simulate Turing
machines, or more precisely two tape pushdown automata, whereas flat programs
without nesting or locally free variables cannot just by using procedures and
scoping. Computational completeness of uninterpreted programs with procedure
nesting renders many formal decision problems undecidable, like e.g. formal
reachability.

Hence, it seems an interesting question if or not the Java class nesting
feature is as powerful as procedure nesting in Algol-like programs. We will
give a positive answer and define a simulation of nested Algol procedures by
nested Java classes. Interestingly enough, this might have a major impact on
the decidability of formal Java-program properties.