Montages Specifications Of Realistic Programming Languages

Program-Transformation.Org: The Program Transformation Wiki
by PhilippKutter and AlfonsoPierantonio. In Journal of Universal Computer Science, vol. 3, no. 5 (1997), 416--442


Montages are a new way of describing all aspects of programming languages formally. Such specifications are intelligible for a broad range of people involved in programming language design and use. In order to enhance readability we combine visual and textual elements to yield specifications similar in structure, length, and complexity to those in common language manuals, but with a formal semantics. The formal semantics is based on Gurevich's Abstract State Machines (formerly called Evolving Algebras).




A Montage is a, partially visual, specification of a programming language construct. The specification consists of a BNF style syntax definition of the construct, a specification of the control and data flow through the construct, and a specification of the computation on the data induced by the construct. Control and data flow are defined by means of additional edges in the abstract syntax tree. The control flow edges indicates in which order program points should be visited during execution. Data flow edges indicate the data dependencies between nodes. The flow information can be specified using a visual language. The following picture shows the control and data flow of the while construct:

Computations are defined by functions applied to the values of previously computed nodes. Control flow is determined by actions which manipulate the abstract program counter CurrentTask. Control flow can be conditional on data values.

A Montage is translated to rules for an AbstractStateMachine?. These rules define how the abstract program counter and the contents of the store are changed by the computations of the tokens. The implicit parallelism of the rules is tamed by annotating program points with flags that indicate whether it has been executed already.


  • Could control flow not be deduced from the data dependencies? First perform the computations corresponding to those nodes from which data is needed.

  • The EvaluationStrategy? is determined by the specification of control flow. How could one model different evaluation strategies for the same language? In other words, tying together all semantic aspects of a language constructs prevents reuse of some aspect.

-- EelcoVisser - 23 Dec 2001

CategoryPaper | CategoryReview