Liebe RaumZeitLaborierende, Hobbyastronomen und Gelegenheits-Sternegucker!

Ihr interessiert euch für Kosmologie und wolltet schon immer mal in der Spiralgalaxie M51 eine Runde drehen? Oder zumindest in einem Haus, was dieser nachempfunden ist?

Kein Problem – am Montag, den 9. Juli habt ihr die Möglichkeit dazu! Ab 16 Uhr werden wir uns für zwei Stunden auf dem Königstuhl in Heidelberg vollständig der Faszination Astronomie hingeben.

Wir werden das spiralförmige Haus der Astronomie, das Max-Planck-Institut für Astronomie und eventuell auch die Landessternwarte besichtigen. Im Ganzkuppelprojektionsauditorium werden wir bis an den Rand des Universums reisen, wir werden uns über neuste Forschungsaktivitäten informieren und größere Teleskope sowie Modelle aus nächster Nähe anschauen.

Diese Exkursion ist kostenlos und selbstverständlich offen für Noch-nicht-RaumZeitLabor-Mitglieder. Wenn ihr dabei sein wollt, schickt mir bis zum 25. Juni eine elektronische Sternschnuppe mit eurem Namen und den Namen eurer Begleiter. Bitte beachtet: Die Führung kann nur stattfinden, wenn mindestens 12 weltraumforschungsbegeisterte Personen teilnehmen!

Ex astris, scientia

flederrattie

Der SMTP Server Postfix bietet sehr umfangreiche Möglichkeiten zur Reduzierung der Anzahl von Spam-Mails die es bis zum User-Account schaffen. Dieser Artikel befasst sich mit dem Szenario wie man bei verschiedenen Diensten im Internet eine spezielle E-Mail Adresse verwenden und nach einem Leak schon durch Postfix an diese Adresse gesendete E-Mails verwerfen lassen kann.

Mit der Einstellung recipient_delimiter = - in der /etc/postfix/main.cf entsteht die Möglichkeit E-Mail Adressen nach dem Schema user-foobar@domain.tld zu verwenden. E-Mails welche an diese Adresse gesendet werden, landen im Postfach von user, das -foobar in diesem Schema wird an dieser Stelle ignoriert. Die E-Mail selbst verliert dies in ihrem Empfängerfeld jedoch nicht. Dies ermöglicht es mit den meisten E-Mail Clients recht unkompliziert eingehende E-Mails von unterschiedlichen Accounts, welche man im Netz hat, zu filtern. Die E-Mails können automatisch in gesonderte Ordner im Postfach verschoben oder direkt gelöscht werden.

Angenommen man registriert sich beim Onlineshop https://alles-viel-zu-teuer.tld und verwendet als E-Mail Adresse user-vielzuteuer@domain.tld. Nun lassen sich im E-Mail Client mit Filterregeln an diese Adresse gesendete E-Mails wie z.B. Bestellbestätigungen direkt in einen separaten Ordner verschieben. Kommt es nun dazu, dass diese E-Mail Adresse nicht länger allein dem Unternehmen hinter dem Onlineshop bekannt ist, dauert es ja sicherlich nicht lange bis die ersten Spam-Mails ankommen.

Um gegen dieses Problem vorzugehen muss man im Onlineshop die E-Mail Adresse des Accounts ändern, zum Beispiel zu user-vielzuteuernachdemleak@domain.tld. Anschließend kann man auf Server Ebene E-Mails, welche an die ursprüngliche Adresse gesendet werden, umgehend verwerfen. Hierzu legt man eine Textdatei /etc/postfix/reject_rules an und fügt solch eine Regel ein:

/^\s*To:.*user-vielzuteuer@/ DISCARD

DISCARD legt fest, dass eingehende E-Mails, welche an Max Mustermann user-vielzuteuer@domain.tld, user-vielzuteuer@domain.tld oder die Adresse in einer Liste von Empfängern gesendet wurden akzeptiert aber umgehend verworfen werden. Der sendende Server "glaubt" die E-Mail wurde zugestellt und entfernt sie aus der Liste der zu sendenden E-Mails. Alternativ kann man statt DISCARD die Aktion REJECT festlegen, die E-Mail wird abgewiesen und an die E-Mail Adresse von welcher die Spam E-Mail (angeblich) kam wird eine entsprechende E-Mail geschickt.

Hat man die Regel festgelegt lässt mit postmap -q "To: Foo Bar <user-vielzuteuer@domain.tld>" regexp:/etc/postfix/reject_rules in der Shell prüfen ob der Reguläre Ausdruck dieses Header Feld erkennt und die Regel funktioniert.

Als Nächstes fügt man in der /etc/postfix/main.cf diese Zeile hinzu:

header_checks = regexp:/etc/postfix/reject_rules

Abschließend startet man den Postfix Daemon neu oder lädt mit dem Befehl postfix reload die Konfiguration direkt neu.

tl;dr: I explain what co-, contra- and invariance are and what the implications for Go's type system would be. In particular, why it's impossible to have variance in slices.

A question that comes up relatively often with Go newcomers is "why can't I pass e.g. an []int to a func([]interface{})"? In this post I want to explore this question and its implications for Go. But the concept of variance (which this is about) is also useful in other languages.

Variance describes what happens to subtype relationships, when they are used in composite types. In this context, "A is a subtype of B" means that a value of type A can always be used, where a value of type B is required. Go doesn't have explicit subtype relationships - the closest it has is assignability which mostly determines whether types can be used interchangeably. Probably the most important case of this is given by interfaces: If a type T (whether its a concrete type, or itself an interface) implements an interface I, then T can be viewed as a subtype of I. In that sense, *bytes.Buffer is a subtype of io.ReadWriter, which is a subtype of io.Reader. And every type is a subtype of interface{}.

The easiest way to understand what variance means, is to look at function types. Let's assume, we have a type and a subtype - for example, let's look at *bytes.Buffer as a subtype of io.Reader. Say, we have a func() *bytes.Buffer. We could also use this like a func() io.Reader - we just reinterpret the return value as an io.Reader. The reverse is not true: We can't treat a func() io.Reader as a func() *bytes.Buffer, because not every io.Reader is a *bytes.Buffer. So, function return values could preserve the direction of subtyping relationships: If A is a subtype of B, func() A could be a subtype of func() B. This is called covariance.

func F() io.Reader {
    return new(bytes.Buffer)
}

func G() *bytes.Buffer {
    return new(bytes.Buffer)
}

func Use(f func() io.Reader) {
    useReader(f())
}

func main() {
    Use(F) // Works

    Use(G) // Doesn't work right now; but *could* be made equivalent to…
    Use(func() io.Reader { return G() })
}

On the other hand, say we have a func(*bytes.Buffer). Now we can't use that as a func(io.Reader): You can't call it with an io.Reader. But we can do the reverse. If we have a *bytes.Buffer, we can call a func(io.Reader) with it. Thus, function arguments reverse the subtype relationship: If A is a subtype of B, then func(B) could be a subtype of func(A). This is called contravariance.

func F(r io.Reader) {
    useReader(r)
}

func G(r *bytes.Buffer) {
    useReader(r)
}

func Use(f func(*bytes.Buffer)) {
    b := new(bytes.Buffer)
    f(b)
}

func main() {
    Use(F) // Doesn't work right now; but *could* be made equivalent to…
    Use(func(r *bytes.Buffer) { F(r) })

    Use(G) // Works
}

So, func is contravariant for arguments and covariant for return values. Of course, we can combine the two: If A and C are subtypes of B and D respectively, we can make func(B) C a subtype of func(A) D, by converting like this:

// *os.PathError implements error

func F(r io.Reader) *os.PathError {
    // ...
}

func Use(f func(*bytes.Buffer) error) {
    b := new(bytes.Buffer)
    err := f(b)
    useError(err)
}

func main() {
    Use(F) // Could be made to be equivalent to
    Use(func(r *bytes.Buffer) error { return F(r) })
}

However, func(A) C and func(B) D are incompatible. Neither can be a subtype of the other:

func F(r *bytes.Buffer) *os.PathError {
    // ...
}

func UseF(f func(io.Reader) error) {
    b := strings.NewReader("foobar")
    err := f(b)
    useError(err)
}

func G(r io.Reader) error {
    // ...
}

func UseG(f func(*bytes.Buffer) *os.PathErorr) {
    b := new(bytes.Buffer)
    err := f()
    usePathError(err)
}

func main() {
    UseF(F) // Can't work, because:
    UseF(func(r io.Reader) error {
        return F(r) // type-error: io.Reader is not *bytes.Buffer
    })

    UseG(G) // Can't work, because:
    UseG(func(r *bytes.Buffer) *os.PathError {
        return G(r) // type-error: error is not *os.PathError
    })
}

So in this case, there just is not relationship between the composite types. This is called invariance.

Now, we can get back to our opening question: Why can't you use []int as []interface{}? This really is the question "Why are slice-types invariant"?. The questioner assumes that because int is a subtype of interface{}, we should also make []int a subtype of []interface{}. However, we can now see a simple problem with that. Slices support (among other things) two fundamental operations, that we can roughly translate into function calls:

as := make([]A, 10)
a := as[0]      // func Get(as []A, i int) A
as[1] = a       // func Set(as []A, i int, a A)

This shows a clear problem: The type A appears both as an argument and as a return type. So it appears both covariantly and contravariantly. So while with functions there is a relatively clear-cut answer to how variance might work, it just doesn't make a lot of sense for slices. Reading from it would require covariance but writing to it would require contravariance. In other words: If you'd make []int a subtype of []interface{} you'd need to explain how this code would work:

func G() {
    v := []int{1,2,3}
    F(v)
    fmt.Println(v)
}

func F(v []interface{}) {
    // string is a subtype of interface{}, so this should be valid
    v[0] = "Oops"
}

Channels give another interesting perspective here. The bidirectional channel type has the same issue as slices: Receiving requires covariance, whereas sending requires contravariance. But you can restrict the directionality of a channel and only allow send- or receive-operations respectively. So while chan A and chan B would not be related, we could make <-chan A a subtype of <-chan B. And chan<- B a subtype of chan<- A.

In that sense, read-only types have the potential to at least theoretically allow variance for slices. While []int still wouldn't be a subtype of []interface{}, we could make ro []int a subtype of ro []interface{} (borrowing the syntax from the proposal).

Lastly, I want to emphasize that all of these are just the theoretical issues with adding variance to Go's type system. I consider them harder, but even if we could solve them we would still run into practical issues. The most pressing of which is that subtypes have different memory representations:

var (
    // super pseudo-code to illustrate
    x *bytes.Buffer // unsafe.Pointer
    y io.ReadWriter // struct{ itable *itab; value unsafe.Pointer }
                    // where itable has two entries
    z io.Reader     // struct{ itable *itab; value unsafe.Pointer }
                    // where itable has one entry
)

So even though you might think that all interfaces have the same memory representation, they actually don't, because the method tables have a different assumed layout. So in code like this

func Do(f func() io.Reader) {
    r := f()
    r.Read(buf)
}

func F() io.Reader {
    return new(bytes.Buffer)
}

func G() io.ReadWriter {
    return new(bytes.Buffer)
}

func H() *bytes.Buffer {
    return new(bytes.Buffer)
}

func main() {
    // All of F, G, H should be subtypes of func() io.Reader
    Do(F)
    Do(G)
    Do(H)
}

there still needs to be a place where the return value of H is wrapped into an io.Reader and there needs to be a place where the itable of the return value of G is transformed into the correct format expected for an io.Reader. This isn't a huge problem for func: The compiler can generate the appropriate wrappers at the call site in main. There is a performance overhead, but only code that actually uses this form of subtyping needs to pay it. However, it becomes significant problem for slices.

For slices, we must either a) convert the []int into an []interface{} when passing it, meaning an allocation and complete copy. Or b) delay the conversion between int and interface{} until the access, which would mean that every slice access now has to go through an indirect function call - just in case anyone would ever pass us a subtype of what we are expecting. Both options seem prohibitively expensive for Go's goals.

From Monday till Wednesday this week I was invited to the computational mathematics research group of Prof. Dr. Benjamin Stamm at the RWTH Aachen University. In retrospect I am very thankful for the invitation, since the three days turned out to be filled with fruitful discussions, scientific exchange and brainstorming of ideas. I really enjoyed the interdisciplinary spirit of the group, where research is conducted on a broad spectrum of topics ranging from developing fundamental models for classical dynamics, electrostatics and physical processes in batteries to domain decomposition methods for electronic structure theory. I overall found it very enlightening to talk to the PhD students and Post Docs of the group, since the background of the group members is almost as diverse as the topics these people work on.

Last Tuesday I was invited to give a talk as part of the MathCCES lunch seminar talk series. I decided to present an overview of the discretisation methods commonly employed in electronic structure theory. In my talk titled State of the basis in electronic structure theory: Sketching the scene beyond Gaussian-type orbitals I discussed and contrasted a range of basis function types, which may be used for numerical modelling in quantum chemistry. Special focus was put on uncommon basis function types, that is basis sets different from contracted Gaussian-type orbitals. Overall this talk could be considered an extension of section 5.3 of my PhD thesis, where a subset of the basis function types mentioned in the talk are discussed in greater depth and elaborating more on the details with respect to applying them for solving the Hartree-Fock self-consistent field problem. As usual the slides are attached below.

Link	Licence
Beyond Gaussian-type orbitals (MathCCES lunch seminar)

Finally, after quite some years of work I have successfully defended my PhD thesis with the title Development of a modular quantum-chemistry framework for the investigation of novel basis functions on 22nd May. An electronic version of the text has now been published online.

To make the topic of my work accessible both for chemists as well as mathematicians the thesis introduces the numerical modelling of chemical systems from a rather mathematical perspective. For example the first chapters are devoted to spectral theory as well as Ritz-Galerkin discretisation techniques and iterative diagonalisation algorithms. In the following chapters the main equations underlying quantum chemical modelling, i.e. the Schrödinger equation as well as the Hartree-Fock approximation, are presented stating known results about their mathematical properties. Afterwards the focus is shifted to numerical techniques for solving Hartree-Fock and further to developing a unified algorithmic approach for dealing with self-consistent field problems irrespective of the basis function type employed. This leads to a discussion of contraction-based methods, lazy matrices as well as the molsturm package. Last but not least convergence results for Coulomb-Sturmian-based quantum chemistry are presented.
For more details see the full abstract given below.

Published thesis versions

My thesis is made available in three forms. Firstly the officially published documents can be accessed using the DOI 10.11588/heidok.00024519. Please use this DOI as well as this bibtex entry for citations.

Secondly the LaTeX source code is made available on github. I will keep amending this repository as errata and typos are discovered. Note, that I deliberately do not publish this code as free software yet, since there are a few legal issues I want to clearify first. Please let me know, however, if you wish to use some of the LaTeX and CMake code and I am sure we can work something out.

Thirdly, from time to time I plan on making new "releases" out of the amended LaTeX code on github. The link https:/michael-herbst.com/publications/2018.05_phd_corrected.pdf will be used to point to the most recent version.

Full thesis abstract

State-of-the-art methods for the calculation of electronic structures of molecules predominantly use Gaussian basis functions. The algorithms employed inside existing code packages are consequently often highly optimised keeping only their numerical requirements in mind. For the investigation of novel approaches, utilising other basis functions, this is an obstacle, since requirements might differ. In contrast, this thesis develops the highly flexible program package molsturm, which is designed in order to facilitate rapid design, implementation and assessment of methods employing different basis function types. A key component of molsturm is a Hartree-Fock (HF) self-consistent field (SCF) scheme, which is suitable to be combined with any basis function type.

First the mathematical background of quantum mechanics as well as some numerical techniques are reviewed. Care is taken to emphasise the often overlooked subtleties when discretising an infinite-dimensional spectral problem in order to obtain a finite-dimensional eigenproblem. Common quantum-chemical methods such as full configuration interaction and HF are discussed providing insight into their mathematical properties. Different formulations of HF are contrasted and appropriate (SCF) solution schemes formulated.

Next discretisation approaches based on four different types of basis functions are compared both with respect to the computational challenges as well as their ability to describe the physical features of the wave function. Besides (1) Slater-type orbitals and (2) Gaussian-type orbitals, the discussion considers (3) finite elements, which are piecewise polynomials on a grid, as well as (4) Coulomb-Sturmians, which are the analytical solutions to a Schrödinger-like equation. A novel algorithmic approach based on matrix-vector contraction expressions is developed, which is able to adapt to the numerical requirements of all basis functions considered. It is shown that this ansatz not only allows to formulate SCF algorithms in a basis-function independent way, but furthermore improves the theoretically achievable computational scaling for finite-element-based discretisations as well as performance improvements for Coulomb-Sturmian-based discretisations. The adequacy of standard SCF algorithms with respect to a contraction-based setting is investigated and for the example of the optimal damping algorithm an approximate modification to achieve such a setting is presented.

With respect to recent trends in the development of modern computer hardware the potentials and drawbacks of contraction-based approaches are evaluated. One drawback, namely the typically more involved and harder-to-read code, is identified and a data structure named lazy matrix is introduced to overcome this. Lazy matrices are a generalisation of the usual matrix concept, suitable for encapsulating contraction expressions. Such objects still look like matrices from the user perspective, including the possibility to perform operations like matrix sums and products. As a result programming contraction-based algorithms becomes similarly convenient as working with normal matrices. An implementation of lazy matrices in the lazyten linear algebra library is developed in the course of the thesis, followed by an example demonstrating the applicability in the context of the HF problem.

Building on top of the aforementioned concepts the design of molsturm is outlined. It is shown how a combination of lazy matrices and a contraction-based SCF scheme separates the code describing the SCF procedure from the code dealing with the basis function type. It is discussed how this allows to add a new basis function type to molsturm by only making code changes in a single integral interface library. On top of that, we demonstrate by the means of examples how the readily scriptable interface of molsturm can be employed to implement and assess novel quantum-chemical methods or to combine the features of molsturm with existing third-party packages.

Finally, the thesis discusses an application of molsturm towards the investigation of the convergence properties of Coulomb-Sturmian-based quantum-chemical calculations. Results for the convergence of the ground-state energies at HF level are reported for atoms of the second and the third period of the periodic table. Particular emphasis is put on a discussion about the required maximal angular momentum quantum numbers in order to achieve convergence of the discretisation of the angular part of the wave function. Some modifications required for a treatment at correlated level are suggested, followed by a discussion of the effect of the Coulomb-Sturmian exponent. An algorithm for obtaining an optimal exponent is devised and some optimal exponents for the atoms of the second and the third period of the periodic table at HF level are given. Furthermore, the first results of a Coulomb-Sturmian-based excited states calculation based on the algebraic-diagrammatic construction scheme for the polarisation propagator are presented.

Acknowledgements

No doubt the research leading up to a PhD thesis cannot be successfully achieved without the help and support from many people, both scientifically as well as on a personal level. In the past years I have been very lucky to be surrounded by people, who created an environment for fruitful discussion. I am happy for everyone from related fields of science and technology, who broadened my own perspective by getting me in touch with new and unusual ideas and who helped me escape the box of my own narrow thinking. Many people should be named in this respect, most of them are already given credit in the acknowledgement section of my PhD thesis, so let me be rather brief here and simply say thanks!

Download thesis

To download the most recent version including corrections for all known errors and typos use this link. To cite the thesis please use this bibtex entry.

Die letzten Jahre war es hier recht ruhig. Das hatte verschiedene Gründe, unter anderem weil ich mich mit dem zuvor verwendeten octopress nicht wirklich anfreunden konnte. Ruby ist keine Sprache, welche ich häufig verwende und da octopress nach Aktualisierungen auf meinen Systemen leider häufiger Probleme mit inkompatiblen Gems hatte, war mir dann irgendwann auch die Lust vergangen.

Nun ein Neuanfang, diesmal mit Pelican, welches auf Python setzt, eine Sprache die ich deutlich häufiger verwende. Wenn es hier zu Inkompatibilitäten kommt muss ich hoffentlich deutlich weniger Zeit investieren. Abgesehen davon war es hier mit dem Standardtheme auch recht einfach Aufrufe externer HTTP Server zu entfernen.

Warning: if you don’t understand one of the steps, don’t blindly follow them, but ask a friend for help instead! Be sure to have a known-working backup before messing with your system.

Motivation

I recently got a Dell XPS 13 9360 (2017), which of course I would like to use with Linux. I figured I’d give Dell’s Ubuntu version a try, as it is the closest I can get to a supported Linux offering on a modern laptop.

Unfortunately, Dell doesn’t sell the XPS 9360 in its shop anymore (and I don’t like its successor due to the lack of USB A ports), so I had to resort to buying a version that comes with Windows.

You can obtain the recovery image dell-bto-xenial-dino2-mlk-A00-iso-20161021-0.iso from http://www.dell.com/support/home/us/en/19/Drivers/OSISO/W764, provided you have the system tag of an XPS 9360 that came with Linux — ask a friend if you accidentally purchased the Windows version. Tip: the service tag is the BIOS serial number, which is included in the output of lshw(1) and similar tools.

Making the image bootable

I don’t understand why this image is not bootable by default. The device it was generated for never had a CD/DVD drive, so what good is using an ISO 9660 image?

Anyway, to make the image bootable, I formatted a USB thumb drive with a FAT file system and installed GRUB in such a way that it will loopback-boot into the ISO image (this is option 2 from https://askubuntu.com/a/395880):

grub-mkimage -o bootx64.efi -p /efi/boot -O x86_64-efi \
 fat iso9660 part_gpt part_msdos \
 normal boot linux configfile loopback chain \
 efifwsetup efi_gop efi_uga \
 ls search search_label search_fs_uuid search_fs_file \
 gfxterm gfxterm_background gfxterm_menu test all_video loadenv \
 exfat ext2 ntfs btrfs hfsplus udf
cat >grub.cfg <<'EOT'
set timeout=3
set color_highlight=black/light-magenta

menuentry 'Ubuntu ISO' {
        set isofile="/efi/boot/dell-bto-xenial-dino2-mlk-A00-iso-20161021-0.iso"
        loopback loop $isofile
        linux (loop)/casper/vmlinuz.efi boot=casper iso-scan/filename=$isofile noprompt noeject quiet splash persistent --
        initrd (loop)/casper/initrd.lz
}
EOT

sudo mkfs.vfat /dev/sdc
pmount /dev/sdc
mkdir -p /media/sdc/efi/boot
cp bootx64.efi *.iso grub.cfg /media/sdc/efi/boot
pumount sdc

Making the installer work

To get the installer to work, I had to comment out the self.genuine checks in /usr/lib/ubiquity/plugins/dell-{bootstrap,recovery}.py, then start ubiquity from the terminal.

Switch to LUKS full-disk encryption

Unfortunately, the recovery installation only offers you to encrypt your homedir, whereas I would like to encrypt my entire disk. Here are the steps I took to enable LUKS full-disk encryption.

First, I copied the root file system’s data to my backup storage. Pay attention to copying the files as root, otherwise setuid and setgid bits might get lost.

# mount /dev/mapper/nvme0n1p3 /mnt/root
# rsync -aXx --relative --numeric-ids /mnt/root/ root@storage:xps/
# umount /mnt/root

Then, I created a new boot partition, encrypted the root partition and re-created the file system:

# cat <<'EOT' | sfdisk /dev/nvme0n1
label: gpt
label-id: C64A87D1-CA61-4BF2-81E6-0216EE6BC4C0
device: /dev/nvme0n1
unit: sectors
first-lba: 34
last-lba: 2000409230

/dev/nvme0n1p1 : start=          34, size=      488248, type=C12A7328-F81F-11D2-BA4B-00A0C93EC93B, name="EFI System Partition"
/dev/nvme0n1p2 : start=      488282, size=     5380681, type=EBD0A0A2-B9E5-4433-87C0-68B6B72699C7, name="fat32"
/dev/nvme0n1p3 : start=     5869568, size=     2097152, type=0FC63DAF-8483-4772-8E79-3D69D8477DE4
/dev/nvme0n1p4 : start=     7966720, size=  1992442511, type=0FC63DAF-8483-4772-8E79-3D69D8477DE4
EOT
# mkfs.ext2 /dev/nvme0n1p3
# cryptsetup luksFormat /dev/nvme0n1p4
# cryptsetup luksOpen /dev/nvme0n1p4 nvme0n1p3_crypt
# mkfs.ext4 /dev/mapper/nvme0n1p4_crypt

Next, I restored the data:

# mount /dev/mapper/nvme0n1p4_crypt /mnt/root
# mount /dev/nvme0n1p3 /mnt/root/boot
# mkdir /mnt/root/boot/efi
# mount /dev/nvme0n1p1 /mnt/root/boot/efi
# rsync -aXx --numeric-ids storage:xps/ /mnt/root

And finally, I fixed the boot partition:

# mount -o bind /dev /mnt/root/dev
# mount -t sysfs sysfs /mnt/root/sys
# mount -t proc proc /mnt/root/proc
# chroot /mnt/root /bin/bash

# apt install cryptsetup
# echo nvme0n1p4_crypt UUID=$(blkid -o value -s UUID /dev/nvme0n1p4) none luks,discard > /etc/crypttab
# cat >/etc/fstab <<EOT
UUID=$(blkid -o value -s UUID /dev/mapper/nvme0n1p4_crypt) / ext4 errors=remount-ro 0 1
UUID=$(blkid -o value -s UUID /dev/nvme0n1p3) /boot ext2 defaults 0 0
UUID=$(blkid -o value -s UUID /dev/nvme0n1p1) /boot/efi vfat umask=0077 0 1
EOT
# update-initramfs -u
# update-grub
# grub-install

# umount /mnt/root/{proc,sys,dev,boot/efi,boot,}

Wir sind zurück von unserer Tour durch’s Technoseum.

Unter dem Motto „Mensch und Maschine“ haben wir einen Ausflug quer durch die Geschichte der Industrialisierung gemacht. An verschiedenen Stationen konnten wir uns den Übergang von der Hand- zur Maschinenarbeit genauer ansehen und unterschiedliche Maschinenantriebe und -steuerungen selbst ausprobieren. Besonders in den Bann gezogen hat uns die Wippendrehbank – vielleicht haben wir das erste DIY-Projekt für unsere neue Werkstatt gefunden?

Nach einer gemeinschaftlichen Montage eines Spielzeugautos mit dem Zweiarm-Roboter YuMi konnten wir Technoseum-Maskottchen Paul noch bei seiner Tanz-Vorführung zuschauen.

Die Zeit nach der Führung nutzten wir spontan, um der Sonderausstellung „Entscheiden“ noch einen Besuch abzustatten.

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.

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:

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.

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.

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

• While not strictly a part of this series, “Hacking your own Kinesis keyboard controller” describes the first controller I built in 2013 (maybe interesting for context).

• The first post introduces the kinX, a keyboard controller with merely 0.2ms of input latency (including USB).

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

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

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

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.

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)

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.

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.

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.

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.

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.

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

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. ⬆

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.

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.

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:

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:

\(\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}\):

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):

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:

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. ⬆

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.

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

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:

• hex dump of the EDID data block
• decoded EDID block
• xrandr --prop output
• Xorg.0.log

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