Generative Grammar-based Computation

A promising approach for set comprehension and set processing is to utilize generative grammars. Generative grammars essentially denote the set of 'sentences' they will generate, and a set of sentences can carry complex information about the world and one's designs for it.

With grammar-based computation, the primary operations would be composition and refinement of grammars. Working with the 'sentences' directly is marginalized except to the extent that literals describe relatively trivial grammars. This breaks from traditional application of grammars, which is to analyze a sentence for 'matches' and to provide rewrite rules that generate a new sentence. This traditional application mirrors common functional programming (pattern matching and production rules), and is often 'lossy' in the sense that one cannot regenerate the original sentence from the matching rules. Grammar-based computation doesn't involve 'rewriting'; there is no explicit 'generated sentence'.

Instead, grammar-based computation is very close to logic-programming. A grammar can be understood as a sort of predicate that will classify the sentences it generates. For example, a grammar named 'Sum' might generate sentences of the form (A B C) where A, B, C represent integers and A+B=C. One might refine this into a new grammar Add4 that generates sentences of the form (B C) where 4+B=C. Simple constraint programming is also feasible - i.e. all (B C) sentences where C < 100 - and then one can 'generate' solutions to the constraint problem.

At the edges of the system, one could ask for sample sentences. Within a grammar, 'queries' would need to be simple without hindering composition of grammars. Perhaps G1\G2 is a composition that generates G1 if G1 is not empty, otherwise generates as G2. (Another useful query might be whether G1 produces a unique sentence... perhaps some sort of 'at least one, at most one' approach.)

The challenge I've been facing is making this practical. By practical I mean supporting properties such as:

  • Supports local reasoning about performance (time-space complexity) and termination across composition.
  • Predictable samples. Perhaps deterministic browsing of sample sentences, or some ability to reason about whether a grammar will produce a unique sentence. Unfortunately, this sort of determinism tends to hinder grammar-rewrites and parallelism. A reflective approach to have this determinism only where critical might be more appropriate.
  • Modularity and information hiding: able to eliminate sub-grammars that do not contribute sentences; able to reason about when information embedded in a grammar can be eliminated from the output grammar. Practically, this means some sort of canonical form for grammars that will be more compressed than the infinite set.
  • Structurally expressive: sentences able to effectively express sequences, multi-dimensional matrices, sparse matrices, sets, cyclic graphs, trees. (Sentences do not need to be impoverished 'strings' - strict character sequences. Structured sentences are okay.) Bonus points if able to effectively describe continuous spaces (i.e. a vector-field in space-time, or a probability cloud). Bonus point if generated sentences can contain grammars (i.e. grammars can generate grammars; first-class grammars) allowing meta-level compositions.
  • Expressive patterns: able to express generation of sorted sequences, Ackermann function, same-fringe, and other classic problems. Able to express POV-ray environments or music obeying constraints and adaptive fractal patterns. Certainly not context-free, but feasibly weaker than Turing-complete.

Some of these features feed one another. For example, if grammars denote sets of sentences, then supporting 'sets' within a sentence effectively means having 'grammars' within sentences. And supporting grammars within sentences, along with expressive patterns to adapt those grammars, might be sufficient to describe continuous fields.

Anyhow, I'm curious as to state-of-the-art and prior-art that I haven't discovered yet, and for any opinions/ideas.

A quick summary of what I have discovered: Attribute grammars and derivatives are simply too darn complex - they attempt to combine functional composition of attributes with grammatical productions, and the result is painful to write, difficult to read, and functions are generally irreversible (analytic rather than generative)... and they certainly weren't designed for reasoning across grammar compositions. Alessandro Warth's OMETA and Parsing Expression Grammars are designed for composition, but are also analytic grammars. The Language Machine seemed related, but really is all about stream-rewriting.

I'm still reading John Shutt's 93 thesis on RAGs, which seem related to what I'm seeking, but I've yet to fully grok them; I'll admit to being put-off by the emphasis on achieving "Turing-power" as though it were a virtue rather than an often unnecessary evil. I just now located an older LtU discussion referencing a paper on 2-level grammars and semantics which seems related. Matt Estes wrote Properties of Infinite Languages and Grammars, which I'll need to read.

I also picked up Grammar Systems: A Grammatical Approach to Distribution and Cooperation and Grammatical Models of Multi-Agent Systems, though I'm really hoping to find something to which I can apply a distributed security model (object capabilities, preferably) and these books describe systems that involve 'trustful' collaboration.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

About TokenTracers

I'm not totally sure what you are after and don't understand your selection of notation ( why are sums represented as tuples (A B C ...) instead of, well, as sums (A + B = C)? ) but when you are after expression generation using CFGs I might have a tip ( I'm not convinced in more powerful grammar formalisms but admit I'm ignorant about them. Maybe someone shows me convincing use cases later in this discussion, that can't be handled much better otherwise ).

You write "grammars are predicates over sets of sentences". The common procedure of evaluation of the predicate is the creation of a parse-tree. If the parser succeeds in parsing a sentence, the sentence can be considered as classified/accepted by the grammar.

I recently found a simpler method to achieve the same goal, which is also applicable for expression generation. I called the corresponding machine a TokenTracer. In essence a TokenTracer operates like a top-down-parser on first and follow sets generated by a parser generator but the TokenTracer ignores everything but the token.

Suppose you have defined a grammar 'Sum':

Sum: Symbol ('+' Symbol)* '=' Symbol
Symbol: INT | NAME

Here INT and NAME shall be terminals and Sum and Symbol are non-terminals.

We initialize the TokenTracer with the language generated from the grammar and the start symbol Sum:

tracer = TokenTracer(Language(Grammar), Sum)
tracer.selectable()  // selectable token [INT, NAME]  

Iterate a few steps  
tracer.selectable()  // ['+', '=']'+')  
tracer.selectable()  // [INT, NAME]  
tracer.selectable()  // ['+', '=']'=')  
tracer.selectable()  // [INT, NAME]  
tracer.selectable()  // []

The TokenTracer can validate a token stream by successively feeding the token-types of the token sequence into select(). If the complete sequence is passed through it is o.k. otherwise it contains an error. It is also a cheap method to liberate the parser from error reporting: if the parser fails to accept a token, so does the TokenTracer and vice versa - the TokenTracer can always detect a wrong token with ease.

Since the TokenTracer determines all possible token in each step, it is possible to randomly select an admissible token and fill in a token-string from whatever source ( user, random-generator, file, ... ). I recently used this method to "breed" grammars to test a parser generator using genetic programming. I could have used exhaustive generation as well, but where is the fun with that?

Re: Notation

why are sums represented as tuples (A B C ...) instead of, well, as sums (A + B = C)?

Sum is represented by a grammar named 'Sum'. The triples would be the sentence accepted by 'Sum'. I could have 'Sum' accept sentences of the form 'A + B = C', but if using Sum in the role of a predicate it would still need be passed to the Sum grammar to see whether the sentence is generated by the Sum grammar:

  • Sum('4 + 11 = 7') would be rejected. (That sentence will not be generated by the grammar Sum).
  • Sum('4 + 7 = 11') would be accepted. (That sentence will be generated by the grammar Sum).

You might be wondering: why don't "+" and "=" form some sort of implicit grammar in the environment? Well, I'm sure we could make that happen, but it wouldn't be effective for illustrating modularity, first-class grammars, or refinement. I.e. with the above example, it is clear that I could replace Sum with some other grammar.


when you are after expression generation using CFGs I might have a tip ( I'm not convinced in more powerful grammar formalisms but admit I'm ignorant about them. Maybe someone shows me convincing use cases later in this discussion, that can't be handled much better otherwise ).

If restricted to CFGs, you cannot express the Sum grammar, which accepts (generates) sentences such as (4 7 11) but rejects sentences such as (4 11 7). Is that convincing, or do I need more?

If we're going to use grammars as the basis for computation, we'll need grammars stronger than CFGs. But we can stop short of Turing-power.

Re: TokenTracer - I agree that one needn't always build a 'tree' in order to generate or classify a sentence.

I'm assuming a sort of scannerless parsing - i.e. no separate lexer; all 'tokens' are represented in the grammar directly (down to the character level, if sentences are represented in strings). How the traces are implemented is under-the-hood and might be selected for performance or predictability on a situational basis.

To what end?

If restricted to CFGs, you cannot express the Sum grammar, which accepts sentences such as (4 7 11) but rejects sentences such as (4 11 7).

Why are you trying to enforce a semantic property by means of syntax?

Semantics and Syntax

Grammars must serve as comprehensions for 'interesting' sets - i.e. sets that carry databases of useful information (constraints, patterns), and we must be able to produce progressively more interesting sets by composition and refinement. That's the basis of generative grammar-based computation (just as developing 'interesting' functions is the basis for functional programming).

The 'syntax' you're concerned with would be whatever syntax is used to describe the Grammars in the first place, or at least bootstrap said descriptions. In that particular case, the syntax would be mapped onto a semantics.

[Edit] Also, it isn't so bad to ask that question in reverse: why do we insist on separating syntax from semantics? What does that indirection buy us, precisely?

The language that can tell no lies

why do we insist on separating syntax from semantics? What does that indirection buy us, precisely?

I think their are two big things that come to mind immediately, one mainly practical and one possibly more technical.

The practical benefit is manageability. It is much easier to break the details of a language up into its syntactic and semantic components rather than having to deal with the whole ball of a wax at once. You stand a much better chance of cleanly describing each separately than hoping to find a single, uniform system that nicely handles all the properties you are trying to model.

The technical benefit is that you ensure that you don't inadvertently hobble yourself by preventing the expression of useful counterfactuals. To use your example, how would you express the set of numbers that are not the sum of 4 and 7? You can see that is as useful a definition relative to sums as the positive cases but very hard to express in a syntax with semantic restriction to actual sums.

Re: Language tells no lies

Are you assuming that composition of grammars would be much less modular than the alternatives?

Re: how would you express the set of numbers that are not the sum of 4 and 7? [...] hard to express in a syntax with semantic restriction to actual sums

You would describe a grammar that denotes that set - perhaps:

  exists C. Nat - C where Sum(4 7 C)

In this, C would be the grammar describing all clauses for which Sum(4 7 C) holds. In this particular case, there happens to be a unique answer. (Unrestricted use of negation might be troublesome if we wish to ensure the ability to decide whether the grammar is empty. I'd like to find something weaker.)

The restriction to expressing actual sums is only true for the language described by the grammar 'Sum'. The language for describing the grammar 'Sum' is not so restricted. For grammar-based computation, developers work primarily in the latter language: the language for describing and composing grammars.

If restricted to CFGs, you

If restricted to CFGs, you cannot express the Sum grammar, which accepts (generates) sentences such as (4 7 11) but rejects sentences such as (4 11 7). Is that convincing, or do I need more?

Oh. I didn't expect your grammars knowing arithmetic. Now I also do understand why you read Shutts master-thesis. He avoids ugly hybridizations with semantic actions but retains their computational power in the grammar formalism. I still don't know what can be better solved that way than using more conventional tool pipelines. It would be cool if you would come up with some positive results.

Why not Conventional Pipelines

As I mentioned at the top, my goal is effective, modular set processing and set comprehensions.

A grammar can be understood as describing a (potentially infinite) set of sentences. A set of sentences is a natural mechanism to carry information - i.e. in the same sense that a set of tuples is 'relation' in a relational model. Naturally, information is finite even if the language is not. Thus, one can understand the informational content of 'grammars' as carried by the constraints describing which sentences are included or excluded from the language: the information (in the form of constraints) is contained by the whole grammar, and the context in which the grammar appears, rather than by any individual sentences.

In this sense, we can understand grammars as related to both logic and constraint programming. Grammars describe modular sets of constraints, and can be composed to refine those constraints (e.g. via intersection) or weaken them (e.g. via union) or relate them (e.g. via joins or sequences). Similar to constraint-programming, with 'generative' grammars we can also generate a sentence as a solution to these constraints (if one exists). Logic programming can be expressed by grammars and vice-versa, but the bases for information and composition are different, and logic predicates are rarely first-class.

Anyhow, conventional tool pipelines would be ineffective and extremely awkward for first-class grammars and reasoning about properties of languages across grammar compositions.

Now since you have shown us

Now since you have shown us what you mean by the Sum grammar I would be curious how you intend to compose a Sum grammar with a Product grammar in a sensible way using set operations like intersection and union and how you "reason about properties" of Sums and Products across this composition.


I'm still studying that problem, which is why I asked in the OP for pointers to state-of-art and prior-art on the subject that my Google-fu was too weak to find. There are many possible mechanisms for describing composition of sums and products into a grammar. Among the more traditional is to use unification based approach. For example, one might express sentences where a^2 + b^2 = c^2 as {(A B C) | exists D E F : Prod(A A D), Prod(B B E), Prod(C C F), Sum(D E F)}.

But unification of this sort has its own costs; the existentials hide expensive searches. I'm interested in finding other designs.

For reasoning about properties, I'm imagining some sort of structural and sub-structural type-system for grammars might appropriate. I'm rather fond of TRS's ability to 'declare' properties such as commutativity, associativity, and identity. I'm very interested in approaches that would describe these structurally in sentences and enforced for grammar processing. Beyond the sentences produced, there are many other properties that are useful to know across grammar compositions - decidable generation and analysis, constraints on uniqueness (at least one sentence, at most one sentence), ambiguity (substructural: at most one way to form a given sentence), and so on.

I've seen this before!

What you are doing is using the trace to define what language is accepted by an automaton in state X. Bart Jacobs has most definitely written papers about this - viewing context-free grammars as coalgebraic structures.

Context Sensitive Grammars

As far as I know, there is only one route you can take, which is context sensitive parsing. I see that it is what you're trying to avoid, but when you've got a context sensitive grammar, you got a context sensitive grammar, you can't dumb it down any more.

You say 2-level grammars are too complex? There are a wide variety of 2-level formalisms used and developed in compiler building and natural language recognition projects. It just depends a lot on how you define the second level (fixed value over a lattice, string type, structural value, fixed unification order, there's a lot to play with).

You might want to look at Early's algorithm since that effectively calculates the intersection of a grammar and an r.e.

[What the *bleep* are coalgebraic structures doing here? Category theory is pseudo-science, best you can get out of it is a reformulation of what you already know? ok, a^2=b^2+c^2 has its uses too, but I don't see the relevance here.]

Re: Context Sensitive Grammars

I'm making no attempt to avoid 'context sensitive'. What gave you that impression? What I seek is a tractable, composable, modular formulation of grammars - i.e. expressive enough for most jobs (Ackermann, sorts, same-fringe, etc.), but supporting local reasoning and useful decisions. (For generative grammars, the most important decision is whether the grammar is empty. Other useful decisions are whether it contains exactly one sentence, whether it is finite, whether it is ambiguous.)

I said attribute grammars are too complex. I'm still learning 2-level grammars, reading some works by Barrett Bryant. Those I've read about rely heavily on existential unification; I suspect that would be remarkably expensive to process.

I'll check out Early's algorithm. Thanks for the pointer.

[To what do you refer wrgt. coalgebraic structures? And isn't the reformulation of what we already know the purpose of all in-the-small computations?]


Sometimes reformulations are good. Like a^2=b^2+c^2, that took a few millenia. Or deriving termination of Collatz from looking at the bit representation of numbers and observe that it's just all bit-cancellation, therefor there's a decreasing measure, the thing is Noetherian. But I don't see the relevance of coalgebras here.

Re: Hmpf (grumpy coalgebras?)

I also don't see the relevance. More precisely, I don't even see the referent. To what are you referring?

Post by Z-Bo

Some postings up.

Btw, Prolog

You forget that Prolog is, accept for its cut-rule, a 2-level formalism.

[hmm, i see you didn't.]


I agree that there is a close relationship between logic programming and grammar-based programming. A given logic predicate, or even a whole program, can be treated as representing a specific grammar. But what I'm seeking is one level higher than that: composition of grammars (or logic programs) and local reasoning about the properties of these compositions.

I.e. effectively, I could have agents sending logic programs to one another, generating new logic programs, combining logic programs provided by multiple agents. And I wish to reason about performance, termination, whether a composed grammar is empty, finite, or has a unique element, what information is hidden, etc.. Prolog is unlikely the best choice for this.

Something I'm not getting

If you want to do the following:

  1. Have values all be languages specified by composition of grammars;
  2. Have these compositional rules be "grammatical", rather than the "operational" rules of PEGs;
  3. Have values be expressive enough to, among other things, accept the class of basic true arithmetic expressions;
  4. Have composition rules that depend on determining that grammars are empty or specify just one string (i.e., your queries); and
  5. You want values to be "untyped", i.e., you want any value to be composable with any operation with any other value (so we are talking about just one class of grammars),

then it seems you're going to have to work to find a class of grammars that does the trick: nothing in the Chomsky hierarchy will work, for sure, nor will two-level grammars.

I'm guessing you're not really attached to the whole of that list: it'd make me get a better idea of where you wanted to go if I knew what trade-offs you were willing to make.

Try CDL3

Re: Tradeoffs

I do want #1,3,4. Though, regarding 3, I don't need all true arithmetic expressions, just a useful subset along the lines of total functional programming.

It is unclear to me what you mean by #2. But I would like the grammar descriptions and compositions to effectively support both generation and recognition of the same sentences, if that is what you mean by "grammatical".

I don't care about #5. As I noted to Kay earlier, I'm okay with giving types to the grammars, and I imagine that would help greatly with local reasoning about the properties of grammar composition. But I would strongly favor structural, implicit typing rather than nominative or manifest typing. When working with total functional programming, I utilized purely structural typing to good effect, complete with support existential typing and limited support for dependent types (via partial functions) and even first-class abstract data types (via sealer/unsealer pairs generated in the agent layer) and open recursive functions (via careful, explicit treatment of recursion). TFP was, unfortunately, too awkward for set processing.

I'll be happy also to reject 'sequences of atoms' as the basic underlying sentence. In doing so, I also obtain some rich alternatives to concatenation.

Sequences add far too much semantic noise. The intended semantics of a generated sentence don't always depend upon the ordering of the elements, but sequences enforce an ordering anyway. This can create extra work on output from a grammar (generating various permutations of sentences). It also can also increase complexity of composition (to explicitly remove ordering) - and one gains no help from the type-system to enforce independence from ordering.

Similarly, namespaces and labels (e.g. for vertices in a graph) are areas where one might pointlessly generate sentences in infinite variation.

Currently, I'm playing with the idea of sentences based on atoms, extended sets, spaces, and (recursively) more grammars. To keep it tractable, generation of grammars would be based only upon composition (as opposed to reflective representation of grammar descriptions). I could also use grammars as the only composition primitive, but I'm unsure whether that makes things too challenging for users.

A 'space' serves as the basis for namespaces and graphs. When I was working with TFP space S: [({S 1} {S 2}) ({S 1} {S 3}) ({S 2} {S 4}) ({S 3} {S 4})] might be understood as a simple digraph whose points are labeled 1,2,3,4 - but where these labels are strictly for representation, and thus is semantically identical to space S: [({S d} {S c}) ({S d} {S b}) ({S c} {S a}) ({S b} {S a})] (using atoms d,c,b,a). Spaces combine effectively with xsets to eliminate semantic noise wrgt. ordering. I'd like to further support associativity, in order to have at least the set supported by common term rewriting systems.

Anyhow, the basic tradeoffs I'm willing to make are:

  • Typing of grammars that will allow developers to control composition in order to ensure useful properties.
  • Structured sentences. No need to limit oneself to string literals (sequences of atoms from an alphabet). I'm not committed to the sentence=xsets+atoms+spaces+grammars quartet, but that should help exemplify what I'm looking to gain from structured sentences.
  • Limit expressiveness to a limited subset of 'true sentences; i.e. recognition and generation of sentences does not need to be Turing powerful by itself. However, expressiveness should be sufficient to express non-primitive recursion (as for Ackermann function), sorts, same-fringe, etc. - the sort of things one can express in a good total functional programming language. Potential for undecidability could also be part of a grammar's 'type', i.e. by requiring use of a particular composition technique to breech into the Turing complete.

And I'm willing to work to find a class of grammars that does the trick. But it seems wise to see if anyone else has already accomplished something near to what I seek.

[Marco, thanks for the ref to CDL3.]

Very promising

Sorry for the delay in replying. By #2, I was getting at the distinction between the fairly algebraic approach to grammar in the Chomsky hierarchy, which is friendly to different kinds of automata, and the very operational notion of state you have in PEGs, which is basically fixed to packrat parsers.

I don't know what you mean by "extended sets".

Spaces I like very much: the point about representing graphs alone is compelling enough. They are going to make the language design hard though, in the sense of mathematically hard, I think.

I think typing is the right path, but it's easy to pile on complexity this way: you offer a dozen different regular expression types, each having different complexity properties when forming, say, intersections with other grammars — in the end, the programmer will need to read all the formal languages papers you read in order to understand the type system.

Pessimism done: I think it sounds great.

RE: extended sets, spaces

I don't know what you mean by "extended sets".

Extended sets (xsets) are, in practice, sets of pairs - of ElementScope where 'Scope' describes the structural role in the set. Element and Scope may each be extended sets or some primitive value (such as an atom). It is the ElementScope pair - as a whole - that exists uniquely in an xset. So {1a, 1b, 2a} is a possible xset.

I require at least one structured composition primitive for sentences, and in the interest of language minimalism I would favor using only one primitive. A common option is sequences or records, which may be composed recursively to describe lists and trees and other 'data' structures. But these options force ordering in the composite 'data structure' that is unnecessary or undesriable to its intended interpretation, or structural ordering induced semantic noise. (Semantic noise is semantic content introduced by the host language that is unnecessary or undesirable for the problem domain. Its presence resists optimization, flexibility, and formalization.) xsets allow control regarding where structural order is introduced. Where ordering is necessary, one can use recursive xsets: {Hhead, Ttail}. Or one may use ordered scopes: {A1, B2, C3}.

As an added benefit, some xset operators would overlap grammar operators (seeing as grammars denote sets of sentences). So programmers would have fewer concepts to learn.

Extended sets were the brainchild of David Childs some decades ago, and are described here, though the focus on those pages is a particular application of extended sets. Unfortunately, the salient points on David Childs' page are buried among mounds of unjustified marketing manure written seemingly for pointy-haired bosses. Less biased descriptions of the subject are also available.

Spaces I like very much: the point about representing graphs alone is compelling enough. They are going to make the language design hard though, in the sense of mathematically hard, I think.

In general, whether two spaces are equivalent is indeed a computationally hard problem.

But I'm hoping(!) to avoid the 'general' hard problem. For generative grammars, it may be feasible to avoid generating two identical spaces from a single grammar, or to otherwise generate them in such a manner such that recognition of identical spaces is a relatively easy problem. Outside of avoiding replicated searches, most operations should consist of generating and recognizing spaces rather than comparing them for equivalence.

Spaces are about avoiding labeling-induced semantic noise, just as xsets avoid structural-ordering-induced semantic noise. In the cases where we really do need to compute whether one space is equal to another, as opposed to generating or recognizing or unifying a space, we should need to do the same regardless of whether spaces were first-class. The 'hard' complexity should(!) only be introduced where it is essential complexity.

Unstructured spaces combine with xsets to denote multi-sets. For example, if I want a multi-set, I could express it as: space S: {1S a, 2S b, 2S c, 3S d}. This says elements 1, 2, 2, and 3 are structured by distinct points (temporarily labeled a,b,c,d, for convenience) in an anonymous space (temporarily labeled S, for convenience).

A problem with spaces is finding means to effectively work with and compose them (after initial construction). My approach with functional programming was to introduce a keyword operator 'probe' that could pass a function into a space; a probe can return a value that contains no points from the space being probed, and may test equivalence between points within the space. Probe was expressive enough to do the job, but very verbose for composing two or more spaces. Without better alternatives to 'probe' that work for multi-space composition, I had decided to table 'spaces' from the functional language. The same might happen for grammar-based computations.

From what I've read, the

From what I've read, the point behind xsets is its ability to use a single structuring technique to represent indexed, associative, and nested data. When coupled with a suitable algebra, an optimizer has a lot to work with, as the entire state of computation from the initial read of data to an output format can be captured in xset notation.

Childs lists some sample operators in an algebra for xsets.

What is the equivalent of a lambda calculus for xsets? Something kanren-like that operates against the xset, instead of the cons cell.

Re: the 'point' behind xsets

the point behind xsets is its ability to use a single structuring technique to represent indexed, associative, and nested data

Unfortunately, that point fails to distinguish xsets from S-expressions, recursive structures, object graphs, untyped lambda calculus, or even regular ZF sets. The 'ability to represent' is not a difficult target. One should discuss instead the relative efficacy of the representation. One could discuss the 'precision' of a representation as being distance to the intended semantics of the data: semantic noise exists if there is too much constraint, and ambiguity exists if there is too little constraint. A precise representation allows more optimizations.

Similarly, 'the entire state of computation from input to output' is achieved in any declarative, pure computation language. If xsets and their algebras have an optimization advantage, it is due only to relative precision of the representation. (Since optimizers must not violate semantic constraints, any semantic noise becomes an unnecessary constraint against optimization. Since optimizers must not assume a particular interpretation, ambiguity can require extra information about non-local processing context in order to achieve local optimizations.)

Xsets are superior to many alternatives for these properties. But before deciding their utility, one should determine how precisely the xsets and algebra will represent graphs, numbers, matrices and multi-sets, fractals, scene-graphs, and other challenges.

What is the equivalent of a lambda calculus for xsets? Something kanren-like that operates against the xset, instead of the cons cell.

What do you mean by 'kanren-like'? And could you clarify the meaning of your question? (What does "lambda calculus for X" mean?)

Point-free Composition and Partial Grammars

After further work on this, it seems to me that favoring partial grammars, composed in a point-free style, offers a more promising foundation for computation. I'll explain.

A complete grammar describes the formal language (set of sentences) it generates. Because I'm unconcerned with 'parsing', I may always replace a grammar with that set of sentences without loss of semantics. This is problematic for several reasons. Among them, I lose the grammar semantics: grammars are not languages. Grammars are rich, condensed structures that describe languages. By working with 'partial' grammars, I can guarantee that much of this rich structure is maintained across composition, persistence, distribution. And partial grammars achieve this without limiting abstract interpretation, type-safety, or partial-evaluation.

Partial-grammars compose similarly to functions. For example, if P1 and P2 are partial grammars, and G is a 'complete' grammar, then P2<G> is a complete grammar produced by inputting G into P2, and (P1 . P2)<G> is the same as P1<P2<G>>. When I say I favor a "point-free style", I mean only to forbid the introduction of 'complete' grammars such as G, at least with regards to syntax and composition. We are free to introduce 'constant' partial grammars such as Pg, where forall X: Pg<X> = G. Thus (P1 . Pg . P2) generates the same language as P1<G> (and may be optimized), but we are allowed to compose to arbitrary depth. For convenience, we could utilize a simple substitution theory (such as lambda calculus) to support the more complex compositions. The common compositions for complete grammars, however, are readily adjusted for point-free partial grammars: if G1 | G2 is a grammar composition (representing union), then P1 | P2 is a point-free grammar composition with semantics (P1 | P2)<G> = (P1<G> | P2<G>).

These partial grammars are generative. However, they are partial, and thus generate incomplete languages - i.e. a subset of complete sentences. They may also generate incomplete sentences (sentences with 'holes' in them), but that is of less interest to me than is the generation of complete sentences. Many compositions of partial grammars improve opportunity to generate a complete sentence; effectively, if P1 is a partial grammar, then (P1 . P2) is a less-partial grammar; some of those 'sentences with holes in them' might have those holes filled to generate complete sentences.

For computation to be interesting, it must model predictions and decision-making. For functional programming today, this is usually via pattern-matching on inputs. For generative grammar based computation, however, an interesting question is: "does this grammar generate at least one complete sentence?". Context-sensitive grammars embody various constraints on the sentences generated, and so this question represents a constraint-satisfaction problem. A grammar can be expressed in such a manner that it makes represents an interesting conditional test.

Anyhow, that's for in-the-small programming. In-the-large, the question is how we compose separately developed programs. Partial grammars also benefit us here: a program is a partial grammar, and composition allows both input to programs and output from them (with both input and output also being partial grammars). This also scales to distributed operation: remote partial grammars, mobile partial grammars, 'agents' that represent active queries and time-varying partial grammars. Everything is a partial grammar, modulo effect typing.

My initial pursuit of partial grammars was due to this in-the-large aspect. I could not see how to effectively integrate IO while assuming complete grammars. But with partial grammars, interaction with remote agents (that behave as partial grammars) expresses interest in both satisfying a modular constraint set, and in determining whether the distributed constraint set is satisfiable. Computation in-the-large becomes a test of whether a big, distributed, partial-grammar can generate at least one complete sentence. Computation 'spreads' across the network of partial grammars until 'complete enough' to generate one such sentence or determine that no such sentence can be generated. When we need more complex behavior, we express a more constrained partial grammar.

Given some careful (effect-typing or security typing) constraints on the expression of unification in-the-large, this should integrate very effectively with reactive demand programming, and should integrate moderately well with variations on the traditional message passing or functional reactive programming designs. A great deal of laziness and parallelism are feasible. Only at the very edges of the system - at interaction with users, hardware, and third-party services - are we to concern ourselves with actually 'browsing' generated sentences.

It seems to me that a good

It seems to me that a good reformulation of all the "point free" stuff is to say that "partial grammars form a monoid." A bit further along, I suspect that given that you can view certain grammars as rings, the concept of a monoid ring may then make itself useful as well...

Re: Partial Grammars as a Monoid

The set of all partial grammars form monoids from more than one choice of operator and identity element - Compose and ID, Union and Empty, and so on. But I'm not seeing how this observation is a "good reformulation of all the 'point free' stuff." Would you mind explaining and clarifying your assertion?

I simply meant to say that I

I simply meant to say that I think one can summarize your description of "point free composition" by just saying that partial grammars form a monoid with compose and id. And from this, there arises the question of how much additional algebraic structure you can endow partial grammars with.

(I should have said seminearring rather than ring above, by the way, I think...)

Algebraic properties of partial grammars

I agree that partial grammars form a near-semiring with, as one example, 'compose' as multiplication and 'union' as addition. (Union lacks the inverse element needed for a near-ring. And compose does not annihilate with respect to Empty on the right, as required for a semiring.) Beyond the properties of 'near-semiring', we can note also that compose is monotonic: P1 ⊆ (P1 . P2) with regards to generation of complete sentences. Further, union is commutative, monotonic, and idempotent - nice properties for incremental and parallel computation.

I am interested in algebraic properties of partial grammars and the various operators with which one might compose them. A proof of associativity and commutativity will support deterministic aggregations over sets. Add identity, and you can parallelize and merge those aggregations. Monotonicity can allow incremental computation and shortcut constraint resolutions. Idempotence allows redundancy (which is important for large-scale parallelism) and reduces concerns regarding ambiguity (allowing a space/time performance tradeoff between remembering information processed vs. processing information more than once). I understand these individual properties well enough.

But I'm not comfortable enough with abstract algebras that recognizing a 'monoid' or a 'near-semiring' allows me to extrapolate anything. That is, I can look at the definitions and say, "yes, this qualifies", but I am unable to extrapolate from "X is a monoid" to conclude "X is a good summary of point-free composition". There are many options other than compose and union to form monoids or near-semirings, such as concat and union or concat and compose. And I understand that commutativity and associativity can simplify syntax. But, in my earlier request for clarification, I was hoping for some explanation as to why you assert that "partial grammars form a monoid with compose and id" is a good summary or reformulation of point-free composition. By which steps do you extrapolate this conclusion?

I think I may have promised

I think I may have promised too much with my comments, although they prompted some very nice thoughts on your part. Of course the judgement that some structure obeys some algebraic laws comes after you have defined the structure, not before. (Although, one may of course aim to design structures which have as many nice algebraic properties as possible.) My point was simply that, given what you described, it could be summarized, to someone familiar with the terminology, as a monoid over compose and id. This is not the same as saying that it is "better" at being that monoid than it is at being other monoids.

In other words, if you tell me that "partial grammars form a monoid with compose and id" then I know that partial grammars can compose with at most one other partial grammar; i.e. that compose :: PG -> PG -> PG. I know that there is a partial grammar that does nothing. I know that there is no way to compose any two partial grammars to get something which *cannot* be further composed. Thus the algebraic structure summarizes a number of the properties of partial grammars given above into a simple and well understood structure.

The one side point is that of course nice algebraic structures lend themselves to taking advantage of nice algebraic laws (and specifying which laws do and do not hold is a way to further understand your structure and the operations on it). And if one uses very general structures, then one can plug in different concrete types, to obtain different effects.

The "Play on Regular Expressions" Functional Pearl accepted to ICFP 2010 shows this quite nicely, I think.

But then, I suspect you know this all better than me already.

Thank you for the

Thank you for the explanation, and for the reference.

Temporal Generative Grammars

For a while I had abandoned Generative Grammars for my work because I had many problems fitting them into the RDP communications framework. But some recent thoughts breathe new life into this idea. I'll just note them here, as I believe they're interesting enough to ensure are documented under this header and worthy of further discussion.

First is the notion of "temporal" generative grammars, which generate sentences that are finite in space and logically infinite (and ideally continuous) in time. This is in the same vein as temporal logics, temporal constraint programming, UTCC and Dedalus and Functional Reactive Programming (of the Yampa or Reactive brand).

A sentence might describe a point event happening at a specific time, or a periodic event, or a continuous signal. Infinite sentences could normally be hugely troublesome from a compute perspective since you cannot generate one in finite space. But we can leverage temporal logic to alleviate these issues: sentences may be infinite through time, but at any given moment in time the spatial property of the generated sentence should be finite - i.e. there is a finite (but not necessarily bounded) number of elements in the sentence. (A 'sentence' might be the size of a PhD thesis in English, of course.) By correlation of the grammar's logical time to 'real' time, we can view generation of a sentence as it progresses through time - and since time serves as our source of logical monotonicity, the spatial properties of that sentence may be non-monotonic in time (shrinking and growing over time).

Being grammars, Temporal Generative Grammars don't (usually) describe only one possible sentence, but rather a finite or infinite number of potential sentences. They describe 'patterns' in space-time, of which any particular sentence is a particular instance. A pattern in space-time corresponds (roughly) to a transitive verb in English - something that can be applied to many different 'instance' situations, like "running" or "bicycling". (In this sense, the generation of any particular sentence may be non-deterministic within the rules of the grammar.) Rather than a particular event happening at a specific time, a simple temporal grammar might assert that a generic sort of event (described by a spatial grammar) happens within a temporal window.

Now, a single temporal grammar isn't anything special by itself... just as one wouldn't take a single function of time (t→d) and call it FRP, one can't take a single grammar describing behavior in time and call it TGG.

What matters is composition. When all your functions are temporal, you get to compose them in interesting ways. Signal transformations such as (t→d)→(t→r), describe one temporal function as reacting to another - the basis of FRP. You can describe switching behaviors, waiting behaviors, delays, numeric integration. With fixpoint and some care to avoid divergence, you can describe mutually interactive behaviors. Additionally, you can compose behaviors that coincide at a given point in time in the normal functional way... e.g. taking (t→a) and (t→b) and producing (t→(a+b)). Further, there are many nice implementation characteristics... if implemented right, the CPUs will be performing advance computation for the next significant moment, allowing you to mask real-time latencies by computing the next observable event before time catches up to it. User input can be integrated as a 'function of real-time' so long as you don't allow expressions to peek into the future.

When generative partial-grammars are temporal, you can describe whole patterns of reaction, interaction, cause-and-effect. And you may still compose grammars via the normal constraint mechanisms - joins, et al. One may specialize the implementation, and compute a future to mask real-time latencies.

Now, the possibility of generating temporal grammars does raise at least one issue: we don't want to start computing an infinite sentence, then discover at some unbounded point in the future that our sentence is invalid and we need to try another sentence. Thus, we are under restriction to only generate valid sentences at least in the temporal dimension. It would be nice, certainly, to also generate valid sentences in the spatial dimension - but we do have a little more flexibility for backtracking there. It is trivial to make grammars that will generate only valid sentences (context-free grammars do exactly that!). The trick is to be expressive enough to describe interesting constraints - a grammar that speaks only 'true' sentences - without needing so much expressiveness that we can't determine whether a sentence is valid before computing it.

How do we ensure an upper-bound on the amount of computation necessary to compute whether a sentence will be valid before generating it? Do seemingly impossible functional programs hold a potential answer?

Or maybe we could use a cost-analysis basis... e.g. associate 'costs' with different temporal behaviors, and guarantee that the cost of a given behavior has a fixed bound in time.

Well, I'll probably be banging my head on the 'mechanism' for a while yet.


It is trivial to make grammars that will generate only valid sentences (context-free grammars do exactly that!). The trick is to be expressive enough to describe interesting constraints - a grammar that speaks only 'true' sentences - without needing so much expressiveness that we can't determine whether a sentence is valid before computing it.

How do we ensure an upper-bound on the amount of computation necessary to compute whether a sentence will be valid before generating it?

As I found your ideas interesting, I refrained from commenting on this too prematurely, that is, before I've been banging my head enough on this as well. So, now, FWIW:

Do seemingly impossible functional programs hold a potential answer?

Yes, I think it's a good intuition that I'd follow if I had the same interests as yours and I had come to the same rationale and choice of path of investigation.

Note I leave alone/aside the rest of your thinking about the nice algebraic properties you're (still?) figuring important to have. So I'm actually trying to share here only about this:

the trick is to be expressive enough to describe interesting* constraints

(* emphasis mine and by "interesting" I take it you're before anything else interested in having the checking of your grammars against them, the described constraints, whatever they are, feasible in finite time and before any attempt to generate anything out of those grammars?)

that I found the most interesting sub-problem where my reflections can (hopefully) be helpful — as a matter of a possible high level strategy to tackle with this specific aspect (so, not at all an actual solution yet, even on paper, of course) :

The seemingly impossible functional programs paper gives a very nice realm of computation where computational decidability over "largely-infinite" sets such as the Cantor space is nevertheless something you can hope to achieve in finite time.

I believe it's easy enough to mentally represent oneself the Cantor space w.r.t its compactness property (well, my own mental view, anyway) : take an infinite sheet of paper divided in x and y in little squares all the same size, number them starting with 0, by following the "escargot"/spiral pattern:

[12][11][10][ 9]
[13][ 2][ 1][ 8]
[14][ 3][ 0][ 7]_____ X
[15][ 4][ 5][ 6]etc

then see the space as a whole as the (infinite) number of combinations where the grid's squares are either filled or empty (0/1)

"Et voila".

Ok, now what?

Well, the very fundamental bottom line of the aforementioned paper is if you're able to devise a scheme where your "things" representations are reductible to projections over this compact space then you can actually rule out (resp. find) in finite time, in that space, functions belonging to the type Cantor -> y, depending on some criteria (resp. "exists for some" or "not exists forall") where the type y itself has decidable equality (like e.g., booleans).

Now, let's say your sub-problem S consists in determining the equality of two functions F : Cantor -> y and G : Cantor -> y.

Hence my idea of a "strategy"(maybe, no promise!) : you could decide to try reduce it to two other sub-problems S1 and S2 (one is about F, the other about G) of verifying N-1 points (in each sub problem) of a N-point shared secret — let's say N=3, for which you have the (arbitrary) point zero, and a pivot-point, the latter distinct between F and G — via Shamir's Secret Sharing algorithm. The points being in the Cantor space, mapped from whatever representation you have for your PG algebra's and/or constraint mechanism's constructs...

No? (or I'm just rather tired and totally missing something either totally impractical or theoretically impossible/irrelevant)

Well, again FWIW (as it's mostly intuition again) & HTH.

(Hmm... after putting some more thinking into this)

Actually, according to this idea/scheme, you'd rather pick N=4 with a choice of two not-so-random constant points, used to determine the fourth via SSS, in the Cantor space:

1. "z" aka "point zero" or "origin" — i.e., this one would be the mapped representation, by design, of the (single) empty set of constraints over the grammars considered, or the analogous "peer" of your wildcard grammar "_", mentioned at the end of your other post.

2. "e" aka "the point of empty" — i.e., the mapped representation, by design, of the infinite set of all ever imaginable constraints (expressed in your algebra) over the grammars considered (which, by imposing "so many" restrictions, end up allowing only the empty language to be generated), or the analogous "peer" of the (single) complete grammar S ::= (empty) (S being its axiom, and which thus generates the empty language).

Now let "x" be the variable ranging in the (infinite) set of mapped representations of all (finite) sets of constraints over the grammars considered (but different from both z and e).

Then, you'd let something like:

F = x -> Checked(x)

G = x -> SSS(z, SSS(z, ToCheck(x), x), x)

(Note when z appears above, you might be interested in putting e, instead, depending on the context.)

Where the 4-point SSS algorithm guarantees us:
given a, b, c: if SSS(a, b, c) == d, then SSS(a, d, c) == b, hence SSS(a, SSS(a, b, c), c) == b)

The "trick" (read: difficulty) is to introduce those two intermediary functions ToCheck, Checked : Cantor -> Cantor in the above, as practically and relevant as possible w.r.t your algebra, and the intersection of the domains of which conceptually represent the one "relevant" set for the initial problem:

* on one side, from ToCheck's domain: i.e., specifically the set of "still to be checked, and maybe interesting enough-constraints"
* and on the other side, Checked's domain subset where ToCheck(x) == Checked(x): i.e., specifically the set of "now checked and chosen as being interesting enough-constraints".

So that you reuse the ideas of the paper to enumerate thru the Cantor space looking for some x where the following does not hold:

F = G => Checked(x) == SSS(z, SSS(z, ToCheck(x), x), x)

(where "=>" denotes the logical implication)


[Edit bis]
Oh yes, finally:

I reckon, it may seem strange to introduce the use of SSS and those two functions ToCheck and Checked for the purpose, but the core idea is to find a scheme (I tried to devise here) to take this wish there, into account:

For the purposes I pursue generative grammar programming, the generated sentence is mostly irrelevant. What matters is the proof and process of meeting constraints.

where, as much as ToCheck can probably be implemented once for all and in a declarative/purely functional fashion with a, say, "static" semantic, over your PG algebra, the other function Checked is still I think useful to introduce as being actually a (I, Cantor) -> Cantor where I is the domain of input you have in mind there, as well:

The answer to that question would be 'yes', 'no', or 'needs input'. One might 'need input' for a particular position, so there are infinite variations on 'needs input' such as 'need input 1' and 'need input 2' and 'need input 3'. [...] PGs provided as input are recursively asked the same question: can you generate a sentence within contextual constraints. This can lead to 'interactive' recursive partial grammars.

(so that while ToCheck is pure, Checked, OTOH, can be dependent on the state of your constraints checking/filtering)

And as far as the use of SSS is concerned, it's just basically (as you may have guessed) just a "cheap" way to provide some kind of inverse function of ToCheck/Checked — more accurately, the inverse of the restriction of ToCheck to the subdomain where constraints will happen to be filtered as "interesting" by its Checked peer afterwards (but is known cannot be computed by the only knowledge/algorithm of ToCheck a priori) — "almost for free" — well, modulo the use of SSS, precisely.

(the values of x where ToCheck(x) == Checked(<state>, x) are these "interesting enough" constraints you are only interested in at any given <state> at the end of the day)

HTH (but again, maybe I totally missed something in your actual problem space/what you're trying to have possible to implement later on w.r.t PG's)

[Edit ter]
(Corrected the defs of F, G, and fixed the discriminant equation in the implication)

But anyway: this being said,

But anyway: this being said, and although that's a pretty challenging problem space you've got yourself here, it's pretty interesting too; and btw, I'd love to read more about some application use cases you have in mind for PGs that you consider to be likely practically impossible to do using other, "more traditional" computation schemes(?)


Most 'traditional' computation schemes fail 'in-the-large' scale. In-the-large, it is necessary to compose mutually distrustful components, integrate with a market and society of services and code, degrade gracefully under partial-failure and recover resiliently, tolerate bugs and disruption and power cycling, support continuous upgrade and maintenance, deal with a changing environment of resources. Further, it remains important to have good performance - and control of performance (efficiency, utilization, latency) - at scale, which means utilizing multiple cores, distributing code, incremental computation and using partial results, etc.

Most 'traditional' computation schemes also fail to effectively and efficiently propagate concerns between domain models. For example, given a simple robot, it is difficult to coordinate: the motion of its wheels, the motion of its arm and camera, the obstacle recognition and avoidance concerns, the balance concerns. Simply moving around an object and taking pictures of it from different angles becomes a huge, painful deal. Anything more complex than that, such as coordinating two robots at once, is practically impossible. Constraint programming and concurrent constraint programming are a decent model for this sort of cross-domain integration.

Generative grammars are promising as a base for fitting into the intersection of these concerns - support for effective integration and collaboration across mutually distrustful, independently developed components and their domain models. My work with partial grammars and temporal grammars are attempts to support aspects of system integration.

Constraint programming

Constraint programming and concurrent constraint programming are a decent model for this sort of cross-domain integration.
Generative grammars are promising as a base for fitting into the intersection of these concerns.

Interesting. I'm not sure I understood everything of your rationale re: "temporal grammars"; while the "partial grammars" part along with the design rationale surrounding the nice algebraic properties for filtering out "uninteresting" constraints over PGs (or, conversely, the positive selection of "interesting" ones) did make more sense (to me). My guess is I still have to re-read you and put some more thought into it given your last reply here. Thanks.

Re: temporal grammars

Pervasive temporal semantics allow many rich forms of system integration to be expressed efficiently and without explicit state. For example: streaming audio and video, animation, UI, robotic motion, real-time synchronization and coordination of streams and behaviors, etc.. Avoiding explicit state is, itself, a very useful feature because explicit state introduces problems for replication and code-distribution (and, thus, for performance).

Pervasive temporal semantics can reduce need for small, periodic updates to keep a system up-to-date. "Small" updates tend to cascade through a system, burning bandwidth and CPU. With temporal semantics, however, one pushes a whole 'model' of future behavior, then only updates that model when it later proves invalid. There is a cascading update of these 'large models', but they occur orders of magnitude less often. For example, one might predict movement of a vehicle to be a function of the lane it is following, in which case we only need to send an update if the vehicle significantly changes speed or starts changing lanes.

Additionally, a window for peeking into the anticipated future is excellent for developing 'planners' that can coordinate and collaborate effectively even in the face of temporary communications disruption and mutual distrust.

With temporal grammars, these qualities are magnified.

The incremental and choiceful nature of grammars allows more intelligent decisions on how far updates should be propagated - a sort of 'stubbornness' whereby one minimizes changes in choice or propagated constraints when accommodating new observations and incoming constraints. By minimizing changes, one gains 'stability' in the system and also improves efficiency even further, surpassing the benefits achieved with temporal semantics alone. Basically, temporal semantics can save us an order of magnitude or two for rate updates cascade through the system, and these incremental stubbornness properties can save us an order of magnitude for the distance that updates cascade through the system.

And the 'planning' mentioned earlier actually occurs implicitly with temporal grammars: one constrains a sentence not only for present behavior, but also for anticipated future behavior. There is no need to explicitly 'peek' into the anticipated future, instead the different constraints come together implicitly to choose a future amenable to all parties. The resulting plans are very simplistic - having no support for contingency - but that's okay, since contingency can be handled by other means (such as reactive dataflow) and the lack of contingency can simplify the planning process itself. A small bit of intelligence can go a very long way.

Speaking of small bits of intelligence, reactive generative grammars and other reactive constraint systems are very promising: given non-deterministic choice, they can 'learn' which choices are most likely to lead to success. This is a small bit of intelligence, but when replicated and scaled up to millions of agents (each with its own concerns and agendas) we end up with a worldwide neural network that 'learns' how to effectively everyone's specified needs and preferences within the limits of priority and authority. Stable constraint semantics provide stubbornness, and temporal semantics provide the rich planning.

Anyhow, I'm still putting the carriage way ahead of its horse with this long term 'vision' of mine. I feel with temporal RDP I've made a major step forward on the scalability side, though, so I've spent some time pursuing ways to combine RDP-like semantics with a model for effective domain integration, such as constraint programming. There are many practical issues still in need of resolution: I need to reconcile security properties for the incremental computation of grammars, and I'm not yet satisfied regarding integration of grammars and other constraint models with FFI and sensors/effectors.

I'd like to be clear: I don't consider temporal grammars to be the only promising possibility. I'm also exploring possibilities based upon stable fixpoint functions, true continuous functions, and bi-temporal integrals (generating a continuous integral of one's anticipated futures as they change over time). I prefer to keep a lot of possibilities open, until I find good reason to close them. To contradict your later post: I've not made any 'choice' as of yet. I figure I'll be implementing a few models as a PL atop RDP before I'm anywhere near satisfied.

Thank you for the explanation

Thank you for the explanation and the related link hints. I'll certainly catch- and follow-up on this later.

I can understand this

I can understand this easily:

Most 'traditional' computation schemes fail 'in-the-large' scale. In-the-large, it is necessary to compose mutually distrustful components, integrate with a market and society of services and code, degrade gracefully under partial-failure and recover resiliently, tolerate bugs [...] Further, [...] at scale, [it] means utilizing multiple cores, distributing code, incremental computation and using partial results, etc.

I believe this is certainly meaningful to anyone having gone thru just a couple of years of intensive experience in software composition in-the-large, and as they've been exposed on a regular basis to the tensions between the various languages, tools, and products they had to try "marry" hard — or just have interoperate "nicely enough", which, granted, is way easier said than done! — (and for any given business purpose or whatever). But I have another question, though:

I'm now curious about which most determining, specific, factor(s), or event(s)/experience(s) (or project(s), etc) did re-orient your interest by a sort of "180 degrees turn" (just so to speak) into this direction of Generative Grammar-Based computation?

(As this has a very much paradigmatic taste of a choice to me, unlikely to be anodyne, no?)

Neural network

Generative grammars are promising as a base for fitting into the intersection of these concerns - support for effective integration and collaboration across mutually distrustful, independently developed components and their domain models. My work with partial grammars and temporal grammars are attempts to support aspects of system integration.

Are you looking at generative grammars because you see a kind of "language" to parse there?

Wouldn't that be more in the domain of neural networks/AI?

Not for Parsing

Generative grammars basis for computation isn't used for parsing. The 'generative' aspect is purely creative (albeit, guided by need for partial intersection).

Perhaps think of it more like one of those games where ten or twenty authors are mad-libbing a story together, except in this case the 'story' involves OpenGL output, music, car designs, dancing robots, etc. The difficulty isn't telling them to write the story, but rather in keeping it relatively sane. For generative grammars, context freedom is insanity.

For example, I'd perhaps like for you to give me a story about display layout, but there are rules: the buttons cannot overlap, they should line up horizontally if feasible, the text shouldn't run beyond the width of the button... and you need (some set of) buttons.

But, unlike constraint programming, say, these 'rules' get expressed almost uniformly as grammars. There might be a few specializations for generating real numbers and such, but mostly we use choice, various forms of sequencing, etc. The 'sentences' generated probably shouldn't be linear, because we don't want any more constraints than absolutely necessary. One could generate sets or record structures instead.

The flexibility here lies somewhere between concurrent constraint programming and logic programming. There are many of the same issues with performance and divergence concerns.

So it's all sort of a pipe dream at the moment. I've yet to find a satisfactory way to constrain the generative grammars for termination and controllable performance, though a simple cost-benefits system seems promising, offering a way to limit the size and complexity of sentences. More importantly, I've yet to find an implementation technique that doesn't violate object capability model, which I consider important for code distribution and (therefore) scalability. I plan to get back to the problem in a few years.

'AI' isn't a computation model, but a generative grammar based computation model could be used for AI. It could even be a learning AI, similar to a neural network, if every agent memoizes just a little bit about which 'sentences' work the most often (they can do this whenever non-deterministic choice exists in the grammars).


Somehow this morning, it gotta hit me: genetic programming.

Of course you don't grow your sentences ( 'chromosomes' ) in this setting using grammars but rather constrain them with those. Change happens using sets or operators including edit-operations like crossovers. What becomes crucial then is to lower admissibility thresholds. A sentence is not just evaluated to true/false but to a real value which might be [0..1] normalized which is important for progressive improvement.

Sentences as chromosomes?

On a (broadly) related note, I was aware a while back of some work in which the rules of an adaptive grammar were the genes — here.


I wasn't even aware that there is research activity, called GE, which widens the GP approach. I did GE recently for evolving test grammars with special properties for testing a parser generator. There are some particular constraints which are not encoded grammatically, foremost the one that an NT which appears on the RHS must have been introduced on the LHS.

A long and cold winter is predicted. So I'll perhaps find some time to look at non-standard grammar formalisms in more depth. Thanks to your master thesis I'll even have some overview over adaptive grammars which were introduced to me to your thesis.

If that helps, too

Ah yes: not a long while ago (last year, I think) I've tinkered my own example of use of a 4-point SSS algorithm JavaScript implementation here btw (with a couple other tweaks for the example's purpose).

Basically just a simple port from David Madore's C implementation (in public domain).

[Edit] Correction made: not a 3-point version of the SSS algo; a 4-point one, indeed, just as in "our" use case here :)

Infinite Arity Partial Grammars

Earlier I described use of partial grammars.

They were unary in nature: type PG = G → G. My assumption was that one didn't actually have syntactic access to a complete grammar G, leading to point-free composition (P1 . P2).

Unfortunately, that is quite inflexible, inexpressive.

I was, perhaps, imagining that partial-grammars would curry effectively - e.g. I can generate tuples from a grammar, so is that not similar to a tuple of grammars? It is not! A grammar that generates tuples imposes constraint relationships that must be preserved, and so one cannot generally 'extract' a grammar without carrying along the other elements in that tuple. (I.e. one can perform an intersection or a join, but not an extraction.)

Fortunately, generative partial-grammars have an interesting property: they can generate output without input. As noted above, composition is monotonic in the number of complete sentences that can be generated (P1 ⊆ P1 . P2). So is application: (P1 ⊆ P1(G)). Having the input only increases the number of potential sentences a partial grammar can generate.

So allowing multiple inputs should increase this further.

What I suggest here is to abandon the point-free style and allow partial grammars to be points: type PG = PG → PG. This is similar to the untyped λ-calculus, in that every operation between partial-grammars will generate a partial-grammar.

However, applicative substitution is only one means for composition and computation for partial grammars. One may compose partial-grammars with the grammatical forms: unordered choice (A | B), ordered choice (A / B), and certain constraint forms such as intersection (∩) or difference (-) or relational join - though the actual set of primitives needs to be restricted if we're going to answer important questions like "does this partial grammar generate a sentence?"

The answer to that question would be 'yes', 'no', or 'needs input'. One might 'need input' for a particular position, so there are infinite variations on 'needs input' such as 'need input 1' and 'need input 2' and 'need input 3'. Providing an input will add to the number of complete sentences that can be generated, but also constrains and specializes the partial grammar, so providing extra input might result in a 'needs input' becoming a yes or no.

PGs provided as input are recursively asked the same question: can you generate a sentence within contextual constraints. This can lead to 'interactive' recursive partial grammars.

For the purposes I pursue generative grammar programming, the generated sentence is mostly irrelevant. What matters is the proof and process of meeting constraints. To that end, it is also useful to introduce a wildcard grammar - a sort of boolean true - which I'm notating as (_). The wildcard grammar can generate whatever you want, which wouldn't be useful if the sentence actually matters, but does allow (A ∩ (_) = A) and (A ∪ (_) = (_)). (Its opposite end is empty choice, false, or bottom.) The wildcard isn't free license to do anything... you still need to meet any existing constraints, but the wildcard itself won't impose any new constraints.


Whether integrated as dmbarbour suggested or not, the process of scanning characters to make lexemes is necessary, and the process of analyzing syntax is necessary. On the other hand, making a module for each process is a design decision, and no matter how good it is, it may not always be the best.

IMO integrating the two processes would not be a disadvantage assuming another set of modules are used to improve manageability.