Implementation notes for the _Ascesis_ parser
=============================================
## _Thin arrow_ rules
In principle, a _thin arrow_ rule doesn't unfold to a proper
(coherent) c-e structure, except in special cases, where there is a
loop on every non-isolated node. Thin arrow rules come in four
variations.
### _Effect-only_ rules
```ebnf
e_rule = node_list "->" polynomial ;
```
This rule specifies an effect `polynomial` for all nodes in the
`node_list`. An effect-only rule generates
- set _T_ of sending ports, one port for each node in the
`node_list`,
- set _R_ of receiving ports, one port for each node occurring in
the `polynomial`,
- set of thin, effect-only links, one for each pair in _T_ ×
_R_.
For example, `a b -> c d` generates ports `[a >]`, `[b >]`, `[c <]`,
`[d <]`, and effect-only links `(a >? c)`, `(a >? d)`, `(b >? c)`,
`(b >? d)`. Cause polynomials of nodes `c` and `d` are _θ_,
hence this rule doesn't unfold to a proper c-e structure.
### _Cause-only_ rules
```ebnf
c_rule = node_list "<-" polynomial ;
```
This rule specifies a cause `polynomial` for all nodes in the
`node_list`. A cause-only rule generates
- set _R_ of receiving ports, one port for each node in the
`node_list`,
- set _T_ of sending ports, one port for each node occurring in the
`polynomial`,
- set of thin, cause-only links, one for each pair in _T_ ×
_R_.
### _Cause-then-effect_ and _forward_ rules
```ebnf
ce_rule = node_list "<-" polynomial "->" polynomial ;
fw_rule = polynomial "->" node_list "->" polynomial ;
```
A cause-then-effect (or forward) rule generates
- set _T_ of sending ports and a set _R_ of corresponding receiving
antiports, one sending port and one receiving port for each node
in the `node_list`,
- set _T'_ of sending ports, one port for each node occurring in the
left `polynomial`,
- set _R'_ of receivingg port, one port for each node occurring in
the right `polynomial`,
- set of effect-only links, one for each pair in (_T_ × _R'_) \\
(_T'_ × _R_),
- set of cause-only links, one for each pair in (_T'_ × _R_)
\\ (_T_ × _R'_),
- set of fat links, one for each pair in (_T_ × _R'_) ∩
(_T'_ × _R_).
For example, `a -> b -> a` generates ports `[a >]`, `[a <]`, `[b >]`,
`[b <]`, cause-only link `(a ?> b)`, and effect-only link `(b >? a)`.
This rule doesn't unfold to a proper c-e structure, because both
polynomials of node `a` are _θ_.
However, since `a b -> a b -> a b` generates the same ports as above
and four fat links, `(a > a)`, `(b > b)`, `(a > b)`, `(b > a)`, it
unfolds to a proper c-e structure.
### _Effect-then-cause_ and _backward_ rules
```ebnf
ec_rule = node_list "->" polynomial "<-" polynomial ;
bw_rule = polynomial "<-" node_list "<-" polynomial ;
```
These are semantically equivalent to cause-then-effect rules with left
and right polynomials exchanged. See above.
## _Fat arrow_ rules
```ebnf
A fat arrow rule is transformed into a sum ('+'-separated sequence) of
thin arrow rules. This procedure takes several steps. A fat arrow
rule with more than two polynomials is first transformed into a sum of
two-polynomial fat arrow rules, for example `b <= a <=> c` becomes `{
a => b } + { a <=> c }`. Then each two-way two-polynomial fat arrow
rule is transformed into a sum of two one-way fat arrow rules, for
example `a <=> c` becomes `{ a => c } + { c => a }`. Then each one-way
two-polynomial fat arrow rule is replaced with a sum of two thin arrow
rules, one effect-only, another cause-only. Next,
- the resulting rule expression is simplified by integrating
effect-only rules having a common node list and doing the same
with cause-only rules; subsequently,
- rule expression is further simplified by merging node lists which
point to the same effect polynomials, and merging node lists
pointed to by the same cause polynomials.
Last two steps are repeated, until a fixed point is reached. Finally,
since the result is a sum of single-polynomial thin arrow rules, any
pair of rules with the same node list is combined into a
two-polynomial rule.
For example, `a b c => d e f` is transformed to
```rust
{ a b c -> d e f } + { d e f <- a b c }
```
`b <= a <=> c` is transformed to
```rust
{ a <- c } + { a -> b + c } + { b c <- a } + { c -> a }
```
etc. A fat arrow rule always unfolds to a proper (coherent) c-e
structure. However, there are structures undefinable with fat arrow
rules only, as a simple triangle structure shows:
```rust
{ a -> b c } + { b <- a c } + { c <- a -> b }
```
## Two forms of c-e structure instantiation
Template instantiations are syntactically distinguished from immediate
instantiations, similarly to Rust macro invocations, which differ from
Rust function calls. When a c-e structure name is used in a template
instantiation, it must be followed by the exclamation mark. [The
specification](ascesis-syntax.ebnf) therefore defines two productions
for the `ces_instance` nonterminal,
```ebnf
ces_instance = identifier "(" ")"
| identifier "!" "(" instance_args ")" ;
```
where `instance_args` expects a nonempty list of arguments,
```ebnf
instance_args = arg_value { "," arg_value } [ "," ] ;
```
The reason for decorating template instantiations with exclamation
mark is twofold. Without,
- the standalone _Ascesis_ language would be less consistent with
[Rust-embedded `ascetic` DSL](ascetic-macros.md), and
- it would contain LR-unparsable sentences, hence requiring to
precede proper parsing with a disambiguation pass.
## What is a node list?
A node list is defined in [the specification](ascesis-syntax.ebnf) as
a sequence of node identifiers,
```ebnf
node_list = identifier { identifier } ;
```
However, in the files
[`ascesis_grammar.bnf`](../src/ascesis_grammar.bnf) and
[`ascesis_parser.lalrpop`](../src/ascesis_parser.lalrpop) `NodeList`
is defined as an alias of the `Polynomial` nonterminal. If, instead,
`NodeList` was implemented as a separate nonterminal with a narrower
sublanguage than that of `Polynomial`, then the current grammar of
_Ascesis_ couldn't be transformed directly into an LR parser.
Therefore, an object of type `Polynomial` carries a flag indicating
whether it is a monomial which was constructed from a syntactically
flat list of node identifiers, and thus it qualifies as a valid node
list following the specification. Node lists are to be notated
without parentheses or an addition operator — leading plus sign
is not allowed, nor an expression reducible by idempotence of
addition.
## Do we need thin forward rules?
Probably not, and they may be removed from future versions of the
language, once it is clear that pushing node list from the front of a
thin arrow rule, to the middle, will cause confussion or make _mental_
parsing harder. On the other hand, they may stay in the language, if
it turns out that the more important factor will be the iconic value
of the formula `cause -> state -> effect` as a hint to the flow of
time, a left-to-right timeline.
## How to support incremental construction?
The idea is to be able to declare template arguments as `Hybrid`, so
that they would accept passing nodes as well as structures.