7 ms·

A Gentle Introduction to Ted Nelson's ZigZag Structure (2002)

89 points by breck 5y ago

gota 5y ago
Wait, I just glanced at the material - is this someone (re/independently) inventing graphs?
- JKCalhoun 5y ago
  Sort of. From Wikipedia: "He coined the terms hypertext and hypermedia in 1963 and published them in 1965."
- feanaro 5y ago
  zzstructures are both graphs where you can have many edges (of different types) between any two nodes and a method of visual presentation and navigation of that structure.
- cratermoon 5y ago
  See Nelson's paper "A File Structure for the Complex, the Changing and the Indeterminate" https://andymatuschak.org/files/papers/Nelson1965.pdf https://andymatuschak.org/files/papers/Nelson1965.pdf Edit to add: I just noticed that the last update to that page was in 2002. When I hit the box about CSS, Mozilla, Netscape Navigator 4.7, and WML I did hard double-take.
- DennisP 5y ago
  It's a "subset of general graphs - the restriction is that a node may have only one incoming and one outgoing edge with a given edge label. So structures are organized as lists/strings of nodes, which makes it easier to visualize than general graphs" http://lambda-the-ultimate.org/node/233#comment-1706 http://lambda-the-ultimate.org/node/233#comment-1706
- uxp100 5y ago
  No, but also not just someone, Ted Nelson. I highly recommend Geeks Bearing Gifts or Computer Lib/Dream Machines. He is a crank, who has never been involved in a successful software project as far as I am aware. He is also great.
  - prionassembly 5y ago
    Every crank is a visionary, but not every visionary is a crank. Some visionaries prove to be prophets and seers. Some have ideas that are bogus. Due to the nature of visionary ideas, this is most of the time unknown -- e.g. Julian Jaynes's bicameral mind. A crank is a visionary whose ideas are knowably bogus: e.g. Rupert Sheldrake. (A charlatan is unlike a crank because he has no idee fixe, no vision -- he moves opportunistically. A conspiracist is similarly unlike a crank because it bites at anything that moves.) Whether Ted Nelson is a crank is left as an exercise for the reader.
nabla9 5y ago
Lukka and others wanted to bring Ted Nelson's dream into reality using open source (GZigZag). Ted Nelson fucked them over. After giving permission he suddenly started to assert trademark and patent rights. "It is a sad story. It is an infuriating story." http://lambda-the-ultimate.org/node/233#comment-1715 http://lambda-the-ultimate.org/node/233#comment-1715
- tangentstorm 5y ago
  Happily, Nelson's patent has finally expired. :) https://patents.google.com/patent/US6262736 https://patents.google.com/patent/US6262736
  - joshgrib 5y ago
    I was thinking this was a data structure, but based on the patent it's actually more a user interface design to explore data > What is claimed is: > 1. A method for visualizing data on a display, comprising: > ... In other words it seems like it could replace a spreadsheet as a way to explore data, but not _necessarily_ by storing the data any differently
- mindcrime 5y ago
  FWIW, some portion of what was Xanadu apparently finally made it to the OSS world. See: http://open.xanadu.com/ http://open.xanadu.com/ I haven't looked at it much, so not sure quite what the state of it all is.
  - astrange 5y ago
    I wasn't expecting a site from 1999 from that "finally".
    - mindcrime 5y ago
      Well, consider that Xanadu itself dates back to like the 1960's or something... I don't remember all the details off-hand. That said, I thought the Udanax stuff came later than 1999 as well. I wouldn't even have noticed the 1999 reference if you hadn't pointed it out just now! Mandela moment for me? Hmmm.
Greek0 5y ago
Brief summary, please correct me if I'm wrong. A ZigZag structure is an undirected graph. Nodes are arranged in an n-dimensional space. For each coordinate axis, every node can only have one edge in the plus-1-along-coordinate direction, and one edge in the minus-1-along-the-coordinate. I.e. no diagonal connections, and max one connection in each "cardinal direction" (+ and - in n dimensions = 2n directions). In its simplest form, a ZigZag structure can be an n-dimensional grid, where each node is connected to its direct neighbors in the grid. In 2D, that would give you a spreadsheet. However, ZigZag can do more: you can have loops along any axis, e.g. a spreadsheet where the columns "wrap around". Furthermore, ZigZag supports looping the columns of only one particular row: a normal 2D spreadsheet, except that row 13 only has 4 columns, and those columns are wrapped up in a loop. You could also have sparse grids - where nodes are missing, and the edges skip over the missing node. The idea is to have something that locally, if you look only at the surrounding nodes, always looks like a neat n-dimensional grid. But the global topology can be totally whacky. I have no idea what you would use such a thing for.
- rendall 5y ago
  Thank you for summarizing. I wasn't even sure I wanted to read this, but now I'm sure I do.
- cjohnson318 5y ago
  > I have no idea what you would use such a thing for. Ditto. Every few years I look at this again, and I never can figure out what to use it for. At any rate, yours is a very good summary, thank you.
- aphextron 5y ago
  >I have no idea what you would use such a thing for. This can be said for pretty much all of Ted's work. Interesting and thought provoking, nonetheless.
- jerf 5y ago
  "I have no idea what you would use such a thing for." Presenting graph-structured data in a way that the graph has sufficient restrictions on it to be representable usefully in a UI. In some sense all data structures are just restrictions on graph data structures. So why not just use graphs directly more often? Because the full freedom of graphs can result in a lot of situations that are pathological for both algorithms and UIs, such as graphs that mostly have one node connected to one node, except suddenly there's a node with 1,000,000 connections, which raises obvious UI issues. To the extent this is not used today, it's probably because in the end it's still too general and has been outcompeted by all the other UI widgets we have that take more advantage of all the menagerie of local structures we have identified. It turns out that we are generally willing to do the work to create specialized representations for those things. We do lose some generality, but, again, we seem willing to do the work to specialize, so it all mostly works out. Only a very few people are out there working with data with so little such specialized support that they are reduced to working with raw graphs directly, and they already mostly have no choice but to learn to deal with the graphs directly and would be as frustrated trying to jam them into this structure as they would any other structure that restricts graphs.
dang 5y ago
Seems like this is the first real HN thread about this, but it has come up in comments over the years, including by people who worked on it: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=ted%20zigzag&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
cjohnson318 5y ago
This helped me understand the dimensions better: http://profs.etsmtl.ca/mmcguffin/research/zigzag/ http://profs.etsmtl.ca/mmcguffin/research/zigzag/
winkywooster 5y ago
Here's a video of Ted Nelson describing the idea: https://www.youtube.com/watch?v=n22A-Say7do https://www.youtube.com/watch?v=n22A-Say7do
vincent-toups 5y ago
Gonna be honest: everything about this screams "inescapable morass."
dustingetz 5y ago
> To put it coarsely, outside ZigZag there are three different kinds of structures in computers today: linear lists (and grids i.e.~lists of lists), hierarchical trees and messes. That is really messes, not meshes. By a mess, I mean any complicated data structure, usually with one-directional links to make things even more unmanageable. That's not a mess, that's a graph.
tuukkah 5y ago
Here's an article on follow-up work by the author with Ted's patented stuff (the ZigZag structure) replaced with RDF: Hyperstructure: Computers built around things that you care about, Benja Fallenstein and Tuomas J. Lukka https://fenfire-org.github.io/manuscripts/2004/hyperstructure/ https://fenfire-org.github.io/manuscripts/2004/hyperstructur...
xtiansimon 5y ago
This is new to me, but when I noticed the project is a Java app, I immediately recalled CMapTools Wasn't that another passion project? https://cmap.ihmc.us/ https://cmap.ihmc.us/ https://en.wikipedia.org/wiki/CmapTools https://en.wikipedia.org/wiki/CmapTools

89 points by breck 5y ago

gota 5y ago

Wait, I just glanced at the material - is this someone (re/independently) inventing graphs?

JKCalhoun 5y ago
Sort of. From Wikipedia: "He coined the terms hypertext and hypermedia in 1963 and published them in 1965."
feanaro 5y ago
zzstructures are both graphs where you can have many edges (of different types) between any two nodes and a method of visual presentation and navigation of that structure.
cratermoon 5y ago
See Nelson's paper "A File Structure for the Complex, the Changing and the Indeterminate" https://andymatuschak.org/files/papers/Nelson1965.pdf https://andymatuschak.org/files/papers/Nelson1965.pdf Edit to add: I just noticed that the last update to that page was in 2002. When I hit the box about CSS, Mozilla, Netscape Navigator 4.7, and WML I did hard double-take.
DennisP 5y ago
It's a "subset of general graphs - the restriction is that a node may have only one incoming and one outgoing edge with a given edge label. So structures are organized as lists/strings of nodes, which makes it easier to visualize than general graphs" http://lambda-the-ultimate.org/node/233#comment-1706 http://lambda-the-ultimate.org/node/233#comment-1706
uxp100 5y ago
No, but also not just someone, Ted Nelson. I highly recommend Geeks Bearing Gifts or Computer Lib/Dream Machines. He is a crank, who has never been involved in a successful software project as far as I am aware. He is also great.
- prionassembly 5y ago
  Every crank is a visionary, but not every visionary is a crank. Some visionaries prove to be prophets and seers. Some have ideas that are bogus. Due to the nature of visionary ideas, this is most of the time unknown -- e.g. Julian Jaynes's bicameral mind. A crank is a visionary whose ideas are knowably bogus: e.g. Rupert Sheldrake. (A charlatan is unlike a crank because he has no idee fixe, no vision -- he moves opportunistically. A conspiracist is similarly unlike a crank because it bites at anything that moves.) Whether Ted Nelson is a crank is left as an exercise for the reader.

nabla9 5y ago

Lukka and others wanted to bring Ted Nelson's dream into reality using open source (GZigZag). Ted Nelson fucked them over. After giving permission he suddenly started to assert trademark and patent rights. "It is a sad story. It is an infuriating story." http://lambda-the-ultimate.org/node/233#comment-1715 http://lambda-the-ultimate.org/node/233#comment-1715

tangentstorm 5y ago
Happily, Nelson's patent has finally expired. :) https://patents.google.com/patent/US6262736 https://patents.google.com/patent/US6262736
- joshgrib 5y ago
  I was thinking this was a data structure, but based on the patent it's actually more a user interface design to explore data > What is claimed is: > 1. A method for visualizing data on a display, comprising: > ... In other words it seems like it could replace a spreadsheet as a way to explore data, but not _necessarily_ by storing the data any differently
mindcrime 5y ago
FWIW, some portion of what was Xanadu apparently finally made it to the OSS world. See: http://open.xanadu.com/ http://open.xanadu.com/ I haven't looked at it much, so not sure quite what the state of it all is.
- astrange 5y ago
  I wasn't expecting a site from 1999 from that "finally".
  - mindcrime 5y ago
    Well, consider that Xanadu itself dates back to like the 1960's or something... I don't remember all the details off-hand. That said, I thought the Udanax stuff came later than 1999 as well. I wouldn't even have noticed the 1999 reference if you hadn't pointed it out just now! Mandela moment for me? Hmmm.

Greek0 5y ago

Brief summary, please correct me if I'm wrong. A ZigZag structure is an undirected graph. Nodes are arranged in an n-dimensional space. For each coordinate axis, every node can only have one edge in the plus-1-along-coordinate direction, and one edge in the minus-1-along-the-coordinate. I.e. no diagonal connections, and max one connection in each "cardinal direction" (+ and - in n dimensions = 2n directions). In its simplest form, a ZigZag structure can be an n-dimensional grid, where each node is connected to its direct neighbors in the grid. In 2D, that would give you a spreadsheet. However, ZigZag can do more: you can have loops along any axis, e.g. a spreadsheet where the columns "wrap around". Furthermore, ZigZag supports looping the columns of only one particular row: a normal 2D spreadsheet, except that row 13 only has 4 columns, and those columns are wrapped up in a loop. You could also have sparse grids - where nodes are missing, and the edges skip over the missing node. The idea is to have something that locally, if you look only at the surrounding nodes, always looks like a neat n-dimensional grid. But the global topology can be totally whacky. I have no idea what you would use such a thing for.

rendall 5y ago
Thank you for summarizing. I wasn't even sure I wanted to read this, but now I'm sure I do.
cjohnson318 5y ago
> I have no idea what you would use such a thing for. Ditto. Every few years I look at this again, and I never can figure out what to use it for. At any rate, yours is a very good summary, thank you.
aphextron 5y ago
>I have no idea what you would use such a thing for. This can be said for pretty much all of Ted's work. Interesting and thought provoking, nonetheless.
jerf 5y ago
"I have no idea what you would use such a thing for." Presenting graph-structured data in a way that the graph has sufficient restrictions on it to be representable usefully in a UI. In some sense all data structures are just restrictions on graph data structures. So why not just use graphs directly more often? Because the full freedom of graphs can result in a lot of situations that are pathological for both algorithms and UIs, such as graphs that mostly have one node connected to one node, except suddenly there's a node with 1,000,000 connections, which raises obvious UI issues. To the extent this is not used today, it's probably because in the end it's still too general and has been outcompeted by all the other UI widgets we have that take more advantage of all the menagerie of local structures we have identified. It turns out that we are generally willing to do the work to create specialized representations for those things. We do lose some generality, but, again, we seem willing to do the work to specialize, so it all mostly works out. Only a very few people are out there working with data with so little such specialized support that they are reduced to working with raw graphs directly, and they already mostly have no choice but to learn to deal with the graphs directly and would be as frustrated trying to jam them into this structure as they would any other structure that restricts graphs.

dang 5y ago

Seems like this is the first real HN thread about this, but it has come up in comments over the years, including by people who worked on it: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=ted%20zigzag&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

cjohnson318 5y ago

This helped me understand the dimensions better: http://profs.etsmtl.ca/mmcguffin/research/zigzag/ http://profs.etsmtl.ca/mmcguffin/research/zigzag/

winkywooster 5y ago

Here's a video of Ted Nelson describing the idea: https://www.youtube.com/watch?v=n22A-Say7do https://www.youtube.com/watch?v=n22A-Say7do

vincent-toups 5y ago

Gonna be honest: everything about this screams "inescapable morass."

dustingetz 5y ago

> To put it coarsely, outside ZigZag there are three different kinds of structures in computers today: linear lists (and grids i.e.~lists of lists), hierarchical trees and messes. That is really messes, not meshes. By a mess, I mean any complicated data structure, usually with one-directional links to make things even more unmanageable. That's not a mess, that's a graph.

tuukkah 5y ago

Here's an article on follow-up work by the author with Ted's patented stuff (the ZigZag structure) replaced with RDF: Hyperstructure: Computers built around things that you care about, Benja Fallenstein and Tuomas J. Lukka https://fenfire-org.github.io/manuscripts/2004/hyperstructure/ https://fenfire-org.github.io/manuscripts/2004/hyperstructur...

xtiansimon 5y ago

This is new to me, but when I noticed the project is a Java app, I immediately recalled CMapTools Wasn't that another passion project? https://cmap.ihmc.us/ https://cmap.ihmc.us/ https://en.wikipedia.org/wiki/CmapTools https://en.wikipedia.org/wiki/CmapTools