Lab note #053 Breaking from structured programming
I've been a bit anxious about the pace of progress these last three weeks. I wanted to strike a balance between making practical progress and having a sound basis. This last week, I struggled with breaking from structured programming.
- What do algebraic effects buy you?
- What is the return value of a React-like component?
- Displaying values in a pipeline without fan-ins
- Prepping for incrementalism
How is raising effects any different than calling a function?
As I kept being hemmed in by the limitations of Python and Javascript, I started to wonder if my implementation of algebraic effects was more or less just a convoluted function call. If so, it was completely unnecessary.
When you raise an effect in a function, it saves the current execution point as a continuation and starts looking up the call stack for the appropriate handler. The appropriate handler is matched by effect type. Once found, the handler does the appropriate side effect, and it can resume the program with the computed side-effect right after raising the effect.
If this was all algebraic effects did, it's not different than returning from a function after calling that function. When you call a function, you push a frame onto a stack, and it seems obvious that when you're done with it, you resume from where you called the function when you pop off the frame. But that's because the nature of a stack facilitates it as an affordance. If we had a different data structure to track stack frames, we'd have a completely different semantic for resuming a computation after calling a function!
Hence with algebraic effects, it has two other options besides just resuming the computation with a computed value.
- It can abort the entire computation and resume from where the handler wrapped the computation.
- It can compute multiple values and resume the continuations with different values.
The first can be used as a version of backtracking. The second is like being able to be pushed values.
Sadly, Python and Javascript have only single resumption continuations, embodied in generators. That means the best you can do in languages where continuations aren't first-class, is the ability to abort computations–unless you can simulate generators in some way.
I looked into some other alternatives, such as doing some state machines (too explicit), or cloning generators (too hacky) in both languages, and decided against solving the problem in the immediate term. For now, my hunch for an incremental system is that it doesn't take much computation to find the resumption point because most of the computation is not done. So you can just start executing from the beginning every time, rather than needing to keep state with a generator.
Structured programming is water. It's non-obvious to me that you could do a lot with this constraint. I guess that's why Go To Statement Considered Harmful and Notes on Structured Programming were so influential. But by swimming in structured programming since I started, I didn't realize you could do something different. And when you do something different, you need to reconstruct what it means to compose.
The return of a React-like component
What does a component return in a React-like component system? On the surface, a React-like component's return value is a declaration of other components to which we pass values. In my functional notebook, these React-like components are cells in the notebook that compose a dataflow pipeline. But while a component looks like it's returning other components, it's actually returning a continuation.
You may eventually realize that the JSX at the bottom is really just an obscure dialect of JavaScript which lacks a real return statement: what this is returning is not a value at all. It is also not passed back to the parent component but to the run-time. The syntax is optimized for named rather than positional arguments, but that's about it.
- Steve Wittens in Reconcile All the Things
This continuation is in the application-layer runtime of the React-like incremental system, not in the underlying language.
This breaks with structured programming a little bit. I had gotten the notebook to evaluate different cells down to the builtins, like Fragment. However, in a tree-like hierarchy of cells, computation always fans out. For dataflow graphs, there's some kind of fan-in to aggregate computation. This is what Witten's Yeet-Reduce addresses, but I didn't really understand the design space until I wrestled with the problem myself.
With functions in structured programming, we take it for granted the value of a function expression is its meaning, and it's returned to the calling function. It's how you compose one computation with another. In addition, you can fan in results from multiple function calls by holding on to their return values before proceeding with the next computation that needs them all. When you break from these norms, you need to consider how computation is chained and composed.
This tripped me up because I didn't recognize I was breaking from structured programming and had to figure out how things were composed. Do I need to return computed values up the tree of fibers, the same way that structured programming returned values from every called function? But not every intermediate ancestor has a use for that computed result. If I had to pass values up and down a tree, that would result in boilerplate connective tissue that I didn't need. On the other hand, if I did something like a Yeet-reduce, it wasn't clear to me that's what I needed to get it minimally useful today.
After sitting with it for a couple of days, I realized that dataflow graphs are usually continuations of values that keep propagating forward(!). Rarely do they reach back and resume. In addition, when I think about the pipelines I have built in the past, the result gets thrown into a store at the very end, rather than returned back as a value to a previous part of the pipeline.
That said, fan-ins are very useful when cells are written as a composition of other cells because the return of the composition of cells is a stand-in for a single cell. It's the basis of composition. But now that I recognize that I broke some basics of structured programming, I know where the problems are and why it didn't seem like things were fitting together.
Recognizing what this is, I think I can leave this for later. For now, I think it's more important to find a way to display computed values and convey a notion of computational progress. So far, I've just been looking at a wall of console.log text. I think I now have the basics of making the notebook more legible to others.
Clean up as motion
I tend to be a coder that cleans up as I go. This makes me slower than other programmers, so I've been fighting the urge, to focus on myself on the-thing-that-will-make progress. But this past week, I was stuck because I was (again) confused. So biasing towards action, I spent time cleaning up loose ends. I found it clarifying because it cleared out old ideas and the codebase now reflected my updated thinking. Hence, when codebase cleanup is an act of understanding, it can be a useful exercise, rather than an act of procrastination (which is what I feared).
Incrementalism
The whole point of putting this together is to have functional cells that can execute side-effects. I hadn't thought too hard on the incrementalism part, other than a little prior-art, blind faith, and some hand-waving in my head. I did come across this talk on building an incremental view maintenance engine.
The formulation is the kind of catnip that engineers like: an expressive system built from a small number of axiomatic components. They were able to frame incremental systems as being able to integrate and differentiate with delay components, much like in a digital signal processing system.
Having concentrated on DSP in college, I wonder why I didn't see this perspective. Maybe I never knew it that well in the first place! I'm not yet sure how and in what way, if at all, to integrate this viewpoint. But for now, it's something I think is worth considering.