Tree @develop-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.
Commit History
@develop-0.11
git clone https://git.catseye.tc/Fountain/
- Fix and document alternative selection bug. Chris Pressey 7 days ago
- Update alternate selection to partially address bug. Chris Pressey 7 days ago
- Add more basic tests for alternation, including two that fail. Chris Pressey 7 days ago
- Update docs to improve clarity Chris Pressey 7 days ago
- Remove lookahead assertions from the language. Chris Pressey 8 days ago
- Bump version on this development branch. Chris Pressey 8 days ago
- Improve the style around the continuation used after NT processing Chris Pressey 9 days ago
- Improve test cases to be more descriptive and comprehensive. Chris Pressey 9 days ago
- Update HISTORY. Chris Pressey 9 days ago
- Improve tests w.r.t. proper backtracking behaviour. Chris Pressey 9 days ago