Fountain Definition

This document defines the Fountain Grammar Formalism.

It does this in part by test cases. These test cases are written in Falderal format.

Grammar of Fountain

This grammar is written in EBNF. Any amount of whitespace may occur between tokens (and for this purpose, comments, which are introduced by // and extend until the end of the line, count as whitespace). Some whitespace must appear between tokens if the tokens would otherwise be interpreted as a single token. The bottommost productions in the grammar describe the concrete structure of tokens; in these productions no whitespace may appear between successive concrete terminals (the symbols enclosed in big angle quotes.) Note, this paragraph should be rewritten for clarity at some point.

Grammar ::= {Production}.
Production ::= NonTerminal [Formals] {ProdQual} "::=" {ProdExpr0}.
ProdQual ::= "(*)" | "(!)".
ProdExpr0 ::= ProdExpr1 {"|" ProdExpr1}.
ProdExpr1 ::= Term {Term}.
Term  ::= "{" ProdExpr0 "}"
        | "(" ProdExpr0 ")"
        | "<." Constraint ".>"
        | Terminal
        | NonTerminal [Actuals].
NonTerminal ::= <<upper>><<alphanumeric>>*.
Terminal ::= StrLit | <<#>>IntLit.
Formals ::= "<" Variable {"," Variable} ">".
Actuals ::= "<" VarExpr {"," VarExpr} ">".
Constraint ::= Variable Op ConExpr.
Op := "=" | "+=" | "-="  | ">" | "<".
ConExpr ::= VarExpr | Literal.
VarExpr ::= Variable.
Literal ::= IntLit | StrLit.
IntLit ::= [<<->>] <<digit>>+.
StrLit ::= <<">> <<any except ">>+ <<">>.

Tests follow.

-> Functionality "Parse using Fountain Grammar" is implemented by
-> shell command "bin/fountain parse %(test-body-file) %(test-input-file)"

-> Functionality "Parse using Fountain Grammar with fixed input parameter n=3" is implemented by
-> shell command "bin/fountain parse %(test-body-file) %(test-input-file) n=3"

-> Functionality "Generate using Fountain Grammar" is implemented by
-> shell command "bin/fountain generate %(test-body-file)"

-> Functionality "Generate using Fountain Grammar with input parameters" is implemented by
-> shell command "bin/fountain generate %(test-body-file) %(test-input-text)"

Tests for Parsing

-> Tests for functionality "Parse using Fountain Grammar"

Sequence.

Goal ::= "f" "o" "o";
<=== foo
===> Success

Goal ::= "f" #111 #111;
<=== foo
===> Success

Goal ::= "f" "o" "o";
<=== fog
???> Failure

Goal ::= "foo";
<=== foom
===> Remaining: "m"

Goal ::= "foo";
<=== fo
???> Failure

Alternation and recursion.

Goal ::= "(" Goal ")" | "0";
<=== (((0)))
===> Success

Goal ::= "(" Goal ")" | "0";
<=== ()
???> Failure

Goal ::= "(" Goal ")" | "0";
<=== 0
===> Success

Repetition.

Goal ::= "(" {"0"} ")";
<=== (0)
===> Success

Goal ::= "(" {"0"} ")";
<=== (000000)
===> Success

Goal ::= "(" {"0"} ")";
<=== ()
===> Success

Goal ::= "(" {"0"} ")";
<=== (00001)
???> Failure

Parsing with Constraints

This one succeeds because it satisfies all constraints.

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

This one fails at the <. b = n .> constraint.

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

Integers used in constraints may be negative.

Goal ::= <. a = -3 .> { "a" <. a += 1 .> } <. a = 0 .>;
<=== aaa
===> Success

Goal ::= <. a = -3 .> { "a" <. a += 1 .> } <. a = 0 .>;
<=== aa
???> Failure

Increment and decrement constraints by constant.

Goal ::= <. a = 3 .> "a" <. a += 3 .> "a" <. a -= 2 .> "a" <. a = 4 .>;
<=== aaa
===> Success

Increment and decrement constraints by variable.

Goal ::= <. a = 3 .> <. b = 4 .> <. c = 5 .> "a" <. a += b .> "a" <. a -= c .> "a" <. a = 2 .>;
<=== aaa
===> Success

Greater-than and less-than constraints by constant.

Goal ::= <. a = 3 .> <. a > 2 .> <. a < 4 .> "a";
<=== a
===> Success

Greater-than and less-than constraints by variable.

Goal ::= <. a = 3 .> <. h = 4 .> <. l = 2 .> <. a > l .> <. a < h .> "a";
<=== a
===> Success

Greater-than-or-equal and less-than-or-equal constraints by constant.

Goal ::= <. a = 3 .> <. a >= 2 .> <. a <= 4 .> "a";
<=== a
===> Success

Goal ::= <. a = 3 .> <. a >= 3 .> <. a <= 3 .> "a";
<=== a
===> Success

Greater-than-or-equal and less-than-or-equal constraints by variable.

Goal ::= <. a = 3 .> <. h = 4 .> <. l = 2 .> <. a >= l .> <. a <= h .> "a";
<=== a
===> Success

Goal ::= <. a = 3 .> <. h = 3 .> <. l = 3 .> <. a >= l .> <. a <= h .> "a";
<=== a
===> Success

Values used in constraints and assigned to variables can be integers, but they can also be other data types, namely strings, and in the future probably other data types, like records of some sort. Note, this syntax is provisional.

Goal ::= <. a = "foo" .> "a" <. a = "foo" .>;
<=== a
===> Success

Goal ::= <. a = "foo" .> "a" <. a = "bar" .>;
<=== a
???> Failure

Note, strings are ordered. Relative operators can be used in constraints with strings.

Goal ::= <. a = "foo" .> "a" <. a > "bar" .>;
<=== a
===> Success

Goal ::= <. a = "foo" .> "a" <. a < "bar" .>;
<=== a
???> Failure

However, strings cannot be incremented or decremented. This will always fail.

Goal ::= <. a = "foo" .> <. a += 1 .> "a";
<=== a
???> Failure

Goal ::= <. a = "foo" .> "a" <. a -= 1 .>;
<=== a
???> Failure

Parsing with local variables

Goal ::= "Hi" Sp "there" Sp "world" "!";
Sp ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .>;
<=== Hi there world!
===> Success

Goal ::= "Hi" Sp "there" Sp "world" "!";
Sp ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .>;
<=== Hi     there  world!
===> Success

Parsing with parameters

Goal ::= "Hi" Sp<a> "there" Sp<a> "world" "!";
Sp<x> ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .> <. n = x .>;
<=== Hi there world!
===> Success

Goal ::= "Hi" Sp<a> "there" Sp<a> "world" "!";
Sp<x> ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .> <. n = x .>;
<=== Hi   there   world!
===> Success

Goal ::= "Hi" Sp<a> "there" Sp<a> "world" "!";
Sp<n> ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .>;
<=== Hi   there  world!
???> Failure

Goal ::= "Hi" Sp<a> "there" Sp<b> "world" "!";
Sp<n> ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .>;
<=== Hi   there  world!
===> Success

Parsing with external parameters

-> Tests for functionality "Parse using Fountain Grammar with fixed input parameter n=3"

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

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

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

Backtracking

A production may be marked as allowing backtracking to occur within it, with the (*) symbol.

When a production is marked as allowing backtracking, the alternatives in it are not required to each begin with a constraint that selects it uniquely based on the state. Instead, all applicable alternatives are tried. (The order in which they are tried is immaterial for parsing, but not for generation -- see below for more on that.)

9 is divisible by 3.

Goal(*) ::= "a" { "bb" } "c" | "a" { "bbb" } "c";
<=== abbbbbbbbbc
===> Success

10 is divisible by 2.

Goal(*) ::= "a" { "bb" } "c" | "a" { "bbb" } "c";
<=== abbbbbbbbbbc
===> Success

11 is not divisible by 2 or by 3.

Goal(*) ::= "a" { "bb" } "c" | "a" { "bbb" } "c";
<=== abbbbbbbbbbbc
???> Failure

Backtracking does not currently work as you would expect inside loops.

Goal(*) ::= "a" { "bb" | "bbb" } "c";
<=== abbbbbbbbbc
???> Failure

We can however write the loop as a recursive production.

Goal(*) ::= "a" R;
R(*)    ::= "bb" R | "bbb" R | "c";
<=== abbbbbbbbbc
===> Success

But note, the "choice point scope" is limited to the alternation expression. So this formulation won't work:

Goal(*) ::= "a" R "c";
R(*)    ::= "bb" R | "bbb" R;
<=== abbbbbbbbbc
???> Failure

Note how these don't work at all with backtracking disabled, because two of the alternatives start with the same terminal.

Goal ::= "a" { "bb" } "c" | "a" { "bbb" } "c";
<=== abbbbbbbbbc
???> Multiple pre-conditions

Tests for Generation

-> Tests for functionality "Generate using Fountain Grammar"

Sequence.

Goal ::= "f" "o" "o";
===> foo

Alternation. Note that, when generating, Alt choices need preconditions because, unlike parsing, we need some guidance of which one to pick.

Goal ::= "f" | "o";
???> No pre-condition

Goal ::= "f" | <. a = 0 .> "o";
???> No pre-condition

Goal ::= (<. a = 0 .> "f") | "o";
???> No pre-condition

But if all choices of the Alt have constraints, we are able to select the one that fulfills the constraints.

Goal ::= <. a = 1 .> (<. a = 1 .> "f" | <. a = 0 .> "o");
===> f

Goal ::= <. a = 0 .> (<. a = 1 .> "f" | <. a = 0 .> "o");
===> o

But only and exactly one of the choices must have its constraints satisfied by the current state. If more than one choice has satisfiable constraints, then that is an ambiguous situation, and (in normal operation) it is an error.

Goal ::= <. a = 0 .> "f" | <. a = 1 .> "o";
???> Multiple pre-conditions

Goal ::= <. a = 0 .> (<. a = 0 .> "f" | <. a = 1 .> "o") (<. a = 1 .> "a" | <. a = 0 .> "z");
===> fz

Repetition. Without constraints, this will error out.

Goal ::= {"f"};
???> No postconditions defined for this Loop

Generation with Constraints

Basic constraint checking during generation of a repeated section.

Goal ::= <. a = 0 .> { "a" <. a += 1 .> } <. a = 5 .>;
===> aaaaa

Generation can also fail if constraints cannot be satisfied.

Goal ::= <. a = 0 .> "a" <. a = 2 .>;
???> Failure

This prior determination may happen outside of the processing of the grammar proper. The Fountain language does not prescribe exactly how this must happen. But it is expected that one way is for these values to be provided as input, in much the same manner the grammar itself is provided as input.

-> Tests for functionality "Generate using Fountain Grammar with input parameters"

Goal ::= <. a = 0 .> "a";
<=== b=5
===> a

Thus we can show the language previously parsed can also be generated.

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

Increment and decrement constraints by constant.

Goal ::= <. a = 3 .> "a" <. a += 3 .> "a" <. a -= 2 .> "a" <. a = 4 .>;
===> aaa

Increment and decrement constraints by variable.

Goal ::= <. a = 3 .> <. b = 4 .> <. c = 5 .> "a" <. a += b .> "a" <. a -= c .> "a" <. a = 2 .>;
===> aaa

Greater-than and less-than constraints by constant.

Goal ::= <. a = 3 .> <. a > 2 .> <. a < 4 .> "a";
===> a

Greater-than and less-than constraints by variable.

Goal ::= <. a = 3 .> <. h = 4 .> <. l = 2 .> <. a > l .> <. a < h .> "a";
===> a

Greater-than-or-equal and less-than-or-equal constraints by constant.

Goal ::= <. a = 3 .> <. a >= 2 .> <. a <= 4 .> "a";
===> a

Goal ::= <. a = 3 .> <. a >= 3 .> <. a <= 3 .> "a";
===> a

Greater-than-or-equal and less-than-or-equal constraints by variable.

Goal ::= <. a = 3 .> <. h = 4 .> <. l = 2 .> <. a >= l .> <. a <= h .> "a";
===> a

Goal ::= <. a = 3 .> <. h = 3 .> <. l = 3 .> <. a >= l .> <. a <= h .> "a";
===> a

Generation with local variables

Goal ::= "Hi" Sp "there" Sp "world" "!";
Sp ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .>;
<=== 
===> Hi there world!

Generation with external parameters

Goal ::= "Hi" Sp<a> "there" Sp<a> "world" "!";
Sp<x> ::= <. n = 0 .> { " " <. n += 1 .> } <. n > 0 .> <. n = x .>;
<=== a=3
===> Hi   there   world!

Backtracking

A production may be marked as allowing backtracking to occur within it, with the (*) qualifier.

Backtracking is by default nondeterministic, meaning that alternatives are tried in an undefined order. For parsing, this doesn't matter, but for generation it can make a difference. An additional qualifier, (!), selects deterministic backtracking, meaning that alternatives are tried in the order they appear in the source code.

Note that, like with parsing, the "choice point scope" for backtracking is limited to the alternation expression. So any failure after (that is, outside of) the alternation expression won't cause a backtrack to occur.

Goal(*) ::= <. n = 0 .> ("a" | "b" <. n += 1 .>) ("a" <. n += 1 .> | "b") <. n = 2 .>;
<=== 
???> Failure

So to get these to work, they need to be formulated in a "tail recursive" way that may not be entirely natural.

Goal(*)    ::= <. n = 0 .> One<n>;
One<n>(*)  ::= ("a" Two<n> | "b" <. n += 1 .> Two<n>);
Two<n>(*)  ::= ("a" <. n += 1 .> Three<n> | "b" Three<n>);
Three<n>(*)::= <. n = 2 .>;
<=== 
===> ba

The "tail recursive" production can be actually recursive to allow this backtracking to have an unbounded extent. (Note that this is selected to be deterministic backtracking so that we always get the same resulting string.)

Goal<n>          ::= <. a = 0 .> Item<a, n>;
Item<a, n>(*)(!) ::= <. a = n .>
                   | "####" <. a += 4 .> <. a <= n .> Item<a, n>
                   | "ooooo" <. a += 5 .> <. a <= n .> Item<a, n>
                   | "xxxxxxx" <. a += 7 .> <. a <= n .> Item<a, n>;
<=== n=30
===> ####################oooooooooo

You can't sum to 6 with these choices.

Goal<n>       ::= <. a = 0 .> Item<a, n>;
Item<a, n>(*) ::= <. a = n .>
                | "####" <. a += 4 .> <. a <= n .> Item<a, n>
                | "ooooo" <. a += 5 .> <. a <= n .> Item<a, n>
                | "xxxxxxx" <. a += 7 .> <. a <= n .> Item<a, n>;
<=== n=6
???> Failure

Note how these don't work at all with backtracking disabled, because two of the alternatives start with the same terminal.

Goal<n>       ::= <. a = 0 .> Item<a, n>;
Item<a, n>    ::= <. a = n .>
                | "####" <. a += 4 .> <. a <= n .> Item<a, n>
                | "ooooo" <. a += 5 .> <. a <= n .> Item<a, n>
                | "xxxxxxx" <. a += 7 .> <. a <= n .> Item<a, n>;
<=== n=6
???> No pre-condition

The alternation processed as ordered choice, above, can also be processed with nondeterministic choice. In this case, the process by which the alternative is selected is not defined by the language.

This makes it difficult to write a sensible test for the behaviour at the language level. However, implementations may define how they implement nondeterministic choice, and provide their own test cases.