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