Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1295

Re: Algol history, was specifying semantics

Show all headers | View raw

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.

Interestingly, wrt the original topic, Wikipedia says:

  The Algol W Language Description defines Algol W in an affix grammar
  that resembles BNF. This grammar was a precursor of the Van
  Wijngaarden grammar.

  Much of Algol W's semantics is defined grammatically:

    * Identifiers are distinguished by their definition within the
      current scope. For example, a <procedure identifier> is an
      identifier that has been defined by a procedure declaration, a
      <label identifier> is an identifier that is being used as a goto
      label.

    * The types of variables and expressions are represented by
      affixes. For example <T function identifier> is the syntactic
      entity for a function that returns a value of type T, if an
      identifier has been declared as an integer function in the
      current scope then that is expanded to <integer function
      identifier>.

    * Type errors are grammatical errors. For example "<integer
      expression> / <integer expression>" and "<real expression> /
      <real expression>" are valid but distinct syntactic entities
      that represent expressions, but "<real expression> DIV <integer
      expression>" (i.e. integer division performed on a
      floating-point value) is an invalid syntactic entity.

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.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Formatting of Language LRMs Seima Rao <seimarao@gmail.com> - 2014-06-17 16:54 +0530
  Re: Formatting of Language LRMs "lpsantil@gmail.com" <lpsantil@gmail.com> - 2014-06-20 10:10 -0700
    Re: Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-03 04:37 +0000
  Re: Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-20 12:09 -0700
    Re: Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-06-21 02:27 +0000
    Re: Formatting of Language LRMs Kaz Kylheku <kaz@kylheku.com> - 2014-06-21 03:09 +0000
    Re: Formatting of Language LRMs Joshua Cranmer 🐧 <Pidgeot18@verizon.net.invalid> - 2014-06-22 21:12 -0500
      Re: VWG and K, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-22 21:47 -0700
      RE: Formatting of Language LRMs "Costello, Roger L." <costello@mitre.org> - 2014-07-03 09:06 +0000
        Re: Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-07-03 22:30 -0700
          Re: syntax checkers, was Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-04 17:35 +0000
          Re: executable semantics, was Formatting of Language LRMs wclodius@earthlink.net (William Clodius) - 2014-07-04 15:53 -0600
  Re: specifying semantics, was Formatting of Language LRMs seimarao@gmail.com - 2014-06-24 02:19 -0700
    Re: specifying semantics, was Formatting of Language LRMs "lpsantil@gmail.com" <lpsantil@gmail.com> - 2014-06-24 13:12 -0700
    Re: specifying semantics, was Formatting of Language LRMs George Neuner <gneuner2@comcast.net> - 2014-06-26 00:54 -0400
      Re: specifying semantics, was Formatting of Language LRMs Andy Walker <news@cuboid.co.uk> - 2014-06-28 20:10 +0100
        Re: specifying semantics, was Formatting of Language LRMs George Neuner <gneuner2@comcast.net> - 2014-06-28 22:43 -0400
          Re: BNF, was specifying semantics wclodius@earthlink.net (William Clodius) - 2014-06-30 22:00 -0600
      Re: specifying semantics, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-28 12:25 -0700
        Re: specifying semantics, was Formatting of Language LRMs Andy Walker <news@cuboid.co.uk> - 2014-06-29 11:19 +0100
        Re: specifying semantics, was Formatting of Language LRMs George Neuner <gneuner2@comcast.net> - 2014-06-29 07:56 -0400
          Re: specifying semantics, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-29 11:49 -0700
            Re: specifying semantics, was Formatting of Language LRMs Gene Wirchenko <genew@telus.net> - 2014-06-30 18:09 -0700
              Re: specifying semantics, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-30 20:53 -0700
                Re: Algol history, was specifying semantics anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-03 11:51 +0000
                Re: Algol history, was specifying semantics Ivan Godard <ivan@ootbcomp.com> - 2014-07-03 22:20 -0700
                Re: Algol history, was specifying semantics wclodius@earthlink.net (William Clodius) - 2014-07-04 15:52 -0600
                Re: Algol history, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-07 05:49 +0000
                Re: Algol history, was specifying semantics Ivan Godard <ivan@ootbcomp.com> - 2014-07-07 10:48 -0700
                Re: Algol history, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-07 19:49 +0000
                Re: Algol history, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-07 19:43 +0000
                Re: specifying semantics, was Formatting of Language LRMs Gene Wirchenko <genew@telus.net> - 2014-07-03 21:44 -0700
            Re: specifying semantics, was Formatting of Language LRMs anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-02 09:51 +0000
              Re: specifying semantics, was Formatting of Language LRMs Stefan Monnier <monnier@iro.umontreal.ca> - 2014-07-03 10:15 -0400
                Re: specifying semantics, was Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-04 06:08 +0000
                Re: specifying semantics, was Formatting of Language LRMs Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-07-04 08:51 +0200
                Re: Parsing Fortran, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-04 17:53 +0000
                Re: Parsing Fortran, was specifying semantics wclodius@earthlink.net (William Clodius) - 2014-07-04 15:57 -0600
  Re: Formatting of Language LRMs mertesthomas@gmail.com - 2014-06-30 12:04 -0700
  Re: Formatting of Language LRMs federation2005@netzero.com - 2014-07-28 17:55 -0700
    Re: Formatting of Language LRMs federation2005@netzero.com - 2014-08-01 14:58 -0700

csiph-web