Pattern languages

uiucdcs!uunet!mcvax!cui!oscar (NIERSTRASZ Oscar)
4 Nov 88 12:41:14 GMT

          From comp.compilers

Related articles
Pattern languages uiucdcs!uunet!mcvax!cui!oscar (1988-11-04)
Re: Pattern languages steve@hubcap.UUCP (1988-11-07)
Re: Pattern languages ti-csl!! (John Gateley) (1988-11-15)
Re: pattern languages (1988-11-09)
Re: Pattern Languages cordy@QUCIS.BITNET (1988-11-15)
Re: Pattern languages harvard!ucbvax.Berkeley.EDU!decvax!tl-vaxa!grover (1988-11-14)
| List of all articles for this month |

From: uiucdcs!uunet!mcvax!cui!oscar (NIERSTRASZ Oscar)
Newsgroups: comp.lang.misc,comp.compilers
Date: 4 Nov 88 12:41:14 GMT
Organization: University of Geneva/Switzerland

Does anyone know of the existence of a "pattern language" that offers
the possibility of defining or extending programming languages through
the definition of patterns? What I am thinking of is something more
powerful than a macro pre-processor but not as general as yacc and
lex. The idea is to define a set of syntactic patterns and their
translations, and to then be able to program either using the patterns
alone, or to use the patterns as an extension of an existing language.

The closest examples I can think of are not general tools, but the
possibility to extend languages through overloading etc. Smalltalk,
Prolog and Lisp all make it relatively easy to add new syntactic
patterns (within certain constraints!).

The two main reasons I would like to have such a tool are:

1. To prototype new programming languages (or language constructs).
      Since the development of a new programming language and its compiler
      is a significant effort, it would be nice to have some tools for
      doing a mock-up that can be easily changed. A common trick is to
      implement the compiler as a translator to an existing high-level
      language like C, thus piggybacking on an existing compiler.
      A pattern language would be ideally suited to such translation.

2. To provide programmer definable language extensions (for enhancing
      software reusability). Programming languages suffer from the
      problem that the language design must "freeze" the language,
      pretending to anticipate the needs of all future programmers.
      Programming constructs basically define the ways in which reusable
      software can be packaged. If I discover I need generic procedures
      or object classes etc., but the language doesn't provide them, then
      I'm stuck. A pattern language would allow a programming language to
      remain open-ended.

Examples of what you should be able to do include:
- macro substitution
- expression re-writing (e.g., translation to postfix form)
- object classes (declaration, inheritance, ...)
- control abstractions (e.g., loops, transactions, ...)
- generic functions

Since a pattern language should be a relatively simple tool (in the
spirit of, say, awk), it should not be concerned with generation of
addresses, optimization, or most of the nasty things real compilers do.

The kind of functionality I believe a pattern language should provide
would be:
- definition of parameterized patterns and their semantic actions
- actions should include bookkeeping (management of scopes and
    symbol tables) and generation of output (translation)
- a primitive form of type-checking for pattern parameters
    (i.e., parameters will also be matched by patterns)
- recursive patterns

I would like to hear of any tools or languages that offer similar
functionality, and any reactions as to the feasibility or advisability
of such an animal.

Oscar Nierstrasz
C.U.I., University of Geneva, Switzerland

E-mail: oscar@cgeuge51.bitnet
[Fifteen years ago, there was IMP-72 which allowed you to put BNF in the
program that extended the language's syntax. Since it parsed with Earley's
algorithm, ambiguous syntax was OK. It worked, and you could indeed add
marvelous new syntax. It failed for three reasons that I could see: Each
program was, in effect, written in a new language, making maintenance nearly
impossible. The underlying compiler had a rather simple idea of what was
going on, making it impossible to add semantically interesting new stuff.
And, finally, Earley is an N^3 algorithm, which made the compiler so slow
that it was painful to use. -John]

Post a followup to this message

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