About
Graphene is a tiny implementation of hierarchical dataflow programming.
If you're new to this kind of programming, think of it as a spreadsheet:
 You create cells with values or formulas inside
 These cells can refer to each other
 When one cell changes, everything that uses it changes too
Here's a graph that calculates area and circumference of a circle, given
a radius r
and the value of pi
:
When the radius (or pi
) changes,
area and circumference are automatically updated.
Graphene extracts the core ideas from Antimony (some of which are described in my Dataflow Engine writeup) and implements them in under 500 lines of Racket.
Core ideas
Everything is code
For graphbased programming to be useful, it must be at least as powerful as its plaintext counterpart.
In Graphene, every datum in a graph is a fullfledged Racket script. Datums are free to define variables, helper functions, etc, and the returned value of a datum is the result of its last expression.
Dependency tracking
Every datum in a graph is evaluated in an environment that includes other datums in that graph. In this environment, other datums are noargument functions. Calling one of these functions both returns the value and records the lookup.
In the graph below, (+ 1 (b))
both
looks up the value of b
and records
that a
cares about b
's value.
A graph stores tables that record forward, inverse, and upstream lookups.
 Forward means that one datum called another
 Inverse is the opposite of forward
 Upstream is the union of the datum itself and all forward lookup's upstream tables. This represents everything that could affect a particular datum.
This graph above has the following lookup tables:
Forward  a 
b 
b 
c 

c 
None  
Inverse  b 
a 
c 
b 

a 
None  
Upstream  a 
a, b, c 
b 
b, c 

c 
c 
With this information, we can correctly propagate changes through the graph.
Using the upstream table, the system also detects (and raises an error on) circular dependencies:
Namespaces and hierarchy
Why are hierarchical graphs useful?
 Information hiding: Implementation details shouldn't be globally visible
 Organization: It's humanfriendly to group related logic into a single block
Let's walk through an example of a system with two subgraphs:
The interesting parts here are the input
and output
keywords:
input
indicates that a datum is evaluated in its parent graph's environmentoutput
makes a datum's value visible to its parent graph
How does this apply to the example above?
 The
n
datums in subgraphs are labelled as inputs, so they grabi
from the parent environment and share it in the subgraph  The
out
datums are labelled as outputs, so they are visible to the outside world  The
ints
datums are implementation details, so the outside world can't see them; they could be changed with no consequences
This design naturally lends itself to a userfriendly display that exposes
 Editable expression and resulting value of
input
datums  Value of
output
datums
For the graph above, the hierarchical view looks something like this:
Change propagation
Each graph stores a dirty queue, which is a list of datums that need reevaluation.Updating the graph is done by popping the head off the queue, evaluating it, and inserting its children (i.e. anything that looked it up) into the queue.
Here's what that looks like in code (read topolist
as queue
for the moment):
(define (graphsync! g)
(unless (topolistempty? (graphdirty g))
;; Get the first item from the list and evaluate it
(let* ([head (topolistpop! (graphdirty g))]
[changed (graphevaldatum! g head)])
;; If it changed, add all of its children to the dirty list
(when changed
(map (lambda (k) (graphdirty! g k))
(lookupinverse>list (graphlookup g) head)))
;; Recurse until the dirty list is empty
(graphsync! g))))
Now, what's a topolist
?
Given this queue of datums that need to be reevaluated, we should schedule them in an order that minimizes rereevaluation.
When a
changes, the correct reevaluation order is b
then c
;
not c
, then b
, then c
again.
Expressed formally, we want a topologically sorted lists of datums to evaluate.
In Graphene, I define a topolist
structure
that creates a topologically sorted list for a given comparison operator.
When used in the graph, the comparison operator is whether a particular datum is downstream of another.
Here's what this looks like in the graph
constructor:
(define (makegraph)
(let* ([lookup (makelookup)]
[comp (lambda (a b) (lookupdownstream? lookup a b))]
[dirty (maketopolist comp)])
(graph (makehash) lookup dirty #f)))
The implementation also includes a topolistpops!
function,
which returns every item in the list until a dependency is found.
In this graph, when a
changes, topolistpops!
would return '(b c)
.
This could enable automatic parallelization of the graph update
(since b
and c
can be evaluated independently);
implementation is left as an exercise for the reader.
Comparison to Antimony
(Feel free to skip this section if you haven't worked with Antimony's graphs;
this is very much an inside baseball discussion.)
Graphene is primarily a toy library and a way to practice my Schemefu. However, it does solve a few interesting problems that Antimony's graphs encounter.
Correct by construction
Graphene ensures that a graph's state is correct by construction. The data in the graph can be invalid or illformed, but the structure of the graph itself is guaranteed to be valid.
Consider the following graph in Antimony:
There's an ambiguity here: the graph has two toplevel nodes named x
.
In practice, the one that was added first wins;
this adds an awkward pathdependence to what should be
a pure function of the graph's state.
In contrast, Graphene will raise an error if you attempt to create two datums with the same identifier.
No nodes, only subgraphs
Graphene also simplifies Antimony's subgraph / node distinction by eliminating nodes.
In Antimony, you could represent a circle as either a script node:
or a subgraph, which looks the same on the surface:
but contains a graph within itself (ad infinitum):
Graphene makes the opinionated decision that the latter is preferable, and removes nodes. To understand why, consider the two uses for nodes in Antimony:
 To contain larger chunks of code, e.g. with intermediate results
 To encapsulate multiple inputs and outputs
Since Scheme is an expressionoriented language, individual datums can define helper functions, intermediate values, etc. This answers our first use case for nodes.
With the first reason for nodes eliminated, the second isn't strong enough to justify them: subgraphs do just as well at encapsulating multiple inputs and outputs.
Hence, the canonical way to make the circle node in Graphene is as a subgraph:
Download
Source for Graphene is available on Github.
It is released under the GPL (version 2 or later).