Lambda the Ultimate

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.

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?

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?

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.

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 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.

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 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.

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.

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.

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

Some postings up.

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.

http://www.cs.ru.nl/~kees/cdl3/cdl3.pdf

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.]

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.

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

Extended sets (xsets) are, in practice, sets of pairs - of Element^Scope 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 Element^Scope pair - as a whole - that exists uniquely in an xset. So {1^a, 1^b, 2^a} 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: {H^head, T^tail}. Or one may use ordered scopes: {A¹, B², C³}.

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 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.

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?)

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...

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 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...)

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 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 explanation, and for the reference.

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:

        Y
        |
        |
[12][11][10][ 9]
[13][ 2][ 1][ 8]
[14][ 3][ 0][ 7]_____ X
[15][ 4][ 5][ 6]etc
[16][17][18][19]...

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.

[Edit]
(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, 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 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.

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 and the related link hints. I'll certainly catch- and follow-up on this later.

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?)

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?

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.

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.

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).

[Credits]
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 :)