cfg

A context free grammar is a formal grammar where the rules all have a codomain of length 1.

Summary

Tree	A tree is a rule for the root and a list of trees called branches.
Rule	A rule is a generator of free operads, given by an atomic type dom, a type cod of arbitrary length and an optional name.
Word	A word is a leaf in a context-free tree.
Id	The identity is a rule that does nothing.
Operad	An operad is a category with a method __call__ which constructs a tree from a root and a list of branches.
Algebra	An algebra is a functor with the free operad as domain and a given operad as codomain.

Axioms

The axioms of multicategories (aka operads) hold on the nose.

>>> x, y = Ty('x'), Ty('y')
>>> f, g = Rule(x @ x, x, name='f'), Rule(x @ y, x, name='g')
>>> h = Rule(y @ x, x, name='h')
>>> assert f(g, h) == Tree(f, *[g, h])

>>> assert Id(x)(f) == f == f(Id(x), Id(x))
>>> left = f(Id(x), h)(g, Id(x), Id(x))
>>> right = f(g, Id(x))(Id(x), Id(x), h)
>>> assert f(g, h) == left == right