1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
|
title: Functional reactive user interfaces with propagators
date: 2024-07-08 08:30:00
tags: lisp, scheme, guile, frp
summary: A look at a prototype functional reactive web UI using the propagator paradigm
---
I’ve been interested in functional reactive programming (FRP) for
about a decade now. I even wrote a couple of
[blog](/posts/functional-reactive-programming-in-scheme-with-guile-2d.html)
[posts](/posts/live-asset-reloading-with-guile-2d.html) back in 2014
describing my experiments. My initial source of inspiration was
[Elm](https://elm-lang.org/), the Haskell-like language for the web
that [once had FRP](https://elm-lang.org/news/farewell-to-frp) as a
core part of the language. From there, I explored the academic
literature on the subject.
(Sidenote: The Elm of 10 years ago looks quite different than the Elm
of today and I don’t know where to find that time-traveling Mario demo
that sent me down this path in the first place. That demo was really
cool! I’ll update this post later if I can find an archive of it.)
Ultimately, I created and then abandoned a library that focused on
[FRP for games](/projects/sly.html). It was a neat idea, but the
performance was terrible. The overhead of my kinda-sorta FRP system
was part of the problem, but mostly it was my own inexperience. I
didn’t know how to optimize effectively and my implementation
language, [Guile](https://gnu.org/s/guile), did not have as many
optimization passes as it does now. Also, realtime simulations like
games require much more careful use of heap allocation.
I found that, overhead aside, FRP is a bad fit for things like
scripting sequences of actions in a game. I don’t want to give up
things like coroutines that make it easy. I’ve learned how different
layers of a program may call for different programming paradigms.
Functional layers rest upoin imperative foundations. Events are built
on top of polling. Languages with expression trees run on machines
that only understand linear sequences. You get the idea. A good
general-purpose language will allow you to compose many paradigms in
the same program. I’m still a big fan of functional programming, but
single paradigm languages do not appeal to me.
Fast forward 10 years, I find myself thinking about FRP again in a new
context. I now work for the [Spritely
Institute](https://spritely.institute) where we’re researching and
building the next generation of [secure, distributed application
infrastructure](https://spritely.institute/goblins). We want to demo
our tech through easy-to-use web applications, which means we need to
do some UI programming. So, the back burner of my brain has been
mulling over the possibilities. What’s the least painful way to build
web UIs? Is this FRP thing worth revisiting?
The reason why FRP is so appealing to me (on paper, at least) is that
it allows for writing interactive programs *declaratively*. With FRP,
I can simply describe the *relationships* between the various
time-varying components, and the system wires it all together for me.
I’m spared from *callback hell*, one of the more frightening layers of
hell that forces programs to be written in a kind of
[continuation-passing
style](https://en.wikipedia.org/wiki/Continuation-passing_style) where
timing and state bugs consume more development time as the project
grows.
## What about React?
In the time during and since I last experimented with FRP, a different
approach to declarative UI programming has swept the web development
world: [React](https://react.dev/). From React, many other similar
libraries emerged. On the minimalist side there are things like
[Mithril](https://mithril.js.org/) (a favorite of mine), and then
there are bigger players like [Vue](https://vuejs.org/). The term
“reactive” has become overloaded, but in the mainstream software world
it is associated with React and friends. FRP is quite different,
despite sharing the declarative and reactive traits. Both help free
programmers from callback hell, but they achieve their results
differently.
The React model describes an application as a tree of “components”.
Each component represents a subset of the complete UI element tree.
For each component, there is a template function that takes some
inputs and returns the new desired state of the UI. This function is
called whenever an event occurs that might change the state of the UI.
The template produces a data structure known as a “virtual
[DOM](https://developer.mozilla.org/en-US/docs/Web/API/Document_Object_Model)”.
To realize this new state in the actual DOM, React diffs the previous
tree with the new one and updates, creates, and deletes elements as
necessary.
With FRP, you describe your program as an acyclic graph of nodes that
contain time-varying values. The actual value of any given node is
determined by a function that maps the current values of some input
nodes into an output value. The system is bootstrapped by handling a
UI event and updating the appropriate root node, which kicks off a
cascade of updates throughout the graph. At the leaf nodes,
side-effects occur that realize the desired state of the application.
Racket’s [FrTime](https://docs.racket-lang.org/frtime/) is one example
of such a system, which is based on Greg Cooper’s 2008 PhD
dissertation [“Integrating Dataflow Evaluation into a Practical
Higher-Order Call-by-Value
Language”](https://cs.brown.edu/people/ghcooper/thesis.pdf). In
FrTime, time-varying values are called “signals”. Elm borrowed this
language, too, and there’s currently a [proposal to add signals to
JavaScript](https://github.com/tc39/proposal-signals). Research into
FRP goes back quite a bit further. Notably, Conal Elliot and Paul
Hudak wrote [“Functional Reactive
Animation”](http://conal.net/papers/icfp97/icfp97.pdf) in 1997.
## On jank
The scope of potential change for any given event is larger in React
than FRP. An FRP system flows data through an acyclic graph, updating
only the nodes affected by the event. React requires re-evaluating
the template for each component that needs refreshing and applying a
diff algorithm to determine what needs changing in the currently
rendered UI. The virtual DOM diffing process can be quite wasteful in
terms of both memory usage and processing time, leading to jank on
systems with limited resources like phones. Andy Wingo has done some
interesting analyses of things like [React
Native](https://wingolog.org/archives/2023/04/21/structure-and-interpretation-of-react-native)
and
[Flutter](https://wingolog.org/archives/2023/04/26/structure-and-interpretation-of-flutter)
and covers the subject of jank well. So, while I appreciate the
greatly improved developer experience of React-likes (I wrote my fair
share of frontend code in the jQuery days), I’m less pleased by the
overhead that it pushes onto each user’s computer. React feels like
an important step forward on the declarative UI trail, but it’s not
the destination.
FRP has the potential for less jank because side-effects (the UI
widget state updates) can be more precise. For example, if a web page
has a text node that displays the number of times the user has clicked
a mouse button, an FRP system could produce a program that would do
the natural thing: Register a click event handler that replaces the
text node with a new one containing the updated count. We don’t need
to diff the whole page, nor do we need to create a wrapper component
to update a subset of the page. The scope is narrow, so we can apply
smaller updates. No virtual DOM necessary. There is, of course,
overhead to maintaining the graph of time-varying values. The
underlying runtime is free to use mutable state, but the user layer
must take care to use pure functions and persistent, immutable data
structures. This has a cost, but the per-event cost to refresh the UI
feels much more reasonable when compared to React. From here on, I
will stop talking about React and start exploring if FRP might really
offer a more expressive way to do declarative UI without too much
overhead. But first, we need to talk about a serious problem.
## FRP is acyclic
FRP is no silver bullet. As mentioned earlier, FRP graphs are
typically of the acyclic flavor. This limits the set of UIs that are
possible to create with FRP. Is this the cost of declarativeness? To
demonstrate the problem, consider a color picker tool that has sliders
for both the red-green-blue and hue-saturation-value representations
of color:
![Network diagram of RGB/HSV color picker](/images/propagators/rgb-hsv-color-diagram.png)
In this program, updating the sliders on the RGB side should change
the values of the sliders on the HSV side, and vice versa. This forms
a cycle between the two sets of sliders. It’s possible to express
cycles like this with event callbacks, though it’s messy and
error-prone to do manually. We’d like a system built on top of event
callbacks that can do the right thing without strange glitches or
worse, unbounded loops.
## Propagators to the rescue
Fortunately, I didn’t create that diagram above. It’s from Alexey
Radul’s 2009 PhD dissertation: [“Propagation Networks: A Flexible and
Expressive Substrate for
Computation”](https://dspace.mit.edu/bitstream/handle/1721.1/49525/MIT-CSAIL-TR-2009-053.pdf).
This paper dedicates a section to explaining how FRP can be built on
top a more general paradigm called *propagation networks*, or just
*propagators* for short. The paper is lengthy, naturally, but it is
written in an approachable style. There isn’t any terse math notation
and there are plenty of code examples. As far as PhD dissertations
go, this one is a real page turner!
Here is a quote from section 5.5 about FrTime (with emphasis added by
me):
> FrTime is built around a custom propagation infrastructure; it
> nicely achieves both non-recomputation and glitch avoidance, but
> unfortunately, the propagation system is **nontrivially
> complicated**, and **specialized for the purpose of supporting
> functional reactivity**. In particular, the FrTime system **imposes
> the invariant that the propagation graph be acyclic**, and
> guarantees that it will **execute the propagators in
> topological-sort order**. This simplifies the propagators
> themselves, but greatly complicates the runtime system, especially
> because it has to **dynamically recompute the sort order** when the
> structure of some portion of the graph changes (as when the
> predicate of a conditional changes from true to false, and the other
> branch must now be computed). That complexity, in turn, makes that
> runtime system **unsuitable for other kinds of propagation**, and
> even makes it **difficult for other kinds of propagation to
> interoperate** with it.
So, the claim is that FRP-on-propagators can remove the acyclic
restriction, reduce complexity, and improve interoperability. But
what are propagators? I like how the book [“Software Design for
Flexibility”](https://mitpress.mit.edu/9780262045490/software-design-for-flexibility/)
(2021) defines them (again, with emphasis added by me):
> “The propagator model is built on the idea that the basic
> computational elements are propagators, **autonomous independent
> machines interconnected by shared cells through which they
> communicate**. Each propagator machine continuously examines the
> cells is is connected to, and adds information to some cells based
> on computations it can make from information it can get from others.
> **Cells accumulate information and propagators produce
> information**.”
Research on propagators goes back a long way (you’ll even find a form
of propagators in the all-time classic [“Structure and Interpretation
of Computer
Programs”](https://sarabander.github.io/sicp/html/3_002e3.xhtml#g_t3_002e3_002e5)),
but it was Alexey Radul that discovered how to unify many different
types of special-purpose propagation systems so that they could share
a generic substrate and interoperate.
Perhaps the most exciting application of the propagator model is AI,
where it can be used to create “explainable AI” that keeps track of
how a particular output was computed. This type of AI stands in stark
contrast to the much hyped mainstream machine learning models that
hoover up our planet’s precious natural resources to produce black
boxes that generate [impressive
bullshit](https://link.springer.com/article/10.1007/s10676-024-09775-5).
But anyway!
The diagram above can also be found in section 5.5 of the
dissertation. Here’s the description:
> “A network for a widget for RGB and HSV color selection. Traditional
> functional reactive systems have qualms about the circularity, but
> general-purpose propagation handles it automatically.”
This color picker felt like a good, achievable target for a prototype.
The propagator network is small and there are only a handful of UI
elements, yet it will test if the FRP system is working correctly.
## The prototype
I read Alexey Radul’s dissertation, and then read chapter 7 of
Software Design for Flexibility, which is all about propagators. Both
use Scheme as the implementation language. The latter makes no
mention of FRP, and while the former explains *how* FRP can be
implemented in terms of propagators, there is (understandably) no code
included. So, I had to implement it for myself to test my
understanding. Unsurprisingly, I had misunderstood many things along
the way and my iterations of broken code let me know that.
Implementation is the best teacher.
After much code fiddling, I was able to create a working prototype of
the color picker. Here it is below:
![(iframe (@ (src "/embeds/frp-color-picker/") (height "600px")))](sxml)
This prototype is written in Scheme and uses
[Hoot](https://spritely.institute/hoot) to compile it to WebAssembly
so I can embed it right here in my blog. Sure beats a screenshot or
video! This prototype contains a minimal propagator implementation
that is sufficient to bootstrap a similarly minimal FRP
implementation.
## Propagator implementation
Let’s take a look at the code and see how it all works, starting with
propagation. There are two essential data types: Cells and
propagators. Cells accumulate information about a value, ranging from
*nothing*, some form of *partial information*, or a complete value.
The concept of partial information is Alexey Radul’s major
contribution to the propagator model. It is through partial
information structures that general-purpose propagators can be used to
implement logic programming, probabilistic programming, type
inference, and FRP, among others. I’m going to keep things as simple
as possible in this post (it’s a big enough infodump already), but do
read the propagator literature if phrases like “dependency directed
backtracking” and “truth maintenance system” sound like a good time to
you.
Cells start out knowing *nothing*, so we need a special, unique value
to represent nothing:
```scheme
(define-record-type <nothing>
(make-nothing)
%nothing?)
(define nothing (make-nothing))
(define (nothing? x) (eq? x nothing))
```
Any unique (as in `eq?`) object would do, such as `(list ’nothing)`,
but I chose to use a record type because I like the way it prints.
In addition to nothing, the propagator model also has a notion of
*contradictions*. If one source of information says there are four
lights, but another says there are five, then we have a contradiction.
Propagation networks do not fall apart in the presence of
contradictory information. There’s a data type that captures
information about them and they can be resolved in a context-specific
manner. I mention contradictions only for the sake of completeness,
as a general-purpose propagator system needs to handle them. This
prototype does not create any contradictions, so I won’t mention them
again.
Now we can define a cell type:
```scheme
(define-record-type <cell>
(%make-cell relations neighbors content strongest
equivalent? merge find-strongest handle-contradiction)
cell?
(relations cell-relations)
(neighbors cell-neighbors set-cell-neighbors!)
(content cell-content set-cell-content!)
(strongest cell-strongest set-cell-strongest!)
;; Dispatch table:
(equivalent? cell-equivalent?)
(merge cell-merge)
(find-strongest cell-find-strongest)
(handle-contradiction cell-handle-contradiction))
```
The details of *how* a cell does things like merge old information
with new information is left intentionally unanswered at this level of
abstraction. Different systems built on propagators will want to
handle things in different ways. In the propagator literature, you’ll
see generic procedures used extensively for this purpose. For the
sake of simplicity, I use a dispatch table instead. It would be easy
to layer generic merge on top later, if we wanted.
The constructor for cells sets the default contents to nothing:
```scheme
(define default-equivalent? equal?)
;; But what about partial information???
(define (default-merge old new) new)
(define (default-find-strongest content) content)
(define (default-handle-contradiction cell) (values))
(define* (make-cell name #:key
(equivalent? default-equivalent?)
(merge default-merge)
(find-strongest default-find-strongest)
(handle-contradiction default-handle-contradiction))
(let ((cell (%make-cell (make-relations name) '() nothing nothing
equivalent? merge find-strongest
handle-contradiction)))
(add-child! (current-parent) cell)
cell))
```
The default procedures used for the dispatch table are either no-ops
or trivial. The default `merge` doesn’t merge at all, it just
clobbers the old with the new. It’s up to the layers on top to
provide more useful implementations.
Cells can have neighbors (which will be propagators):
```scheme
(define (add-cell-neighbor! cell neighbor)
(set-cell-neighbors! cell (lset-adjoin eq? (cell-neighbors cell) neighbor)))
```
Since cells accumulate information, there are procedures for adding
new content and finding the current strongest value contained within:
```scheme
(define (add-cell-content! cell new)
(match cell
(($ <cell> _ neighbors content strongest equivalent? merge
find-strongest handle-contradiction)
(let ((content* (merge content new)))
(set-cell-content! cell content*)
(let ((strongest* (find-strongest content*)))
(cond
;; New strongest value is equivalent to the old one. No need
;; to alert propagators.
((equivalent? strongest strongest*)
(set-cell-strongest! cell strongest*))
;; Uh oh, a contradiction! Call handler.
((contradiction? strongest*)
(set-cell-strongest! cell strongest*)
(handle-contradiction cell))
;; Strongest value has changed. Alert the propagators!
(else
(set-cell-strongest! cell strongest*)
(for-each alert-propagator! neighbors))))))))
```
Next up is the propagator type. Propagators can be *activated* to
create information using content stored in cells and store their
results in some other cells, forming a graph. Data flow is not forced
to be directional. Cycles are not only permitted, but very common in
practice. So, propagators keep track of both their input and output
cells:
```scheme
(define-record-type <propagator>
(%make-propagator relations inputs outputs activate)
propagator?
(relations propagator-relations)
(inputs propagator-inputs)
(outputs propagator-outputs)
(activate propagator-activate))
```
Propagators can be *alerted* to schedule themselves to be re-evaluted:
```scheme
(define (alert-propagator! propagator)
(queue-task! (propagator-activate propagator)))
```
The constructor for propagators adds the new propagator as a neighbor
to all input cells and then calls `alert-propagator!` to bootstrap it:
```scheme
(define (make-propagator name inputs outputs activate)
(let ((propagator (%make-propagator (make-relations name)
inputs outputs activate)))
(add-child! (current-parent) propagator)
(for-each (lambda (cell)
(add-cell-neighbor! cell propagator))
inputs)
(alert-propagator! propagator)
propagator))
```
There are two main classes of propagators that will be used:
**primitive propagators** and **constraint propagators**. Primitive
propagators are directional; they apply a function to the values of
some input cells and write the result to an output cell:
```scheme
(define (unusable-value? x)
(or (nothing? x) (contradiction? x)))
(define (primitive-propagator name f)
(match-lambda*
((inputs ... output)
(define (activate)
(let ((args (map cell-strongest inputs)))
(unless (any unusable-value? args)
(add-cell-content! output (apply f args)))))
(make-propagator name inputs (list output) activate))))
```
We can use `primitive-propagator` to lift standard Scheme procedures
into the realm of propagators. Here’s how we’d make and use an
addition propagator:
```scheme
(define p:+ (primitive-propagator +))
(define a (make-cell))
(define b (make-cell))
(define c (make-cell))
(p:+ a b c)
(add-cell-content! a 1)
(add-cell-content! b 3)
;; After the scheduler runs…
(cell-strongest c) ;; => 4
```
It is from these primitive propagators that we can build more
complicated, compound propagators. Compound propagators compose
primitive propagators (or other compound propagators) and lazily
construct their section of the network upon first activation:
```scheme
(define (compound-propagator name inputs outputs build)
(let ((built? #f))
(define (maybe-build)
(unless (or built?
(and (not (null? inputs))
(every unusable-value? (map cell-strongest inputs))))
(parameterize ((current-parent (propagator-relations propagator)))
(build)
(set! built? #t))))
(define propagator (make-propagator name inputs outputs maybe-build))
propagator))
```
By this point you may be wondering what all the references to
`current-parent` are about. It is for tracking the parent/child
relationships of the cells and propagators in the network. This could
be helpful for things like visualizing the network, but we aren’t
going to do anything with it today. I’ve omitted all of the other
relation code for this reason.
Constraint propagators are compound propagators whose inputs and
outputs are the same, which results in bidirectional propagation:
```scheme
(define (constraint-propagator name cells build)
(compound-propagator name cells cells build))
```
Using primitive propagators for addition and subtraction, we can build
a constraint propagator for the equation `a + b = c`:
```scheme
(define p:+ (primitive-propagator +))
(define p:- (primitive-propagator -))
(define (c:sum a b c)
(define (build)
(p:+ a b c)
(p:- c a b)
(p:- c b a))
(constraint-propagator 'sum (list a b c) build))
(define a (make-cell))
(define b (make-cell))
(define c (make-cell))
(c:sum a b c)
(add-cell-content! a 1)
(add-cell-content! c 4)
;; After the scheduler runs…
(cell-strongest b) ;; => 3
```
With a constraint, we can populate any two cells and the propagation
system will figure out the value of the third. Pretty cool!
This is a good enough propagation system for the FRP prototype.
## FRP implementation
If you’re familiar with terminology from other FRP systems like
“signals” and “behaviors” then set that knowledge aside for now. We
need some new nouns. But first, a bit about the problems that need
solving in order to implement FRP on top of general-purpose
propagators:
* The propagator model does not enforce any ordering of *when*
propagators will be re-activated in relation to each other. If
we’re not careful, something in the network could compute a value
using a mix of fresh and stale data, resulting in a momentary
“glitch” that could be noticeable in the UI.
* The presence of cycles introduce a crisis of identity. It’s not
sufficient for every time-varying value to be treated as its own
self. In the color picker, the RGB values and the HSV values are
two representations of *the same thing*. We need a new notion of
identity to capture this and prevent unnecessary churn and glitches
in the network.
For starters, we will create a “reactive identifier” (needs a better
name) data type that serves two purposes:
1) To create shared identity between different information sources
that are *logically* part of the same thing
2) To create localized timestamps for values associated with this identity
```scheme
(define-record-type <reactive-id>
(%make-reactive-id name clock)
reactive-id?
(name reactive-id-name)
(clock reactive-id-clock set-reactive-id-clock!))
(define (make-reactive-id name)
(%make-reactive-id name 0))
(define (reactive-id-tick! id)
(let ((t (1+ (reactive-id-clock id))))
(set-reactive-id-clock! id t)
`((,id . ,t))))
```
Giving each logical identity in the FRP system its own clock
eliminates the need for a global clock, avoiding a potentially
troublesome source of centralization. This is kind of like how
[Lamport timestamps](https://en.wikipedia.org/wiki/Lamport_timestamp)
are used in distributed systems.
We also need a data type that captures the value of something at a
particular point in time. Since the cruel march of time is unceasing,
these are *ephemeral* values:
```scheme
(define-record-type <ephemeral>
(make-ephemeral value timestamps)
ephemeral?
(value ephemeral-value)
;; Association list mapping identity -> time
(timestamps ephemeral-timestamps))
```
Ephemerals are boxes that contain some arbitrary data with a bunch of
shipping labels slapped onto the outside explaining from whence they
came. This is the partial information structure that our propagators
will manipulate and add to cells.
Here’s how to say “the mouse position was (1, 2) at time 3” in code:
```scheme
(define mouse-position (make-reactive-id ’mouse-position))
(make-ephemeral #(1 2) `((,mouse-position . 3)))
```
We need to perform a few operations with ephemerals:
1) Test if one ephemeral is *fresher* (more recent) than another
2) Compose the timestamps from several inputs to form an aggregate
timestamp for an output, but only if all timestamps for each distinct
identifier match (no mixing of fresh and stale values)
3) Merge two ephemerals when cell content is added
```scheme
(define (ephemeral-fresher? a b)
(let ((b-inputs (ephemeral-timestamps b)))
(let lp ((a-inputs (ephemeral-timestamps a)))
(match a-inputs
(() #t)
(((key . a-time) . rest)
(match (assq-ref b-inputs key)
(#f (lp rest))
(b-time
(and (> a-time b-time)
(lp rest)))))))))
(define (merge-ephemerals old new)
(cond
((nothing? old) new)
((nothing? new) old)
(else (if (ephemeral-fresher? new old) new old))))
(define (merge-ephemeral-timestamps ephemerals)
(define (adjoin-keys alist keys)
(fold (lambda (key+value keys)
(match key+value
((key . _)
(lset-adjoin eq? keys key))))
keys alist))
(define (check-timestamps id)
(let lp ((ephemerals ephemerals) (t #f))
(match ephemerals
(() t)
((($ <ephemeral> _ timestamps) . rest)
(match (assq-ref timestamps id)
;; No timestamp for this id in this ephemeral. Continue.
(#f (lp rest t))
(t*
(if t
;; If timestamps don't match then we have a mix of
;; fresh and stale values, so return #f. Otherwise,
;; continue.
(and (= t t*) (lp rest t))
;; Initialize timestamp and continue.
(lp rest t*))))))))
;; Build a set of all reactive identifiers across all ephemerals.
(let ((ids (fold (lambda (ephemeral ids)
(adjoin-keys (ephemeral-timestamps ephemeral) ids))
'() ephemerals)))
(let lp ((ids ids) (timestamps '()))
(match ids
(() timestamps)
((id . rest)
;; Check for consistent timestamps. If they are consistent
;; then add it to the alist and continue. Otherwise, return
;; #f.
(let ((t (check-timestamps id)))
(and t (lp rest (cons (cons id t) timestamps)))))))))
```
Example usage:
```scheme
(define e1 (make-ephemeral #(3 4) `((,mouse-position . 4))))
(define e2 (make-ephemeral #(1 2) `((,mouse-position . 3))))
(ephemeral-fresher? e1 e2) ;; => #t
(merge-ephemerals e1 e2) ;; => e1
(merge-ephemeral-timestamps (list e1 e2)) ;; => #f
(define (mouse-max-coordinate e)
(match e
(($ <ephemeral> #(x y) timestamps)
(make-ephemeral (max x y) timestamps))))
(define e3 (mouse-max-coordinate e1))
(merge-ephemeral-timestamps (list e1 e3)) ;; => ((mouse-position . 4))
```
Now we can build a primitive propagator constructor that lifts
ordinary Scheme procedures so that they work with ephemerals:
```scheme
(define (ephemeral-wrap proc)
(match-lambda*
((and ephemerals (($ <ephemeral> args) ...))
(match (merge-ephemeral-timestamps ephemerals)
(#f nothing)
(timestamps (make-ephemeral (apply proc args) timestamps))))))
(define* (primitive-reactive-propagator name proc)
(primitive-propagator name (ephemeral-wrap proc)))
```
## Reactive UI implementation
Now we need some propagators that live at the edges of our network
that know how to interact with the DOM and can do the following:
1) Sync a DOM element attribute with the value of a cell
2) Create a two-way data binding between an element’s `value` attribute
and a cell
3) Render the markup in a cell and place it into the DOM tree in the
right location
Syncing an element attribute is a directional operation and the
easiest to implement:
```scheme
(define (r:attribute input elem attr)
(let ((attr (symbol->string attr)))
(define (activate)
(match (cell-strongest input)
(($ <ephemeral> val)
(attribute-set! elem attr (obj->string val)))
;; Ignore unusable values.
(_ (values))))
(make-propagator 'r:attribute (list input) '() activate)))
```
Two-way data binding is more involved. First, a new data type is used
to capture the necessary information:
```scheme
(define-record-type <binding>
(make-binding id cell default group)
binding?
(id binding-id)
(cell binding-cell)
(default binding-default)
(group binding-group))
(define* (binding id cell #:key (default nothing) (group '()))
(make-binding id cell default group))
```
And then a reactive propagator applies that binding to a specific DOM
element:
```scheme
(define* (r:binding binding elem)
(match binding
(($ <binding> id cell default group)
(define (update new)
(unless (nothing? new)
(let ((timestamp (reactive-id-tick! id)))
(add-cell-content! cell (make-ephemeral new timestamp))
;; Freshen timestamps for all cells in the same group.
(for-each (lambda (other)
(unless (eq? other cell)
(match (cell-strongest other)
(($ <ephemeral> val)
(add-cell-content! other (make-ephemeral val timestamp)))
(_ #f))))
group))))
;; Sync the element's value with the cell's value.
(define (activate)
(match (cell-strongest cell)
(($ <ephemeral> val)
(set-value! elem (obj->string val)))
(_ (values))))
;; Initialize element value with the default value.
(update default)
;; Sync the cell's value with the element's value.
(add-event-listener! elem "input"
(procedure->external
(lambda (event)
(update (string->obj (value elem))))))
(make-propagator 'r:binding (list cell) '() activate))))
```
A simple method for rendering to the DOM is to replace some element
with a newly created element based on the current ephemeral value of a
cell:
```scheme
(define (r:dom input elem)
(define (activate)
(match (cell-strongest input)
(($ <ephemeral> exp)
(let ((new (sxml->dom exp)))
(replace-with! elem new)
(set! elem new)))
(_ (values))))
(make-propagator 'dom (list input) '() activate))
```
The `sxml->dom` procedure deserves some further explanation. To
create a subtree of new elements, we have two options:
1) Use something like the
[`innerHTML`](https://developer.mozilla.org/en-US/docs/Web/API/Element/innerHTML)
element property to insert arbitrary HTML as a string and let the
browser parse and build the elements.
2) Use a Scheme data structure that we can iterate over and make the
relevant `document.createTextNode`, `document.createElement`,
etc. calls.
Option 1 might be a shortcut and would be fine for a quick prototype,
but it would mean that to generate the HTML we’d be stuck using raw
strings. While string-based templating is commonplace, we can
certainly [do
better](https://www.more-magic.net/posts/structurally-fixing-injection-bugs.html)
in Scheme. Option 2 is actually not too much work and we get to use
Lisp’s universal templating system,
[`quasiquote`](https://www.gnu.org/software/guile/manual/r5rs/Quasiquotation.html),
to write our markup.
Thankfully, [SXML](https://en.wikipedia.org/wiki/SXML) already exists
for this purpose. SXML is an alternative XML syntax that uses
s-expressions. Since Scheme uses s-expression syntax, it’s a natural
fit.
Example:
```scheme
'(article
(h1 "SXML is neat")
(img (@ (src "cool.jpg") (alt "cool image")))
(p "Yeah, SXML is " (em "pretty neato!")))
```
Instead of using it to generate HTML text, we’ll instead generate a
tree of DOM elements. Furthermore, because we’re now in full control
of how the element tree is built, we can build in support for reactive
propagators!
Check it out:
```scheme
(define (sxml->dom exp)
(match exp
;; The simple case: a string representing a text node.
((? string? str)
(make-text-node str))
((? number? num)
(make-text-node (number->string num)))
;; A cell containing SXML (or nothing)
((? cell? cell)
(let ((elem (cell->elem cell)))
(r:dom cell elem)
elem))
;; An element tree. The first item is the HTML tag.
(((? symbol? tag) . body)
;; Create a new element with the given tag.
(let ((elem (make-element (symbol->string tag))))
(define (add-children children)
;; Recursively call sxml->dom for each child node and
;; append it to elem.
(for-each (lambda (child)
(append-child! elem (sxml->dom child)))
children))
(match body
((('@ . attrs) . children)
(for-each (lambda (attr)
(match attr
(((? symbol? name) (? string? val))
(attribute-set! elem
(symbol->string name)
val))
(((? symbol? name) (? number? val))
(attribute-set! elem
(symbol->string name)
(number->string val)))
(((? symbol? name) (? cell? cell))
(r:attribute cell elem name))
;; The value attribute is special and can be
;; used to setup a 2-way data binding.
(('value (? binding? binding))
(r:binding binding elem))))
attrs)
(add-children children))
(children (add-children children)))
elem))))
```
Notice the calls to `r:dom`, `r:attribute`, and `r:binding`. A cell
can be used in either the context of an element (`r:dom`) or an
attribute (`r:attribute`). The `value` attribute gets the additional
superpower of `r:binding`. We will make use of this when it is time
to render the color picker UI!
## Color picker implementation
Alright, I’ve spent a lot of time explaining how I built a minimal
propagator and FRP system from first principles on top of
Hoot-flavored Scheme. Let’s *finally* write the dang color picker!
First we need some data types to represent RGB and HSV colors:
```scheme
(define-record-type <rgb-color>
(rgb-color r g b)
rgb-color?
(r rgb-color-r)
(g rgb-color-g)
(b rgb-color-b))
(define-record-type <hsv-color>
(hsv-color h s v)
hsv-color?
(h hsv-color-h)
(s hsv-color-s)
(v hsv-color-v))
```
And procedures to convert RGB to HSV and vice versa:
```scheme
(define (rgb->hsv rgb)
(match rgb
(($ <rgb-color> r g b)
(let* ((cmax (max r g b))
(cmin (min r g b))
(delta (- cmax cmin)))
(hsv-color (cond
((= delta 0.0) 0.0)
((= cmax r)
(let ((h (* 60.0 (fmod (/ (- g b) delta) 6.0))))
(if (< h 0.0) (+ h 360.0) h)))
((= cmax g) (* 60.0 (+ (/ (- b r) delta) 2.0)))
((= cmax b) (* 60.0 (+ (/ (- r g) delta) 4.0))))
(if (= cmax 0.0)
0.0
(/ delta cmax))
cmax)))))
(define (hsv->rgb hsv)
(match hsv
(($ <hsv-color> h s v)
(let* ((h' (/ h 60.0))
(c (* v s))
(x (* c (- 1.0 (abs (- (fmod h' 2.0) 1.0)))))
(m (- v c)))
(define-values (r' g' b')
(cond
((<= 0.0 h 60.0) (values c x 0.0))
((<= h 120.0) (values x c 0.0))
((<= h 180.0) (values 0.0 c x))
((<= h 240.0) (values 0.0 x c))
((<= h 300.0) (values x 0.0 c))
((<= h 360.0) (values c 0.0 x))))
(rgb-color (+ r' m) (+ g' m) (+ b' m))))))
```
We also need some procedures to convert colors into the hexadecimal
representations we’re used to seeing:
```scheme
(define (uniform->byte x)
(inexact->exact (round (* x 255.0))))
(define (rgb->int rgb)
(match rgb
(($ <rgb-color> r g b)
(+ (* (uniform->byte r) (ash 1 16))
(* (uniform->byte g) (ash 1 8))
(uniform->byte b)))))
(define (rgb->hex-string rgb)
(list->string
(cons #\#
(let lp ((i 0) (n (rgb->int rgb)) (out '()))
(if (= i 6)
out
(lp (1+ i) (ash n -4)
(cons (integer->char
(let ((digit (logand n 15)))
(+ (if (< digit 10)
(char->integer #\0)
(- (char->integer #\a) 10))
digit)))
out)))))))
(define (rgb-hex->style hex)
(string-append "background-color: " hex ";"))
```
Now we can lift the color API into primitive reactive propagator
constructors:
```scheme
(define-syntax-rule (define-primitive-reactive-propagator name proc)
(define name (primitive-reactive-propagator 'name proc)))
(define-primitive-reactive-propagator r:rgb-color rgb-color)
(define-primitive-reactive-propagator r:rgb-color-r rgb-color-r)
(define-primitive-reactive-propagator r:rgb-color-g rgb-color-g)
(define-primitive-reactive-propagator r:rgb-color-b rgb-color-b)
(define-primitive-reactive-propagator r:hsv-color hsv-color)
(define-primitive-reactive-propagator r:hsv-color-h hsv-color-h)
(define-primitive-reactive-propagator r:hsv-color-s hsv-color-s)
(define-primitive-reactive-propagator r:hsv-color-v hsv-color-v)
(define-primitive-reactive-propagator r:rgb->hsv rgb->hsv)
(define-primitive-reactive-propagator r:hsv->rgb hsv->rgb)
(define-primitive-reactive-propagator r:rgb->hex-string rgb->hex-string)
(define-primitive-reactive-propagator r:rgb-hex->style rgb-hex->style)
```
From those primitive propagators, we can build the necessary
constraint propagators:
```scheme
(define (r:components<->rgb r g b rgb)
(define (build)
(r:rgb-color r g b rgb)
(r:rgb-color-r rgb r)
(r:rgb-color-g rgb g)
(r:rgb-color-b rgb b))
(constraint-propagator 'r:components<->rgb (list r g b rgb) build))
(define (r:components<->hsv h s v hsv)
(define (build)
(r:hsv-color h s v hsv)
(r:hsv-color-h hsv h)
(r:hsv-color-s hsv s)
(r:hsv-color-v hsv v))
(constraint-propagator 'r:components<->hsv (list h s v hsv) build))
(define (r:rgb<->hsv rgb hsv)
(define (build)
(r:rgb->hsv rgb hsv)
(r:hsv->rgb hsv rgb))
(constraint-propagator 'r:components<->hsv (list rgb hsv) build))
```
At long last, we are ready to define the UI! Here it is:
```scheme
(define (render exp)
(append-child! (document-body) (sxml->dom exp)))
(define* (slider id name min max default #:optional (step "any"))
`(div (@ (class "slider"))
(label (@ (for ,id)) ,name)
(input (@ (id ,id) (type "range")
(min ,min) (max ,max) (step ,step)
(value ,default)))))
(define (uslider id name default) ; [0,1] slider
(slider id name 0 1 default))
(define-syntax-rule (with-cells (name ...) body . body*)
(let ((name (make-cell 'name #:merge merge-ephemerals)) ...) body . body*))
(with-cells (r g b rgb h s v hsv hex style)
(define color (make-reactive-id 'color))
(define rgb-group (list r g b))
(define hsv-group (list h s v))
(r:components<->rgb r g b rgb)
(r:components<->hsv h s v hsv)
(r:rgb<->hsv rgb hsv)
(r:rgb->hex-string rgb hex)
(r:rgb-hex->style hex style)
(render
`(div
(h1 "Color Picker")
(div (@ (class "preview"))
(div (@ (class "color-block") (style ,style)))
(div (@ (class "hex")) ,hex))
(fieldset
(legend "RGB")
,(uslider "red" "Red"
(binding color r #:default 1.0 #:group rgb-group))
,(uslider "green" "Green"
(binding color g #:default 0.0 #:group rgb-group))
,(uslider "blue" "Blue"
(binding color b #:default 1.0 #:group rgb-group)))
(fieldset
(legend "HSV")
,(slider "hue" "Hue" 0 360 (binding color h #:group hsv-group))
,(uslider "saturation" "Saturation" (binding color s #:group hsv-group))
,(uslider "value" "Value" (binding color v #:group hsv-group))))))
```
Each color channel (R, G, B, H, S, and V) has a cell which is bound to
a slider (`<input type="range">`). All six sliders are identified as
`color`, so adjusting *any of them* increments `color`’s timestamp.
The R, G, and B sliders form one input group, and the H, S, and V
sliders form another. By grouping the related sliders together,
whenever one of the sliders is moved, *all members* of the group will
have their ephemeral value refreshed with the latest timestamp. This
behavior is *crucial* because otherwise the `r:components<->rgb` and
`r:components<->hsv` propagators would see that one color channel has
a fresher value than the other two and *do nothing*. Since the
underlying propagator infrastructure does not enforce activation
order, reactive propagators *must* wait until their inputs reach a
consistent state where the timestamps for a given reactive identifier
are all the same.
With this setup, changing a slider on the RGB side will cause a new
color value to propagate over to the HSV side. Because the
relationship is cyclical, the HSV side will then attempt to propagate
an equivalent color value back to the RGB side! This could be bad
news, but since the current RGB value is equally fresh (same
timestamp), the propagation stops right there. Redundant work is
minimized and an unbounded loop is avoided.
And that’s it! Phew!
Complete source code can be found
[here](https://git.dthompson.us/software-design-for-flexibility/tree/chapter-7/propagators.scm).
## Reflections
I think the results of this prototype are promising. I’d like to try
building some larger demos to see what new problems arise. Since
propagation networks include cycles, they cannot be garbage collected
until there are no references to any part of the network from the
outside. Is this acceptable? I didn’t optimize, either. A more
serious implementation would want to do things like use `case-lambda`
for all n-ary procedures to avoid consing an argument list in the
common cases of 1, 2, 3, etc. arguments. There is also a need for a
more pleasing domain-specific language, using Scheme’s macro system,
for describing FRP graphs.
Alexey Radul’s dissertation was published in 2009. Has anyone made a
FRP system based on propagators since then that’s used in real
software? I don’t know of anything but it’s a big information
superhighway out there.
I wish I had read Alexey Radul's disseration 10 years ago when I was
first exploring FRP. It would have saved me a lot of time spent
running into problems that have already been solved that I was not
equipped to solve on my own. I have even talked to Gerald Sussman (a
key figure in propagator research) *in person* about the propagator
model. That conversation was focused on AI, though, and I didn’t
realize that propagators could also be used for FRP. It wasn’t until
more recently that friend and colleague [Christine
Lemmer-Webber](https://dustycloud.org/), who was present for the
aforementioned conversation with Sussman, told me about it. There are
so many interesting things to learn out there, but I am also so tired.
Better late than never, I guess!
Anyway, if you made it this far then I hope you have enjoyed reading
about propagators and FRP. ’Til next time!
|