Hi, can everybody hear me?
Yes.
Okay, great.
Hi, everybody.
My name is Dave Thompson.
I am the CTO at the Sprite Institute.
And today, we're talking about functional reactive programming with propagators.
Words you may or may not understand.
Don't worry.
I will explain them.
But quickly, about Sprite Lee, Christine already explained, but working on the next generation
of you centralized technology.
So I probably won't belabor the point since Christine was just here.
So let's get right into it.
Before we get to the functional aspect, let's just talk about reactive programming.
Who knows what knows what it is or has used a library for active programming.
Okay.
Little over half of the room I'd say.
Okay.
For those that don't know, the way I like to describe it is it's a way to work with time varying values
without entering callback health.
So without having to do like procedural event driven continuation passing style programming.
So it's usually as a declarative abstraction.
Sorry, abstraction on top of an event loop.
So like in the web browser, you know, you have events for keyboard input, mouse input, etc.
Rather than writing event callbacks, you have some declarative ways to do this.
Graphical user interfaces are kind of where this type of programming seems to be used the most.
And probably if I say the word react.
Does everyone know what react is?
Show of hands.
Okay, basically.
Okay, yeah.
So react really means streamed.
Reactive programming for like the web development community at large.
So here's an example.
Probably the simplest example from the react documentation.
It's just a button.
And then every time you click it, the click increments.
So this is reactive, but it's not functional.
So I want to talk about the functional side.
At it's simplest, we just take reactive programming and then we use more peer functions.
And we have function active programming.
However, it's really hard to define FRP without probably making somebody mad.
Because it's not a super well-defined term.
And there's no way we can do that.
It's really hard to define FRP without probably making somebody mad.
Because it's not a super well-defined term.
And there seems to be contention about what it really means.
There's many forms.
There's a continuous FRP, discrete FRP, push-based pull-based hybrid push-pull-based.
But for this talk, I'm just going to say that discrete push-based FRP seems to be the most practical thing for dealing with things like just the event loops that we're typically used to.
So I'm going to go with that.
And this is not a new idea.
This is a paper from ICFP in 1997 called Functional Reactive Animation.
And I believe this is the origin of the term Functional Reactive programming.
This was implemented in Haskell way back when.
And I believe the authors of this paper would probably be mad about the definition of FRP that I just told you.
So hopefully they're not ever going to see this.
Unlike React, which is immensely popular, FRP has not had the same success of React likes.
And I like to think of this blog post from the L language.
If anyone's familiar with L, it was like a Haskell like that ran in the compiled JavaScript ran.
But I was still around.
But I had a big moment in the early-to-mid, you know, 2010s.
And it went all in on FRP at the beginning.
And then in 2016, they wrote this, the creator Evan wrote a farewell to FRP.
And I kind of like to, to me, this is kind of like the death now of of FRP as like an idea that was gaining like.
It was gathering steam and then it kind of, I feel like a kind of died here.
But I, this FRP bug has been in my brain for longer than this and it's never really left.
I keep being interested in it.
And so never mind all that stuff, you know, maybe all these projects tried and failed.
Let's, let's look at this with scheme.
So here's a really wonderful, amazing demo.
It was very complicated.
And you see it's the same thing as in the React code that I showed you.
Little button, I click in an increments. Oh, great.
Well, that's amazing. Okay, talk over.
What I'm going to show is, I'll show you some scheme code.
So don't worry too much about understanding this, but I want to show that it's declarative and functional.
In the sense that we, you're not going to see a set bang here or any kind of mutation.
We, we have this, I'm calling themselves a, they hold time-bearing values.
This one's going to hold click notifications.
Concepts that we're used to in functional programming are like doing operations on list, map pretty well.
So we're going to fold and it's a fold not over a list, but over time.
We're going to take in the click cell.
We're going to have an initial value of zero because the initially the user hasn't clicked the button at all.
And every time an event comes in, we're going to modify that kind of, we're going to increment it.
And then good thing Christine was just talking about SXML.
This is the next SXML template.
And what we do is we have an on-click handler here.
And we got this on-quote thing.
We turn this click cell.
We make a listener for it.
So every time a click event comes in, we update our little FRP cell.
And then we splat in the count.
And so this refers to the value of the cell.
The engine behind all of this just ensures that the UI is updated.
And so this presentation that I've been showing you is running the web browser is running a scheme program.
This is the source code for the slide you just saw.
So this is a web assembly program that is a scheme program called the web assembly running these slides.
So this is the actual code of the demo I just showed you.
So we'll go back to the presentation.
I think I have to click off of here.
Okay.
So I can't talk about FRP without talking about glitches.
I can't really talk about reactive programming general without talking about glitches.
The most important job of any reactive library or framework is to avoid glitches.
And a glitch is usually a brief small, like tiny moment of time, where a time varying value gets computed with a mix of scale and fresh data.
And it becomes often becomes user visible and it's like a flash of something weird.
And it comes in it goes, but it leads to like a janky user experience.
And we don't want this.
So I'm going to try to walk through this little thing.
I can explain glitches with just a graph of four nodes.
So right here, it's just a very simple data flow graph.
A is the root.
Numbers enter here.
I'm just going to be working with integers.
And so it gets any time A changes.
We take A times two.
We put it in B.
Take A plus one.
Put it in C.
And then D depends on both B and C and we just take the difference.
And so at the start, the cells contain nothing.
We have to bootstrap our graph.
So somehow we insert the number two and that kicks off reactivity.
So it flows to B.
And we double it.
So we get four.
We add one.
We get three.
And then finally we take the difference and we get one.
Great.
All looks well.
However, let's take another another approach to it.
Another data flow path.
So we come in at the root again bootstrap.
We update this value to three.
We propagate to to node B.
We double it.
We get six.
But instead of going to node C, we go to node D.
Node D depends on B and C.
So we take the difference and we get three.
But that's wrong.
Because the value here is three.
So what we really want is the value two.
But because this cell refreshed before this one, we have a glitch.
And so eventually, after two more steps, converges to the correct value.
But we have a moment that's probably going to annoy a user somewhere in the interface where the value is wrong.
So this is no good.
How do we avoid glitches?
Reactive libraries typically do something like a topological sort.
So D is below nodes B and C in the graph.
So B and C should be refreshed first and then D.
And then we ensure that D is always computed with fresh values.
But we have a restriction.
Once we add that property.
The node graph must be a cyclic.
And only, and therefore as a consequence,
only a subset of possible interfaces that we can implement with event callbacks are now expressable with reactive programming or functional reactive programming.
So it turns out.
We will be able to remove this restriction.
But I want to show an example.
So this is a color picker diagram.
Here we have the RGB values for representing color that way.
And then on the other side we have a hue saturation value.
Sliders.
And what we would like to have happen is any time you manipulate one of these sliders.
The sliders over here change.
So we convert RGB to HSV and update the sliders accordingly.
And when you change any of the HSV values.
We convert HSV to RGB and update these.
So there's circularity there.
Like you see in the middle.
And so we can't express that with acyclic reactivity.
But acyclic reactivity is the norm.
And it's what is popular.
And it seems like what's going to continue to be used in the industry at large.
This is a screenshot of a TC39 proposal.
The standards group responsible for changes to JavaScript.
They're working on something called signals.
And it's a proposal for one way data flow in JavaScript.
And it's going to be a reactive libraries in JavaScript to bring an API to JavaScript itself.
But so that's the state of the art there.
But I wouldn't be up here if I thought cyclic reactivity was impossible.
It's very possible.
And the secret ingredient is propagators.
Has anyone heard of propagators?
Okay.
Much smaller group of people than new about reactivity in general.
So I want to introduce you to one of my favorite PhD dissertations, which I feel is a weird thing to say.
Because who has a list of their favorite ones.
Normally they're so dense they're hard to read.
I got to trust me on this.
This one isn't.
This is by Alexei Raduel, who was a PhD student MIT.
This is from 2009.
Propagation networks, a flexible and expressive substrate for computation.
It is a fantastic read.
I'm going to cover just a little tiny bit of that paper that talks about FRP.
And no more, but I really recommend if any of this peaks your interest.
Go there.
Everything I'm about to tell you is derived from it.
So what the hell are propagators?
This is a lot of text.
I'll just read the bold part.
There are autonomous independent machines interconnected by shared cells through which they communicate.
And this is straight out of Gerald Susman's and I'm forgetting the co-author right now.
But software design for flexibility from 2021.
If you liked SICP and you want something similar to it that's not from the 80s with additional more advanced topics,
check that book out MIT press.
Okay.
So in real simple terms, cells are nodes.
But notably they contain partial information.
This is Alexa Redwell's key insight in his dissertation.
You can including partial information being nothing.
So there's initially a cell contains nothing and over time it accumulates information.
And this can get particularly complicated.
A lot of propagator, lore and research goes into AI systems and like truth, maintenance systems and stuff.
I'm going to talk about something much simpler.
You can get pretty crazy.
And the propagators you can just think of as the edges.
They're the things that take values from some input cells.
Just some computation and then write them to one or more output cells.
But notably this relationship between cells can be one to one.
It can be one to what many.
It can be many to many.
There's no restriction on that.
And also there's no restriction on when propagators like fire and when they refresh themselves.
So propagator flow is dumb and it's dumb on purpose to meant to be very easy to implement.
And so propagator networks by definition, they have no order of evaluation and they have no directionality restrictions.
So if we want to build reactivity on propagators, we can't do topological sort.
So we have to do something else.
So we have a problem.
If we don't solve the problem, we're going to have glitches and we're going to have a terrible reactive system.
So as is often the case, there's a lot of things in computer science where you start with some kind of unordered system and you put order on top of it.
Well, propagators are no different.
I'll actually write a dual-explained that using an approach that really resembles logical timestamps in a distributed system.
If you're familiar with logical clocks, transport timestamps, vector clocks, very similar concept.
What we want to do is when we bootstrap our nodes, when data comes into it from the outside world somewhere, we want to make sure that each piece of data is tagged with some kind of unique identifier for each piece of data.
And then some kind of logical timestamp, that's increasing monotonically with each change.
And so as values accumulate and flow through the graph, you'll get many such pairs and these pairs form a vector clock.
And with that, you can tell if the data that you're about to use is fresh or not.
And so we can halt propagation when when a propagator fires and it discovers that its inputs have differing timestamps for the same identifier.
One says that the time was one when this value came in and the other was two.
That's conflicting. We have old and new mixed together. We should stop right there. We need to wait in order to actually do the transformation that we want to do so we halt.
And that enables circularity without infinite loops.
And so the trade-off here is that there is a bit of redundant computation because a propagator may fire when it can't actually do anything yet and it has to stop and it has to know that.
So versus topological sort, you kind of visit each node and you know it's ready to go.
But the total amount of redundant computation is actually quite minimal.
And so without any ordering guarantees, a much simpler substrate, much simpler infrastructure, we can still get the same properties that we want values that converge without glitches.
And so my definition of FRP on propagators is that it's the propagation of a femoral values. A femoral values are things that change over time.
And so in my prototype implementation there is a type of record type and scheme is just called a femoral.
It's a box that has any arbitrary value.
And then on the side it has a set of sources. It's the vector clock. It has all the information from once that value came, you know.
It's derived from these identifiers at these particular points in logical time.
And that is enough to get what we need.
I want to make a quick note. I mentioned this earlier, but it's not just I showed a fold earlier, but pretty much any list processing idiom translates really well to FRP.
You're just not mapping over a set of pairs. You're mapping over time.
So map, fold, filter. You get the idea. All these things, you know, map pretty naturally.
So as a functional programmer or a scheme programmer or a list programmer that's used to these things, I think you can get with it pretty quick.
So let's go back to the color picker. You know, I showed this graph earlier.
And I wouldn't show it if we couldn't do it.
And here it is. So this is running in the slide. This is actually code that's using propagators running in the hoot scheme interpreter, which has been compiled to web assembly and running in the browser here.
So you see as as I adjust the sliders in the RGB, the HSV side changes and we have the little color swatch up there to tell you what it is and the hex code if you want to copy it out in some other application.
And here I am changing Q saturation and value and the RGB sliders go.
So yeah, it works and don't just take my word for it.
I mean, I guess you have to also take my word that this is real code that runs and I didn't just do smoke and mirrors on you.
But this is kind of, I'm going to have a hard time with the resolution of this fitting it in a single page.
But just to show you, I've been working on some syntax that's not very good right now to define recursive graphs of notes.
And so here are the values that become our sliders. We have the RGB group and as RGB and then HSV group HSV one thing I haven't talked about is what the heck is this group.
Turns out that so RGB those are three facets of the same object like they they compose together to form an RGB expression of color.
And so what we want is that all three of these, they have the same identifier and they share the same timestamp counter.
So when you change any one of those you're changing this identifier that becomes the RGB group.
You know it starts at zero and change R goes to one you change B it goes to two they're linked together.
And that proves to be an essential part of making the propagation work so essentially facets of of a composite object that are at the root of your reactive graph.
You you generally you want to make sure that they are using the same logical time and they're kind of understood as like one machine in the system.
If that didn't make sense don't don't worry too much about it and then finally my kind of work in progress terrible notation for.
The edges in the graph if you've ever used the dot notation and graph is it's like a kind of a list be version of that, but I'm just saying that Rg and B those cells combine.
To write a value to the RGB cell and RGB color is a constructor for an RGB color record.
But it's bi-directional so when RGB changes we destructure the record and we put the RGB values in their corresponding cells the same thing applies to HSV just with the HSV record and it's it's accessors and then the the good stuff happens here it's just a this is a bi-directional expression of when HSV changes.
We convert it to RGB and we write it to the RGB cell when RGB changes we convert it to HSV and put it in the HSV cell.
So that's like the that's the that's the entire propagator network really and then all that's left to do is hook it up to a UI.
And let's see if I can get it all I can get it mostly on one screen.
The top it doesn't really matter we we have some procedures to convert an RGB color to a hex train.
I'm just like jet splatting out some gross CSS there for the color swatch and then again we have.
This is the slide that I just showed you this is the record type for these slides in the the slideshow system.
And another quasi quote and so another SXML template and then I have some helpers to do the sliders for me but notably.
There's Rgb I'm referring to these cells and the rendering engine will hook things up such that there it does all the callback stuff under the hood.
So there's a slider and the sliders have a value anytime the cell changes it'll it'll call it'll update the value of the dom node for that slider.
And anytime someone slides it that value will then get placed into the cell as an updated value and then the propagation starts.
So this is how values enter the propagation graph and the graph is bootstrapped.
But it's a two way binding so so if you're used to two way binding for many other web UI framework it's it's the same thing but just expressed in a in a different way.
So yeah, that's the basics of the of the code and I am close to done here.
I just wanted to show you that just so future work.
I cobbled this together pretty fast before for them I had done I wrote a blog post about this in 2024 and then I kind of just stopped doing anything with it and I kind of refreshed it for this talk.
And so I did a lot of re-implementation of things and it's kind of a mess but it works but it's not optimal there's a lot of places that are slow so to make this actually usable from scheme.
In real programs that are not just demos I'd like to optimize internal algorithms to make the propagation better and generate less garbage.
So we run the garbage collector less frequently which could lead to UI junk you know the be a bad experience with the GC's running all the time.
And I'd like to publish a library that works for both the guy virtual machine and also on the web for who I mean I mostly want to use this for web UI's.
And then I'd like to actually test drive it in some of the demos that we do it sprightly we've been wanting some kind of UI framework for a while and since we we use scheme.
As Christine was saying it's a great thing for doing all of our experimentation but on the other hand the flip side is that you end up rolling your own stuff a lot of the time.
So you know I don't I don't want to use reactive you or anything like that I want I want to use our scheme thing so I want to try it out there.
So that's really it you know I do all this with sprightly if you like what we do at all where if I want to see three my profit.
You know we can't do the work we do without help from from you all so please spread the Institute slash donate.
If you become a recurring donor we will shout you out on our on like every blog post we do I plug.
I check out our donations list and I thank everybody that's that's got monthly donations set up in there on our various tiers.
So anyway we greatly appreciate your support support I'm done thank you do we have time for questions.
Like clapping for myself over here I don't understand.
Okay let's see I'll start here.
The question was in my demo I have this arrow operator and what is that.
It's it's a syntax literal it's just used to separate the inputs from the outputs because the.
I just needed some notation to show that it's like values are flowing from the left to the right.
It's it's not no so I just wrote.
This is what needs development like we need I need an ergonomic like domain specific language for doing this and in the very little time I had.
I thought of just using what graph is does and you just do a little arrow.
Yeah yeah yep so it's I could show you the macro after it's kind of it's it's trash to be honest with you but.
Yeah I think it's like approximately something that you would want but like without the arrow.
It looks like this and it's like if you're reading that it's like how do I know that I don't know what that's doing like if I read it like.
But with the arrow looks like okay values are flowing from the left to the right so that's just kind of the intent that I wanted to put behind this syntax.
But it's just a literal there.
Thank you.
Okay.
Still like in this piece of code.
Yeah like in this case the propagator doesn't execute like each individual function like.
It goes a little signed a value one at a time or sort of happens like.
The group gets a reassign all in what's because it's a group right.
Yeah so for the groups what happens is when a cell is updated like said the R cell gets updated.
As part of it it looks at all the members of its group and it calls the special thing to fresh in the timestamp on it.
So it doesn't propagate that value from those other cells but it does ensure that it knows about the timestamp going up.
So they just have to all have the same notion of logical time.
And if and if they do then the propagation works if if that didn't happen the problem becomes that there's a lot of redundant computation that happens if they if they're not like synced up in that way.
I don't think I can explain that in a succinct way right now.
Yeah.
Okay yeah welcome.
Let's see oh all the way in the back.
Yeah.
I think that is up at the end.
Look at the air sometimes here.
I was here is.
So I specifically like the form of classic pepperoni from like the little alien.
There's continuous time and simple formal semantics.
And the distinction of the people here is an event.
Yeah where does your implementation relate to this.
Do you have a similar model of like the semantics which operators supposed to do here.
I think the distinction or is our things grouped together more.
Let's see okay the question was about if.
If I'm used if or.
Hmm how do we even say the question about continuous FRP semantics versus discrete semantics I think was the core of the question.
Sorry.
Did I get that roughly right I.
Yeah it does not exist.
So I'll just I think the short answer is it's not classic FRP.
I have not gone the continuous route.
I've gone for discrete event based things because we're used to discrete event based systems.
And it seems like the fastest way to get something that works.
But I'm also I've never used a continuous FRP system.
So it could be that I'm just ignorant.
And I need some exposure to that to know what I could take from it.
So do you have any recommendations I would love to hear.
Yeah thank you for your question.
Yeah.
I'm explaining which is you mentioned that.
When resolving two values for different time exams you have to stop the date.
Yes.
So the question was why not just use the freshest value if there's a mix of the two.
And in the general case there could be many things that are not fresh about it.
There could be more than one.
And it's not you're not guaranteed you could have two stale values actually for the same thing.
And that would also result in a glitch because it may be maybe some third that maybe some third input
Propagated over there.
So like you know add a fifth node to the graph and that one updated and you still have stale data.
So I think in the general case it's tough maybe there's an optimization.
So I've just went the dumb way that I know works.
Yeah.
I think that's is that it for questions.
We could take it outside or.
Well okay I will be we can hallway track it.
Happy to answer questions outside.