Joachim Breitner

Blog

microG on Jolla

Published 2016-11-23 in sections English, Digital World.

I am a incorrigibly in picking non-mainstream, open smartphones, and then struggling hard. Back then in 2008, I tried to use the OpenMoko FreeRunner, but eventually gave up because of hardware glitches and reverted to my good old Siemens S35. It was not that I would not be willing to put up with inconveniences, but as soon as it makes live more difficult for the people I communicate with, it becomes hard to sustain.

Two years ago I tried again, and got myself a Jolla phone, running Sailfish OS. Things are much nicer now: The hardware is mature, battery live is good, and the Android compatibility layer enables me to run many important apps that are hard to replace, especially the Deutsche Bahn Navigator and various messengers, namely Telegram, Facebook Messenger, Threema and GroupMe.

Some apps that require Google Play Services, which provides a bunch of common tasks and usually comes with the Google Play store would not run on my phone, as Google Play is not supported on Sailfish OS. So far, the most annoying ones of that sort were Uber and Lyft, making me pay for expensive taxis when others would ride cheaper, but I can live with that. I tried to install Google Play Services from shady sources, but it would regularly crash.

Signal on Jolla

Now in Philadelphia, people urged me to use the Signal messenger, and I was convinced by its support for good end-to-end crypto, while still supporting offline messages and allowing me to switch from my phone to my desktop and back during a conversation. The official Signal app uses Google Cloud Messaging (GCM, part of Google Play Services) to get push updates about new posts, and while I do not oppose this use of Google services (it really is just a ping without any metadata), this is a problem on Sailfish OS.

Luckily, the Signal client is open source, and someone created a “LibreSignal” edition that replaced the use of GCM with websockets, and indeed, this worked on my phone, and I could communicate.

Things were not ideal, though: I would often have to restart the app to get newly received messages; messages that I send via Signal Desktop would often not show up on the phone and, most severe, basically after every three messages, sending more messages from Desktop would stop working for my correspondents, which freaked them out. (Strangely it continued working from their phone app, so we coped for a while.)

So again, my choice of non-standard devices causes inconveniences to others. This, and the fact that the original authors of Signal and the maintainers of LibreSignal got into a fight that ended LibreSignal discontinued, meant that I have to change something about this situation. I was almost ready to give in and get myself a Samsung S7 or something boring of the sort, but then I decided to tackle this issue once more, following some of the more obscure instructions out there, trying to get vanilla Signal working on my phone. About a day later, I got it, and this is how I did it.

microG

So I need Google Play Services somehow, but installing the “real thing” did not seem to be very promising (I tried, and regularly got pop-ups telling me that Play Services has crashed.) But I found some references to a project called “microG”, which is an independent re-implementation of (some of) of the play services, in particular including GCM.

Installing microG itself was easy, as you can add their repository to F-Droid. I installed the core services, the services framework and the fake store apps. If this had been all that was to do, things would be easy!

Play Store detection work arounds

But Signal would still complain about the lack of Google Play Services. It asks Android if an app with a certain name is installed, and would refuse to work if this app does not exist. For some reason, the microG apps cannot just have the names of the “real” Google apps.

There seem to be two ways of working around this: Patching Signal, or enabling Signature Spoofing.

The initially most promising instructions (which are in a README in a tarball on a fishy file hoster linked from an answer on the Jolla support forum…) suggested patching Signal, and actually came both with a version of an app called “Lucky Patcher” as well as a patched Android package, but both about two years old. I tried a recent version of the Lucky Patcher, but it failed to patch the current version of Signal.

Signature Spoofing

So on to Signature Spoofing. This is a feature of some non-standard Android builds that allow apps (such as microG) to fake the existence of other apps (the Play Store), and is recommended by the microG project. Sailfish OS’s Android compatibility layer “Alien Dalvik” does not support it out of the box, but there is a tool “tingle” that adds this feature to existing Android systems. One just has to get the /system/framework/framework.jar file, put it into the input folder of this project, run python main.py, select 2, and copy the framework.jar from output/ back. Great.

Deodexing Alien Dalvik

Only that it only works on “deodexed” files. I did not know anything about odexed Android Java classes (and did not really want to know), but there was not way around. Following this explanation I gathered that one finds files foo.odex in the Android system folder, runs some tool on them to create a classes.dex file, and adds that to the corresponding foo.jar or foo.apk file, copies this back to the phone and deletes the foo.odex file.

The annoying this is that one does not only have to do it for framework.jar in order to please tingle, because if one does it to one odex file, one has to do to all! It seems that for people using Windows, the Universal Deodexer V5 seems to be a convenient tool, but I had to go more manually.

So I first fetched “smali”, compiled it using ./gradlew build. Then I fetched the folders /opt/alien/system/framework and /opt/alien/system/app from the phone (e.g. using scp). Keep a backup of these in case something breaks. Then I ran these commands (disclaimer: I fetched these from my bash history and slightly cleaned them up. This is not a fire-and-forget script! Use it when you know what it and you are doing):

cd framework
for file in *.odex
do
  java -jar ~/build/smali/baksmali/build/libs/baksmali.jar deodex $file -o out
  java -jar ~/build/smali/smali/build/libs/smali.jar a out -o classes.dex
  zip -u $(basename $file .odex).jar classes.dex
  rm -rf out classes.dex $file
done
cd ..

cd app
for file in *.odex
do
  java -jar ~/build/smali/baksmali/build/libs/baksmali.jar deodex -d ../framework $file -o out
  java -jar ~/build/smali/smali/build/libs/smali.jar a out -o classes.dex
  zip -u $(basename $file .odex).apk classes.dex
  rm -rf out classes.dex $file
done
cd ..

The resulting framework.jar can now be patched with tingle:

mv framework/framework.jar ~/build/tingle/input
cd ~/build/tingle
./main.py
# select 2
cd -
mv ~/build/tingle/output/framework.jar framework/framework.jar

Now I copy these framework and app folders back on my phone, and restart Dalvik:

devel-su systemctl restart aliendalvik.service

It might start a bit slower than usually, but eventually, all the Android apps should work as before.

The final bit that was missing in my case was that I had to reinstall Signal: If it is installed before microG is installed, it does not get permission to use GCM, and when it tries (while registering: After generating the keys) it just crashes. I copied /data/data/org.thoughtcrime.secretsms/ before removing Signal and moved it back after (with cp -a to preserve permissions) so that I could keep my history.

And now, it seems, vanilla Signal is working just fine on my Jolla phone!

What’s missing

Am I completely happy with Signal? No! An important feature that it is lacking is a way to get out all data (message history including media files) in a file format that can be read without Signal; e.g. YAML files or clean HTML code. I do want to be able to re-read some of the more interesting conversations when I am 74 or 75, and I doubt that there will be a Signal App, or even Android, then. I hope that this becomes available in time, maybe in the Desktop version.

I would also hope that pidgin gets support to the Signal protocol, so that I conveniently use one program for all my messaging needs on the desktop.

Finally it would be nice if my Signal identity was less tied to one phone number. I have a German and a US phone number, and would want to be reachable under both on all my clients. (If you want to contact me on Signal, use my US phone number.)

Alternatives

Could I have avoided this hassle by simply convincing people to use something other than Signal? Tricky, at the moment. Telegram (which works super reliable for me, and has a pidgin plugin) has dubious crypto and does not support crypto while using multiple clients. Threema has no desktop client that I know of. OTR on top of Jabber does not support offline messages. So nothing great seems to exist right now.

In the long run, the best bet seems to be OMEMO (which is, in essence, the Signal protocol) on top of Jabber. It is currently supported by one Android Jabber client (Conversations) and one Desktop application (gajim, via a plugin). I should keep an eye on pidgin support for OMEMO and other development around this.

Drei Jahreszeiten

Published 2016-11-20 in sections Philadelphia, Deutsch.

Hier in Pennsylvania tickt das Wetter etwas anders als bei uns…

Sommer

Dieses Wochenende fuhr ich mit einer Freundin in die Poconos Mountains. Wir bezogen eine kleine Holzhütte im Wald. Samstag morgen frühstückten wir draußen. Wir wanderten im T-Shirt durch den Beltzville Park und picknickten mittags am Ufer von der Sonne beschienen und unter blauem Himmel. Temperatur vielleicht 26°C.

Frühstück in der Sonne

Frühstück in der Sonne

Herbst

Im Anschluss wanderten wir durch die Lehigh Gorge. Ein kühler Ostwind blies uns um die Ohren und lupfte das Laub in die Höhe. Wir futterten in Jim Thorpe und als wir wieder im Auto waren, fielen die ersten Regentropfen aufs Dach. Temperatur vielleicht 10°C.

Winter

Irgendwann hörte ich abends den Regen nicht mehr – er wurde zu Schnee. Und Sonntag morgen war die Hütte, das Auto und der Wald um uns herum mit einer 15cm dicken Schneeschicht bedeckt. Das Thermometer zeigte -3°C. Wir gingen wieder spazieren, diesmal um den Gipfel des Camelback Mountain herum. Alles war weiß und dick eingepudert,

Kein Frühstück im Schnee

Kein Frühstück im Schnee

Drei Jahreszeiten an einem Wochenende – das nenn ich effizienten Urlaub.

(Mehr Bilder auf meiner Bilderseite.)

Nach der Wahl

Published 2016-11-15 in sections Deutsch, Philadelphia.

„Wie sieht’s aus in Trump-Land?“

Gute Frage. Ich kann ja mal ein paar Eindrücke schildern.

Wahlkampf

Anfangs war alles noch nett und lustig. Mit Arbeitskollegen schaute ich das erste Fernsehduell zwischen Clinton und Trump. Es wurde viel getrunken, vor allem wenn Trump den Mund aufmachte, aber insgesamt machte Hillary Trump fertig. Sah also gut aus.

Auf Facebook (und den auf Facebook verlinkten Medien) wurde sich über Trump’s Persönlichkeit ausgelassen, und ich wundere mich, warum so wenig über seine Politik geredet wird – lieber ein Arschloch als Präsident, der das richtige macht, als ein Traumschwiegersohn mit den falschen Zielen, würde ich sagen – aber wohl zurecht wurde ich darauf hingewiesen, dass man auf seine Wahlversprechen eh nichts geben kann. Trotzdem halte ich fest dass die Übermoralisierung des Politikers hier weiter fortgeschritten ist als in Deutschland.

Die letzte Woche vor der Wahl war überraschend ruhig. Die Prognosen sahen gut aus (Gewinnwahrscheinlichkeit für Clinton war bei ⅔). Viele meine Kollegen beteiligten sich ehrenamtlich am Wahlkampf, klingelten Telefonlisten durch oder marschierten von Haus zu Haus. Dabei geht es nicht darum, Wechselwähler oder gar Trumpwähler umzustimmen, sondern lediglich, die demokratisch gesinnten Wähler auch zum Wählen zu kriegen.

Wahltag

Am Wahltag war -- soweit ich das erkennen kann -- gerade zu heitere Stimmung. Das Wetter war gut, und auf dem Campus trug jeder stolz seinen „I voted“-Aufkleber auf der Brust, den man hier bekommt. Man fragte sich gegenseitig, ob man schon wählen war.

Abends verfolgte eine Freundin und ich das Geschehen in einer Kneipe hier in West-Philadelphia, es lief CNN. Als verkündet wurde, dass Michigan an die Republikaner ging, war ihr klar, dass hier etwas gewaltig schief lief. CNN berichtete noch von neuen Meldungen aus den verschiedenen Staaten, aber die Prognose auf nytimes.com sagte schon eine Wahrscheinlichkeit von >95% für Trump. Die Wahl war gelaufen, und sie lief anders als von allen in meiner Umgebung hier erhofft, und auch anders als erwartet. Für mich fühlte es sich wie eine Wiederholung des Brexit-Wahlabends an. Auch Pennsylvania kippte und wählte insgesamt für Trump. Wir hatten keine Lust mehr auf Kneipe und verzogen uns.

Nach der Wahl

Selbst das Wetter war deprimiert. Davor noch herrlich sonnig, war es jetzt plötzlich kalt und regnerisch. Tränen hier in meiner WG. Eine Mitbewohnerin macht sich Sorgen um ihre Krankenversicherung wenn Obamacare gestrichen wird. An der Uni gedrückte Stimmung. Auf Facebook gingen die Emotionen um. Freunde luden Freunde zum gemeinsamen Wundenlecken ein.

Am zweiten Abend gab es in der Innenstadt Protestmärsche gegen Trump mit mehreren Tausend Teilnehmern. Gleichzeitig gab es Berichte über sogenannte „hate crimes“ im ganzen Land (eine von Schwarzen genutzte Kirche wurde noch vor der Wahl abgefackelt, weitere andere nach der Wahl beschmiert und in Philadelphia (Hakenkreuz-Graffiti und Nazi-Sprüche an Wänden, sexistische Sprüche in die Autofenster einer Professorin geritzt). Facebook-Freunde von mir erkundigen sich nach geeigneten Kampfsportarten und Selbstverteidigungskursen um bei eventuellen Auseinandersetzungen ihre Freunde und sich selbst schützen zu können. Es werden Parallelen zu Deutschland nach dem ersten Weltkrieg und Hitlers Machtübernahme gezogen.

An der Universität werden schwarze Studenten per „GroupMe“ mit rassistischen Sprüchen überzogen. Große Aufregung mit mehreren Rundmails des Präsidiums an alle Mitglieder der Studenten, FBI eingeschaltet, und Ermittlungen in Oklahoma, wo die Täter wohl sind.

Eine andere Rundmail der Präsidentin an alle Mitarbeiter, dass einige Studenten jetzt nach der Wahl sicherlich eine schwere Zeit durchmachen, und an solle doch bitte nachsichtig und einfühlsam zu sein, und flexibel was Hausaufgaben oder so angeht.

Und ich?

Unmittelbar betrifft mich die Wahl von Trump nicht. Ich bin kein Muslim, ich bin kein Mexikaner, ich bin keine Frau, nicht Queer und ich bin legal hier. Noch fühle ich mich durch den Straßenverkehr und die in Deutschland sicherlich so verboten schmalen Treppen stärker bedroht. Mittelfristig macht mir die zu erwartende Klimapolitik und Trumps Einstellung zur NATO durchaus sorgen. Aber ich bin Optimist, vielleicht hat ein unberechenbarer US-Präsident eher einen Fukushima-Moment mit 180°-Wende als die Parteipolitikerin.

Ich finde es bedenklich, wie segregiert das Land hier ist. In Pennsylvania gibt es zwei große Städte, und hier habe ich kein einziges Trump-Schild in den Vorgärten gesehen. Keiner, den ich kenne, hat offen für die Republikaner gestimmt. Die knapp 50% der Wähler, die Trump an die Macht gebracht haben -- wir kennen sie hier nicht, und sie kennen uns nicht. Das ist in Deutschland doch anders: Da gehen CDU- und SPD-Wähler gemeinsam zum Sport, auch ein Grünenwähler kennt vermutlich einen FDP-Anhänger, und selbst AFDler leben unter uns, und man kann mit ihnen reden. Ich wünsche den USA, irgendwie diese Spaltung zu überwinden und eine gesündere Demokratie zu entwickeln, vielleicht sogar eine mit Verhältniswahlrecht, vielleicht mit Wahlbeteiligung deutlich über 50%, besonders nach einem so kontroversen Wahlkampf. Man wird ja wohl noch träumen dürfen.

Showcasing Applicative

Published 2016-10-26 in sections English, Haskell.

My plan for this week’s lecture of the CIS 194 Haskell course at the University of Pennsylvania is to dwell a bit on the concept of Functor, Applicative and Monad, and to highlight the value of the Applicative abstraction.

I quite like the example that I came up with, so I want to share it here. In the interest of long-term archival and stand-alone presentation, I include all the material in this post.1

Imports

In case you want to follow along, start with these imports:

import Data.Char
import Data.Maybe
import Data.List

import System.Environment
import System.IO
import System.Exit

The parser

The starting point for this exercise is a fairly standard parser-combinator monad, which happens to be the result of the student’s homework from last week:

newtype Parser a = P (String -> Maybe (a, String))

runParser :: Parser t -> String -> Maybe (t, String)
runParser (P p) = p

parse :: Parser a -> String -> Maybe a
parse p input = case runParser p input of
    Just (result, "") -> Just result
    _ -> Nothing -- handles both no result and leftover input

noParserP :: Parser a
noParserP = P (\_ -> Nothing)

pureParserP :: a -> Parser a
pureParserP x = P (\input -> Just (x,input))

instance Functor Parser where
    fmap f p = P $ \input -> do
	(x, rest) <- runParser p input
	return (f x, rest)

instance Applicative Parser where
    pure = pureParserP
    p1 <*> p2 = P $ \input -> do
        (f, rest1) <- runParser p1 input
        (x, rest2) <- runParser p2 rest1
        return (f x, rest2)

instance Monad Parser where
    return = pure
    p1 >>= k = P $ \input -> do
        (x, rest1) <- runParser p1 input
        runParser (k x) rest1

anyCharP :: Parser Char
anyCharP = P $ \input -> case input of
    (c:rest) -> Just (c, rest)
    []       -> Nothing

charP :: Char -> Parser ()
charP c = do
    c' <- anyCharP
    if c == c' then return ()
               else noParserP

anyCharButP :: Char -> Parser Char
anyCharButP c = do
    c' <- anyCharP
    if c /= c' then return c'
               else noParserP

letterOrDigitP :: Parser Char
letterOrDigitP = do
    c <- anyCharP
    if isAlphaNum c then return c else noParserP

orElseP :: Parser a -> Parser a -> Parser a
orElseP p1 p2 = P $ \input -> case runParser p1 input of
    Just r -> Just r
    Nothing -> runParser p2 input

manyP :: Parser a -> Parser [a]
manyP p = (pure (:) <*> p <*> manyP p) `orElseP` pure []

many1P :: Parser a -> Parser [a]
many1P p = pure (:) <*> p <*> manyP p

sepByP :: Parser a -> Parser () -> Parser [a]
sepByP p1 p2 = (pure (:) <*> p1 <*> (manyP (p2 *> p1))) `orElseP` pure []

A parser using this library for, for example, CSV files could take this form:

parseCSVP :: Parser [[String]]
parseCSVP = manyP parseLine
  where
    parseLine = parseCell `sepByP` charP ',' <* charP '\n'
    parseCell = do
        charP '"'
        content <- manyP (anyCharButP '"')
        charP '"'
        return content

We want EBNF

Often when we write a parser for a file format, we might also want to have a formal specification of the format. A common form for such a specification is EBNF. This might look as follows, for a CSV file:

cell = '"', {not-quote}, '"';
line = (cell, {',', cell} | ''), newline;
csv  = {line};

It is straightforward to create a Haskell data type to represent an EBNF syntax description. Here is a simple EBNF library (data type and pretty-printer) for your convenience:

data RHS
  = Terminal String
  | NonTerminal String
  | Choice RHS RHS
  | Sequence RHS RHS
  | Optional RHS
  | Repetition RHS
  deriving (Show, Eq)

ppRHS :: RHS -> String
ppRHS = go 0
  where
    go _ (Terminal s)     = surround "'" "'" $ concatMap quote s
    go _ (NonTerminal s)  = s
    go a (Choice x1 x2)   = p a 1 $ go 1 x1 ++ " | " ++ go 1 x2
    go a (Sequence x1 x2) = p a 2 $ go 2 x1 ++ ", "  ++ go 2 x2
    go _ (Optional x)     = surround "[" "]" $ go 0 x
    go _ (Repetition x)   = surround "{" "}" $ go 0 x

    surround c1 c2 x = c1 ++ x ++ c2

    p a n | a > n     = surround "(" ")"
          | otherwise = id

    quote '\'' = "\\'"
    quote '\\' = "\\\\"
    quote c    = [c]

type Production = (String, RHS)
type BNF = [Production]

ppBNF :: BNF -> String
ppBNF = unlines . map (\(i,rhs) -> i ++ " = " ++ ppRHS rhs ++ ";")

Code to produce EBNF

We had a good time writing combinators that create complex parsers from primitive pieces. Let us do the same for EBNF grammars. We could simply work on the RHS type directly, but we can do something more nifty: We create a data type that keeps track, via a phantom type parameter, of what Haskell type the given EBNF syntax is the specification:

newtype Grammar a = G RHS

ppGrammar :: Grammar a -> String
ppGrammar (G rhs) = ppRHS rhs

So a value of type Grammar t is a description of the textual representation of the Haskell type t.

Here is one simple example:

anyCharG :: Grammar Char
anyCharG = G (NonTerminal "char")

Here is another one. This one does not describe any interesting Haskell type, but is useful when spelling out the special characters in the syntax described by the grammar:

charG :: Char -> Grammar ()
charG c = G (Terminal [c])

A combinator that creates new grammar from two existing grammars:

orElseG :: Grammar a -> Grammar a -> Grammar a
orElseG (G rhs1) (G rhs2) = G (Choice rhs1 rhs2)

We want the convenience of our well-known type classes in order to combine these values some more:

instance Functor Grammar where
    fmap _ (G rhs) = G rhs

instance Applicative Grammar where
    pure x = G (Terminal "")
    (G rhs1) <*> (G rhs2) = G (Sequence rhs1 rhs2)

Note how the Functor instance does not actually use the function. How should it? There are no values inside a Grammar!

We cannot define a Monad instance for Grammar: We would start with (G rhs1) >>= k = …, but there is simply no way of getting a value of type a that we can feed to k. So we will do without a Monad instance. This is interesting, and we will come back to that later.

Like with the parser, we can now begin to build on the primitive example to build more complicated combinators:

manyG :: Grammar a -> Grammar [a]
manyG p = (pure (:) <*> p <*> manyG p) `orElseG` pure []

many1G :: Grammar a -> Grammar [a]
many1G p = pure (:) <*> p <*> manyG p

sepByG :: Grammar a -> Grammar () -> Grammar [a]
sepByG p1 p2 = ((:) <$> p1 <*> (manyG (p2 *> p1))) `orElseG` pure []

Let us run a small example:

dottedWordsG :: Grammar [String]
dottedWordsG = many1G (manyG anyCharG <* charG '.')
*Main> putStrLn $ ppGrammar dottedWordsG
'', ('', char, ('', char, ('', char, ('', char, ('', char, ('', …

Oh my, that is not good. Looks like the recursion in manyG does not work well, so we need to avoid that. But anyways we want to be explicit in the EBNF grammars about where something can be repeated, so let us just make many a primitive:

manyG :: Grammar a -> Grammar [a]
manyG (G rhs) = G (Repetition rhs)

With this definition, we already get a simple grammar for dottedWordsG:

*Main> putStrLn $ ppGrammar dottedWordsG
'', {char}, '.', {{char}, '.'}

This already looks like a proper EBNF grammar. One thing that is not nice about it is that there is an empty string ('') in a sequence (…,…). We do not want that.

Why is it there in the first place? Because our Applicative instance is not lawful! Remember that pure id <*> g == g should hold. One way to achieve that is to improve the Applicative instance to optimize this case away:

instance Applicative Grammar where
    pure x = G (Terminal "")
    G (Terminal "") <*> G rhs2 = G rhs2
    G rhs1 <*> G (Terminal "") = G rhs1
    (G rhs1) <*> (G rhs2) = G (Sequence rhs1 rhs2)
	```
Now we get what we want:
*Main> putStrLn $ ppGrammar dottedWordsG
{char}, '.', {{char}, '.'}

Remember our parser for CSV files above? Let me repeat it here, this time using only Applicative combinators, i.e. avoiding (>>=), (>>), return and do-notation:

parseCSVP :: Parser [[String]]
parseCSVP = manyP parseLine
  where
    parseLine = parseCell `sepByP` charG ',' <* charP '\n'
    parseCell = charP '"' *> manyP (anyCharButP '"') <* charP '"'

And now we try to rewrite the code to produce Grammar instead of Parser. This is straightforward with the exception of anyCharButP. The parser code for that inherently monadic, and we just do not have a monad instance. So we work around the issue by making that a “primitive” grammar, i.e. introducing a non-terminal in the EBNF without a production rule – pretty much like we did for anyCharG:

primitiveG :: String -> Grammar a
primitiveG s = G (NonTerminal s)

parseCSVG :: Grammar [[String]]
parseCSVG = manyG parseLine
  where
    parseLine = parseCell `sepByG` charG ',' <* charG '\n'
    parseCell = charG '"' *> manyG (primitiveG "not-quote") <* charG '"'

Of course the names parse… are not quite right any more, but let us just leave that for now.

Here is the result:

*Main> putStrLn $ ppGrammar parseCSVG
{('"', {not-quote}, '"', {',', '"', {not-quote}, '"'} | ''), '
'}

The line break is weird. We do not really want newlines in the grammar. So let us make that primitive as well, and replace charG '\n' with newlineG:

newlineG :: Grammar ()
newlineG = primitiveG "newline"

Now we get

*Main> putStrLn $ ppGrammar parseCSVG
{('"', {not-quote}, '"', {',', '"', {not-quote}, '"'} | ''), newline}

which is nice and correct, but still not quite the easily readable EBNF that we saw further up.

Code to produce EBNF, with productions

We currently let our grammars produce only the right-hand side of one EBNF production, but really, we want to produce a RHS that may refer to other productions. So let us change the type accordingly:

newtype Grammar a = G (BNF, RHS)

runGrammer :: String -> Grammar a -> BNF
runGrammer main (G (prods, rhs)) = prods ++ [(main, rhs)]

ppGrammar :: String -> Grammar a -> String
ppGrammar main g = ppBNF $ runGrammer main g

Now we have to adjust all our primitive combinators (but not the derived ones!):

charG :: Char -> Grammar ()
charG c = G ([], Terminal [c])

anyCharG :: Grammar Char
anyCharG = G ([], NonTerminal "char")

manyG :: Grammar a -> Grammar [a]
manyG (G (prods, rhs)) = G (prods, Repetition rhs)

mergeProds :: [Production] -> [Production] -> [Production]
mergeProds prods1 prods2 = nub $ prods1 ++ prods2

orElseG :: Grammar a -> Grammar a -> Grammar a
orElseG (G (prods1, rhs1)) (G (prods2, rhs2))
    = G (mergeProds prods1 prods2, Choice rhs1 rhs2)

instance Functor Grammar where
    fmap _ (G bnf) = G bnf

instance Applicative Grammar where
    pure x = G ([], Terminal "")
    G (prods1, Terminal "") <*> G (prods2, rhs2)
        = G (mergeProds prods1 prods2, rhs2)
    G (prods1, rhs1) <*> G (prods2, Terminal "")
        = G (mergeProds prods1 prods2, rhs1)
    G (prods1, rhs1) <*> G (prods2, rhs2)
        = G (mergeProds prods1 prods2, Sequence rhs1 rhs2)

primitiveG :: String -> Grammar a
primitiveG s = G (NonTerminal s)

The use of nub when combining productions removes duplicates that might be used in different parts of the grammar. Not efficient, but good enough for now.

Did we gain anything? Not yet:

*Main> putStr $ ppGrammar "csv" (parseCSVG)
csv = {('"', {not-quote}, '"', {',', '"', {not-quote}, '"'} | ''), newline};

But we can now introduce a function that lets us tell the system where to give names to a piece of grammar:

nonTerminal :: String -> Grammar a -> Grammar a
nonTerminal name (G (prods, rhs))
  = G (prods ++ [(name, rhs)], NonTerminal name)

Ample use of this in parseCSVG yields the desired result:

parseCSVG :: Grammar [[String]]
parseCSVG = manyG parseLine
  where
    parseLine = nonTerminal "line" $
        parseCell `sepByG` charG ',' <* newline
    parseCell = nonTerminal "cell" $
        charG '"' *> manyG (primitiveG "not-quote") <* charG '"
*Main> putStr $ ppGrammar "csv" (parseCSVG)
cell = '"', {not-quote}, '"';
line = (cell, {',', cell} | ''), newline;
csv = {line};

This is great!

Unifying parsing and grammar-generating

Note how simliar parseCSVG and parseCSVP are! Would it not be great if we could implement that functionality only once, and get both a parser and a grammar description out of it? This way, the two would never be out of sync!

And surely this must be possible. The tool to reach for is of course to define a type class that abstracts over the parts where Parser and Grammer differ. So we have to identify all functions that are primitive in one of the two worlds, and turn them into type class methods. This includes char and orElse. It includes many, too: Although manyP is not primitive, manyG is. It also includes nonTerminal, which does not exist in the world of parsers (yet), but we need it for the grammars.

The primitiveG function is tricky. We use it in grammars when the code that we might use while parsing is not expressible as a grammar. So the solution is to let it take two arguments: A String, when used as a descriptive non-terminal in a grammar, and a Parser a, used in the parsing code.

Finally, the type classes that we except, Applicative (and thus Functor), are added as constraints on our type class:

class Applicative f => Descr f where
    char :: Char -> f ()
    many :: f a -> f [a]
    orElse :: f a -> f a -> f a
    primitive :: String -> Parser a -> f a
    nonTerminal :: String -> f a -> f a

The instances are easily written:

instance Descr Parser where
    char = charP
    many = manyP
    orElse = orElseP
    primitive _ p = p
    nonTerminal _ p = p

instance Descr Grammar where
    char = charG
    many = manyG
    orElse = orElseG
    primitive s _ = primitiveG s
    nonTerminal s g = nonTerminal s g

And we can now take the derived definitions, of which so far we had two copies, and define them once and for all:

many1 :: Descr f => f a -> f [a]
many1 p = pure (:) <*> p <*> many p

anyChar :: Descr f => f Char
anyChar = primitive "char" anyCharP

dottedWords :: Descr f => f [String]
dottedWords = many1 (many anyChar <* char '.')

sepBy :: Descr f => f a -> f () -> f [a]
sepBy p1 p2 = ((:) <$> p1 <*> (many (p2 *> p1))) `orElse` pure []

newline :: Descr f => f ()
newline = primitive "newline" (charP '\n')

And thus we now have our CSV parser/grammar generator:

parseCSV :: Descr f => f [[String]]
parseCSV = many parseLine
  where
    parseLine = nonTerminal "line" $
        parseCell `sepBy` char ',' <* newline
    parseCell = nonTerminal "cell" $
        char '"' *> many (primitive "not-quote" (anyCharButP '"')) <* char '"'

We can now use this definition both to parse and to generate grammars:

*Main> putStr $ ppGrammar2 "csv" (parseCSV)
cell = '"', {not-quote}, '"';
line = (cell, {',', cell} | ''), newline;
csv = {line};
*Main> parse parseCSV "\"ab\",\"cd\"\n\"\",\"de\"\n\n"
Just [["ab","cd"],["","de"],[]]

The INI file parser and grammar

As a final exercise, let us transform the INI file parser into a combined thing. Here is the parser (another artifact of last week’s homework) again using applicative style2:

parseINIP :: Parser INIFile
parseINIP = many1P parseSection
  where
    parseSection =
        (,) <$  charP '['
            <*> parseIdent
            <*  charP ']'
            <*  charP '\n'
            <*> (catMaybes <$> manyP parseLine)
    parseIdent = many1P letterOrDigitP
    parseLine = parseDecl `orElseP` parseComment `orElseP` parseEmpty

    parseDecl = Just <$> (
        (,) <*> parseIdent
            <*  manyP (charP ' ')
            <*  charP '='
            <*  manyP (charP ' ')
            <*> many1P (anyCharButP '\n')
            <*  charP '\n')

    parseComment =
        Nothing <$ charP '#'
                <* many1P (anyCharButP '\n')
                <* charP '\n'

    parseEmpty = Nothing <$ charP '\n'

Transforming that to a generic description is quite straightforward. We use primitive again to wrap letterOrDigitP:

descrINI :: Descr f => f INIFile
descrINI = many1 parseSection
  where
    parseSection =
        (,) <*  char '['
            <*> parseIdent
            <*  char ']'
            <*  newline
            <*> (catMaybes <$> many parseLine)
    parseIdent = many1 (primitive "alphanum" letterOrDigitP)
    parseLine = parseDecl `orElse` parseComment `orElse` parseEmpty

    parseDecl = Just <$> (
        (,) <*> parseIdent
            <*  many (char ' ')
            <*  char '='
            <*  many (char ' ')
            <*> many1 (primitive "non-newline" (anyCharButP '\n'))
	    <*  newline)

    parseComment =
        Nothing <$ char '#'
                <* many1 (primitive "non-newline" (anyCharButP '\n'))
		<* newline

    parseEmpty = Nothing <$ newline

This yields this not very helpful grammar (abbreviated here):

*Main> putStr $ ppGrammar2 "ini" descrINI
ini = '[', alphanum, {alphanum}, ']', newline, {alphanum, {alphanum}, {' '}…

But with a few uses of nonTerminal, we get something really nice:

descrINI :: Descr f => f INIFile
descrINI = many1 parseSection
  where
    parseSection = nonTerminal "section" $
        (,) <$  char '['
            <*> parseIdent
            <*  char ']'
            <*  newline
            <*> (catMaybes <$> many parseLine)
    parseIdent = nonTerminal "identifier" $
        many1 (primitive "alphanum" letterOrDigitP)
    parseLine = nonTerminal "line" $
        parseDecl `orElse` parseComment `orElse` parseEmpty

    parseDecl = nonTerminal "declaration" $ Just <$> (
        (,) <$> parseIdent
            <*  spaces
            <*  char '='
            <*  spaces
            <*> remainder)

    parseComment = nonTerminal "comment" $
        Nothing <$ char '#' <* remainder

    remainder = nonTerminal "line-remainder" $
        many1 (primitive "non-newline" (anyCharButP '\n')) <* newline

    parseEmpty = Nothing <$ newline

    spaces = nonTerminal "spaces" $ many (char ' ')
*Main> putStr $ ppGrammar "ini" descrINI
identifier = alphanum, {alphanum};
spaces = {' '};
line-remainder = non-newline, {non-newline}, newline;
declaration = identifier, spaces, '=', spaces, line-remainder;
comment = '#', line-remainder;
line = declaration | comment | newline;
section = '[', identifier, ']', newline, {line};
ini = section, {section};

Recursion (variant 1)

What if we want to write a parser/grammar-generator that is able to generate the following grammar, which describes terms that are additions and multiplications of natural numbers:

const = digit, {digit};
spaces = {' ' | newline};
atom = const | '(', spaces, expr, spaces, ')', spaces;
mult = atom, {spaces, '*', spaces, atom}, spaces;
plus = mult, {spaces, '+', spaces, mult}, spaces;
expr = plus;

The production of expr is recursive (via plus, mult, atom). We have seen above that simply defining a Grammar a recursively does not go well.

One solution is to add a new combinator for explicit recursion, which replaces nonTerminal in the method:

class Applicative f => Descr f where
    
    recNonTerminal :: String -> (f a -> f a) -> f a

instance Descr Parser where
    
    recNonTerminal _ p = let r = p r in r

instance Descr Grammar where
    
    recNonTerminal = recNonTerminalG

recNonTerminalG :: String -> (Grammar a -> Grammar a) -> Grammar a
recNonTerminalG name f =
    let G (prods, rhs) = f (G ([], NonTerminal name))
    in G (prods ++ [(name, rhs)], NonTerminal name)

nonTerminal :: Descr f => String -> f a -> f a
nonTerminal name p = recNonTerminal name (const p)

runGrammer :: String -> Grammar a -> BNF
runGrammer main (G (prods, NonTerminal nt)) | main == nt = prods
runGrammer main (G (prods, rhs)) = prods ++ [(main, rhs)]

The change in runGrammer avoids adding a pointless expr = expr production to the output.

This lets us define a parser/grammar-generator for the arithmetic expressions given above:

data Expr = Plus Expr Expr | Mult Expr Expr | Const Integer
    deriving Show

mkPlus :: Expr -> [Expr] -> Expr
mkPlus = foldl Plus

mkMult :: Expr -> [Expr] -> Expr
mkMult = foldl Mult

parseExpr :: Descr f => f Expr
parseExpr = recNonTerminal "expr" $ \ exp ->
    ePlus exp

ePlus :: Descr f => f Expr -> f Expr
ePlus exp = nonTerminal "plus" $
    mkPlus <$> eMult exp
           <*> many (spaces *> char '+' *> spaces *> eMult exp)
           <*  spaces

eMult :: Descr f => f Expr -> f Expr
eMult exp = nonTerminal "mult" $
    mkPlus <$> eAtom exp
           <*> many (spaces *> char '*' *> spaces *> eAtom exp)
           <*  spaces

eAtom :: Descr f => f Expr -> f Expr
eAtom exp = nonTerminal "atom" $
    aConst `orElse` eParens exp

aConst :: Descr f => f Expr
aConst = nonTerminal "const" $ Const . read <$> many1 digit

eParens :: Descr f => f a -> f a
eParens inner =
    id <$  char '('
       <*  spaces
       <*> inner
       <*  spaces
       <*  char ')'
       <*  spaces

And indeed, this works:

*Main> putStr $ ppGrammar "expr" parseExpr
const = digit, {digit};
spaces = {' ' | newline};
atom = const | '(', spaces, expr, spaces, ')', spaces;
mult = atom, {spaces, '*', spaces, atom}, spaces;
plus = mult, {spaces, '+', spaces, mult}, spaces;
expr = plus;

Recursion (variant 2)

Interestingly, there is another solution to this problem, which avoids introducing recNonTerminal and explicitly passing around the recursive call (i.e. the exp in the example). To implement that we have to adjust our Grammar type as follows:

newtype Grammar a = G ([String] -> (BNF, RHS))

The idea is that the list of strings is those non-terminals that we are currently defining. So in nonTerminal, we check if the non-terminal to be introduced is currently in the process of being defined, and then simply ignore the body. This way, the recursion is stopped automatically:

nonTerminalG :: String -> (Grammar a) -> Grammar a
nonTerminalG name (G g) = G $ \seen ->
    if name `elem` seen
    then ([], NonTerminal name)
    else let (prods, rhs) = g (name : seen)
         in (prods ++ [(name, rhs)], NonTerminal name)

After adjusting the other primitives of Grammar (including the Functor and Applicative instances, wich now again have nonTerminal) to type-check again, we observe that this parser/grammar generator for expressions, with genuine recursion, works now:

parseExp :: Descr f => f Expr
parseExp = nonTerminal "expr" $
    ePlus

ePlus :: Descr f => f Expr
ePlus = nonTerminal "plus" $
    mkPlus <$> eMult
           <*> many (spaces *> char '+' *> spaces *> eMult)
           <*  spaces

eMult :: Descr f => f Expr
eMult = nonTerminal "mult" $
    mkPlus <$> eAtom
           <*> many (spaces *> char '*' *> spaces *> eAtom)
           <*  spaces

eAtom :: Descr f => f Expr
eAtom = nonTerminal "atom" $
    aConst `orElse` eParens parseExp

Note that the recursion is only going to work if there is at least one call to nonTerminal somewhere around the recursive calls. We still cannot implement many as naively as above.

Homework

If you want to play more with this: The homework is to define a parser/grammar-generator for EBNF itself, as specified in this variant:

identifier = letter, {letter | digit | '-'};
spaces = {' ' | newline};
quoted-char = non-quote-or-backslash | '\\', '\\' | '\\', '\'';
terminal = '\'', {quoted-char}, '\'', spaces;
non-terminal = identifier, spaces;
option = '[', spaces, rhs, spaces, ']', spaces;
repetition = '{', spaces, rhs, spaces, '}', spaces;
group = '(', spaces, rhs, spaces, ')', spaces;
atom = terminal | non-terminal | option | repetition | group;
sequence = atom, {spaces, ',', spaces, atom}, spaces;
choice = sequence, {spaces, '|', spaces, sequence}, spaces;
rhs = choice;
production = identifier, spaces, '=', spaces, rhs, ';', spaces;
bnf = production, {production};

This grammar is set up so that the precedence of , and | is correctly implemented: a , b | c will parse as (a, b) | c.

In this syntax for BNF, terminal characters are quoted, i.e. inside '…', a ' is replaced by \' and a \ is replaced by \\ – this is done by the function quote in ppRHS.

If you do this, you should able to round-trip with the pretty-printer, i.e. parse back what it wrote:

*Main> let bnf1 = runGrammer "expr" parseExpr
*Main> let bnf2 = runGrammer "expr" parseBNF
*Main> let f = Data.Maybe.fromJust . parse parseBNF. ppBNF
*Main> f bnf1 == bnf1
True
*Main> f bnf2 == bnf2
True

The last line is quite meta: We are using parseBNF as a parser on the pretty-printed grammar produced from interpreting parseBNF as a grammar.

Conclusion

We have again seen an example of the excellent support for abstraction in Haskell: Being able to define so very different things such as a parser and a grammar description with the same code is great. Type classes helped us here.

Note that it was crucial that our combined parser/grammars are only able to use the methods of Applicative, and not Monad. Applicative is less powerful, so by giving less power to the user of our Descr interface, the other side, i.e. the implementation, can be more powerful.

The reason why Applicative is ok, but Monad is not, is that in Applicative, the results do not affect the shape of the computation, whereas in Monad, the whole point of the bind operator (>>=) is that the result of the computation is used to decide the next computation. And while this is perfectly fine for a parser, it just makes no sense for a grammar generator, where there simply are no values around!

We have also seen that a phantom type, namely the parameter of Grammar, can be useful, as it lets the type system make sure we do not write nonsense. For example, the type of orElseG ensures that both grammars that are combined here indeed describe something of the same type.


  1. It seems to be the week of applicative-appraising blog posts: Brent has posted a nice piece about enumerations using Applicative yesterday.

  2. I like how in this alignment of <*> and <* the > point out where the arguments are that are being passed to the function on the left.

Die Taxitür und ich

Published 2016-10-20 in sections Deutsch, Philadelphia.

Hier in Philadelphia radele ich täglich von meiner Wohnung in der Baltimore Avenue zur Uni. Praktische alle Straßen, die ich dabei nehme, haben einen explizit markierten Fahrradstreifen, so dass das im Großen und Ganzen gut geht. Aber halt nicht immer…

Die Türe öffnet sich

Ich fuhr also gerade die leicht abschüssige Spruce Street hinab, als in etwa hier ein Taxi vor mir nach rechts ausschert und den halben Fahrradstreifen blockiert. Gerade als ich an ihm vorbeifahren wollten, macht der Passagier die hintere rechte Türe auf und blockiert meinen Weg.

Ich konnte wohl noch etwas, aber nicht vollständig abbremsen. Mein Vorderrad muss noch zur Hälfte rechts an der Türe vorbeigekommen sein, bevor ich von der Kante der Türe endgültig gestoppt wurde.

Das Taxi verschwindet

Der Passagier stieg aus, erkundigte sich knapp nach meinem Wohlergehen. Nach einem schnellen Check entdeckte ich nur eine Schramme unter der linken Brust und eine Delle am linken Bremshebel, aber sonst schien alles in Ordnung und das Fahrrad sah auch gut aus. Ich sagte „I’m ok“ und er verschwand.

Der Taxifahrer machte keine Anstalten auszusteigen oder sich nach mir zu erkundigen. Entweder er war eine Weile unschlüssig und wartete ob ich mich melde, oder hat das gar nicht mitbekommen. Ich wusste nicht recht was zu tun ist und habe den Taxifahrer nicht konfrontiert (was hätte ich auch sagen sollen?), aber ich hab ein Photo von seine Nummernschild gemacht, während sich das Taxi nach ein paar Momenten (vielleicht einer halben Minute?) von dannen fuhr.

Die Uniformierten helfen

Ein Security-Mensch des Krankenhauses, vor dem sich das zugetragen hat und wohl das meiste gesehen hat, wollte wissen wie es mir geht. Ich entdeckte noch weitere Schrammen am linken Oberarm, aber nichts weiter. Alle Rippen fest am Platz, Atmen normal möglich.

Er fragte, ob er die Polizei rufen soll. Ich zögerte und druckste herum – es schien ja nichts kaputt zu sein, weder an mir noch am Fahrrad, also was soll der Terz? – aber druckste wohl zu lange, denn er sprach irgendwas in sein Funkgerät und wenige Minuten später war eine Polizistin (selbst auch per Rad unterwegs) da.

Die ausgesprochen freundliche Vertreterin der Uni-eigenen Polizei nahm meine Personalien auf und ließ sich den Tathergang beschreiben. Sie bestärkte mich darin, einen Bericht zu erstatten: Der Taxifahrer hat sich klar falsch verhalten (die Fahrradspur missachtet, nicht auf Radfahrer geachtet, weggefahren ohne zu sich zu kümmern). Sie trieb auch einen Zeugen auf, der in seinem Wagen auf dem Parkstreifen direkt hinter der Unfallstelle saß und meinen Bericht bestätigen konnte.

So hab ich jetzt eine Berichtnummer und eine Telefonnummer wo ich mich melden kann falls sich noch etwas ändert. Wenn ich innerhalb von 24 Stunden noch etwas entdecke, was kaputt ist (was ja nicht unwahrscheinlich ist, sobald das Adrenalin weg ist), wird das noch dem Unfall zugeordnet. Aber es scheint tatsächlich nicht mehr kaputt zu sein.

Nachbemerkungen

Meine Kollegen sagen, dass man hier sehr vorsichtig Fahrrad fahren muss. Manche nutzen die Fahrradspur nicht, sondern fahren immer mittig auf einer Autospur. Und nur weil Taxifahrer berufsmäßige Autofahrer sind, heißt das nicht, dass sie auch professionell fahren…

Das ist ja auch alles richtig, und ich weiß natürlich, dass ich als Radfahrer hier ein erhöhtes Risiko eingehe. Trotzdem halte ich es es für gerechtfertigt, auch wenn ich den Crash vielleicht bei anderer Fahrweise vermeiden hätte können, mir an diesem Crash keine Schuld zuzuweisen.

Und vielleicht hat die Geschichte den Effekt dass zumindest ein Taxifahrer hier in Zukunft besser auf die Fahrradspur aufpasst.

T430s → T460s

Published 2016-10-08 in sections English, Digital World.

Earlier this week, I finally got my new machine that came with my new position at the University of Pennsylvania: A shiny Thinkpad T460s that now replaces my T430s. (Yes, there is a pattern. It continues with T400 and T41p.) I decided to re-install my Debian system from scratch and copy over only the home directory – a bit of purification does not hurt. This blog post contains some random notes that might be useful to someone or alternative where I hope someone can tell me how to fix and improve things.

Installation

The installation (using debian-installer from a USB drive) went mostly smooth, including LVM on an encrypted partition. Unfortunately, it did not set up grub correctly for the UEFI system to boot, so I had to jump through some hoops (using the grub on the USB drive to manually boot into the installed system, and installing grub-efi from there) until the system actually came up.

High-resolution display

This laptop has a 2560×1440 high resolution display. Modern desktop environments like GNOME supposedly handle that quite nicely, but for reasons explained in an earlier post, I do not use a desktop envrionment but have a minimalistic setup based on Xmonad. I managed to get a decent setup now, by turning lots of manual knobs:

  • For the linux console, setting

    FONTFACE="Terminus"
    FONTSIZE="12x24"

    in /etc/default/console-setup yielded good results.

  • For the few GTK-2 applications that I am still running, I set

    gtk-font-name="Sans 16"

    in ~/.gtkrc-2.0. Similarly, for GTK-3 I have

    [Settings]
    gtk-font-name = Sans 16

    in ~/.config/gtk-3.0/settings.ini.

  • Programs like gnome-terminal, Evolution and hexchat refer to the “System default document font” and “System default monospace font”. I remember that it was possible to configure these in the GNOME control center, but I could not find any way of configuring these using command line tools, so I resorted to manually setting the font for these. With the help from Alexandre Franke I figured out that the magic incarnation here is:

    gsettings set org.gnome.desktop.interface monospace-font-name 'Monospace 16'
    gsettings set org.gnome.desktop.interface document-font-name 'Serif 16'
    gsettings set org.gnome.desktop.interface font-name 'Sans 16'
  • Firefox seemed to have picked up these settings for the UI, so that was good. To make web pages readable, I set layout.css.devPixelsPerPx to 1.5 in about:config.

  • GVim has set guifont=Monospace\ 16 in ~/.vimrc. The toolbar is tiny, but I hardly use it anyways.

  • Setting the font of Xmonad prompts requires the sytax

    , font = "xft:Sans:size=16"

    Speaking about Xmonad prompts: Check out the XMonad.Prompt.Unicode module that I have been using for years and recently submitted upstream.

  • I launch Chromium (or rather the desktop applications that I use that happen to be Chrome apps) with the parameter --force-device-scale-factor=1.5.

  • Libreoffice seems to be best configured by running xrandr --dpi 194 before hand. This seems also to be read by Firefox, doubling the effect of the font size in the gtk settings, which is annoying. Luckily I do not work with Libreoffice often, so for now I’ll just set that manually when needed.

I am not quite satisfied. I have the impression that the 16 point size font, e.g. in Evolution, is not really pretty, so I am happy to take suggestions here.

I found the ArchWiki page on HiDPI very useful here.

Trackpoint and Touchpad

One reason for me to sticking with Thinkpads is their trackpoint, which I use exclusively. In previous models, I disabled the touchpad in the BIOS, but this did not seem to have an effect here, so I added the following section to /etc/X11/xorg.conf.d/30-touchpad.conf

Section "InputClass"
        Identifier "SynPS/2 Synaptics TouchPad"
        MatchProduct "SynPS/2 Synaptics TouchPad"
        Option "ignore" "on"
EndSection

At one point I left out the MatchProduct line, disabling all input in the X server. Had to boot into recovery mode to fix that.

Unfortunately, there is something wrong with the trackpoint and the buttons: When I am moving the trackpoint (and maybe if there is actual load on the machine), mouse button press and release events sometimes get lost. This is quite annoying – I try to open a folder in Evolution and accidentially move it.

I installed the latest Kernel from Debian experimental (4.8.0-rc8), but it did not help.

I filed a bug report against libinput although I am not fully sure that that’s the culprit.

Update: According to Benjamin Tissoires it is a known firmware bug and the appropriate people are working on a work-around. Until then I am advised to keep my palm of the touchpad.

Also, I found the trackpoint too slow. I am not sure if it is simply because of the large resolution of the screen, or because some movement events are also swallowed. For now, I simply changed the speed by writing

SUBSYSTEM=="serio", DRIVERS=="psmouse", ATTRS{speed}="120"

to /etc/udev/rules.d/10-trackpoint.rules.

Brightness control

The system would not automatically react to pressing Fn-F5 and Fn-F6, which are the keys to adjust the brightness. I am unsure about how and by what software component it “should” be handled, but the solution that I found was to set

Section "Device"
        Identifier  "card0"
        Driver      "intel"
        Option      "Backlight"  "intel_backlight"
        BusID       "PCI:0:2:0"
EndSection

so that the command line tool xbacklight would work, and then use Xmonad keybinds to perform the action, just as I already do for sound control:

    , ((0, xF86XK_Sleep),       spawn "dbus-send --system --print-reply --dest=org.freedesktop.UPower /org/freedesktop/UPower org.freedesktop.UPower.Suspend")
    , ((0, xF86XK_AudioMute), spawn "ponymix toggle")
    , ((0, 0x1008ffb2 {- xF86XK_AudioMicMute -}), spawn "ponymix --source toggle")
    , ((0, xF86XK_AudioRaiseVolume), spawn "ponymix increase 5")
    , ((0, xF86XK_AudioLowerVolume), spawn "ponymix decrease 5")
    , ((shiftMask, xF86XK_AudioRaiseVolume), spawn "ponymix increase 5 --max-volume 200")
    , ((shiftMask, xF86XK_AudioLowerVolume), spawn "ponymix decrease 5")
    , ((0, xF86XK_MonBrightnessUp), spawn "xbacklight +10")
    , ((0, xF86XK_MonBrightnessDown), spawn "xbacklight -10")

The T460s does not actually have a sleep button, that line is a reminiscence from my T430s. I suspend the machine by pressing the power button now, thanks to HandlePowerKey=suspend in /etc/systemd/logind.conf.

Profile Weirdness

Something strange happend to my environment variables after the move. It is clearly not hardware related, but I simply cannot explain what has changed: All relevant files in /etc look similar enough.

I use ~/.profile to extend the PATH and set some other variables. Previously, these settings were in effect in my whole X session, which is started by lightdm with auto-login, followed by xmonad-session. I could find no better way to fix that than stating . ~/.profile early in my ~/.xmonad/xmonad-session-rc. Very strange.

Swing-Tanzen in Philadelphia

Published 2016-09-17 in sections Deutsch, Philadelphia.

Ich bin mal wieder unterwegs, diesmal auf dem Weg zur ICFP in Nara in Japan, und habe Zeit einen weiteren Bericht aus Philadelphia zu schreiben. Wie manchen versprochen erzähle ich heute, wie es mit Swing-Tanzen in Philadelphia aussieht.

Man könnte meinen ich hätte meine Wohnung strategisch günstig zum Swing-Tanzen gewählt, denn die beiden wöchentlichen Events sind in unmittelbarer Nähe:

Jazz Attack

Donnerstags findet in den Räumlichkeiten der University City Arts League Jazz Attack statt: Um 20 Uhr gibt es einen Kurs mit monatlich wechselnden Themen (im August waren es Turns, Tension und Stretch beim Charlston, jetzt im September lernen wir Balboa), stets parallel zu einer Einführung für absolute Anfänger. Einsteigen ist also jederzeit möglich. Die Kurse werden von Freiwilligen gehalten (und sind nicht ganz so lehrreich wie bei einer „richtigen“ Tanzschule). Mit 7 Dollar ist man dabei, und darf auch gleich zum Social bleiben, der von 21 bis 23 Uhr geht.

Jazz Attack

Jazz Attack

Das Gebäude ist – wie auch jenes in dem ich wohne – ein ganz normales Reihenhaus, geschätzt aus dem frühen 20. Jahrhundert. Das heißt man tanzt im 1. Stock auf schönem Parkett. Wenn im Kurs alle im gleichen Takt ihre Schritte machen, dann wackelt und rödelt die Schiebetür, und im Erdgeschoss sieht man die Decke zentimeterhoch beben und fragt sich, was da ein Statiker zu sagen würde. Aber es scheint zu halten.

Leider ist der Tanzraum nicht besonders groß, vielleicht so groß wie die reine Tanzfläche im Schlachthof in Karlsruhe, und jetzt, wo das Semester begonnen hat, wird es ziemlich voll. Die Organisatoren installieren zwar eine mobile Klimaanlage in einem der Fenster, aber gegen die Tänzer kann die nicht viel ausrichten. Immerhin gibt es gegenüber einen kleineren zweiten Raum, in dem man sich ein wenig abkühlen und auch besser unterhalten kann.

Clark Hop

Sonntags mittags von halb 1 bis halb 3 findet im Park direkt vor meiner Haustüre der kostenlose Open-Air-Social Clark Hop (ja, der im Hintergrund auf dem Titelbild der Seite bin ich) statt. Zumindest sofern das Wetter mitspielt – im August hat die Hitzewelle hier ein paar mal dafür gesorgt, dass es abgesagt werden musste.

Live-Musik im Clark Park

Live-Musik im Clark Park

In der Regel wird der kleine Beton-Platz vor der Charles-Dickens-Statue von einer Boombox beschallt, doch schon zweimal seit ich hier bin spielte eine lokale Band auf, die sich ganz nonchalant auf der Parkbank zurecht macht und für gute Musik sorgt. Der Boden ist nur mäßig zum Tanzen geeignet, und meine guten Schuhe bleiben Sonntags zu hause (Karlsruher, eure Holzinsel am ZKM ist echt was wert!).

PILE

Letzten Samstag fand der jährliche Swing-Exchange Philadelphias mit dem etwas unvorteilhaften Namen PILE statt: Workshops von 10 bis 3 Uhr, dann Wettbewerbe (an denen nur Vollzeitstudenten teilnehmen durften, ich hatte also Pause, die ich nach 4 Stunden Workshop auch brauchen konnte) und abends ein Social. Wir tanzten in der Houston Hall, einem stattlichen Gebäude der University of Pennsylvania mit schön großem Saal. Ich habe am Advanced-Workshop teilgenommen, mit zwei Lehrern aus New York, und war auch entsprechend gefordert (Twenties-Charlston – nie gemacht!), aber nicht fehl am Platz. Leider ist auch bei den neuen Figuren da das Problem, dass ich sie schnell wieder vergesse.

Advanced-Kurs bei PILE

Advanced-Kurs bei PILE

Bal Night

Jeden zweiten Freitag im Monat findet die Bal Night statt: Ort, Aufbau und Kosten wie Jazz Attack, nur dass Balboa getanzt wird. Nachdem jetzt bei Jazz Attack geschickter weise auch Balboa gelehrt wurde, kann ich mich in Zukunft öfter auf der Bal Night blicken lassen.

Blues

Diese ganzen Veranstaltungen werden vom Verein LaB (Lindy and Blues) organisiert, und so findet Montag abends in der Innenstadt Powerhouse Blues statt. Ich war bisher einmal dort, als ein Einstieg für Anfänger geboten wurde, und auch Blues macht Spaß. Weniger hektisch, mehr Improvisation. Ich werde es im Oktober wohl nochmal probieren.

Fun fact: LaB wurde von Carsie Blanton gegründet, von der man in Karlsruhe das Lied „Baby can dance“ kennt, von dem ich bis vor kurzem dachte, es wäre ein altes Lied.

Und wie ist es so?

Naja, Swing halt! Im Großen und Ganzen ist es nicht viel anders als Swing in Karlsruhe. Ein paar kleine Unterschiedegibt es:

  • Hier ist Ein-Tanz-Land. Das heißt, nachdem man mit jemandem getanzt hat und das Lied zu Ende ist, wird vielleicht noch kurz Danke gesagt und man macht sich wieder aus dem Staub. Karlsruhe ist ja tendenziell eher Zwei-Tanz-Land, wo man nach dem ersten Lied in der Regel noch ein zweites mit dem gleichen Partner tanzt.
  • Frauen fordern zwar auch hier seltener auf als Männer (soweit ich das einschätzen kann), aber trotzdem noch häufiger als in Karlsruhe.
  • Männerüberschuss (präziser: Leaderüberschuss) ist auch hier keine Seltenheit. Mist.
  • Ich vermisse die Atmosphäre des Socials im Schlachthof. Es ist einfach ein Unterschied ob 30 Tänzer ein einem schnöden Raum tanzen, und sonst nichts ist, oder ob 30 Tänzer in einem schönen Raum tanzen, in dem Tische stehen, mit einer Bar nebenan und normalen Menschen um einem herum. (Ein wenig Verklärung mag da sicher dabei sein, schließlich waren die Schlachthofsocials vor 2½ Jahren mein Einstieg ins Swingtanzen in Karlsruhe.)
  • Der Swingout wird hier deutlich mehr getanzt als in Karlsruhe (wobei das eigentlich mein Eindruck auch sonst war, wenn ich außerhalb Karlsruhes getanzt habe). Ich frage mich woran das liegt. Die Figur war lange meine Schwachstelle, und ist es immernoch, aber von mal zu mal klappt es besser.
  • Ohne Facebook geht hier gar nichts; alle Ankündigungen etc. laufen darüber. In Karlsruhe war es zwar auch so, dass ich vorwiegend wegen der Swing-Community nach vielen Jahren Verweigerung mich bei Facebook angemeldet hatte, um Mitfahrgelegenheiten und so nicht zu verpassen, aber zumindest alles „offizielle“ bekommt man über die Mailingliste mit.
  • Jam Circles gibt es für alle Geburtstage der letzten Woche (nicht nur für den Tag) und für alle auswärtigen Gäste. Gerade letzteres ist eine Tradition die ich euch in Karlsruhe sehr nahelegen will; da fühlt man sich als Gast gleich viel willkommener.
  • Es gibt in Philadelphia noch eine Swing-Szene, die sich wöchentlich weiter im Norden trifft. Anscheinend sind diese Szenen weitgehend disjunkt und dort eher ältere. In Karlsruhe sind wir da nicht so.
  • Mein Vorname ist absolut ungeeignet, um damit in den USA zu leben, und der Geräuschpegel beim Social macht es noch sinnloser, wenn ich versuche, die richtige Aussprache vorzumachen. Daher zeige ich die richtige Schreibweise und Aussprache yo-AH-kheem auf meinem Handy (per screen-message), das klappt ein wenig besser.

Ich tanze zwar weiter vorwiegend mein übliches Programm (der Fluch der Leader – man lernt auf Socials nur schwer neue Figuren), aber bis zum Jahresende wird sich sicherlich die eine oder andere neue Figur eingeschlichen haben. Sollte es in Karlsruhe wieder einen Silvesterswing geben, so stehen die Chancen gut dass ihr sie mich dort tanzen sehen könnt.

Ein Krankenhausbesuch in den USA

Published 2016-09-07 in sections Deutsch, Philadelphia.

Seit gestern morgen habe ich einen ziemlich rauen Hals und hab mich auch sonst nicht gesund gefühlt (fiebrig, Kopfweh). Heute erfahre ich von einem Kollegen, mit dem ich am Samstag gemeinsam unterwegs ist, dass er auch krank ist und „Strep“ hat, eine bakterielle Entzündung des Rachens. Da das ansteckend ist und behandelt schneller weg geht empfiehlt er mir (per Mail), einen Schnelltest zu machen.

Ich nehme das als Anlass, meine ersten Erfahrungen mit dem US-Gesundheitssystem zu machen. Über meine Anstellung an der Uni habe ich eine Krankenversicherung, die aber nur für bestimmte Ärzte und Kliniken in vollem Umfang bezahlt. Auf deren Homepage kann ich für mein Anliegen (Untersuchung mit Strep-Schnelltest) mir sagen lassen, wie viele ich dabei wohl zuschießen muss (20$) und wo ich entsprechende Ärzte finde. Die nächste Klinik, das „Presbyterian Medical Center“ ist direkt auf dem Campus und gehört zur Universität.

Ich mache mich also auf den Weg und gehe dort zur Information am Haupteingang. Der Wachmann dort lässt mich wissen, dass ich zum „Emergency Walk-In“, also der Notaufnahme, gehen muss (auch wenn das nicht gerade meinem Verständnis eines „Notfalls“ entspricht), und ein kräftiger Sicherheitsmann führt mich durch das Gebäude, zu einem Neben-Ausgang, und weißt mir da den Weg zum „Emergency Walk-In“.

Hier muss ich erst durch eine Sicherheitskontrolle mit Röntgengerät. Dann ein Empfang, wo ich ein paar Daten (Name, Social-Security-Nummer, Geburtsdatum sowie Anliegen) abgebe, und im Gegenzug ein Papierband mit Barcode für mein Handgelenk erhalte. Damit setze ich mich in den Wartebereich und warte (ein Glück dass ich eine e-Book-Lese-Programm auf mein Handy geladen habe.)

Mir fällt auf dass hier im Wartesaal außer mir nur Schwarze warten, und die meisten sehen nicht aus als ob sie gerade von einem Akademiker-Job kommen. Habe ich etwas falsch gemacht (oder zumindest anders als meine Kollegen machen würde)? Hätte ich vielleicht statt dessen einen Termin mit einem Arzt ausmachen sollen? Oder in die Sprechstunde eines HNO-Arzt gehen?

Nach 1½ Stunden werde ich von einer freundlichen Krankenschwester ausgerufen und in ein Untersuchungszimmer geführt. Sie fragt nach meinen Symptome, Medikamenten, Allergien und misst Blutdruck, Puls, Temperatur. Dann meint sie ich wäre gerade zur richtigen Zeit da und werde jetzt „fasttracked“, was wohl heißen soll, dass ich jetzt schnell behandelt werde. Sie führt mich in ein anderes Untersuchungszimmer („Super Track 3“) und lässt mich auf die Ärztin warten.

Nach einer halben Stunde kommt nicht die Ärztin, sondern eine Mitarbeiterin, die mehr Daten von mir will (Adresse, Versicherungskarte, Notfallkontakt). Während ich ihr das noch alles buchstabiere, kommt dann die Ärztin. Auch sympathisch, fragt die Symptome ab, schaut mir in die Ohren und den Rachen, hört meine Lunge ab und holt dann den Schnelltest, für den sie einen Rachenabstrich macht. Sie meint, das braucht 20 Minuten, und lässt mich im Untersuchungszimmer warten.

Hier warte ich also, lese weiter, und hole irgendwann meinen Laptop raus um diesen Text zu schreiben. Zwischendurch kam eine Mitarbeiterin und legte Aufkleber auf den Tisch. Dann kam eine Schwester und holte die Aufkleber, um damit den Test zu bekleben, und meinte das dauert nochmal eine Stunden. Dann wieder die Mitarbeiterin, die mir verkündet, dass mein Beitrag nicht 20 sondern 75 Dollar sind. Ich gebe ihr meine Bankkarte, sie geht und kommt zum Unterschreiben wieder. Ich warte weiter. Dann kommt sie nochmal und will meine Telefonnummer.

Mein Hals tut weiter weh, aber so langsam krieg ich Hunger.

Eine Stunde später kehrt die Ärztin wieder und verkündet mir ein negatives Testergebnis. Weil der Schnelltest aber nicht 100% sicher ist macht sie noch einen Abstrich für einen Labortest, dessen Ergebnisse ich in zwei Tagen bekommen kann. Sie vermutet einen Virus und will mir entsprechendes verschreiben. Ich bleibe weiter in dem Untersuchungszimmer sitzen und warte auf „the paperwork“ (den Papierkram).

Ein paar Minuten später kam der auch. Eine Schwester ging mit mir nochmal die Diagnose durch, erklärte mir die Verschreibung (Ibuprofen gegen Schmerzen bei Bedarf) und legte mir Salzwasserspülungen nah. Sie nahm sich tatsächlich Zeit und gab mir die Möglichkeit, Fragen zu stellen – an der Stelle scheint das US-System einen Vorteil gegenüber dem Deutschen zu haben, dass sich diese Zeit nimmt.

Auf meine Frage nach der Zusammensetzung der Wartenden und ob ich das „Übliche“ gemacht habe meinte sie, dass das schon richtig so ein, dass das Krankenhaus eben auch das umliegende Viertel versorgt, das wohl vorwiegend von Schwarzen bewohnt wird. Allerdings hätte ich auch, wenn ich einen Hausarzt hätte, zu dem ich bei so leichten Beschwerden gehen kann. Mit insgesamt 3½ Stunden kam ich wohl sogar schnell durch, und es können auch 6 oder 8 werden. Direkt bei einem eigenen Arzt geht das dann effizienter.

Fazit: Meine generelle Annahme, dass zum Arzt gehen meist nicht lohnt, hat sich wieder einmal bestätigt, und hier kommen noch signifiakten Kosten dazu. Die nächste Erkältung kuriere ich also eher selber aus. Aber wenn was wirklich ernsthaftes ist, weiß ich zumindest mal wo der Eingang zur Notaufnahme ist.

Update: Ich habe meine Krankenversicherung gefragt warum es so viel teurer geworden ist, und habe erfahren, dass es -- neben der Notaufnahme und Besuchen direkt beim Arzt -- hier auch das Konzept des Urgent Care Center gibt: Dort kann man ohne Anmeldung mit allen dringenden, aber nicht lebensgefährlichen Beschwerden hin, kommt in der Regel schneller durch (laut Webseite des Centers im Schnitt eine Stunde) und zahlt weniger (30$). Das hätte in meinem Fall deutlich besser gepasst. PS: Wer sich unsicher ist ob eine Schussverletzung nun „dringend“ behandelt werden muss, oder ein „Notfall“ ist, für den gibt es eine Entscheidungshilfe.

Update 2: Der Labortest ist negativ.

Update 3: Gut eine Woche nach der ganzen Aktion flattert mir eine Rechnung vom Krankenhaus über 75 Dollar ins Haus. Seltsam, weil ich hab ja vor Ort bezahlt (und mein Kontoauszug sagt das auch). Beim Kundenservice des Krankenhaus angerufen (das klingt komisch) und denen das geschilert. Die sehen die Zahlung nicht, und ich möge denen doch bitte eine Kopie des Kontoauszugs als Zahlungsbeleg schicken...

Update 4: Die Krankenversicherung verrät mir dass ihr der ganze Spaß 1393 Dollar gekostet hat. Find ich krass.

The new CIS-194

Published 2016-09-05 in sections English, Haskell.

The Haskell minicourse at the University of Pennsylvania, also known as CIS-194, has always had a reach beyond the students of Penn. At least since Brent Yorgey gave the course in 2013, who wrote extensive lecture notes and eventually put the material on Github.

This year, it is my turn to give the course. I could not resist making some changes, at least to the first few weeks: Instead of starting with a locally installed compiler, doing execises that revolve mostly around arithmetic and lists, I send my students to CodeWorld, which is a web programming environment created by Chris Smith1.

This greatly lowers the initial hurlde of having to set up the local toolchain, and is inclusive towards those who have had little expose to the command line before. Not that I do not expect my students to handle that, but it does not hurt to move that towards later in the course.

But more importantly: CodeWorld comes with a nicely designed simple API to create vector graphics, to animate these graphics and even create interactive programs. This means that instead of having to come up with yet another set of exercieses revolving around lists and numbers, I can have the students create Haskell programs that are visual. I believe that this is more motivating and stimulating, and will nudge the students to spend more time programming and thus practicing.

In fact, the goal is that in their third homework assignemnt, the students will implement a fully functional, interactive Sokoban game. And all that before talking about the built-in lists or tuples, just with higher order functions and custom datatypes. (Click on the picture above, which is part of the second weeks’s homework. You can use the arrow keys to move the figure around and press the escape key to reset the game. Boxes cannot be moved yet -- that will be part of homework 3.)

If this sounds interesting to you, and you always wanted to learn Haskell from scratch, feel free to tag along. The lecture notes should be elaborate enough to learn from that, and with the homework problems, you should be able to tell whether you have solved it yourself. Just do not publish your solutions before the due date. Let me know if you have any comments about the course so far.

Eventually, I will move to local compilation, use of the interpreter and text-based IO and then start using more of the material of previous iterations of the course, which were held by Richard Eisenberg in 2014 and by Noam Zilberstein in 2015.


  1. Chris has been very helpful in making sure CodeWorld works in a way that suits my course, thanks for that!

Explicit vertical alignment in Haskell

Published 2016-08-30 in sections English, Haskell.

Chris Done’s automatic Haskell formatter hindent is released in a new version, and getting quite a bit of deserved attention. He is polling the Haskell programmers on whether two or four spaces are the right indentation. But that is just cosmetics…

I am in principle very much in favor of automatic formatting, and I hope that a tool like hindent will eventually be better at formatting code than a human.

But it currently is not there yet. Code is literature meant to be read, and good code goes at length to be easily readable, and formatting can carry semantic information.

The Haskell syntax was (at least I get that impression) designed to allow the authors to write nicely looking, easy to understand code. One important tool here is vertical alignment of corresponding concepts on different lines. Compare

maze :: Integer -> Integer -> Integer
maze x y
| abs x > 4  || abs y > 4  = 0
| abs x == 4 || abs y == 4 = 1
| x ==  2    && y <= 0     = 1
| x ==  3    && y <= 0     = 3
| x >= -2    && y == 0     = 4
| otherwise                = 2

with

maze :: Integer -> Integer -> Integer
maze x y
| abs x > 4 || abs y > 4 = 0
| abs x == 4 || abs y == 4 = 1
| x == 2 && y <= 0 = 1
| x == 3 && y <= 0 = 3
| x >= -2 && y == 0 = 4
| otherwise = 2

The former is a quick to grasp specification, the latter (the output of hindent at the moment) is a desert of numbers and operators.

I see two ways forward:

  • Tools like hindent get improved to the point that they are able to detect such patterns, and indent it properly (which would be great, but very tricky, and probably never complete) or
  • We give the user a way to indicate intentional alignment in a non-obtrusive way that gets detected and preserved by the tool.

What could such ways be?

  • For guards, it could simply detect that within one function definitions, there are multiple | on the same column, and keep them aligned.
  • More general, one could take the approach lhs2Tex (which, IMHO, with careful input, a proportional font and with the great polytable LaTeX backend, produces the most pleasing code listings) takes. There, two spaces or more indicate an alignment point, and if two such alignment points are in the same column, their alignment is preserved – even if there are lines in between!

    With the latter approach, the code up there would be written

    maze :: Integer -> Integer -> Integer
    maze x y
    | abs x > 4   ||  abs y > 4   = 0
    | abs x == 4  ||  abs y == 4  = 1
    | x ==  2     &&  y <= 0      = 1
    | x ==  3     &&  y <= 0      = 3
    | x >= -2     &&  y == 0      = 4
    | otherwise                   = 2

    And now the intended alignment is explicit.

(This post is cross-posted on reddit.)

Update (2016-09-05) Shortly after this post, the Haskell formatter brittany gets released, which supports vertial alignment. Yay!