lab notes

A collection of 56 posts

lab notes

Lab note #057 Effects and R1

I'm a little indisposed this week, but I did find some time here and there to do research into effects. I spent the time reading and watching a talk about effects by Oleg Kiselyov. The short version is that side-effects can be formulated as a communication protocol between a program

lab notes

Lab note #056 Using version vectors

I'm back, after a little hiatus from writing the notes. Last time, I discovered that I should have been looking more deeply into other reactive models before I embarked on a functional component (React-like) model to model data pipelines. The impedance mismatch should have been indicative that something wasn't quite

lab notes

Lab note #055 Rabbit holes leave project in shambles

Last week, I started looking at Signals. When I stepped back and looked at the entire front-end ecosystem, it seemed like many of them outside of React (Solid, Vue, Svelte, Preact), converged on some variation of Signals. There is even a Javascript proposal to include Signals in the language. Given

lab notes

Lab note #054 Visualizing Execution

One of my main goals is to make non-CRUD backend pipelines more visible. I didn't think nodes and wires programming was the way to go, but unconsciously, I envisioned just showing the results of a cell next to the cell, like regular computational notebooks. But my underlying assumption was that

lab notes

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

lab notes

Lab note #052 Epx for everything

This past week, I worked through more confusion on my part. * Consolidated the representation of an algebraic effect with the React-like components (Fibers) * Worked out a solution for resuming fibers after getting a result back from from the algebraic effect. (Then block) * Use a data description of all cells (Epx)

lab notes

Lab note #051 Cell composition and lazy evaluation

Last week, I merged the runtime worker into the kernel worker. Originally, I wanted that to run multiple kernels at once, so users can run languages in a mix of cells, or they can run more than one cell in parallel. It was too hard to trace execution over a

lab notes

Lab note #050 Prior art of a React-like runtime

I fell short this week in that I didn't do what I said I was going to do. Instead, of writing code, I went down the incremental rabbit hole. It was innocuous at first, but ended up being a full deep dive, mostly into the work of Steven Wittens (aka

lab notes

Lab note #049 Survey of Reactive and Incremental Programming

For a while now, I've been circling the drain on the Tools for Thought space and all the topics related to it. One large topic is reactivity, and not too far behind is incremental computation. They're two sides to a coin, so it's hard to disentangle them from each other.

lab notes

Lab note #048 Basic Effects Done, Reactivity Next

I spent most of the week getting a basic algebraic effects runtime working. The initial version is single-threaded, synchronous, no typing, with a single yield from handlers. For now, it's good enough for building the proverbial skateboard. Only during implementation did I run into design questions I wouldn't have had

lab notes

Lab note #047 Progress on Notebook

My progress on Crafting Interpreters halted when I was researching how Algebraic Effects were implemented, once I realized that I might not need all the gory details. The part I wanted to get to was understanding how closures were implemented, especially if they were relevant to getting Algebraic Effects to

lab notes

Lab note #046 Algebraic Effects for Notebook Cells

The notebook that I want to build and use has pure functional cells. Functional cells are where the output only depends on the input. * No need to figure out the correct execution order for the notebook cells to get it in a working state. * For any change, only dependent cells

lab notes

Lab note #045 From Database to Notebook

I spent the last month doing some contract work, both to pay the bills and get some perspective on how web devs are working nowadays. I've been away for about two years and some things have changed. I worked on a Next.js stack, and I'm honestly a little horrified

lab notes

Lab note #044 Sailing by cache-oblivious data structures

As part of biasing towards action, I thought it was time to reimplement the Prolly Tree in Zig. I wanted to focus on being cache-friendly this time, now that I have lower-level control. But that resulted in a deep dive into data-oriented programming. The question is how to represent a

lab notes

Lab note #043 Merkle CRDT protocol

My adherence to immutability has put me on the hard path for everything so far. Not just for the unicit Prolly tree, but also for the CRDT. Most practical CRDT libraries use an op-based CRDT or a delta-based CRDT, but many do not keep the entire history around. I think

lab notes

Lab note #042 LLM Zine

I started working on making an LLM Zine. Not to worry, the work on the database is still in the works, but this has been a burgeoning interest and opportunity. LLMs are a fundamental technological breakthrough, and the effects of this technology will take at least a decade to work

lab notes

Lab note #041 Two flavors of Op-based CRDTs as a baseline

I've now implemented an Op-based and a Pure op-based CRDT. I couldn't quite make the leap before to merkle-based CRDTs. While vectors clocks are mechanically simple, I wasn't quite sure how they mapped to a merkle-DAG node if replica IDs weren't available. After seeing them in action, I'm fairly certain

lab notes

Lab note #040 Hitting a wall and going back to basics with CRDTs

This continues my exploration into CRDTs, beyond the typical tutorials. The more I looked, the more threads there were to pull on. I currently have a couple of lines of questioning to answer: * How do we compose CRDTs so they both converge to a single state without coordination but with

lab notes

Lab note #039 Semantics of Composed CRDTs

After the implementation of the Prolly Tree, I set about writing an immutable map. It was pretty straightforward as most of the heavy lifting is done by the Prolly Tree implementation. The immutable map just keeps a simple list of roots after every change. There are a bunch of improvements

lab notes

Lab note #038 Prolly Tree Incremental Insert Finally Done

It took a long time, but the incremental insert for a Prolly Tree is finally done. I don't think I've ever spent this long as such a little part of code. The two aspects that had me struggling were the bottom-up breadth-first traversal, and how to replace the swath of

lab notes

Lab note #037 Replacing a swath of nodes

The punchline first: the incremental insert is finally done on the Prolly Tree. I don't think I've ever spent so much time on such a small, core piece of code. It was also a lesson for me to lean into the struggle and talk about it. Last time, I talked

lab notes

Lab note #036 Bottom-up Breadth-first Traversal

A problem was that traversal in a layer would be backward. I'd need to traverse left-to-right to match the build process when building the Prolly Tree from scratch. No problem, I'll just loop through the children backward when processing top-down.

lab notes

Lab note #035 A quagmire of replacement nodes

I've been stuck on the incremental insertion of a key in a Prolly Tree, and feeling like I'm in a bog. The version where a Prolly Tree is built from scratch was relatively straightforward. I was able to write it in a day. The incremental version has undergone four or

lab notes

Lab note #034 Incremental insertion into Prolly Trees

Last week, I built Prolly Trees from scratch and probed some of its properties. This week, I started building a Prolly Tree incrementally, by inserting one key at a time. It was more challenging than I suspected at first glance, seeing as I implemented it three times. In a typical

lab notes

Lab note #033 Cascading boundary changes in Prolly Trees

Alright, party people. This week I went back to reimplementing Prolly Trees. I wanted to finish out the Lattice Merkle Tree. But given that my goals aren't to just fiddle around in applied research and Prolly Trees already work, I reimplemented Prolly Trees from scratch. I was delighted that the