[HN Gopher] Understanding Programs Using Graphs
___________________________________________________________________
Understanding Programs Using Graphs
Author : caution
Score : 99 points
Date : 2020-06-02 17:14 UTC (5 hours ago)
(HTM) web link (engineering.shopify.com)
(TXT) w3m dump (engineering.shopify.com)
| ncfausti wrote:
| I started learning Blueprints in Unreal Engine recently, I swear
| it has helped my problem solving ability in other general areas
| of programming. Watching the links light up as nodes are executed
| is pretty great for debugging.
| johnsonjo wrote:
| I honestly feel I had a similar feeling when I played Little
| Big Planet 2 when I was in my late teens. It had a creative
| mode where you could use basic logic gates like and gates and
| or gates, and other utilities like counters and the like
| (including not just digital inputs but also analog ones).
| Understanding inputs and outputs from a chip level was quite
| interesting to me. I tried to make a calculator and learned all
| about bit adders and such, but was never able to figure out as
| a teenager how to make a conversion of the binary bits to
| decimal so that I could display it. I'm still not entirely sure
| what the proper algorithm is for that (if by chance anyone
| knows that would be nice to know), but I'm sure I could find it
| out now that I have a degree in CS (just saying that's plenty
| sufficient but not necessary to have a degree).
| indiv0 wrote:
| You'd use a BCD to 7 segment display circuit [0]. At least
| that's what we did in my digital systems design course.
| Depending on what number you're trying to display you light
| up different parts of the segmented display.
|
| [0]: http://electronics-course.com/bcd-7-segment
| thelazydogsback wrote:
| The graphic is too fuzzy -- but I'm trying to figure out why the
| AST for fib in Ruby would be so complex...
| chrisseaton wrote:
| Ruby has more complicated semantics.
|
| An example of a concrete difference here is that Ruby checks
| for overflow on integer maths, where Java does not. This means
| each maths operation is a little cluster of nodes, rather than
| a single node.
|
| Another example is that Ruby has dynamic typing, so values that
| come into the function need to be type checked, and values
| going out need to put into a format where they can have their
| type inspected.
|
| One more example is that the call to fib in Java is static - we
| know exactly where that goes. In Ruby the call is dynamic, so
| we need to check we're calling the correct method.
|
| Here's a full SVG copy of that diagram
| https://www.dropbox.com/s/k68id9aqu258blw/fib-ruby.svg.
| thelazydogsback wrote:
| Thanks - I knew all that, but I guess I expected those
| semantics to be implicit rather than explicit. I guess
| because we're not really looking at an "AST" but an
| intermediate executable representation. Certainly this is
| good for understanding what Ruby is doing, but not so useful
| for understanding what fib is doing - trees vs. forest. I
| guess what you really want is to be able to zoom into IL-
| semantics only if you care about such things, otherwise you
| show only enough detail to get across the algorithm being
| expressed -- possibly with the addition of declaratively
| showing additional constraints that have been added by the
| runtime without showing how the contraints have been
| satisfied.
| navan wrote:
| Interesting article and good question about whether we should
| program using graphs. In a different domain, languages like
| halide, tvm and tiramisu or in a way letting programmers create
| graphs for high performance.
| lmkg wrote:
| Programming via graphs is common in big-data machine-learning
| as well. Apache Beam and Tensorflow are both programmed by
| creating an execution graph object, and handing that off to the
| runtime.
| rcfox wrote:
| Makefiles basically just trees.
| simonw wrote:
| One of the many neat uses of Observable is quickly prototyping
| these kinds of graphics - often by starting with a notebook
| someone has already created and iterating on it.
|
| I have a notebook here which can visualize the table structure of
| any Datasette-hosted database:
| https://observablehq.com/@simonw/datasette-table-diagram
|
| My first version used a force-directed graph for this, but then
| Thomas Ballinger from the Observable team showed me how to use a
| DOT diagram, which is a much better visualization for relational
| tables.
| kipply wrote:
| Seas of nodes are also used as IR in Java Hotspot and the V8
| engine (https://doar-e.github.io/blog/2019/01/28/introduction-to-
| tur...)
| zomglings wrote:
| This was a nice article, and I thank you for providing those
| references at the end.
|
| The article makes it seem as if TruffleRuby is a Shopify project,
| where this GitHub repo seems to differ on that point:
| https://github.com/oracle/truffleruby. What's the deal?
|
| I'm also very curious about how much TruffleRuby helps you save
| in infrastructure costs. It looks like Shopify is starting to put
| together serious systems around optimization of Ruby code.
| chrisseaton wrote:
| We're working on TruffleRuby at Shopify, but it's an Oracle-led
| project yes.
|
| > I'm also very curious about how much TruffleRuby helps you
| save in infrastructure costs.
|
| We don't have an empirical answer to this yet. We're working on
| it. We're investing in MRI, TruffleRuby, and many other parts
| of the Ruby ecosystem.
| zomglings wrote:
| Cool. Another question since you are around: How many of your
| sea-of-nodes-level optimizations do you think can be applied
| instead as AST-level optimizations?
| chrisseaton wrote:
| Well you can see the one in the article about sharing the
| computation from the two branches - there's no way to
| represent that in an AST, for the very reason that it's a
| tree - there can only be one user of a node in an AST, but
| in a graph, multiple nodes can use it.
|
| You could introduce some kind of hidden local variables and
| assign to those, but then you're kind of building a graph
| in an AST, and might as well use a graph, and those
| variables are harder to understand for other optimisations.
|
| (Note that these aren't 'my' optimisations, I'm just
| writing about them.)
___________________________________________________________________
(page generated 2020-06-02 23:00 UTC)