Concatenative Event Streams and Reactive Programming

Ideas
1

The term “Functional-Reactive Programming” as a concept of computation is thrown around a lot today, and a bit like with Object-Oriented Programming, every person with an implementation of it seems to have their own definition.

Wikipedia: Functional reactive programming - Wikipedia

Basically, the idea is that everything in a software system (an application inside a web browser, usually, but if it’s a valid model of computation then theoretically it could be an entire application, OS, or network of computers) is a “pure function from input to output”. Pure functional languages usually struggle with I/O, because it involves change. The various approaches loosely described as “FRP” try to remove this element of change by pushing the change itself into a “framework”, while the components which handle this change remain “pure”.

It’s easy to glimpse the loose spirit of FRP by looking at a graphical window. There’s a bunch of components. Events come in (mouse clicks, keyboard presses, updates from the data source). Events go out (screen rewrites, changes of state of the components, changes to the data source). Naively, you’d think “this window is basically just a big function from a bunch of input events to a bunch of output events; why can’t I just write it as a function? A big pipe of data go in, data come out? Wouldn’t that be simpler than all this object stuff of setup and teardown, callbacks and promises, invocation ceremonies, component registries, mockups and tests and such?”

An even more naive, blurry, look at a window would make you think further “well this window is literally just a view of some data. A view is a function. Why can’t this window just be… a function call?”

Someone coming from the command-line world, especially Unix (or Powershell on Windows) might also think “All my text commands are pipes. Why isn’t my window a pipe?” And especially if they’ve used Tcl/Tk, they might ask “there’s a scripting language where windows literally are pipes, why is the whole world not like this?”

And presumably some of this thinking seeped into the huge Internet companies writing Web frontends, and became things like React, Reduct, Vue etc.

I’ve been watching the FRP scene from a distance for the last 20 years or so, and remain confused about how exactly the core paradigm is supposed to work. My feeling is that while the edges can be as complicated as you like, the core mechanism of “how computation happens” ought to be fairly simple and graspable. In Lisp, it’s “lists are rewritten into other lists”. In Forth, it’s “words put stuff on the stack”. In Smalltalk, it’s “objects send method selectors and arguments to objects and get replies”. In Fortran, Algol and all the little Algol children, it’s “I do this then I do that, then I go somewhere else and do what it says there”. 28 years after it was first introduced, FRP remains … not quite that clear. Something updates, or changes, or doesn’t change, or gets “reduced” or doesn’t, but what, and how?

One idea that was buzzing in my head around 20 years ago - under the influence of Joy and Factor at the time, and the revival of Forth - was this:

“FRP systems are really event-based programming. A program then looks pretty much like a pure function of a stream of input events, to a stream of output events. A graph of components, yes, but essentially a tree starting from the machine input. Each component in that graph/tree then could be expressed as a function which takes an input event, and replaces it with (zero, one or many) output events, and also an updated function to catch the next input event in the stream”.

I felt like this concept ought to be pretty simple and easy to grasp. Maybe too simple - it probably handwaves away all of the important detail. But I wanted to see it implemented.

I never did end up implementing it. Maybe it’s time to try.

20 years ago, I imagined the language and the evaluator as being a prefix-concatenative language, which are super rare, and haven’t been worked on in the years since. It seemed important at the time as a way of capturing the intuition that a software system might be able to represented just as an event stream with functions inside it, with functions plus arguments rewriting themselves to “output plus next version of function”. But a postfix language would probably have a simpler evaluator and might still be able to capture some of the essence of the idea.

Essentially, functions (or Joy-like combinators, or Forth-like words) would be coroutines: they could produce one value, then yield control to the next function up the pipe, then if reactivated, would recurse on themselves (updating some state, just like a “fold” or “reduce” function). I assume that this is essentially how modern web FRP frameworks like React work, since they use the term “reduce”. But React is a library over the whole object-based complexity of Javascript, the DOM and the browser. This would be something much simpler.

I feel like this must have been explored, and yet I don’t see where it has been explored.

I now have a vague sketch in my head of a modified two-stack postfix machine that feels like it ought to be able to naturally do coroutines over infinite streams of events. It would use a layered stack and a “yield” opcode so that calling between coroutines could be fairly efficient and also safe. I hope. I’ll try to build it to demonstrate what I mean. Whether this approach could actually help in reducing event-processing complexity, I’m not sure.

Edit: It turns out that the Wikipedia article on “Reactive Programming” is much more useful than the article on “Functional Reactive Programming”. I guess FRP lost its F in the last few years?

2

I’m not at all sure that the two-stack concatenative coroutine machine is enough for doing concatenative streams. But the idea so far is:

We have the usual Work and Return stacks. We augment each of these with either a type tag or a second stack, such that each of the Work and Return stacks can store either a data item or a code address. (Data items can be addresses of code, but by “code address” I mean particularly an address which represents code-being-executed). Normally, the Return stack stores code addresses (of the next program counter after a Call opcode) and the Work stack stores data items. But the Return stack can also store temporary data items (which is normal in Forthlike stack machines)… and the Work stack can also store temporary code address (which is not normal). A code address on the Work stack represents a paused coroutine. We get a paused coroutine by using the “yield” opcode, which leaves the top data item on the top of the Work stack, but puts the code address of a resume address under it. A code address on either stack acts as a stack floor, preventing normal access to data items under it, except using the Call/Return and Yield/Resume mechanisms.

When an opcode executes that hits a Work stack underflow condition (ie if there’s a code address on the Work stack and not enough data items above it) then the program counter goes on the Return stack, and the code address on the Work stack is Resumed to generate more data .

(There’d be a little bit more complexity for the Yield and Resume states: we’d probably want to move any data items on the Return stack to the Work stack on Yield, and any data items on the Work stack to the Return stack on Resume.)

If the Data stack is ever actually empty, then a system “input” opcode executes that waits for input, or reads from a buffer, and puts one data item on the stack. Similarly, if the return stack ever is empty, a system output opcode emits one data item from the Data stack (resuming any yielded continuations needed to do that).

I would also pair this with some form cons memory and a garbage collector, so no raw RAM access.

These primitives might not be all that’s needed - we might also need to manipulate a yielded coroutine in some ways - but hopefully what this might give us is a stack machine that’s strict about memory and stack safety (data items can’t be accidentally or maliciously executed) but flexible enough to handle realtime streams of events without separate I/O instructions.

3

Thanks, lots of interesting thoughts here.

This was a distinction I was trying to get at in my post at The Data-First movement - #7 by Bosmon but I realise I tend to write posts that are far too long with too many different points in them so I should try to condense!

  • “Reactive programming” is an older, more fundamental and at the same time more diffuse discipline than FRP and has somewhat been eclipsed by the discussion bubble around the latter
  • The cornerstone of FRP was originally the elegant type system around continuous time behaviours, but this has more recently been muddied by various kinds of discrete-time FRP which I think should properly be considered varieties of regular RP
  • On the one hand whilst it is fun I don’t consider the continuous time formulation adds something of primary value to typical end-user programs, and on the other hand distracts from issues which I see as crucial, such as the potential for glitches:
  • Note that the RP article has a substantial section on glitches whereas the FRP one has none. A competent implementor of an FRP system (as suggested in the in the 2012 Bainomugisha et al Survey on Reactive Programming) will tend to make sure that their system is glitch-free but interestingly will not talk much about this.

To me, the discipline of malleable systems is about making intelligible, visible systems with tractable and stable behaviour, with as few as possible hidden abstractions (sources of “divergence”). So whilst I appreciate the elegance of stack-based concatenative languages, I tend to worry that there might be a requirement for the user of the system to think too much about what is “on the stack” without it necessarily being a relevant part of the visibly executing system - what do you think about this?