Graph Programming (2020) | Hacker News Reader

Graph Programming (2020)

hyro.ai

92 pointsZivgid11 comments

I think a "labeled port graph" is the suitable abstraction here. Graph nodes assert a number ports each with a label, composition is expressed as edges between ports.

Optionally, ports may assert a type allowing only like-type edges to be valid. Ports may also assert a direction requiring outgoing to connect only to incoming.

A nice feature of this concept (as also described in the article) is that a composition of a number of nodes can be recast to a single node which asserts the ports that have as yet not been connected.

Isn't programming itself inherently consist of "graph"? We convert everything into AST after all.

The use of abstract concept like currying, recursion, map reduce is to have vocabulary express our thought IMO. Turning into graph is like coding imperatively - hard to grasp from quick glance. Code is more frequently read than written

ASTs are, as the name suggests, trees. There are useful concepts you can't express directly in source code of most programming languages. For example, while you can express a function reducing results of other functions directly:

  f(a(), b())

you generally can't do the reverse. Not directly. Best you can do it:

  foo = f()
  a(foo)
  b(foo)

where you create a runtime indirection, or - in a language with reader macros, like Common Lisp:

  (a #1=(f) #1#)

where #1= lets you reference an AST node, and #1# lets you backlink to it. Unfortunately, that code will cause (f) to be called twice.

The article is effectively exploring a way to combine these two methods - to have the code denote a DAG directly (or even cheat a little and denote a graph with cycles), where the runtime representation is also a graph, and not a tree.

Myself, I'm strongly hoping there will be more work done in that direction, because being forced to talk in trees is very limiting. Some problems would be much easier to express as DAGs (or even cyclic graphs), and would even be easier to read them as such.

I worry that what's keeping us working with trees is the nature of plaintext itself. I haven't proven it, or seen it proven, but I strongly suspect that there is no minimal, direct representation of a DAG possible in plaintext - you can't move past a tree without assigning labels for backreferences.

SISAL was a language that parsed to a dataflow intermediate representation (IF1). IF1 would then be compiled to native instructions for either a regular (e.g. Cray) or dataflow architecture processor.

IIRC, function composition with multiple return values is sufficient to transform to IF1's 'function with named ports' representation.

https://en.wikipedia.org/wiki/SISAL

I wrote a blog post about this https://shopify.engineering/understanding-programs-using-gra....

A closer model is a Control Flow Graph (CFG): https://en.wikipedia.org/wiki/Control-flow_graph

also a lot of loops look like combinatorics and graphs to me these days

This looks a lot like a Probabilistic Programming Language, minus the explicit probability aspect. Almost like operating over a Bayes Net, but simpler. I like this model of computation and I think one can go quite far with these approaches. See: TensorFlow Probability (Python), Amidst (Java), PyMC3 (Python), Keanu (Java), etc.

Checking the intent and historical awareness:

> https://github.com/hyroai/computation-graph implements the first graph-programming framework, in python

Is this claiming to be the first such programming framework to be unveiled for Python, or the first one ever that just happens to b in Python? The comma usually would be chosen and placed to indicate the latter. But we’ve been doing this for many years under different guises.

Thinking about trees and DAGs, and having converted trees to DAGs in translators via pattern-matching: Functional languages like Haskell with let-forms allow graphs to be constructed, I believe. The let provides the definition of nodes with multiple out-edges.

Really appreciating this after reading it. Given the analogues in functional languages, I'm thinking of using this more to reason about whole python programs and then implement that reasoning more directly as these graphy compositions. To me it seems like a very elegant abstraction.

This looks like my idealized functional language [0], but practical.

[0]: https://github.com/mlajtos/moniel

Reply on news.ycombinator.com