I think the real problem is syntax. Someone needs to come up with a textual graph literal that fits in source code, and it'll be good enough for the small type. Switch to a custom ubergraph when you exceed, idk, ten million entries.
The hunt for the missing data type
11–20 of 259 posts
Re: The hunt for the missing data type
#12What would a programming language look like that could address all those issues?
Re: The hunt for the missing data type
#13I understand the constraints, but imagine how legible you could make code by replacing some key parts with a graph type that everybody knows. I honestly think that having a type that supports a small subset of possibilities and only has the simplest algorithms implemented would go a long way.
Re: The hunt for the missing data type
#14As 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.
Then I saw Petgraph [0] which is the first time I had really looked at a generic graph library. It's very interesting, but I still have implemented graphs at a domain level.
Re: The hunt for the missing data type
#15Why don't we have graphs in FP (or in Rust)? Because graphs require mutation (respectively break linearity).
Why don't we have graphs in imperative languages? Perhaps because very few imperative languages have ADTs? Just a thought.
Re: The hunt for the missing data type
#16I would supplement it with the observation that when I was a younger programmer, like many people, I considered "generic" or "flexible" a positive when describing a library or framework. I have come to see it as generally negative, especially when the developer's summary puts these adjectives or something similar front and center.
Let me show you the most flexible possible Javascript framework. This will look like a joke, but it's not. It fits perfectly into an HN post. The most flexible possible JS framework is simply:
eval
Similarly flexible frameworks exist for dynamic scripting languages. For static languages one must invoke the entire compiler as the framework. Of course, if you think about it hard enough, I'm doing that for dynamic languages here too, it just has a snappier representation for dynamic languages.Frameworks and libraries provide their value precisely through limiting things, and then building on those limitations. Of course, the limitations must be well-chosen, to make what can be built on them interesting enough to pay for the limitations the framework chooses. But the essence of them are in their limitations. I start out from the get-go with the maximally flexible framework my language allows, which is itself the language, and the additional framework needs to make limitations on my code in order to do anything useful.
(A problem when framework designers don't understand this is that they make a series of little incorrect design decisions that can often add up to a real pain. For instance, if I were to design a web framework that took over some amount of routing from the user, I would still leave you the ability to claim some bit of the URL space and route it entirely out of my framework, because I understand that my framework is based around limitations and you may need to expose a URL to something that can't work under those limitations. But someone who doesn't realize that frameworks intrinsically involve limitations might fail to give that callout because they can't imagine that someone might have a problem that their framework is not "flexible" and "generic" enough to handle. Imagine a CRUD framework, even a very good one, but I need to offer an endpoint based on streaming server events in the same URL space, which is intrinsically foreign to the CRUD framework's concept of page loads. This is just one example; real frameworks designed without this understanding will make dozens or hundreds of such little mistakes.)
Graphs have the same problem. It seems like they're so flexible and generic that they ought to be more used and more useful. But that's precisely what kills them. Even if you nail down the problem to exactly one representation, they still don't fit. For instance I have a great need for data structures that don't admit cycles, but if all I have is a graph, imposing that limitation from a coding perspective is a real challenge. Mathematically it's trivial, I just say "and this graph has no cycles" et voila [1], there are no cycles, but in code I need to enforce that somehow and there's no trivial solution to that.
Another way of viewing graphs is that we do work in graphs all the time, precisely because everything in RAM can be seen as a graph. GC algorithms even generally work by viewing everything in very raw graphy terms. It just turns out the API you'd expect to work over a graph just isn't useful in the general sense when applied to everything in a programming language's memory space. It seems like it ought to be, but it just isn't. It may seem like it would be great to have a set of employees and extract their names and then look that up into another database etc. etc. with a general graph query language or something, but it turns out the special considerations at each layer make it so that what the general purpose programming language is already doing is actually generally better. The details at each layer matter.
I like the metaphor of architecture astronautics and have often discussed "the 30,000 foot view" versus the view on the ground here on HN, and to my mind the key to the metaphor isn't the nerdery of being an astronaut or the difficulty. The key is that when you get high up, everything looks the same. It feels like graphs ought to be awesome when you're looking down at the entire computing landscape from metaphorical low Earth orbit. But down in the trenches, the local concerns overwhelm that viewpoint... and this is real. This is not just because we all suck or we don't try hard enough or we just Don't Get It. It's real. The architecture astronaut is just wrong in this case. It's not even a beautiful vision this world isn't good enough to manifest or any such conciliatory thing... it's just wrong. It is good to write good code and reduce the amount of bespoke details to be considered. The programming community has made great progress there and there is still great opportunity to do more. But there are an awful, awful lot of details in the world, and the world being detailed is fundamental.
[1]: Or if you are, like me, kinda a fan of surprise stringed instrument attacks, et viola.
Re: The hunt for the missing data type
#17I 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.
If you are looking at the debug symbols and a copy of the program you can usually figure this graph out but you might need to think about it sometimes.
Re: The hunt for the missing data type
#18This is looking like a programming language problem. There is no way to make graph algorithms available in a way where the details are abstracted away. What would a programming language look like that could address all those issues?
It's a shame it's so hard to write that kind of generic template code.
Re: The hunt for the missing data type
#19I think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the re…