Extended DCG's: Declarative Programming with State

Extended DCG's generalize Prolog's Definite Clause Grammar notation to support multiple named accumulators. EDCG's allow effective declarative programming with state. They enforce single-threading for state updating. They keep a program short and make it easier to maintain. With the term_expansion mechanism their use is transparent to the programmer. EDCG's can be considered as a sound way to combine imperative programming with logic programming. In short, EDCG's are a Good Thing. Extended DCG's are related to the use of monads in functional programming.

Logical State Threads

Logical State Threads is a package for SICStus Prolog and compatible systems that simplifies the development of large Prolog programs. The package was designed by Andreas Kagedal, Peter Van Roy and Bruno Dumant, and written mostly by Andreas Kagedal. The package subsumes the Wild_Life and Extended DCG packages. A beta version has been released in January 1997.

The Wild_Life Preprocessor

This preprocessor for the LIFE language allows accumulators to have scope and to be composed (see example below). The preprocessor was jointly developed with Bruno Dumant. The preprocessor is described in the following documents:

A Prolog Preprocessor

An extended version is available of the EDCG preprocessor that was used to build Aquarius Prolog. This preprocessor is described in the following documents:

An Example of EDCG's: Compiling Unification

To show how EDCG's are used in practice, this section presents a compilation algorithm for psi-term unification. The algorithm used is the two-stream algorithm, which is the best way to compile unification for native code compilation. The example uses the Wild_Life preprocessor and merits careful study.

Further Documentation and Examples

Please send all comments to vanroy@dfki.uni-sb.de.