Information Technology Reference
In-Depth Information
Nygaard's thesis is a harsh critics towards Algol and a praise of object oriented
languages among which Java [GJSB00] is a prototypical and most widely used
one today. The statement seems to be apodictic, but is rather informal and
intuitive. Good scientific tradition obliges surviving colleagues to make the thesis
more precise and more formal such that a convincing, rigorous proof or disproof
of Nygaard's thesis is possible.
In [Goe05] W. Goerigk came up with a theorem which can be considered to
be a disproof :
Theorem 2: Algol60-programs, even with nested and formal procedures, can be
simulated by object oriented Java-programs in a structurally equivalent manner.
In other words: For every well-formed Algol60-program there can be constructed
a well-formed Java-program with an essentially equal formal execution (call)
tree. The latter notion was introduced in [Lan73a,Lan73b,Lan74,Old79,LaO80,
Old81a, Old81b] in order to prove structural equivalence of Algol-like programs
with procedures and of correctness and relative completeness of Hoare-like proof
calculi [Hoa69]. With some care the notion can be extended to Java-like pro-
grams. Structurally equivalent programs are especially functionally equivalent
(have the same input-output behaviour) independently of the interpretation of
data constants and data operators, even for non-constructive data and opera-
tions. There is no Godel-numbering used, there is not employed any Java-written
interpreter which interprets Algol60-programs.
Since Algol60 is an untyped language, whereas Java is typed, we have to
require that well-formedness (static semantical correctness) of Algol60-programs
is slightly more stringent than the Algol60-report demands. The programs have
to be typable in the sense of Algol68 [Wij + 69] , i.e. the system of type equations
associated to procedure declarations and calls has to be solvable.
Goerigk's strutural simulation allows to formulate the following
Counterthesis 3 to K.Nygaard: The structure of object oriented programs is
not at all more intelligible than the structure of procedure oriented programs.
Every structural complication (which, by definition, is representing itself in
formal execution trees), especially if generated by use of formal Algol-procedures
and of formal global variables, transfers also to Java with its object orientation.
Thus object orientation does not lower down the complications. The unpleasant
structure properties of Algol60 in Nygaard's sense are straight forwardly trans-
ferred to Java by Goerigk's structural simulation; object orientation does not
prevent the unpleasanties.
From [Lan73b] we know that Algol60-programs can simulate Turing-machines
without employment of data like numbers and of conditional statements and ex-
pressions although Algol60-procedures have no functional results as we have
them in λ -calculus [CuF68], Lisp [McC65, Ste84], Algol68 or StandardML
[MTH90]. This simulation is performed purely by procedure declarations, their
nestings, non-formal and formal procedure calls and their call-by-name parame-
ter transmissions. So formal termination (finiteness of formal execution trees)
of Algol60-programs is algorithmically undecidable. It is merely semi-decidable,
 
Search WWH ::




Custom Search