Scalable distributed databases made easy with CockroachDB | Erlang Solutions Webinar

Permalink

[Sponsored content: Erlang Solutions ] Blockchain in Financial Services | Fintech Week London 2021

Permalink

Elixir OTP Design Lessons from Hardware Hosted by Bruce Tate | Erlang Solutions Webinar

Permalink

My favorite Erlang Container

2022/07/09

My favorite Erlang Container

Joe Armstrong wrote a blog post titled My favorite Erlang Program, which showed a very simple universal server written in Erlang:

universal_server()->receive{become,F}->F()end.

You could then write a small program that could fit this function F:

factorial_server()->receive{From,N}->From!factorial(N),factorial_server()end.factorial(0)->1;factorial(N)->N*factorial(N-1).

If you had an already running universal server, such as you would by having called Pid = spawn(fun universal_server/0), you could then turn that universal server into the factorial server by calling Pid ! {become, fun factorial_server/0}.

Weeds growing in driveway cracks

Joe Armstrong had a way to get to the essence of a lot of concepts and to think about programming as a fun thing. Unfortunately for me, my experience with the software industry has left me more or less frustrated with the way things are, even if the way things are is for very good reasons. I really enjoyed programming Erlang professionally, but I eventually got sidetracked by other factors that would lead to solid, safe software—mostly higher level aspects of socio-technical systems, and I became SRE.

But a part of me still really likes dreaming about the days where I could do hot code loading over entire clusters—see A Pipeline Made of Airbags—and I kept thinking about how I could bring this back, but within the context of complex software teams running CI/CD, building containers, and running them in Kubernetes. This is no short order, because we now have decades of lessons telling everyone that you want your infrastructure to be immutable and declared in code.

I also have a decade of experience telling me a lot of what we've built is a frustrating tower of abstractions over shaky ground. I know I've experienced better, my day job is no longer about slinging my own code, and I have no pretense of respecting the tower of abstraction itself.

A weed is a plant considered undesirable in a particular situation, "a plant in the wrong place". Examples commonly are plants unwanted in human-controlled settings, such as farm fields, gardens, lawns, and parks. Taxonomically, the term "weed" has no botanical significance, because a plant that is a weed in one context is not a weed when growing in a situation where it is wanted.

Like the weeds that decide that the tiniest crack in a driveway is actually real cool soil to grow in, I've decided to do the best thing given the situation and bring back Erlang live code upgrades to modern CI/CD, containerized and kubernetized infrastructure.

If you want the TL:DR; I wrote the dandelion project, which shows how to go from an Erlang/OTP app, automate the generation of live code upgrade instructions with the help of pre-existing tools and CI/CD, generate a manifest file and store build artifacts, and write the necessary configuration to have Kubernetes run said containers and do automated live code upgrades despite its best attempts at providing immutable images. Then I pepper in some basic CI scaffolding to make live code upgrading a tiny bit less risky. This post describes how it all works.

A Sample App

A lot of "no downtime" deployments you'll find for Kubernetes are actually just rolling updates with graceful connection termination. Those are always worth supporting (even if it can be annoying to get right), but it has a narrow definition of downtime that's different from what we're aiming for here: no need to restart the application, dump and re-hydrate the state, nor to drop a single connection.

A small server with persistent connections

I wrote a really trivial application, nothing worth calling home about. It's a tiny TCP server with a bunch of acceptors where you can connect with netcat (nc localhost 8080) and it just displays stuff. This is the bare minimum to show actual "no downtime": a single instance, changing its code definitions in a way that is directly observable to a client, without ever dropping a connection.

The application follows a standard release structure for Erlang, using Rebar3 as a build tool. Its supervision structure looks like this:

               top level
              supervisor
               /      \
        connection   acceptors
        supervisor   supervisor
            |            |
        connection    acceptor
         workers        pool
       (1 per conn)

The acceptors supervisor starts a TCP listen socket, which is passed to each worker in the acceptor pool. Upon each accepted connection, a connection worker is started and handed the final socket. The connection worker then sits in an event loop. Every second it sends in a small ASCII drawing of a dandelion, and for every packet of data it receives (coalesced or otherwise), it sends in a line containing its version.

A netcat session looks like this:

$ nc localhost 8080

   @
 \ |
__\!/__


   @
 \ |
__\!/__

> ping!
vsn: 0.1.5

   @
 \ |
__\!/__

^C

Universal container: a plan

Modern deployments are often done with containers and Kubernetes. I'm assuming you're familiar with both of these concepts, but if you want more information—in the context of Erlang—then Tristan Sloughter wrote a great article on Docker and Erlang and another one on using Kubernetes for production apps.

In this post, I'm interested in doing two things:

1. Have an equivalent to Joe Armstrong's Universal server
2. Force the immutable world to nevertheless let me do live code upgrades

The trick here is deceptively simple, enough to think "that can't be a good idea." It probably isn't.

The plan? Use a regular container someone else maintains and just wedge my program's tarball in there. I can then use a sidecar to automate fetching updates and applying live code upgrades without Kubernetes knowing anything about it.

Erlang Releases: a detour

To understand how this can work, we first need to cover the basics of Erlang releases. A good overview of the Erlang Virtual Machine's structure is an article I've written in OTP at a high level, but that I can summarize here by describing the following layers, from lowest to highest:

• There is an Erlang Runtime System (ERTS), which is essentially the VM itself, written in C. This can't be live upgraded, and offers features around Erlang's immutability, preemptive scheduling, memory allocation, garbage collection, and so on.
• A few pre-loaded modules that offer core functionality around files and sockets. I don't believe that these get to be live upgraded either.
• There is a pair of libraries ("applications" in Erlang-speak) called kernel and stdlib that define the most basic libraries around list processing, distributed programs, and the core of "OTP", the general development framework in the language. These can be live upgraded, but pretty much nobody does that
• Then we have the Erlang standard library. This includes things such as TLS support, HTTP clients and servers, Wx bindings, test frameworks, the compiler, and extra scaffolding around OTP niceties, to name a few.

Your own project is pretty much just your own applications ("libraries"), bundled with select standard library libraries and a copy of the Erlang system:

The end result of this sort of ordeal is that every Erlang project is pretty much people writing their own libraries (in blue in the drawing above), fetching bits from the Erlang base install (in red in the drawing above), and then using tools (such as Rebar3) to repackage everything into a brand new Erlang distribution. A detailed explanation of how this happens is also in Adopting Erlang.

Whatever you built on one system can be deployed on an equivalent system. If you built your app on a 64 bit linux—and assuming you used static libraries for OpenSSL or LibreSSL, or have equivalent ones on a target system—then you can pack a tarball, unpack it on the other host system, and get going. Those requirements don't apply to your code, only the standard library. If you don't use NIFs or other C extensions, your own Erlang code, once built, is fully portable.

The cool thing is that Erlang supports making a sort of "partial" release, where you take the Erlang/OTP part (red) and your own apps (blue) in the above image, only package your own app's and a sort of "figure out the Erlang/OTP part at run-time" instruction, and your application is going to be entirely portable across all platforms (Windows, Linux, BSD, MacOS) and supported architectures (x86, ARM32, ARM64, etc.)

I'm mentioning this because for the sake of this experiment, I'm running things locally on a M1 macbook air (ARM64), with MicroK8s (which runs a Linux/aarch64), but am using Github Actions, which are on an x86 linux. So rather than using a base ubuntu image and then needing to run the same sort of hardware family everywhere down the build chain, I'll be using an Erlang image from dockerhub to provide the ERTS and stdlib, and will then have the ability to make portable builds from either my laptop or github actions and deploy them onto any Kubernetes cluster—something noticeably nicer than having to deal with cross-compilation in any language.

Controlling Releases

The release definition for Dandelion accounts for the above factors, and looks like this:

{relx,[{release,{dandelion,"0.1.5"},% my release and its version (dandelion-0.1.5)[dandelion,% includes the 'dandelion' app and its depssasl]},% and the 'sasl' library, which is needed for% live code upgrades to work%% set runtime configuration values based on the environment in this file{sys_config_src,"./config/sys.config.src"},%% set VM options in this file{vm_args,"./config/vm.args"},%% drop source files and the ERTS, but keep debug annotations%% which are useful for various tools, including automated%% live code upgrade plugins{include_src,false},{include_erts,false},{debug_info,keep},{dev_mode,false}]}.

The release can be built by calling rebar3 release and packaged by calling rebar3 tar.

Take the resulting tarball, unpack it, and you'll get a bunch of directories: lib/ contains the build artifact for all libraries, releases/ contains metadata about the current release version (and the structure to store future and past versions when doing live code upgrades), and finally the bin/ directory contains a bunch of accessory scripts to load and run the final code.

Call bin/dandelion and a bunch of options show up:

$ bin/dandelion
Usage: dandelion [COMMAND] [ARGS]

Commands:

  foreground              Start release with output to stdout
  remote_console          Connect remote shell to running node
  rpc [Mod [Fun [Args]]]] Run apply(Mod, Fun, Args) on running node
  eval [Exprs]            Run expressions on running node
  stop                    Stop the running node
  restart                 Restart the applications but not the VM
  reboot                  Reboot the entire VM
...
  upgrade [Version]       Upgrade the running release to a new version
  downgrade [Version]     Downgrade the running release to a new version
  install [Version]       Install a release
  uninstall [Version]     Uninstall a release
  unpack [Version]        Unpack a release tarball
  versions                Print versions of the release available
...

So in short, your program's lifecycle can become:

• bin/dandelion foreground boots the app (use bin/dandelion console to boot a version in a REPL)
• bin/dandelion remote_console pops up a REPL onto the running app by using distributed Erlang

If you're doing the usual immutable infrastructure, that's it, you don't need much more. If you're doing live code upgrades, you then have a few extra steps:

1. Write a new version of the app
2. Give it some instructions about how to do its live code upgrade
3. Pack that in a new version of the release
4. Put the tarball in releases/
5. Call bin/dandelion unpack <version> and the Erlang VM will unpack the new tarball into its regular structure
6. Call bin/dandelion install <version> to get the Erlang VM in your release to start tracking the new version (without switching to it)
7. Call bin/dandelion upgrade <version> to apply the live code upgrade

And from that point on, the new release version is live.

Hot Code Upgrade Instructions

I've sort of papered over the complexity required to "give it some instructions about how to do its live code upgrade." This area is generally really annoying and complex. You first start with appup files, which contain instructions on upgrading individual libraries, which are then packaged into a relup which provides instructions for coordinating the overall upgrade.

If you're running live code upgrades on a frequent basis you may want to get familiar with these, but most people never bothered, and the vast majority of live code upgrades are done by people writing manual scripts to load specific modules.

A very nice solution that also exists is to use Luis Rascão's rebar3_appup_plugin which will take two releases, compare their code, and auto-generate instructions on your behalf. By using it, most of the annoyances and challenges are automatically covered for you.

All you need to do is to make sure all versions are adequately bumped, do a few command line invocations, and package it up. This will be a prime candidate for automation soon in this post.

For now though, let's assume we'll just put the release in an S3 bucket that the kubernetes cluster has access to, and build our infrastructure on the Kubernetes side.

Universal container: a kubernetes story

Let's escape the Erlang complexity and don our DevOps hat. We now want to run the code we assume has made it safely to S3. All of it beautifully holds into a single YAML file—which, granted, can't really be beautiful on its own. I use three containers in a single kubernetes pod:

All of these containers will share a 'release' directory, by using an EmptyDir volume. The bootstrap container will fetch the latest release and unpack it there, the dandelion-release container will run it, and the sidecar will be able to interact over the network to manage live code upgrades.

The bootstrap pod runs first, and fetches the first (and current) release from S3. I'm doing so by assuming we'll have a manifest file (<my-s3-bucket>/dandelion-latest) that contains a single version number that points to the tarball I want (<my-s3-bucket>/dandelion-<version>.tar.gz). This can be done with a shell script:

#!/usr/bin/env bashset -euxo pipefail
RELDIR=${1:-/release}S3_URL="https://${BUCKET_NAME}.s3.${AWS_REGION}.amazonaws.com"TAG=$(curl "${S3_URL}/${RELEASE}-latest" -s)
wget -nv "${S3_URL}/${RELEASE}-${TAG}.tar.gz" -O "/tmp/${RELEASE}-${TAG}.tar.gz"
tar -xvf "/tmp/${RELEASE}-${TAG}.tar.gz" -C ${RELDIR}
rm "/tmp/${RELEASE}-${TAG}.tar.gz"

This fetches the manifest, grabs the tag, fetches the release, unpacks it, and deletes the old tarball. The dandelion-release container, which will run our main app, can then just call the bin/dandelion script directly:

#!/usr/bin/env bashset -euxo pipefail
RELDIR=${1:-/release}exec${RELDIR}/bin/${RELEASE} foreground

The sidecar is a bit more tricky, but can reuse the same mechanisms. Every time interval (or based on a feature flag or some server-sent signal), check the manifest, and apply the unpacking steps. Something a bit like:

#!/usr/bin/env bashset -euxo pipefail
RELDIR=${2:-/release}S3_URL="https://${BUCKET_NAME}.s3.${AWS_REGION}.amazonaws.com"CURRENT=$(${RELDIR}/bin/${RELEASE} versions | awk '$3=="permanent" && !vsn { vsn=$2 } $3=="current" { vsn=$2 } END { print vsn }')TAG=$(curl "${S3_URL}/${RELEASE}-latest" -s)if[["${CURRENT}" !="${TAG}"]];then
    wget -nv "${S3_URL}/${RELEASE}-${TAG}.tar.gz" -O "${RELDIR}/releases/${RELEASE}-${TAG}.tar.gz"${RELDIR}/bin/${RELEASE} unpack ${TAG}${RELDIR}/bin/${RELEASE} install ${TAG}${RELDIR}/bin/${RELEASE} upgrade ${TAG}fi

Call this in a loop and you're good to go.

Now here's the fun bit: ConfigMaps are a Kubernetes thing that lets you take arbitrary metadata, and optionally use them as files into pods. This is how we get close to our universal container.

By declaring the three scripts above as a ConfigMap and mounting them in a /scripts directory, we can then declare the 3 containers in a generic fashion:

initContainers:-name:dandelion-bootstrapimage:erlang:25.0.2env:-...volumeMounts:-name:releasemountPath:/release-name:scriptsmountPath:/scriptscommand:-/scripts/init-latest.sh# Regular containers run nextcontainers:-name:dandelion-releaseimage:erlang:25.0.2env:-...volumeMounts:-name:releasemountPath:/release-name:scriptsmountPath:/scriptscommand:-/scripts/boot-release.shports:-containerPort:8080hostPort:8080-name:dandelion-sidecarimage:erlang:25.0.2env:-...volumeMounts:-name:releasemountPath:/release-name:scriptsmountPath:/scriptscommand:-/scripts/update-loop.sh

The full file has more details, but this is essentially all we need. You could kubectl apply -f dandelion.yaml and it would get going on its own. The rest is about providing a better developer experience.

Making it Usable

What we have defined now is an expected format and procedure from Erlang's side to generate code and live upgrade instructions, and a wedge to make this usable within Kubernetes' own structure. This procedure is somewhat messy, and there are a lot of technical aspects that need to be coordinated to make this usable.

Now comes the time to work around providing a useful workflow for this.

Introducing Smoothver

Semver's alright. Most of the time I won't really care about it, though. I'll go read the changelog and see if whatever I depend on has changed or not. People will pick versions for whichever factor they want, and they'll very often put a small breaking change (maybe a bug fix!) as non-breaking because there's an intent being communicated by the version.

Here the semver semantics are not useful. I've just defined a workflow that mostly depends on whether the server can be upgraded live or not, with some minor variations. This operational concern is likely to be the main concern of engineers who would work on such an application daily, particularly since as someone deploying and maintaining server-side software, I mostly own the whole pipeline and always consider the main branch to be canonical.

As such, I should feel free to develop my own versioning scheme. Since I'm trying to reorient Dandelion's whole flow towards continuous live delivery, my versioning scheme should actually reflect and support that effort. I therefore introduce Smoothver (Smooth Versioning):

Given a version number RESTART.RELUP.RELOAD, increment the:

• RESTART version when you make a change that requires the server to be rebooted.
• RELUP version when you make a change that requires pausing workers and migrating state.
• RELOAD version when you make a change that requires reloading modules with no other transformation.

The version number now communicates the relative expected risk of a deployment in terms of disruptiveness, carries some meaning around the magnitude of change taking place, and can be leveraged by tooling.

For example:

• Fixing a bug in a data structure is a RELOAD deploy so long as the internal representation does not change (e.g. swapping a > for a >= in a comparison)
• Adding a new endpoint or route to an existing HTTP API is likely a RELOAD deploy since no existing state relies on it. Rolling it back is a business concern, not a technical one.
• Adding or changing a field in a data structure representing a user is a RELUP operation, since rolling forward or backward implies a data transformation to remain compatible
• Upgrading the VM version is a RESTART because the C code of the VM itself can't change
• Bumping a stateful dependency that does not provide live code upgrades forces a RESTART version bump

As with anything we do, the version bump may be wrong. But it at least carries a certain safety level in letting you know that a RESTART live code upgrade should absolutely not be attempted.

Engineers who get more familiar with live code upgrades will also learn some interesting lessons. For example, a RELUP change over a process that has tens of thousands of copies of itself may take a long long time to run and be worse than a rolling upgrade. An interesting thing you can do then is turn RELUP changes (which would require calling code change instructions) into basic code reloads by pattern matching an old structure and converting it on each call, turning it into a somewhat stateless roll-forward affair.

That's essentially converting operational burdens into dirtier code, but this sort of thing is something you do all the time with database migrations (create a new table, double-write, write only to the new one, delete the old table) and that can now be done with running code.

For a new development workflow that tries to orient itself towards live code upgrades, Smoothver is likely to carry a lot more useful information than Semver would (and maybe could be nice for database migrations as well, since they share concerns).

Publishing the Artifacts

I needed to introduce the versioning mechanism because the overall publication workflow will obey it. If you're generating a new release version that requires a RESTART bump, then don't bother generating live code upgrade instructions. If you're generating anything else, do include them.

I've decided to center my workflow around git tags. If you tag your release v1.2.3, then v1.2.4 or v1.4.1 all do a live code upgrade, but v2.0.0 won't, regardless of which branch they go to. The CI script is not too complicated, and is in three parts:

1. Fetch the currently deployed manifest, and see if the newly tagged version requires a live code upgrade ("relup") or not
2. Build the release tarball with the relup instructions if needed. Here I rely purely on Luis's plugin to handle all the instructions.
3. Put the files on S3

That's really all there is to it. I'm assuming that if you wanted to have more environments, you could setup gitops by having more tags (staging-v1.2.3, prod-v1.2.5) and more S3 buckets or paths. But everything is assumed to be driven by these builds artifacts.

A small caveat here is that it's technically possible to generate upgrade instructions (appup files) that map from many to many versions: how to update to 1.2.0 from 1.0.0, 1.0.1, 1.0.2, and so on. Since I'm assuming a linear deployment flow here, I'm just ignoring that and always generating pairs from "whatever is in prod" to "whatever has been tagged". There are obvious race conditions in doing this, where two releases generated in parallel can specify upgrade rules from a shared release, but could be applied and rolled out in a distinct order.

Using the Manifest and Smoothver

Relying on the manifest and versions is requiring a few extra lines in the sidecar's update loop. They look at the version, and if it's a RESTART bump or an older release, they ignore it:

# Get the running versionCURRENT=$(${RELDIR}/bin/${RELEASE} versions | awk '$3=="permanent" && !vsn { vsn=$2 } $3=="current" { vsn=$2 } END { print vsn }')TAG=$(curl "${S3_URL}/${RELEASE}-latest" -s)if[["${CURRENT}" !="${TAG}"]];thenIS_UPGRADE=$(echo"$TAG$CURRENT"| awk -vFS='[. ]''($1==$4 && $2>$5) || ($1==$4 && $2>=$5 && $3>$6) {print 1; exit} {print 0}')if[[$IS_UPGRADE -eq 1]];then
      wget -nv "${S3_URL}/${RELEASE}-${TAG}.tar.gz" -O "${RELDIR}/releases/${RELEASE}-${TAG}.tar.gz"${RELDIR}/bin/${RELEASE} unpack ${TAG}${RELDIR}/bin/${RELEASE} install ${TAG}${RELDIR}/bin/${RELEASE} upgrade ${TAG}fifi

There's some ugly awk logic, but I wanted to not host images. The script could be made a lot more solid by looking at whether we're bumping from the proper version to the next one, and in this it shares a sort of similar race condition to the generation step.

On the other hand, the install step looks at the specified upgrade instructions and will refuse to apply itself (resulting in a sidecar crash) if a bad release is applied.

I figure that alerting on crashed sidecars could be used to drive further automation to ask to delete and replace the pods, resulting in a rolling upgrade. Alternatively, the error itself could be used to trigger a failure in liveness and/or readiness probes, and force-automate that replacement. This is left as an exercise to the reader, I guess. The beauty of writing prototypes is that you can just decide this to be out of scope and move on, and let someone who's paid to operationalize that stuff to figure out the rest.

Oh and if you just change the Erlang VM's version? That changes the kubernetes YAML file, and if you're using anything like helm or some CD system (like ArgoCD), these will take care of running the rolling upgrade for you. Similarly, annotating the chart with a label of some sort indicating the RESTART version will accomplish the same purpose.

You may rightfully ask whether it is a good idea to bring mutability of this sort to a containerized world. I think that using S3 artifacts isn't inherently less safe than a container registry, dynamic feature flags, or relying on encryption services or DNS records for functional application state. I'll leave it at that.

Adding CI validation

Versioning things is really annoying. Each OTP app and library, and each release needs to be versioned properly. And sometimes you change dependencies and these dependencies won't have relup instructions available but you didn't know and that would break your live code upgrade.

What we can do is add a touch of automation to catch the most obvious failure situations and warn developers early about these issues. I've done so by adding a quick relup CI step to all pull requests, by using a version check script that encodes most of that logic.

The other thing I started experimenting with was setting up some sort of test suite for live code upgrades:

# This here step is a working sample, but if you were to run a more# complex app with external dependencies, you'd also have to do a# more intricate multi-service setup here, e.g.:# https://github.com/actions/example-services-name:Run relup applicationworking-directory:erlangrun:|mkdir relupcitar -xvf "${{ env.OLD_TAR }}" -C relupci# use a simple "run the task in the background" setuprelupci/bin/dandelion daemonTAG=$(echo "${{ env.NEW_TAR }}"  | sed -nr 's/^.*([0-9]+\.[0-9]+\.[0-9]+)\.tar\.gz$/\1/p')cp "${{ env.NEW_TAR }}" relupci/releases/relupci/bin/dandelion unpack ${TAG}relupci/bin/dandelion install ${TAG}relupci/bin/dandelion upgrade ${TAG}relupci/bin/dandelion versions

The one thing that would make this one a lot cooler is to write a small extra app or release that runs in the background while the upgrade procedure goes on. It could do things like:

• generate constant load
• run smoke tests on critical workflows
• maintain live connections to show lack of failures
• report on its state on demand

By starting that process before the live upgrade and questioning it after, we could ensure that the whole process went smoothly. Additional steps could also look at logs to know if things were fine.

The advantage of adding CI here is that each pull request can take measures to ensure it is safely upgradable live before being merged to main, even if none of them are deployed right away. By setting that gate in place, engineers are getting a much shorter feedback loop asking them to think about live deployments.

Running through a live code upgrade

I've run through a few iterations to test and check everything. I've set up microk8s on my laptop, ran kubectl -f apply dandelion.yaml and showed that the pod was up and running fine:

$ kubectl -n dandelion get pods
NAME                                    READY   STATUS    RESTARTS   AGE
dandelion-deployment-648db88f44-49jl8   2/2     Running   0          25H

It is possible to run into one of the containers, log on onto a REPL, and see what is going on:

$ kubectl-ndandelionexec-i-tdandelion-deployment-648db88f44-49jl8-cdandelion-sidecar--/bin/bashroot@dandelion-deployment-648db88f44-49jl8:/#/release/bin/dandelionremote_consoleErlang/OTP25[erts-13.0.2][source][64-bit][smp:2:2][ds:2:2:10][async-threads:1][jit]EshellV13.0.2(abortwith^G)(dandelion@localhost)1>release_handler:which_releases().[{"dandelion","0.1.5",["kernel-8.4.1","stdlib-4.0.1","dandelion-0.1.5","sasl-4.2"],permanent},{"dandelion","0.1.4",["kernel-8.4.1","stdlib-4.0.1","dandelion-0.1.4","sasl-4.2"],old}]

This shows that the container had been running for a day, and already had two releases—it first booted on version 0.1.4 and had already gone through a bump to 0.1.5. I ran a small pull request changing the display (and messed up versioning, which CI caught!), merged it, tagged it v0.1.6, and started listening to my Kubernetes cluster:

$ nc 192.168.64.2 8080

   @
 \ |
__\!/__

...

   @
 \ |
__\!/__

vsn?
vsn: 0.1.5

   @
 \ |
__\!/__

      *
   @
 \ |
__\!/__

vsn?
vsn: 0.1.6
      *
   @
 \ |
__\!/__

...

This shows me interrogating the app (vsn?) and getting the version back, and without dropping the connection, having a little pappus floating in the air.

My REPL session was still live in another terminal:

(dandelion@localhost)2>release_handler:which_releases().[{"dandelion","0.1.6",["kernel-8.4.1","stdlib-4.0.1","dandelion-0.1.6","sasl-4.2"],permanent},{"dandelion","0.1.5",["kernel-8.4.1","stdlib-4.0.1","dandelion-0.1.5","sasl-4.2"],old},{"dandelion","0.1.4",["kernel-8.4.1","stdlib-4.0.1","dandelion-0.1.4","sasl-4.2"],old}]

showing that the old releases are still around as well. And here we have it, an actual zero-downtime deploy in a kubernetes container.

Conclusion

Joe's favorite program could hold on a business card. Mine is maddening. But I think this is because Joe didn't care for the toolchains people were building and just wanted to do his thing. My version reflects the infrastructure we have put in place, and the processes we want and need for a team.

Rather than judging the scaffolding, I'd invite you to think about what would change when you start centering your workflow around a living system.

Those of you who have worked with bigger applications that have a central database or shared schemas around network protocols (or protobuf files or whatever) know that you approach your work differently when you have to consider how it's going to be rolled out. It impacts your tooling, how you review changes, how you write them, and ultimately just changes how you reason about your code and changes.

In many ways it's a more cumbersome way to deploy and develop code, but you can also think of the other things that change: what if instead of having configuration management systems, you could hard-code your config in constants that just get rolled out live in less than a minute—and all your configs were tested as well as your code? Since all the release upgrades implicitly contain a release downgrade instruction set, just how much faster could you rollback (or automate rolling back) a bad deployment? Would you be less afraid of changing network-level schema definitions if you made a habit of changing them within your app? How would your workflow change if deploying took half-a-second and caused absolutely no churn nor disruption to your cluster resources most of the time?

Whatever structure we have in place guides a lot of invisible emergent behaviour, both in code and in how we adjust ourselves to the structure. Much of what we do is a tacit response to our environment. There's a lot of power in experimenting alternative structures, and seeing what pops up at the other end. A weed is only considered as such in some contexts. This is a freak show of a deployment mechanism, but it sort of works, and maybe it's time to appreciate the dandelions for what they can offer.

Permalink

Erlang/OTP 25.0 Release

Erlang/OTP 25 is a new major release with new features, improvements as well as a few incompatibilities.

For details about new features, bugfixes and potential incompatibilities see the Erlang 25.0 README or the Erlang/OTP 25.0 downloads page.

Many thanks to all contributors!

Erlang/OTP 25.0 Highlights

stdlib

• New function filelib:ensure_path/1 will ensure that all directories for the given path exists
• New functions groups_from_list/2 and groups_from_list/3 in the maps module
• New functions uniq/1 uniq/2 in the lists module
• New PRNG added to the rand module, for fast pseudo-random numers.

compiler, kernel, stdlib, syntax_tools

• Added support for selectable features as described in EEP-60. Features can be enabled/disabled during compilation with options (ordinary and +term) to erlc as well as with directives in the file. Similar options can be used to erl for enabling/disabling features allowed at runtime. The new maybe expression EEP-49 is fully supported as the feature maybe_expr.

erts & JIT

• The JIT now works for 64-bit ARM processors.
• The JIT now does type-based optimizations based on type information in the BEAM files.
• Improved the JIT’s support for external tools like perf and gdb, allowing them to show line numbers and even the original Erlang source code when that can be found.

erts, stdlib, kernel

• Users can now configure ETS tables with the {write_concurrency, auto} option. This option forces tables to automatically change the number of locks that are used at run-time depending on how much concurrency is detected. The {decentralized_counters, true} option is enabled by default when {write_concurrency, auto} is active.
  Benchmark results comparing this option with the other ETS optimization options are available here: benchmarks.
• To enable more optimizations, BEAM files compiled with OTP 21 and earlier cannot be loaded in OTP 25.
• The signal queue of a process with the process flag message_queue_data=off_heap has been optimized to allow parallel reception of signals from multiple processes. This can improve performance when many processes are sending in parallel to one process. See benchmark.
• The Erlang installation directory is now relocatable on the file system given that the paths in the installation’s RELEASES file are paths that are relative to the installations root directory.
• A new option called short has been added to the functions erlang:float_to_list/2 and erlang:float_to_binary/2. This option creates the shortest correctly rounded string representation of the given float that can be converted back to the same float again.
• Introduction of quote/1 and unquote/1 functions in the uri_string module - a replacement for the deprecated functions http_uri:encode and http_uri:decode.
• The new module peer supersedes the slave module. The slave module is now deprecated and will be removed in OTP 27.
• global will now by default prevent overlapping partitions due to network issues. This is done by actively disconnecting from nodes that reports that they have lost connections to other nodes. This will cause fully connected partitions to form instead of leaving the network in a state with overlapping partitions.
  It is possible to turn off the new behavior by setting the the kernel configuration parameter prevent_overlapping_partitions to false. Doing this will retain the same behavior as in OTP 24 and earlier.
• The format_status/2 callback for gen_server, gen_statem and gen_event has been deprecated in favor of the new format_status/1 callback.
  The new callback adds the possibility to limit and change many more things than the just the state.
• The timer module has been modernized and made more efficient, which makes the timer server less susceptible to being overloaded. The timer:sleep/1 function now accepts an arbitrarily large integer.

compiler

• The maybe ... end construction as proposed in EEP-49 has been implemented. It can simplify complex code where otherwise deeply nested cases would have to be used.
  To enable maybe, give the option {enable_feature,maybe_expr} to the compiler. The exact option to use will change in a coming release candidate and then it will also be possible to use from inside the module being compiled.
• When a record matching or record update fails, a {badrecord, ExpectedRecordTag} exception used to be raised. In this release, the exception has been changed to {badrecord, ActualValue}, where ActualValue is the value that was found instead of the expected record.
• Add compile attribute -nifs() to empower compiler and loader with information about which functions may be overridden as NIFs by erlang:load_nif/2.
• Improved and more detailed error messages when binary construction with the binary syntax fails. This applies both for error messages in the shell and for erl_error:format_exception/3,4.
• Change format of feature options and directives for better consistency. Options to erlc and the -compile(..) directive now has the format {feature, feature-name, enable | disable}. The -feature(..) now has the format -feature(feature-name, enable | disable).

crypto

• Add crypto:hash_equals/2 which is a constant time comparision of hashvalues.

ssl

• Introducing a new (still experimental) option {certs_keys,[cert_key_conf()]}. With this a list of a certificates with their associated key may be used to authenticate the client or the server. The certificate key pair that is considered best and matches negotiated parameters for the connection will be selected.

public_key

• Functions for retrieving OS provided CA-certs added.

dialyzer

• Optimize operations in the erl_types module. Parallelize the Dialyzer pass remote.
• Added the missing_return and extra_return options to raise warnings when specifications differ from inferred types. These are similar to, but not quite as verbose as overspecs and underspecs.
• Dialyzer now better understands the types for min/2, max/2, and erlang:raise/3. Because of that, Dialyzer can potentially generate new warnings. In particular, functions that use erlang:raise/3 could now need a spec with a no_return() return type to avoid an unwanted warning.

Misc

• A new DEVELOPMENT HOWTO guide has been added that describes how to build and test Erlang/OTP when fixing bugs or developing new functionality.
• Testing has been added to the Github actions run for each opened PR so that more bugs are caught earlier when bug fixes and new features are proposed.

Download links for this and previous versions are found here

• https://www.erlang.org/downloads

Permalink

Errors are constructed, not discovered

2022/04/13

Errors are constructed, not discovered

Over a year ago, I left the role of software engineering* behind to become a site reliability engineer* at Honeycomb.io. Since then, I've been writing a bunch of blog posts over there rather than over here, including the following:

• OnCallogy Sessions
• On the brittleness of dashboards
• How we define SRE work
• Data availability isn't observability

There are also a couple of incident reviews, including one on a Kafka migration and another on a spate of scaling-related incidents.

Either way, I only have so much things to rant about to fill in two blogs, so this place here has been a bit calmer. However, I recently gave a talk at IRConf (video).

I am reproducing this talk here because, well, I stand behind the content, but it would also not fit the work blog's format. I'm also taking this opportunity because I don't know how many talks I'll give in the next few years. I've decided to limit how much traveling I do for conferences due to environmental concerns—if you see me at a conference, it either overlapped with other opportunistic trips either for work or vacations, or they were close enough for me to attend them via less polluting means—and so I'd like to still post some of the interesting talks I have when I can.

The Talk

This talk is first of all about the idea that errors are not objective truths. Even if we look at objective facts with a lot of care, errors are arbitrary interpretations that we come up with, constructions that depend on the perspective we have. Think of them the same way constellations in the night sky are made up of real stars, but their shape and meaning are made up based on our point of view and what their shapes remind us of.

The other thing this talk will be about is ideas about what we can do once we accept this idea, to figure out the sort of changes and benefits we can get from our post-incident process when we adjust to it.

I tend to enjoy incidents a lot. Most of the things in this talk aren't original ideas, they're things I've read and learned from smarter, more experienced people, and that I've put back together after digesting them for a long time. In fact, I thought my title for this talk was clever, but as I found out by accident a few days ago, it's an almost pure paraphrasing of a quote in a book I've read over 3 years ago. So I can't properly give attribution for all these ideas because I don't know where they're from anymore, and I'm sorry about that.

This is a quote from "Those found responsible have been sacked": some observations on the usefulness of error" that I'm using because even if errors are arbitrary constructions, they carry meaning, and they are useful to organizations. The paper defines four types I'll be paraphrasing:

• Defense against entanglement: the concept of error or fault is a way for an organization to shield itself from the liabilities of an incident. By putting the fault on a given operator, we avoid having to question the organization's own mechanisms, and safely deflect it away.
• Illusion of control: by focusing on individuals and creating procedures, we can preserve the idea that we can manage the world rather than having to admit that adverse events will happen again. This gives us a sort of comfort.
• Distancing: this is generally about being able to maintain the idea that "this couldn't happen here", either because we are doing things differently or because we are different people with different practices. This also gives us a decent amount of comfort.
• Failed investigation: finally, safety experts seem to see the concept of error, particularly human error, as a marker that the incident investigation has ended too early. There were more interesting things to dig into and that hasn't been done—because the human error itself is worth understanding as an event.

So generally, error is useful as a concept, but as an investigator it is particularly useful as a signal to tell you when things get interesting, not as an explanation on their own.

And so this sort of makes me think about how a lot of incident reviews tend to go on. We use the incident as an opportunity because the disruption is big and large enough to let us think about it all. But the natural framing that easily comes through is to lay blame to the operational area.

Here I don't mean blame as in "people fucked up" nearly as much as "where do we think the organisation needs to improve"—where do we think that as a group we need to improve as a result of this. The incident and the operations are the surface, they often need improvement for sure because it is really tricky work done in special circumstances and it's worth constantly adjusting it, but stopping there is missing on a lot of possible content that could be useful.

People doing the operations are more or less thrown in a context where a lot of big decisions have been made already. Whatever was tested, who was hired, what the budgets are, and all these sorts of pressures are in a large part defined by the rest of the organization, they matter as well. They set the context in which operations take place.

So one question then, is how do we go from that surface-level vision, and start figuring out what happens below that organisational waterline.

The first step of almost any incident investigation is to start with a timeline. Something that lets us go back from the incident or its resolution, and that we use as breadcrumbs to lead us towards ways to prevent this sort of thing from happening again. So we start at the bottom where things go boom, and walk backwards from there.

The usual frameworks we're familiar with apply labels to these common patterns. We'll call something a failure or an error. The thing that happened right before it tends to be called a proximate cause, which is frequently used in insurance situations: it's the last event in the whole chain that could have prevented the failure from happening. Then we walk back. Either five times because we're doing the five whys, or until you land at a convenient place. If there is a mechanical or software component you don't like, you're likely to highlight its flaws there. If it's people or teams you don't trust as much, you may find human error there.

Even the concept of steady state is a shaky one. Large systems are always in some weird degraded state. In short, you find what you're looking for. The labels we use, the lens through which we look at the incident, influence the way we build our explanations.

The overall system is not any of the specific lenses, though, it's a whole set of interactions. To get a fuller richer picture, we have to account for what things looked liked at the time, not just our hindsight-fuelled vision when looking behind. There are a lot of things happening concurrently, a lot of decisions made to avoid bad situations that never took place, and some that did.

Hindsight bias is something somewhat similar to outcome bias, which essentially says that because we know there was a failure, every decision we look at that has taken place before the incident will seem to us like it should obviously have appeared as risky and wrong. That's because we know the result, it affects our judgment. But when people were going down that path and deciding what to do, they were trying to do a good job; they were making the best calls they could to the extent of their abilities and the information available at the time.

We can't really avoid hindsight bias, but we can be aware of it. One tip there is to look at what was available at the time, and consider the signals that were available to people. If they made a decision that looks weird, then look for what made it look better than the alternatives back then.

Counterfactuals are another thing to avoid, and they're one of the trickiest ones to eliminate from incident reviews. They essentially are suppositions about things that have never happened and will never happen. Whenever we say "oh, if we had done this at this point in time instead of that, then the incident would have been prevented." They're talking about a fictional universe that never happened, and they're not productive.

I find it useful to always cast these comments into the future: "next time this happens, we should try to try that to prevent an issue." This orients the discussion towards more realistic means: how can we make this option more likely? the bad one less interesting? In many cases, a suggestion will even become useless: by changing something else in the system, a given scenario may no longer be a concern for the future, or it may highlight how a possible fix would in fact create more confusion.

Finally, normative judgments. Those are often close to counterfactuals, but you can spot them because they tend to be about what people should or shouldn't have done, often around procedures or questions of competence. "The engineer should have checked the output more carefully, and they shouldn't have run the command without checking with someone else, as stated in the procedure." Well they did because it arguably looked reasonable at the time!

The risk with a counterfactual judgment is that it assumes that the established procedure is correct and realistically applicable to the situation at hand. It assumes that deviations and adjustments made by the responder are bound to fail even if we'll conveniently ignore all the times they work. We can't properly correct procedures if we think they're already perfect and it's wrong not to obey them, and we can't improve tooling if we believe the problem is always the person holding it wrong.

A key factor is to understand that in high pressure incident responses, failure and successes use the same mechanisms. We're often tired, distracted, or possibly thrown in there without adequate preparation. What we do to try and make things go right and often succeed through is also in play when things go wrong.

People look for signals, and have a background and training that influences the tough calls that usually will be shared across situations. We tend to want things to go right. The outcome tends to define whether the decision was good one or not, but the decision-making mechanism is shared both for decisions that go well and those that do not. And so we need to look at how these decisions are made with the best of intentions to have any chance of improving how events unfold the next time.

This leads to the idea you want to look at what's not visible, because they show real work.

I say this is "real work" because we come in to a task with an understanding of things, a sort of mental model. That mental model is the rolled up experience we have, and lets us frame all the events we encounter, and is the thing we use to predict the consequences of our decisions.

When we are in an incident, there's almost always a surprise in there, which means that the world and our mental model are clashing. This mismatch between our understanding of the world and the real world was already there. That gap between both needs to be closed, and the big holes in an incident's timelines tend to be one of the places where this takes place.

Whenever someone reports "nothing relevant happens here", these are generally the places where active hypothesis generation periods happen, where a lot of the repair and gap bridging is taking place.

This is where the incident can become a very interesting window into the whole organizational iceberg below the water line.

So looking back at the iceberg, looking at how decisions are made in the moment lets you glimpse at the values below the waterline that are in play. What are people looking at, how are they making their decisions. What's their perspective. These are impacted by everything else that happens before.

If you see concurrent outages or multiple systems impacted, digging into which one gets resolved first and why that is is likely to give you insights about what responders feel confident about, the things they believe are more important to the organization and users. They can reflect values and priorities.

If you look at who they ask help from and where they look for information (or avoid looking for it), this will let you know about various dynamics, social and otherwise, that might be going on in your organization. This can be because some people are central points of knowledge, others are jerks, seen as more or less competent, or also be about what people believe the state of documentation is at that point in time.

And this is why changing how we look at and construct errors matters. If we take the straightforward causal approach, we'll tend to only skim the surface. Looking at how people do their jobs and how they make decisions is an effective way to go below that waterline, and have a much broader impact than staying above water.

To take a proper dive, it helps to ask the proper type of questions. As a facilitator, your job is to listen to what people tell you, but there are ways to prompt for more useful information. The Etsy debriefing facilitation guide is a great source, and so is Jeli's Howie guide. The slide contains some of the questions I like to ask most.

There's one story I recall from a previous job where a team had specifically written an incident report on an outage with some service X, and the report had that sort of 30 minutes gap in it and were asking for feedback on it. I instantly asked "so what was going on during this time?" Only for someone on the team to answer "oh, we were looking for the dashboard of service Y". I asked why they had been looking at the dashboard of another service, and he said that the the service's own dashboard isn't trustworthy, and that this one gave a better picture of the health of the service through its effects. And just like that we opened new paths for improvements that were so normal it had become invisible.

Another one also came from a previous job where an engineer kept accidentally deleting production databases and triggering a whole disaster recovery response. They were initially trying to delete a staging database that was dynamically generated for test cases, but kept fat-fingering the removal of production instances in the AWS console. Other engineers were getting mad and felt that person was being incompetent, and were planning to remove all of their AWS console permissions because there also existed an admin tool that did the same thing safely by segmenting environments.

I ended up asking the engineer if there was anything that made them choose the AWS console more than the admin tool given the difference in safety, and they said, quite simply, that the AWS console has an autocomplete and they never remembered the exact table name, so it was just much faster to delete that table often there than the admin. This was an interesting one because instead of blaming the engineer for being incompetent, it opened the door to questioning the gap in tooling rather than adding more blockers and procedures.

In both of these stories, a focus on how people were making their decisions and their direct work experience managed to highlight alternative views that wouldn't have come up otherwise. They can generate new, different insights and action items.

And this is the sort of map that, when I have time for it, I tried to generate at Honeycomb. It's non-linear, and the main objective is to help show different patterns about the response. Rather than building a map by categorizing events within a structure, the idea is to lay the events around to see what sort of structure pops up. And then we can walk through the timeline and ask what we were thinking, feeling, or seeing.

The objective is to highlight challenging bits and look at the way we work in a new light. Are there things we trust, distrust? Procedures that don't work well, bits where we feel lost? Focusing on these can improve response in the future.

This idea of focusing on generating rather than categorizing is intended to take an approach that is closer to Qualitative science than Quantitative research.

The way we structure our reviews will have a large impact on how we construct errors. I tend to favour a qualitative approach to a quantitative one.

A quantitative approach will often look at ways to aggregate data, and create ways to compare one incident to the next. They'll measure things such as the Mean Time To Recovery (MTTR), the impact, the severity, and will look to assign costs and various classifications. This approach will be good to highlight trends and patterns across events, but as far as I can tell, they won't necessarily provide a solid path for practical improvements for any of the issues found.

The qualitative approach by comparison aims to do a deep dive to provide more complete understanding. It tends to be more observational and generative. Instead of cutting up the incidents and classifying its various parts, we look at what was challenging, what are the things people felt were significant during the incident, and all sorts of messy details. These will highlight tricky dynamics, both for high-pace outages and wider organizational practices, and are generally behind the insights that help change things effectively.

To put this difference in context, I have an example from a prior jobs, where one of my first mandates was to try and help with their reliability story. We went over 30 or so incident reports that had been written over the last year, and a pattern that quickly came up was how many reports mentioned "lack of tests" (or lack of good tests) as causes, and had "adding tests" in action items.

By looking at the overall list, our initial diagnosis was that testing practices were challenging. We thought of improving the ergonomics around tests (making them faster) and to also provide training in better ways to test. But then we had another incident where the review reported tests as an issue, so I decided to jump in.

I reached out to the engineers in question and asked about what made them feel like they had enough tests. I said that we often write tests up until the point we feel they're not adding much anymore, and that I was wondering what they were looking at, what made them feel like they had reached the points where they had enough tests. They just told me directly that they knew they didn't have enough tests. In fact, they knew that the code was buggy. But they felt in general that it was safer to be on-time with a broken project than late with a working one. They were afraid that being late would put them in trouble and have someone yell at them for not doing a good job.

And so that revealed a much larger pattern within the organization and its culture. When I went up to upper management, they absolutely believed that engineers were empowered and should feel safe pressing a big red button that stopped feature work if they thought their code wasn't ready. The engineers on that team felt that while this is what they were being told, in practice they'd still get in trouble.

There's no amount of test training that would fix this sort of issue. The engineers knew they didn't have enough tests and they were making that tradeoff willingly.

So to conclude on this, the focus should be on understanding the mess:

• go for a deeper understanding of specific incidents where you feel something intriguing or interesting happened. Aggregates of all incidents tend to hide messy details, so if you have a bunch of reviews to do, it's probably better to be thorough on one interesting one than being shallow on many of them
• Mental models are how problem solving tends to be done; we understand and predict things based on them. Incidents are amazing opportunities to correct and compare and contrast mental models to make them more accurate or more easy to contextualize
• seek an understanding of how people do their work. There is always a gap between the work as we imagine it to be and what it actually is. The narrower that gap, the more effective our changes are going to be, so focusing on understanding all the nitty gritty details of work and their pressures is going to prove more useful than having super solid numbers
• psychological safety is always essential; the thing that lets us narrow the gap between work as done and work as imagined is going to be whether people feel safe in reporting and describing what they go through. Without psychological safety and good blame awareness, you're going to have a hard time getting good results.

Overall, the idea is that looking for understanding more than causes opens up a lot of doors and makes incidents more valuable.

* I can't legally call myself a software engineer, and technically neither can I be a site reliability engineer, because Quebec considers engineering to be a protected discipline. I however, do not really get to tell American employers what they should give as a job title to people, so I get stuck having titles I can't legally advertise but for which no real non-protected forms exist to communicate. So anywhere you see me referred to any sort of "engineer", that's not an official thing I would choose as a title. It'd be nice to know what the non-engineer-titled equivalent of SRE ought to be.

Permalink

OTP 25 Release candidate 3

OTP 25-rc3

Erlang/OTP 25-rc3 is the third and final release candidate before the OTP 25.0 release.

The intention with this release is to get feedback from our users. All feedback is welcome, even if it is only to say that it works for you. We encourage users to try it out and give us feedback either by creating an issue here https://github.com/erlang/otp/issues or by posting to Erlangforums or the mailing list erlang-questions@erlang.org.

All artifacts for the release can be downloaded from the Erlang/OTP Github release and you can view the new documentation at https://erlang.org/documentation/doc-13.0-rc3/doc/. You can also install the latest release using kerl like this: kerl build 25.0-rc3 25.0-rc3.

Erlang/OTP 25 is a new major release with new features, improvements as well as a few incompatibilities. Some of the new features are highlighted below.

Many thanks to all contributors!

Below are some highlights of the release:

Highlights rc3

compiler

Change format of feature options and directives for better consistency. Options to erlc and the -compile(..) directive now has the format {feature, feature-name, enable | disable}. The -feature(..) now has the format -feature(feature-name, enable | disable).

ssl

Introducing a new (still experimental) option {certs_keys,[cert_key_conf()]}. With this a list of a certificates with their associated key may be used to authenticate the client or the server. The certificate key pair that is considered best and matches negotiated parameters for the connection will be selected.

Highlights rc2

stdlib

• New function filelib:ensure_path/1 will ensure that all directories for the given path exists
• New functions groups_from_list/2 and groups_from_list/3 in the maps module
• New functions uniq/1 uniq/2 in the lists module

compiler, kernel, stdlib, syntax_tools

• Added support for selectable features as described in EEP-60. Features can be enabled/disabled during compilation with options (ordinary and +term) to erlc as well as with directives in the file. Similar options can be used to erl for enabling/disabling features allowed at runtime. The new maybe expression EEP-49 is fully supported as the feature maybe_expr.

Highlights rc1

erts & jit

• The JIT now works for 64-bit ARM processors.
• The JIT now does type-based optimizations based on type information in the BEAM files.
• Improved the JIT’s support for external tools like perf and gdb, allowing them to show line numbers and even the original Erlang source code when that can be found.

erts, stdlib, kernel

• Users can now configure ETS tables with the {write_concurrency, auto} option. This option forces tables to automatically change the number of locks that are used at run-time depending on how much concurrency is detected. The {decentralized_counters, true} option is enabled by default when {write_concurrency, auto} is active.

  Benchmark results comparing this option with the other ETS optimization options are available here: benchmarks.

• To enable more optimizations, BEAM files compiled with OTP 21 and earlier cannot be loaded in OTP 25.
• The signal queue of a process with the process flag message_queue_data=off_heap has been optimized to allow parallel reception of signals from multiple processes. This can improve performance when many processes are sending in parallel to one process. See benchmark.
• The Erlang installation directory is now relocatable on the file system given that the paths in the installation’s RELEASES file are paths that are relative to the installations root directory.
• A new option called short has been added to the functions erlang:float_to_list/2 and erlang:float_to_binary/2. This option creates the shortest correctly rounded string representation of the given float that can be converted back to the same float again.
• Introduction of quote/1 and unquote/1 functions in the uri_string module - a replacement for the deprecated functions http_uri:encode and http_uri:decode.
• The new module peer supersedes the slave module. The slave module is now deprecated and will be removed in OTP 27.

• global will now by default prevent overlapping partitions due to network issues. This is done by actively disconnecting from nodes that reports that they have lost connections to other nodes. This will cause fully connected partitions to form instead of leaving the network in a state with overlapping partitions.

  It is possible to turn off the new behavior by setting the the kernel configuration parameter prevent_overlapping_partitions to false. Doing this will retain the same behavior as in OTP 24 and earlier.

• The format_status/2 callback for gen_server, gen_statem and gen_event has been deprecated in favor of the new format_status/1 callback.

  The new callback adds the possibility to limit and change many more things than the just the state.

• The timer module has been modernized and made more efficient, which makes the timer server less susceptible to being overloaded. The timer:sleep/1 function now accepts an arbitrarily large integer.

Compiler

• The maybe ... end construction as proposed in EEP-49 has been implemented. It can simplify complex code where otherwise deeply nested cases would have to be used.

  To enable maybe, give the option {enable_feature,maybe_expr} to the compiler. The exact option to use will change in a coming release candidate and then it will also be possible to use from inside the module being compiled.

• When a record matching or record update fails, a {badrecord, ExpectedRecordTag} exception used to be raised. In this release, the exception has been changed to {badrecord, ActualValue}, where ActualValue is the value that was found instead of the expected record.
• Add compile attribute -nifs() to empower compiler and loader with information about which functions may be overridden as NIFs by erlang:load_nif/2.
• Improved and more detailed error messages when binary construction with the binary syntax fails. This applies both for error messages in the shell and for erl_error:format_exception/3,4.

Crypto

• Add crypto:hash_equals/2 which is a constant time comparision of hashvalues.

Dialyzer

• Optimize operations in the erl_types module. Parallelize the Dialyzer pass remote.
• Added the missing_return and extra_return options to raise warnings when specifications differ from inferred types. These are similar to, but not quite as verbose as overspecs and underspecs.
• Dialyzer now better understands the types for min/2, max/2, and erlang:raise/3. Because of that, Dialyzer can potentially generate new warnings. In particular, functions that use erlang:raise/3 could now need a spec with a no_return() return type to avoid an unwanted warning.

Misc

• A new DEVELOPMENT HOWTO guide has been added that describes how to build and test Erlang/OTP when fixing bugs or developing new functionality.
• Testing has been added to the Github actions run for each opened PR so that more bugs are caught earlier when bug fixes and new features are proposed.

For more details about new features and potential incompatibilities see

• https://erlang.org/download/otp_src_25.0-rc3.readme

Permalink

Function/Variable Ambiguity in Elixir

-module(shadowing).

-export([x/0, x/1]).

-define(X, 5).

x() -> x().
x(X) when X == 0 -> X;
x(X) -> x(X - 1).

Permalink

OTP 25 Release candidate 2

OTP 25-rc2

Erlang/OTP 25-rc2 is the second release candidate of three before the OTP 25.0 release.

The intention with this release is to get feedback from our users. All feedback is welcome, even if it is only to say that it works for you. We encourage users to try it out and give us feedback either by creating an issue here https://github.com/erlang/otp/issues or by posting to Erlangforums or the mailing list erlang-questions@erlang.org.

All artifacts for the release can be downloaded from the Erlang/OTP Github release and you can view the new documentation at https://erlang.org/documentation/doc-13.0-rc2/doc/. You can also install the latest release using kerl like this: kerl build 25.0-rc2 25.0-rc2.

Erlang/OTP 25 is a new major release with new features, improvements as well as a few incompatibilities. Some of the new features are highlighted below.

Many thanks to all contributors!

Below are some highlights of the release:

Highlights rc2

stdlib

• New function filelib:ensure_path/1 will ensure that all directories for the given path exists
• New functions groups_from_list/2 and groups_from_list/3 in the maps module
• New functions uniq/1 uniq/2 in the lists module

compiler, kernel, stdlib, syntax_tools

• Added support for selectable features as described in EEP-60. Features can be enabled/disabled during compilation with options (ordinary and +term) to erlc as well as with directives in the file. Similar options can be used to erl for enabling/disabling features allowed at runtime. The new maybe expression EEP-49 is fully supported as the feature maybe_expr.

Highlights rc1

erts & jit

• The JIT now works for 64-bit ARM processors.
• The JIT now does type-based optimizations based on type information in the BEAM files.
• Improved the JIT’s support for external tools like perf and gdb, allowing them to show line numbers and even the original Erlang source code when that can be found.

erts, stdlib, kernel

• Users can now configure ETS tables with the {write_concurrency, auto} option. This option forces tables to automatically change the number of locks that are used at run-time depending on how much concurrency is detected. The {decentralized_counters, true} option is enabled by default when {write_concurrency, auto} is active.

  Benchmark results comparing this option with the other ETS optimization options are available here: benchmarks.

• To enable more optimizations, BEAM files compiled with OTP 21 and earlier cannot be loaded in OTP 25.
• The signal queue of a process with the process flag message_queue_data=off_heap has been optimized to allow parallel reception of signals from multiple processes. This can improve performance when many processes are sending in parallel to one process. See benchmark.
• The Erlang installation directory is now relocatable on the file system given that the paths in the installation’s RELEASES file are paths that are relative to the installations root directory.
• A new option called short has been added to the functions erlang:float_to_list/2 and erlang:float_to_binary/2. This option creates the shortest correctly rounded string representation of the given float that can be converted back to the same float again.
• Introduction of quote/1 and unquote/1 functions in the uri_string module - a replacement for the deprecated functions http_uri:encode and http_uri:decode.
• The new module peer supersedes the slave module. The slave module is now deprecated and will be removed in OTP 27.

• global will now by default prevent overlapping partitions due to network issues. This is done by actively disconnecting from nodes that reports that they have lost connections to other nodes. This will cause fully connected partitions to form instead of leaving the network in a state with overlapping partitions.

  It is possible to turn off the new behavior by setting the the kernel configuration parameter prevent_overlapping_partitions to false. Doing this will retain the same behavior as in OTP 24 and earlier.

• The format_status/2 callback for gen_server, gen_statem and gen_event has been deprecated in favor of the new format_status/1 callback.

  The new callback adds the possibility to limit and change many more things than the just the state.

• The timer module has been modernized and made more efficient, which makes the timer server less susceptible to being overloaded. The timer:sleep/1 function now accepts an arbitrarily large integer.

Compiler

• The maybe ... end construction as proposed in EEP-49 has been implemented. It can simplify complex code where otherwise deeply nested cases would have to be used.

  To enable maybe, give the option {enable_feature,maybe_expr} to the compiler. The exact option to use will change in a coming release candidate and then it will also be possible to use from inside the module being compiled.

• When a record matching or record update fails, a {badrecord, ExpectedRecordTag} exception used to be raised. In this release, the exception has been changed to {badrecord, ActualValue}, where ActualValue is the value that was found instead of the expected record.
• Add compile attribute -nifs() to empower compiler and loader with information about which functions may be overridden as NIFs by erlang:load_nif/2.
• Improved and more detailed error messages when binary construction with the binary syntax fails. This applies both for error messages in the shell and for erl_error:format_exception/3,4.

Crypto

• Add crypto:hash_equals/2 which is a constant time comparision of hashvalues.

Dialyzer

• Optimize operations in the erl_types module. Parallelize the Dialyzer pass remote.
• Added the missing_return and extra_return options to raise warnings when specifications differ from inferred types. These are similar to, but not quite as verbose as overspecs and underspecs.
• Dialyzer now better understands the types for min/2, max/2, and erlang:raise/3. Because of that, Dialyzer can potentially generate new warnings. In particular, functions that use erlang:raise/3 could now need a spec with a no_return() return type to avoid an unwanted warning.

Misc

• A new DEVELOPMENT HOWTO guide has been added that describes how to build and test Erlang/OTP when fixing bugs or developing new functionality.
• Testing has been added to the Github actions run for each opened PR so that more bugs are caught earlier when bug fixes and new features are proposed.

For more details about new features and potential incompatibilities see

• https://erlang.org/download/otp_src_25.0-rc2.readme

Permalink

Rational number arithmetic in Erlang | FQA 2

This is post number 2 in an ongoing series called Foundations of QAnal.

Outline

The goal for today is for you to understand

• what a rational number is
• how it is represented in Erlang
• how the operations are defined
• basic properties of the operations

This is going to be brief (ish). I want to talk cool stuff like rational geometry. But first we have to talk about this.

This is (mostly) tedium. Most of this is known to every single math major (the stuff that isn’t is the weird details that the computability constraint imposes).

This is something you go over once in a “Foundations of Analysis” course (oh wait that’s what this is…), you get it, you move on, and you never worry about it again.

However, non-mathematicians are probably unclear on some of the mathematical terminology. Like, for instance, what exactly a “rational” number is and what distinguishes it from an “irrational” number.

I’m going to selectively skip some detail. Specifically, I’m going to skip most of the detail of why our “make sure every rational number has unique representation” procedure works. There’s a very deep rabbit hole of detail that you can dive into there.

Said detail is crucially important for logical rigor, but adds almost nothing in terms of cognitive clarity. Moreover, I already explained all of that excrutiating detail in my Math for Programmers playlist. So go watch that if you really want to dig in. Or if you’re a bookcel, try chapter 4 of Concrete Mathematics or chapter 1 of Numbers, Groups, and Cryptography.

The Rational Numbers

A [rational number] is what you probably know as a fraction. It means a ratio of two integers. Rationals are also called “quotients” In mathematics, the standard notation for rational numbers is a capital Q (hence QAnal = rational analysis).

I will use the terms “rational”, “fraction”, “ratio”, and “quotient” interchangeably.

So, let’s pick a starting point for some definitions and we’ll improve it as we move on

Defining rationals: first attempt

1. A rational number is a pair of integers {T, B}, where B is not 0.
2. T is called the top (or the numerator) of the fraction
3. B is called the bottom (or denominator) of the fraction
4. Two rationals {T1, B1} and {T2, B2} are equal precisely when

   0 =:= T1*B2 - T2*B1

I first want you to note a pattern here:

• we defined a higher-order data structure (rationals) in terms of a lower-order data structure (integers)
• we imposed a new definition of “equals” on our higher-order data structure which is written in terms of the lower-order data structure; that is, to calculate if two rationals are equal, you calculate the integer T1*B2 - T2*B1 and check to see if it is equal to the integer 0.QAnal happens to have the property that everything ends up being written as finite computations with integer arithmetic. Which is extremely significant. The CIA’s math does not have this property.

Anyway. In mathematics, this design pattern is known as [quotienting]. Which is some lovely terminology overloading. It’s a very important idea that will come up again and again and again, and so I want to note it when it shows up.

The QAnal Equity Principle

There’s a problem straightaway with this definition. It’s not a mathematical or logical flaw. It’s a practical flaw: we have many different pairs of integers that refer to the same rational number. For instance

1> RatEq = fun({T1, B1}, {T2, B2}) -> 0 =:= T1*B2 - T2*B1 end.
#Fun<erl_eval.43.65746770>
2> RatEq({1,2}, {2,4}).
true
3> RatEq({1,2}, {-2,-4}).
true
4> RatEq({1000,-20}, {-50,1}).
true
4> RatEq({100,-20}, {-50,1}).
false

The equality definition is reflective of the fact that we can scale the top and bottom of any fraction by a nonzero integer, and it represents the same fraction. So for instance, {1, 2} is the same fraction as {2, 4}, which is the same as {3, 6} and so on.

If you stare carefully at the expression X = T1*B2 - T2*B1, you will notice that if we take T1 and B1 and multiply both of them by a nonzero integer C, it has the effect of scaling X. That is:

X = T1*B2 - T2*B1

(C*T1)*B2 - T2*(C*B1)
    = C*(T1*B2 - T2*B1)
    = C*X

The same thing happens if you scale T2 and B2. So the test for rational equality captures the fact that rationals have this scale-invariance to them.

In mathematics, this does not represent a problem. In computing, it does.

This brings up a principle of QAnal that I should have mentioned in the original post: equal things must have equal representation. This is the QAnal Equity Principle.

The QAnal Equity Principle implies that there must exist a procedure (which we call a [reduction procedure]) that reduces all members of a given [equivalence class] to a [canonical form]. You don’t have to do some secondary check to see if two things are equal. You look at the representation, and the two things are either equal or they aren’t.

Most of this post concerns the reduction procedure for rationals.

The CIA’s mathematics is laughably incompatible with the QAnal Equity Principle. A “real number” for instance is typically defined as an equivalence class of Cauchy sequences of rational numbers (never mind what exactly that means). There is not even a way to determine in finite time if two such Cauchy sequences lie in the same equivalence class, let alone a reduction procedure.

Why Haskell sucks

Some programming languages, such as Haskell, don’t have a universal “equals”, and instead insist that you explicitly define equals for each new data structure.

-- File: Rat.hs
module Rat where

data Rat = Rat {top :: Integer,
                bot :: Integer}

instance Eq Rat where
    (==) (Rat t1 b1) (Rat t2 b2) =
        (==) 0
             ((-) ((*) t1 b2)
                  ((*) t2 b1))


-- |shortcut for Rat that crashes if second argument is 0
q :: Integer -> Integer -> Rat

q _ 0 = error "cannot divide by zero"
q t b = Rat t b

In GHCi:

GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/doctorajaykumar/.ghc/ghci.conf
Prelude> :l Rat.hs
[1 of 1] Compiling Rat              ( Rat.hs, interpreted )
Ok, modules loaded: Rat.
*Rat> (q 1 2) == (q 2 4)
True
*Rat> (q 1 2) == (q (-2) (-4))
True
*Rat> (q 1000 (-20)) == (q (-50) 1)
True
*Rat> (q 100 (-20)) == (q (-50) 1)
False

This seems nice but it has the effect of limiting the scope of pattern matching within the language. For instance, consider this Erlang code

-module(eq).

-export([eq/2]).

eq(X, X)             -> "pattern equal";
eq(X, Y) when X == Y -> "compare equal";
eq(_, _)             -> "not equal".

This is meant to illustrate the difference between “pattern equals” and “compare equals”:

1> c(eq).
{ok,eq}
2> eq:eq(0, 0.0).
"compare equal"
3> eq:eq(0, 0).
"pattern equal"
4> eq:eq(0, 1).
"not equal"

When writing this, I naively tried to do something similar for Haskell:

-- |equals demonstration
eq :: Rat -> Rat -> String

eq x x             = "pattern equal"
eq x y | (==) x y  = "compare equal"
       | otherwise = "not equal"

But it turns out that code doesn’t compile

Prelude> :l Rat.hs 
[1 of 1] Compiling Rat              ( Rat.hs, interpreted )

Rat.hs:23:4: error:
    • Conflicting definitions for ‘x’
      Bound at: Rat.hs:23:4
                Rat.hs:23:6
    • In an equation for ‘eq’
Failed, modules loaded: none.

I haven’t written much Haskell in years, and it seems during that time I’ve forgot some subtleties of the language.

The effective premise of Haskell (and similar languages) is that you can typecheck away all possible errors that might occur in your code. That’s just false.

There is a correct statement that is similar. Functional languages tend to have the property that once you sort out the shapes of your data, the procedural code writes itself. This is a theme throughout QAnal.

This is remarkable, and it’s why functional programming is fundamentally easy: you can offload all of the cognitive complexity of your program into your data structures.

However. You cannot offload uncertainty into your data structures. Crashes happen. Hardware fails. Disk reads fail. Networks fail. You can’t typecheck reality.

Type systems are fake news

Note also that I used the word shape rather than type.

Lately I’ve been working primarily with two languages: Erlang and TypeScript. Neither of these languages have real type systems.

(Erlangers: TypeScript is basically dialyzer.js.)

Both languages instead have something called “success type systems”. This basically means that the type checker will only catch type errors at the point where data that violates the typespec is passed into a function call.

Dialyzer and TypeScript have pretty much identical origin stories: there’s a dynamically typed language but hoomans make type errors and want a type checker. So you invent a fake type system that is optional and can be applied gradually, then overlay it on top of the language.

Working with two similar, but slightly different success type systems has granted me a minor epiphany: type systems are fake news.

[ 5:32 AM ] Supreme Founder Ajay Kumar PHD : I was giving a naive definition of rationals as pairs of integers, and then saying this doesn't work because we have distinct pairs that correspond to equal rationals
[ 5:32 AM ] Supreme Founder Ajay Kumar PHD : And it's led to an interesting tangent about why Haskell sucks
[ 5:43 AM ] Supreme Founder Ajay Kumar PHD : @zxq9 you said something in a podcast a while ago about type systems. Something like C programmer graybeards who hate the world will tell you that there's only one type of data, and that's binary. The context of what you pretend the binary means is what gives something meaning
[ 5:44 AM ] zxq9 : Yes.
[ 5:44 AM ] zxq9 : Specifically, the only real data type in computerland is binary integers.
[ 5:44 AM ] zxq9 : You just pretend that means different things depending on what you are doing with it at the moment.
[ 5:45 AM ] zxq9 : The Quake III fast inverse square root thing is an example of that.
[ 5:45 AM ] Supreme Founder Ajay Kumar PHD : yeah ok I'll add that
[ 5:47 AM ] zxq9 : Same like when people pack a double with some specific data that has nothing to do with doubles (like a long unicode multibyte they know for certain can never be larger than 8 bytes or whatever) because they can stash it in a register temporarily to avoid a round trip out to the cache because they know nothing else can possibly be using that register just then to speed up unicode processing.
[ 5:49 AM ] zxq9 : Weird black magic tricks like this are possible because at the root there is only one data type as far as the computer is concerned: binary integers. What it does with those integers, integer operations, memory fetches, floating point operations, etc. is merely a function of the circuitry you happen to decide to wiggle with those bits attached -- the processor has no inherent meanings of its own that are attached. All of the meanings the computer "knows" and every belief it holds at that level are represented purely by the arrangement of the gates, and it mechanistically and faithfully pulses electrons through them, oblivious to whether it means anything, is in error, or is "good" or "bad". 
[ 5:50 AM ] zxq9 : We give those numbers meanings at a different layer. Stated differently and at a very different level of interpretation, playing DayZ or having this little chat online is the Holographic Principle in action.

So, the reason Haskell sucks is that you end up spending most of your development time fighting with the type system. (Well, actually, you spend most of your time fighting with the packaging system, but you get my point.) All of your cognitive energy ends up being spent trying to shoehorn your problem into Haskell’s type system, where most of the time it really doesn’t fit.

In our terminology, Haskell’s type system has Angry Dragon Problems. And it ultimately stems from the false assumption that types are real, and the subsequent insistence that types should play a primary role in development.

In Erlang and TypeScript, the typechecker is your assistant. In Haskell, the typechecker is your boss.

The typechecker should be your assistant.

Data structures are shapes. They are not types. That’s what “structure” means.

/rant

The Reduction Procedure for Rationals

Anyway, Erlang has shapes, not types. And it has a universal equals. And when you’re coding, you want to lean on the universal equals. Since we’re doing this in Erlang, we need to follow the QAnal Equity Principle.

Therefore we must do the following

1. Define our canonical form for rationals.
2. Define the reduction procedure.

So let me tell you the definitions.

What does “positive” mean?

We have to talk about signs in a minute, so I want to clear up some terminology.

Apparently the word “positive” is ambiguous. Half of the English-speaking world includes 0 as a positive number, and the other half does not. I am from the half of the world where 0 is not a positive number.

Everyone agrees that “strictly positive” excludes 0, and that the word “non-negative” means numbers that are either strictly positive or zero.

The word “non-negative” sucks, because

1. It’s double negation which is confusing.
2. The half of the English-speaking world that thinks 0 is positive also thinks that 0 is negative, which would make them logically believe that “non-negative” and “strictly positive” are synonyms.Thankfully, mathematical terminology has a solid reputation of being confusing and illogical, so this is not an issue that appears in practice.

I will try to avoid this issue, but will probably fail. Here is the convention I will follow:

• X is [strictly positive] precisely when 0 < X.
• X is [strictly negative] precisely when X < 0.
• X is [HIV-positive] precisely when 0 =< X (because this terminology is AIDS).
• X is [HIV-negative] precisely when X =< 0.
• I will try to use the phrases [strictly positive] and [strictly negative] to avoid ambiguity, but will not be very good at it.
• Absent qualification, [positive] means [strictly positive], and [negative] means [strictly negative].

Defining rationals, second attempt

1. A canonical rational number is a pair of integers {T, B} with the following properties
   1. B is strictly positive; that is, 0 < B.
   2. The [greatest common divisor] of T and B is 1.(BTW, pairs of integers whose GCD is 1 are called [coprime] or [relatively prime]).
2. T is called the top of the fraction.
3. B is called the bottom of the fraction.
4. Two canonical-rationals {T1, B1} and {T2, B2} are equal precisely when

   {T1, B1} =:= {T2, B2}

Why this definition is correct

The condition 0 < B takes care of the sign ambiguity:

*Rat> (q 1 (-2)) == (q (-1) 2)
True

The top of the fraction can be positive, negative, or zero. The bottom of the fraction must always be strictly positive. Division by zero is never allowed, so the bottom of the fraction can never be zero.

We could just as easily store the “sign bit” in the bottom of the fraction instead of the top. However, in that case, the bottom of the fraction could be strictly positive or strictly negative, but never zero, and the top of the fraction would have to be HIV-positive. Storing the sign bit in the top is more elegant.

The GCD condition takes care of the scale ambiguity:

*Rat> (q 1 2) == (q 40 80)
True

Erlang definition of rationals and the reduction procedure

So alas, here is our type definition (source):

-type z()   :: qx_z:z().
-type zp()  :: qx_z:zp().
-type q()   :: {q, z(), zp()}.

Z (short for German Zahlen = “numbers”) is standard mathematical notation for “integers”. If we look inside the qx_z module, we can see that these are just aliases for standard Erlang types.

-type z()   :: integer().
-type znn() :: non_neg_integer().
-type zp()  :: pos_integer().

And our reduction procedure (source):

-spec q(z(), z()) -> q().
% @doc form the quotient of two integers

% Cannot divide by zero
q(_, 0) ->
    error(badarg);
q(Top, Bot) when Bot < 0 ->
    q(-1 * Top, -1 * Bot);
q(Top, Bot) when 0 < Bot,
                 is_integer(Top),
                 is_integer(Bot) ->
    GCD = qx_z:gcd(Top, Bot),
    {q, Top div GCD,
        Bot div GCD}.

The logic is as follows

1. No division by zero.

   q(_, 0) ->
       error(badarg);

2. If the bottom of the fraction is negative, (using the scale invariance property) scale the top and bottom of the fraction by -1 and try again:

   q(Top, Bot) when Bot < 0 ->
       q(-1 * Top, -1 * Bot);

3. Otherwise, divide the top and bottom of the fraction by their GCD, and store that.

   q(Top, Bot) when 0 < Bot,
                    is_integer(Top),
                    is_integer(Bot) ->
       GCD = qx_z:gcd(Top, Bot),
       {q, Top div GCD,
           Bot div GCD}.

Every time QAnal constructs a rational number, it uses this q function. This ensures canonical representation throughout.

Why does this reduction procedure work?

So this begs two questions:

1. Why is it that if we divide the top and bottom of the fraction by their GCD, then the resulting pair of integers is coprime?
2. How does qx_z:gcd/2 work?

I will give a fake answer the first question, and give a real answer to the second question.

The fake answer to the first question is to look at the prime factorizations of the two integers.

Let’s switch to Scheme for a moment, and consider the fraction 105/60.

scheme@(guile-user)> 105/60
$1 = 7/4
scheme@(guile-user)> (* 3 5 7)
$2 = 105
scheme@(guile-user)> (* 3 4 5)
$3 = 60
scheme@(guile-user)> (/ (* 3 5 7)
                        (* 3 4 5))
$4 = 7/4

You see that the GCD ends up being the “intersection” of the prime factorizations, and so when you divide by it, it cancels all the common factors.

The reason this is a fake answer is it begs the question “why is prime factorization unique?” That is, why is there not a different set of prime numbers whose product is 105?

Well it turns out that the proper way to set this up logically is to start with the GCD algorithm. Then you use the properties of the GCD algorithm to prove the uniqueness of factorization.

I took some moderate care to set this up correctly in my Math for Programmers playlist. So go consult that. Or look at one of the books I suggested (links in the links section).

It’s very voluminous, only moderately interesting, and somewhat outside the scope of this post. You’ve gone your entire life without knowing why integer factorization is unique, and you’re doing just fine. Let’s keep going.

Euclid’s GCD Algorithm

First of all, I should mention that the glowies are playing some word games with the word “greatest”. See, friend, whenever someone says that X is “best” or “greatest”, there’s an implicit ordering relation with respect to which X is the greatest.

The glowie word game here is subtly changing the ordering relation under your nose and not telling you. The CIA’s favorite activity is implicit context swaps. That’s why glowies love object-oriented programming.

This by the way is why the CIA is going woke. At the bottom, the CIA’s mathematics is based on smoke and mirrors and retarded word games. Wokeism is entirely smoke and mirrors and retarded word games. Glowie mathematicians in woke discourse are like a pig in shit. This is their whole thing.

The glowies implicit ordering relation with respect to which the GCD is greatest is the divisibility ordering on integers. In particular:

• 1 is the universal lower bound (1 divides everything and nothing divides 1)
• 0 is the universal upper bound (0 divides nothing and everything divides 0)

The divisibility ordering differs in many subtle ways from the standard ordering. For instance, the standard ordering is a total order: given two integers X and Y, at least one of the following statements is true:

• X =< Y
• Y =< X

This is not true with divisibility, which is a partial ordering.

I explored this caveat in slightly more depth in the Math for Programmers playlist.

For our purposes, this doesn’t actually matter. The first thing we do in computing gcd is make sure both arguments are HIV-positive. And on HIV-positive integers, the divisibility ordering implies the standard ordering, except for the fact that 0 is a universal upper bound. That is:

• if X and Y are strictly positive integers and X divides Y
• then X =< Y with respect to the standard ordering

This is a pitfall that you might have to be aware of at some point down the line. And it’s very important to be alert at all times for signs of glowie word games.

The proper definition is: the [greatest common divisor] of a set S of integers is the greatest lower bound of S with respect to the divisibility relation.

Anyway, algorithm. It’s extremely simple.

The first premise is that gcd is HIV-positive: meaning if we have the fractions (/ -105 60) or (/ 105 60), the thing we want to cancel from the top and bottom is the same.

So the first thing we do is make sure both arguments are HIV-positive (source):

% make sure both arguments are HIV-positive
gcd(X, Y) ->
    gcdabs(abs(X), abs(Y)).

The next premise is that gcd is symmetric: meaning if we have the two fractions 60/105 or 105/60, the integer we want to cancel from top and bottom is the same. So we establish a convention that the bigger number goes on the left (source).

% gcd where the arguments can be assumed to be HIV-positive,
% but not necessarily in the correct order
%
% This function is responsible for making sure the argument on
% the left is bigger than or equal to the argument on the right.

gcdabs(X, Y) when X < Y ->
    gcdplus(Y, X);
gcdabs(X, Y) when X >= Y->
    gcdplus(X, Y).

And finally we get to the heart of the matter: qx_z:gcdplus/2.

% gcd where the arguments can be assumed to be HIV-positive and
% in the correct order

% zero is a universal upper bound in the divisibility relation.
% so when compared with anything, return the other thing
gcdplus(X, 0) ->
    X;
% X might be equal to Y here, in which case, modulo(X, Y) = 0, and
% the next call will degenerate into the base case
gcdplus(X, Y) when X >= Y ->
    % X = qY + R
    % R = X - qY
    % 0 =< R < Y
    % therefore any common divisor of X and Y (such as the gcd) also
    % divides R
    % therefore
    % gcd(X, Y) ->
    %   gcd(Y, R)
    gcdplus(Y, modulo(X, Y)).

modulo/2 is a function that in this cases matches the rem operator in Erlang.

Let’s walk though that 105 and 60 example:

gcdplus(105, 60) ->
    % 105 rem 60 = 45
    gcdplus(60, 45) ->
        % 60 rem 45 = 15
        gcdplus(45, 15) ->
            % 45 rem 15 = 0
            gcdplus(15, 0) ->
                % base case
                15

And if you remember our little Scheme thing, it’s true that 15 is the product of the common factors:

scheme@(guile-user)> 105/60
$1 = 7/4
scheme@(guile-user)> (* 3 5 7)
$2 = 105
scheme@(guile-user)> (* 3 4 5)
$3 = 60
scheme@(guile-user)> (/ (* 3 5 7)
                        (* 3 4 5))
$4 = 7/4

The rational number operations

I will refer you to the code. Now that we’ve ironed out all of our shapes, the procedures are obvious. Godspeed.

Properties of integer arithmetic

In QAnal, we assume that these are true.

Below, I illustrate how the rational number arithmetic properties are consequences of the integer arithmetic properties.

It is possible, in a similar way, to rewrite the integer arithmetic properties in terms of a more “primitive” data structure (say, Peano arithmetic). I don’t think there’s anything to be gained clarity-wise from doing things like that, but it can be done.

It’s mathturbation: it’s not necessarily wrong to do it, but it’s probably wrong to do it in public. Nonetheless, there’s tons of videos on the internet if you want to learn how.

The properties of the integer operations are the [commutative ring] properties:

1. Addition is associative:

   (equal? (z+ (z+ a b) c)
           (z+ a (z+ b c))
           (z+ a b c))

2. Addition is commutative:

   (equal? (z+ x y)
           (z+ y x))

3. There is a unique integer called zero which has the property of being an additive identity:

   (equal? x
           (z+ zero x)
           (z+ x zero))

4. For each integer x there exists a unique integer (minus x) which is its additive inverse:

   (equal 0
          (z+ x (minus x))
          (z+ (minus x) x))

5. Multiplication is associative:

   (equal? (z* (z* a b) c)
           (z* a (z* b c))
           (z* a b c))

6. Multiplication is commutative:

   (equal? (z* x y)
           (z* y x))

7. There is a unique integer called one which has the property of being a multiplicative identity:

   (equal? x
           (z* one x)
           (z* x one))

8. Multiplication distributes over addition

   (equal? (z+ (z* a b) (z* a c))
           (z* a (z+ b c)))

Properties of rational arithmetic

The first 8 properties are identical to those of integers. There is only one addtional property and that concerns division of rationals.

The properties of the rational operations are the [field] properties:

1. Addition is associative:

   (equal? (q+ (q+ a b) c)
           (q+ a (q+ b c))
           (q+ a b c))

2. Addition is commutative:

   (equal? (q+ x y)
           (q+ y x))

3. There is a unique rational called zero which has the property of being an additive identity:

   (equal? x
           (q+ zero x)
           (q+ x zero))

4. For each rational x there exists a unique rational (minus x) which is its additive inverse:

   (equal zero
          (q+ x (minus x))
          (q+ (minus x) x))

5. Multiplication is associative:

   (equal? (q* (q* a b) c)
           (q* a (q* b c))
           (q* a b c))

6. Multiplication is commutative:

   (equal? (q* x y)
           (q* y x))

7. There is a unique rational called one which has the property of being a multiplicative identity:

   (equal? x
           (q* one x)
           (q* x one))

8. Multiplication distributes over addition

   (equal? (q+ (q* a b) (q* a c))
           (q* a (q+ b c)))

9. Every rational x that is different from zero has a multiplicative inverse, called (oneover x), with the property

   (equal? one
           (q* x (oneover x)))

Homework

Prove the properties of rational number operations.

What do I mean by that? What I mean is to use the rewrite layer idea: everything in QAnal can be rewritten in terms integer arithmetic.

So assume the properties of integer arithmetic are true, and also assume the scale invariance of rationals (the thing where if you multiply the top and bottom by the same nonzero integer, it’s the same rational number).

All you will need to do is some very straightforward algebra. In each case, you can show that if the properties of integer arithmetic are true, then the properties of rational arithmetic are true.

Disclaimer: I haven’t done this and I’m tired so that’s why it’s an exercise.

Example: proof that rational addition is associative

Let me give an example: I will prove that rational number addition is associative.

-spec plus(q(), q()) -> q().
% @doc add two rationals

plus({q, TL, BL}, {q, TR, BR}) ->
    % make common denominator
    q((TL * BR) + (TR * BL),
      BR * BL).

I accidentally chose the hardest example so this is a bit long. But I did the hardest part of your homework for you.

I think this is a bit clearer in Scheme-ish notation

(equal? (q+ (/ t1 b1)
            (/ t2 b2))
        (/ (z+ (z* t1 b2)
               (z* t2 b1))
           (z* b1 b2)))

We are trying to prove that

(equal? (q+ (q+ q1 q2) q3)
        (q+ q1 (q+ q2 q3)))

I’m used to the CIA’s notation, and so it’s very likely that I made an error in the S-expression manipulations below. One interesting constraint that the blog medium imposes is that I cannot use CIA notation. So far I like this constraint.

So let’s just pick this apart

; rewrite treelike
(equal? (q+ (q+ q1
                q2)
            q3)
        (q+ q1
            (q+ q2
                q3)))

; expand each of q1, q2, q3
(equal? (q+ (q+ (/ t1 b1)
                (/ t2 b2))
            (/ t3 b3))
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; inside out rewrite, starting on the left:
(equal? (q+ (/ (z+ (z* t1 b2)
                   (z* t2 b1))
               (z* b1 b2))
            (/ t3 b3))
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; reformat so tops and bottoms are visually easier to pick out
; (no change to tree structure)
(equal? (q+ (/ (z+ (z* t1 b2) (z* t2 b1))
               (z* b1 b2))
            (/ t3
               b3))
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; again rewriting inside out starting on the left
;
; q+ rewrites as
;
;   - quotient of
;       - sum of
;           - product of
;               - top left
;               - bottom right
;           - product of
;               - top right
;               - bottom left
;       - product of
;           - bottom left
;           - bottom right
;
; jesus christ
(equal?
        ; quotient of
        (/
            ; sum of
            (z+
                ; product of
                (z*
                    ; top left
                    (z+ (z* t1 b2) (z* t2 b1))
                    ; bottom right
                    b3
                )
                ; product of
                (z*
                    ; top right
                    t3
                    ; bottom left
                    (z* b1 b2)
                )
            )
            ; product of
            (z*
                ; bottom left
                (z* b1 b2)
                ; bottom right
                b3
            )
        )
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; take binary trees with identical associative/commutative stems
; and rewrite them as a single n-ary tree where the branches are
; arranged alphabetically
;
; so for instance:
;
;       (z* t3 (z* b1 b2))
;
; becomes
;
;       (z* b1 b2 t3)
;
; result:
(equal?
        ; quotient of
        (/
            ; sum of
            (z+
                ; product of
                (z*
                    ; top left
                    (z+ (z* b1 t2) (z* b2 t1))
                    ; bottom right
                    b3
                )
                ; product of
                (z* b1 b2 t3)
            )
            ; product of
            (z* b1 b2 b3)
        )
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; apply the distributive law to collapse the tree some more
(equal?
        ; quotient of
        (/
            ; sum of
            (z+
                (z* b1 b2 t3)
                (z* b1 b3 t2)
                (z* b2 b3 t1)
            )
            ; product of
            (z* b1 b2 b3)
        )
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; reformat (no change to structure)
(equal? (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3))
        (q+ (/ t1 b1)
            (q+ (/ t2 b2)
                (/ t3 b3))))

; alright now we get to do all of that again, but to the
; right-hand side.
;
; first we expand out the innermost q+ and rewrite it as integer
; operations
;
; I learned from experience on the left side that it's best to
; pre-emptively sort terms in dictionary order when the integer
; operations allow it. So I'm going to do that without saying it
; explicitly, alright?
(equal? (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3))
        (q+ (/ t1 b1)
            (/ (z+ (z* b2 t3)
                   (z* b3 t2))
               (z* b2 b3))))

; reformat so tops and bottoms are vertically aligned in each
; quotient
(equal? (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3))
        (q+ (/ t1
               b1)
            (/ (z+ (z* b2 t3) (z* b3 t2))
               (z* b2 b3))))

; alright. q+ rewrites as
;
;   - quotient of
;       - sum of
;           - product of
;               - top left
;               - bottom right
;           - product of
;               - top right
;               - bottom left
;       - product of
;           - bottom left
;           - bottom right
;
; jesus christ
(equal? (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3))
        ; quotient of
        (/
            ; sum of
            (z+
                ; product of
                (z*
                    ; top left
                    t1
                    ; bottom right
                    (z* b2 b3)
                )
                ; product of
                (z*
                    ; top right
                    (z+ (z* b2 t3) (z3* b3 t2))
                    ; bottom left
                    b1
                )
            )
            ; product of
            (z*
                ; bottom left
                b1
                ; bottom right
                (z* b2 b3)
            )
        )
)

; alright. home stretch folks
; let's apply some integer magic to the right hand side and go
; home
(equal? (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3))
        ; quotient of
        (/
            ; sum of
            (z+
                ; associative and commutative laws:
                (z* b2 b3 t1)
                ; distributive law
                (z+
                    (z* b1 b2 t3)
                    (z* b1 b3 t2)
                )
            )
            ; associative law
            (z* b1 b2 b3)
        )
)

; more integer magic:
(equal? (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3))
        (/ (z+ (z* b1 b2 t3)
               (z* b1 b3 t2)
               (z* b2 b3 t1))
           (z* b1 b2 b3)))

And alas, we have the same expressions on both sides, so the statement is true.

A tradeoff in QAnal

Proofs in QAnal typically end up being like this: very long, often laborious, and tedious chains of algebra.

We end up trading away a bit of intuition, and in exchange we get back logic that is extremely concrete and extremely verbose.

Links and Further reading

• Foundations of QAnal category
• Math for Programmers playlist
• Quake III Fast Inverse Square Root Algorithm
• QAnal source tree at the time of writing
  • qx_q module
    • qx_q:q typedef
    • qx_q:q/2 function
  • qx_z module
    • qx_z:gcd/2
    • qx_z:gcdabs/2
    • qx_z:gcdplus/2 function
• Wikipedia commutative ring
• Wikipedia field
• Book suggestions:
  • Concrete Mathematics
  • Numbers, Groups, and Cryptography

Permalink