Live data from Hacker News

The hunt for the missing data type

hillelwayne.com

11–20 of 259 posts

Re: The hunt for the missing data type

#11
I 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 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.

Re: The hunt for the missing data type

#12
This 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?

Re: The hunt for the missing data type

#13
devils advocate: Is this maybe a case of discarding an 80% solution because you can’t do the last 20%?

I 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

#14

As 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.

I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sense to implement them at a domain-ish level (the article mentions this in the "There are too many implementation choices" section).

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.

[0] https://github.com/petgraph/petgraph

Re: The hunt for the missing data type

#15
Ok, trees are not graphs but they are very related, and algebraic data types are trees, so they are ubiquitous in functional programming.

Why 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

#16
This is a good article and I endorse it.

I 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

#17

I 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.

For that matter it's true about a certain kind of C program. In a civilized language you have run-time typing and introspection and have all the type information so that it is straightforward to look at the program's data structures as 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

#18
post #12

This 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?

Some C++ libraries do pretty well. In the Eigen math library you can call most functions on dense or sparse matrices, and some template magic makes it work efficiently for all combinations.

It's a shame it's so hard to write that kind of generic template code.

Re: The hunt for the missing data type

#19
post #11

I 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…

What do you mean by "textual graph literal"?
Post reply on HN