Re: Algol history, was specifying semantics

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:


> Ivan Godard <ivan@ootbcomp.com> writes:
> >When Algol68 was revised, there was a major split in the committee as
> >to the merits of the proposed changes, and even more about the use of
> >VWG as a language notation. The majority accepted the proposal, and
> >their work became the Revised Report and their spiritual descendant
> >populate IFIPS WG2.1 (Algol) to this day.
> >
> >The minority, which included a number of luminaries such as Wirth and
> >Dijkstra, resigned from WG2.1, wrote scathingly about the Algol68
> >language, and formed a rump group that became WG2.3, which also
> >survives. Philosophically they wished to return to (a slightly cleaned
> >up) Algol 60; the linguistic descendants include Pascal and Ada.
>
> The story I read (IIRC in the HOPL paper on Algol 68 was that this
> split happened in 1965 or so, leading to Wirth and Hoare publishing a
> paper on Algol W in 1966. So that was not when Algol68 was revised,
> but when Algol 60 was revised. Wirth and Hoare wanted a relatively
> conservative revision, while the other wanted a revolutionary
> revision.


Not quite. More easily accessible than the HOPL papers are de Beer's
papers


<http://heerdebeer.org/ALGOL/The_History_of_ALGOL.pdf>
<http://datamuseum.dk/site_dk/20100213/Huub_de_Beer-ALGOL_anniversary.pdf>


What became as Algol 68 started off with the proposed name Algol 66,
with three original goals to be embodied in separate reports: one
describing a language to be used in the semantic definition of
programming languages; a small revision of Algol 60 addressing the most
obvious problems, but described using the language of the other paper;
and what I think of as a user guide for Algol '66'.


As is often the case arriving at a consensus was difficult. From the
begining there was strong disagreement about what was meant by a small
revision of Algol 60. At one extreme some took it as a requirement to
fix only the ambiguities and contradictions in the semantics of the
revised Algol 60 report. However a significant fraction also wanted to
replace call by name with a different argument passing mechanism.
Another significant fraction wanted to add features such as case
selection and record data types. It was hard to reach a concensus on how
ambiguities and contradictions would be resolved, while call by name
could not be implemented efficientlyin descibing algorithm's in papers
it had a minor impact and alternative mechanisms were harder to
describe, and while time passed arguing those two issues more small
additions appeared on the table. It is common in this situation for
people to say, in effect "The proposal is too large and must be
simplified, but it is essential that it also have these additons that
are still not accepted." and when push comes to shove make more of a
deal oabout the lack of the additions than about the complexity of other
people's additions.


(Van Wijngaarden appears to have been ambivalent about the proposed
additions. He is reported to, at least a couple of times, have strongly
resisted proposals on their first suggestion with the objection that
they would complicate the language too much and impose too much of a
delay, and then the next day change his mind and note that with a few
minor changes in the current draft the proposal could be made to work.
With him having done the most obvious groundwork it was easy for
proposals to slip from Algol Y into Algol X.)


As time went it became obvious by that the 1966 deadline would not be
met so the effort was renamed Algol X, with features not currently
accepted for Algol X documented as planned for a followon language Algol
Y. Wirth and Hoare's report that served as the basis of Algol W was
their idea of a minimal Algol X that could meet the 1966 deadline, if
accepted by the comittee. But Algol W kept call by name, while adding
record data types and Hoare's select case, so it was too large revision
for the minimalists, and was not as efficient in implementation as the
majority of revisionists wanted. Wirth and Hoare remained in the
comittee until the first draft was published for comment hoping that
something would happen to change Algol 68 back to Algol W.


Van Wijngaarden was the only researcher far enough along to provide a
semantics language on the desired time scale so he soon came to play a
major role in all three efforts. From the beginning, there were
complaints from prominant participants that two level grammars were too
complicated to understand. I suspect that this reflects less a problem
with two level grammars per se than that: semantics in general are hard
to understand; there was no existing concensus on the description of
semantics so all participants had poor groundwork for learning two-level
grammars; and most participants (other than van Wijngaarden and the
editors) were involved part time which made it even more difficult for
them to fully follow the details of the semantics descriptions.




(Note the above makes it tempting for language definitions to be lazy
about defining semantics. It is tempting to write an implementation that
does the most obvious desired things and take that as the definition,
written up as a fifty page or so report. But that fifty page report will
typically have serious ambiguities, or limited functionality. To that
end I am reminded of Richard A. O'Keefe's comment in comp.lang.misc:


"The essential ideas of Algol 68 were that the whole language should be
precisely defined and that all the pieces should fit together smoothly.
The basic idea behind Pascal was that it didn't matter how vague the
language specification was (it took *years* to clarify) or how many
rough edges there were, as long as the CDC Pascal compiler was fast."


I am also reminded of Fortran 77, which had a rather long appendix
listing potential incompatibilities with Fortran 66 compilers, with the
vast majority of the incompatibilities being ambiguities in the Fortran
66 standard that were defined in the Fortran 77 standard.)




> <snip>
>
> And already the Algol 60 grammar (in BNF) does a number of things in
> the grammar that are done in the type system in, say, Pascal. So it
> seems to me that we explored the power of grammar formalisms in the
> 1960s, but eventually came to the conclusion that going beyond
> context-free grammars is not practically useful, and type systems are
> best not expressed in the grammar (they also became more complex
> later, so expressing them as grammars probably would have been a
> burden).
>
> And no other generally-used formalism for expressing type systems has
> appeared, either, although that seems to be an area where a formalism
> can be helpful. But apparently the type systems always need new
> features that would require extending the formalism, and people have
> not learned how to divide stuff between a common type system formalism
> that does not cover everything on the one side and stuff that does not
> fit into the formalism on the other side. Given that, it's surprising
> that we have learned how to do that with context-free grammars/(E)BNF,
> and to accept the limitations of that formalism.


Part of the problem is the variety of formalisms available for
describing semantics. In addition to vWgs, there is the Vienna
Definition Method (and its predecessor the Vienna Definition Language),
atribute grammars, Scott/Strachley, etc. all of which come with minor
variants in notation. It is easy for the experts to wind up in detailed
arguments about minor features, and the majority of non-experts to
decide that if the experts cann't agree on what tool to use, lets see
what we can do without using the tools.


Another part of the problem is there is not a good consensus on how to
use semantic formalisms in language definitions: i.e., use it to guide
the desing as in vWgs in Algol 68 or the Vienna Definition Method in the
Modula II standard, or use it to describe a design as was attempted with
the Vienna Definition Language and PL/I.


<https://cs.uwaterloo.ca/research/tr/1979/CS-79-01.pdf>

Return to the comp.compilers page.
Search the comp.compilers archives again.