underlap

No this isn't about the 2004 tear-jerker film. It's about using an actual, physical notebook (and, no, I don't mean a laptop computer either). I've been using two kinds of notebooks for decades: technical notebooks and journals.

The advantages of a physical notebook are pretty obvious. Even though I can touch-type, it's quicker to write notes in longhand than use a keyboard (especially when it comes to mathematics) and much quicker to draw diagrams. A physical notebook doesn't need charging and is devoid of distractions, unlike electronic devices. I can easily highlight things, connect ideas with arrows, make marginal notes, scribble questions, and add annotations.

The main apparent downside of using a physical notebook is the relative lack of editability compared to text on a computer. But this doesn't matter because my notebooks capture thoughts on a particular date and I hardly ever update them. If I'm drafting something, I use pencil, but once I've finished, I rarely go back and change pencilled entries.

My technical notebooks

I've long since used a notebook¹ when developing software. It helps me particularly when learning about the problem domain or getting my head round how possible dependencies work.

I also like to write up rough thoughts on the design of a piece of software, using text, mathematics (often partial Z specifications), or diagrams. Seeing my rough thinking on paper helps me process my thinking. I can leave gaps and come back and fill them in later. It's also really helpful in resuming a train of thought after an interruption.

I dutifully discarded 26 years worth of notebooks when I left IBM because they contained some company confidential material. However, I kept the notebooks that I used since then. Here's a flavour of their contents:

Notebook 1: Nov 2008 to March 2009: OSGi and the development of an application platform based on OSGi modules and hosting applications constructed from OSGi modules.

Notebook 2: March 2009 to August 2011: Continuation of OSGi and the application platform. Donation of the platform to Eclipse as the Virgo project. Virgo development.

Notebook 2: August 2011 to January 2018: Continutation of Virgo development. Early days of Pivotal and Cloud Foundry development and how Virgo might fit into that. Pivotal's eventual move away from Virgo. Buildpacks and warden/garden container manager development, including investigation of Linux control groups and namespaces. Spring Cloud Services. The jvmkill plugin and porting it from C++ to Rust (including extending bindgen).

Notebook 4: January 2018 onwards: Pivotal Function Service and Kubernetes. Riff is for functions. Collaborating on the “Elafros” project from Google (which became Knative), particularly on the autoscaler component. Image relocation. Collaboration with Microsoft and others on CNAB. Integration of image relocation into the the sheaf utility and, as a consequence, the need for a JSONPath specification. JSONPath spec development. Retirement! Teaching a university module on functional programming in Haskell. Modelling JSONPath non-determinism in Haskell. NGINX robot access module. Open development experiment.

I settled on my preferred physical format of notebook: A4, spiral-bound. I can open one of these up and lay it flat or fold it back on itself and occasionally turn it to landscape format for drawing large diagrams. I prefer lined paper because my writing tends to get messy when taking notes on blank paper, although blank paper would be better for diagrams.

After my recent open development experiment, how does using a technical notebook compare to writing blog posts? Although I tend to write notes when I'm developing something, I don't necessarily want to polish them for publication. The ability to jot down half-formed, or even incoherent, thoughts is a great freedom compared to writing up my thoughts for consumption by others. I'm free from possible criticism (except by myself) and I'm free to ditch ideas, change tack, and so forth.

My journals

I've been journaling, highly sporadically for nearly thirty years. I'm not going to get into the contents of my journals². Suffice to say they are reflective and deeply personal. Perhaps it's not surprising that I'm more inclined to look back at old journals than old technical notebooks.

See Joan Westenberg's recent article The Art of Not Sharing for more on journaling.

Conclusion

Notebooks help me on at least three fronts:

• Learning
• Working out what I think
• Helping me restart a task after interruption.

I don't yet carry a notebook with me however. Signal's “Note to self” feature is a convenient way to capture thoughts when I'm out and about.

#SoftwareDevelopment #SoftwareDesign #Journaling

---

Postscript

My friend and fellow blogger Henrik Jernevad wrote Notebooks no more in response to this post. He describes why he switched away from physical notebooks to, in his case, Obsidian.

I certainly see the advantages of (internal and external) linking and searching. I number my journal pages for indexing, especially of retreat days. But apart from that, I haven't really found a need to search my technical notebooks. Because my journaling is so sporadic, there aren't that many pages to look through when I very occasionally want to refer back to something I wrote in a journal. In fact, I'm more inclined to flip through a journal seeing what was going on in my life over a particular period than to think of something I want to search for.

I've also tried software alternatives, including Obsidian and Logseq, but there's something about the physical act of writing which, for me, gives it the edge. Also, there's something about the current page of a technical notebook which gives me better perspective, psychological “distance” if you like, from the task of writing software than a software alternative (which is just another window or tab on my desktop, competing with the task in hand for focus).

We are all different. Each to his and her own.

---

Footnotes:

¹ My preferred technical notebook is A4 spiral-bound which can be laid flat or folded back on itself, e.g. the Pukka Pad Jotta with 200 lined pages in a cardboard cover.

² My preferred format for personal journals is a Moleskine classic notebook, although I've also used A5 spiral-bound notebooks in the past:

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

Today I managed the rather fiddly operation of removing the glove box in my car, replacing a blown fuse, and refitting the glove box. So, being on a roll, I thought I'd replacing the SSL certificate of this site, which was due to expire in a couple of weeks.

It was easy to create a new certificate using the management web UI provided by my domain name registrar. But then I wanted to install the certificate on my VPS.

Setting up a writefreely instance reminded me roughly what was involved last time. I needed to create a chained certificate because one of the intermediate certificates was missing.

So I downloaded the files for the new certificate from my domain name registrar:

• certificate
• private key
• zip file containing two intermediate certificates.

So I needed to figure out which, if any, of these intermediate certificates I needed to add to my certificate to form a chained certificate. Since there were two intermediate certificates, I thought I'd add them both, but needed to work out the correct order.

Piping each of the certificates into openssl x509 -text in turn showed that:

• underlap.org_ssl_certificate.cer (my server certificate) was issued by Sectigo Limited
• intermediate1.cer for Sectigo Limited was issued by The USERTRUST Network
• intermediate2.cer for The USERTRUST Network was issued by Comodo CA Limited.

So I constructed a chained certificate by concatenating the contents of underlap.org_ssl_certificate.cer, intermediate1.cer, and intermediate2.cer in that order.

After installing these in my VPS and checking that my blog was accessible from a web browser and Mastodon could still navigate to the profile of @glyn@underlap.org, I declared success.

#colophon

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

An experienced programmer friend of mine is finally going to get to use Rust in his work. He asked me about resources for learning the language.

Online books

I like mdbook format books and there are many available on Rust and its applications. Since there wasn't a convenient catalogue of such books, I produced The Little Book of Rust Books (LBORB) in January 2021. The community has helped extend and maintain it since then.

The list of official books in LBORB includes two particularly good ones for beginners:

• Rust by Example – runnable examples illustrating Rust concepts. This seems particularly useful for experienced programmers as the examples can be edited and run.
• The Rust Programming Language – “the book”, which gives a careful explanation of Rust's features.

After that, the list of official books includes an “advanced” section that my friend will surely soon be consulting.

Practice

When I learned Rust several years ago, it took a couple of weeks to get used to the borrow checker – the part of the compiler than deals with memory ownership. I'd written code in lots of languages before, including C++ and assembly language, so I was expecting Rust's ownership rules to be reasonably intuitive.

When I wrote C++, for example, one crucial skill was being clear about the ownership of any piece of allocated memory. I needed to define the rules when returning allocated memory from a function. For instance, was it up to the caller to free the memory or did it need to be passed in to another function to be deallocated?

However, I found that Rust was much stricter (and safer) than vanilla C++. I could write code that initially seemed ok to me and find it wouldn't compile. I ended up “fighting” the borrow checker. This seems to be a common experience.

One solution is to resort to using smart pointers. Another is to copy memory around willy-nilly. But these solutions don't really work with the “grain” of the language. For that, it's important to rework code so that the borrow checker no longer complains.

I think the best way to learn this is to practise writing some Rust code, e.g. Rustlings or “Advent of Code” solutions, and then create a side project or contribute to an existing codebase to work with more “realistic” code.

Depending on your preference and learning style, sooner or later you'll also want to read Understanding Ownership in “the book” or Rust Ownership the Hard Way to firm up your understanding.

Is that it?

Those are the main tips I am giving my friend. Oh and to use the wonderful rustup to install the toolchain if he hasn't already done that.

#Rust

---

Postscript: The original post didn't mention Rustlings, but a couple of people recommended it and it looks really good. I even gave Rustlings an honourable mention in LBORB, in spite of it not being an actual book.

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

Here are some of my ethical concerns about social media and some other sites and tools.

Avoiding Facebook

I have severe misgivings about Facebook:

1. It has been shown to impact people's mental health, causing loneliness, anxiety, fear of missing out, social comparison, and depression. See A Psychiatrist's Perspective on Social Media Algorithms and Mental Health, Tammy Qiu, Stanford University, 2021.
2. It has failed to act to prevent the abuse of human rights. See The Facebook Papers: What do they mean from a human rights perspective?, Amnesty International, 2021 and Facebook says Chinese hackers used platform to hack Uyghurs abroad, Kevin Collier, NBC News, 2021.
3. It collects users' private information (including tracking their web browsing activity), uses that information for its own purposes, and shares some of the information with others. See Meta Privacy Policy, accessed November 2024.
4. It continues to fail to prevent the propagation of certain types of fake news. An acquaintance of mine with mental health issues has been taken in by conspiracy theories circulating on Facebook. See Misinformation, Meta Transparency Center, accessed November 2024.

Avoiding Twitter

I deleted my Twitter account before deleting my Facebook account. Since then I understand that X/Twitter moderation has gotten significantly worse.

Avoiding Reddit

I deleted my Reddit account after the company effectively crippled third party moderation tools and disenfranchised much of its moderator community.

However, some user communities, e.g. Haskell, have stuck with Reddit. r/haskell has 80K members, who presumably hold their noses.

Avoiding LLMs

LLMs ignore copyright and have a high carbon cost to train and use.

Apart from avoiding using LLMs, I block the AI web crawlers in a community-maintained list using my own nginx module, as I described in an earlier post.

Tolerating Instagram

I tolerate Instagram mainly because I see photos of my grandchildren there and it tells me when I've seen everything new from those I follow. But I rarely post.

Tolerating Threads

The jury is out until Threads implements ActivityPub federation fully as well as supporting easy account migration (from Threads to elsewhere).

Tolerating Bluesky

The jury is again out. See Bluesky and enshittification, Cory Doctorow, November 2024.

Tolerating GitHub

Although I don't approve of Copilot scraping my open source repository contents, there's just too much inertia for me to move off GitHub any time soon. The service provided by GitHub is superb. After writing this post, I'll certainly consider hosting my next repository on codeberg.org or similar.

Ethics and this site

The main ethical consideration for this site is privacy.

As stated in the about page:

This site does not collect any information about visitors except for the total number of views of each post.

As part of the ActivityPub support, the blog records the ActivityPub identity of anyone who follows it, so they can be notified of new posts.

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

List of posts in this series

In the previous post I defined the ordering function and found an implementation I could reuse. This was both good news and bad news: good news because someone else had already done the work of implementing an ordering function using a Feistel network, but bad news because I didn't get to have some fun writing bit-twiddling code.

In this eleventh and final post of the series, I'll reflect on the outcome of the experiment and also on what I've learned about truly open development.

Admittedly the experiment was small and bounded. But it was also non-trivial and interesting. The outcome was a fairly typical trade-off between writing new code and reusing someone else's.

What were the downsides of reusing another implementation?

Apart from not getting to write more code, the main downside was that the code wasn't quite what I would have written myself. The code was clean and understandable and had good documentation.

But I wouldn't want to ship code that panics when presented with invalid inputs. An interface is often used quite differently from how I expect. If I make sure that error handling is explicit in the interface, then it encourages all code calling the interface to handle errors suitably. The using code might panic, but at least the panic will point to the code that needs fixing.

That said, I was able to wrap the code in a clean interface that returns errors rather than panicking. That was fine because my performance requirements weren't too exacting. A URL shortener would call the ordering function just once per request to shorten a URL (and wouldn't call it at all when mapping a shortened URL to the original URL). There's a little extra complexity in maintaining a wrapper, but not much and certainly less than maintaining the ordering function itself.

Then there was a part of the code that I didn't understand: a test that the permutation was pseudorandom. I spent a while searching for information on testing pseudorandomness in terms of a triangular distribution, but couldn't find anything. However, this test is unlikely to cause trouble. In the worst case, it might fail if the permutation implementation was changed significantly. But in that case, the project owner would almost certainly change the test to make it pass.

What were the upsides?

The main upside was having a clean implementation with good documentation and decent tests, but with minimal effort.

Also, if I'd written my own code, it may well have remained a solo effort. But by reusing someone else's code, at least two pairs of eyes have looked over it carefully.

Then there's maintenance. If bugs are found, there's a good chance someone else will fix them. Maintaining my wrapper would be very straightforward. I'd just have to decide if and when to bump the dependency to pick up changes.

I also felt I added a little value to the reused code by proving the correctness (see the previous post) of part of it which wasn't obviously correct (at least to me).

What about the experiment as a whole?

I enjoyed the process of writing up my thinking as I went along. I don't mind working quite slowly on projects these days as I'm doing them for fun and personal satisfaction rather than for an employer and on a schedule.

Parts of the process were quite tricky to write down in real time. When I was mulling over the requirements and design, I had to force myself to write down some things that would turn out to be dead ends. If instead I'd written just one post after the project was complete, it wouldn't have had so many lose ends. But hopefully that gives readers a more realistic impression of the way I work.

Insights into the way I work

I go off on tangents occasionally. The commit history of my code describes just a small part of my development process. This was always the case throughout my career. My goal was to grow my understanding and skills as well as deliver working software. This approach helped make even the dullest piece of work enjoyable and thereby helped me do it well.

Going off on tangents is also about the way I learn: I need to explore aspects of a problem that interest me. I find skipping over things I don't understand deeply unsatisfactory. I guess that tended to take the edge off my raw productivity, but it also increased my longevity.

Would I repeat the experiment?

Probably not. Although I tend to write stuff down as I go along, I wouldn't necessarily want to polish the material for publication. In fact, I think going back to using a physical development notebook is preferable. The ability to work in pencil, draw rough diagrams, scribble questions, and jot down half-formed thoughts is a great freedom compared to writing up my thoughts coherently for consumption by others.

Conclusion

Working in a completely open way — by which I mean publishing my thinking as I go along, as in this experiment — certainly influences the development process and the ultimate outcome, but I'm not sure these effects will always be positive.

The extra time investment represents inertia that could reduce the chances of switching to a better design or feeling free to make certain kinds of improvement. Perhaps a sweet spot would be to keep notes as I go and use these as the basis for a blog post if that seems appropriate.

#OpenDevelopment

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

List of posts in this series

After reviewing the state of play in the previous post, I'm now going to start defining an ordering function in code. First I need to decide where to put the code.

Code repository

I took a closer look at the URL shortener repository. The code to generate a new short link simply returns a random adjective separated from a random name by a hyphen, e.g. “clever-knuth”. No state is maintained except for a database mapping previously generated short links to their original, unshortened URLs.

So there is actually very little in the URL shortener's repository of relevance to the ordering function I want to develop. To focus on the task at hand, I decided to create a new repository. I might eventually port some code back to my fork of the URL shortener repository, but I'll think about that later.

Repository name

As Leon Bambrick quipped, there are only two hard problems in computer science: cache invalidation, naming things, and off-by-1 errors. I want a repository to host the ordering function. I don't want to tie the name to the specific application of URL shortening, especially as the ordering function will be much more general purpose than that. I'll probably use a Feistel network, but that's an implementation choice, so I don't think Feistel network should necessarily appear in the name. So what will the ordering function actually do? It will permute a range of integers.

After searching crates.io for “permute” and “permutation”, just in case that turned up an existing piece of code, I settled on a repository name of range-permutation-rs (the “-rs” suffix is a convention indicating Rust code).

Setting up the repository

If you're happy setting up a git repository with Rust content, you may wish to skip this section.

I created the repository in a new directory, with the usual empty commit:

mkdir range-permutation-rs
cd range-permutation-rs
git init
git commit --allow-empty

I then set up a remote repository and pushed the main branch up.

Before I get into Rust, I populated the repository with some basic documentation: a README, a LICENSE, code of conduct, and contributor guide. This probably seems over the top, but I think it's good practice to take 10 minutes to set these things up early, so anyone who comes across the repository knows the ground rules. I also added a .editorconfig file to set my default editor conventions and try to ensure some consistency between editors.

I intend the repository to be a library, so I then checked my Rust toolchain was up to date and used cargo to initialise the Rust side of the repository:

rustup update
cargo init --lib --name range-permutation --vcs git

The option --vcs git does not affect the existing git repository, but adds a suitable .gitignore file listing just /target.

Defining an interface

I want to start off with a very simple interface: a function that takes the size of the range and returns an ordering function that permutes integers in the specified range. What does this look like in Rust?

I want to separate out the creation of the permutation function from the function itself, because I want to develop some generic tests of the permutation function and I expect the creation function to become more complicated over time (e.g. to take a key which will act as a randomisation seed).

The creation function will take an integer to set the size of the range. The permutation function will take an integer in the range and return another in the range. I expect the permutation function not to mutate any internal state, so it will be a pure function with no side-effects. I looked at some ways of representing an integer in a range in Rust, but decided that they didn't make the functions any clearer. So I ended up with this:

pub fn create(size: u64) -> impl Fn(u64) -> Result<u64, &'static str> {
    ...
}

This is admittedly quite busy, especially if you're not used to Rust. Let's go through it in detail.

The input parameter size is an unsigned 64-bit integer specifying the size of the range we want to permute.

The return type of create is the Rust way of specifying a function that takes an unsigned 64-bit integer and returns a result which contains either an unsigned 64-bit integer (in the successful case) or a string error message (when the input is outside the range).

As a placeholder, I made the permutation function simply return its input value, wrapped in Ok(), or an error if the input was out of range.

Docs and tests

Next I wrote some documentation, with a simple example, and some tests and checked the example and tests passed.

Good news, bad news

While I was writing the docs, I had another look at Tom Conway's feistel-permutation-rs repository. After he merged my PR to add an open source license, I was delighted to find he had written up a very clear README.

In fact, his code pretty much meets my requirements for an ordering function. I could press on with my own implementation, but my motivation has disappeared. Indeed, to write my own code would amount to NIH (“not invented here”).

Apologies to anyone who was hoping to see me develop some Feistel network code from scratch in Rust. The good news is you can now read Tom's clear and well-tested code, which I'll explore further below. The bad news (kind of) is that I enjoy writing bit-twiddling code, but now I'm not going to have the pleasure.

Implementing in terms of feistel-permutation-rs

One aspect where feistel-permutation-rs didn't match my ideal interface was the way it handled a range of numbers. The permutation (get) function asserts that the input value is in the relevant range. The effect is that the code panics if an out of range value is passed to get. I prefer to return an error rather than panic.

So I implemented my ordering function in terms of feistel-permutation-rs, like this:

pub fn create(size: u64, seed: u64) -> impl Fn(u64) -> Result<u64, &'static str> {
    let perm = Permutation::new(size, seed, DefaultBuildHasher::new());
    move |n| {
        if n >= size {
            Err("out of range")
        } else {
            Ok(perm.get(n))
        }
    }
}

As expected, I added the key or pseudorandom seed to the signature of create.

The code above is straightforward, except for the use of move to capture the value of size in the closure, rather than a reference to size. Capturing a reference fails to compile because the lifetime of the closure exceeds the lifetime of size. In other words, size goes out of scope and cannot be referred to afterwards.

With this code, it's not surprising my tests passed. So let's take a look at Tom's code.

A Feistel network: feistel.rs

The core of feistel-permutation-rs is a Feistel network with a user-specified round function, a range, and a key schedule.

The range (of values to be encrypted) is specified as an even number of bits, so that values in the range can be split into left and right portions with the same number of bits.

The round function is applied on each iteration, or “round”, of the Feistel network and is a way of making the order of the results pseudorandom. The inputs to the round function are an encryption key (described next) and the right portion of the data being encrypted. The round function is supplied via a hash function builder (conventionally named “bob” – geddit?).

The key schedule is a vector of encryption keys which are passed in turn to the round function. The number of rounds is determined by the length of the vector.

The code is straightforward¹:

pub fn encrypt(&self, x: u64) -> u64 {
    let (mut l, mut r) = self.split(x);
    for k in self.keys.iter() {
        l ^= self.hash(*k, r);
        (l, r) = (r, l);
    }
    self.combine(r, l)
}

The value to be encrypted (x) is split into left and right portions. If the number of bits in the range is 2n the valid range of inputs is 0..2^(2n). Then the input value has 2n significant bits and these are splits into left and right portions, each with n bits.

There are some interesting (at least to me) edge cases. It's perfectly valid to specify a range of 0 bits which will then encrypt just one value (0).

It's also valid to provide an empty vector for the key schedule, in which case the encryption will be the identity function.

Crucially, the encrypt function permutes the range. The body of the for loop is clearly invertible (one-one) and it follows that so is encrypt. Since all the values of the range are mapped to distinct values, also in the range, encrypt is onto. In other words encrypt is a bijection from the range to itself, i.e. a permutation.

Arbitrary range permutation: permutation.rs

feistel-permutation-rs builds on the Feistel network to create a permutation of an arbitrary unsigned 64-bit range.

The first step is to build a key schedule of five keys from a single input seed. The first key in the schedule is the hash of the input seed. Each subsequent key is the hash of the previous seed. This relieves the user of the responsibility to provide a complete key schedule.

The second step is to obtain a permutation of an arbitrary range by taking the next even power of 2 higher than the size of the range and using a Feistel network with the corresponding number of bits.

This is combined with an algorithm that applies the Feistel network encryption and, if the encrypted value exceeds the range, keeps on applying the Feistel network encryption until the encrypted value falls in the range. The code looks like this:

pub fn get(&self, x: u64) -> u64 {
    assert!(x < self.n);
    let mut res = self.feistel.encrypt(x);
    while res >= self.n {
        res = self.feistel.encrypt(res);
    }
    res
}

To see that this provides a permutation of the range 0..n, first observe that all the results are in the range. Secondly, let's prove get() is one-one.

Proof

(The proof was formatted with Typst. Click here to enlarge.)

permutation.rs also includes an interesting test that the generated permutation is random. I don't pretend to understand the relevant theory, so I wouldn't have included such a test.

Contributions

While reading through feistel-permutation-rs, I made a number of very small contributions by way of pull requests:

• Add Apache 2.0 license – after raising the issue License to discuss first
• Make crate license Apache 2.0 – missed this in the previous PR
• Fix two typos – I also took the opportunity to thank Tom for writing a README
• Assert maximum number of bits – this is quite the edge case, but why not?
• Swap variables using destructuring assignment – a nice little Rust feature clarifies the code

I also raised Fix test which wasn't valid, but which prompted Tom to add the interesting test mentioned above.

Conclusion

By depending on feistel-permutation-rs the ordering function, with my preferred interface, is now complete.

I'll have to think about whether it's worth the effort to use this in the URL shortener. The URL shortener is sufficient for practical use and I'd have to fork the code and add a dependency on the above ordering function. I don't think I could justify making such a substantial change in the upstream repository, so I'd end up with a hard fork.

In fact, as I've been working through this experiment, I've become less keen to support a URL shortener on my site, so I may just ditch it.

But the point of the experiment was to see what it was like doing a piece of development in the open and to have some fun. The actual coding side of the experiment ended up being a lot smaller than expected, but I've enjoyed reusing and analysing Tom Conway's code.

The experiment demonstrates one of the trade-offs in open source development: whether to reuse existing code or write your own. It also demonstrates some of the costs associated with reusing code:

• wrapping reused code to provide a different interface
• analysing the correctness of reused code
• taking some parts of the reused code on trust (the permutation randomness test, which I don't understand).

Footnotes:

¹ The original used a temporary value to swap l and r.

² In mathematical proofs, “without loss of generality” (“WLOG”) is a way of abbreviating a proof by considering just one of a number of very similar cases. Here the cases are symmetric. See WLOG on Wikipedia for more explanation.

#OpenDevelopment #Mathematics

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

List of posts in this series

It's a month since my last post in this series in which I reflected on the interactions this experiment has generated. My wife and I have spent three weeks on a road trip to Italy during which I've only fleetingly thought about the experiment. So as I re-enter, I've got an opportunity to see things from a fresh perspective.

Fresh perspective

One of the challenges of software development is to be able to keep in mind high-level requirements and goals while simultaneously diving down into the detail of algorithms, code, tests, etc.

Having written up some of the high-level requirements in posts for this experiment is a help as I can always go back to those posts if I feel I'm losing sight of the big picture. But there's also the risk that re-reading my earlier thoughts will cause me to miss some new insight. The fresh perspective made possible by a significant break is a precious thing, and I don't want to waste it.

How to proceed?

Since there are eight posts in this series, one option would be to re-read those posts to come back up to speed and then think about what to do next. That's certainly an option, but I may lose the benefit of my fresh perspective.

Another option would be to completely ignore previous posts, start from scratch, and build on what recollections I have. But I doubt that's going to be particularly effective.

Instead, I'm going to work through the posts slowly and, when I get fresh insights, I'll pause, and discuss them below. Let's see how this goes.

Introductory post

In the introductory post, the following jumped out:

I suspect I'll want to plug the algorithm into the existing code, but in such a way that alternative algorithms can be used in future. The idea is to come up with a usable, testable interface to the set of possible algorithms. So designing a suitable interface, in Rust, will be part of the challenge.

I think testing could be tricky, so designing the interface and some tests would be a helpful next step. It could also benefit from my current fresh perspective.

(At this point, I was tempted to start work on the interface, but I suspect I would start to lose the fresh perspective during that task, so I continued to re-read the next post.)

Requirements

The requirements were mostly about the usability — shortness, memorability, unambiguity — of shortened URLs, but also about unpredictability: generating URLs in a pseudorandom order.

I anticipate introducing an interface that returns a pseudorandom permutation of a range of integers, one at a time, and use the returned integer to select a specific shortened URL and then implement that interface (using a Feistel network, or whatever). The URL usability requirements will be satisfied above the interface (i.e. by the code calling the interface) and the unpredictability requirement will be satisfied below the interface (i.e. by the implementation of the interface).

Given the purpose of the experiment is mainly to have fun, I intend to focus on the algorithm (the interesting bit) below the interface and make do with the current format of shortened URLs (the boring bit) above the interface. Once the interface is in place, it should be relatively easy to evolve the code above and below the interface independently should I, or anyone else, wish to do that.

Design

The design post reminded me of already having had the above ideas about a suitable interface! It seems my fresh perspective didn't make me think of a different approach.

To recap, the interface will provide a bijection from the range 1..n to the range 1..n, where n will be the number of possible shortened URLs. A bijection is a function that is one-one (no two distinct inputs produce the same output) and onto (each member of the output range 1..n is generated). This bijection can also be thought of as a permutation.

Having thought of this interface twice seems to be a validation that the approach is reasonable (at least to me). Alternatively, I might be failing to see a better alternative, but there's not much I can do about that right now.

Search for Feistel networks

This post found a couple of Rust open source projects that implemented a Feistel network. Whether I can use one of those or I have to “roll my own crypto” remains to be seen.

Next step?

But for the moment, I plan to look at defining a suitable Rust interface and thinking about how to test it. I have a couple of questions at this stage:

• How easy will it be to map the range 1..n to a Feistel network, given that, as far as I've seen, Feistel networks tends to permute sequence of bits? I suppose in the worst case, I could restrict n to be a power of 2.

• Should the interface take a key as an input, so that the pseudorandom sequence isn't predetermined by the implementation of the interface? The format of the key would seem to be a big design decision.

I'll have to think more about these questions as I start to flesh out the interface, which I'll save for the next post.

#OpenDevelopment

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

(This is a revised version of a post from April 2022.)

A (now defunct) thread on mastodon got me thinking about my experience with concurrent programming. Here's a thumbnail sketch of the approaches I've tried.

The problem

But first, what's the problem? Let's look at three examples of concurrency problems: races, deadlocks, and livelocks.

Races

A prime example of when concurrent code behaves incorrectly is the race. A race occurs when two or more concurrent activities affect the external behaviour of a program and, depending on the ordering of events (e.g. which activity “wins” the race), the external behaviour is different. One example of a race is a data race.

A classic example of a data race is where a bank account is credited concurrently and, because of an invalid algorithm, both credit activities load the same initial account value and the final account value reflects one or other of the the credits, but not, as it should, both.

Deadlocks

A deadlock occurs when two or more concurrent activities enter a deadly embrace and none of them can make progress. Deadlocks can sometimes be mitigated using timeouts, but it's better to avoid deadlocks altogether.

Livelocks

A livelock is when concurrent activities continue indefinitely without making external progress. A livelock is sometimes described as “internal chatter”: something may be going on internally, but nothing useful is achieved. Often a livelock results in high CPU consumption.

Approaches

So, now we've covered the main sorts of concurrency problems, here are the approaches I have tried.

Ad hoc analysis

I think the first approach to concurrency most software developers attempt is trying to think through the problem at hand. Considering all the possible interleavings of concurrent activities at first seems like a tricky, but tractable, puzzle. But, ultimately, this approach comes unstuck on all but the simplest cases. It's possible to persuade yourself you've thought about all the possibilities, until something completely unexpected rears its head and your confidence is (rightly) dented.

Compare-and-swappery

Some of the first concurrent code I wrote involved managing multiple threads of execution using compare and swap instructions. This was hard work, but I wasn't tempted to try anything particularly complex because it was just too hard to reason about. This was before the days of unit testing¹, so developers were used to spending a lot of time thinking about the correctness of code before attempting to run it.

At least with compare and swap code, there is a limited number of possibilities to consider: each compare and swap operation can succeed or fail. This makes ad hoc analysis tempting, but ultimately tricky for all but the simplest cases.

A more general term for compare-and-swappery and similar approaches is lock free programming.

Locking

One way to prevent races is by acquiring and releasing locks, especially around access to shared data. One common locking pattern is a monitor where shared data is protected by locking or some other mutual exclusion technique.

If the duration, or scope, of locks is too large, locking can result in deadlock. One coding convention to avoid such deadlocks is not to make calls to other parts of a program which may obtain their own locks while holding a lock.

To avoid deadlocks, it's sometimes also possible to arrange locks in a hierarchy or to ensure locks are always acquired in a fixed order.

Locking is fine for simple cases, but beyond that, it becomes difficult to reason about.

Model checking

One way of reasoning about concurrent code was to model the behaviour in CSP and then use a model checker like FDR to check various properties. Unfortunately, even relatively simple concurrent code took quite a bit of effort to model in CSP. Also, model checking, even with FDR's amazing “compressions”, tended to take too long unless the state space could be kept manageable. So with this approach I again tended to spend a lot of time thinking, this time about how to structure the CSP model to keep model-checking tractable. The result was I only produced one or two limited CSP models.

I would say the main benefit of CSP modelling is that it makes you aware of the main types of concurrency bugs: deadlock and livelock, described above, and more general kinds of divergence (e.g. where the system spends its time “chattering” internally without making useful progress).

Memory models

Java has various low-level locking mechanisms for managing concurrency. The Java memory model gives a good framework for reasoning about concurrent code in Java. Again the emphasis was on reasoning and it was hard work, but at least there was the sense that it was well founded.

Channels and goroutines

I've used Go a lot and would say goroutines (similar to lightweight threads, sometimes called “Green threads”) and channels are deceptively simple. The principle is that you can safely write to, and read from, a channel in distinct goroutines. It's easy to build concurrent systems that work most of the time, although it's hard to be sure they are bug free. But at least you're better off than in a language which only provides low-level mutexes and such like.

Language support

Rust guarantees safe access to shared data at compile time. The main difficulty is getting used to the constraints imposed by this model and then designing your code appropriately. That said, I haven't written much concurrent code in Rust, so I'll simply defer to the book.

#SoftwareDevelopment #concurrency

Footnote 1: When I did write the occasional unit test, I also deleted it to avoid having to maintain it!

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

List of posts in this series

As a little light relief from the search for, and possible development of, an ordering function, I thought I'd mention some interactions related to this series.

Open source licensing

When I encountered the Rust feistel-permutation-rs crate, I was disappointed there was no license file. I could have called the code in the crate, but if I'd wanted to extend or modify it, the lack of an open source license would have stopped me doing that without infringing the author's copyright.

Thankfully after I raised an issue asking for a license to be added, the author responded positively and was happy to merge a pull request adding an Apache 2.0 license file (and some license headers, a necessary part of applying the Apache 2.0 license). He also added an interesting comment to the issue explaining some of the motivation for the crate (in bioinformatics).

While writing this post, I noticed that the crate appeared to be licensed as GPL-3.0-or-later on crates.io. It turned out this was declared in the Cargo.toml in the git repository for the crate. I submitted another PR to change this to the Apache 2.0 license.

Error handling

While examining the Rust cryptographic_primitives crate, I noticed that it was not clear when some of the errors were returned and also that the code sometimes panicked instead of returning an error.

I raised an issue on the panicking behaviour and the author kindly fixed this to return errors instead. He even went to the trouble of publishing a new version of the crate.

He helpfully explained his view of the likelihood of certain errors being returned and even added some tests to clarify when errors occur.

There is still a certain amount of uncertainty in my mind, so I'm not inclined to use the crate. It didn't feel appropriate to press for more clarity as the author had already been very responsive and helpful and we probably have different opinions on the acceptability of assuming that a highly unlikely error will never be returned¹.

Feedback on posts

There have been a few responses on Mastodon to some of the posts in this series. It's nice to know people are reading the posts and perhaps finding them interesting or helpful.

Introduction to the experiment

I got a couple of responses which encouraged me from the start.

James Ravenscroft wrote:

very cool – looking forward to following along!

while Henrik Jernevad wrote:

Awesome idea! 😊

Requirements

Andy Scott commented:

I enjoyed catching up on this series this morning. Reading about requirements always leaves me thinking more creatively, and now I'm aware of the Feistel cipher ;)

Ordering function

Jeff Slarve offered me an ordering function written in TypeScript. We had a nice interaction about this.

Search for Feistel networks

Tomas Stropus replied:

Oh man, I feel this so hard. This is giving me flashbacks! I recently needed a PELT library for C# and ended up in the same boat – zilch options, so I had to code it myself.

Gotta say, I'm impressed by your patience. I probably would've thrown in the towel and started rolling my own way sooner. But hey, that Cloudproof FPE does sound promising. Curious to hear how it goes when you jump back in.

Next steps

Postscript: after a month's break, the next post turned out to be looking back on the posts so far to get back up to speed.

Footnote:

¹ In my experience, I've found that if something can go wrong, it probably will at some stage in the future. On several occasions, it seemed that simply noticing the possibility of a bug caused the bug to manifest itself in production within a few days or weeks, but correlation does not imply causation.

#OpenDevelopment

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]

List of posts in this series

In the previous post, I started looking at the Cryptographic primitives crate, but was put off by some fairly inscrutable conditions under which the code would panic. So here I continue looking at the most recently updated crates found by searching crates.io for “Feistel”.

Dandelion random

The next crate in the list, dandelion-random, refers to Feistel only in the README, although it makes the following reassuring statement:

---

Indeed, a Feistel round

(x, y) ⇒ (y + H(x), x)

is a permutation irrespective of any properties of H.

---

But there's no Feistel network code so we pass on to bidirectional_hash.

Bidirectional hash

This is a Rust implementation of Pseudo encrypt. This is a keyless Feistel network with three rounds and a simple — maybe too simple — round function:

let r2 = l1 ^ ((((1366 * r1 + 150889) % 714025) as f64 / 714025.0 * 32767.0) as i32);

Arweave RS packing

This crate's documentation assumes the reader is familiar with “Arweave data”. The Arweave website is off-putting in stating “Dive in! The rabbit hole is deep, and the possibilities are endless.” Next!

ore.rs

This crate also refers to Feistel networks only in its README, to point out it doesn't use a Feistel network. Moving on...

Cloudproof FPE

This looks promising as the crate is specifically designed to offer FPEs and it has a good README. The crate has a commercial backer, but is open sourced under Affero GPLv3, which would probably be ok for my use.

Feistel permutation rs

This also looks promising. The code is very simple and there are tests. But there's no README to give any clue about the author's intentions. There's no LICENSE either, so it's not open source. It may be useful to refer to.

(Postscript: the author kindly merged a PR to add an open source license.)

Next steps

I'm probably AFK for several weeks now, but my next step may be to start to look at the Cloudproof FPE code and its documentation.

(Postscript: the next post turned out to be some light relief looking at some of the interactions with others that this experiment has generated.)

#OpenDevelopment

[ | about | blogroll | contact | notes | now | search | subscribe | © | ]