Journal entry for

While out hiking in Madeira I had an idea to solve a problem with my “straightforward purely functional Paxos” implementation. The idea could be summarized as “inserting effects into clean/pleasing program definitions without changing the definition”.

The issue with my Paxos explorations is that Paxos is a sequence of voting rounds, but if you have a voting algorithm you cannot use those directly in your Paxos implementation. Instead, you have to rewrite your voting rounds to exfiltrate some state at each of the voters. The vote influences the state at the voters (e.g. highest round seen), and also at the vote requester (e.g. any previous accepted value + round number).

What if you could just keep that original definition of your voting algorithm, but insert some tell’s at the appropriate places to get the information you need?

Collatz conjecture example

I thought a simpler example could feature the Collatz Conjecture. The algorithm is easily written as a function:

collatz n =
  if n == 1
  then 1
  else if (even? n)
       then n / 2
       else 3 * n + 1

The conjecture is that this algorithm will always terminate with n = 1 for any n > 1.

Suppose that you’re naive and think you can solve the conjecture, or you’re just exploring the problem space a little bit. You could rewrite this definition each time you want to explore something about the algorithm, e.g. looking at the sequence of n values it goes through, or collecting all the primes, etc.

If you want to get the sequence of values, you’d have to rewrite it as follows:

collatzSeq n =
  if n == 1
  then [n]
  else n : (collatzSeq (if n == 1 then ...))

But what if instead of doing that you could just say “collatzSeq is collatz but at at the top level if add a tell [n] effect”?

Random notes

A good implementation would ensure hygiene for identifiers so that you can get at shadowed variables etc.

The more order-independent your effect is the better as well, because then you don’t have to worry so much about evaluation order. If you want to do this in layers/compositionally then all effects need to compose in any order as well.

Also, this is once again an example of where our text-based programming model is so much worse than programming in an interactive GUI environment would be. In that case you could simply point at the expression you want to attach an effect to, and you wouldn’t need to find a scheme to identify parts of a program definition textually.

More examples?

The problem with Paxos is that I’d have to explain Distributed FRP; that would be a lot.

The best examples would be algorithms which are built up from simpler components, which are individually useful, but where you normally have to re-write the component to exfiltrate some information. Or maybe where people usually complicate the definition of the component because they know it’s going to be used by something else.

Maybe some graph algorithms have similar structure?

Implementation

I found Tomas Petricek’s paper on Evaluation strategies for monadic computations. I think this describes a way to turn arbitrary lambda terms into ones that are evaluated in a monadic context. This I suspect would work well for the problem above.

This idea made me think of Aspect-Oriented Programming which you could also interpret as wanting a clean model of some program and doing the dirty business by defining aspects which attaching to methods of the model.

This is of course limited to methods, while the idea above is much more general.