Re: Programming language specification languages

Nick Maclaren writes:
> Also, because this is a DESIGN process, I am keen not to have to use a
> notation that forces me to use a markup language, on the grounds that
> semi-automatic searching and editing of plain text is so much easier.
> All good 1960s and 1970s software engineering principles, though
> that's not what we called it then. What I want is something enough
> beyond BNF that I can define type-consistency, scoping, aliasing and
> value-constraint rules. The really fancy stuff can be said in
> English.
>
> It is easy enough to invent my own notation, but that is a stupid
> idea on several grounds. The question is whether needs must, or
> whether there is an appropriate specification language. Has anyone
> considered or tackled this task, and with what conclusion, if any?


Concentrating on extensions to BNF, let me recommend 3 things (all
represented in ASCII text).


1) Eli (a parsing tool) has a notation called "OIL" which is
      specifically intended to address the specification of type
      consistency and conversions.


2) FNC2 (another parsing tool) represents all internal structures (in
      particular AST's) as LISP-like trees and has defined a nice set of
      rules for writing grammars that operate on trees (again using a
      LISP-like notaton).


3) Along the same lines as FNC2, SORCERER (part of the PCCTS toolkit)
      is a tree parser (and the latest version of the toolkit (renamed
      ANTLR) integrated the concept into the parsing model, so it is no
      longer a standalone tool).


The point of suggestions 2 and 3 is that it might be suitable to
express your model in a subset of the source language, and define the
"higher level" semantics in terms of transformations to the lower
level dialect (using an "as if" rule). Languages in the LISP family
have long used this idea to great effect.


For example, I think C would be a much simpler language semantically
if each operations was described terms of a dialect of C where each
statement could have only 1 operator (and that operator was "atomic"
on some set of data types (perhaps only chars)) and between each
operator there was a "sequence point" in C terms and complex
operations made the order of evaluation and temporaries explicit
(again, at least in an "as if" way). Something like,


source: a = b ? c + d : e + ( f * g );
definition: (must be executed "as if" the user had written)
t0 = b != 0;
                t1 = c + d;
                t2 = f * g;
t3 = e + t2;
if ( t0 ) {
a = t1;
}
else {
a = t2;
}


Note, we actually built an optimizing compiler built on this concept
while I was a consultant at Honeywell. The key feature it has is that
if one codes one's optimizations to respect safety, it eliminates many
bugs where changing the optimization level has rearranged the side-
effects. This allows novice and careless programmers to end up with
fewer surprises. And as I said, I think C would be a nicer language,
if that's how the specification defined it (sure it would have been a
little tougher on some compilers to generate optimal code without
doing analysis), but I think the increased portability of code that
resulted (less code would flounder on the rocks of undefined behavior
due to code ordering) would have been worth it.


BTW, in terms of Algol 68, as you know, 2-level grammars have been
shown to be equivalent in power to attribute grammars (and vice versa)
and similarly they are equivalent to manipulations of AST trees.
Thus, a notation that describes (constrains, operates on) AST trees
gives you the type of descriptive power you need. And some
specialized notations (e.g. OIL) can address certain parts of the
problem, so one doesn't have to write an one-shot interpreter to
enforce all the rules.


Actually, now that I'm thinking along that way, using SSA
(static-single assignment form) is another way to constrain your
notation so that it has well-defined semantics, by applying an already
developed model.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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