Yesterday the journal of chemical theory and computation accepted our manuscript titled Polarizable Embedding Combined with the Algebraic Diagrammatic Construction: Tackling Excited States in Biomolecular Systems. In this work we describe the combination of the polarisable embedding~(PE) scheme for including environmental effects with the algebraic-diagrammatic construction~(ADC) approach.

The main idea of polarisable embedding is to model the effect an environment has on a core system by means of modelling the classical electrostatic interactions between both. For this the potential generated by the electron density of the environment is expanded in a multipole series, which is typically truncated at the level of dipoles. Furthermore effect of the core on the environment itself is taken into account by allowing for induced dipoles in the environment next the aforementioned static dipoles of the multipole expansion. Instead of modelling the full details, the environment is thus reduced to a set of static dipole moments and polarisabilities, which are located at some predefined sites, typically the position of the nuclei. During the SCF procedure of the core region the dipoles induced by the core are optimised self-consistently along the SCF, such that after the SCF procedure a consistent electrostatic potential of the environment is included inside the core density.

The reduction of the environment to a set of dipoles and polarisabilities has the advantage, that these parameters can be determined a priori based on a comparatively cheap computational method and a standardised fitting procedure (e.g. LoProp). This implies that one can reduce the size of the system, which needs to be modelled by a more expensive method. One example would be the algebraic-diagrammatic construction scheme for the polarisation propagator for computing so-called excited states, which we connect with polarisable embedding in this work. In order to achieve this properly one has to do a little more than self-consistently finding the electrostatic embedding potential. Namely, one has to keep in mind that an electronic excitation changes the electronic structure of the core, thus changes the polarisation on the embedding and thus again the electronic structure of the core. Taking this effect fully into account would require another self-consistent iteration back and forth between ADC and the PE scheme. One can avoid this by treating this effect only approximately via linear response as well as perturbative corrections on top of an ADC calculation.

Apart from describing these corrections and their connections to physical quantities, we also hint at another important aspect of the simulation procedure, namely finding sensible arrangements for the environment atoms. Since the environment often consists of a solvent or a protein, it tends to be much more flexible compared to the core system. For this reason one cannot merely pick a single random molecular arrangement for the environment, but one needs to sample and perform the full calculation (that is ADC on the core) multiple times in order to gain some statistical results, which are a meaningful model for the exact physical system.

Last but not least we demonstrate the applicability of PE-ADC using three examples, namely a water cluster environment around para-nitroaniline, lumiflavin in bulk water and lumiflavin inside a dodecin protein. For each of the cases a detailed analysis of the results and comparison with existing methods is presented including statistical analysis of the sampling employing box plots.

The full abstract of the paper reads as follows:

We present a variant of the algebraic diagrammatic construction (ADC) scheme by combining ADC with the polarizable embedding (PE) model. The presented PE-ADC method is implemented through second and third order and is designed with the aim of performing accurate calculations of excited states in large molecular systems. Accuracy and large-scale applicability are demonstrated with three case studies, and we further analyze the importance of both state-specific and linear-response-type corrections to the excitation energies in the presence of the polarizable environment. We demonstrate how our combined method can be readily applied to study photo-induced biochemical processes as we model the charge-transfer (CT) excitation which is key to the photoprotection mechanism in the dodecin protein with PE-ADC(2). Through direct access to state-of-the-art excited state analysis, we find that the polarizable environment plays a decisive role by significantly increasing the CT character of the electronic excitation in dodecin. PE-ADC is thus suited to decipher photoinduced processes in complex, biomolecular systems at high precision and at reasonable computational cost.

Vergangene Woche haben wir uns auf den Weg zum Heidelberger Königstuhl gemacht. Neben dem Haus der Astronomie und dem Max-Planck-Institut für Astronomie befindet sich dort oben mit der Landessternwarte Königstuhl ein Teil der größten universitären Einrichtung für astronomische Forschung und Lehre Deutschlands.

Der erste Teil unserer Astrotour brachte uns zu einem über hundert Jahre alten Teleskop in einer der Kuppeln der 1898 eröffneten Landessternwarte. Nachdem wir händisch das Teleskop Richtung Sonne gedreht hatten, durften die Pyromanen unter uns Experimente mit Papier und Lichtbündelung unter Linsen machen.

Im Kuppelprojektionsauditorium des HdA reisten wir mit Hilfe des digitalen Planetariumssystems virtuell durch das Universum, statteten Mark Watney einen Besuch auf dem Mars ab und ließen uns alle unsere Fragen zum Thema Astronomie und Forschung beantworten.

Der letzte Teil unserer Tour führte uns ins Max-Planck-Institut für Astronomie. Dort konnten wir den »Sternenraum« bestaunen – ein von zwei Masterstudenten gebautes 3D-Modell eines Stück Universums. Dargestellt durch über 100 LEDs hängen Sterne und Galaxien an feinen Drähten im Raum. Zum Abschluss unserer Führung durften wir als Vergleich zum Landessternwarten-Teleskop noch ein moderneres 70cm Spiegelteleskop in der Ostkuppel des MPIA bewundern.

Unser Dank für diesen spannenden Nachmittag gilt Stefan, unserem Tourguide und der Presse- und Öffentlichkeitsarbeit des HdA und des MPIA.

Last week from 18th till 23rd June I attended the 16th International Congress of Quantum Chemistry (ICQC) in Menton, France. Apart from the absolutely stunning scenery at the French Riviera as well as the historic conference building, the conference was a great opportunity to meet up and discuss with people from the community. Often the discussions continued in one of the plenty of bars in the old town or right next to the beach. Even though the program was pretty packed, I fortunately still had the chance to walk around and enjoy the Mediterranean atmosphere in Menton as well as the sun and the sea.

During the conference I presented a poster titled Coulomb Sturmians in electronic structure theory, where I discussed my recent convergence results on Coulomb Sturmians, just recently published in my PhD thesis. The poster pdf is attached below.

Link	Licence
Coulomb Sturmians in electronic structure theory (Poster A109)

Last week we submitted the molsturm design paper titled Towards quantum-chemical method development for arbitrary basis functions. This manuscript is a condensed summary of the arguments about design and implementation of a basis-function independent self-consistent field scheme (SCF) already presented in my PhD thesis.

Our approach to a basis-function-independent electronic structure theory code is to employ contraction-based methods for solving the Hartree-Fock (HF) problem. The idea of this ansatz is to avoid storing the Fock matrix, i.e. the matrix representation of the operator underlying the HF problem, in memory. Instead one focuses on only employing optimised expressions for the product of this matrix with a set of trial vectors in the SCF procedure for solving HF. As the paper discusses in more detail this is possible, since all SCF algorithms known to us can be performed based upon iterative procedures, which only require a matrix-vector product.

An advantage of the contraction-based SCF is that the basis-function-dependent structure of the Fock matrix can be hidden inside the expression for the matrix-vector product. As a result the SCF code becomes independent of the basis function choice and new basis functions can be added to our SCF procedure in a plug and play fashion just by linking to appropriate integral libraries. The abstract of the paper reads

We present the design of a flexible quantum-chemical method development framework, which supports employing any type of basis function. This design has been implemented in the light-weight program package molsturm, yielding a basis-function-independent self-consistent field scheme. Versatile interfaces, making use of open standards like python, mediate the integration of molsturm with existing third-party packages. In this way both rapid extension of the present set of methods for electronic structure calculations as well as adding new basis function types can be readily achieved. This makes molsturm well-suitable for testing novel approaches for discretising the electronic wave function and allows comparing them to existing methods using the same software stack. This is illustrated by two examples, an implementation of coupled-cluster doubles as well as a gradient-free geometry optimisation, where in both cases, an arbitrary basis functions could be used. molsturm is open-source and can be obtained from http://molsturm.org.

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.