Hello,
The last couple of days I’ve been thinking about our bytecode instruction set.
TP3’s bytecode was introduced a bit late into TP3’s development and ultimately
became (nearly) in 1-to-1 correspondence with the Gremlin traversal steps. We
don’t want to do this for TP4. We want to limit the instruction set to only
those that are necessary to express universal computation. The benefits are:
1. Less testing — less instructions to consider.
2. Less degrees of freedom — an orthogonal set of instructions makes it
so there is only one way to do things.
3. Easier for language/processor providers — less stuff to consider.
4. Decoupled from Gremlin — we don’t want Gremlin to be intertwined
with the TP4 virtual machine in any way.
So, without further ado, here are my thoughts on branch.
1. Branch Instructions
We only need one branch instruction to represent choose, coalesce, optional,
union, and ?repeat?.
The branch instruction is generally defined as [see: page 19/section E of
https://zenodo.org/record/2565243 <https://zenodo.org/record/2565243>]:
[branch, branch_1_predicate, branch_1_flatmap, branch_2_predicate,
branch_2_flatmap, …]
branch_x_predicate => take branch x?
branch_x_flatmap => branch x.
This is basically generalized if/else.
if x_predicate . x
if y_predicate . y
…
I will use faux Gremlin-syntax to make it easier to read than writing out
instructions.
——————
choose(name).
option(marko,out).
option(josh,in).
option(peter,both) // generalized choose() in TP3
branch().
option(name. <http://name.is/>eq(marko),out).
option(name.eq(josh),in).
option(name.eq(peter),both)
——————
choose(age.gt(20), out) // if-then choose() in TP3
branch()
option(age.gt(20),out)
——————
choose(age.gt(20), out, in) // if-then-else choose() in TP3
branch()
option(age.gt(20), out)
option(not(age.gt(20)), in)
——————
coalesce(out,in,both)
branch().
option(out,out).
option(not(out),
branch().
option(in,in).
option(not(in),
branch().
option(both,both))
——————
optional(out)
branch()
option(out,out)
option(not(out),identity)
——————
union(out,in,both)
branch().
option(identity,out).
option(identity,in).
option(identity,both)
——————
I don’t know how to elegantly merge repeat() into branch(). The best
representation I have is an exponent-based representation that recurses similar
to coalesce(). I don’t like it as it puts too much work on the compiler. I
believe repeat() might just have to be a “special” branch instruction. ??
repeat(out).times(10)
branch()
option(loops.eq(10), identity).
option(not(loops.eq(10)), out.branch().
option(loops.eq(10), identity)
option(not(loops.eq(10)), out.branch().
...
When considering emit(), you need another option that acts like a union(). It
gets ugly fast.
——————
Now that we have one instruction for all our branching needs, Beam and Pipes
only need to know how to deal with a branch instruction and not also a union,
coalesce, optional, choose, etc. instruction. As you can see, this means much
less work for the processor vendors!
https://github.com/apache/tinkerpop/blob/tp4/java/machine/processor/beam/src/main/java/org/apache/tinkerpop/machine/processor/beam/util/TopologyUtil.java#L109-L126
<https://github.com/apache/tinkerpop/blob/tp4/java/machine/processor/beam/src/main/java/org/apache/tinkerpop/machine/processor/beam/util/TopologyUtil.java#L109-L126>
https://github.com/apache/tinkerpop/blob/tp4/java/machine/processor/pipes/src/main/java/org/apache/tinkerpop/machine/processor/pipes/Pipes.java#L59-L60
<https://github.com/apache/tinkerpop/blob/tp4/java/machine/processor/pipes/src/main/java/org/apache/tinkerpop/machine/processor/pipes/Pipes.java#L59-L60>
If anyone has a better branch representation, please share. One thing I’m
considering:
not(…) -> Pick.none which is in TP3 and is like default in a switch
statement.
Thanks,
Marko.
http://rredux.com <http://rredux.com/>
