Graph programming languages

Apart from lack of time, one of the things that’s stopping me from doing any further work on the ArcEm JIT is that I don’t really know what the code graph needs to look like (What different types of node are there? What data does each node type need to store?), or what the various transformation rules need to be. Working all that out is going to take quite a lot of time, especially if it was all developed within the ArcEm sources.

So rather than developing it in C in the ArcEm sources, I’m wondering what alternative languages are available which could allow for quicker prototyping. A language which has support for polymorphism / interfaces (to cope with the different node types), and which allows me to easily edit those types. It should also make it easy to process graph data structures. Potentially it could be a non-procedural programming language, where the program can just be a list of transformation rules that should be applied to the graph to convert it from the input form to the output form. Perhaps the most crucial thing though, would be ease of debugging – this is a graph I’m dealing with, so ideally there needs to be some way of rendering that graph to the screen at any stage through the program, for easy debugging & verification. Plus some kind of single-stepper mechanism so that I can watch the transformations be applied and spot the exact point where things go wrong.

Has anyone spotted such a system that could meet my requirements? Googling for graph programming languages didn’t result in anything that was obviously useful (just research projects and “big data” systems)

At the moment I’m thinking my best option might be to just create my own prototyping framework in C++. I’ll be able to reuse bits from ArcEm to help get it started (e.g. disassembler), and potentially merge the final code back into ArcEm once it’s complete. But it would still take a fair amount of time to create a framework that’s good enough to make the rest of the task easy.

What an overloaded word graph is. To consider a graph language you need first a suitably abstract notion of a graph. Allow me to draw your attention to chapter 14 of Lua programming gems , ISBN 978-85-903798-4-.

To consider a graph language you need first a suitably abstract notion of a graph.

Thanks – that may have helped steer me on to the right track a bit. I’ve been starting from the viewpoint that I’ll want to separate the different nodes and edges into different types, based on which attributes they have, as if I was to e.g. implement each node/edge type as a C struct. But an abstract graph wouldn’t place any restrictions on which attributes can be applied where (and thus no explicit node/edge types beyond “node” and “edge”), and it’s that flexibility that I’d want to have available while I try and work out the different processing rules.

Allow me to draw your attention to chapter 14 of Lua programming gems , ISBN 978-85-903798-4-.

Unfortunately I have a rather dim view of Lua, so I can’t see myself buying a copy of that book any time soon.

What don’t you like about Lua?

• It’s an interpreted language, so it has some inherent drawbacks compared to compiled languages
  • Poor performance – this was a critical factor on a couple of console game ports that I worked on (and by “critcal”, I mean “spend several weeks converting 10,000-line Lua files to C++”). LuaJIT wasn’t an option, but even if it was I doubt it would have saved us.
  • No compile step = less error checking = more bugs.
• Duck typing makes it very hard for the programmer or the computer to check that the right types are being used in the right places. Insufficient type checking = less error checking = more bugs.
  • For Lua this is particularly bad, since tables are the root of the user-defined type system, and you can add any key to any table, irrespective of its “type”. So you can create a Duck, accidentally pass it to a function which expects a Gorilla, and get a Duck-Gorilla hybrid by mistake.
  • This also didn’t help much with the C++ conversion mentioned above – trying to infer types where none were present wasn’t particularly easy.

What about Haskell or F#?

I haven’t had much exposure to functional programming languages – the closest I’ve come to those two was when I had to decipher a short Haskell program to help with writing a similar algorithm in C++. So I’d first have to learn the languages, and then learn how to do what I want in them, which might not be a particularly quick process.

The next closest thing which I am familiar with would be Prolog, which I did use for a while. Possibly that would work without becoming too awkward.

Prolog is specialised to making inferences. Lazy functional languages, such as Haskell or Clean, are basically graph-reduction machines. There has been a lot of research into making these efficient. Sounds to me as if what you are after is something with a good graphical IDE.

I’m not too fussed about performance – this is only going to be prototype code (unless we find a high-performance language which will work on all the platforms ArcEm works on).

Sounds to me as if what you are after is something with a good graphical IDE.

Pretty much!

Writing my own code for displaying the code graph is possible, but it would obviously be quicker/more convenient to use an existing framework.

What’s a code graph in relation to ArcEm? I looked up the phrase and got something about bridges in Russia…?

Control flow graph is perhaps a more correct term, although I’m not sure if what I’ll be creating would follow the definition exactly.

Have you looked at GP2 which can apparently output C, have a look at The Design of GP2 to see if it’s applicable.

You might also want to look at the graphing features in game engines, such as CryEngine, Unreal, Unity etc.

EDIT: Forgot to mention Script Canvas in Lumberyard

Have you looked at GP2 which can apparently output C, have a look at The Design of GP2 to see if it’s applicable.

Yes – it looks like it’s still stuck in the “research project” phase. Although there is a tool for rendering the graphs, there’s no graphical editor yet, so it’ll be a bit fiddly to learn and write complex programs for. It also only supports a handful of primitive data types, so I’m not sure how well that will work with everything that I need to store.

You might also want to look at the graphing features in game engines, such as CryEngine, Unreal, Unity etc.

I’d be surprised if they had what I was after. Sure, they might have node-based graphical editors, but I doubt they’d have a sophisticated language for manipulating those graphs.