We talk so much about Abstract Syntax Trees, but maybe we should talk about "abstract structure graphs"?

Say you have code like:

foo = 1;
foo += bar(foo);

In AST form, using Lisp notation:

'((:= "foo" 1)
(+= "foo" ("bar" "foo")))

In "ASG" form:

'((:= #1="foo" 1)
(+= #1# ("bar" #1#))

Where #1= and #1# mean all instances of #1# contain (via pointers) *the same* object as marked with #1=, not just an equal one.

Some pictures to clarify what I mean are attached.


Now I'm not a compiler guy, but I'm pretty sure the very next step after parsing some code into AST is turning it into "ASG" - whether represented as a graph structure directly, or by a combination of helper structures (e.g. symbol table) and dynamic state (e.g. "environments" carried by recursing functions). You need to do that in some way, to be able to correctly associate a thing (like variable, function) with all references to it in the AST.

I wonder, why not expose this abstraction to the user?


In a way, we already implicitly code in graphs, not in trees. Rules of most programming languages make it that when you write:

foo = 1; foo += bar(foo);

all three instances of "foo" are *meant to* refer to the same thing.

But then, for code transformation, we parse it into AST, and that "sameness" becomes implicit. The graph becomes unrolled into a tree, and it's hard to walk it. We need supplemental information to work with it.

But what if we let the transformer writers walk graphs instead?


Imagine a more complex case:

a = bar(foo);
b = bar(foo) + bar(baz);

In pseudo-Lisp,

((:= a (bar foo))
(:= b (+ (bar foo) (bar baz))))

What if that parsed, in memory, into a graph structure like:

((:= a #1=(#2=bar foo))
(:= b (+ #1# (#2# baz))))

(picture attached)

Would it be easier or harder to work with it?

I honestly have no answer; it's just some pondering that I had on the back of my mind for the last year or so.


The previous toot had a notation change on the diagram - function application is made explicit, and so is ordering of the edges (to compensate for PlantUML/Graphviz "optimizing" it).

But operators are functions too, so how about the same, but with all function applications explicit?

Attached is a picture of a proper graph form of the code.

I wonder, is that a more useful form to work with than AST?

I'm likely reinventing a branch of here; pointers to existing body of work appreciated.


@temporal I spent some time looking at the graph and I think can't help but think it doesn't contain enough information to recreate the original structure. Either that or I don't understand the notation.

The Lisp form is very clear though.

@loke I've not had time to investigate in depth, but the graph form looks complete to a quick glance. I might be missing something, but it looks executable, so I'd've though it equivalent.

Interested to know what you think is missing (and hence what I might've missed).



@ColinTheMathmo, since I have you in this thread - do you know if there exists, and/or could you help me find, a branch of mathematics that provides a language for higher-level transformations of graphs?

E.g. I have two directed graphs (or multigraphs) and want to join them together, based on some rules of how edges are formed.

Example use case here: mastodon.technology/@temporal/.

There must be a relevant body of vocabulary for this. I took a look at "graph algebra" on Wiki, but only got confused.


· · Web · 1 · 0 · 0

@temporal My knowledge is a little (well, a lot) out-of-date, but to my knowledge there is no such general language. AFAIK, when mathematicians want to do something like "Prepend digraph G to digraph H" they simply write the operation. So P(G,H) = (V,E) where V = V(G)uV(H), and E = E(G) u E(H) u D where D={(u,v) for u in V(G) and v in V(H)}

They might then invent a notation like D = V(G)->V(H), note somewhere what that means, then use it freely elsewhere.

This probably doesn't help.


@ColinTheMathmo Thanks, this gives me some perspective.

I just stumbled upon relevant material, that just happened to be on HN's frontpage today:


Can't decide if the article is wise or full of confusion, but it touches on some of the same things this toot thread did.


Associated HN thread, which is full of the kind of information I am interested in. Struck gold here.


@temporal There's a lot going on in both the article and the thread ... I hope they are helping you, even if only giving you more to think about.

I'm not sure I can help further, but feel free to ask. Don't forget, if it's helpful, you can ask @Chartodon to chart this conversation.


Sign in to participate in the conversation
Mastodon for Tech Folks

This Mastodon instance is for people interested in technology. Discussions aren't limited to technology, because tech folks shouldn't be limited to technology either!