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:
- The Wild_Life
User Manual (700K) contains complete documentation of the
preprocessor in Appendix F.
The latest release of Wild_Life, including complete source code of
the preprocessor, is available by anonymous ftp
from gatekeeper.dec.com in pub/plan/Life1.01.tar.Z.
- Appendix F (120K)
of the Wild_Life User Manual contains only the preprocessor documentation.
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
- Peter Van Roy,
Extended DCG Notation: A Tool for Applicative Programming in Prolog,
Technical Report UCB/CSD 90/583,
Computer Science Division,
UC Berkeley, July 1990.
- Large parts of the Aquarius Prolog compiler
are written with EDCG's. To get a free copy of the Full release
of Aquarius, which contains source code,
send a message with empty subject and body
get aquarius-info license to
listserv@acal-server.usc.edu.
- To illustrate the use of EDCGs in large programs,
here is the source code of Aquarius Prolog's global analysis module
(analyze.pl)
and its unification compiler module
(unify.pl).
Both of these modules extensively use EDCGs.
These modules are of intrinsic interest as well.
The global analysis is a practical and fairly efficient implementation of
abstract interpretation.
The unification compiler does its best to take all type and mode
information into account for the compilation.
Please send all comments to vanroy@dfki.uni-sb.de.