Tree @develop-0.13 (Download .tar.gz)
Fountain
Version 0.13 | 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.13
git clone https://git.catseye.tc/Fountain/
- Resolve some shadowing issues under GHC 8.8.4 Chris Pressey 15 hours ago
- Change generated NT name to avoid collision with user-supplied NTs Chris Pressey a day ago
- Fixed a parsing bug w/empty fallback choice at end of input. Chris Pressey a day ago
- The default value for initial-fuel is 5. Chris Pressey a day ago
- Refuel factor defaults to 1, not to "no fuel accounting at all" Chris Pressey 2 days ago
- Depict settings when pretty-printing grammar. Chris Pressey 2 days ago
- Add tests for running out of fuel when backtracking. Chris Pressey 2 days ago
- Define basic precedence, parenthesis, show empty parens invalid. Chris Pressey 2 days ago
- Clarify that an empty RHS to a production is not valid. Chris Pressey 2 days ago
- Clarify and fix some behaviour of settings. Chris Pressey 2 days ago