A Declarative Programming Language

The extensions to the classical Attribute Grammar formalism proposed in this paper improve its expressiveness and result in a language that is comparable in power to a first-order-only version of ML or Typol. While it does not subsume the latter, this ``new'' language is attractive because it retains all the pleasant properties of programming with Attribute Grammars:

• Extended specifications are still declarative, so that programmers do not need to worry about evaluation order.
• They are well structured because the classical structuring paradigm based on productions is extended to scheme productions and conditional productions.

The examples given in this paper are, unfortunately for us, too short to show the effectiveness of Olga for developping large programs. For instance, most copy rules of the form $a(X) := $a(Y) can be automatically generated and omitted from the program; this allows the developer to concentrate on important computations rather than on simple information transfer [JP90a].

This programming language is already available in our FNC-2 system [JPJ 90, JPG93]. FNC-2 provides powerful mechanisms for composition and reusability [BJPR93, Bel93, Rou94]. It is a very flexible system which can generate exhaustive or incremental attribute evaluators in C, Lisp, and ML, running on monoprocessor or shared-memory multiprocessor machines [Mar94] and using sophisticated memory optimization techniques. With companion processors, FNC-2\ can generate complete applications. But it is also an open system that can interface with many other tools. This allows a developer to fully exploit the complementarity of Attribute Grammars with other programming paradigms (in particular, functional programming), by letting him select the most appropriate language and system for each part of his application.

At first sight, allowing attributes to carry functional values (closures) and applying them in semantic rules seems totally independent from the basic Attribute Grammar\ formalism and the work described here. This is a first step towards making Olga a fully functional language, but not the topic of this paper.

Given that the choice of a programming language over another is a very subjective matter, it is not our aim here to convert every ML or Typol programmer to Olga. In fact, it is clear to us that the Attribute Grammar formalism is restricted, in that it is just a syntactic abstraction of some function or inference rule, and it does not subsume these other formalisms and tools.

Besides, in our opinion, the real interest of our work is not the language itself but the computation model that underlies it. This model is that of classical Attribute Grammars, and our work was ``just'' to extend its applicability.