Ripple: An OCaml Library for Incremental Computation [part-ii-incr]

Boris Hall

Following the work of Adaptive Functional Programming and Implicit self-adjusting computation, this project will build an incremental computation engine in OCaml alongside an expressive combinator library for build such computations. As an extension, a small DSL will be built that makes use of the engine to build an implicitly incremental programming language.

The core of this project is to implement an eDSL and a runtime in OCaml for self-adjusting computation. I also propose a new TDT which allows for generic monoidal folds over modifiable sequences: the library will include a native foldMap primitive that allows performant reduction over a modifiable sequence of modifiable values for any general monoid, giving logarithmic updates with a small trace. I will then compare foldMap to the generic fold implemented in plain SAC.
-- From Boris' Proposal

References

Reference. Implicit self-adjusting computation for purely functional programs [chen2011implicit]

2011
Yan Chen, Jana Dunfield, Matthew A. Hammer, Umut A. Acar
10.1145/2034773.2034792
https://doi.org/10.1145/2034773.2034792

Abstract

2011
Yan Chen, Jana Dunfield, Matthew A. Hammer, Umut A. Acar

Computational problems that involve dynamic data, such as physics simulations and program development environments, have been an important subject of study in programming languages. Building on this work, recent advances in self-adjusting computation have developed techniques that enable programs to respond automatically and efficiently to dynamic changes in their inputs. Self-adjusting programs have been shown to be efficient for a reasonably broad range of problems but the approach still requires an explicit programming style, where the programmer must use specific monadic types and primitives to identify, create and operate on data that can change over time.We describe techniques for automatically translating purely functional programs into self-adjusting programs. In this implicit approach, the programmer need only annotate the (top-level) input types of the programs to be translated. Type inference finds all other types, and a type-directed translation rewrites the source program into an explicitly self-adjusting target program. The type system is related to information-flow type systems and enjoys decidable type inference via constraint solving. We prove that the translation outputs well-typed self-adjusting programs and preserves the source program's input-output behavior, guaranteeing that translated programs respond correctly to all changes to their data. Using a cost semantics, we also prove that the translation preserves the asymptotic complexity of the source program.

Reference. Adaptive functional programming [acar2002adaptive]

2002
Umut A. Acar, Guy E. Blelloch, Robert Harper
10.1145/503272.503296
https://doi.org/10.1145/503272.503296

Abstract

2002
Umut A. Acar, Guy E. Blelloch, Robert Harper

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in their scope of applicability. We propose a general mechanism for adaptive computing that enables one to make any purely-functional program adaptive.We show that the mechanism is practical by giving an efficient implementation as a small ML library. The library consists of three operations for making a program adaptive, plus two operations for making changes to the input and adapting the output to these changes. We give a general bound on the time it takes to adapt the output, and based on this, show that an adaptive Quicksort adapts its output in logarithmic time when its input is extended by one key.To show the safety and correctness of the mechanism we give a formal definition of AFL, a call-by-value functional language extended with adaptivity primitives. The modal type system of AFL enforces correct usage of the adaptivity mechanism, which can only be checked at run time in the ML library. Based on the AFL dynamic semantics, we formalize the change-propagation algorithm and prove its correctness.

Context

Shells, SOOCon26 and Part IIs [weekly-2026-w40]

October 9, 2026
Patrick Ferris

Last week I gave a precise meaning to the "mergeability" of container images. The further I go down this rabbit hole, the less convinced I am of the exact benefits of such an approach. However, there are lots of off-shoots to explore as well, which all seem very worthwhile and might have better semantics than merging (e.g. incremental computation and provenance-tracking).

Uniform Representations [uniform-repr]

October 12, 2026
Patrick Ferris

Whilst working on things related to Merry and Shelter, I couldn't help but think how much easier parts of this problem would be if we were using Plan9 for one simple reason: the uniform access to OS resources. Half the battle on Linux is trying to trace or sandbox a process with respect to some set of OS resources (in an ideal world, all of them). Syscalls are perhaps the closest thing we have, but there isn't a one-to-one mapping between user actions and syscalls (e.g. opening a file using io_uring does not call open(2) or openat(2)).

I think there is often a trade-off here in terms of performance and simplicity. Plan9's 9P protocol was not exactly known for its performance. But, I still find myself, to use a phrase my colleague Ryan once used when explaining his use of emacs, comfy with uniform representations. Another example, a tree in Forester.

It is pleasant when these representations have a defined structure, even if the contents are more malleable. For instance, I don't want everything to be schema-less JSON. Forester trees have tags and that allows me to impose a schema in a structured way that doesn't lead to parsing errors. Similarly, 9P offers a simple protocol on which all things are built. As I understand it, the semantics are given by the interpretation of the file server that is resolved, but the protocol is uniform. Anyway, just some thoughts.

State of Open Conference 2026 -- Belfast [soocon2026-belfast]

October 9, 2026
Patrick Ferris
https://stateofopencon.com/belfast-soocon26/

This week I was fortunate enough to attend (as a volunteer) SOOCon26 in Belfast in the Ulster Bank building, just opposite the City Hall. Thanks to Anil Madhavapeddy for linking me up with Amanda Brock to make it happen at the last hour.

If I can boil down the conference into a general topic it would be: how are large language models and coding agents impacting commercial, business-oriented open-source software. I found the conference's near-total focus on AI a little surprising and a little disappointing, but I suppose it reflects the current state of open source. For example, most, if not all, the working developers and business owners at this conference, for one reason or another, felt the need to relate their work to AI, both in their talks and in hallway conversations. Something I continue to struggle with, though, is that almost all references to "AI" pointed to large, expensive, closed frontier models (such as Claude, ChatGPT, Copilot and Gemini). That being said, there were talks on data (and AI) sovereignty as well as mentions of the increasingly capabale open models (e.g. Qwen).

I would like to add that the conference was essentially offline: no recordings or streaming. With that in mind, I want to respect the fact that most attendees and presenters could speak freely and candidly, so I will only focus on some of the higher level threads of discussion without attributing too much to any individual.

AI: Productivity

October 9, 2026
Patrick Ferris

The morning focused mainly on the question: what is a software developer's job in 2026? This culminated in a panel discussion on "building trust in AI". Already, I would say the conference's mind was made up, AI is here to stay; it is just a tool; we should learn how to hold it properly. I think, in part, this was mainly due to the group of speakers who were all, more or less, executives within for-profit businesses that incorporate open source in some way: Github, BIMP.ai and Budibase. The only exception was a speaker from the Institute of Directors. I think this gave the morning session a commercial flavour which suggested the tech industry's large-scale adoption of AI tooling, a position I'm not sure is as common among, or available to, smaller open-source maintainers.

One stream of thought that was popular was arguing that languages like C, where it is easy to introduce memory bugs and vulnerabilities, are on the way out. Copilot's runtime rewrite in Rust was championed as a success story for the kinds of productivity that can be unlocked for highly-skilled developers. A pinch of salt is needed though, as Microsoft did sponsor the event. My own thoughts, however, are that there are quite a few success stories we can learn from where software was translated from one programming language to another using an LLM. Migration seems well-defined and well-scoped, often with large, pre-existing test suites that can easily guide a tool towards some form of correctness. In the same breath, it is not necessarily that straightforward, for example, see some lobste.rs commentary on the Bun rewrite in Rust.

Another undercurrent throughout the morning talks was how LLMs could free up developers to actively engage with users. Some quotes from the talks included "experiment with empathy" and "AI doesn't write the story". On the surface, this seems like a reasonable argument. But, shouldn't these large teams of people have already been thinking about their users, with or without AI? I'm also not convinced this free time will appear. When the metric of success is at least proportional to the rate of new features, it would seem that a tool, like an LLM, would only crank out more widgets rather than better widgets.

A final worrying conversation from the panel, discussed the fact that companies are not hiring graduates. This was self-evident from a few other people I met in and around the conference: computer science graduates still looking for jobs.

AI: Community, Data Centres and Vulnerabilities

October 9, 2026
Patrick Ferris

The post-lunch session included a talk about the future of community open source, a talk about AI data centres and finally a panel about the "vulnpocalypse".

The first talk focused on the realities of doing community open source and how, in effect, AI and LLMs are not (yet) a part of our shared open culture, citing large, anti-AI open-source projects, some which have banned AI contributions (e.g. NLNet Labs, Codemirror) and pro-AI projects which have closed contributions (e.g. Ladybird). Of course, open source never meant the right to contribute, but it still signals a, perhaps, worrying shift in open-source, cultural norms. An arXiv paper collected some AI policies on popular repositories which is worth a skim.

Another topic in the talk was the "time to open". The speaker argued that it was now possible to completely reverse engineer closed-source products and tools in as little as 48 hours. This could lead to more open source business models, as closed models are no longer viable. The speaker suggested that the open-source community around a project is now more important than the code itself. I think I fall somewhere closer to believing that they are both important. I worry about the proliferation of agentically-managed software stacks which companies and individuals use with little incentive to upstream patches back to the community (or release their new code for the community). This kind of isolationism seems more likely given the ability to create your own implementation of any piece of software.

Data Centres

October 9, 2026
Patrick Ferris

The talk on hyperscalar data centres presented some great work from the folks at Action to Protect Rural Scotland (APRS). With some serious energy projections:

This gives an estimated around 7,306 MW currently in the planning system or in pre-application consultation. Peak winter electricity demand in Scotland is just over 4,000 MW.

It seemed like the feeling in the room was that these data centres are inevitable, in spite of these jarring numbers; and that somewhere down the line, the ends will be just so good, that the means will be justified.

It seems, once again, I must reach for Pete Seeger.

Perhaps the biggest change will come when we don't have to change much at all When maniacs holler "grow, grow, grow, grow!"; we can choose to be small.

Vulnerabilities

October 9, 2026
Patrick Ferris

I don't think this needs too much explaining, but visit Daniel Stenberg's mastodon feed and that will catch you up. Edit: I wanted to also add a more recent post from Daniel highlighting the other work of the core curl team.

Conclusion of sorts

October 9, 2026
Patrick Ferris

Unfortunately, I missed a good portion of the final session as I was helping clear up. The talks were: "The cost of Sovereignty", "Knowledge Graphs for Digital Transformation" and "You can't download trust".

I managed to have a good chat with Phil Weir, director of Flax and Teal, about some of their work including Alizarin, a tool for working with knowledge graphs and Arches data. It was refreshing to hear about the details of an actual project someone was building.

Ultimately, I would say the day left me disheartened for the immediate future of (open-source) software. What I found most unsettling about SOOCon is what I find unsettling about the tech industry at large. It would seem that the industry is leaving new graduates in the lurch. Additionally, environmental concerns are falling somewhere (far?) below commerical concerns.

I'm also anxious that open source's ethos is being eclipsed by the need for companies (and individual employees) to demonstrate their relevance in an AI-focused economy, and that that performance of relevance is really about integrating, into whatever you're doing, the products coming out of a few powerful companies, which are not invested in the values which make open source make sense.

I think conferences like State of Open are important, and we need more conversations from all kinds of open-source community members. I'd like to see more talks from students, sole maintainers of highly depended-on software, folks from other non-profit-driven open-source initiatives like Outreachy or the Processing Foundation (these are just examples I know). I recognise that, perhaps, SOOCon26 Belfast was suffering from being in Belfast, hardly the most connected metropolis in the world... but it is the home of The Big Fish. I'm excited to hopefully see it return in the years to come.

My friends, Maddie and Emma, enjoying the splendour of Belfast!

Thanks to Meredith, my partner, for helping me edit this and form some much more coherent ideas.

Part II Projects

October 9, 2026
Patrick Ferris

After some super-human administration by Anil Madhavapeddy, I have closed this week with three part II projects to supervise.

An Embedded DSL for Querying OpenStreetMap [part-ii-edsl-osm]

Matthew Occleshaw

This project, originally conceived by Anil Madhavapeddy, hopes to make it easier to answer questions like "What is the safest route to Pembroke College from Cambridge train station?". Here, "safest", can have lots of meanings: the best lit road, a route with tactile paving or accessible pedestrian signals etc.

In addition to this, we may wish to provide suggestions for how to improve the current folksonomy of information OSM stores.

From OCaml to Graphics Shader Languages [part-ii-shaders]

Rohan Wadhawan

This project wants to reuse OCaml's typechecker to provide a safe way to create graphics shaders. As an extension, a ppx rewriter will provide a translation layer from OCaml to the embedded DSL making it possible to write shaders in a subset of the OCaml language.

When interacting with the GPU for graphics programming, parts of the rendering pipeline are written as standalone shader programs. The standard method of using these is to store the shader source code as a string, which is then compiled at runtime by the GPU driver. This is not a performance issue, as shader programs are usually small enough that compilation time is negligible. However, it does mean simple syntax errors or incorrect types, which would normally be caught at compilation, won’t manifest until the entire program is run.
I propose a new library, Shaders_of_ocaml, allowing for shader programs to be written inline as native OCaml, which is then compiled to shader code strings to be passed to the existing graphics libraries. This would allow the OCaml compiler to provide type checking for every shader written.
-- From Rohan's Proposal

Ripple: An OCaml Library for Incremental Computation [part-ii-incr]

Boris Hall

The core of this project is to implement an eDSL and a runtime in OCaml for self-adjusting computation. I also propose a new TDT which allows for generic monoidal folds over modifiable sequences: the library will include a native foldMap primitive that allows performant reduction over a modifiable sequence of modifiable values for any general monoid, giving logarithmic updates with a small trace. I will then compare foldMap to the generic fold implemented in plain SAC.
-- From Boris' Proposal

Ppxlib

October 9, 2026
Patrick Ferris

Just a quick footnote about [Ppxlib]: I opened a PR tomerge multiple instances of a deriver. I threw together this OCaml script for checking implementation and interface files. Running it on Forester, it picked up two instances which can be avoided.

open Ppxlib

let attr_compare (a1 : attribute) (a2 : attribute) =
  String.compare a1.attr_name.txt a2.attr_name.txt

let has_derivings_recursively =
  object
    inherit [bool] Ast_traverse.fold as super

    method! structure_item s acc =
      match s.pstr_desc with
      | Pstr_type (Recursive, (_ :: _ as tds)) ->
        let attributes =
          List.fold_left (fun acc td -> td.ptype_attributes @ acc) [] tds
        in
        let uniq = List.sort_uniq attr_compare attributes in
        List.length attributes <> List.length uniq || super#structure_item s acc
      | _ -> acc

    method! signature_item s acc =
      match s.psig_desc with
      | Psig_type (Recursive, (_ :: _ as tds)) ->
        let attributes =
          List.fold_left (fun acc td -> td.ptype_attributes @ acc) [] tds
        in
        let uniq = List.sort_uniq attr_compare attributes in
        List.length attributes <> List.length uniq || super#signature_item s acc
      | _ -> acc
  end

let main f =
  let is_ml = Filename.extension f = ".ml" in
  let is_mli = Filename.extension f = ".mli" in
  let kind =
    if is_ml then Some Ppxlib_private.Utils.Kind.Impl
    else if is_mli then Some Intf
    else None
  in
  match kind with
  | None -> Format.eprintf "Skipping %s@,%!" f
  | Some kind -> (
    match Driver.load_input ~kind ~relocate:false ~input_name:f f with
    | Error (e, _) ->
      Format.eprintf "Input err %a: %s" Location.print (Location.Error.get_location e) (Location.Error.message e);
      exit 127
    | Ok (_, _, Impl s) ->
      if has_derivings_recursively#structure s false then
        Format.printf ">>> Maybe fix: %s@,%!" f
      else ()
    | Ok (_, _, Intf s) ->
      if has_derivings_recursively#signature s false then
        Format.printf ">>> Maybe fix: %s@,%!" f
      else ())

Note, that given the implementation of attr_compare, this will be an overapproximation.

Shells, SOOCon26 and Part IIs [weekly-2026-w41]

October 9, 2026
Patrick Ferris

Uniform Representations [uniform-repr]

October 12, 2026
Patrick Ferris

State of Open Conference 2026 -- Belfast [soocon2026-belfast]

October 9, 2026
Patrick Ferris
https://stateofopencon.com/belfast-soocon26/

AI: Productivity

October 9, 2026
Patrick Ferris

AI: Community, Data Centres and Vulnerabilities

October 9, 2026
Patrick Ferris

The post-lunch session included a talk about the future of community open source, a talk about AI data centres and finally a panel about the "vulnpocalypse".

Data Centres

October 9, 2026
Patrick Ferris

The talk on hyperscalar data centres presented some great work from the folks at Action to Protect Rural Scotland (APRS). With some serious energy projections:

This gives an estimated around 7,306 MW currently in the planning system or in pre-application consultation. Peak winter electricity demand in Scotland is just over 4,000 MW.

It seems, once again, I must reach for Pete Seeger.

Perhaps the biggest change will come when we don't have to change much at all When maniacs holler "grow, grow, grow, grow!"; we can choose to be small.

Vulnerabilities

October 9, 2026
Patrick Ferris

Conclusion of sorts

October 9, 2026
Patrick Ferris

My friends, Maddie and Emma, enjoying the splendour of Belfast!

Thanks to Meredith, my partner, for helping me edit this and form some much more coherent ideas.

Part II Projects

October 9, 2026
Patrick Ferris

After some super-human administration by Anil Madhavapeddy, I have closed this week with three part II projects to supervise.

An Embedded DSL for Querying OpenStreetMap [part-ii-edsl-osm]

Matthew Occleshaw

In addition to this, we may wish to provide suggestions for how to improve the current folksonomy of information OSM stores.

From OCaml to Graphics Shader Languages [part-ii-shaders]

Rohan Wadhawan

When interacting with the GPU for graphics programming, parts of the rendering pipeline are written as standalone shader programs. The standard method of using these is to store the shader source code as a string, which is then compiled at runtime by the GPU driver. This is not a performance issue, as shader programs are usually small enough that compilation time is negligible. However, it does mean simple syntax errors or incorrect types, which would normally be caught at compilation, won’t manifest until the entire program is run.
I propose a new library, Shaders_of_ocaml, allowing for shader programs to be written inline as native OCaml, which is then compiled to shader code strings to be passed to the existing graphics libraries. This would allow the OCaml compiler to provide type checking for every shader written.
-- From Rohan's Proposal

Ripple: An OCaml Library for Incremental Computation [part-ii-incr]

Boris Hall

The core of this project is to implement an eDSL and a runtime in OCaml for self-adjusting computation. I also propose a new TDT which allows for generic monoidal folds over modifiable sequences: the library will include a native foldMap primitive that allows performant reduction over a modifiable sequence of modifiable values for any general monoid, giving logarithmic updates with a small trace. I will then compare foldMap to the generic fold implemented in plain SAC.
-- From Boris' Proposal

Ppxlib

October 9, 2026
Patrick Ferris

open Ppxlib

let attr_compare (a1 : attribute) (a2 : attribute) =
  String.compare a1.attr_name.txt a2.attr_name.txt

let has_derivings_recursively =
  object
    inherit [bool] Ast_traverse.fold as super

    method! structure_item s acc =
      match s.pstr_desc with
      | Pstr_type (Recursive, (_ :: _ as tds)) ->
        let attributes =
          List.fold_left (fun acc td -> td.ptype_attributes @ acc) [] tds
        in
        let uniq = List.sort_uniq attr_compare attributes in
        List.length attributes <> List.length uniq || super#structure_item s acc
      | _ -> acc

    method! signature_item s acc =
      match s.psig_desc with
      | Psig_type (Recursive, (_ :: _ as tds)) ->
        let attributes =
          List.fold_left (fun acc td -> td.ptype_attributes @ acc) [] tds
        in
        let uniq = List.sort_uniq attr_compare attributes in
        List.length attributes <> List.length uniq || super#signature_item s acc
      | _ -> acc
  end

let main f =
  let is_ml = Filename.extension f = ".ml" in
  let is_mli = Filename.extension f = ".mli" in
  let kind =
    if is_ml then Some Ppxlib_private.Utils.Kind.Impl
    else if is_mli then Some Intf
    else None
  in
  match kind with
  | None -> Format.eprintf "Skipping %s@,%!" f
  | Some kind -> (
    match Driver.load_input ~kind ~relocate:false ~input_name:f f with
    | Error (e, _) ->
      Format.eprintf "Input err %a: %s" Location.print (Location.Error.get_location e) (Location.Error.message e);
      exit 127
    | Ok (_, _, Impl s) ->
      if has_derivings_recursively#structure s false then
        Format.printf ">>> Maybe fix: %s@,%!" f
      else ()
    | Ok (_, _, Intf s) ->
      if has_derivings_recursively#signature s false then
        Format.printf ">>> Maybe fix: %s@,%!" f
      else ())

Note, that given the implementation of attr_compare, this will be an overapproximation.

Part II Students 2026 [part-ii-2026]

September 10, 2024

This year I am excited to be the day to day supervisor for three quite different projects. All implemented in OCaml of course!

An Embedded DSL for Querying OpenStreetMap [part-ii-edsl-osm]

Matthew Occleshaw

In addition to this, we may wish to provide suggestions for how to improve the current folksonomy of information OSM stores.

Ripple: An OCaml Library for Incremental Computation [part-ii-incr]

Boris Hall

The core of this project is to implement an eDSL and a runtime in OCaml for self-adjusting computation. I also propose a new TDT which allows for generic monoidal folds over modifiable sequences: the library will include a native foldMap primitive that allows performant reduction over a modifiable sequence of modifiable values for any general monoid, giving logarithmic updates with a small trace. I will then compare foldMap to the generic fold implemented in plain SAC.
-- From Boris' Proposal

From OCaml to Graphics Shader Languages [part-ii-shaders]

Rohan Wadhawan

When interacting with the GPU for graphics programming, parts of the rendering pipeline are written as standalone shader programs. The standard method of using these is to store the shader source code as a string, which is then compiled at runtime by the GPU driver. This is not a performance issue, as shader programs are usually small enough that compilation time is negligible. However, it does mean simple syntax errors or incorrect types, which would normally be caught at compilation, won’t manifest until the entire program is run.
I propose a new library, Shaders_of_ocaml, allowing for shader programs to be written inline as native OCaml, which is then compiled to shader code strings to be passed to the existing graphics libraries. This would allow the OCaml compiler to provide type checking for every shader written.
-- From Rohan's Proposal