What is cool about the ChronoGraph? Part #2 - Unlimited stack depth

In the previous post we started looking at the unique features of ChronoGraph, which are not available in other reactive systems of the same class.

This post is about the next such feature - unlimited stack depth.

What is "reactive" stack depth?

We all know what stack depth is for regular synchronous function calls. It is how deeply function calls can be "nested" into the current one.

You can determine the stack depth of you JS engine with the following snippet:

let depth = 0 
function deep () { 
    depth++
    try {
        deep()
    } catch (e) { 
        console.log(depth) 
    }
}
deep()

For v8 and Firefox engines it is about 10000.

For reactive systems, the stack depth is - how deep a dependency chain of some atom can be.

For example, lets say we have a reactive box with value 0, lets call it box0. Then we create a new computed box, box1, which adds 1 to box0. Then, box2 adds 1 to box1, etc.

The maximum length of such dependency chain determines the "reactive" stack depth.

The "reactive" stack depth is naturally limited by the "synchronous" stack depth - every calculation of box is modeled with the function call. Reactive system also adds some intermediate calls, so in practice the "reactive" stack depth is ~1300 for ChronoGraph1 and ~1500 for Mobx.

The problem

For some applications, the reactive stack depth of ~1300 might not be enough.

For example, ChronoGraph is powering the business logic of the Bryntum Gantt. In the Gantt chart, tasks are scheduled by "dependency relations", like "task B starts when task A ends, task C starts when task B ends". Such relations may form arbitrary long chains.

Since scheduling the task's start date also uses some intermediate atoms, the maximum effective length of the chain of connected tasks becomes 300-400, which is not enough (some clients are requesting the maximum length of 1000-1500).

When using regular synchronous calculations, the stack depth becomes a hard limit, which can not be worked around.

The solution

Thankfully, ChronoGraph supports generator-based calculations, and for such calculations, this limit does not apply.

The "reactive" stack depth for generator-based ChronoGraph's calculation is limited by the available memory and not the synchronous stack depth. This is possible because generators can be seen as a form of delimited continuations which allows to do magical things with stack.

Codewise it looks like this:

import { ChronoGraph, ChronoIterator } from "../../src/chrono/Graph.js"
import { CalculatedValueGen, Identifier } from "../../src/chrono/Identifier.js"

const graph = ChronoGraph.new()

const boxes : Identifier[] = [ graph.variable(0) ]

const anyStackDepth = 100000

for (let i = 0; i < anyStackDepth; i++) {
    const nextBox = CalculatedValueGen.new({
        *calculation  () : ChronoIterator<number> {
            const prev : number = yield boxes[ this - 1 ]
            return prev + 1
        },
        context : boxes.length
    })

    graph.addIdentifier(nextBox)

    boxes.push(nextBox)
}

const lastBox = boxes[ boxes.length - 1 ]

console.log(graph.read(lastBox)) 

Which outputs 100000 !!

Conclusion

As demonstrated, ChronoGraph provides support for generator-based computations, for which the regular stack depth limitations do not apply.

This is a novel and unique property, not available in other reactive state management systems. It enables the real-world use case of computing the very long dependencies chain in the Gantt chart schedule.

P.S. This week chronograph is medieval clock from Venice, Italy. Photo by Bill Smith