Hangout for experimental confirmation and demonstration of software, computing, and networking. The exercises don't always work out. The professor is a bumbler and the laboratory assistant is a skanky dufus.

Recent Items
 
Orcmid's Lair: Global Social Identity
 
What We See Is Not What We Get: Character Codes and Computers
 
Blinking at Quarks: Is It an Object that I See Before Me
 
The Quarks of Object-Oriented Development
 
Performing in Teams: Where's the Praxis?
 
Windows Home Server Edition
 
The Ultimate Confirmable Incoherence Experience
 
To Express or Not To Express: Choosing a C/C++ Compiler
 
Agile Builds: Making a Bad Idea Efficient?
 
Patterns: Starting in the Meta-Middle

Archives
2004-06-13
2004-06-20
2004-06-27
2004-08-29
2004-09-05
2004-09-12
2004-09-19
2004-10-10
2004-10-24
2004-11-07
2004-11-28
2004-12-05
2004-12-12
2004-12-26
2005-01-30
2005-02-06
2005-03-06
2005-03-13
2005-03-20
2005-04-03
2005-04-10
2005-04-17
2005-04-24
2005-05-01
2005-05-08
2005-05-15
2005-05-29
2005-06-05
2005-06-12
2005-06-19
2005-06-26
2005-07-10
2005-07-17
2005-07-31
2005-08-28
2005-10-09
2005-10-16
2005-10-23
2005-11-13
2005-11-27
2005-12-04
2005-12-18
2006-01-08
2006-02-05
2006-02-12
2006-02-19
2006-03-05
2006-03-12

Appreciating ALGOL 60: Launching Computer Science

Peter Naur's receipt of ACM's 2005 A. M. Turing Award reminded me of the significant place that ALGOL 60 occupies in my development as a computer scientist.  When I found the report in library stacks in 1961, my world shifted completely.  I was so taken by the power of the descriptive notation now known as BNF (for Backus-Naur Form) that I copied out the syntax rules in pencil and took them with me to study. 

The language design and its specification provided a level of rigor and conceptual tidiness that was unknown up to that point.  It is probably no longer possible to surpass that achievement.

{tags: Peter Naur Turing Award ALGOL 60 programming languages Backus-Naur Form BNF computer history orcmid}

Inspiration by Language Elegance

In the face of today's 2000-page specifications for software standards, it is difficult to appreciate that the complete ALGOL 60 report was 16 typeset pages, including index.  ALGOL sparked a revolution in how programming languages were thought of.  New ideas in software were often expressed in reference to ALGOL 60.  The language became the lodestone for contributions that would define the emergence of computer science as a discipline:

• The BNF notation encouraged conceptual harmony in the definition of language constructs.  It became a tool of thought and discussion.

• Having formal syntax led to creation of techniques for computer-aided syntactic analysis, parser generation, and regularity of compiler structure that persist to this day.

• The language provided a reference point for development of new ideas and economies in programming methodology.

• The introduction of lexical scoping and strong typing along with dynamic allocation of data in recursive procedures raised new challenges for execution models,  That has influenced hardware and software ever since.  The parts of ALGOL that were considered too difficult keep having to be re-invented in new forms.

• The language became the basis for publishing and interchange of algorithmic procedures in the open literature.

The ALGOL 60 Report and ALGOL language gave us a way to illustrate new thinking about programming languages, programming methodology, and approaches to compiler construction and execution environments. 

As a practical, programmed-in language, ALGOL was welcomed in Europe and the Soviet Union.  In North America, other realities of life, and the rapid deployment of FORTRAN and COBOL, became a barrier as was the disruptive failure of IBM to embrace the language.  IBM's tardy pretender to universal computer language, NPL (New Programming Language, eventually morphed into PL/I), owed a great debt to ALGOL and experiments in expanding ALGOL to greater areas of application.  Meanwhile, the radical departure of ALGOL 68 from ALGOL 60 (rejecting the practical improvements of ALGOL-W) reduced ALGOL to just-one-more esoteric programming language.

My last contact with ALGOL came in April 1986.   I flew from Rochester, New York, to Washington, DC, on a visit to the U.S. Census Bureau.  A computer-services firm that I free-lanced with wanted to respond to an RFP for converting existing census software to standard technology before the 1990 census.  To my surprise, the legacy software of concern was written in NU ALGOL and running on Univac 1100-series computers.  The Norwegian University ALGOL distribution was the descendent of the Case ALGOL 60 compiler that was also the original basis for the SIMULA language implementation.  The Census Bureau was mandated to move onto (government-recognized) standard languages and platforms.  They were looking for a mechanical solution, quite a challenge if humans would have to maintain the result, one that would be quite unnatural when expressed in any then-current production-programming languages.  I wonder how they managed.

However poorly ALGOL 60 fared as an everyday language for working programmers, its position in the founding of computer science and the inspiration of modern programming-language designs is unassailable, standing with LISP as a world-altering contribution.  Although its name is forgotten, its mark is still observable in its now-popular descendants.  We can also be grateful that Anders Hjelberg's first programming language was ALGOL.

ALGOL and the Turing Award

Perhaps the simplest demonstration of the caliber of the ALGOL 60 effort and its inspiration to computer science is observation of the connection between recipients of the ACM A. M. Turing Award and ALGOL (Ashenhurst & Graham 1987).  Four of the ALGOL 60 authors have received the Turing Award:

Peter Naur (2005)

   Citation: For fundamental contributions to programming language design and the definition of Algol 60, to compiler design, and to the art and practice of computer programming.
    

John W. Backus (1977)

   Citation: For profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on FORTRAN, and for seminal publication of formal procedures for the specification of programming languages.
   Lecture: Can Programming Be Liberated from the von Neumann Style?  A Functional Style and Its Algebra of Programs.
   Backus combined notions of applicative systems, a little APL, and a unique language, FP (and its formal implementation, FFP) to produce an idiosyncratic, personal approach to functional programming with a strong theoretical framework.  The use of the Turing Award Lecture to launch a major new look at programming was delightful, and the paper of the lecture is heavily cited in work undertaken since.
    

John McCarthy (1971)

McCarthy is a co-founder of the field of Artificial Intelligence.  His Turing Award lecture was never published.
      

Alan J. Perlis (1966)

   Citation: For his influence in the area of advanced programming techniques and compiler construction.
   Lecture: The Synthesis of Algorithmic Languages.
   The Perlis lecture examined the development harmony required in the development of data structures and procedural elements of programming languages.  He was wondering about successors to the ALGOL-like languages.  "Programmers should never be satisfied with languages which permit them to program everything, but to program nothing of interest easily."

ALGOL Contributors and the Turing Award

In addition, a remarkable number of Turing Award recipients worked with ALGOL, contributed to it, and also developed programming and programming-language concepts that extended from experience with ALGOL 60.

Edsger W. Dijkstra (1972)

   Citation: Edsger Dijkstra was a principal contributor in the late 1950's to the development of the ALGOL, a high level programming language which has become a model of clarity and mathematical rigor. He is one of the principal exponents of the science and art of programming languages in general, and has greatly contributed to our understanding of their structure, representation, and implementation. His fifteen years of publications extend from theoretical articles on graph theory to basic manuals, expository texts, and philosophical contemplations in the field of programming languages.
   Lecture: The Humble Programmer
   About ALGOL 60: "I think that it is fair to say that only very few documents as short as this have had an equally profound influence on the computing community."  Among his many accomplishments, Dijkstra produced one of the first running compilers for a complete version of the language.
    

Donald E. Knuth (1974)

   Citation: For his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the "art of computer programming" through his well-known books in a continuous series by this title.
   Lecture: Computer Programming as an Art.
   "... Everything we learn about programming helps us to improve our own artistry.  In this sense, we should continually be striving to transform every art into a science: in the process, we advance the art."
    

Robert W. Floyd (1978)

   Citation: For having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms.
   Lecture: The Paradigm of Programming.
   Floyd's startling work in making syntax analysis systematic and optimizable under verifiable conditions was amazing to me.  Donald Knuth provides a touching account of the reach of Floyd's understanding of programming and programming languages (2003).
    

C. Antony R. Hoare (1980)

   Citation: For his fundamental contributions to the definition and design of programming languages.
   Lecture: The Emperor's Old Clothes.
   "Around Easter 1961, a course on ALGOL 60 was offered in Brighton, England, with Peter Naur, Edsger W. Dijkstra, and Peter Landin as tutors. ... It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining.  It was there that I wrote the procedure, immodestly named QUICKSORT, on which my career as a computer scientist is founded.  Due credit must be paid to the genius of the designers of ALGOL 60 who included recursion in their language and enabled me to describe my invention so elegantly to the world.  I have regarded it as the highest goal of programming language design to enable good ideas to be elegantly expressed."
    

Niklaus Wirth (1984)

   Citation: For developing a sequence of innovative computer languages, EULER, ALGOL-W, MODULA and PASCAL. PASCAL has become pedagogically significant and has provided a foundation for future computer language, systems, and architectural research.
   Lecture: From Programming Language Design to Computer Construction.
   "ALGOL 60 was the first language defined with clarity; its syntax was even specified in a rigorous formalism.  The lesson was that a clear specification is a necessary but not sufficient condition for a reliable and effective implementation."
   "Occasionally, it has been claimed that Pascal was designed as a language for teaching.  Although this is correct, its use in teaching was not the only goal.  In fact, I do not believe in using tools and formalisms in teaching that are inadequate for any practical task. ... [Teaching with Pascal] turned out to be a success because it allowed the teacher to concentrate more heavily on structures and concepts than features and peculiarities, that is, on principles rather than techniques."
    

Ole-Johan Dahl and Kristen Nygaard (2001)

   Citation: For ideas fundamental to the emergence of object oriented programming, through their design of the programming languages Simula I and Simula 67.  
   Both recipients died before they were able to deliver a lecture of their choice at OOPSLA 2002 in Seattle.

Sources

Ashenhurst, Robert L., Graham, Susan., eds. (1987)

ACM Turing Award Lectures, The First Twenty Years: 1966-1985.  ACM Press Anthology Series.  Addison-Wesley, Reading, MA.  ISBN 0-201-07794-9.
    

Knuth, Donald E. (2003)

Robert W. Floyd, In Memoriam.  ACM SIGACT News 34, 4 (December 2003), 3-13.  Available at <http://doi.acm.org/10.1145/954092.954488>.  Adobe Postscript ps.gz file also available as unrefereed paper Q201 via <http://www-cs-faculty.stanford.edu/~knuth/preprints.html#unref>.
    

Naur, Peter, et.al. (1960)

Report on the Algorithmic Language ALGOL 60.  Comm. ACM 3, 5 (May 1960), 299-314.  Available at <http://doi.acm.org/10.1145/367236.367262>.
    

Naur, Peter, et.al. (1963)

Revised Report on the Algorithmic Language ALGOL 60.  Comm. ACM 6, 1 (January 1963), 1-17.   Available at <http://doi.acm.org/10.1145/366193.366201>.  An HTML version is on-line at <http://www.masswerk.at/algol60/report.htm>.

posted by orcmid at 3/15/2006 12:08:34 PM, rating data by NewsGator Online