git @ Cat's Eye Technologies Fountain / 0.11
0.11

Tree @0.11 (Download .tar.gz)

Fountain

Version 0.11 | Entry @ catseye.tc

Cat's Eye Technologies' Fountain is a work-in-progress grammar formalism capable of expressing context-sensitive languages (CSLs), and supporting both efficient parsing and efficient generation of strings conforming to those languages.

It does this by allowing semantic constraints to be inserted between the elements of a production rule. To support efficient generation, these interspersed semantic constraints can be analyzed to determine a usable deterministic strategy for generation.

Here is an example Fountain grammar which expresses the classic CSL a^n b^n c^n:

Goal<n> ::=
    <. a = 0 .> { "a" <. a += 1 .> } <. a = n .>
    <. b = 0 .> { "b" <. b += 1 .> } <. b = n .>
    <. c = 0 .> { "c" <. c += 1 .> } <. c = n .>
    ;

During parsing based on this grammar, the variable n will be, like the others, initially undefined. The first time a = n is encountered, a will be unified with n, and will take on its value. When b = n is later encountered, unification of b with n will take place; if b is some value other than n, the parse will fail.

% echo -n "aaabbbccc" | ./bin/fountain parse eg/anbncn.fountain --
Success

In comparison, during generation, we assume the variable n has already been assigned a value, as part of the (externally supplied) input to the generation process. In addition, the repetition construct { "a" <. a += 1 .> } can "see" the a = n constraint that follows it; it will be checked on each iteration, and the repetition will terminate when it is true.

% ./bin/fountain generate eg/anbncn.fountain n=5
aaaaabbbbbccccc

Neither of the above processes involve backtracking; the string is parsed and generated in linear time. Fountain is, however, not restricted to determinism; modes of nondeterministic behaviour can be explicitly selected. The intent is that Fountain can express all and only the context-sensitive languages (CSLs); equivalently, that it can perform all and only the computations in polynomnial space (PSPACE). It implements a system of "fuel consumption" that intends to prevent it from performing computations that are outside these bounds.

For a more definitive description of the Fountain language, see doc/Definition-of-Fountain.md.

For insight into the design choices underlying Fountain, see doc/Design-of-Fountain.md. This includes several interesting questions that the design of Fountain raises, such as:

  • Can't a Definite Clause Grammar (DCG) do what Fountain does?
  • Doesn't a Context-Sensitive Grammar (CSG) do what Fountain does?
  • Isn't Fountain really a programming language in disguise?
  • How can it be ensured that Fountain can express only the CSLs?
  • Should we think of constraints as relational operators?
  • Why would we want to support local variables?
  • How can parameter passing be implemented?
  • How can we apply randomness during generation?
  • How should parameters with different data types be handled?

TODO

See TODO.md.

History

See HISTORY.