Here, I want to study through coding experiments the duality between Observer and Enumerator discovered by Erik Meijer [1].
I am following [1, 2] and the implementation is based on a rewriting in Typescript of this code snippet. Pseudocode in Meijer's talks was also useful to clarify some aspects.
Warning. At the moment I am not sure about the underlying theory and I could use math terms in an improper way. I would like to develop the details more formally, but I am now more interested in building something that runs.
- Web architectures as categorical traces. Since some particular categories with dual objects have a trace, it is possible to build one in a reactive framework based on the duality Observer/Enumerator. I think that trace is a fundamental structure underlying modern UI architectures for the Web such as CycleJS and React+Redux.
- Transparent reactivity. Transparent reactivity (proposed and pioneered by Meteor framework [5]) is a sort of "functor". Roughly speaking, it allows us to write reactive code in a more familiar interactive style without callbacks or streams. In practice Meteor
Tracker.autoruntransforms a function overEnumerables (in Meteor reactive data sources or dependent functions are a kind of enumerable data structure) into a function overObservables that is rerun by the underlying framework every time inputs change, automagically. - Composition. Meijer claims that "reactive" is all about composing side effects. I defined some HOCs for building complex interactions between side effects.
Current limitations:
- Unfortunately, it is not possible to check types at run time since Typescript compiles into Javascript. For this reason, I am using custom type guards (see trace and par API) in order to split union of types. Moreover, union type in Typescript is not a variant type, I still do not know if this could be a source of trouble. So far it is ok, but API could change in the future, if I come up with a better solution.
- Function types are not contra-variant in Typescript. Composition is not always type safe. Perhaps I can fix that with some constraints on generics.
- I am overlooking performance issues. I feel I can optimize the code reducing the number of "forks" I make (i.e. how many times annihilate is called) and the number of shared queues.
- Threads are fake.
- Subscriptions are not disposed properly.
- API are unstable. Take this project as an experiment, it is not a library.
A list of things I would like to explore is here.
In test there are some examples of usage. In order to run tests:
$ npm install
$ npm run test
A simple example of a cyclejs-like app. Full code is in test/traceTest.ts.
This code is based on the first example in CycleJS tutorial.
// the main application takes two observables of types Time and HtmlDom.
// Time observable returns a tick signal every 1 ms while dom observable is a representation of the dom
const main = (input: Observable<Init|HtmlDom|Time>): Observable<HtmlDom|void> => {
const [ clock ] = split<Time, HtmlDom>(input, isTimeEvent);
const [ subject, output ] = makeSubject<HtmlDom|void>();
// listen to clock ticks
clock.subscribe({
onNext: ({tick}: Time) => {
// update the dom on each tick
subject.onNext({tagName: 'h1', value: `${tick} ms elapsed`});
}
});
// return the dom driver stream
return output;
}
// just an helper function
const id = (x: Observable<Init>) => x;
// Observable<Time> and Observable<HtmlDom> are generated by two "drivers": clock and dom.
const drivers = par(id, par<HtmlDom,void,HtmlDom,Time>(dom, clock, isDomEvent), isInitEvent);
const app = seq(drivers, main);
const run = trace<Init, HtmlDom, void>(app, isVoid);Graphically, it looks like:
+------------------------+
| +-----+ |
| |clock+----+ |
| +-----+ | |
| +-----+ | +-----+ |
+-|dom +--- +--+main +--+
+-----+ | +-----+
+------------+
This project is pretty much reinventing the wheel and could not have been started without ideas and code from several sources.
Observable/Enumerable duality was discovered and made popular by Erik Meijer [1]. I followed the categorical construction defined in [2]. My implementation is strongly influenced by Meijer's lively talks and, basically, is a rewriting in Typescript of this code.
Rummelhoff observed in [2] that the Meijer category is symmetric and monoidal; the latter is not said explicitly, but it should follow from his definition of the tensor product. The fact that symmetric monoidal categories with dual objects have a trace is well-known [3, 4]. I built the trace following the diagrams you can find on Wikipedia.
The new trend of functional/unidirectional architectures (e.g. React+Redux and CycleJS) helped me a lot to connect the dots I was chasing. In particular, CycleJS implementation guided me for building the trace. I am not deeply into CycleJS as I would like to, but I am strongly influenced and motivated by this framework. There are strong analogies with what I am attempting here.
CycleJS is compositional (André Staltz, CycleJS creator, says "fractal"). Here, I want to explore a slightly different (?) alternative where composition is defined by higher order components (i.e. seq, par, trace). In particular, my source of inspiration is [6] where it is defined a symmetric monoidal structure for parallel asynchronous composition (very similar to what I would like to do here), a trace operator and a duality player/opponent instead of observer/enumerator. Moreover, symmetric monoidal categories are a quite natural structure to model circuits (see, for example, John Baez's blog). I have already attempted to apply [6] to web programming few years ago.
The application of dataflow-like languages to UI design or, more in general, to signal processing is not a new idea at all. Functional Reactive Programming (FRP) should have many examples. I have not seen Elm yet, but it should share several ideas with FRP, dataflows, CycleJS. A nice paper on signal processing is also [7]. The language syntax and semantics remember a symmetric monoidal category, but the framework is not reactive nor asynchronous and it is highly specific to a particular domain. [7], as well as other algebraic languages, has a similar set of operators/rules (e.g. seq, par, trace/feedback and others) which are the essence of the monoidal structure defined in [6].
This is a personal side project that I am carrying out just for fun and curiosity.
Although the intended audience is mainly myself, I try to be as much accurate as possible. However, it is often difficult to find time and energies for polishing and reviewing what I do. I thank you in advance if you are so generous to point out anything missing or wrong.
I am not an expert in CT and I do not have any experience with Rx or similar frameworks. Hence, take everything with a grain of salt.
[1] Erik Meijer, Subject/Observer is Dual to Iterator, FIT: Fun Ideas and Thoughts at PLDI, 2010
[2] Ivar Rummelhoff, Duality Formalized?, 2011
[3] Wikipedia Symmetric Monoidal Category
[4] Wikipedia Compact Closed Category
[5] Sashko Stubailo, Beating event emitters and Promises with Tracker, Devshop SF Feb 2015
[6] Samson Abramsky, Retracing some paths in Process Algebra, International Conference on Concurrency Theory, 1996
[7] Yann Orlarey and Dominique Fober and Stephane Letz, Syntactical and semantical aspects of Faust, Softcomputing, 2004
Ascii diagrams generated with asciflow.