Tree @develop-0.12 (Download .tar.gz)
Fountain
Version 0.12 | 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.12
git clone https://git.catseye.tc/Fountain/
- Rename `--start-symbol` to `--goal-symbol` and update HISTORY.md. Chris Pressey 3 days ago
- Rename "fuel factor" to "refuel factor". Chris Pressey 3 days ago
- Update tests to reflect language def'n of settings and of fuel. Chris Pressey 4 days ago
- Parse InitialFuel as an optional command-line value. Chris Pressey 5 days ago
- This will require a little debugging Chris Pressey 5 days ago
- Begin making the fuel tests part of the language specification. Chris Pressey 5 days ago
- Make construct initial state responsible for initial fuel state Chris Pressey 6 days ago
- Parse fuel settings too. Chris Pressey 6 days ago
- A Fountain grammar can specify which symbol is the goal symbol Chris Pressey 6 days ago
- Continue refactor Chris Pressey 6 days ago