stree2()

jbr 2023

The stree (s is for "summary" or "simpatico") allows you to express many related sequences with ease. If we associate each branch with a row then all we need is a way to make new rows. And once we have our rows, we need a way to select old ones. The convention I have selected is to reserve number typed input to do both tasks.

Negative integers select rows. Subsequent input is added here.
Positive integers select nodes. A new row is formed, parented to the numbered node.

// import {assertEquals} from "/core.js";
// import {stree} from '/stree2.js';

const ops = [
    'he',
  0, 'y',
  0, 're',
  2, 'tic',
  0, 'rmit',
];

const concat = (a, b) => a + b;
const push = (arr, elt) => [...arr, elt];

let s = stree(ops, concat, '' , push, []);
const expected = ['he', 'hey', 'here', 'heretic', 'hermit'];
assertEquals(expected, s.residues);

// compute the same answer a different way
const strings = s.branches().map(arr => arr.slice(0).reduce(concat,''));
assertEquals(expected, strings);

The reduction is over the list of nodes in order from root, which you can find easily from any node by walking up the parent. The major interface is a (growing) list of branches, represented simply by the nodes with no children.

While I do have an implementation written precisely in that way, but I'll be using another implementation. This one anticipates long runs of input targeted at a single row, so instead of wrapping each input in a new object, simply puts the input in the array. It also corresponds to the visualization.

Interestingly, the basics of this data-structure has little to do with combine. I feel that combine's utility (which I think is high) is multiplied by the stree. In part that's because it harnesses one of the computers great superpowers, the ability to perfectly copy complex structure effortlessly. If you have a simple, general, usefully constrained way to represent program state, it makes sense to apply an stree to that in particular.

function testTreeInternals() {
  // Lets experiment with adding integers to the operations list, forming a trie
  const o = {};
  const a1={a:1},a2={a:2},a3={a:3},a4={a:4},a5={a:5},a6={a:6};
  const ops2 = [
    o, a1, a2,
    0, a3, a4,
    2, a5,
    -1, a6
  ];
  // we only care about structure, not reductions, so set a noop
  function noop (){};
  const {nodes, rows, branches}  = stree(ops2, noop, '', noop, '');

  assertEquals([o, a1, a2, a3, a4, a5, a6], nodes);
  assertEquals([
    [o, a1, a2],
    [0, a3, a4, a6],
    [2, a5]
  ], rows);
  assertEquals([
    [o, a1, a2],
    [o, a3, a4, a6],
    [o, a1, a2, a5]
  ], branches());
}
testTreeInternals();

STree and Combine

Let's make sure that combine works within the stree, using some simple, synthetic handlers.

import {assertHandler, logHandler} from "/handlers.js";
const incHandler = {handle: () => [{a: 1}], call:()=>({handler: 'inc'})};
const decHandler = {handle: () => [{a: -1}], call:()=>({handler: 'dec'})};
const mulHandler = {handle: (core, msg) => [{a : null},{a: msg.factor * core.a}], call: a => ({handler: 'mul', factor: a})};

// These are convenience methods for authoring; we're still just adding objects together.
const has = assertHandler.call, loggy = logHandler.call;
const inc = incHandler.call, dec = decHandler.call, mul = mulHandler.call;
const ops = [
  assertHandler.install(),
  logHandler.install(), has({debug: true, lastOutput: ''}),
  {handlers:{inc: incHandler, dec: decHandler, mul: mulHandler}},
  {a: 10},has({a: 10}),
  inc(),  has({a: 11}),
  dec(),  has({a: 10}),
  dec(),  has({a: 9}),
  mul(5), has({a: 45}),
  loggy('okay, lets backtack and start from an earlier node.'),
  5,      has({a: 10}),
  mul(2), has({a: 20}),
  inc(),  has({a: 21}),
  loggy('now lets backtrack to node 10 and '),
  10,     has({a: 9}),
  mul(20),has({a: 180}),
]
window.s = stree(ops);

Canonical ops

At the end of the day all the elements in this array are either objects or integers. This example is equivalent to the previous one, but now we show the JSON representation of the ops.

import {stringifyWithFunctions} from '/core.js';
const ops = [...etc];
const ops2 = stringifyWithFunctions(ops, "[long function string]");

ops2 looks like this:

[
    {
        "handlers": {
            "assert": {
                "name": "assert",
                "install": "function(){return {handlers: {assert: this}}}",
                "call": "a => ({handler: 'assert', ...a})",
                "handle": "[long function string]"
            }
        }
    },
    {
        "handlers": {
            "log": {
                "name": "log",
                "install": "[long function string]",
                "call": "[long function string]",
                "handle": "[long function string]"
            }
        },
        "debug": true,
        "lastOutput": ""
    },
    {
        "handler": "assert",
        "debug": true,
        "lastOutput": ""
    },
    {
        "handlers": {
            "inc": {
                "handle": "() => [{a: 1}]",
                "call": "()=>({handler: 'inc'})"
            },
            "dec": {
                "handle": "() => [{a: -1}]",
                "call": "()=>({handler: 'dec'})"
            },
            "mul": {
                "handle": "(core, msg) => [{a : null},{a: msg.factor * core.a}]",
                "call": "a => ({handler: 'mul', factor: a})"
            }
        }
    },
    {
        "a": 10
    },
    {
        "handler": "assert",
        "a": 10
    },
    {
        "handler": "inc"
    },
    {
        "handler": "assert",
        "a": 11
    },
    {
        "handler": "dec"
    },
    {
        "handler": "assert",
        "a": 10
    },
    {
        "handler": "dec"
    },
    {
        "handler": "assert",
        "a": 9
    },
    {
        "handler": "mul",
        "factor": 5
    },
    {
        "handler": "assert",
        "a": 45
    },
    {
        "handler": "log",
        "msg": "okay, lets backtack and start from an earlier node."
    },
    5,
    {
        "handler": "assert",
        "a": 10
    },
    {
        "handler": "mul",
        "factor": 2
    },
    {
        "handler": "assert",
        "a": 20
    },
    {
        "handler": "inc"
    },
    {
        "handler": "assert",
        "a": 21
    },
    {
        "handler": "log",
        "msg": "now lets backtrack to node 10 and "
    },
    10,
    {
        "handler": "assert",
        "a": 9
    },
    {
        "handler": "mul",
        "factor": 20
    },
    {
        "handler": "assert",
        "a": 180
    }
]

Simpatico OOP

Building out an example of classic OOP types and instantiation with Simpatico. Rows are simply designated a type with a label. We introduce some conventions that constrain the structure of the tree. The first rows are types, consisting only of handlers. The latter rows are instances, consisting only of messages.

import {assertHandler, logHandler} from "/handlers.js";
const DEBUG = false;

const h1 = {handle: (core, msg) => [{a:1}], call: {handler: 'h1'}};
const h2 = {handle: (core, msg) => [{a:2}], call: {handler: 'h2'}};
const [a, b] = [h1.call, h2.call];

const has = assertHandler.call, loggy = logHandler.call;
const ops = [
  assertHandler.install(),
  logHandler.install(),
  {handlers: {h1, h2}, debug: DEBUG},
  {a:0}, loggy('this is node 4'), has({a:0}), a, b,                  has({a:3}),
  3 , loggy('row 1 parent 3'),    has({a:0}), b, b,                  has({a:4}),
  3 , loggy('row 2 parent 3'),    has({a:0}), b, b, a, b, b, a, a,   has({a:11}),
  11, loggy('row 3 parent 11'),   has({a:2}), a, a,                  has({a:4}),
];
const s = stree(ops);

// We can keep adding to the stree
const moreOps = [{debug: true}, a, a, b, b, log('hello from moreOps, still row 3')];
s.addAll(moreOps);
s.add({a: null});
s.add(has({a:0}));
assertEquals(3, s.currRowIndex);

window.s = s;