History of Fountain

0.7

Added the --convert-loops flag to the implementation, which causes loops to be converted to recursion internally, before executing the requested functionality. All tests currently pass both with and without this flag.

Added the --fuel-factor and --initial-fuel flags to the implementation, which impose limits on the ability of a Fountain grammar to recurse. If --fuel-factor is given, the processing is subject to fuel management, which is summarized as follows:

• processing begins with an initial amount of "fuel" specified by --initial-fuel (default 0)
• each time a character is parsed or generated, "fuel" is increased by the number of units specified by --fuel-factor
• each time a non-terminal is descended into, one unit of "fuel" is expended
• if all available "fuel" is exhausted, parsing fails with an "out of fuel" condition.

The effect of this is that the number of times a grammar can descend into a non-terminal is bounded linearly by the length of the string being parsed or generated. Since a single non-terminal can consume only a fixed amount of storage, this limits Fountain to simulating a Linear Bounded Automaton (LBA), which is the known bounds for parsing Context-Sensitive Languages (CSLs).

--fuel-factor may only be specified when --convert-loops is also specified.

Also moved project history to its own HISTORY.md file.

0.6

Parameters supplied externally to the parsing or generation process must be declared on the start symbol in order for them to be visible to the grammar.

Fixed up syntax for && so it is now infix again, on parsing and pretty-printing. It is now called Conj internally.

Added support for the following constraints:

• negation (prefix ~) of constraints;
• disjunction (infix ||) of constraints;
• defined, which succeeds only when a variable is defined;
• lookahead assertions;
• generating, which succeeds only when generating.

(although these should all be considered somewhat experimental, presently).

The check (during deterministic operation) that every branch of an alternation has preconditions has been dropped. Instead the user will only get the error that multiple branches of the alternation are allowable, and the parsing or generation will not proceed.

Refactored internals to attempt to make parser and generator more similar to each other.

Added speculative writings on how we might desugar loops into recursive productions.

(Version 0.6 is perhaps best viewed as the fallout of trying to desugar loops into recursive functions, realizing afresh that loops have different semantics under parsing and generation (including an implicit ordered choice) and trying to capture those different semantics in constraints so that they could be applied during recursive applications just as well.)

0.5

Backtracking may be either nondeterministic (the default, with the (*) qualifier on a production) or deterministic (with the (!) qualifier). For parsing this doesn't matter, but for generation, deterministic backtracking follows the source code order. The ordering of nondeterministic backtracking is undefined by the Fountain language, but the fountain implementation uses uniform pseudo-random shuffling of the alternatives based on a user-supplied seed which defaults to 0.

Variables may take on values of types other than integer. This is a work in progress. Currently, the only other type of value available is the string type. The plan is that string type values can be used as (variable) terminals. But that plan will not come to fruition in the scope of version 0.5.

0.4

Language

Fountain now distinguishes between productions that may backtrack and ones that may not, in both parsing and generation.

By default, backtracking is not permitted. Productions may be marked with (*) to indicate that backtracking is permitted when processing alternations in that production.

When backtracking is not permitted, every choice in an alternation must start with a constraint. Exactly zero or one of those constraints must be satisfied in a given state. If none are, that is a failure (and if this failure happens in an enclosing context where backtracking is permitted, then backtracking will occur in that context). If more than one are, the process will abort with an error message.

It should be noted that the implementation of backtracking currently has limitations. The scope of a "choice point" that can be backtracked to is limited to the alternation expression in which it occurs; a failure that occurs after (that is, outside of) this expression will not cause a backtrack to occur. In particular, backtracking does not work at all as you might expect inside a loop. There is a way to write recursive productions in a "tail recursive" manner such that they do backtrack, but this style of writing the grammar may not be entirely natural.

Also:

Greater than or equal and less than or equal constraints.

"Both" combinator on constraints (which really needs reworking).

Implementation

The --start-symbol option may now be passed to fountain to cause it to start parsing or generating at the named non-terminal.

Implementation improvements such as better flattening of the AST representing the grammar during its parsing, and pretty-printing fragments of the AST (albeit crudely) when displaying them.

0.3

Comments and characters terminals given by Unicode code point were added to the Fountain syntax.

Inc, dec, greater than and less than constraints can take a simple expression (an integer literal or a variable name) on the right-hand side.

When parsing, parameters can also be supplied from external sources.

Example Fountain grammar describing a heartwarming and context-sensitive novel about a wayward animal companion has been included in the distribution.

Distribution placed under BSD license.

0.2

0.2 refined some of the core ideas of Fountain. The Design of Fountain document (consisting primarily of design questions rather than design answers) was written. Parameter passing was added to productions. Many small improvements were made to the reference implementation.

0.1 had an arb construct, which was intended to signal that a variable could be computed during parsing, but was needed to be defined ("arbitrarily") beforehand during generation. Essentially it asserted that the variable was defined, but only during generation. During the design work for 0.2 it was determined that it was not necessary (this sort of signal overlaps with parameters to a production, which signal some kind of arguments need to be supplied; and in another sense, shouldn't need to be stated inside the grammar because it is the concern of the client of the grammar rather than the grammar itself), and it was removed.

0.1

0.1 was the original release of Fountain, to show proof of concept. Only global variables were supported. Efficient choice was not supported.