3 ms·

https://news.ycombinator.com/item?id=561443#562884 https://news.ycombinator.com/item?id=561443#562884 Does anybody know how array languages handle pointers and

https://news.ycombinator.com/item?id=561443#562884 https://news.ycombinator.com/item?id=561443#562884 Does anybody know how array languages handle pointers and trees?

refset 7y ago
I believe Aaron Hsu's work on tree processing for Co-dfns [0] is a novel example of tree handling - a data parallel compiler for efficient compilation on a GPU using extensive tree-oriented "nanopass" transformations [1]. [0] https://github.com/Co-dfns/Co-dfns https://github.com/Co-dfns/Co-dfns [1] https://dyalog.tv/Dyalog18/?v=hzPd3umu78g https://dyalog.tv/Dyalog18/?v=hzPd3umu78g
- akkartik 7y ago
  Holy crap, that video is mind-blowing. Thank you! I was vaguely aware of Co-dfns before, but now it's squarely on my radar.
vchak1 7y ago
John Earnest also details how trees are handled in K (an array based language invented by Arthur Whitney). https://github.com/JohnEarnest/ok/blob/gh-pages/docs/Trees.md https://github.com/JohnEarnest/ok/blob/gh-pages/docs/Trees.m...
- RodgerTheGreat 7y ago
  I also wrote a paper about recursive combinators which touches on these ideas a bit: http://archive.vector.org.uk/art10501740 http://archive.vector.org.uk/art10501740 And I translated some of Aaron Hsu's APL ideas into k5. With a little massaging they work just as well: https://github.com/JohnEarnest/ok/blob/gh-pages/examples/key.k https://github.com/JohnEarnest/ok/blob/gh-pages/examples/key...
geocar 7y ago
If you have cycles in your graph, you can build a tree out of a vector of indices, or as a table of parent/child node keys. The former is what John Scholes does[1], and the latter has plenty of common SQL examples. [1]: https://youtu.be/DsZdfnlh_d0 https://youtu.be/DsZdfnlh_d0 If you have a non-cyclic tree (e.g. a 256-trie) you can nest it directly: @/ will traverse to nodes, and COW keeps updates from trashing memory too much. However trees are rarely the best data structure: Binary search on a sorted list can beat b-trees simply because the end of the search will already be in cache, so for a routing table of IP address ranges, I use something like: ipStart where ipStart bin x

https://news.ycombinator.com/item?id=561443#562884 https://news.ycombinator.com/item?id=561443#562884 Does anybody know how array languages handle pointers and trees?

refset 7y ago

I believe Aaron Hsu's work on tree processing for Co-dfns [0] is a novel example of tree handling - a data parallel compiler for efficient compilation on a GPU using extensive tree-oriented "nanopass" transformations [1]. [0] https://github.com/Co-dfns/Co-dfns https://github.com/Co-dfns/Co-dfns [1] https://dyalog.tv/Dyalog18/?v=hzPd3umu78g https://dyalog.tv/Dyalog18/?v=hzPd3umu78g

akkartik 7y ago
Holy crap, that video is mind-blowing. Thank you! I was vaguely aware of Co-dfns before, but now it's squarely on my radar.

vchak1 7y ago

John Earnest also details how trees are handled in K (an array based language invented by Arthur Whitney). https://github.com/JohnEarnest/ok/blob/gh-pages/docs/Trees.md https://github.com/JohnEarnest/ok/blob/gh-pages/docs/Trees.m...

RodgerTheGreat 7y ago
I also wrote a paper about recursive combinators which touches on these ideas a bit: http://archive.vector.org.uk/art10501740 http://archive.vector.org.uk/art10501740 And I translated some of Aaron Hsu's APL ideas into k5. With a little massaging they work just as well: https://github.com/JohnEarnest/ok/blob/gh-pages/examples/key.k https://github.com/JohnEarnest/ok/blob/gh-pages/examples/key...

geocar 7y ago

If you have cycles in your graph, you can build a tree out of a vector of indices, or as a table of parent/child node keys. The former is what John Scholes does[1], and the latter has plenty of common SQL examples. [1]: https://youtu.be/DsZdfnlh_d0 https://youtu.be/DsZdfnlh_d0 If you have a non-cyclic tree (e.g. a 256-trie) you can nest it directly: @/ will traverse to nodes, and COW keeps updates from trashing memory too much. However trees are rarely the best data structure: Binary search on a sorted list can beat b-trees simply because the end of the search will already be in cache, so for a routing table of IP address ranges, I use something like: ipStart where ipStart bin x