Planet NoName e.V.

01. January 2001

koebi

Über

Blog von Jakob “koebi” Schnell. Alltägliches über Musik, Computer, Mathe und wassonstsopassiert. Zweisprachig Englisch/Deutsch. Gegebenenfalls auch irgendwann konsistent. Erstellt mittels hugo unter Verwendung von hugo-Xmin

01. January 2001 00:00:00

17. April 2018

sECuREs Webseite

kinX: USB Hub

This post is part of a series of posts about the kinX project.

Motivation

The Kinesis Advantage comes with a built-in 2-port USB hub. That hub uses a proprietary connector to interface with a PS/2 keyboard controller, so it cannot be used with a USB keyboard controller. As the built-in hub is the natural place to connect the Logitech unified receiver dongle, not being able to use the hub is mildly annoying.

The kinX MK66F keyboard controller presently needs two USB cables: one connected to the USBFS port to supply the PCB with power and receive firmware updates (via the Teensy bootloader chip), and one connected to the USBHS port for the actual keyboard device.

Lastly, even if the original built-in USB hub had internal ports (instead of a PS/2 converter), it only supports USB 1.1, nullifying any latency improvements.

Hence, I decided to build a drop-in replacement USB 2.0 hub with 2 external USB ports and 2 internal USB ports, using the same proprietary connector as the original, so that the original keyboard USB cable could be re-used.

Design phase

Unfortunately, I could not find an open hardware USB 2.0 hub design on the internet, so I started researching various USB hub chips. I quickly discarded the idea of using USB 3 due to its much stricter requirements.

In the end, I decided to go with the Cypress HX2VL series because of their superior documentation: I found a detailed data sheet, an evaluation board, the associated schematics, design checklist/guidelines, and even the evaluation board’s bill of materials.

This is what the finished build of my design looks like:

Power

After completing my first build, I tested a few USB devices with my hub. The Logitech unified receiver dongle and the YubiKey worked fine. However, my external hard drive and my USB memory stick did not work. In the syslog, I would see:

kernel: usb 1-14.4.4: rejected 1 configuration due to insufficient available bus power

This is because the USB specification limits bus-powered hubs to 100mA per port. While high power usage does not come as a surprise for the external hard disk, it turns out that even my USB memory stick requires 200mA. This was a surprise, because that stick works on other, commercial bus-powered USB hubs.

A closer look reveals that all 3 commercial USB hubs I have tested claim to be self-powered (i.e. using an external power supply), even though they are not. This way, the kernel’s power limitation is circumvented, and up to 500mA can be used per port. In practice, the host port only supplies 500mA, so the user must be careful not to plug in devices which require more than 500mA in aggregate.

I changed the SELFPWR configuration pin to have my hub claim it was self-powered, too, and that made all USB devices I tested work fine.

EEPROM programming

When debugging the power issue, I originally thought the Maximum Power setting in the hub’s USB device descriptor needed to be raised. This turned out to not be correct: the Maximum Power refers to the power which the hub uses for its own circuitry, not the power it passes through to connected devices.

Nevertheless, it’s a nice touch to modify the device descriptor to put in a custom vendor name, product name and serial number: that way, the device shows up with a recognizable name in your syslog or lsusb(8) output, and udev rules can be used to apply settings based on the serial number.

To modify the device descriptor, an EEPROM (electrically erasable programmable read-only memory) needs to be added to the design, from which the HX2VL will read configuration.

The HX2VL allows field-programming of the connected EEPROM, i.e. writing to it via the USB hub chip. I found the Windows-only tool hard to set up on a modern Windows installation, so I wondered whether I could build a simpler to use tool.

Under the covers, the tool merely sends commands with the vendor-specific request code 14 via USB, specifying an index of the two-byte word to read/write. This can be replicated in a few lines of Go:

dev, _ := usb.OpenDeviceWithVIDPID(0x04b4, 0x6570)
eepromRequest := 14
wIndex := 0 // [0, 63] for 128 bytes of EEPROM
dev.Control(gousb.RequestTypeVendor|0x80, 
  eepromRequest, 0, wIndex, make([]byte, 2))

The EEPROM contents are well-described in the HX2VL data sheet, so the rest is easy.

See https://github.com/kinx-project/mk66f-blaster for the tool.

Lessons learnt

  • If possible, design the PCB in such a way that components you think you don’t need (e.g. the EEPROM) can optionally be soldered on. This would have saved me a PCB design/fabrication cycle.

  • Get the evaluation board to figure out the configuration you need (e.g. self-powered vs. bus-powered).

Next up

The last post introduces the processing latency measurement firmware for the FRDM-K66F development board and draws a conclusion.

17. April 2018 15:49:00

kinX: latency measurement

This post is part of a series of posts about the kinX project.

Latency measurement

End-to-end latency consists of 3 parts:

  1. input latency (keyboard)
  2. processing latency (computer)
  3. output latency (monitor)

During the development of the kinX keyboard controller, I realized that measuring processing latency was quite simple with my hardware: I could start a timer when sending a key press HID report to the computer and measure the elapsed time when I would receive a reply from the computer.

The key to send is the Caps Lock key, because unlike other keys it results in a reply: a HID report telling the keyboard to turn the Caps Lock LED on.

Measurement device

To make this measurement technique accessible to as many people as possible, I decided to pull it out of my kinX keyboard controller and instead build it using the FRDM-K66F evaluation board, which uses the same microcontroller.

The FRDM-K66F can be bought for about 60 USD at big electronics shops, e.g. Digi-Key.

Find the firmware at https://github.com/kinx-project/measure-fw

Baseline

To determine the lowest processing latency one can possibly get for userspace applications on a Linux system, I wrote a small program which uses Linux’s evdev API to receive key presses and react to a Caps Lock keypress as quickly as it can by turning the Caps Lock LED on.

Find the program at https://github.com/kinx-project/measure-evdev

The following layers are exercised when measuring this program:

  • USB host controller
  • Linux kernel (USB and input subsystems)
  • input event API (evdev)

Notably, graphical interfaces such as X11 or Wayland are excluded.

The measurements can be verified using Wireshark’s usbmon capturing, which provides a view of the USB bus from the computer’s perspective, excluding USB poll latency and USB transaction time.

Using Ubuntu 17.10, I measured a processing latency of 152 μs on average.

Emacs

Now let’s see whether my current editor of choice adds significant latency.

Using a few lines of Emacs Lisp, I instructed Emacs to turn on the Caps Lock LED whenever a key is inserted into the current buffer. In combination with remapping the Caps Lock key to any other key (e.g. “a”), this allows us to measure Emacs’s processing latency.

On the same Ubuntu 17.10 installation used above, Emacs 25.2.2 adds on average 278 μs to the baseline processing latency.

Find the code at https://github.com/kinx-project/measure-emacs

End-to-end latency

With the kinX keyboard controller, we can achieve the following end-to-end latency:

contributor latency
Matrix scan ≈ 100 μs
USB poll ≈ 125 μs
Linux ≈ 152 μs
Emacs ≈ 278 μs


This sums up to ≈ 655 μs on average. On top of that, we have output latency within [0, 16ms] due to the 60 Hz refresh rate of our monitors.

Note that using a compositor adds one frame of output latency.

Input latency perception

A natural question to ask is how well humans can perceive input latency. After all, keyboards have been manufactured for many years, and if input latency was really that important, surely manufacturers would have picked up on this fact by now?

I ran a little unscientific experiment in the hope to further my understanding of this question at the most recent Chaos Communication Congress in Leipzig.

In the experiment, I let 17 people play a game on a specially prepared keyboard. In each round, the game reconfigures the keyboard to either have additional input latency or not, decided at random. The player can then type a few keys and make a decision. If the player can correctly indicate whether additional input latency was present in more than 50% of the cases, the player is said to be able to distinguish latency at that level. On each level, the game decreases the additional input latency: it starts with 100ms, then 75ms, then 50ms, etc.

The most sensitive player reliably recognized an additional 15ms of input latency.

Some players could not distinguish 75ms of additional input latency.

Every player could distinguish 100ms of additional input latency.

My take-away is that many people cannot perceive slight differences in input latency at all, explaining why keyboard manufacturers don’t optimize for low latency.

Reducing input latency still seems worthwhile to me: even if the reduction happens under the threshold at which you can perceive differences in input latency, it buys you more leeway in the entire stack. In other words, you might now be able to turn on an expensive editor feature which previously slowed down typing too much.

Conclusion

When I started looking into input latency, my keyboard had dozens of milliseconds of latency. I found an easy win in the old firmware, then hit a wall, started the kinX project and eventually ended up with a keyboard with just 0.225ms input latency.

Even if I had not reduced the input latency of my keyboard at all, I feel that this project was a valuable learning experience: I now know a lot more about PCB design, ARM microcontrollers, USB, HID, etc.

Typing on a self-built keyboard feels good: be it because of the warm fuzzy feeling of enjoying the fruits of your labor, or whether the input latency indeed is lower, I’m happy with the result either way.

Lastly, I can now decidedly claim that the processing latency of modern computers is perfectly fine (remember our 152 μs + 278 μs measurement for Linux + Emacs), and as long as you pick decent peripherals, your end-to-end latency will be fine, too.

What’s next?

By far the biggest factor in the end-to-end latency is the monitor’s refresh rate, so getting a monitor with a high refresh rate and no additional processing latency would be the next step in reducing the end-to-end latency.

As far as the keyboard goes, the matrix scan could be eliminated by wiring up each individual key to a microcontroller with enough GPIO pins. The USB poll delay could be eliminated by switching to USB 3, but I don’t know of any microcontrollers which have USB 3 built-in yet. Both of these improvements are likely not worth the effort.

17. April 2018 15:49:00

kinX: keyboard controller with <0.225ms input latency

This post is part of a series of posts about the kinX project.

Background

10 years ago I got a Kinesis Advantage keyboard. I wrote about the experience of learning to touch-type using the ergonomic NEO layout in my (German) post “Neo-Layout auf einer Kinesis-Tastatur”.

The Kinesis Advantage is still the best keyboard I’ve ever used, and I use one every day, both at the office and at home.

I had two reasons to start modifying the keyboard:

  1. I prefer Cherry MX blue key switches over the Cherry MX brown key switches the Kinesis comes with. Nowadays, you can get a Kinesis with Cherry MX red key switches, which felt okay in a quick test.

  2. The original keyboard controller has (had?) a bug where modifier keys such as Shift would get stuck at least once a week: you would press Shift, press A, release A, release Shift, press A and see AA instead of Aa.

I solved issue ① with the help of the excellent Kinesis technical support, who sold me unpopulated PCBs so that I could solder on my own key switches.

Issue ② was what lead to my first own keyboard controller build, which I documented in “Hacking your own Kinesis keyboard controller” (2013).

Then, the topic of input latency popped into my filter bubble, with excellent posts such as Pavel Fatin’s “Typing with pleasure”. I started wondering what input latency I was facing, and whether/how I could reduce it.

Given that I was using a custom keyboard controller, it was up to me to answer that question. After trying to understand and modify the firmware I had been using for the last 4 years, I realized that I first needed to learn much more about how keyboards work.

I firmly believe that creating a good environment is vital for development, especially for intrinsically-motivated side projects like this one. Hence, I set the project aside until a colleague gifted me his old Kinesis which had intermittent issues. I removed the electronics and started using that keyboard as my development keyboard.

Sources of input latency

A keyboard controller has 3 major tasks:

  • matrix scan: to avoid physically connecting every single key switch directly to a microcontroller (requiring a large number of GPIO pins), most keyboards use a matrix. See “How to make a keyboard — the matrix” for a good explanation.

  • debouncing: when pressing a key switch, it doesn’t cleanly change from a low voltage level to a high voltage level (or vice-versa). Instead, it bounces: the voltage level rapidly oscillates until it eventually reaches a stable steady state. Because one key press shouldn’t result in a whole bunch of characters, keyboard controllers need to debounce the key press.

  • USB: nowadays, keyboards use USB (for example to be compatible with laptops, which generally don’t have PS/2 ports), so the keyboard’s state needs to be communicated to the computer via USB.

Here’s an illustration of the timing of a key press being handled by a naive keyboard controller implementation:

In the worst case, a key press happens just after a keyboard matrix scan. The first source of latency is the time it takes until the next keyboard matrix scan happens.

Depending on the implementation, the key press now sits in a data structure, waiting for the debounce time to pass.

Finally, once the key press was successfully debounced, the device must wait until the USB host polls it before it can send the HID report.

Unless the matrix scan interval is coupled to the USB poll interval, the delays are additive, and the debounce time is usually constant: in the best case, a key press happens just before a matrix scan (0ms) and gets debounced (say, 5ms) just before a USB poll (0ms).

Teensy 3.6 controller (for learning)

My old keyboard controller used the Teensy++, which is fairly dated at this point. I decided a good start of the project would be to upgrade to the current Teensy 3.6, cleaning up the schematics on the way.

To ensure I understand all involved parts, I implemented a bare-metal firmware almost from scratch: I cobbled together the required startup code, USB stack and, most importantly, key matrix scanning code.

In my firmware, the Teensy 3.6 runs at 180 MHz (compared to the Teensy++’s 16 MHz) and scans the keyboard matrix in a busy loop (as opposed to on USB poll). Measurements confirmed a matrix scan time of only 100μs (0.1ms).

I implemented debouncing the way it is described in Yin Zhong’s “Keyboard Matrix Scanning and Debouncing”: by registering a key press/release on the rising/falling edge and applying the debounce time afterwards, effectively eliminating debounce latency.

Note that while the Cherry MX datasheet specifies a debounce time of 5ms, I found it necessary to increase the time to 10ms to prevent bouncing in some of my key switches, which are already a few years old.

I set the USB device descriptor’s poll interval to 1, meaning poll every 1 USB micro frame, which is 1ms long with USB 1.x (Full Speed).

This leaves us at an input latency within [0ms, 1.1ms]:

  • ≤ 0.1ms scan latency
  • 0ms debounce latency
  • ≤ 1ms USB poll latency

Can we reduce the input latency even further? The biggest factor is the USB poll interval.

USB High Speed

With USB 2.0 High Speed, the micro frame duration is reduced to 125μs (0.125ms). The NXP MK66F micro controller in the Teensy 3.6 has two USB ports:

  1. the Full Speed-only USBFS port, which is used by the Teensy 3.6
  2. the High Speed-capable USBHS port, which the Teensy optionally uses for host mode, with experimental software support (at the time of writing)

While the software support was a road block which could conceivably be solved, I also faced a mechanical problem: the available space in the Kinesis keyboard and the position of the USB High Speed port pins on the Teensy 3.6 unfortunately prevented installing any sort of breakout board to actually use the port.

I decided to move from the Teensy 3.6 to my own design with the same microcontroller.

MK66F keyboard controller

To make development pleasant, I connected a USB-to-serial adapter (to UART0) and a “rebootor” (to PROGHEAD): another Teensy with a special firmware to trigger programming mode. This way, I could set my editor’s compile-command to make && teensy_loader_cli -r …, compiling the code, uploading and booting into the resulting firmware with a single keyboard shortcut.

I based the firmware for this controller on NXP’s SDK examples, to ensure I get a well-tested and maintained USB stack for the USBHS port. I did some measurements to confirm the stack does not add measurable extra latency, so I did not see any value in me maintaining a custom USB stack.

The firmware can be found at https://github.com/kinx-project/mk66f-fw

The hardware can be found at https://github.com/kinx-project/mk66f-hw

Using USB 2.0 High Speed leaves us at an input latency within [0ms, 0.225ms]:

  • ≤ 0.1ms scan latency
  • 0ms debounce latency
  • ≤ 0.125ms USB poll latency

Lessons learnt

  • In the future, I will base custom designs on the vendor’s development board (instead of on the Teensy). This way, the vendor-provided code could be used without any modifications.

  • While the Teensy bootloader means getting started with the microcontroller just requires a USB port, using a JTAG connector for development would be more powerful: not only does it replace the combination of Teensy bootloader, serial and rebootor, but it also supports debugging with gdb.

Next up

The second post motivates and describes building a drop-in replacement USB hub for the Kinesis Advantage keyboard.

17. April 2018 15:49:00

kinX: overview

The kinX project is described in a series of blog posts:

You can find the project’s artifacts at https://github.com/kinx-project.

17. April 2018 15:49:00

16. April 2018

michael-herbst.com

Oberwolfach reports: Molsturm modular electronic structure theory framework

As announced in my previous post about the Oberwolfach workshop on Mathematical Methods in Quantum Chemistry, the proceedings of each Oberwolfach workshop are published in the form of an article in the Oberwolfach reports. For this purpose each speaker is asked for an extended abstract summarising the content of his or her talk. I have finally submitted the summary of my contribution, namely some quick introduction into Coulomb-Sturmians, lazy matrices and the molsturm framework. The introductory paragraph reads as follows.

The talk gives an overview of our recent efforts to simplify the investigation of novel types of basis functions for quantum-chemical calculations. Motivated by Coulomb-Sturmians as basis functions for quantum-chemistry simulations, the design of the flexible and light-weight quantum-chemical method development framework molsturm is outlined, where new discretisation methods for electronic structure theory calculations can be easily implemented and tested.

A preprint of the full text is available below and some more details regarding the Oberwolfach seminar as well as my talk can be found in my previous post.

by Michael F. Herbst at 16. April 2018 16:00:00

27. March 2018

michael-herbst.com

Oberwolfach workshop: Mathematical Methods in Quantum Chemistry

Last week I was invited to the Mathematical Research Institute Oberwolfach (Mathematisches Forschungsinstitut Oberwolfach) for a workshop about Mathematical Methods in Quantum Chemistry. I am really grateful to the organisers Eric Cancès, Gero Friesecke, Trygve Helgaker and Lin Lin for asking me to join this meeting as it turned out to be a week of interesting talks, stimulating discussions and getting to know many interesting people.

Unlike the typically rather large and tightly scheduled quantum-chemistry conferences, which I went to in the past years, the Oberwolfach workshop was not extremely dense. Much rather there was a lot of free time, where one could talk to other participants and discuss each other's topic very well. Overall I learned a lot about current research regarding the mathematical aspects of quantum chemistry.

One should mention that Oberwolfach, being located in the middle of the Black Forest, has a very unique atmosphere with numerous black boards, comfortable chairs and a huge library scattered around the institute. Whilst it might seem a bit hard to believe in the beginning, this environment really has an inspiring effect, where one starts to sit with fellow researchers and discuss all kinds of interesting topics for many hours and sometimes till late at night. If I am ever offered to return to this place for another meeting or workshop, I would hesitate no second.

On the last day of the workshop, namely last Friday, I was asked to present my current research. For this I choose to give a rather broad overview over molsturm and our recent take on Coulomb-Sturmian-based quantum chemistry. The slides are attached below and an extended abstract about the talk will soon become available as part of the Oberwolfach reports.

Update: The preprint of the extended abstract is now available.

Link Licence
molsturm: Modular electronic structure theory framework
(Slides Oberwolfach talk)
Creative Commons License

by Michael F. Herbst at 27. March 2018 22:00:00

21. March 2018

RaumZeitLabor

Exkursion ins Technoseum Mannheim

Hallo liebe RaumZeitLaborierende, liebe Museumsfans und Technikinteressierte!

Es ist wieder soweit: April heißt Ausflugszeit!

Am Samstag, den 28.04.2018, werden wir 200 Jahre Technik- und Automatisierungsgeschichte in einem der großen Technikmuseen Deutschlands etwas genauer unter die Lupe nehmen.

Los geht’s um viertel nach 12 im Foyer des Technoseums.

Bei der anderthalbstündigen Führung durch verschiedene Ausstellungsstationen der Industrialisierung werden wir uns der Frage stellen „Was bringt die Zukunft – Mensch und Maschine oder Mensch gegen Maschine?“

Ihr wollt dabei sein und Wasserrad und Dampfmaschine aus nächster Nähe anschauen? Kein Problem! Da die Plätze allerdings begrenzt sind, bitte ich bis spätestens zum 21.04.2018 um Rückmeldung per Mail.

Für Mitglieder des Vereins ist diese Tour kostenlos. Nichtmitglieder bitten wir, vor Beginn der Führung 6€ in die RZL-Tourenkasse zu werfen.

by flederrattie at 21. March 2018 00:00:00

18. March 2018

koebi

17. March 2018

sECuREs Webseite

BSD license

Copyright (c) 2006-2018, Michael Stapelberg
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice, this
  list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
* Neither the name of Michael Stapelberg nor the names of its contributors may
  be used to endorse or promote products derived from this software without
  specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

17. March 2018 21:31:29

13. March 2018

sECuREs Webseite

cpu(1) with Linux

motivation

To run the tests of my i3 Go package, I use the following command:

go test -v go.i3wm.org/...

To run the tests of my i3 Go package on a different architecture, the only thing I should need to change is to declare the architecture by setting GOARCH=arm64:

GOARCH=arm64 go test -v go.i3wm.org/...

“Easy!”, I hear you exclaim: “Just apt install qemu, and you can transparently emulate architectures”. But what if I want to run my tests on a native machine, such as the various Debian porter boxes? Down the rabbit hole we go…

cpu(1)

On Plan 9, the cpu(1) command allows transparently using the CPU of dedicated compute servers. This has fascinated me for a long time, so I tried to replicate the functionality in Linux.

reverse sshfs

One of the key insights this project is built on is that sshfs(1) can be used over an already-authenticated channel, so you don’t need to do awkward reverse port-forwardings or even allow the remote machine SSH access to your local machine.

I learnt this trick from the 2014 boltblog post “Reverse SSHFS mounts (fs push)”.

The post uses dpipe(1)’s bidirectional wiring of stdin/stdout (as opposed to a unidirectional wiring like in UNIX pipes).

Instead of clumsily running dpipe in a separate window, I encapsulated the necessary steps in a little Go program I call cpu. The reverse sshfs principle looks like this in Go:

sftp := exec.Command("/usr/lib/openssh/sftp-server")
stdin, _ := sftp.StdinPipe()
stdout, _ := sftp.StdoutPipe()
session.Stdin = stdout
session.Stdout = stdin
sftp.Stderr = os.Stderr
session.Stderr = os.Stderr
const (
	host = ""
	src  = "/"
	mnt  = "/mnt"
)
session.Start(fmt.Sprintf("sshfs %s:%s %s -o slave", host, src, mnt))
sftp.Start()

Here’s how the tool looks in action:

binfmt_misc

Now that we have a tool which will make our local file system available on the remote machine, let’s integrate it into our go test invocation.

While we don’t want to modify the go tool, we can easily teach our kernel how to run aarch64 ELF binaries using binfmt_misc.

I modified the existing /var/lib/binfmts/qemu-aarch64’s interpreter field to point to /home/michael/go/bin/porterbox-aarch64, followed by update-binfmts --enable qemu-aarch64 to have the kernel pick up the changes.

porterbox-aarch64 is a wrapper invoking cpu like so:

cpu \
  -host=rpi3 \
  unshare \
    --user \
    --map-root-user \
    --mount-proc \
    --pid \
    --fork \
    /bindmount.sh \
      \$PWD \
      $PWD \
      $@

Because it’s subtle: * \$PWD refers to the directory in which the reverse sshfs was mounted by cpu. * $PWD refers to the working directory in which porterbox-aarch64 was called. * $@ refers to the original command with which porterbox-aarch64 was called.

bindmount

bindmount is a small shell script preparing the bind mounts:

#!/bin/sh

set -e

remote="$1"
shift
wd="$1"
shift

# Ensure the executable (usually within /tmp) is available:
exedir=$(dirname "$1")
mkdir -p "$exedir"
mount --rbind "$remote$exedir" "$exedir"

# Ensure /home is available:
mount --rbind "$remote/home" /home

cd "$wd"
"$@"

demo

This is what all of the above looks like in action:

layers

Putting all of the above puzzle pieces together, we end up with the following picture:

go test
├ compile test program for GOARCH=arm64
└ exec test program (on host)
  └ binfmt_misc
    └ run porterbox-aarch64
      └ cpu -host=rpi3
        ├ reverse sshfs
        └ bindmount.sh
          └ unshare --user
            ├ bind /home, /tmp
            └ run test program (on target)

requirements

On the remote host, the following requirements need to be fulfilled:

  • apt install sshfs, which also activates the FUSE kernel module
  • sysctl -w kernel.unprivileged_userns_clone=1

If the tests require any additional dependencies (the tests in question require Xvfb and i3), those need to be installed as well.

On Debian porter boxes, you can install the dependencies in an schroot session. Note that I wasn’t able to test this yet, as porter boxes lacked all requirements at the time of writing.

Unfortunately, Debian’s Multi-Arch does not yet include binaries. Otherwise, one might use it to help out with the dependencies: one could overlay the local /usr/bin/aarch64-linux-gnu/ on the remote /usr/bin.

conclusion

On first glance, this approach works as expected. Time will tell whether it’s useful in practice or just an interesting one-off exploration.

From a design perspective, there are a few open questions:

  • Making available only /home might not be sufficient. But making available / doesn’t work because sshfs does not support device nodes such as /dev/null.
  • Is there a way to implement this without unprivileged user namespaces (which are disabled by default on Linux)? Essentially, I think I’m asking for Plan 9’s union directories and namespaces.
  • In similar spirit, can binfmt_misc be used per-process?

Regardless, if this setup stands the test of time, I’ll polish and publish the tools.

13. March 2018 08:35:00

25. February 2018

Mero’s Blog

Persistent datastructures with Go

I've recently taken a liking to persistent datastructures. These are datastructures where instead of mutating data in-place, you are creating a new version of the datastructures, that shares most of its state with the previous version. Not all datastructures can be implemented efficiently like this, but those that do get a couple of immediate benefits - keeping old versions around allows you to get cheap snapshotting and copying. It is trivial to pass a copy to a different thread and you don't have to worry about concurrent writes, as neither actually mutates any shared state.

Persistent datastructures are popular in functional programming languages, but I also found the idea a useful tool to model datastructures in Go. Go's interfaces provide a nice way to model them and make them easy to reason about. In this post, I will try to illustrate this with a couple of examples.

There are four key ideas I'd like you to walk away with:

  • Modeling datastructures as persistent (if possible) makes them easier to reason about.
  • When you want to use sum types, try to think of the common properties you are trying to abstract over instead - put those in an interface.
  • Separate out the required from the provided interface. Make the former an interface type, provide the latter as functions or a wrapper.
  • Doing these allows you to add more efficient implementations later, when you discover they are necessary.

Linked lists

This is more of an illustrative example, to demonstrate the techniques, than actually useful. But one of the simplest datastructures existing are linked lists: A list of nodes, where each node has a value and possibly a next node (unless we are at the end of the List). In functional languages, you'd use a sum type to express this:

type List a = Node a (List a) -- either it's a node with a value and the rest of the list
            | End             -- or it's the end of the list

Go infamously does not have sum types, but we can use interfaces to instead. The classical way would be something like

type List interface {
  // We use an unexported marker-method. As nothing outside the current package
  // can implement this unexported method, we get control over all
  // implementations of List and can thus de-facto close the set of possible
  // types.
  list()
}

type Node struct {
  Value int
  Next List
}

func (Node) list() {}

type End struct {}

func (End) list() {}

func Value(l List) (v int, ok bool) {
  switch l := l.(type) {
  case Node:
    return l.Value, true
  case End:
    return 0, false
  default:
    // This should never happen. Someone violated our sum-type assumption.
    panic(fmt.Errorf("unknown type %T", l))
  }
}

This works, but it is not really idiomatic Go code. It is error-prone and easy to misuse, leading to potential panics. But there is a different way to model this using interfaces, closer to how they are intended. Instead of expressing what a list is

A list is either a value and a next element, or the end of the list

we say what we want a list to be able to do:

A list has a current element and may have a tail

type List interface {
  // Value returns the current value of the list
  Value() int
  // Next returns the tail of the list, or nil, if this is the last node.
  Next() List
}

type node struct {
  value int
  next  List
}

func (n node) Value() int {
  return n.value
}

func (n node) Next() List {
  return n.next
}

func New(v int) List {
  return node{v, nil}
}

func Prepend(l List, v int) List {
  return node{v, l}
}

This is a far more elegant abstraction. The empty list is represented by the nil interface. We have only one implementation of that interface, for the nodes. We offer exported functions to create new lists - potentially from existing ones.

Note that the methods actually have node as a receiver, not *node, as we often tend to do with structs. This fact makes this implementation a persistent linked list. None of the methods can modify the list. So after creation, the linked list will stay forever immutable. Even if you type-assert to get to the underlying data, that would only provide you with a copy of the data - the original would stay unmodified. The memory layout, however, is the same - the value gets put on the heap and you are only passing pointers to it around.

The beauty of this way to think about linked lists, is that it allows us to amend it after the fact. For example, say we notice that our program is slow, due to excessive cache-misses (as linked lists are not contiguous in memory). We can easily add a function, that packs a list:

type packed []int

func (p packed) Value() int {
  return p[0]
}

func (p packed) Next() List {
  if len(p) == 0 {
    return nil
  }
  return p[1:]
}

func Pack(l List) List {
  if l == nil {
    return nil
  }
  var p packed
  for ; l != nil; l = l.Next() {
    p = append(p, l.Value())
  }
  return p
}

The cool thing about this is that we can mix and match the two: For example, we could prepend new elements and once the list gets too long, pack it and continue to prepend to the packed list. And since List is an interface, users can implement it themselves and use it with our existing implementation. So, for example, a user could build us a list that calculates fibonacci numbers:

type fib [2]int

func (l fib) Value() int {
  return l[0]
}

func (l fib) Next() List {
  return fib{l[1], l[0]+l[1]}
}

and then use that with functions that take a List. Or they could have a lazily evaluated list:

type lazy struct {
  o sync.Once
  f func() (int, List)
  v int
  next List
}

func (l *lazy) Value() int {
  l.o.Do(func() { l.v, l.next = l.f() })
  return l.v
}

func (l *lazy) Next() List {
  l.o.Do(func() { l.v, l.next = l.f() })
  return l.next
}

Note that in this case the methods need to be on a pointer-receiver. This (technically) leaves the realm of persistent data-structures. While they motivated our interface-based abstraction and helped us come up with a safe implementation, we are not actually bound to them. If we later decide, that for performance reasons we want to add a mutable implementation, we can do so (of course, we still have to make sure that we maintain the safety of the original). And we can intermix the two, allowing us to only apply this optimization to part of our data structure.

I find this a pretty helpful way to think about datastructures.

Associative lists

Building on linked lists, we can build a map based on Association Lists. It's a similar idea as before:

type Map interface {
  Value(k interface{}) interface{}
  Set(k, v interface{}) Map
}

type empty struct{}

func (empty) Value(_ interface{}) interface{} {
  return nil
}

func (empty) Set(k, v interface{}) Map {
  return pair{k, v, empty{}}
}

func Make() Map {
  return empty{}
}

type pair struct {
  k, v interface{}
  parent Map
}

func (p pair) Value(k interface{}) interface{} {
  if k == p.k {
    return p.v
  }
  return p.parent.Value(k)
}

func (p pair) Set(k, v interface{}) Map {
  return pair{k, v, p}
}

This time, we don't represent an empty map as nil, but add a separate implementation of the interface for an empty map. That makes the implementation of Value cleaner, as it doesn't have to check the parent map for nil -- but it requires users to call Make.

There is a problem with our Map, though: We cannot iterate over it. The interface does not give us access to any parent maps. We could use type-assertion, but that would preclude users from implementing their own. What if we added a method to the interface to support iteration?

type Map interface {
  Value(k interface{}) interface{}

  // Iterate calls f with all key-value pairs in the map.
  Iterate(f func(k, v interface{}))
}

func (empty) Iterate(func(k, v interface{})) {
}

func (p pair) Iterate(f func(k, v interface{})) {
  f(p.k, p.v)
  p.parent.Iterate(f)
}

Unfortunately, this still doesn't really work though: If we write multiple times to the same key, Iterate as implemented would call f with all key-value-pairs. This is likely not what we want.

The heart of the issue here, is the difference between the required interface and the provided interface. We can also see that with Set. Both of the implementations of that method look essentially the same and neither actually depends on the used type. We could instead provide Set as a function:

func Set(m Map, k, v interface{}) Map {
  return pair{k,v,m}
}

The lesson is, that some operations need support from the implementation, while other operations can be implemented without it. The provided interface is the set of operations we provide to the user, whereas the required interface is the set of operations that we rely on. We can split the two and get something like this:

// Interface is the set of operations required to implement a persistent map.
type Interface interface {
  Value(k interface{}) interface{}
  Iterate(func(k, v interface{}))
}

type Map struct {
  Interface
}

func (m Map) Iterate(f func(k, v interface{})) {
  seen := make(map[interface{}]bool)
  m.Interface.Iterate(func(k, v interface{}) {
    if !seen[k] {
      f(k, v)
    }
  })
}

func (m Map) Set(k, v interface{}) Map {
  return Map{pair{k, v, m.Interface}}
}

Using this, we could again implement a packed variant of Map:

type packed map[interface{}]interface{}

func (p packed) Value(k interface{}) interface{} {
  return p[k]
}

func (p packed) Iterate(f func(k, v interface{})) {
  for k, v := range p {
    f(k, v)
  }
}

func Pack(m Map) Map {
  p := make(packed)
  m.Iterate(func(k,v interface{}) {
    p[k] = v
  })
  return m
}

Ropes

A Rope is a data structure to store a string in a way that is efficiently editable. They are often used in editors, as it is too slow to copy the complete content on every insert operation. Editors also benefit from implementing them as persistent data structures, as that makes it very easy to implement multi-level undo: Just have a stack (or ringbuffer) of Ropes, representing the states the file was in after each edit. Given that they all share most of their structure, this is very efficient. Implementing ropes is what really bought me into the patterns I'm presenting here. Let's see, how we could represent them.

Rope representing the string "Hello_my_name_is_Simon"

A Rope is a binary tree with strings as leafs. The represented string is what you get when you do a depth-first traversal and concatenate all the leafs. Every node in the tree also has a weight, which corresponds to the length of the string for leafs and the length of the left subtree for inner nodes. This allows easy recursive lookup of the ith character: If i is less than the weight of a node, we look into the left subtree, otherwise into the right. Let's represent this:

type Base interface {
  Index(i int) byte
  Length() int
}

type leaf string

func (l leaf) Index(i int) byte {
  return l[i]
}

func (l leaf) Length() int {
  return len(l)
}

type node struct {
  left, right Base
}

func (n node) Index(i int) byte {
  if w := n.left.Length(); i >= w {
    // The string represented by the right child starts at position w,
    // so we subtract it when recursing to the right
    return n.right.Index(i-w)
  }
  return n.left.Index(i)
}

func (n node) Length() int {
  return n.left.Length() + n.right.Length()
}

type Rope struct {
  Base
}

func New(s string) Rope {
  return Rope{leaf(s)}
}

func (r Rope) Append(r2 Rope) Rope {
  return Rope{node{r.Base, r2.Base}}
}

Note, how we did not actually add a Weight-method to our interface: Given that it's only used by the traversal on inner nodes, we can just directly calculate it from its definition as the length of the left child tree. In practice, we might want to pre-calculate Length on creation, though, as it currently is a costly recursive operation.

The next operation we'd have to support, is splitting a Rope at an index. We can't implement that with our current interface though, we need to add it:

type Base interface {
  Index(i int) byte
  Length() int
  Split(i int) (left, right Base)
}

func (l leaf) Split(i int) (Base, Base) {
  return l[:i], l[i:]
}

func (n node) Split(i int) (Base, Base) {
  if w := n.left.Length(); i >= w {
    left, right := n.right.Split(i-w)
    return node{n.left, left}, right
  }
  left, right := n.left.Split(i)
  return left, node{n.right, right}
}

func (r Rope) Split(i int) (Rope, Rope) {
  // Note that we return the wrapping struct, as opposed to Base.
  // This is so users work with the provided interface, not the required one.
  left, right := r.Split(i)
  return Rope{left}, Rope{right}
}

I think this code is remarkably readable and easy to understand - and that is mostly due to the fact that we are reusing subtrees whenever we can. What's more, given these operations we can implement the remaining three from the wikipedia article easily:

func (r Rope) Insert(r2 Rope, i int) Rope {
  left, right := r.Split(i)
  return left.Append(r2).Append(right)
}

func (r Rope) Delete(i, j int) Rope {
  left, right := r.Split(j)
  left, _ = left.Split(i)
  return left.Append(right)
}

func (r Rope) Slice(i, j int) Rope {
  r, _ = r.Split(j)
  _, r = r.Split(i)
  return r
}

This provides us with a fully functioning Rope implementation. It doesn't support everything we'd need to write an editor, but it's a good start that was quick to write. It is also reasonably simple to extend with more functionality. For example, you could imagine having an implementation that can rebalance itself, when operations start taking too long. Or adding traversal, or random-access unicode support that is still backed by compact UTF-8. And I found it reasonably simple (though it required some usage of unsafe) to write an implementation of Base that used an mmaped file (thus you'd only need to keep the actual edits in RAM, the rest would be read directly from disk with the OS managing caching for you).

Closing remarks

None of these ideas are revolutionary (especially to functional programmers). But I find that considering if a datastructure I need can be implemented as a persistent/immutable one helps me to come up with clear abstractions that work well. And I also believe that Go's interfaces provide a good way to express these abstractions - because they allow you to start with a simple, immutable implementation and then compose it with mutable ones - if and only if there are clear efficiency benefits. Lastly, I think there is an interesting idea here of how to substitute sum-types by interfaces - not in a direct manner, but instead by thinking about the common behavior you want to provide over the sum.

I hope you find that this inspires you to think differently about these problems too.

25. February 2018 17:30:00

29. January 2018

RaumZeitLabor

Coden & Kauen – Eine Neuauflage des Bits & Bites Brunch

Coden-und-Kauen

Wertes RaumZeitLabor, werte Freunde des gepflegten Spätstücks,

wir freuen uns verkünden zu können, dass nach vielen Jahren Pause endlich mal wieder ausgiebig gebruncht wird!

Am Sonntag, den 4. Februar 2018 treffen wir uns ab 11.30 Uhr unter dem Motto “Coden & Kauen” zum gemeinsamen Mampf im RaumZeitLabor.

Egal ob ihr den Tag normalerweise mit einem Nerdtellabrot oder einer Fahrt im Universal Cereal Bus startet – für alle wird etwas beim Buffet zu finden sein!

Nebenbei darf und soll selbstverständlich gecoded und gebastelt werden, was das Zeug hält. Vielleicht findet sich die Zeit, um über ein paar alte und neue Projekte und Ideen vom RZL zu sprechen.

Damit wir wissen, wie viele iBeacons and Eggs wir kaufen sollten, freuen wir uns über eine kurze Rückmeldung per Mail bis zum Freitag, den 2. Februar – Keine Mail, kein Müsli!

Wir bitten um Zahlung einer Brunch-Pauschale von 10€ pro Kopf. Alles was nach dem Einkauf an Geld übrig bleibt, geht wie immer als Spende an den Raum.

Viele Grüße die Brunchorganisatoren

by flederrattie at 29. January 2018 00:00:00

21. January 2018

Mero’s Blog

What even is error handling?

tl;dr: Error handling shouldn't be about how to best propagate an error value, but how to make it destroy it (or make it irrelevant). To encourage myself to do that, I started removing errors from function returns wherever I found it at all feasible

Error handling in Go is a contentious and often criticized issue. There is no shortage on articles criticizing the approach taken, no shortage on articles giving advice on how to deal with it (or defending it) and also no shortage on proposals on how to improve it.

During these discussion, I always feel there is something missing. The proposals for improvement usually deal with syntactical issues, how to avoid boilerplate. Then there is the other school of thought - where it's not about syntax, but about how to best pass errors around. Dave Chaney wrote an often quoted blog post on the subject, where he lists all the ways error information can be mapped into the Go type system, why he considers them flawed and what he suggests instead. This school of thought regularly comes up with helper packages, to make wrapping or annotating errors easier. pkg/errors is very popular (and is grown out of the approach of above blog post) but upspin's incarnation also gathered some attention.

I am dissatisfied with both schools of thought. Overall, neither seems to explicitly address, what to me is the underlying question: What is error handling? In this post, I'm trying to describe how I interpret the term and why, to me, the existing approaches and discussions mostly miss the mark. Note, that I don't claim this understanding to be universal - just how I would put into words my understanding of the topic.


Let's start with a maybe weird question: Why is the entry point into the program func main() and not func main() error? Personally, I start most of my programs writing

func main() {
  if err := run(); err != nil {
    log.Fatal(err)
  }
}

func run() error {
  // …
}

This allows me to use defer, pass on errors and all that good stuff. So, why doesn't the language just do that for me?

We can find part of the answer in this old golang-nuts thread. It is about return codes, instead of an error, but the principle is the same. And the best answer - in my opinion - is this:

I think the returned status is OS-specific, and so Go the language should not define its type (Maybe some OS can only report 8-bit result while some other OS support arbitrary string as program status, there is considerable differences between that; there might even be environment that don't support returning status code or the concept of status code simply doesn't exist)

I imagine some Plan 9 users might be disagree with the signature of os.Exit().

So, in essence: Not all implementations would necessarily be able to assign a reasonable meaning to a return code (or error) from main. For example, an embedded device likely couldn't really do anything with it. It thus seems preferable to not couple the language to this decision which only really makes semantic sense on a limited subset of implementations. Instead, we provide mechanisms in the standard library to exit the program or take any other reasonable action and then let the developer decide, under what circumstances they want to exit the program and with what code. Being coupled to a decision in the standard library is better than being coupled in the language itself. And a developer who targets a platform where an exit code doesn't make sense, can take a different action instead.

Of course, this leaves the programmer with a problem: What to do with errors? We could write it to stderr, but fmt.Fprintf also returns an error, so what to do with that one? Above I used log.Fatal, which does not return an error. What happens if the underlying io.Writer fails to write, though? What does log do with the resulting error? The answer is, of course: It ignores any errors.

The point is, that passing on the error is not a solution. Eventually every program will return to main (or os.Exit or panic) and the buck stops there. It needs to get handled and the signature of main enforces that the only way to do that is via side-effects - and if they fail, you just have to deal with that one too.


Let's continue with a similar question, that has a similar answer, that occasionally comes up: Why doesn't ServeHTTP return an error? Sooner or later, people face the question of what to do with errors in their HTTP Handlers. For example, what if you are writing out a JSON object and Marshal fails? In fact, a lot of HTTP frameworks out there will define their own handler-type, which differs from http.Handler in exactly that way. But if everyone wants to return an error from their handler, why doesn't the interface just add that error return itself? Was that just an oversight?

I'm strongly arguing that no, this was not an oversight, but the correct design decision. Because the HTTP Server package can not handle any errors. An HTTP server is supposed to stay running, every request demands a response. If ServeHTTP would return an error, the server would have to do something with it, but what to do is highly application-specific. You might respond that it should serve a 500 error code, but in 99% of cases, that is the wrong thing to do. Instead you should serve a more specific error code, so the client knows (for example) whether to retry or if the response is cacheable. http.Server could also just ignore the error and instead drop the request on the floor, but that's even worse. Or it could propagate it up the stack. But as we determined, eventually it would have to reach main and the buck stops there. You probably don't want your server to come down, every time a request contains an invalid parameter.

So, given that a) every request needs an answer and b) the right answer is highly application-specific, the translation from errors into status codes has to happen in application code. And just like main enforces you to handle any errors via side-effects by not allowing you to return an error, so does http force you to handle any errors via writing a response by not allowing you to return an error.¹

So, what are you supposed to do, when json.Marshal fails? Well, that depends on our application. Increment a metric. Log the error. panic. Write out a 500. Ignore it and write a 200. Commit to the uncomfortable knowledge, that sometimes, you can't just pass the decision on what to do with an error to someone else.


These two examples distill, I think, pretty well, what I view as error handling: An error is handled, when you destroy the error value. In that parlance, log.Error handles any errors of the underlying writer by not returning them. Every program needs to handle any error in some way, because main can't return anything and the values need to go somewhere. Any HTTP handler needs to actually handle errors, by translating them into HTTP responses.

And in that parlance, packages like pkg/errors have little, really, to do with error handling - instead, they provides you with a strategy for the case where you are not handling your errors. In the same vein, proposals that address the repetitive checking of errors via extra syntax do not really simplify their handling at all - they just move it around a bit. I would term that error propagation, instead - no doubt important, but keep in mind, that an error that was handled, doesn't need to be propagated at all. So to me, a good approach to error handling would be characterized by mostly obviating the need for convenient error propagation mechanisms.

And to me, at least, it seems that we talk too little about how to handle errors, in the end.


Does Go encourage explicit error handling? This is the phrasing very often used to justify the repetitive nature, but I tend to disagree. Compare, for example, Go's approach to checked exceptions in Java: There, errors are propagated via exceptions. Every exception that could be thrown (theoretically) must be annotated in the method signature. Any exception that you handle, has to be mentioned in a try-catch-statement. And the compiler will refuse to compile a program which does not explicitly mention how exceptions are handled. This, to me, seems like the pinnacle of explicit error handling. Rust, too, requires this - it introduces a ? operator to signify propagating an error, but that, still, is an explicit annotation. And apart from that, you can't use the return value of a function that might propagate an error, without explicitly handling that error first.

In Go, on the other hand, it is not only perfectly acceptable to ignore errors when it makes sense (for example, I will always ignore errors created from writing to a *bytes.Buffer), it is actually often the only sensible thing to do. It is fundamentally not only okay, but 99% of times correct to just completely ignore the error returned by fmt.Println. And while it makes sense to check the error returned from json.Marshal in your HTTP handler against *json.MarshalError (to panic/log/complain loudly, because your code is buggy), any other errors should 99% of the time just be ignored. And that's fine.

I believe that to say Go encourages explicit error handling, it would need some mechanism of checked exceptions, Result types, or a requirement to pass an errcheck like analysis in the compiler.

I think it would be closer to say, that Go encourages local error handling. That is, the code that handles an error, is close to the code that produced it. Exceptions encourages the two to be separated: There are usually several or many lines of code in a single try-block, all of which share one catch-block and it is hard to tell which of the lines produced it. And very often, the actual error location is several stack frames deep. You could contrast this with Go, where the error return is immediately obvious from the code and if you have a line of error handling, it is usually immediately attached to the function call that produced it.

However, that still seems to come short, in my view. After all, there is nothing to force you to do that. And in fact, one of the most often cited articles about Go error handling is often interpreted to encourage exactly that. Plus, a lot of people end up writing return err far too often, simply propagating the error to be handled elsewhere. And the proliferation of error-wrapping libraries happens in the same vein: What their proponents phrase as "adding context to the error value", I interpret as "adding back some of the information as a crutch, that you removed when passing the error to non-local handling code". Sadly, far too often, the error then ends up not being handled at all, as everyone just takes advantage of that crutch. This leaves the end-user with an error message that is essentially a poorly formatted, non-contiguous stacktrace.

Personally, I'd characterize Go's approach like this: In Go, error handling is simply first-class code. By forcing you to use exactly the same control-flow mechanisms and treat errors like any other data, Go encourages you to code your error handling. Often that means a bunch of control flow to catch and recover from any errors where they occur. But that's not "clutter", just as it is not "clutter" to write if n < 1 { return 1 } when writing a Fibonacci function (to choose a trivial example). It is just code. And yes, sometimes that code might also store the error away or propagate it out-of-band to reduce repetition where it makes sense - like in above blog post. But focussing on the "happy path" is a bit of a distraction: Your users will definitely be more happy about those parts of the control flow that make the errors disappear or transform them into clean, actionable advise on how to solve the problem.

So, in my reading, the title of the Go blog post puts the emphasis in slightly the wrong place - and often, people take the wrong message from it, in my opinion. Not "errors are values", but "error handling is code".


So, what would be my advise for handling errors? To be honest, I don't know yet - and I'm probably in no place to lecture anyone anyway.

Personally, I've been trying for the last couple of months to take a page out of http.Handlers playbook and try, as much as possible, to completely avoid returning an error. Instead of thinking "I should return an error here, in case I ever do any operation that fails", I instead think "is there any way at all I can get away with not returning an error here?". It doesn't always work and sometimes you do have to pass errors around or wrap them. But I am forcing myself to think very hard about handling my errors and it encourages a programming-style of isolating failing components. The constraint of not being able to return an error tends to make you creative in how to handle it.


[1] You might be tempted to suggest, that you could define an HTTPError, containing the necessary info. Indeed, that's what the official Go blog does, so it can't be bad? And indeed, that is what they do, but note that they do not actually return an error in the end - they return an appError, which contains the necessary information. Exactly because they don't know how to deal with general errors. So they translate any errors into a domain specific type that carries the response. So, that is not the same as returning an error.

I think this particular pattern is fine, though, personally, I don't really see the point. Anything that builds an appError needs to provide the complete response anyway, so you might as well just write it out directly. YMMV.

21. January 2018 23:40:00

15. January 2018

Mero’s Blog

Generating entropy without imports in Go

tl;dr: I come up with a couple of useless, but entertaining ways to generate entropy without relying on any packages.

This post is inspired by a comment on reddit, saying

[…]given the constraints of no imports and the function signature:

func F(map[string]string) map[string]string { ... }

F must use a deterministic algorithm, since it is a deterministic algorithm it can be represented in a finite state machine.

Now, the point of this comment was to talk about how to then compile such a function into a deterministic finite state machine, but it got me thinking about a somewhat different question. If we disallow any imports and assume a standard (gc) Go implementation - how many ways can we find to create a non-deterministic function?

So, the challenge I set to myself was: Write a function func() string that a) can not refer to any qualified identifier (i.e. no imports) and b) is non-deterministic, that is, produces different outputs on each run. To start me off, I did add a couple of helpers, to accumulate entropy, generate random numbers from it and to format strings as hex, without any imports:

type rand uint32

func (r *rand) mix(v uint32) {
    *r = ((*r << 5) + *r) + rand(v)
}

func (r *rand) rand() uint32 {
    mx := rand(int32(*r)>>31) & 0xa8888eef
    *r = *r<<1 ^ mx
    return uint32(*r)
}

func hex(v uint32) string {
    var b []byte
    for v != 0 {
        if x := byte(v & 0xf); x < 10 {
            b = append(b, '0'+x)
        } else {
            b = append(b, 'a'+x-10)
        }
        v >>= 4
    }
    return string(b)
}

Obviously, these could be inlined, but separating them allows us to reuse them for our different functions. Then I set about the actual task at hand.

Method 1: Map iteration

In Go, the iteration order of maps is not specified:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.

But gc, the canonical Go implementation, actively randomizes the map iteration order to prevent programs from depending on it. We can use this, to receive some of entropy from the runtime, by creating a map and iterating over it:

func MapIteration() string {
  var r rand

  m := make(map[uint32]bool)
  for i := uint32(0); i < 100; i++ {
    m[i] = true
  }
  for i := 0; i < 1000; i++ {
    for k := range m {
      r.mix(k)
      break // the rest of the loop is deterministic
    }
  }
  return hex(r.rand())
}

We first create a map with a bunch of keys. We then iterate over it a bunch of times; each map iteration gives us a different start index, which we mix into our entropy pool.

Method 2: Select

Go actually defines a way in which the runtime is giving us access to entropy directly:

If one or more of the communications can proceed, a single one that can proceed is chosen via a uniform pseudo-random selection.

So the spec guarantees that if we have multiple possible communications in a select, the case has to be chosen non-deterministically. We can, again, extract that non-determinism:

func Select() string {
    var r rand

    ch := make(chan bool)
    close(ch)
    for i := 0; i < 1000; i++ {
        select {
        case <-ch:
            r.mix(1)
        case <-ch:
            r.mix(2)
        }
    }
    return hex(r.rand())
}

We create a channel and immediately close it. We then create a select-statement with two cases and depending on which was taken, we mix a different value into our entropy pool. The channel is closed, to guarantee that communication can always proceed. This way, we extract one bit of entropy per iteration.

Note, that there is no racing or concurrency involved here: This is simple, single-threaded Go code. The randomness comes directly from the runtime. Thus, this should work in any compliant Go implementation. The playground, however, is not compliant with the spec in this regard, strictly speaking. It is deliberately deterministic.

Method 3: Race condition

This method exploits the fact, that on a multi-core machine at least, the Go scheduler is non-deterministic. So, if we let two goroutines race to write a value to a channel, we can extract some entropy from which one wins this race:

func RaceCondition() string {
    var r rand

    for i := 0; i < 1000; i++ {
        ch := make(chan uint32, 2)
        start := make(chan bool)
        go func() {
            <-start
            ch <- 1
        }()
        go func() {
            <-start
            ch <- 2
        }()
        close(start)
        r.mix(<-ch)
    }

    return hex(r.rand())
}

The start channel is there to make sure that both goroutines become runnable concurrently. Otherwise, the first goroutine would be relatively likely to write the value before the second is even spawned.

Method 4: Allocation/data races

Another thought I had, was to try to extract some entropy from the allocator or GC. The basic idea is, that the address of an allocated value might be non-deterministic - in particular, if we allocate a lot. We can then try use that as entropy.

However, I could not make this work very well, for the simple reason that Go does not allow you to actually do anything with pointers - except dereferencing and comparing them for equality. So while you might get non-deterministic values, those values can't be used to actually generate random numbers.

I thought I might be able to somehow get a string or integer representation of some pointer without any imports. One way I considered was inducing a runtime-panic and recovering that, in the hope that the error string would contain a stacktrace or offending values. However, none of the error strings created by the runtime actually seem to contain any values that could be used here.

I also tried a workaround to interpret the pointer as an integer, by exploiting race conditions to do unsafe operations:

func DataRace() string {
    var r rand

    var data *uintptr
    var addr *uintptr

    var i, j, k interface{}
    i = (*uintptr)(nil)
    j = &data

    done := false
    go func() {
        for !done {
            k = i
            k = j
        }
    }()
    for {
        if p, ok := k.(*uintptr); ok && p != nil {
            addr = p
            done = true
            break
        }
    }

    data = new(uintptr)
    r.mix(uint32(*addr))
    return hex(r.rand())
}

It turns out, however, that at least this particular instance of a data race has been fixed since Russ Cox wrote that blog post. In Go 1.9, this code just loops endlessly. I tried it in Go 1.5, though, and it works there - but we don't get a whole lot of entropy (addresses are not that random). With other methods, we could re-run the code to collect more entropy, but in this case, I believe the escape analysis gets into our way by stack-allocating the pointer, so it will be the same one on each run.

I like this method, because it uses several obscure steps to work, but on the other hand, it's the least reliable and it requires an old Go version.

Your Methods?

These are all the methods I could think of; but I'm sure I missed a couple. If you can think of any, feel free to let me know on Twitter, reddit or hackernews :) I also posted the code in a gist, so you can download and run it yourself, but keep in mind, that the last method busy-loops in newer Go versions.

15. January 2018 01:04:30

13. January 2018

sECuREs Webseite

Off-site backups with an apu2c4

Background

A short summary of my backup strategy is: I run daily backups to my NAS. In order to recover from risks like my apartment burning down or my belongings being stolen, I like to keep one copy of my data off-site, updated less frequently.

I used to store off-site backups with the “unlimited storage” offerings of various cloud providers.

These offers follow a similar pattern: they are announced, people sign up and use a large amount of storage, the provider realizes they cannot make enough money off of this pricing model, and finally the offer is cancelled.

I went through this two times, and my friend Mark’s similar experience and home-grown solution inspired me to also build my own off-site backup.

Introduction

I figured the office would make a good place for an external hard disk: I’m there every workday, it’s not too far away, and there is good internet connectivity for updating the off-site backup.

Initially, I thought just leaving the external hard disk there and updating it over night by bringing my laptop to the office every couple of weeks would be sufficient.

Now I know that strategy doesn’t work for me: the time would never be good (“maybe I’ll unexpectedly need my laptop tonight!”), I would forget, or I would not be in the mood.

Lesson learnt: backups must not require continuous human involvement.

The rest of this article covers the hardware I decided to use and the software setup.

Hardware

The external hard disk enclosure is a T3US41 Sharkoon Swift Case PRO USB 3.0 for 25 €.

The enclosed disk is a HGST 8TB drive for which I paid 290 € in mid 2017.

For providing internet at our yearly retro computing event, I still had a PC Engines apu2c4 lying around, which I repurposed for my off-site backups. For this year’s retro computing event, I’ll either borrow it (setting it up is quick) or buy another one.

The apu2c4 has two USB 3.0 ports, so I can connect my external hard disk to it without USB being a bottle-neck.

Setup: installation

On the apu2c4, I installed Debian “stretch” 9, the latest Debian stable version at the time of writing. I prepared a USB thumb drive with the netinst image:

% wget https://cdimage.debian.org/debian-cd/current/amd64/iso-cd/debian-9.2.1-amd64-netinst.iso
% cp debian-9.2.1-amd64-netinst.iso /dev/sdb

Then, I…

  • plugged the USB thumb drive into the apu2c4
  • On the serial console, pressed F10 (boot menu), then 1 (boot from USB)
  • In the Debian installer, selected Help, pressed F6 (special boot parameters), entered install console=ttyS0,115200n8
  • installed Debian as usual.
  • Manually ran update-grub, so that GRUB refers to the boot disk by UUID instead of root=/dev/sda1. Especially once the external hard disk is connected, device nodes are unstable.
  • On the serial console, pressed F10 (boot menu), then 4 (setup), then c to move the mSATA SSD to number 1 in boot order
  • Connected the external hard disk

Setup: persistent reverse SSH tunnel

I’m connecting the apu2c4 to a guest network port in our office, to keep it completely separate from our corporate infrastructure. Since we don’t have permanently assigned publically reachable IP addresses on that guest network, I needed to set up a reverse tunnel.

First, I created an SSH private/public keypair using ssh-keygen(1).

Then, I created a user account for the apu2c4 on my NAS (using cloud-config), where the tunnel will be terminated. This account’s SSH usage is restricted to port forwardings only:

users:
  - name: apu2c4
    system: true
    ssh-authorized-keys:
      - "restrict,command=\"/bin/false\",port-forwarding ssh-rsa AAAA…== root@stapelberg-apu2c4"

On the apu2c4, I installed the autossh Debian package (see the autossh(1) manpage for details) and created the systemd unit file /etc/systemd/system/autossh-nas.service with the following content:

[Unit]
Description=autossh reverse tunnel
After=network.target
Wants=network-online.target

[Service]
Restart=always
StartLimitIntervalSec=0
Environment=AUTOSSH_GATETIME=0
ExecStart=/usr/bin/autossh -M 0 -N -o "ServerAliveInterval 60" -o "ServerAliveCountMax 3" -o "ExitOnForwardFailure yes" apu2c4@nas.example.net -R 2200:localhost:22

[Install]
WantedBy=multi-user.target

After enabling and starting the unit using systemctl enable --now autossh-nas, the apu2c4 connected to the NAS and set up a reverse port-forwarding.

On the NAS, I configure SSH like so in my /root/.ssh/config:

Host apu2c4
  Hostname localhost
  Port 2200
  User root
  IdentitiesOnly yes

Finally, I authorized the public key of my NAS to connect to the apu2c4.

Note that this concludes the setup of the apu2c4: the device’s only purpose is to make the external hard disk drive available remotely to my NAS, clean and simple.

Setup: full-disk encryption

I decided to not store the encryption key for the external hard disk on the apu2c4, to have piece of mind in case the hard disk gets misplaced or even stolen. Of course I trust my co-workers, but this is a matter of principle.

Hence, I amended my NAS’s cloud-config setup like so (of course with a stronger key):

write_files:
  - path: /root/apu2c4.lukskey
    permissions: 0600
    owner: root:root
    content: |
    ABCDEFGHIJKL0123456789

…and configured the second key slot of the external hard disk to use this key.

Setup: Backup script

I’m using a script roughly like the following to do the actual backups:

#!/bin/bash
# vi:ts=4:sw=4:et
set -e

/bin/ssh apu2c4 cryptsetup luksOpen --key-file - /dev/disk/by-id/ata-HGST_HDN1234 offline_crypt < /root/apu2c4.lukskey

/bin/ssh apu2c4 mount /dev/mapper/offline_crypt /mnt/offsite

# step 1: update everything but /backups
echo "$(date +'%c') syncing NAS data"

(cd /srv && /usr/bin/rsync --filter 'exclude /backup' -e ssh -ax --relative --numeric-ids ./ apu2c4:/mnt/offsite)

# step 2: copy the latest backup
hosts=$(ls /srv/backup/)
for host in $hosts
do
  latestremote=$(ls /srv/backup/${host}/ | tail -1)
  latestlocal=$(/bin/ssh apu2c4 ls /mnt/offsite/backup/${host} | tail -1)
  if [ "$latestlocal" != "$latestremote" ]
  then
    echo "$(date +'%c') syncing $host (offline: ${latestlocal}, NAS: ${latestremote})"
    /bin/ssh apu2c4 mkdir -p /mnt/offsite/backup/${host}
    (cd /srv && /usr/bin/rsync -e ssh -ax --numeric-ids ./backup/${host}/${latestremote}/ apu2c4:/mnt/offsite/backup/${host}/${latestremote} --link-dest=../${latestlocal})

    # step 3: delete all previous backups
    echo "$(date +'%c') deleting everything but ${latestremote} for host ${host}"
    ssh apu2c4 "find /mnt/offsite/backup/${host} \! \( -path \"/mnt/offsite/backup/${host}/${latestremote}/*\" -or -path \"/mnt/offsite/backup/${host}/${latestremote}\" -or -path \"/mnt/offsite/backup/${host}\" \) -delete"
  fi
done

/bin/ssh apu2c4 umount /mnt/offsite
/bin/ssh apu2c4 cryptsetup luksClose offline_crypt
/bin/ssh apu2c4 hdparm -Y /dev/disk/by-id/ata-HGST_HDN1234

Note that this script is not idempotent, lacking in error handling and won’t be updated. It merely serves as an illustration of how things could work, but specifics depend on your backup.

To run this script weekly, I created the following cloud-config on my NAS:

coreos:
  units:
    - name: sync-offsite.timer
      command: start
      content: |
        [Unit]
        Description=sync backups to off-site storage

        [Timer]
        OnCalendar=Sat 03:00

    - name: sync-offsite.service
      content: |
        [Unit]
        Description=sync backups to off-site storage
        After=docker.service srv.mount
        Requires=docker.service srv.mount

        [Service]
        Type=oneshot

        ExecStart=/root/sync-offsite-backup.sh

Improvement: bandwidth throttling

In case your office (or off-site place) doesn’t have a lot of bandwidth available, consider throttling your backups. Thus far, I haven’t had the need.

Improvement: RTC-based wake-up

I couldn’t figure out whether the apu2c4 supports waking up based on a real-time clock (RTC), and if yes, whether that works across power outages.

If so, one could keep it shut down (or suspended) during the week, and only power it up for the actual backup update. The downside of course is that any access (such as for restoring remotely) require physical presence.

If you know the answer, please send me an email.

Conclusion

The presented solution is easier to integrate than most cloud storage solutions.

Of course my setup is less failure-tolerant than decent cloud storage providers, but given the low probability of a catastrophic event (e.g. apartment burning down), it’s fine to just order a new hard disk or apu2c4 when either of the two fails — for this specific class of backups, that’s an okay trade-off to make.

The upside of my setup is that the running costs are very low: the apu2c4’s few watts of electricity usage are lost in the noise, and syncing a few hundred MB every week is cheap enough these days.

13. January 2018 16:30:00

08. January 2018

Mero’s Blog

Monads are just monoids in the category of endofunctors

tl;dr: I explain the mathematical background of a joke-explanation of monads. Contains lots of math and a hasty introduction to category theory.

There is a running gag in the programming community, that newcomers will often be confused by the concept of monads (which is how sequential computations are modeled in purely functional languages) and getting the explanation "it is simple, really: Monads are just monoids in the category of endofunctors". This is not meant as an actual explanation, but rather to poke a bit of fun at the habit of functional programmers to give quite abstract and theoretical explanations at times, that are not all that helpful.

However, given my background in mathematics, I decided that I wanted to actually approach Haskell from this point of view: I am interested in how it uses math to model programming and also to, after several years of doing mostly engineering focused programming work, flex my math muscles again - as there is quite a bit of interesting math behind these concepts.

The quote is from a pretty popular book about category theory and is, in full:

All told, a monad in \(X\) is just a monoid in the category of endofunctors of \(X\), with product \(\times\) replaced by composition of endofunctors and unit set by the identity endofunctor.

This, of course, is an explanation of the mathematical concept of monads, not meant for programmers. Most explanations of the quote that I found either assumed quite a bit of knowledge in Haskell or took a lot of liberties with the mathematical concepts (and relied a lot on "squinting") or both. This write up is my attempt, to walk through all the concepts needed to explain monads as a mathematical concept and how it relates to Haskell - with as little squinting as possible.

Of course, there are a couple of disclaimers, I should start with:

  1. This is not the best way to understand what monads are, if you are actually interested in using them to program. In fact, it is literally the worst way. I would recommend this intro, which takes a much more practical approach.
  2. This is not the best way to understand how category theory works, if you are actually interested in learning mathematics. In fact, it is literally the worst way. I would recommend the book the quote is from, it's quite good (but assumes a math audience).
  3. I haven't done mathematics in years. I also don't know much Haskell either. So I might be getting a bunch of stuff wrong to varying degrees. I'm sure I will hear all about it :)
  4. Even if I would understand everything correctly, there are still a lot of details, mostly of technical nature, I had to omit, to keep this "short". Not that it is short.

Originally, I intended this to be the ultimate explanation, which would teach Haskellers category theory, mathematicians Haskell and people who know neither both. Unsurprisingly, this is not what this is, at all. It ended up mostly a write up to assure myself that I understood the path myself. If anything, you can treat this as a kind of "reading companion": If you want to understand this topic of the intersection between category theory and functional programming, this post can lead you through the correct terms to search for and give you a good idea what to focus on, in the respective Wikipedia articles.

With all that out of the way, let's begin.

Categories

In mathematics, a category is (roughly) a collection of objects and a collection of arrows between them. There is not a lot of meaning behind these, but it will probably help you to think of objects as sets and arrows as mappings. Every arrow goes from an object (the domain) to an object (the codomain) and we write an arrow as \(f:X\to Y\), where \(f\) is the name of the arrow, \(X\) is the domain and \(Y\) is the codomain. Just like with mappings, there can be many arrows between any given pair of objects - or there may be none.

We do need some restrictions: First, we require a specific identity arrow \(\mathrm{id}:X\to X\) attached to every object \(X\), which has \(X\) as both domain and codomain. Secondly, we require (some) arrows to be composable. That is if we have two arrows \(f:X\to Y,g:Y\to Z\) - so, whenever the domain of \(g\) is the codomain of \(f\) - there should also be a composed arrow¹ \(g\circ f: X\to Z\), that shares the domain with \(f\) and the codomain with \(g\).

Furthermore, the identity arrows must act as a unit for composition, that is, for every arrow \(f\) we require \(\mathrm{id}\circ f = f = f \circ\mathrm{id}\). We also require composition to be associative, that is \((f\circ g)\circ h = f\circ(g\circ h)\) (whenever all compositions exist)².

When we talk about a category, we often draw diagrams like this:

\[ \require{AMScd} \begin{CD} X @>{f}>> Y \\ @V{g}VV @VV{p}V \\ Z @>>{q}> W \\ \end{CD} \]

They show some of the objects and arrows from the category in a compact way. This particular diagram indicates that there are four objects and four arrows involved, with obvious domains and codomains. We only draw a subset of the objects and arrows, that is interesting for the point we are trying to make - for example, above diagram could also contain, of course, identity arrows and compositions \(p\circ f\) and \(q\circ g\)), but we didn't draw them. In a square like this, we can take two paths from \(X\) to \(W\). If these paths are identical (that is, \(p\circ f = q\circ g\), we say that the square commutes. A commutative diagram is a diagram, in which any square commutes, that is, it does not matter which path we take from any object to another. Most of the time, when we draw a diagram, we intend it to be commutative.

So, to summarize, to define a mathematical category, we need to:

  1. Specify what our objects are
  2. Specify what our arrows are, where each arrow starts and ends at a certain object
  3. This collection of arrows need to include an arrow \(\mathrm{id}_X\) for every object \(X\), which starts and ends at \(X\)
  4. And we need to be able to glue together arrows \(f:X\to Y\) and \(g:Y\to Z\) to an arrow \(g\circ f: X\to Z\)

In Haskell, we work on the category Hask, which consists of:

  1. The objects are types: Int is an object, String is an object but also Int | String, String -> Int and any other complicated type you can think of.
  2. The arrows are functions: f :: a -> b is a function taking an a as an input and returning a b and is represented by an arrow f, which has a as its domain and b as its codomain. So, for example, length :: String -> Int would start at the type String and end at Int.
  3. Haskell has a function id :: a -> a which gives us the identity arrow for any type a.
  4. We can compose functions with the operator (.) :: (b -> c) -> (a -> b) -> (a -> c). Note, that this follows the swapped notation of \(\circ\), where the input type of the left function is the output type of the right function.

In general, category theory is concerned with the relationship between categories, whereas in functional programming, we usually only deal with this one category. This turns out to be both a blessing and a curse: It means that our object of study is much simpler, but it also means, that it is sometimes hard to see how to apply the general concepts to the limited environment of functional programming.

Monoids

Understanding categories puts us in the position to understand monoids. A monoid is the generalized structure underlying concepts like the natural numbers: We can add two natural numbers, but we can't (in general) subtract them, as there are no negative numbers. We also have the number \(0\), which, when added to any number, does nothing - it acts as a unit for addition. And we also observe, that addition is associative, that is, when doing a bunch of additions, the order we do them in doesn't matter.

The same properties also apply to other constructs. For example, if we take all maps from a given set to itself, they can be composed and that composition is associative and there is a unit element (the identity map).

This provides us with the following elements to define a monoid:

  1. A set \(M\)
  2. An operation \(\star\colon M\times M\to M\), which "adds" together two elements to make a new one
  3. We need a special unit element \(u\in M\), which acts neutrally when added to any other element, that is \(m\star u=m=u\star m\)
  4. The operation needs to be associative, that is we always require \(m\star(n\star k)=(m\star n)\star k\)

There is another way to frame this, which is closer in line with category theory. If we take \(1 := \{0\}\) to be a 1-element set, we can see that the elements of \(M\) are in a one-to-one correspondence to functions \(1\to M\): Every such function chooses an element of \(M\) (the image of \(0\)) and every element \(m\in M\) fixes such a function, by using \(f(0) := m\). Thus, instead of saying "we need a special element of \(M\)", we can also choose a special function \(\eta: 1\to M\). And instead of talking about an "operation", we can talk about a function \(\mu: M\times M\to M\). Which means, we can define a monoid via a commutative diagram like so:

\[ \begin{CD} 1 \\ @V{\eta}VV \\ M \\ \end{CD} \hspace{1em} \begin{CD} M\times M \\ @V{\mu}VV \\ M \\ \end{CD} \hspace{1em} \begin{CD} M\times 1 @>{\mathrm{id}\times\eta}>> M\times M @<{\eta\times\mathrm{id}}<< 1\times M \\ @V{\pi_1}VV @V{\mu}VV @V{\pi_2}VV \\ M @>{\mathrm{id}}>> M @<{\mathrm{id}}<< M \\ \end{CD} \hspace{1em} \begin{CD} M\times M\times M @>{\mu\times\mathrm{id}}>> M\times M \\ @V{\mathrm{id}\times\mu}VV @V{\mu}VV \\ M\times M @>{\mu}>> M \\ \end{CD} \]

\(\pi_1\) and \(\pi_2\) here, are the functions that project to the first or second component of a cross product respectively (that is \(\pi_1(a, b) := a, \pi_2(a, b) := b\)) and e.g. \(\mathrm{id}\times\eta\) is the map that applies \(\mathrm{id}\) to the first component of a cross-product and \(\eta\) to the second: \(\mathrm{id}\times\eta(m, 0) = (m, \eta(0))\).

There are four sub-diagrams here:

  1. The first diagram just says, that we need an arrow \(\eta:1\to M\). This chooses a unit element for us.
  2. Likewise, the second diagram just says, that we need an arrow \(\mu:M\times M\to M\). This is the operation.
  3. The third diagram tells us that the chosen by \(\eta\) should be a unit for \(\mu\). The commutativity of the left square tells us, that it should be right-neutral, that is \[ \forall m\in M: m = \pi_1(m, 0) = \mu(\mathrm{id}\times\eta(m, 0)) = \mu(m, \eta(0)) \] and the commutativity of the right square tells us, that it should be left-neutral, that is \[ \forall m\in M: m = \pi_2(0,m) = \mu(\eta\times\mathrm{id}(0, m)) = \mu(\eta(0), m) \]

Thus, the first diagram is saying that the element chosen by \(\eta\) should act like a unit. For example, the left square says

\[\pi_1(m,0) = \mu((\mathrm{id}\times\eta)(m,0)) = \mu(m,\eta(0))\]

Now, writing \(\mu(m,n) = m\star n\) and \(\eta(0) = u\), this is equivalent to saying \(m = u\star m\).

The second diagram is saying that \(\mu\) should be associative: The top arrow combines the first two elements, the left arrow combines the second two. The right and bottom arrows then combine the result with the remaining element respectively, so commutativity of that square means the familiar \(m\star (n\star k) = (m\star n)\star k\).

Haskell has the concept of a monoid too. While it's not really relevant to the discussion, it might be enlightening to see, how it's modeled. A monoid in Haskell is a type-class with two (required) methods:

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a

Now, this gives us the operation (mappend) and the unit (a), but where are the requirements of associativity and the unit acting neutrally? The Haskell type system is unable to codify these requirements, so they are instead given as a "law", that is, any implementation of a monoid is supposed to have these properties, to be manually checked by the programmer:

  • mappend mempty x = x (the unit is left-neutral)
  • mappend x mempty = x (the unit is right-neutral)
  • mappend x (mappend y z) = mappend (mappend x y) z (the operation is associative)
Functors

I mentioned that category theory investigates the relationship between categories - but so far, everything we've seen only happens inside a single category. Functors are, how we relate categories to each other. Given two categories \(\mathcal{B}\) and \(\mathcal{C}\), a functor \(F:\mathcal{B}\to \mathcal{C}\) assigns to every object \(X\) of \(\mathcal{B}\), an object \(F(X)\) of \(\mathcal{C}\). It also assigns to every arrow \(f:X\to Y\) in \(\mathcal{B}\) a corresponding arrow \(F(f): F(X)\to F(Y)\) in \(\mathcal{C}\)³. So, a functor transfers arrows from one category to another, preserving domain and codomain. To actually preserve the structure, we also need it to preserve the extra requirements of a category, identities and composition. So we need, in total:

  1. An object map, \(F:O_\mathcal{B} \to O_\mathcal{C}\)
  2. An arrow map, \(F:A_\mathcal{B}\to A_\mathcal{C}\), which preserves start and end object, that is the image of an arrow \(X\to Y\) starts at \(F(X)\) and ends at \(F(Y)\)
  3. The arrow map has to preserve identities, that is \(F(\mathrm{id}_X) = \mathrm{id}_{F(X)}\)
  4. The arrow map has to preserve composition, that is \(F(g\circ f) = F(g)\circ F(f)\).

A trivial example of a functor is the identity functor (which we will call \(I\)), which assigns each object to itself and each arrow to itself - that is, it doesn't change the category at all.

A simple example is the construction of the free monoid, which maps from the category of sets to the category of monoids. The Free monoid \(S^*\) on a set \(S\) is the set of all finite length strings of elements of \(S\), with concatenation as the operation and the empty string as the unit. Our object map then assigns to each set \(S\) its free monoid \(S^*\). And our arrow map assigns to each function \(f:S\to T\) the function \(f^*:S^*\to T^*\), that applies \(f\) to each element of the input string.

There is an interesting side note here: Mathematicians love to abstract. Categories arose from the observation, that in many branches of mathematics we are researching some class of objects with some associated structure and those maps between them, that preserve this structure. It turns out that category theory is a branch of mathematics that is researching the objects of categories, with some associated structure (identity arrows and composition) and maps (functors) between them, that preserve that structure. So it seems obvious that we should be able to view categories as objects of a category, with functors as arrows. Functors can be composed (in the obvious way) and every category has an identity functor, that just maps every object and arrow to itself.

Now, in Haskell, Functors are again a type class:

class Functor f where
  fmap :: (a -> b) -> (f a -> f b)

This looks like our arrow map: It assigns to each function g :: a -> b a function fmap g :: f a -> f b. The object map is implicit: When we write f a, we are referring to a new type, that depends on a - so we "map" a to f a .

Again, there are additional requirements the type system of Haskell can not capture. So we provide them as laws the programmer has to check manually:

  • fmap id == id (preserves identities)
  • fmap (f . g) == fmap f . fmap g (preserves composition)

There is one thing to note here: As mentioned, in Haskell we only really deal with one category, the category of types. That means that a functor always maps from the category of types to itself. In mathematics, we call such a functor, that maps a category to itself, an endofunctor. So we can tell, that in Haskell, every functor is automatically an endofunctor.

Natural transformations

We now understand categories and we understand functors. We also understand, that we can look at something like the category of categories. But the definition of a monad given to us talks about the category of endofunctors. So we seem to have to step up yet another level in the abstraction hierarchy and somehow build this category. As objects, we'd like to have endofunctors - and arrows will be natural transformations, which take one functor to another, while preserving its internal structure (the mapping of arrows). If that sounds complicated and abstract, that's because it is.

We need two functors \(F,G:\mathcal{B}\to \mathcal{C}\) of the same "kind" (that is, mapping to and from the same categories). A natural transformation \(\eta:F\dot\to G\) assigns an arrow \(\eta_X: F(X)\to G(X)\) (called a component of \(\eta\)) to every object in \(\mathcal{B}\). So a component \(\eta_X\) describes, how we can translate the action of \(F\) on \(X\) into the action of \(G\) on \(X\) - i.e. how to translate their object maps. We also have to talk about the translation of the arrow maps. For that, we observe that for any arrow \(f:X\to Y\) in \(\mathcal{B}\), we get four new arrows in \(\mathcal{C}\):

\[ \begin{CD} X \\ @V{f}VV \\ Y \\ \end{CD} \hspace{1em} \begin{CD} F(X) @>{\eta_X}>> G(X) \\ @V{F(f)}VV @VV{G(f)}V \\ F(Y) @>>{\eta_Y}> G(Y) \\ \end{CD} \]

For a natural transformation, we require the resulting square to commute.

So, to recap: To create a natural transformation, we need

  1. Two functors \(F,G:\mathcal{B}\to\mathcal{C}\)
  2. For every object \(X\) in \(\mathcal{B}\), an arrow \(\eta_X: F(X)\to G(X)\)
  3. The components need to be compatible with the arrow maps of the functors: \(\eta_Y\circ F(f) = G(f)\circ \eta_X\).

In Haskell, we can define a natural transformation like so:

class (Functor f, Functor g) => Transformation f g where
    eta :: f a -> g a

f and g are functors and a natural transformation from f to g provides a map f a -> g a for every type a. Again, the requirement of compatibility with the actions of the functors is not expressible as a type signature, but we can require it as a law:

  • eta (fmap fn a) = fmap fn (eta a)
Monads

This, finally, puts us in the position to define monads. Let's look at our quote above:

All told, a monad in \(X\) is just a monoid in the category of endofunctors of \(X\), with product \(\times\) replaced by composition of endofunctors and unit set by the identity endofunctor.

It should be clear, how we can compose endofunctors. But it is important, that this is a different view of these things than if we'd look at the category of categories - there, objects are categories and functors are arrows, while here, objects are functors and arrows are natural transformations. That shows, how composition of functors can take the role of the cross-product of sets: In a set-category, the cross product makes a new set out of two other set. In the category of endofunctors, composition makes a new endofunctor out of two other endofunctors.

When we defined monoids diagrammatically, we also needed a cross product of mappings, that is, given a map \(f:X_1\to Y_1\) and a map \(g:X_2\to Y_2\), we needed the map \(f\times g: X_1\times X_2\to Y_1\times Y_2\), which operated on the individual constituents. If we want to replace the cross product with composition of endofunctors, we need an equivalent for natural transformations. That is, given two natural transformations \(\eta:F\to G\) and \(\epsilon:J\to K\), we want to construct a natural transformation \(\eta\epsilon:J\circ F\to K\circ G\). This diagram illustrates how we get there (working on components):

\[ \begin{CD} F(X) @>{\eta_X}>> G(X) @. \\ @V{J}VV @VV{J}V @. \\ J(F(X)) @>{J(\eta_X)}>> J(G(X)) @>{\epsilon_{G(X)}}>> K(G(X)) \\ \end{CD} \]

As we can see, we can build an arrow \(\epsilon_{G(X)}\circ J(\eta_X): J(F(X)) \to K(G(X))\), which we can use as the components of our natural transformation \(\eta\epsilon:J\circ F\to K\circ G\). This construction is called the horizontal composition of natural transformations. We should verify that this is indeed a natural transformation - for now, let's just accept that it follows from the naturality of \(\eta\) and \(\epsilon\).

Lastly, there is an obvious natural transformation taking a functor to itself; each component being just the identity arrow. We call that natural transformation \(\iota\), staying with the convention of using Greek letters for natural transformations.

With this, we can redraw the diagram we used to define monoids above, the replacements indicated by the quotes:

\[ \begin{CD} I \\ @V{\eta}VV \\ M \\ \end{CD} \hspace{1em} \begin{CD} M\circ M \\ @V{\mu}VV \\ M \\ \end{CD} \hspace{1em} \begin{CD} M\circ I @>{\iota\ \eta}>> M\circ M @<{\eta\ \iota}<< I\circ M \\ @VVV @V{\mu}VV @VVV \\ M @>{\iota}>> M @<{\iota}<< M \\ \end{CD} \hspace{1em} \begin{CD} M\circ M\circ M @>{\mu\ \iota}>> M\circ M \\ @V{\iota\ \mu}VV @V{\mu}VV \\ M\circ M @>{\mu}>> M \\ \end{CD} \]

The vertical arrows in the middle diagram now simply apply the composition of functors, using that the identity functor is a unit.

These diagrams encode these conditions on our natural transformations:

  • \(\mu\circ\eta\iota = \mu = \iota\eta\circ\mu\), that is \(\eta\) serves as a unit
  • \(\mu\circ\mu\iota = \mu\circ\iota\mu\), that is \(\mu\) is associative

To recap, a monad, in category theory, is

  • An endofunctor \(M\)
  • A natural transformation \(\eta: I\to M\), which serves as an identity for horizontal composition.
  • A natural transformation \(\mu: M\circ M\to M\), which is associative in respect to horizontal composition.

Now, let's see, how this maps to Haskell monads.

First, what is the identity functor in Haskell? As we pointed out above, the object function of functors is implicit, when we write f a instead of a. As such, the identity functor is simply a - i.e. we map any type to itself. fmap of that functor would thus also just be the identity fmap :: (a -> a) -> (a -> a).

So, what would our natural transformation \(\eta\) look like? As we said, a natural transformation between two functors is just a map f a -> g a. So (if we call our endofunctor m) the identity transformation of our monoid is eta :: a -> m a mapping the identity functor to m. We also need our monoidal operation, which should map m applied twice to m: mu :: m (m a) -> m a.

Now, Haskellers write return instead of eta and write join instead of mu, giving us the type class

class (Functor m) => Monad where
  return :: a -> m a
  join :: m (m a) -> m a

As a last note, it is worth pointing out that you usually won't implement join, but instead a different function, called "monadic bind":

(>>=) :: m a -> (a -> m b) -> m b

The reason is, that this more closely maps to what monads are actually used for in functional programming. But we can move between join and >>= via

(>>=) :: m a -> (a -> m b) -> m b
v >>= f = join ((fmap f) v)

join :: m (m a) -> m a
join v = v >>= id
Conclusion

This certainly was a bit of a long ride. It took me much longer than anticipated both to understand all the steps necessary and to write them down. I hope you found it helpful and I hope I didn't make too many, too glaring mistakes. If so (either), feel free to let me know on Twitter, reddit or Hacker News - but please remember to be kind :)

I want to thank Tim Adler and mxf+ for proof-reading this absurdly long post and for making many helpful suggestions for improvements


[1] It is often confusing to people, that the way the arrows point in the notation and the order they are written seems to contradict each other: When writing \(f:X\to Y\) and \(g:Y\to Z\) you might reasonably expect their composite to work like \(f\circ g: X\to Z\), that is, you glue together the arrows in the order you are writing them.

The fact that we are not doing that is a completely justified criticism, that is due to a historical accident - we write function application from right to left, that is we write \(f(x)\), for applying \(f\) to \(x\). Accordingly, we write \(g(f(x))\), when applying \(g\) to the result of applying \(f\) to \(x\). And we chose to have the composite-notation be consistent with that, instead of the arrow-notation.

I chose to just eat the unfortunate confusion, as it turns out Haskell is doing exactly the same thing, so swapping things around would just increase the confusion.

Sorry.

[2] Keep in mind that this is a different notion from the ones for monoids, which we come to a bit later: While the formulas seem the same and the identities look like a unit, the difference is that only certain arrows can be composed, not all. And that there are many identity arrows, not just one. However, if we would have only one object, it would have to be the domain and codomain of every arrow and there would be exactly one identity arrow. In that case, the notions would be the same and indeed, "a category with exactly one object" is yet another way to define monoids.

[3] It is customary, to use the same name for the object and arrow map, even though that may seem confusing. A slight justification of that would be, that the object map is already given by the arrow map anyway: If \(F\) is the arrow map, we can define the object map as \(X\mapsto \mathrm{dom}(F(\mathrm{id}_X))\). So, given that they are always occurring together and you can make one from the other, we tend to just drop the distinction and save some symbols.

What was that? Oh, you thought Mathematicians where precise? Ha!

[4] It is important to note, that this is not really a function. Functions operate on values of a given type. But here, we are operating on types and Haskell has no concept of a "type of types" built in that a function could operate on. There are constructs operating on types to construct new types, like data, type, newtype or even deriving. But they are special syntactical constructs that exist outside of the realm of functions.

This is one of the things that was tripping me up for a while: I was trying to figure out, how I would map types to other types in Haskell or even talk about the object map. But the most useful answer is "you don't".

[5] An important note here, is that the \(\eta_X\) are arrows. Where the object map of a functor is just a general association which could look anything we like, the components of a natural transformation need to preserve the internal structure of the category we are working in.

[6] You will often see these conditions written differently, namely written e.g. \(\mu M\) instead of \(\mu\iota\). You can treat that as a notational shorthand, it really means the same thing.

[7] There is a technicality here, that Haskell also has an intermediate between functor and monad called "applicative". As I understand it, this does not have a clear category theoretical analogue. I'm not sure why it exits, but I believe it has been added into the hierarchy after the fact.

08. January 2018 00:30:00

02. January 2018

Mero’s Blog

My case for veganism

I'm going to try to make an argument for being vegan, but, to be clear, it is not very likely to convince you to change your eating habits. It is not designed to - it is only supposed to change the way you think about it. I mention all of that, so you are aware that I don't care what your conclusions are here. If you are reading this, you should do so out of a genuine interest of my motives and for the purpose of self-reflection - not to pick a fight with that vegan dude and really show him he's wrong. I will not debate the content of this article with you. So, with that out of the way, here is a thought experiment:

Say, we would live in a Star Trek like post-scarcity society. Energy is all but abundant and we figured out replicator-technology, that can instantly create anything we like out of it. You get offer the choice between two meals, one is a delicious steak dinner (or whatever), made in a traditional manner. The second is the same thing, but from a replicator. Both are indistinguishable, they taste the same, they have the same nutritional and chemical composition, they cost the same. They only differ in how they're made.

You might be trying to rules-lawyer this. You might be trying to make up an argument, for why the replicator-steak would have to be worse. Or that the cow would already be dead, so it wouldn't matter. But that is obviously not the point of this thought experiment (and remember, you don't have to convince anyone of being right, here). The point is, that I strongly believe that the vast majority of people would agree, that all things being equal, choosing the meal that no animal suffered for is the correct choice. And if you truly believe that it isn't, if you can honestly say to yourself that it doesn't matter: You won't gain anything from the rest of this article. You are relieved and might now just as well stop reading.

The point I am trying to make, is that you probably already know all the reasons you should be vegan. It's very likely that you already have an intuitive understanding of all the reasons in the "pro veganism" column of your pro/contra list. And it really shouldn't be necessary to convince you it's a good idea, in general.

Why then, do so few people actually choose to be vegan, if they are fully aware of all the reasons to do so? The obvious answer is: Because not all things are being equal. There is a "contra veganism" column and it's filled with many good reasons not to. What reasons those are, is deeply individual. It might be due to health. Due to an appeal to nature. Convenience. Money. Availability. Taste. Or maybe just priorities: Other things seem more important and deserving of your energy. And that's okay. We all have to make hundreds of decisions every day and weigh these kinds of questions. And sometimes we do things that we shouldn't and we usually have good reasons to. And sometimes we compromise and don't go all the way, but just do the best we feel able to and that's fine too. Nobody has to be perfect all the time.

The reason, I'm writing this article anyway, is that there is a fundamental difference between the two questions "Why are you vegan?" and "Why are you not not vegan?". When you ask me why I am vegan, you are making the conversation inherently about my values and you will usually end up attacking them - not because you disagree with them (you likely are not), but just because that's the natural progression of this question. And to be absolutely clear: I don't owe you a justification for my value system. I'm sorry if that sounds harsh, but the topic is mostly really annoying to me (as hard as that may be to believe at this point).

A more sensible question, though, is to ask how to best mitigate the contra-column. If we agree that, fundamentally, the points in the pro-column are valid and shared reasons, we can proceed into the much more productive conversation about how much weight the downsides really have and how you might be able to reduce at least some of their impact. And, again to be clear: The outcome of that might very well be, that your reasons are completely valid, rational and that, applied to your personal situation, veganism wouldn't be a good choice. (And to be also clear: I might not be in the mood to have this conversation either. But it's much preferable).

So, what I wish people to take away from this is

  1. Stop asking why you should be vegan (or why I am), you more than likely already know. If you are really interested in making an informed choice, bring up your concerns instead, but also accept if I don't want to talk about them at that particular time - it's a lot of emotional labor, to give the same explanations repeatedly. It might not seem like a big deal to me, to ask these questions, but I've repeated most of my answers literally hundreds of times at this point and might prefer to just enjoy my food.
  2. Stop treating veganism as a preference and start treating it as a moral choice. There is a qualitative difference between someone who does not like Italian food and a vegan. This is interesting when choosing what or where to eat as a group: This is hard enough as it is and I at least usually try very hard to accommodate everyone and not be a burden. And I absolutely do not expect to be treated like I'm better for that. But if it actually would come down to a choice between a vegetarian restaurant or a steakhouse, just because you really like meat: Yes, I do absolutely expect us to avoid the steakhouse. (To be clear: In my experience, it rarely actually comes down to only those two choices. And there are good reasons to avoid vegetarian restaurants that are not based on preference which should be given ample weight too - e.g. someone I know has Coeliac disease, fructose intolerance and lactose intolerance and tends to have a very hard time eating non-meat things. In my experience, though, people who have needs and not just preferences tend to ironically be more open to compromise anyway, so it is less often a problem with them).
  3. Maybe think about your reasons for not being vegan and evaluate them seriously. To be clear, this is a stretch-goal and not the actual point of this article.

And if you want to, you can watch someone who does eat meat say essentially the same things here:

Thanks for reading, don't @ me. ;)


Reasons I'm not not vegan

Now, the main point of this post is dedicated to the general question of "how I think about the topic and how I believe you should think about it too". But I also want it to serve as a reference of my personal, specific thoughts driving my decision - so if you don't know me well or are not interested in my personal reasons, this would be a good place to close the tab and do something else.

I'm still writing this, because I hope this can be the last thing I ever have to write about this (yeah, lol). Because again, I don't actually like discussing it, as unbelievable as that may seem. So here is, as a reference, why I am vegan (and I might add to/change this list over time, when my viewpoints evolve). Why, after ten-ish years of thinking "I should be vegan, but…", I decided to make the switch - or at least give it a serious try. So, this is a list of reasons I gave to myself to justify not going vegan and why they stopped being convincing to me. Your mileage may vary.

Meat/Cheese/Eggs/Bailey's is awesome and I can't imagine giving it up.

For most of my life I didn't think about vegetarianism or veganism at all. Eating meat was the default, so that's what I did. When I did start to think about it, I convinced myself that I couldn't give up meat, because most of my favorite foods where meat-based. However, a lot of people in my peer-group around that time (university) where vegetarian or vegan, so I naturally got into contact with a lot of good food that wasn't naturally meat-based. So I started eating less and less meat - and the less meat I ate, the more I realized I didn't really miss it that much, given how much good alternatives there are. Eventually I decided to become a "flexitarian", which very quickly (in ~1-2 months) became "vegetarian", when I realized that it didn't actually bother me to not eat meat at all - and making that commitment meant less decisions, so it made things easier. With Cheese/Eggs/Bailey's, I basically went through exactly the same transition, six or seven years later: "I can't imagine giving them up" - "Actually, there are really good alternatives" - "Let's just try reducing it and see how far I get" - "Meh, might as well just commit completely".

So, to me, giving up animal products just turned out much easier, than expected, when I actually tried. And I'm not saying I don't miss them, every once in a while, I will still look longingly at a steak or think fondly of my scrambled eggs. But for the most part, the alternatives are just as great (or at times better), so it isn't as big a sacrifice as expected.

Being vegetarian/vegan is unhealthy.

There is a bunch of research about this and for a while (especially before actually looking into the details) the health implications of veganism (vegetarianism not so much) did concern me. But, it turns out, this topic is pretty complicated. Nutrition research is very hard - and that manifests in the fact that for most of it, the statistical significance is usually low and the effect sizes usually small. Now, I'm not denying, that there are health downsides to a vegan diet. But even with the general mess that nutritional research is, it doesn't seem very controversial that if you are concerned for your health, there are much more important factors to consider. If weighed against the health benefits of sleeping more, doing more sports, not sitting all day, stop recreational drug use, taking extensive vacations… (neither of which I seem to be willing to do, even though they would be easy enough), the relatively minor health effects of eating animal products (contrasted with a somewhat balanced vegan diet plus supplementation) just did not seem to be a relevant driving force for that decision and more of a rationalization.

That being said, from what I can gather so far, there is a general consensus that if a) you pay attention to having a somewhat balanced diet and b) are willing to supplement the nutrients you can't actually get, the health impact of veganism is pretty low, if any. Personally, I am supplementing Vitamins B12 and D right now, which has very low quality of life impact - so I don't consider that a significant downside. I also pay a little bit more attention to what I'm eating, which I consider a good thing.

If it turns out that I can not sustain a vegan diet, I will reconsider it, but for now, I don't see any realistic danger of that happening.

It is cumbersome to know whether or not something is vegan.

This is mostly true. As a vegetarian, this mostly revolved around looking for gelatin in the ingredients of sweets and asking in a restaurant whether "Lasagna" is made with meat or not. Being a vegan does involve a lot of scanning ingredients-lists of basically every product I buy. Though I'm positively surprised how many vendors are recently starting to choose to get their products certified - and not only brands you would expect to focus on that, but also, increasingly, all kinds of mainstream products.

That being said, there is an availability issue (especially around "may contain traces of…", which is basically saying "if you are allergic, we can't rule out cross-contamination of other things from the same factory"). I tend to be pragmatic about this: If I have the choice, I will buy the certifiably vegan option, otherwise I'm also fine with traces of animal products, personally. If I don't know, I will go with my best guess and how I feel in the moment.

This is definitely the most true and heavy argument still on the contra-side for me, but being kind of pragmatic about it helps alleviate most of the pain.

It's hypocritical to draw the line at X and not at Y.

You can always be more rigorous and there are a lot of line-drawing questions that come up when thinking about vegetarianism/veganism. For the record, a lot of that is just plain nonsense, but there are some legitimate questions to be asked around whether or not insects count, for example, or certain shellfish, whether you would eat meat if it would be thrown away otherwise or would eat an egg, if the Hen laying it was living a happy, free life. In the end, the vast majority of things you can eat will involve some harm to the environment or animals and you won't always know, so where do you draw the line?

Personally, I decided that definite harm is worse than potential harm and more harm is worse than less harm. "It is hypocritical to not eat meat/cheese/eggs but still kill a wasp entering your apartment" is about as convincing an argument to me as "it is hypocritical to eat meat/cheese/eggs but not also eat dogs/jellyfish/human". The world isn't black-and-white and it's fine to choose a gray spot in the middle that makes you comfortable.

Eating out becomes a PITA.

Yes. Going out and eating in a group is a PITA. Honestly, there are no two ways about it. I do have to actively make sure that a chosen food place has options for me and more often than not that does involve making special requests and/or making do with less great meals.

In general, this still works reasonably well. The cafeteria at work has great vegan options most of the time, Zurich has an amazing choice of great restaurants for vegans to offer, most other restaurants can accommodate too and even if not, I'm fine just eating a little thing and then later eat some more at home.

The main problem is working around the social issues associated with it - dealing with people who are unwilling to be accommodating, having to justify/discuss my choice or just exposing something about my person I might prefer to keep private. Basically, I wrote a whole thing about this.

But this is simply one of those downsides I chose to accept. Nobody said going vegan wouldn't come with sacrifices.

Being vegan is expensive

I am not sure this is true in general. I am relatively sure, that being vegetarian at least actually ended up saving me money as a student. But I can't be completely certain, as the change also came with other changes in circumstances. My vegan diet is probably more expensive than my vegetarian one, mainly because it includes a lot more processed substitute products ("faux meat" and various plant milks, which are at least in Switzerland still significantly more expensive than the cow-based variants), but again, I didn't actually run any numbers.

I'm pretty sure it's possible to have an affordable vegan diet, especially if limiting processed substitute products and not eating out so often. Luckily, this isn't really a concern for me, right now, though. Food and Groceries is a relatively small proportion of my monthly expenses and as such, the impact this has on me is pretty limited either way.

I convinced myself, that if I can afford spending money on all kinds of luxury items and electronic gadgets, I can probably afford spending a little more on food.

02. January 2018 00:23:00

11. December 2017

sECuREs Webseite

Dell 8K4K monitor (Dell UP3218K)

Background

Ever since I first used a MacBook Pro with Retina display back in 2013, I’ve been madly in love with hi-DPI displays. I had seen the device before, and marvelled at brilliant font quality with which scientific papers would be rendered. But it wasn’t until I had a chance to use the device for a few hours to make i3 compatible with hi-DPI displays that I realized what a difference it makes in the day-to-day life.

Note that when I say “hi-DPI display”, I mean displays with an integer multiple of 96 dpi, for example displays with 192 dpi or 288 dpi. I explain this because some people use the same term to mean “anything more than 96 dpi”.

In other words, some people are looking for many pixels (e.g. running a 32 inch display with 3840x2160 pixels, i.e. 137 dpi, with 100% scaling), whereas I desire crisp/sharp text (i.e. 200% scaling).

Hence, in 2014, I bought the Dell UP2414Q with 3840x2160 on 24" (185 dpi), which was one of the first non-Apple devices to offer a dpi that Apple would market as “Retina”.

After getting the Dell UP2414Q, I replaced all displays in my life with hi-DPI displays one by one. I upgraded my phone, my personal laptop, my work laptop and my monitor at work.

Dell UP3218K

In January 2017, Dell introduced the Dell Ultrasharp UP3218K monitor at the Consumer Electronics Show (CES). It is the world’s first available 8K monitor, meaning it has a resolution of 7680x4320 pixels at a refresh rate of 60 Hz. The display’s dimensions are 698.1mm by 392.7mm (80cm diagonal, or 31.5 inches), meaning the display shows 280 dpi.

While the display was available in the US for quite some time, it took until October 2017 until it became available in Switzerland.

Compatibility

The UP3218K requires connecting two separate DisplayPort 1.4 cables in order to reach the native resolution and refresh rate. When connecting only one cable, you will be limited to a refresh rate of 30 Hz, which is a very noticeable annoyance on any display: you can literally see your mouse cursor lag behind. Ugh.

Note that this mode of connection does not use Multi-Stream Transport (MST), which was a trick that first-generation 4K displays used. Instead, it uses the regular Single-Stream Transport (SST), but two cables.

As of November 2017, only latest-generation graphics cards support DisplayPort 1.4 at all, with e.g. the nVidia GTX 1060 being marketed as “DisplayPort 1.2 Certified, DisplayPort 1.3/1.4 Ready”.

AMD Radeon Pro WX7100

Hence, I thought I would play it safe and buy a graphics card which is explicitly described as compatible with the UP3218K: I ordered an AMD Radeon Pro WX7100.

Unfortunately, I have to report that the WX7100 is only able to drive the monitor at native resolution when using Windows. On Linux, I was limited to 1920x1080 at 60Hz (!) when using the Open Source amdgpu driver. With the Closed Source amdgpu-pro driver, I reached 3840x2160 at 60Hz, which is still not the native resolution. Also, the amdgpu-pro driver is a hassle to install: it requires an older kernel and isn’t packaged well in Debian.

nVidia GeForce GTX 1060

I returned the WX7100 in exchange for the cheapest and most quiet GeForce 10 series card with 2 DisplayPort outputs I could find. My choice was the MSI GeForce GTX 1060 GAMING X 6G (MSI V328-001R). The card seems like overkill, given that I don’t intend to play games on this machine, but lower-end cards all come with at most one DisplayPort output.

Regardless, I am happy with the card. It indeed is silent, and with the Closed Source driver, it powers the UP3218K without any trouble. Notably, it supports RandR 1.5, which I’ll talk about a bit more later.

Compatibility Matrix

Operating System Graphics Card Driver Resolution
Windows Radeon WX7100 yes 7680x4320 @ 60 Hz
Windows GeForce 1060 yes 7680x4320 @ 60 Hz
Linux Radeon WX7100 amdgpu 1920x1080 @ 60 Hz
Linux Radeon WX7100 pro 3840x2160 @ 60 Hz
Linux GeForce 1060 nVidia 7680x4320 @ 60 Hz

Recommendation

If you want to play it safe, buy an nVidia card of the GeForce 10 series. Verify that it says “DisplayPort 1.4 Ready”, and that it comes with two DisplayPort outputs.

I read about improvements of the amdgpu driver for the upcoming Linux 4.15, but I don’t know whether that will help with the problems at hand.

Impressions

The unboxing experience is well-designed, and all components make a good impression. All cables which you will need (two DisplayPort cables, a power cable, a USB cable) are included and seem to be of high quality.

The display has a thin bezel, much thinner than my other monitors ViewSonic VX2475Smhl-4K or Dell UP2414Q.

The power LED is white and not too bright. The on-screen menu reacts quickly and is reasonably intuitive.

The built-in USB hub works flawlessy, even with devices which don’t work on my standalone USB3 hub (for reasons which I have yet to find out).

Display Quality

The display quality of the screen is stunningly good.

It was only when I configured 300% scaling that I realized why some Chromebooks had a distinctly different look and feel from other computers I had used: I always assumed they differed in font rendering somehow, but the actual difference is just the screen DPI: fonts look distinctly better with 288 dpi than with 192 dpi, which of course looks better than 96 dpi.

Some people might wonder whether an 8K display is any better than a 4K display, and I now can answer that question with a decisive “yes, one can easily see the difference”. I’m not sure if the difference between a 288 dpi and a 384 dpi display would be visible, but we’ll see when we get there :-).

Glossy

What I didn’t expect is that the UP3218K is a glossy display, as opposed to a matte display. Depending on the brightness and colors, you might see reflections. With my preferred brightness of 50%, I can clearly see reflections when displaying darker colors, e.g. on a black terminal emulator background, or even in my grey Emacs theme.

While one can mentally ignore the reflections after a little while, I still consider the glossyness a mild annoyance. I hope as 8K displays become more prevalent, display vendors will offer matte 8K displays as well.

Scaling

I found it interesting that the display works well in both 200% scaling and 300% scaling.

When running the display at 200% scaling, you get 3840x2160 (4K resolution) “logical pixels”, but sharper.

When running the display at 300% scaling, you get 2560x1440 “logical pixels”, but extremely sharp.

I would say it is a subjective preference which of the two settings to use. Most likely, people who prefer many pixels would run the display at 200%, whereas I prefer the 300% scaling mode for the time being.

Linux compatibility / configuration

To use this display without gross hacks, ensure all relevant components in your software stack support RandR 1.5. My known working configuration is:

  • Xorg 1.19.5
  • nVidia driver 375.82
  • libxcb 1.12
  • i3 4.14
  • i3lock 2.10

With the following command, you can create a RandR MONITOR object spanning the DisplayPort outputs DP-4 and DP-2:

xrandr --setmonitor up3218k auto DP-4,DP-2

I place this command in my ~/.xsession before starting i3.

Theoretically, Xorg could create a MONITOR object automatically. I filed a feature request for this.

Scaling compatibility

With regards to scaling issues, the situation is very similar to any other monitor which requires scaling. Applications which were updated to support 200% scaling seem to work with 300% scaling just as well.

Of course, applications which were not yet updated to work with scaling look even smaller than on 200% displays, so it becomes more of a nuisance to use them. As far as I can tell, the most likely offender are Java applications such as JDownloader.

Buzzing noise

Unfortunately, the monitor emits a high-pitched buzzing noise, very similar to Coil Whine. The noise is loud enough to prevent focused work without listening to music.

I verified that this symptom was happening with Windows and Linux, on two different computers, with default monitor settings, and even when no input source was connected at all.

Finally, I contacted Dell support about it. In the call I received on the next business day, they were very forthcoming and offered to replace the monitor.

The replacement monitor still emits some noise, but much less pronounced. I think I can easily ignore the noise.

Wakeup issues

Rarely (less than once a week), when waking up the monitor from DPMS standby mode, only the left half of the screen would appear on my monitor.

This can be fixed by turning the monitor off and on again.

My theory is that one of the scalers does not manage to synchronize with the video card, but I don’t know for sure.

Interestingly enough, I also encountered this issue with the Dell UP2414Q I bought in 2014. My workaround is to power down that display using its power button in the evenings, and power it up in the mornings.

Conclusion

For me, this monitor is worth it: I am okay with paying the hefty Research & Development tax that first-to-market products such as this monitor have. I like to think that I’m voting with my wallet to make sure vendors notice my interest in “Retina” displays.

For most people, I would recommend to wait until the second or third generation of 8K monitors. By then, I expect most issues to be resolved, compatibility to not be a concern, and vendors focusing on extra features. Hopefully, we’ll eventually see matte 8K monitors with higher refresh rates than 60 Hz.

Technical details

In the hope the following is useful (perhaps for debugging?) to anyone:

11. December 2017 09:05:00

02. December 2017

michael-herbst.com

Annual Colloquium 2017: Introduction to Bohrium

Last Thursday the PhDs of my graduate school gathered again for our self-organised mini conference, named Annual Colloquium. Having organised this event myself as well a couple of years back, I had rather mixed feelings this time, since I most likely not be around in Heidelberg for another AC.

For this reason I am very happy that the organisers gave me the chance to once again make a contribution to this great event. This time I was asked to repeat my interactive introductory talk about the Bohrium automatic parallelisation framework. I already presented about Bohrium in one of my c¼h lectures at the Heidelberg Chaostreff earlier this year and in fact this talk turned out to be very similar to the previous one.

Compared to the points mentioned in my earlier blog post, one should probably add a few things, which have changed in Bohrium in the recent months. First of all Bohrium has made quite some progress regarding the interoperability with other efforts like cython, pyopencl and pycuda for improving the performance of python scripts. In fact Bohrium and these projects can now be used side-by-side and will work together flawlessly to accelerate algorithms written in python. Along a similar line, Bohrium started to look into mechanisms, which could be used to speed up places where one would typically require a plain python for-loops. Whilst this destroys the full compatibility with numpy on the one hand, this allows on the other hand to increase performance in settings, which are hard to write only as array operations.

On top of that the recent integration into the Spack package manager makes it comparatively easy to install Bohrium on any machine (including HPC clusters) to give it a try in a production environment. See the Spack section of the Bohrium documentation for more details.

If you want to find out more about Bohrium, I suggest you read my previous post or watch the recording of my previous talk. For completeness I attach below the demonstration script I used for both Bohrium presentations.

Link Licence
Bohrium moments example script Creative Commons License

by Michael F. Herbst at 02. December 2017 23:00:00

29. November 2017

RaumZeitLabor

Hack To The Future – Mentorinnen und Mentoren gesucht

Ihr überlegt noch, was die erste gute Tat des neuen Jahres werden soll? Ihr habt vom 19. bis 21. Januar Zeit?

Das RaumZeitLabor wird die Initiative Kindermedienland am dritten Wochenende im Januar beim “Hack To The Future” in der Stadtbibliothek Mannheim unterstützen.

Technikbegeisterte Jugendliche bilden kleine Teams und entwickeln innerhalb des Wochenendes eigene digitale Projekte. Dabei werden sie von erfahrenen Mentorinnen und Mentoren unterstützt. Ihr habt Lust und Zeit beim Tüfteln, Coden und bei der Projektentwicklung zu helfen? Perfekt! Dann schaut doch mal hier vorbei!

Vergütet wird das Ganze nicht. Für Mentorinnen und Mentoren gibt es ein HTTF-Shirt und kostenlose Verpflegung am ganzen Wochenende sowie ein gemeinsames Essen nach der Veranstaltung als Dankeschön.

httf_logo

by flederrattie at 29. November 2017 00:00:00

19. November 2017

sECuREs Webseite

Keyboard input latency

I positioned my keyboard as close as possible to the monitor, then used my iPhone to shoot a slo-mo video of me pressing keys while running sm(1).

To quickly get an unmodified copy, I opened Apple Photos (TODO) and shared the file with Google Drive and downloaded it from there. Side note: an upspin dirserver+fileserver iOS app would be amazing. TODO

Converted the video from Apple’s H264 into individual JPG frames:

ffmpeg -i IMG_1748.MOV frame%05d.png

For conveniently moving through the recording frame-by-frame, I opened the file in avidemux3_qt5. Here is a timeline of frames:

  1. frame 1595 LED off, no characters
  2. frame 1596 LED on, no characters
  3. frame 1600 LED on, screen starts updating
  4. frame 1609 LED on, character appears (after animation) 1610 1611 1612 1613 1614 frame 1615 LED off

Each frame is 4.16ms long, so a latency of 4 frames is equivalent to 16.6ms.

frame 2796 led off frame 2797 led on frame 2798 led on, screen update 2799 2800 frame 2801 led off (10ms after led on) latency of one is equivalent to 4.16ms

Connectivity

TODO: measure whether the teensy code runs in <1ms, otherwise we delay the poll rate TODO: change code to permanently scan, so that buffer is already full at poll time, and polls are shorter

TODO: teensy++ 2.0 (which i’m using currently) has no DMA.

Currently used pins: D0-D7, B0-B6, F0-F3 (leds), C0-C6 8+7+7(+4) = 26

Teensy 3.6 has: A9-A10 (10) + A22-A14 (8)

19. November 2017 21:45:00

14. November 2017

sECuREs Webseite

Talks

I have given numerous presentations and talks over the years. As they are starting to vanish from the internet, I started collecting them here.

2017

(en) Go Time #59: Improved Improved Improved (i3)

(de) gokrazy: ein Go userland für Raspberry Pi 3 appliances


(de) die manpages.debian.org-Modernisierung


(en) gokrazy: a Go userland for Raspberry Pi 3 appliances

  • @Go meetup Zürich 2017-04-27

2016

(de) RobustIRC


(de) Monitoring mit Prometheus


2015

(en) RobustIRC


(en, lightning talk) freetserv, a free terminal server (prepared, not presented) pdf

(de @ NoName e.V. 2015-09-24) freetserv, a free terminal server abstract

(de @ GPN15) Debian Code Search Instant

YouTube abstract mp4 pdf


2014

(de @ NoName e.V. 2014-10-30) U2F (Universal 2nd factor): how security keys work abstract pdf

(de @ GPN14) systemd und journald für Nutzer

YouTube abstract mp4 pdf


(de @ GPN14) Linux-based home NAS

YouTube abstract mp4 pdf


2013

(en @ DebConf13) systemd myths debunked!

YouTube abstract ogv pdf


(en @ DebConf13) Making your package work with systemd

YouTube abstract ogv pdf


(de) kanla: small-scale alerting


(de) Debian Code Search


(de @ GPN13) Plan 9


(de @ NoName e.V. 2013-03-21) CHICKEN Scheme abstract pdf

(de @ NoName e.V. 2013-03-14) notmuch abstract pdf

(de @ NoName e.V. 2013-01-24) IPv6 abstract slides (7z)

(de @ NoName e.V. 2013-01-17) DRBD abstract pdf

2012

(de @ NoName e.V. 2012-12-20) Ingress abstract

(de @ NoName e.V. 2012-11-22) Geschichten über WLAN an Bildungseinrichtungen abstract

(de @ NoName e.V. 2012-09-27) Podcasts abstract

(de @ NoName e.V. 2012-09-20) mitgliedsgebühren.pl abstract pdf

(de) systemd

(de @ NoName e.V. 2012-08-30) Yubikey abstract

(de @ NoName e.V. 2012-08-23) buildbot abstract pdf

(de @ NoName e.V. 2012-08-16) scaling the apache/php/postgresql-stack, a real-world example abstract pdf

(de @ NoName e.V. 2012-07-26) Reverse Engineering, Teil 2 abstract

(de @ NoName e.V. 2012-07-19) nVidia CUDA abstract pdf

(de @ NoName e.V. 2012-06-28) Crackmes: Reverse-Engineering auf Assembler-Ebene abstract

(de) Linux Networking - Ninja Style


(de) Go – eine moderne Programmiersprache

(de @ NoName e.V. 2012-05-17) Google App Engine (+Go) abstract pdf

(de @ NoName e.V. 2012-04-26) Raspberry Pi abstract pdf

(de @ RaumZeitLabor 2012-04-24) Videoschnitt

YouTube


(de @ NoName e.V. 2012-04-12) Debian Packaging abstract

(de) Protocol Buffers


(de @ RaumZeitLabor 2012-03-20) BenutzerDB

YouTube


(de) „AllKnowingDNS — Reverse DNS für 2^64 IPv6-Adressen“


(de @ NoName e.V. 2012-03-08) Live-Coding, oder warum Testsuites toll sind, oder sECuRE macht sich zum Affen. abstract

(de) Remote-upgrading microcontroller firmware like a boss


(en @ Google 2012-01-25) i3 — An Improved Tiling Window Manager

YouTube


2011

(de) Lolpizza


(de @ RaumZeitLabor 2011-02-12) IPv6-Grundlagen

(de @ NoName e.V. 2011-04-07) X11-Visualisierung abstract

2010

(de @ NoName e.V. 2010-03-18) CouchDB, eine verteilte, dokumentbasierte Datenbank abstract pdf

(de @ NoName e.V. 2010-02-18) sup, ein Commandline-Mailclient auf Thread-Basis abstract

(de @ NoName e.V. 2010-01-14) dn42 - ein dynamisches VPN abstract pdf

2009

(de @ NoName e.V. 2009-10-15) Vorstellung Hackerspace Rhein-Neckar abstract pdf

(de) Hacking your own Window Manager


(de @ NoName e.V. 2009-08-20) Warum modern perl toll ist abstract pdf

(de @ NoName e.V. 2009-05-21) Cloud Computing-Infrastruktur mit Eucalyptus abstract pdf

(de @ NoName e.V. 2009-04-16) IPv6 – wie, wo, warum? abstract pdf

(de @ NoName e.V. 2009-02-26) Debuggen mit gdb abstract pdf

2008

(de @ NoName e.V. 2008-06-12) git – the stupid content tracker. Wie arbeite ich mit git und warum ist es so viel cooler als subversion? abstract pdf

(de @ NoName e.V. 2008-06-05) Status von p2pdfs (peer-to-peer distributed filesystem), unserem bittorrent-gestützten FUSE-Filesystem - (Kurzform: Ja, da kommen Daten durch mittlerweile!) abstract pdf

(de @ NoName e.V. 2008-05-08) mxallowd abstract pdf

(de @ NoName e.V. 2008-03-27) Bacula-Vortrag, ebenfalls als 50% Vortrag/50%-Workshop abstract pdf

2006

(de @ NoName e.V. 2006-08-24) sECuRE und ch3ka stellen ihr (Python/PHP-)Script PIX vor, mit dem man Filme “galleryzen” kann. abstract

14. November 2017 08:44:04

10. November 2017

michael-herbst.com

Lazy matrices talk from the IWR school 2017

As mentioned in a previous post on this matter last month, from 2nd to 6th October, the IWR hosted the school Mathematical Methods for Quantum Chemistry, which I co-organised together with my supervisors Andreas Dreuw and Guido Kanschat as well as the head of my graduate school Michael Winckler.

From my personal point of view the school turned out to be a major success, where I had the chance to meet a lot of interesting people and got a bucket of ideas to try out in the future. The feedback we got from the participants was positive as well and so I am very happy that all the effort in the past half a year really turned to be worth the while for all of us.

Even though all relevant documents from the school, including the slides from the lectures and most contributed talks, are finally published at the school's website, I nevertheless want to include a pointer to the slides of my lazy matrices talk from this blog for reference.

The topic and structure of the talk is very similar to the talks of the previous months. I motivate the use of contraction-based methods from the realisation, that storing intermediate computational results in memory can be less optimal than recomputing them in a clever way when needed. Then I present lazy matrices as a solution to the issue that the code needed for performing calculations in the sense of contraction-based methods can become very complicated. Afterwards I hint how we use lazy matrices in the context of the quantum chemistry program molsturm and how molsturm itself really facilitates the implementation of new quantum-chemical methods. For this I show in slide 20 a comparison of parts of a working Coupled-Cluster doubles (CCD) code based on molsturm with the relevant part of the equation for the CCD residual.

Link Licence
Lazy matrices for contraction-based algorithms (IWR school talk) Creative Commons License

by Michael F. Herbst at 10. November 2017 23:00:00

20. October 2017

Mero’s Blog

A day in the life of an Omnivore

You get an E-Mail. It's an invite to a team dinner. As you have only recently joined this team, it's going to be your first. How exciting! You look forward to get to know your new coworkers better and socialize outside the office. They are nice and friendly people and you are sure it's going to be a great evening. However, you also have a distinct feeling of anxiety and dread in you. Because you know, the first dinner with new people also means you are going to have the conversation again. You know it will come up, whether you want to or not. Because you had it a thousand times - because you are an Omnivore.

You quickly google the place your manager suggested. "Green's Organic Foodery". They don't have a menu on their site, but the name alone makes clear, that meat probably isn't their specialty, exactly. You consider asking for a change of restaurant, but quickly decide that you don't want to get a reputation as a killjoy who forces their habits on everyone just yet. You figure they are going to have something with meat on their menu. And if not, you can always just grab a burger on your way home or throw a steak into a pan when you get back. You copy the event to your calendar and continue working.

At six, everyone gathers to go to dinner together. It's not far, so you decide to just walk. On the way you get to talk to some of your team mates. You talk about Skiing, your home countries, your previous companies. You are having fun - they seem to be easy-going people, you are getting along well. It's going to be an enjoyable night.

You arrive at the restaurant and get seated. The waiter arrives with the menu and picks up your orders for drinks. When they leave, everyone starts flipping through the menu. “You've got to try their Tofu stir-fry. It's amazing”, Kevin tells you. You nod and smile and turn your attention to the booklet in your hand. You quickly take in the symbols decorating some of the items. “G” - safe to assume, these are the gluten-free options. There's also an “O” on a bunch of them. Also familiar, but ambiguous - could be either “Omnivores" or “Ovo-lacto” (containing at least dairy products or eggs), you've seen both usages. There is no legend to help disambiguate and quickly flipping through the rest of the menu, you find no other symbols. Ovo-lacto, then. You are going to have to guess from the names and short descriptions alone, whether they also contain any meat. They have lasagna, marked with an “O”. Of course that's probably just the cheese but they might make it with actual minced beef.

The waiter returns and takes your orders. “The lasagna - what kind is it?”, you ask. You are trying to avoid the O-word as long as you can. “It's Lasagna alla Bolognese, house style”. Uh-oh. House style? “Is it made from cattle, or based on gluten proteins?” (you don't care how awkward you have to phrase your question, you are not saying the magic trigger words!) “Uhm… I'm not sure. I can ask in the kitchen, if you'd like?” “That would be great, thanks”. They leave. Jen, from across the table, smiles at you - are you imagining it, or does it look slightly awkward? You know the next question. “Are you an Omnivore?” “I eat meat, yes”, you say, smiling politely. Frick. Just one meal, is all you wanted. But it had to come up at some point anyway, so fine. “Wow. I'm Ovo-lacto myself. But I couldn't always eat meat, I think. Is it hard?” You notice that your respective seat neighbors have started to listen too. Ovo-lactos aren't a rarity anymore (Onmivores a bit more so, but not that much), but the topic still seems interesting enough to catch attention. You've seen it before. What feels like a hundred thousand times. In fact, you have said exactly the same thing Jen just said, just a year or so ago. Before you just decided to go Omnivore.

“Not really”, you start. “I found it not much harder than when I went Ovo-lacto. You have to get used to it, of course, and pay a little more attention, but usually you find something. Just like when you start eating cheese and eggs.” At that moment, the waiter returns. “I spoke to the chef and we can make the lasagna with beef, if you like”. “Yes please”, you hand the menu back to them with a smile. “I considered going Ovo-lacto”, Mike continues the conversation from the seat next to Jen, “but for now I just try to have some milk every once in a while. Like, in my coffee or cereal. It's not that I don't like it, there are really great dairy products. For example, this place in the city center makes this amazing yogurt. But having it every day just seems very hard“. “Sure”, you simply say. You know they mean well and you don't want to offend them by not being interested; but you also heard these exact literal words at least two dozen times. And always with ample evidence in the room that it's not actually that hard.

“I don't really see the point”, Roy interjects from the end of the table. You make a mental check-mark. “Shouldn't people just eat what they want? I don't get why suddenly we all have to like meat”. It doesn't matter that no one suggested that. “I mean, I do think it's cool if people eat meat”, someone whose name you don't remember adds, “I sometimes think I should eat more eggs myself. But it's just so annoying that you get these Omnivores who try to lecture you about how unhealthy it is to not eat meat or that humans are naturally predisposed to digest meat. I mean, you seem really relaxed about it”, they quickly add as assurance in your direction, “but you can't deny that there are also these Omni-nazis”. You sip on your water, mentally counting backwards from 3. “You know how you find an Omnivore at a party?”, Kevin asks jokingly from your right. “Don't worry, they will tell you”, Rick delivers the punchline for him. How original.

”I totally get Omnivores. If they want to eat meat, that's great. What I don't understand is this weird trend of fake-salad. Like, people get a salad, but then they put french dressing on it, or bacon bits. I mean, if you want a salad, why not just simply have a salad?”. You know the stupidly obvious answer of course and you haven't talked in a while, so you decide to steer the conversation into a more pleasant direction. “It's simple, really. You like salad, right?” “Yeah, of course“ “So, if you like salad, but decide that you also want to eat dairy or meat - doesn't it make sense to get as close to a pure salad as you can? While still staying with your conviction to eat meat? It's a tradeoff, sure, but isn't it better than no salad at all?” There's a brief pause. You can tell that they haven't considered that before. No one has. Which you find baffling. Every single time. “Hm. I guess I haven't thought about it like that before. From that point of view it does kind of make sense. Anyway, I still prefer the real deal”. “That's fine”, you say, smiling “I will continue to eat my salad with french dressing”.

Your food arrives and the conversation continues for a bit, with the usual follow-up questions - do you eat pork too, or just beef? What about dogs? Would you consider eating monkey meat? Or Human? You explain that you don't worry about the exact line, that you are not dogmatic about it and usually just decide based on convenience and what seems obvious (and in luckily, these questions don't usually need an answer in practice anyway). Someone brings up how some of what's labeled as milk actually is made from almonds, because it's cheaper, so you can't even be sure you actually get dairy. But slowly, person by person, the topic shifts back to work, hobbies and family. “How's the lasagna?”, Jen asks. “Great”, you reply with a smile, because it is.

On your way home, you take stock. Overall, the evening went pretty well. You got along great with most of your coworkers and had long, fun conversations. The food ended up delicious, even if you wish they had just properly labeled their menu. You probably are going to have to nudge your team on future occasions, so you go out to Omnivore-friendlier places. But you are also pretty sure they are open to it. Who knows, you might even get them to go to a steak house at some point. You know you are inevitably going to have the conversation again, at some point - whether it will come up at another meal with your team or with a new person, who you eat with for the first time. This time, at least, it went reasonably well.


This post is a work of fiction. ;) Names, characters, places and incidents either are products of the author's imagination or are used fictitiously. Any resemblance to actual events or locales or persons, living or dead, is entirely coincidental.

Also, if we had "the conversation" before, you should know I still love you and don't judge you :) It's just that I had it a thousand times :)

20. October 2017 23:45:00

18. September 2017

michael-herbst.com

Coulomb-Sturmians and molsturm

Yesterday I gave a talk at our annual group retreat at the Darmstädter Haus in Hirschegg, Kleinwalsertal. For this talk I expanded the slides from my lazy matrix talk in Kiel, incorporating a few of the more recent Coulomb-Sturmian results I obtained.

Most importantly I added a few slides to highlight the issues with standard contracted Gaussians and to discuss the fundamental properties of the Coulomb-Sturmians. Furthermore I gave some details why a contraction-based scheme is advantageous if Coulomb-Sturmian basis functions are employed and discussed the design of our molsturm program package and how it allows to perform calculations in a fully contraction-based manor.

Link Licence
Coulomb-Sturmians and molsturm (Slides Kleinwalsertal talk) Creative Commons License

by Michael F. Herbst at 18. September 2017 22:00:00

12. September 2017

Mero’s Blog

Diminishing returns of static typing

I often get into discussions with people, where the matter of strictness and expressiveness of a static type system comes up. The most common one, by far, is Go's lack of generics and the resulting necessity to use interface{} in container types (the container-subpackages are obvious cases, but also context). When I express my view, that the lack of static type-safety for containers isn't a problem, I am treated with condescending reactions ranging from disbelief to patronizing.

I also often take the other side of the argument. This happens commonly, when talking to proponents of dynamically typed languages. In particular I got into debates of whether Python would be suitable for a certain use-case. When the lack of static type-safety is brought up, the proponents of Python defend it by pointing out that it now features optional type hints. Which they say make it possible, to reap the benefits of static typing even in a conventionally dynamically typed language.

This is an attempt to write my thoughts on both of these (though they are not in any way novel or creative) down more thoroughly. Discussions usually don't provide the space for that. They are also often charged and parties are more interested in “winning the argument”, than finding consensus.


I don't think it's particularly controversial, that static typing in general has advantages, even though actual data about those seems to be surprisingly hard to come by. I certainly believe that, it is why I use Go in the first place. There is a difference of opinion though, in how large and important those benefits are and how much of the behavior of a program must be statically checked to reap those benefits.

To understand this, we should first make explicit what the benefits of static type checking are. The most commonly mentioned one is to catch bugs as early in the development process as possible. If a piece of code I write already contains a rigorous proof of correctness in the form of types, just writing it down and compiling it gives me assurance that it will work as intended in all circumstances. At the other end of the spectrum, in a fully dynamic language I will need to write tests exercising all of my code to find bugs. Running tests takes time. Writing good tests that actually cover all intended behavior is hard. And as it's in general impossible to cover all possible execution paths, there will always be the possibility of a rare edge-case that we didn't think of testing to trigger a bug in production.

So, we can think of static typing as increasing the proportion of bug-free lines of code deployed to production. This is of course a simplification. In practice, we would still catch a lot of the bugs via more rigorous testing, QA, canarying and other practices. To a degree we can still subsume these in this simplification though. If we catch a buggy line of code in QA or the canary phase, we are going to roll it back. So in a sense, the proportion of code we wrote that makes it as bug-free into production will still go down. Thus:

This is usually the understanding, that the “more static typing is always better” argument is based on. Checking more behavior at compile time means less bugs in production means more satisfied customers and less being woken up at night by your pager. Everybody's happy.

Why then is it, that we don't all code in Idris, Agda or a similarly strict language? Sure, the graph above is suggestively drawn to taper off, but it's still monotonically increasing. You'd think that this implies more is better. The answer, of course, is that static typing has a cost and that there is no free lunch.

The costs of static typing again come in many forms. It requires more upfront investment in thinking about the correct types. It increases compile times and thus the change-compile-test-repeat cycle. It makes for a steeper learning curve. And more often than we like to admit, the error messages a compiler will give us will decline in usefulness as the power of a type system increases. Again, we can oversimplify and subsume these effects in saying that it reduces our speed:

This is what we mean when we talk about dynamically typed languages being good for rapid prototyping. In the end, however, what we are usually interested in, is what I'd like to call velocity: The speed with which we can deploy new features to our users. We can model that as the speed with which we can roll out bug-free code. Graphically, that is expressed as the product of the previous two graphs:

In practice, the product of these two functions will have a maximum, a sweet spot of maximum velocity. Designing a type system for a programming language is, at least in part, about finding that sweet spot¹.

Now if we are to accept all of this, that opens up a different question: If we are indeed searching for that sweet spot, how do we explain the vast differences in strength of type systems that we use in practice? The answer of course is simple (and I'm sure many of you have already typed it up in an angry response). The curves I drew above are completely made up. Given how hard it is to do empirical research in this space and to actually quantify the measures I used here, it stands to reason that their shape is very much up for interpretation.

A Python developer might very reasonably believe that optional type-annotations are more than enough to achieve most if not all the advantages of static typing. While a Haskell developer might be much better adapted to static typing and not be slowed down by it as much (or even at all). As a result, the perceived sweet spot can vary widely:

What's more, the importance of these factors might vary a lot too. If you are writing avionics code or are programming the control unit for a space craft, you probably want to be pretty darn sure that the code you are deploying is correct. On the other hand, if you are a Silicon Valley startup in your growth-phase, user acquisition will be of a very high priority and you get users by deploying features quicker than your competitors. We can model that, by weighing the factors differently:

Your use case will determine the sweet spot you are looking for and thus the language you will choose. But a language is also designed with a set of use cases in mind and will set its own sweet spot according to that.

I think when we talk about how strict a type system should be, we need to acknowledge these subjective factors. And it is fine to believe that your perception of one of those curves or how they should be weighted is closer to a hypothetical objective reality than another persons. But you should make that belief explicit and provide a justification of why your perception is more realistic. Don't just assume that other people view them the same way and then be confused that they do not come to the same conclusions as you.


Back to Go's type system. In my opinion, Go manages to hit a good sweet spot (that is, its design agrees with my personal preferences on this). To me it seems that Go reaps probably upwards of 90% of the benefits you can get from static typing while still being not too impeding. And while I definitely agree static typing is beneficial, the marginal benefit of making user-defined containers type-safe simply seems pretty low (even if it's positive). In the end, it would probably be less than 1% of Go code that would get this additional type-checking and it is probably pretty obvious code. And meanwhile, I perceive generics as a language feature pretty costly. So I find it hard to justify a large perceived cost with a small perceived benefit.

Now, that is not to say I'm not open to be convinced. Just that simply saying “but more type-safety!” is only looking at one side of the equation and isn't enough. You need to acknowledge that there is no free lunch and that this is a tradeoff. You need to accept that your perceptions of how big the benefit of adding static typing is, how much it costs and how important it is are all subjective. If you want to convince me that my perception of their benefit is wrong, the best way would be to provide specific instances of bugs or production crashes caused by a type-assertion on an interface{} taken out of a container. Or a refactoring you couldn't make because of the lack of type-safety with a specific container. Ideally, this takes the form of an experience report, which I consider an excellent way to talk about engineered tradeoffs.

Of course you can continue to roll your eyes whenever someone questions your perception of the value-curve of static typing. Or pretend that when I say the marginal benefit of type-safe containers is small, I am implying that the total benefit of static typing is small. It's an effective debate-tactic, if your goal is to shut up your opposition. But not if your goal is to convince them and build consensus.


[1] There is a generous and broad exception for research languages here. If the point of your design is to explore the possibility space of type-systems, matters of practicality can of course often be ignored.

12. September 2017 11:05:00

11. September 2017

michael-herbst.com

Advanced bash scripting 2017

I am very happy to announce that my graduate school asked me to repeat the block course about bash scripting, which I first taught in 2015.

In the course we will take a structured look at UNIX shell scripting from the bottom up. We will revise some elements about the UNIX operating system infrastructure, discuss handy features of the shell as well as its syntax elements. Whilst the main focus of the course is the bash shell, we will look at other common utility programs like grep, sed and awk as well as they are very handy in the context of scripting. Last but not least we will discuss common pitfalls and how they can be avoided.

The course runs from 6th till 10th November 2017 at Heidelberg University. You can find further information on the "Advanced bash scripting" course website.

As usual all course material will be published both on the course website as well as the course github repository afterwards.

Update (29/09/2017): Registration is now open.

by Michael F. Herbst at 11. September 2017 08:00:00

05. September 2017

Mero’s Blog

Gendered Marbles

tl;dr: "Some marbles, apparently, have a gender. And they seem to be overwhelmingly male."

A couple of days ago The MarbleLympics 2017 popped into my twitter stream. In case you are unaware (I certainly was): It's a series of videos where a bunch of marbles participate in a made-up Olympics. They are split into teams that then participate in a series of "competitions" in a variety of different events. The whole event is professionally filmed, cut and overlaid both with fake noises from spectators and a well-made, engaging sports commentary. It is really fun to watch. I don't know why, but I find it way more captivating than watching actual sports. I thoroughly recommend it.

Around event 8 (high jump) though, I suddenly noticed that the commentator would occasionally not only personify but actually gender marbles. For most of the commentary he just refers to the teams as a whole with a generic "they". But every once in a while - and especially often during the high-jump event - he would use a singular gendered pronoun. Also, that only really occurred to me when he referred to one of the marbles as "she".

This instantly became one of those things that after noticing it, I couldn't unnotice it. It's not so much that it matters. But from then on, I couldn't stop listening up every time a singular pronoun was used.

Well, you know where this is going. Fully aware of how much of a waste of my time this is, I sat down and counted. More specifically, I downloaded the closed captions of all the videos and grepped through them for pronouns. I did double-check all findings and here is what I found: By my count, 20 distinct marbles are referred to by singular pronouns (yes. I noted their names to filter duplicates. Also I kind of hoped to find a genderfluid marble to be honest). Here is an alphabetized list of gendered marbles:

  • Aqua (Oceanics) - Male
  • Argent (Quicksilvers) - Male
  • Clementin (O'Rangers) - Male
  • Cocoa (Chocolatiers) - Male (in two events)
  • Cosmo (Team Galactic) - Male
  • Imar (Primaries) - Male
  • Jump (Jungle Jumpers) - Male
  • Leap (Jungle Jumpers) - Male
  • Mandarin (O'Rangers) - Male (in two events)
  • Mary (Team Primary) - Female
  • Mercurial (Quicksilvers) - Male
  • Mimo (Team Momo) - Male
  • Momo Momo (Team Momo) - Male (in three events)
  • Pinky Winky (Pinkies) - Male
  • Rapidly (Savage Speeders) - Male
  • Taffy (Jawbreakers) - Male
  • Wespy (Midnight Wisps) - Male
  • Whizzy (Savage Speeders) - Male
  • Yellah (Mellow Yellow) - Male
  • Yellup (Mellow Yellow) - Male

As you can see, the overwhelming majority of gendered marbles are men. There is exactly one exception: Mary. From what I can tell, that's because it's the only name that has clear gender associations. All the other names probably could go either way. And marbles obviously have no gender. They are as non-gendered an object as you could imagine. And yet there seems to be a default assumption that athletic marbles would be men.

Obviously this doesn't matter. Obviously you can't discriminate marbles. You can't misgender them or hurt their feelings. Obviously the commentator didn't sit down and made a list of all the marbles and assigned 95% of them a male gender - it's clearly just an ad-hoc subconscious assignment. And to be absolutely clear: I do not try to fault the makers of these videos at all. They did nothing wrong. It's a ludicrous expectation for them to sit down and make sure that they assign balanced genders to their marbles.

But I do find it an interesting observation. I do think it reflects an implicit, unconscious bias in a striking way. I also think it illustrates nicely that gender bias in language isn't exclusive to languages like German, where all nouns are gendered (take note, German friends). Of course none of this is news. This kind of unconscious gender bias in language is well-researched and documented. It's just that once you know about it, you can't stop noticing the evidence for it popping up everywhere. Even with marbles.

And all of that being said: Yes, I am also aware that all of this is slightly ridiculous.


PS: In case the team behind the MarbleLympics are reading this: Really, thank you for the videos :) They are great.

05. September 2017 23:22:00

18. August 2017

RaumZeitLabor

Analogspieleabend im RaumZeitLabor

Am 30.09.2017 findet der erste Analogspieleabend im RaumZeitLabor statt. Von Brettspiele über Kartenspiele bis hin zu Rätselspielen und sonstigem hätten wir gerne alles dabei. Deshalb bringt auch eure eigenen Spiele mit! Wir werden dann gemeinsam in netter Runde, zu Mate und Tiefkühlpizza und anderen traditionell nerdigen Speisen, Spiele spielen, wie es im 20. Jahrhundert noch tradition war. Die Veranstaltung beginnt um 17 Uhr. Der Eintritt ist selbstverständlich frei, wir würden uns aber über Spenden freuen. Vorbei ist es, wenn der letzte geht. Ihr wart noch nie im RaumZeitLabor? Schaut euch [Anfahrtbeschreibung](https://raumzeitlabor.de/kontakt/anfahrt/) an und das wichtigste: Schreibt euch die Nummer vom Raum (+49 621 76 23 13 70) auf, damit wir euch helfen können, solltet ihr den Weg nicht finden.

by uwap at 18. August 2017 00:00:00