The hunt for the missing data type
hillelwayne.com
The hunt for the missing data type
1–10 of 259 posts
Re: The hunt for the missing data type
#2I would claim that object oriented languages are a syntax, semantics and type system for graphs.
Objects are nodes.
Fields are edges.
The object graph is the heap.
So your whole program state is a graph.
Re: The hunt for the missing data type
#3As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times.
I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.
Re: The hunt for the missing data type
#4I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
I was about to post "Data structures are graphs," but your explanation says it better.
Re: The hunt for the missing data type
#5I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
I think this is a useful model for me personally, and don't want to diminish its potential value to others; I often think of programs as graphs.
I think it's interesting to add to the discussion that I'm wary to reduce anything to any particular "Turing-complete concept". Because anything can be represented by anything.
Re: The hunt for the missing data type
#6I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
Graphs are such a general concept that if you squint everything is a graph. Your example works just as well with structs and member fields, we don't even need the OO hypothesis.
Re: The hunt for the missing data type
#7I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
Right, I think that's just what I said the first time this came up: all languages with GC have graphs builtin.
(Though C has graphs too. If every node shares the same lifetime, then it's pretty easy to manage. Otherwise it can be pretty painful)
And the good news is that you simply use the TYPE SYSTEM to categorize your nodes and edges.
Your edges are references to other objects, which are typed. Node can be typed as well.
---
Although the original article does get at this -- there are many types of graphs, and some of them can be encoded in a typed object graph.
Some of them can't -- you need the equivalent of void* for the edges.
Others would need a List[T] for the edges, if the out degree is not fixed.
And that only covers directed graphs, etc.
Also, it's true that allocating all these tiny objects as GC objects can be very slow, so then you use other representations of graphs, like a list of pairs of node IDs.
I don't really think of it as a "missing" data structure, but yeah now I do see how that framing can be useful.
Re: The hunt for the missing data type
#8> And then for each of those types we have hypergraphs, where an edge can connect three or more nodes, and ubergraphs, where edges can point to other edges.
Huh, I've heard of hypergraphs (although never actually really used them) but never an 'ubergraph'. Sounds tricky!
In practice, how often are there situations you definitely need hypergraphs? I had a particular situation where I needed graphs that were both vertex coloured (labelled) and edge coloured (labelled) - even then it was outside the normal situation for what I was doing (graph canonicalization).
Re: The hunt for the missing data type
#9I wonder if it would be possible to mathematically define (in a theorem proving language like Coq) a bunch of accessor methods as well as a bunch of implementation primitives and then "compile" a custom graph implementation with whatever properties you need for your application. Some accessor methods will be very efficient for some implementations and very inefficient for others, but every method will still be available for every implementation. Profiling your application performance can help adjust the implementation "compiler" settings.
Ironically, this is a graph problem.
Re: The hunt for the missing data type
#10I would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
A limitation is that you can only have one such graph in the program. So any graph algorithm that returns a graph, or uses another graph during the computation, doesn't fit.