Exploiting parser ambiguity

First I'll state my (admittedly fledgling) understanding of avoiding parser ambiguity in normal languages and then I'll ask my question about how it might be exploited instead of avoided in some "abnormal" languages.

My understanding is that normally it is imporant for the concrete syntax of a language to parse unambiguously, e.g. it is important that precedence be specified so that an expression like

a + b * c

will be parsed to give the same parse tree as either

a + (b * c)

or

(a + b) * c

(For this example, probably the former, but that is beside the point.)

In giving an abstract syntax, it seems that you can usually assume the concrete syntax is designed to parse unambiguously, i.e. the abstract syntax defines the syntax of parse trees rather than the syntax of the lexeme sequences that are parsed into those trees.

So, my question is, what if you want to design a language in which

a op1 b op2 c

means

(a op1 b) op3 (b op2 c)

i.e. the ambiguity is resolved by inserting an implicit operator (op3) and repeating the symbol in common between both sub-expressions (b). E.g. the expression

a < b < c

might (as it normally does in math) mean

a < b && b < c

So my question is, how does one present syntaxes (concrete and abstract) and semantics for such a language? It seems like traditional methods can't accomodate this way of resolving parsing ambiguity. Or maybe they can and I'm missing something; that would be great.

I hope this post's topic is appropriate to this site. I also hope my question isn't too vague or malformed: I admit I haven't thought about it a lot yet but thought some responses might be useful to point me in the right direction earlier rather than later so I don't go reinventing the wheel.

Comment viewing options

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

Not really a parser problem

I don't think this a parser problem, but rather a specification problem.

You can easily define a language where a < b < c is syntactic sugar for a < b && b < c. (This may be a pain to generalize to an arbitrary number of comparisons, though)

If you just want to define < and let the general case fall out, you have to think about what you want.

If a < b returns a boolean, then you have a type mismatch error, since

a < b < c

will evaluate in left to right order as, e.g.

true < c

which probably doesn't make sense. (Though you could specify it to make sense.)

I'm not sure that the convenience of this syntactic form justifies the problems with it, which probably explains why it is not that common in PLs.

Implementing "overlapping reference" as sugar

Yeah, I'm beginning to think I'm making this too complicated and should just define this as sugar.

If I were actually doing this in a textual language, though, I think this still leaves open the parsing question. Because I would like the de-sugaring stage to operate on the parse graph, not the lexeme sequence. So there is still the question of how (if there is a way) to get normal parsers to parse to non-tree graphs.

Then this desugaring could be viewed as the way of "tree-ifying" the graph.

But as I mentioned in another reply, in my actually application I already have the parse graph.

Back to basics

Because I would like the de-sugaring stage to operate on the parse graph, not the lexeme sequence.

To help clarify, let's define what we mean by "parsing", "parse graph" (I assume you mean something like abstract syntax tree) and "sugaring".

Normally when we say parse, we mean reading text and converting it into an abstract syntax tree. Once that is done, there is no more "parsing" to be done; the syntactic structure is laid bare.

By "syntactic sugar", we usually mean two syntactic forms whose semantics are identical. You may or may not want to give them the same abstract syntax representation, probably depending on how different the forms are.

If none of this makes sense, or we are not on the same page with the terminology, I would recommend a good compiler book, such as Appel's Tiger Book.

So there is still the question of how (if there is a way) to get normal parsers to parse to non-tree graphs.

This isn't that different from the normal situation. Even though called trees, and represented as trees, semantically ASTs are really arbitrary graphs by virtue of reference. By this I mean, use of identifiers that are defined elsewhere in the tree or that identify an ancestor node (recursion).

Terminology clarification

  • Sorry, indeed I should have used "AST" instead of "parse graph."
  • I agree that the sugared and de-sugared form of an expression are semantically identical, but I don't think that is enough to define "sugar." Perhaps you were not aiming for an all-inclusive definition but rather just highlighting this one aspect of sugar. I would attempt to define sugar as syntax
    • that is part of the language but not part of some smaller subset of the language identified as its "kernel"
    • that is transformable ("de-sugarable") to the kernel
    • whose semantics are defined indirectly, via this transformation, rather than directly, as the semantics for the syntax of the kernel are.
  • The de-sugaring transformation could operate on the program text, but my preference would be for it to operate on the AST, in which case the sugared and de-sugared form of an expression would not have the same AST, but I admit that this is just based on my preference.
  • I see what you mean about ASTs for normal languages implicitly having multiple edges go to the same identifier vertex by virtue of reference. But my ASTs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can handle that. Maybe that difference between explicit and implicit edges is really not so significant.
  • Clearly I need to educate myself on this stuff some more, so I've ordered the "Tiger Book" on your recommendation. Couldn't decide between the C, Java, and ML versions, but, although I find functional languages more interesting, I eventually chose the Java version since it was a lot cheaper ($5 used!) :-).

Syntax graphs

my preference would be for it to operate on the AST, in which case the sugared and de-sugared form of an expression would not have the same AST

As I said previously, I don't think this is a problem; you just add another case that has to be processed further down the compiler chain.

But my ASTs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can handle that.

I'm a bit confused by your use of parser again here. As I mentioned before, once you get to AST, the parsing is done. If you mean just processing the AST to the next step of the compilation, then the normal technique of traversing the AST to transform it still works.

You probably have to do a little more work to make the traversal work correctly, since you have an explicit unrestricted graph, instead of a proper tree.

If you step back for a moment and rethink your AST representation a bit, you might be able to get the best of both worlds, by using symbolic references rather than "pointers" for identifiers.

The Tiger Book will probably do the trick for you in this regard.

Can parser produce ASG?

This may clarify why it seemed I was referring to parsing once parsing was done:

Instead of

But my ASTs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can handle that.
I should have said "But my ASGs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can generate that.

In other words I was imagining the data flow as

  • program text
  • -- lexer -->
  • lexeme sequence
  • -- parser -->
  • ASG
  • -- de-sugarer -->
  • AST
where data types are unadorned (e.g. "program text") and processes are adorned by being inside arrows (e.g. "-- parser -->").

Example made plain

But my ASGs have multiple explicit edges to the same identifier vertex, and I wonder whether a parser designed for normal languages can generate that.

Think about a simpler case. Take

a < b && b < c

Let's say that becomes an AST representation like:

(logical-and 
  (exp-list 
    [(comparison "<" 
      (id "a")
      (id "b"))
     (comparison "<" 
      (id "b")
      (id "c"))]))

I now have two references to (id "b"). This is normally done with a symbol table at this point.

But let's say instead I decide to convert my (id "b") reference to a pointer to the value of "b". I now have the very situation you refer to: multiple explicit references to the same node.

All of this falls just fine into the normal techniques for parsing and compilation.

If you tilt your head, it's still a tree.

bdenckla:
So there is still the question of how (if there is a way) to get normal parsers to parse to non-tree graphs.

At the syntactic level, "a < b < c" can still be represented as a tree.

class CompExpr extends Expr {
   Expr first;
   List<(CompOp, Expr)> rest;
}

term: a < b <= c > d

structure:
  CompExpr {
     first = "a"
     list = [
        (LT, "b"),
        (LE, "c"),
        (GT, "d")
     ]
  }

This structure is amenable to folding. To construct it, all you have to do is parse it like a list operator.

Expr -> ... | CompExpr | ...
CompOp -> "<" | ">" | "<=" | ...

CompExpr -> Expr CompOp Expr
   {
     $$ = new CompExpr();
     $$.first = $1;
     $$.rest = new List();
     $$.rest.add(($2, $3));
   }
CompExpr -> CompExpr CompOp Expr
   {
     $1.rest.add(($2, $3));
     $$ = $1;
   }

This is different from a binary operator in that you're explicitly handling contiguous operators. The semantics of your operator require this. For example, addition could be defined as a list operator. It doesn't need to be because "a+b+c" isn't different from "(a+b)+c" or "a+(b+c)", and so it is more elegantly dealt with as a binary operator. However, your operator doesn't have those properties and so you've got to parse multiple entries all in a row.

Converting the form after the parse (i.e. in AST form) could be problematic because you lose a little information when you go to AST form. If your initial parse simply treats "<" like a regular binary operator:

term 1: a < b < c
term 2: (a < b) < c

Both terms translate to the same AST (if "<" is a left-associative binary operator). However, I'd think that term 2 should be disallowed. You would be able to distinguish between the two terms if your AST contains information about parens, but I think this is more complicated than getting the parse right in the first place.

An idea to consider

A common assumption that is frequently made about programming languages is that they (FTMP) should be context-free grammars (and restricted forms of CFGs, such as LALR(1) or LL(1) grammars). Of course, no language is purely such (a CFG cannot, for example, enforce the constraint that a variable be defined before it is used), but virtually all programming languages have a CFG skeleton.

Why? For several reasons: 1) CFGs are well-understood; 2) there exist numerous tools to generate such parsers from a high-level spec (especially important for LALR(1) grammars), and 3) they can be parsed efficiently--the time required for a LALR(1) parser is linear with the input size (which is asymptopically as good as you can do).

However, in many cases (especially for small strings of tokens) it might be useful to bring more powerful computational models to bear. Even if they require exponentially greater time/space to analyze; for a small number of tokens that probably doesn't matter. To do that, simply move the rules in question out of the parser definition, and make them part of the semantic actions; you now have full Turing-machine power. This is how variable names, etc. are currently handled.

In this particular case, you might want to move the operator-handling code out of the parser, and deal with the operators using a standalone function of some sort. i.e.


expression := empty
expression := terms /* This rule provides a hook for
* the semantic analyzer to
* process a sequence of terms
*/

terms := term
terms := terms term
term := literal /* numeric, string, atom, whatever */
term := operator /* +, *, -, :=, etc. as necessary */
term := open expression close /* anything in braces */
open := ( | [ | { /* etc */
close := ) | ] | } /* and so on */

The CFG gets used to handle braces and the like; and strings of terms are handled using external logic, which could certainly do what you suggest. (I should note that what you want isn't ambiguity--never a good thing in a formal language--but ways to be more flexible than Yacc and such would make easy).

One might note that if you make no syntactic distinction between "literals" and "operators" (which may or may not be necessary; I just did it to make a point), then the above is essentially a grammar for parsing S-expressions.

The difference between this an S-expression in Lisp or Scheme is that it isn't necessarily assumed that the first term in a sequence of terms is the name of a function/macro/special form, and the remainder its arguments. In the case of an expression like (4 + 7), one could view "+" as the function, and 4 and 7 as the arguments. (Or, one could take the Smalltalk point of view and view 4 as the receiver of the "+ 7" message).

I'm using the above technique on a project I've been working on in my copious spare time (snicker), and it looks like a promising way of doing things.

You might also check out the language Rebol as an interesting example of parsers being pushed to the extreme...

Reframing the problem in terms of classes of grammars

Thanks for your reply, Scott, this helps me reframe my problem in terms of "what class of grammars does my language belong to" and the answer looks like "not CFGs."

Without knowing it, I think I was already moving in this direction when, right after making my original post, I drew a parse "tree" for my a < b < c example and found that it was not a tree (b has two parents (both <'s)!). Are sentences in CFGs always representable as trees? I should review CFGs and hopefully find the answer in the process.

Also your reply helps me reframe my problem not just in terms of diverging from CFGs (which, as you point out, is common), but in terms of diverging from CFGs in a way other languages normally don't, and therefore having to push some functionality that is normally handling by parsing into external logic.

I should mention, in case it is relevant, that the context for this question, i.e. my application, is not implementing a language that allows a < b < c. Rather I just thought that was a good, simple example.

In fact my application is a graphical language. This has the advantage of "already being parsed," i.e. it is graphical in the sense of already being a graph.

I am trying to make a denotational semantics for this language and am a little stuck on not knowing how to proceed with this relativel novel (i.e. non-tree) grammar.

Side note: one interesting feature of this language is, not only can you use the same identifier in two different expressions, in fact you *must* do so if it appears in two different expressions, i.e. identifiers can only appear once. I think this is interesting from the perspective of eliminating a class of errors in traditional languages where the user intends to refer to the same identifier but chooses another. Usually the other identifier is undefined, or of the wrong type, so this will be caught (assuming a language that requires definition before use and is statically typed!) but sometimes the user is not so lucky and chooses a valid, but incorrect identifier.

Stop in the name of the Chomsky Hierarchy!

this helps me reframe my problem in terms of "what class of grammars does my language belong to" and the answer looks like "not CFGs."

Unfortunately, unless I have horribly misunderstood your problem, Scott is way off base, and you don't need a more powerful grammar than CFG.

In fact, I can't think of a grammar that isn't LINEAR (i.e. recognizable with regular expressions) for the form a op b op c, whether it is fixed ternary or extensible to the right. (Unless you have REALLY weird rules for contants and identifiers)

To make this clear: let ID be the regular expression for identifiers/constants, then the grammar:

S -> ID A
A -> op ID A?

will do the trick. (Hopefully, this is obviously linear, if a bit of an abuse of grammar notation.)

If you give us a more concrete example of your actual problem, perhaps we can offer better advice.

[fixed small error]

CFGs and such

way off base....

Perhaps; a clarification is in order.

You are probably correct in that what the original poster wanted to do could be done in a CFG. I won't attempt to prove or disprove that.

My essential point is that what he wants to do might be more easily implemented as a standalone function, rather than as rules given to YACC or some other similar tool. If what the original poster wants is one simple case for one simple operator, than explicit rules in the grammar is the best way to go--if for no other reason than the fact that such tools will tell you if you introduce any ambiguities.

However, I got the impression that the original poster wants to be able to parse sequences of terms/operators in some arbitrary ways (perhaps even dynamically!). In which case, use of external (to the parser generator) logic is probably a better way to go. Doing so, of course, does allow you to escape the bounds of a linear grammar; whether or not you choose to take advantage is up to you.

At any rate, sorry for any confusion.

Regexps enough?

I agree that the grammar is can be described via regexp, e.g. what you gave, or

ID (op ID)*

but then what would the AST look like? My concern is that "parsing via regexp" (if that is a meaningful concept) would parse
a + b * c
as
a (+ b) (* c)
which still has tree structure, and in particular a single reference to b. Although, admittedly, it has a kind of interesting tree structure, reminiscent of the SmallTalk "send the message (+ b) to a" spirit mentioned elsewhere in this thread.

Multiple Layers

My concern is that "parsing via regexp" (if that is a meaningful concept) would parse
a + b * c
as
a (+ b) (* c)

My example assumed a single operator, so this is a different case.

I think once you work through the first few chapters of the Tiger Book, you will probably have enough food for thought to rethink and reformulate your language so that existing compiler technologies will do the trick.

In particular, Appel does a good job of showing how to break down the language features into the different steps of the compilation process. I think that will help here.

List associativity

This might be a case of what some people call a list associative operator. For example:

                   term: a + b + c
 left-associative parse: (+ (+ a b) c)
right-associative parse: (+ a (+ a b))
 list-associative parse: (+ [a b c])

I think you would want the "<" operator to be a list operator and not a binary operator. I believe that this is roughly equivalent to the way commas are handled in most languages.

You might also want to make the other comparisons list associative as well (to allow "a < b <= c"). You might want to watch out for "==" and "!=", though; they work with booleans and therefore could cause some confusion:

            term: a < b == c
interpretation 1: (a < b) == c
interpretation 2: (a < b) && (b == c)

Notational abuse

E.g. the expression a < b < c might (as it normally does in math) mean a < b && b < c

This is an abuse of notation, and not a good one.

Say a, b, c are of type Bool and Bool is ordered (supports the <= operator). Then it is perfectly reasonable to write (a <= b) <= c or a <= (b <= c), and having the compiler interpret this in an idiosyncratic fashion would be annoying and probably confusing.

Furthermore, as has been pointed out by some researchers (though I cannot recall a reference offhand, it is probably one of the Squiggolists), this abuse obscures certain useful and important facts like the fact that = defined on Bool is associative: (a = b) = c = a = (b = c).

Please do not try to institutionalize notational abuse.

In fact, you are better off forgetting about syntax and notation altogether, adopting the current conventions, and dedicating yourself to understanding semantic issues, where the return on investment is orders of magnitude greater.

Update: I forgot to mention the obvious fact that a mechanism like the one you suggests disallows writing things like a * b * c. Making the conditional dependent on the operators involved will work very badly in a higher-order language, since it implies deciding functional equality. Making the mechanism conditional on typing then makes the parsing depend on typing. And if you think that's a good idea, then we have no common ground at all, so feel free to do what you like.

Surprisingly judgemental response

I will give you the benefit of the doubt and assume you meant your use of the word "abuse" to be more playful in tone than your text communicated.

I've found other responders to my post to be wonderfully more open minded about my question.

I admit that I have revealed hardly any of the details of the context of my question, i.e. my application. As such, others have witheld judgement on whether it is a "good idea" and instead answered my question with the implicit caveat, "Assuming this is really what you want to do, ..." Others have actually asked for more details of my application (which I admit I have yet to provide, partially because I fear they will be a distraction.)

But instead of witholding judgement and addressing the issues narrowly, or asking for more information, you launch into a discussion of the advisability of what I want to do, assuming, it seems, I am designing a general-purpose programming language, e.g. with Bool data types, ordered comparisons on those Bool data types, and a '*' operator with standard meaning.

Probably my examples like a < b < c and a + b * c misled you into this assumption, but I would have thought that with the frequent use of 'op' instead of <, +, and *, and the general abstract tone of the discussion, you might have assumed less about my application.

Now, moving away from meta-discussion...

Consider that within the mathematical domain, I believe the a < b < c is standard, not viewed as an abuse at all. How do you know I'm not writing a language designed to reflect the conventions of that particular user community? (I'm not, but that is beside the point.)

I agree that people get far too caught up with syntax, and I should try not to fail into that trap. CS education, with its emphasis on parsing in compiler design classes, reinforces this, which is why the only language-relevant class I ever took was just on semantics, not compiler design, although as you can see from my ignorance on certain issues, that decision was not without its impact! Probably I would have forgotten a lot of it even had I taken the class, though :-).

One of the questions I am trying to answer, though, is how do I present a denotational semantics in a language that does not have normal syntax. In other words I got involved in syntax because it was frustrating my attempt to make a semantics.

I'm beginning to think that traditionally, semantics are presented (albeit implicitly) as operating on trees, which represents an implicit assumption about the abstract syntax of the language.

Also, and not surprisingly, traditional parsers assume the abstract syntax is a tree, but although that topic is interesting (and that's mainly what we've been talking about so far on this thread), as I've mentioned it is not really "my problem" because in my application I do not need to parse, i.e. what the user gives me is already a graph.

So back to semantics, I need the "meaning functions" of my semantics to operate on non-tree types, and I'm not sure (a) how to do that (b) once I do that will it be a denotational semantics, i.e. have the well-established well-definedness that den. sem. on trees have and (c) even if it is still well-defined, will, people accept it as such, i.e. how do I convince them it is a "real" den. sem. not something like a den. sem. that I cooked up ad hoc.

The abuse

The abuse arises because formally a < b < c has to be considered as a separate relation, where _<_<_ = {(a,b,c) | a < b and b < c}. A generalization can be defined inductively by <n = {(a1,..,an) | <n-1(a1,..,an-1) and an-1 < an} for integer n > 2 and <2 = <. That _<_<_ and _<_ share '<' is the abuse.

foo

I will give you the benefit of the doubt and assume you meant your use of the word "abuse" to be more playful in tone than your text communicated.

"Abuse of notation" is mathematical jargon. It means a notation whose semantics is understood by the reader yet is formally undefined or ambiguous.

But instead of witholding judgement and addressing the issues narrowly, or asking for more information, you launch into a discussion of the advisability of what I want to do

Yeah, so? I have strong opinions. Don't be so thin-skinned.

I believe the a < b < c is standard, not viewed as an abuse at all.

It is absolutely viewed as an abuse. It is a standard abuse.

I'm beginning to think that traditionally, semantics are presented (albeit implicitly) as operating on trees

Yes.

So back to semantics, I need the "meaning functions" of my semantics to operate on non-tree types

You need to assign semantics to graphs, then? The standard way is to a define it as a graph morphism.

A more general way is to generate the category of paths from the graph, and define the semantics as a functor to some other category. So you interpret a node as an object and a path as a morphism.

I need the "meaning functions" of my semantics to operate on non-tree types, and I'm not sure (a) how to do that (b) once I do that will it be a denotational semantics, i.e. have the well-established well-definedness that den. sem. on trees have and (c) even if it is still well-defined, will, people accept it as such, i.e. how do I convince them it is a "real" den. sem. not something like a den. sem. that I cooked up ad hoc.

I don't really understand what you are saying, but inasmuch as denotational semantics is compositional, if you are dealing with non-tree structures, a categorical semantics will give you the same advantages.

BTW, many denotational semantics in PLT are not based on trees (algebraic). For example, a lambda-term is not a tree, but a kind of graph, and that's why a denotational semantics has to thread an environment through.

First stab at a (more) formal semantics

S(B,C) = (f, I, O) where The meaning S of a diagram (a diagram is a
set of blocks B and connections C) is itself a block (a block is
a function f, a set of inports I, and a set of outports O) where that block's components are defined as follows:

I = UI(B,C)

I is the set of all unbound inports (UI) of the diagram

O = UO(B,C)

O is the set of all unbound outports (UO) of the diagram

f = \T(O).T(I) [where] A where

f is a function taking T(O), which is the set of all unbound outports (O) converted to a tuple, and returning
T(I), which is the set of all unbound inports (I) converted to a tuple, where a set of assignments (constraints)
A apply, where A is defined as follows:

A = Sb(B) union Sc(C)

A is the meaning of the blocks, Sb(B), and the meaning of the connections, Sc(C).

UI(B,C) = CI(C) - BI(B) The set of all unbound inports of a diagram, UI(B,C), is the set of all inports of a diagram, CI(C), minus the set of all bound
inports of a diagram, BI(B). A bound inport is one that is inside, i.e. "belongs to" a block.
UO(B,C) = CO(C) - BO(B) The set of all unbound outports of a diagram, UO(B,C), is defined analogously to UI(B,C).
CI(C) = {i | (i,o) in C} The set of all inports of a diagram, CI(C), is the set of all inports that are part of a connection since unconnected
inports are not allowed.
CO(C) = {o | (i,o) in C} The set of all outports of a diagram, CO(C), is defined analogously to CI(C).
BI(B) = union {I | (f, I, O) in B} The set of all bound inports of a diagram, BI(B,C), is the union of the sets of inports of all blocks.
BO(B) = union {O | (f, I, O) in B} The set of all bound inports of a diagram, BO(B,C), is defined analogously to BI(B,C).
Sb(B) = {T(O) [assign] f [apply] T(I) | (f,I,O) in B} The meaning of a set of blocks is a set of assignments of each blocks's function, applied to a tuple
of its inports, to a tuple of its outports.
Sc(C) = {i [assign] o | (i,o) in C} The meaning of a set of connections is a set of assignments of each connection's outport to its inport.
T(I) = ? Not sure how to define this; there is a degree of arbitrariness here since to turn a set into a tuple
we need to impose an (arbitrary) ordering on the set's elements.
T(O) = ? T(O) is (un)defined analogously to T(i).

Some questions

  • You have defined all of your entities extensionally (i.e. you assume a set and extract members from it). How do you build these sets?
  • Your definition for f makes it sound like every f maps all unbound inputs to all unbound outputs. If this is not so, how do you select a relavent subset of inputs and outputs for a given f? How does f know its arity (the size of the tuples it consumes and returns)?
  • I'm not clear how the assignments in C are different from the f-mappings in B
  • If all that is going on here is that you start with a set of inputs and a set of outputs, and you end up with a set of correspondences between inputs and outputs, why not build a simpler system that does just that?

Some answers

  • These sets are built from the ASG; not sure how to indicate that.
  • The f for a given block only maps that block's inports to that block's outports. The top-level f that is the meaning of the diagram maps the diagram's unbound outports to its unbound inports. Note the somewhat counterintuitive switch at this top level: inputs are outports and outputs are inports.
  • The assignments that C gives rise to via the semantic (sub)function Sc are of the simple form identifier1 = identifier2. The assignments that B gives rise to via the semantic (sub)function Sb are of the form tuple1 = function tuple2. Does that help clarify?
  • Not sure how to address your last question; hopefully the answers to the above 3 questions will help.

A more complicated example sometimes helps


Here's a more complicated example diagram
, which may help illustrate the "real" use of this language, which is to do a generalized form of function composition (i.e. hooking up blocks/functions f and g in arbitrary ways).

Oh, yeah, the meaning of this new example

I don't have access to my code generator at the moment, but I'm pretty confident that the code it would generate for the new example would be something like

diagram (u1,u2) = (y1,y2,y3) where
(b1, b2) = f (a1, a2)
d = g c
a1 = u1
a2 = u2
y1 = b1
y2 = b2
y3 = d
c = b1

Block interpretation

I think I begin to see the problem: the meaning of a block is either underspecified or overspecified.

If all that matters for the meaning of the graph is the path-terminating nodes, then you don't need any information about the blocks, just treat them as opaque nodes.

If you do care about the internals of the blocks, you need to add some information to them to make it possible to evaluate them consistently. For example, in one case the block sequence b1 b2 a1 a2 f evaluates to (b1, b2) = f (a1, a2), but in another the sequence d g c evaluates to d = g c.

There simply isn't enough info in your definition or the diagrams to predict this, so you would have to add some knowledge of block evaluation rules to your system, for example as valency info in the functions, or by some explicit block building grammar.

Block evaluation

Perhaps a source of this confusion is the idea that the user can just plop nodes into a block. They can't. They use blocks whole. Is this the notion of opacity you were referring to?

Spatial order (e.g. left-to-right or up-to-down) is irrelevant in this language. So there is no notion of a "block sequence" like "b1 b2 a1 a2 f" in which order matters. There is just a block tuple of (f, {a1, a2}, {b1, b2}).

In the diagrams and the semantics, I claim that there is enough info to know how to evaluate a block, except for the problem of establishing an order in the set-to-tuple conversion (I mention this problem in the semantics with respect to leaving the T functions undefined).

But leaving that problem aside, in the diagram,

  • any node with an incoming arrow is known to be an inport
  • any node with an outgoing arrow is known to be an outport
  • and any node with neither is known to be a function.
  • a node with both is disallowed by the grammar (which I admit I have not really specified). In the semantics this could be disallowed by saying that a diagram's connections, C, (its set of inport/outport pairs) are over disjoint sets, i.e. an inport is never an outport and vice versa.

Vroom, vroom

I claim that there is enough info to know how to evaluate a block, except for the problem of establishing an order in the set-to-tuple conversion

That's kind of like claiming you have car that runs well, except it has no engine. ;-)

You NEED to provide some structure to block to be able to evaluate them, whether by function valencies, ordering or labelling of elements, or some other mechanism.

Once you solve this problem, there is nothing here that looks unusual compared to any compostional language.

ordering (set-to-tuple conversion)

You NEED to provide some structure to block to be able to evaluate them, whether by function valencies, ordering or labelling of elements, or some other mechanism.

The elements of the inport and outport sets are already labelled, e.g. "a1", "a2", "b1", "b2".

So perhaps this is too important to leave implicit, but let's assume that each block has info about how, based on these symbols, it should order its inports and outports into tuples.

Or instead of thinking of blocks as containing functions, can we just say that they contain expressions with free symbols corresponding to their inport symbols and assignments to symbols corresponding to their outport symbols? That way we get away from the whole ordering thing. Then, in the end if the users wants to turn the diagram into a function, the user must supply the ordering.

compositional languages

Where can I find out more about the compositional languages to which you refer?

Compositional

Where can I find out more about the compositional languages

I'm using compostional as a plain adjective here; I'm not referring to some exotic class of languages.

I just mean "languages where larger units are understood in terms of smaller units that make them up".

This covers most interesting languages and grammars.

Sheafification...

A more general way is to generate the category of paths from the graph, and define the semantics as a functor to some other category. So you interpret a node as an object and a path as a morphism.
I tried a couple of times to explore the paper-space of denotational semantics as a functor from path category, and both times was repelled by quite steep cost of entry - things like presheaves almost killed me.

There seems to be a vacuum between multiple introductions to category theory and the papers that really use it. Any suggestions on teaching myself advanced category theory in 12 easy steps? :-)

CT for Dummies ;-)

There seems to be a vacuum between multiple introductions to category theory and the papers that really use it.

I've been studying CT (in my spare time, on and off) for the better part of a decade, and I still those moments of frustration when I get flummoxed by a particular application I see in a paper.

So I know exactly what you mean. ;-)

One observation that I have is that one of the great powers of CT is that it makes it easy to express very general, multi-level mathematical relationships. The catch is that it can be very difficult to understand how this general relationship applies in a particular case.

Generally, to really get these particular cases, you need a fair background in some other, more specific algebraic field. (e.g. group theory, algebraic topology, set theory). One part of my strategy to understand CT has involved learning about these various fields and then coming back to papers and books to see what more I understand.

(Most of the fields are interesting in their own right, too)

The advice I would give someone who had limited time for mathematical exploration would be to choose some field that they know a lot about (or want to) and learn how to represent it thoroughly in CT terms.

This helps to give intuitions about the meaning and utility of various CT constructs "under fire".

An obvious candidate for most people with some mathematical background (and a pretty good start for CS apps) is set theory.

Lawvere and Rosebrugh gives a fairly thorough account of set theory in CT. Its probably a good start for someone with a set theory background.

Lawvere and Schanuel is similar but for people with more modest mathematical backgrounds. (Still good if you want a more basic level of intuition.)

Another strategy I employ is to collect CT textbooks. ;-) Reading different accounts and presentations of the same material is useful both as review and as fresh perspectives on the ideas. You never know what simple distinction is going to "flip the light switch" for you.

Actually, this advice holds for PLT or any other mathematical field as well.

If you want a text that is intro but will take you up into some pretty hairy CS-related areas, I would recommend Barr and Wells (special order only)

Thanks

I will consider one of the former books. I am currently entangled in Chapter 1 of Presheaf Models for Concurrency (sorry about OT).

It's not abuse because it's unambiguous

Who said that a<b<c must be equivalent to either (a<b)<c or a<(b<c)? In Python it's neither, it's 'a<b and b<c', and it works fine. It doesn't depend on types, it's just a parsing issue. What is the problem?

Someone forgot to use &amp;lt; ;-)

Can someone (maybe Qrczak?) fixed the previous post?

Needs to have < changed to &lt;.

Fixed, thanks.

Fixed, thanks.

Gibblets

Who said that a<b<c must be equivalent to either (a<b)<c or a<(b<c)?

The standard rules for infix operator symbols.

In Python it's neither, it's 'a<b and b<c', and it works fine.

I presume they special-cased <. You're right that a particular case like this can be made unambiguous in a particular language. I was thinking about mathematics, where the standard rules are assumed to hold without exception. (Knowing you, Marcin, you will quibble that a < b < c is clearly an exception, so the standard rules are not assumed to hold without exception, but I assert that both hold simultaneously, thus there is a contradiction, and hence ambiguity.)

Anyway, the poster was asking about a general mechanism for doing this for infix operators, presumably only relational (and similar) ones, since otherwise you don't want to eliminate the ability to parenthesize subterms. And to identify a relational operator you need to look at the type.

P.S. If you don't think special cases are confusing, please explain to us all why you tripped over the special-casing of < in HTML.

Whose standard rules?

The standard, unspoken rule in mathematics is that a<b<c ≡ a<b and b<c. It's not ambiguous. Both do not hold simultaneously--a<b<c does not mean (a<b)<c. You seem to be insisting a<b<c must be equivalent to either (a<b)<c or a<(b<c) in PLs because of "standard rules" even though the supposed standard obviously doesn't hold in mathematics. I don't see why you insist on calling it "abuse of notation" when all high-school educated people understand the notation and so do a few PLs. IMO, more PLs should accept it.

Denotational semantics for a block diagram language

Okay I'll start over by actually presenting the context for my question, i.e. my application. My application is to give a denotational semantics for a block diagram language. The block diagram language is used to describe causal, discrete-time, unirate systems, if that matters and/or you're curious.

Actually it is not so much my language as my attempt to formalize various informal languages of this type that are in common use.

Currently I think about the language as having only two operators: "FA" (apply function to variables and assign result to variable) and "A" (assign variable).

Programs in this language are not easy to represent in text (that's a good sign of it "needing" to be a graphical language, after all!), but here's a simple one:

y A b = f a A u
where I've notated the ternary operator
AF b f a
as
b = f a
(apply function f to a and assign result to b) and I've notated the binary operator
A y b
as
y A b
(assign b to y).

Now, you might ask, what is the point of the program

y A b = f a A u
in particular, isn't it equivalent to
y = f u
and the answer is yes, but in this language you can't choose which I/O variables the AF operator applies to, i.e. you have to use
b = f a
as a block, which, graphically, is in fact what it is. If you want to use the same function f elsewhere, you can ask for a new block containing "f", and you will get a block which will have auto-generated unique I/O variables, e.g.
b2 = f a2.

The abnormal/neat thing about this language is, as I've conceived it, variables only appear once in the abstract syntax graph, so a single vertex must be able to be the argument to more than one operator (have multiple incoming edges).

Now, maybe these multiple edges are coming from another abnormal/neat thing about this language as I've conceived it, which is that the abstract and concrete syntaxes are the same thing, or, depending on how you want to look at it, there is no concrete syntax, or there is no abstract syntax (probably the latter is a better way of thinking about it than the former.)

I already have a "compiler" for this language in the form of a C++ program that generates Haskell code. So in some sense what I'm trying to do is trying to formalize what I'm doing in the C++ code. I.e., the C++ code is transforming the syntax graph of the program into Haskell, and a semantic function transforms the syntax graph of a program into lambda calculus, and Haskell (or at least the tiny subset of it I'm using) can be considered a sugared lambda calculus, so if I can express what I'm doing in C++ as a semantic function, I have a denotational semantics, right?

Ouch, that hurt ;-)

Sorry, but it took me a really long to time to think that I understood that. ;-)

I'm not sure that there isn't a simpler language in there trying to get out, but here are some thoughts:

you have to use b = f a as a block
So why not bracket that expression or give "=" a higher operator precedence.

the abstract and concrete syntaxes are the same thing

You want Lisp or Scheme then. ;-)

variables only appear once in the abstract syntax graph, so a single vertex must be able to be the argument to more than one operator (have multiple incoming edges).

I'm starting to wonder if what you really want is unification.

CTM has a good explanation of this feature.

Why I can't bracket "b = f a"

Sorry, I accidentally posted my reply as a fresh thread, so see above.

Why I can't bracket "b = f a"

Sorry this should have been a response to the 'ouch' post.

I can't bracket "b = f a" or accomplish grouping by giving the 'FA' operator higher precedence because, for example, I need to be able to apply the 'A' (assign variable) operator to b, not the whole expression.

The distinction between operating on the expression as a whole and operating on a specific I/O variable within it is really only needed if f's input and/or output is tuples, i.e.

(b1, b2) = f (a1, a2)
But unfortunately this is where it gets a little hard to represent textually. But, for example, I need to be able to apply the 'A' operator to b2 specifically, not the whole output of the block, which is (b1, b2).

First sim antics, then sin tax

I need to be able to apply the 'A' operator to b2 specifically, not the whole output of the block, which is (b1, b2).

Now I know I'm confused. ;-)

You may have found Frank, well, frank, but his advice is good. Drop all thought of this as a syntax problem, and work out exactly what your semantics are.

Find a semantic description for one of the class of languages you are working on, if you need help getting started.

I think that hoping to find out what the semantics is by working through the syntax is not going to work. You'd be better to define the semantics and then figure out a good syntax (or graph representation, if you prefer) after the fact.

I already know the semantics of my language

I claim I already know what the semantics of my language are. I just need to put them into as-standard-as-possible form. I think the denotational semantics would be most appropriate, since I already know the language has a fairly natural mapping to Haskell, i.e. my "compiler" (Haskell generator) really doesn't have to do much.

But I am having some difficulty figuring out what the "meaning functions" would look like, because (at least this is my claim) the standard form in which semantics are presented makes some assumptions about the syntax being defined. In particular, it assumes single reference to identifiers/a tree-shaped syntax graph.

I guess I'm repeating myself. Hopefully the links I posted to the diagrams will help me express myself.

And the semantics goes to...

I claim I already know what the semantics of my language are.

Well, do share. ;-) I wasn't able to say for sure what the semantics were based on the diagrams.

The semantics

Using Haskell as my language to define meaning, the meaning of such a diagram is a function

diagram [tuple of unbound outports] = [tuple of unbound inports] where
[dump all assignments in the ASG here]
where unbound ports are identifiers outside blocks, outports are identifiers that are arrow sources, and inports are identifiers that are arrow destinations.

For example, the meaning of this diagram (which has this ASG) is

diagram (u1,u2) = (y1,y2) where
(b1, b2) = f (a1, a2)
a1 = u1
a2 = u2
y1 = b1
y2 = b2

Interpretation

the meaning of such a diagram

OK. Let's see if I get this.

You have a block of registers (we'll call them) that evaluate from right to left.

The program has three steps:
1) load values from external references into the input registers
2) evaluate the block with those values. The result ends up in the output registers of the block
3) store the results to external references.

That sounds likes assembly language. ;-)

I don't really see a problem for normal methods here. If your block of registers is fixed, then your "f" procedure simply needs to know which registers to get its parameters from, and which to store its result in.

If the problem is that you don't know when your values will be bound, you need something like dataflow variables with unification. See CTM mentioned earlier.

The language needs laziness

If the problem is that you don't know when your values will be bound, you need something like dataflow variables with unification. See CTM mentioned earlier.

Is not knowing when your values will be bound the same as needing laziness?

If so, that is the case in my language, since blocks can be hooked up with feedback.

I have duly ordered a copy of CTM, although the price was nothing near the $5 bargain price I found for the "Tiger" book.

BTW, I think I put too much semantics into my ASG, here's a new version of the ASG for my standard diagram with this concrete syntax (I guess I do have a somewhat separate concrete and abstract syntax after all).

Boundness

Is not knowing when your values will be bound the same as needing laziness?

For what I mean, no. To given an example: an uninitialized pointer is unbound. An initialized pointer is bound. To dereference an initialized pointer is to evaluate it. (More or less.)

With laziness, typically your variable is bound (it refers to a valid expression), but you don't know when or if it will be evaluated.

If you won't know until later what expression a variable will be bound to, you probably want dataflow variables.

I have duly ordered a copy of CTM, although the price was nothing near the $5 bargain price I found for the "Tiger" book.

A worthwhile addition to any PL enthusiast's library. I was a skeptic about the whole multiparadigm thing way back when, but this book is so well done it changed my mind.

Though there were relatively few brand new things I learned from reading it, those few things were of high value, and the presentation of material I was already familiar with was fresh enough to give me a new perspective on it.

Not necessarily a syntax problem

This is a very long thread and I confess I did not even read all the answers. So maybe you have already more material in your hands than what you hoped for, but here is yet another small thing you might want to consider:

You seem to imply that the concrete grammar disambiguate expressions by application of precedence rules, and wonder how one could treat some ambiguities in a different way syntactically. You might want to consider this at a different level: precedence rules would not be part of the syntax of a CFG (thought usually they can be expressed by modifying the CFG), but they would already be a step of semantical analysis rebuilding the abstract syntax "a+(b*c)" from the concrete one "a+b*c". There is nothing against building an abstract syntax "a < b && b < c" from the concrete one "a < b < c" from a syntax point of view: all this can be seen as semantics.

Both equal as lambda expressions

I just went through adding support to this to my grammar, so I thought I would comment. This is how I represented it:

a = b = c

Op=
  |
  +-- a
  |
  +-- Both=
      |
      +-- b
      |
      +-- c

That also works with a < b <= c or the other way around.

My parser is eager, that is why I have more subtrees on the right.
The rationale for this representation is that the second argument is a lambda expression that returns: (b, b = c)
Then with this lambda it is trivial to evaluate: a = b AND b = c