Swirly Mein Kopf

Wednesday, April 2. 2014

Steuerhinterziehung bei Subway?

Politik

Kürzlich war ich, wie üblich vor dem (sehr zu empfehlenden) Spieleabend in der Karlsruher Spielepyramide bei Subway essen. Heute wollte ich wissen, wie viel ich da eigentlich ausgegeben habe. Den Kassenzettel hatte ich nicht mitgenommen, aber da ich bei Subway Punkte sammle kann ich da ja problemlos nachschauen, was mich das Essen gekostet hat.

Den Eintrag „Kauf 8.59 €“ an dem Tag finde ich – allerdings am gleichen Tag auch einen Eintrag „Kaufstornierung -8.59 €“, samt entsprechendem Punkteabzug. Das Sandwich hatte ich gegessen, das Geld habe ich auch nicht mehr, also ist irgendwas faul.

Meine Vermutung ist: Steuerhinterziehung. Wie kürzlich in Der Zeit beschrieben ist es wohl unter Gastronomen zum Teil gängige Praxis, am Abend ein paar Einnahmen aus der Kasse zu löschen – weniger Einnahmen heißt weniger Steuerlast. Bevorzugt natürlich jene bei denen der Kunde den Kassenbon nicht mitgenommen hat. Nun scheint die Subway-Kasse direkt an das Punktesammelsystem angeschlossen zu sein, so dass das Stornieren auch meine Punkte gelöscht hat.

Zum einen bin ich etwas sauer: Nicht nur dass sich ja jemand auf unser aller Kosten um seine steuerlichen Pflichten drückt (sozusagen ein 100000000tel Hoeneß), mir entgehen auch noch meine sauer erfressenen Bonuspunkte!

Andererseits haben es Fast-Food-Franchisenehmer alles andere als einfach, und Subway ist hier wohl ein besonders heftiger Fall – gut möglich dass es der Händler solche Tricks nötig hat, um über die Runden zu kommen. Im Vergleich zu z.B. dem Karlsruher Freshsub haben die bei Subway ganz offensichtlich weniger zu lächeln...

Außerdem entgeht so nicht nur dem Staat ein wenig Geld, sondern auch Subway selbst, die – so schätze ich – einen Anteil des Gewinns oder gar des Umsatzes vom Franchisenehmer einfordern. Dazu passt auch dass Subway auf seiner Facebookseite sehr erpicht darauf war, in einem ähnlichen Fall genau zu erfahren, welcher Händler hier ein Storno durchgeführt hat.

Was lerne ich daraus? In Zukunft den Kassenbon mitnehmen, und wenn mir öfter die Punkte durch den Lappen gehen werde ich den Händler mal drauf ansprechen.

Wednesday, March 5. 2014

Creative use of screen-message

Digital World

I just learnt that the math and computer science student body is using screen-message to power an information screen in their room:

There are five instances of screen-message, configured to use non-standard colors and a fixed-width fonts, and controlled by the rather new remote control feature, where screen-messages repeatedly keeps reading text from standard input until a form feed character (ASCII 0x0C) comes, and displays that. The window manager ratpoison takes care of tiling the instances.

It looks quite a bit like a poor man’s version of dividuum’s great info-beamer. I was told that they also tried out info-beamer, but the Raspberry Pi was too slow and weak for that, while screen-message and ratpoison run happily on such small hardware.

Correction: Info-beamer was not tried, but rather ruled out as overkill for this task.

Monday, February 10. 2014

Personalisierte Tip-Toi-Datei als Geschenk

Digital World

Mein Neffe, gerade frisch 5 Jahre alt geworden, ist ein großer Fan der Ravensburger Tip-Toi-Bücher, und ich glaube er hat inzwischen alle für sein Alter geeignete. Wer das Konzept nicht kennt: Man kauft im Spielwarenladen (z.B. die gut sortierte Spielepyramide in Karlsruhe) recht teure Erklärbücher mit vielen Bildern und wenig Text, und dazu braucht man noch so einen dicken Stift. MIt dem kann man auf die Bildchen im Buch zeigen, und dann erzählt einem der Stift etwas. Im Stift ist ein kleiner Micro-Controller, das heißt er kann auch ein bisschen Logik – etwa: Finde alle Mäuse auf der Seite, dann sagt er einem sowas wie „Gut gemacht“ oder „Die Maus hast du schon“ oder „Das ist doch keine Maus!“. Das Video auf ravensburger.de erklärt das auch nochmal.

Zu jedem Buch gibt es auf ravensburger.de die entsprechende Datei zum Herunterladen und per USB auf den Stift kopieren. Und wer Computer-Freaks kennt weiß was jetzt passiert: Die Datei wird natürlich einmal im Hex-Editor aufgemacht...

Und nach vielen Stunden Hex-Dateien anschauen haben ein paar Leute, die sich nach und nach bei mir gemeldet haben und mitmachen wollten, und ich es letztendlich geschafft, das Dateiformat zu verstehen: Wir können die vorhandenen Dateien dekodieren und die enthaltenen Audio-Dateien als auch die zugehörige Logik, also was wann wie abgespielt wird, auslesen. Und es geht auch andersrum: Aus eigenen Audio-Aufnahmen komplett eigene GME-Dateien erstellen!

Und so gab es für meinen Neffen zum Geburtstag eine Spezial-Edition des Weltatlas-Buches, wo ich zu einigen Sachen auf den ersten beiden Seiten ihm etwas erzählt hab, mal was mir zu dem Land eingefallen ist, mal was den Ort mit unserer Familie verbindet, oder einfach nur die Geräusche eines Lastschiffes oder eines Löwen nachgemacht. Insgesamt 60 Aufnahmen, und trotzdem nur einen kleinen Teil des Buches abgedeckt – kein Wunder sind die so teuer. Beim Geburtstag kam das dann wohl gut an, wurde mir berichtet, wobei ich nicht einschätzen kann ob es nicht die anwesenden Erwachsenen (die ja eher erwarten dass sowas eigentlich nicht geht) mehr beeindruckt hat als das Geburtstagskind selbst.

Der nächste Schritt wäre jetzt, auch eigene Bücher (oder zumindest Bilder) zu erstellen. Theoretisch wären wir soweit, die optischen Codes sind verstanden, nur braucht man wohl einen etwas besseren Drucker als die die man üblicherweise zu Hause hat. Und ich selbst kanns nicht probieren, weil mir die Hardware fehlt; meine bisherigen Experimente musste ich immer durch andere testen lassen.

Du willst auch so eine GME-Datei für deine Verwandschaft erstellen? Sehr schön! Ich habe eine Anleitung (in Englisch) geschrieben; wenn dabei Probleme auftauchen, einfach nachfragen. Und wenn nicht, würde mich trotzdem sehr interessieren, was du draus gemacht hast und wie es angekommen ist.

Es gibt noch mehr zu tun, z.B. die Logik für die Spiele (also das was mit via dem Würfel unten rechts startet) dekodieren. Mithelfer sind sehr willkommen!

Sunday, January 19. 2014

Eine Woche Freizeitstress in Cambridge

So als Strohwitwer hat man ja wenig Gründe, den Feierabend einfach nur zu hause herumzusitzen, und daher habe ich meine Woche inzwischen gut mit Programm gefüllt. Die letzte Woche beispielsweise sah so aus:

Montag

Montag abends gings zu einem Tanzkurs des Cambridge Dancer’s Club, dem Tanzverein der Universität. Ich habe mich am Kurs „Ballroom and Latin Advanced“ versucht, und eigentlich war das auch mal mein Tanzniveau, aber das ist etwa 11 Jahre her... und so tat ich mich doch recht schwer. In dem Kurs ging die Zahl der Frauen und Männer auf, und so tanzte ich durchgehend mit einer vielleicht 70-jährigen Dame, die ebenso Schwierigkeiten mit den Figuren hatte, was natürlich auch nicht geholfen hat. Direkt im Anschluss war ein etwas einfacherer Kurs, in dem ich besser mithalten konnte. Hinterher habe ich gesehen dass dieser als  „DanceSport Ballroom Improvers“ deklariert ist, also für Leute die in Richtung Tanzwettbewerb gehen wollen, was ja nicht mein Ziel ist. Ich bin mir noch unschlüssig ob ich hier weiter mache, oder den Tag anders füllen will.

Dienstag

Diestag abend ist die traditionelle „Microsoft Research Interns Movie Night“, deren Organisation inzwischen bei mir gelandet ist. Diese Woche haben wir die neuste Folge der BBC-Serie „Sherlock“ im Auditorium – also mit großem Beamer und Kino-mäßigen Sesseln – geschaut; für nächste Woche ist „Gran Turino“ geplant.

Mittwoch

Mittwochs gehts stets zu einer Brettspielrunde, die ich übers Internet gefunden habe, mit einer Spielauswahl fast so groß wie beim Spieleabend in der Karlsruhe Spielepyramide, darunter sehr viele Spiele aus Deutschland, oft auch in der deutschen Ausgabe, mit einer aus dem Internet besorgten englischen Übersetzung. Zum Abschluss spielen wir immer noch eine Runde Bohnanza, wobei aus der Brechbohne dann die „Breckbean“ wird.

Donnerstag

Ich bei meinem Schüleraustausch in den USA vor 12 Jahren dort ein bisschen Swing, insbesondere Lindy Hop, getanzt, und seit dem nicht mehr. Daher war ich hoch erfreut zu sehen, dass hier gerade wieder ein Kurs beginnt: Diesmal nicht von der Universität aus, sondern von Cambs and Beds Lindy Experience, die in der Village Hall von Grantchester (da wo die berühmten Cambridger Auen sind) erst Lindy Hop und dann Balboa lehren. Von Lindy Hop hab ich sogar noch einen kleinen Rest im motorischen Gedächtnis, welches mir aber beim Balboa Schwierigkeiten macht: Der Tanz ähnelt oberflächlich dem Disco Fox, das heißt wenn ich auf die Füße achte, mache ich plötzlich Disco-Fox-Figuren (und verwirre meine Tanzpartnerin), und wenn ich auf die Figuren achte machen die Füße Mist. Da hilft wohl nur üben...

Freitag

Freitags kann ich dann üben, allerdings wiederum Latein- und Standardtanz, beim freien Tanzen in der Cafeteria des University Centers. Diese Woche mit dem unerfreulichen Zusatzprogramm „Fahrradschieben“, weil sich ein Glassplitter in den Reifen gebohrt hat. Aber ich bin hier ja ein verwöhnter Leihfahrradfahrer und hab das Rad also auf dem Rückweg beim Fahrradladen am Bahnhof (soweit sehr zu empfehlen!) angeschlossen, den Schlüssel mit einer kleinen Notiz in den Briefkasten geworfen und am nächsten Morgen frisch repariert und gewartet abholen können – daran könnte man sich gewöhnen.

Samstag

Samstags hab ich noch nichts wöchentlich regelmäßiges; diese Woche war ein Brettspieletag in Ely (etwa 40 Auto-Minuten nördlich von Cambrige), mit noch mehr neuen Brettspielen. Dort wurde ich auch auf yucata.de hingewiesen, ein Portal, in dem man viele Brettspiele kostenlos und asynchron, also ohne ständig online zu sein, spielen kann. Das wäre die ideale Plattform für meine eigenen Versuche, Brettspiele umzusetzten (zuletzt meine Adaption von Sim Salim als Sum Serum), doch leider ist mir die technische Umsetzung mit .NET und anderen Microsoft-Produkten doch zu fremd – was hab ich denn schon mit Microsoft am Hut?

Sonntag

Aber eigentlich brauch ich ja auch nicht unbedingt mehr Projekte, meine aktuellen langen ja auch um den Sonntag gut zu füllen. Z.B. in dem ich diesen Blogeintrag schreiben. Aber zur Zeit beschäftigt mich allerdings vor allem das Tip-Toi-Reverse-Engineering, bei dem wir inzwischen in der Lage, nicht nur die Audio-Daten der Tip-Toi-Dateien zu extrahieren, sondern sogar solche Dateien mit komplett eigenen Töne und Spiellogiken für existierende Bücher zu erstellen. Und wenn ich das richtig sehe dann scheitert das basteln von eigenen Büchern nur an der meist zu geringen Auflösung von haushaltsüblichen Druckern.

Kleines PS für die Karlsruher: Wenn ihr das Uni-Kino AFK gut fandet, überlegt doch ob ihr auch deren Crowdfunding-Kampagne unterstützen wollt!

Sunday, December 29. 2013

Sim Serim as a browser game

Digital World

Recently, I gave the very elegant board game “Sim Serim” away as a present, without actually playing it, leaving me curious about the game. One can easily play it on paper (you just need a paper, and 4 tokens like coins for each player, BoardGameGeek has English rules the of game), but I took this as an opportunity to learn more about HTML5 canvas and nodejs, and so I created the browser game “Sum Serum”, implementing the game mechanics of “Sim Serim”. You can play it locally with two people, or over the network. Contributions are welcome! Especially slicker graphics...

In other news, given that in recent years I became one, I’m on BoardGameGeek myself now, see my profile there.

Friday, December 20. 2013

My contribution to XKCD’s #949 is not needed

Digital World

A few hours ago I posted about share-file, a small tool to make a local file available at a public URL so that it is transferred from my machine, without being stored at some central server. I wanted to create something like FileTea, but usable from the command line.

My post made it to HackerNews (which brought my server to its knees for a while; let’s say I had the opportunity to find out what setting for apache’s MaxClient option works on my machine...), where the comments (besides some misunderstanding about the notable features of share-file) contained interesting links related to solving #949:

  • First of all, James Brechin implemented a command line client for FileTea. It is not clear to me whether he created it in response to my posting, or whether it lay around for a while, but I don’t care: It does precisely what I need, making share-file obsolete for me. Lazyweb works!
  • There is a service very similar to FileTea, but seemingly developed independently, at https://fipelines.org. It seems that this task is best solved using unorthodox programming language choices; while FileTea uses C and glib (not common in web applications), fipes, the software behind fipelines, is implemented in Erlang.
  • The new and shiny thing for peer-to-peer communication without additional software is WebRTC, which only needs a modern browser, and there is a chat- and file-transfer program at https://rtccopy.com/. I did not test how well it handles the case where both sides are behind a NAT, though, and sending a ready-to-use link is still simpler for the other side.
  • I found another WebRTC-based tool that focuses on sharing files only, and where users who have downloaded a file will, as long as their browser tab is open, help uploading it –  a bit like Bittorrent. So if you need to share a file with many people (all of which are using up-to-date non-IE browsers), sharefest is worth a try.

Thursday, December 19. 2013

My contribution to XKCD’s #949

Digital World

Randall Munroe rightly put shame on all the geeks in the world when he pointed out that transferring files over the internet is still an unsolved problem.

I am a big fan of FileTea’s approach to transferring files, where they are streamed from browser to browser, without registration and without being stored on some central server, and where closing the browser tab reliably cleans up the transfer. But I wanted something that works from the command line, so I created a small tool called share-file that will use SSH port forwarding to serve the files from a local, embedded web server at a publicly available port, as shown in these screenshots:

It works without additional dependencies (but better with python-magic installed) and requires a publicly available SSH server configured with GatewayPorts clientspecified. For more details, see the README, and to try it out, simply fetch it with git clone git://git.nomeata.de/share-file.git.

BTW, if someone implements a command line client for FileTea, I’ll happily dump share-file for it.

Sunday, December 1. 2013

Eine Geschichte über Heizungen in Großbritannien

Am Mittwoch nach der Arbeit kam ich nach hause und hörte so ein nerviges Piepen. Meine erste Vermutung war, dass einer der vielen Rauchmelder sich beschwert, dass seine Batterie leer geht. Das Piepen kam aus dem kleinen Zimmer, in dem ich die ersten zwei Nächte wohnte, und es war dann auch tatsächlich ein Melder, aber kein Rauchmelder, sondern ein der Kohlenmonoxidmelder, der unter dem Heizungs-Boiler liegt. Allerdings beschwerte der sich nicht über Kohlenmonoxid, sondern über das Wasser, das kräftig auf ihn drauf tropfte.

Ich hab ihn erstmal abgetrocknet und dann die Batterien rausgenommen, um meinen Ohren eine kleine Pause gönnen zu können. Kurz drauf stellte ich fest dass alle Steckdosen im Haus keinen Strom hatten (die Lichte allerdings gingen). Leider wusste ich nicht wo die Sicherungen sind, ging also erstmal einkaufen und wartete auf meinen Mitbewohner.

Der stellte dann fest, dass wenn man die Sicherung reinmachte, sie gleich wieder raussprang. Das ging so lange so bis wir den Boiler komplett vom Strom trennten – der hat sich wohl selbst einen Kurzschluss verpasst.

Mein Mitbewohner telefonierte dann mit dem Vermieter, der telefonierte dann mit British Gas und brachte die dazu, am gleichen Abend noch einen Techniker zu schicken (wozu er wohl etwas dick auftragen musste und behauptete, der Strom würde gar nicht mehr tun). Und entgegen allen Unkenrufen meiner Mitbewohner und der mittwöchlichen Brettspielrunde, dass man sich bei British Gas keine große Hoffnungen machen muss, kam dann auch ein Techniker. Der stellte dann größere Schäden am Boiler fest, für die erstmal Ersatzteile besorgt werden müssen – bis Freitag bleibt die Heizung kalt.

Ich hab mir zwar inzwischen die dickste Decke gekauft gehabt, die es im Sainsbury gab, aber die Nächte waren doch recht frostelig.

Am Freitag war ich dann von uns vier Mitbewohnern (der fünfte ist ja praktisch nicht existent) wohl der mit den flexibelsten Arbeitszeiten und dem gutmütigsten Chef, so dass ich vormittags zu hause blieb und um 10 Uhr einen freundlichen Menschen von Britisch Gas empfing und mit Tee versorgte, während der – laut über das alte Gerät schimpfend, das wohl schon längst ausgetauscht gehörte – den Boiler wieder instand setzte.

Passend dazu übrigens ein Artikel in der neusten Zeit (leider noch nicht online) über das Verhältnis der Briten zum Heizen, den ich nun voll bestätigen kann – dass ich hier doppelt verglaste Fenster hab muss man schon als Glück bezeichnen.

An der Stelle interessant: Trotz der unglaublich schlechten Isolation der britischen Häuser und deren Einstellung zur Heizeffizienz produzieren wir in Deutschland mehr CO₂ pro Nase. Was vermutlich daran liegt dass die Briten vor einer Weile weitgehend auf ihren industriellen Sektor verzichtet haben.

Thursday, November 21. 2013

Meine erste Woche in Cambridge

Vor sieben Tagen bin ich nach einer längeren und relativ ereignislosen Zugfahrt über Köln, Brüssel und London hier in Cambridge angekommen, und so langsam wird es Zeit für einen kleinen Bericht. Ich versuche mal das Erzählenswerte thematisch zu sortieren.

Meine Unterkunft

Ich hatte mich schon vor einigen Wochen nach Zimmern umgeschaut und dann über die Wohnungsvermittlungswebsite der Universität ein Zimmer gefunden. Es ist eines der typischen britischen Reihenhäuser, für mich sehr geschickt gelegen (direkt neben einem großen Supermarkt, und Bahnhof und Microsoft Research in weniger als 10 Minuten mit dem Fahrrad zu erreichen). Ich teile es mir mit vier Master- und Ph.D. Studenten aus England, Deutschland und irgendwo her (jenen sieht man auch praktisch nie), und komme soweit mit allen gut zurecht, inkl. gemeinsam Essen bestellen und XBox zocken. Die Sauberkeit entspricht etwa dem, was ich aus der Insterburg gewohnt bin.

Mein erster Eindruck des Zimmers war nicht so gut: Klein, ein Fenster zur Straße hin, das zum vernünftig Lüften zu klein ist (was man roch) und vor allem der war darin – gut versteckt – der Kessel der Gasheizung, der laufend geräuschvoll ansprang. Aber man gewöhnt sich an vieles...

Muss man aber nicht: Zwei Tage später war ein Mitbewohner etwas verwirrt als ich meinte dass ich auf Grund der Beschreibung und dem Bild auf der Wohnungsvermittlungsseite dachte dass ich in das Zimmer ziehe das die Frau bewohnt hat, die vor mir hier im Haus gewohnt hat. Aber die wohnte nicht in dem Zimmer in dem ich wohnte, als ich einzog, sondern in dem Zimmer, in dem da der andere Mitbewohner wohnte, welcher ursprünglich im kleinen Zimmer wohnte. Alles klar soweit? Der war dann überrascht dass ich dachte dass ich das Zimmer bekomme in dem er zu dem Zeitpunkt wohnt, fand es aber schon komisch dass ob für das kleinere Zimmer die Miete des größeren zahlen solle (immerhin 50£ Unterschied).

Ich hatte zwar gedacht, dass das alles so seine Richtigkeit hat – schließlich hat die Vermieterin einem Bekannten von mir, der in Cambridge wohnt und den ich zur Zimmerbesichtigung in die Brooks Rd schickte, auch schon das kleine Zimmer gezeigt. Andererseits war ich mir sicher dass die Zimmerbeschreibung, die ich gelesen hatte, nur auf das größere Zimmer passt.

Er fragte dann bei der Vermieterin nach, was denn nun Sache sei und tatsächlich: Ich sollte das größere Zimmer bekommen. Es war also alles nur ein Missverständnis (wenn auch ein vielleicht billigend in Kauf genommenes – wer weiß). Also flugs Zimmer getauscht und nun habe ich ein größeres Fenster, Blick auf den Garten und kein Heizungskessel neben dem Bett.

Ganz toll ist das Zimmer aber trotzdem nicht (wobei da die anderen nicht besser sein werden): Nachts wird die Heizung abgestellt und da wurde es schon arg kalt, so dass ich vorgestern um halb 5 aufwachte und frierend nicht mehr einschlafen konnte, bis ich dann einen dicken Pulli angezogen hab. Aber gerade komme ich vom Sainsbury mit der dicksten Decke, die sie hatten, zurück; damit sollte auch das klappen.

Ansonsten ist das Haus auf einem Stand wie man ihn erwartet, wenn man ein eher günstiges Zimmer in guter Lage erwischt (und dafür wohl wieder ganz gut). Die Dusche läuft warm, aber wenig, Küchengeräte etc. sind vorhanden (der Geschirrspüler ist kaputt), und dass ich meinen Rasierer im Bad nur mit Verlängerungskabel verwenden kann ist wohl in ganz England so – 230V-Steckdosen sind hier in Bädern verboten.

Ich hab ein paar Bilder von Zimmern und Haus hochgeladen.

Fahrrad

Da ich mein Laptop mitgebracht hatte war das das nächst wichtigste, was ich noch brauchte, ein Fahrrad. Hier hab ich mir den Luxus eines Mietrads gegönnt, statt lange nach günstigen gebrauchten zum Kaufen und Wiederverkaufen zu suchen – insbesondere da, was ich später erfuhr, Microsoft Research die Kosten übernimmt. Das Rad hat Bremsen, Stecklichter und ein Schloss und fährt sich sehr gut, so dass es eine Freude ist, damit über die weitgehend flachen Straßen von Cambridge zu düsen. Mit dem Linksverkehr klappt es soweit auch ganz gut, lediglich in Situationen wie z.B. beim Ausweichen auf Radwegen muss ich gut aufpassen.

Essen

Fast wie zu Hause: Abendbrot mit Käse und Salami (das Brot kann mit unserem natürlich nicht mithalten, aber für eine Weile tuts es), Mittags in der Kantine (sowohl preislich als qualitativ mit dem MRI in Karlsruhe zu vergleichen), nur zum Frühstück gehe ich mit der britischen Kultur auf Tuchfühlung und bin auf Porridge, also Haferbrei, umgestiegen.

Ich hatte eigentlich schon erwartet dass man bei Microsoft Research Zugriff auf einen Snacks oder zumindest frisches Obst hat, und Getränke gibt es ja schließlich auch kostenlos, aber dem ist nicht so. Also musste ich mir selber helfen und einen Karottenvorrat im Bürokühlschrank anlegen.

Arbeitsplatz

Microsoft Research hat seine Cambridger Niederlassung in einem niegelnagelneuen Haus in der Station Road (auch hier hab ich ein paar Bilder für euch), entsprechend schick und modern ist das Gebäude: Ein heller Lichthof, viele Wände aus Glas oder (um die Büros herum) Milchglas, die gleichzeitig als Tafelflächen dienen, eine schöne Dachterrasse mit weitem Blick (leider dafür die falsche Jahrszeit). Die Büros selbst, auch von so Persönlichkeiten wie Tony Hoare, sind eher klein, verglichen mit was man von der Uni Karlsruhe kennt, aber immerhin mit schönem Ausblick. Die Interns bekommen nur einen Schreibtisch in der „Open Work Area“ mit Blick in den Lichthof, wo man den Interns auf der anderen Seite beim Arbeiten zuschauen kann. Hier vermisse ich den augenentspannenden Blick in die Ferne, gerade wenn man den ganzen Tag auf seinen Laptop starrt.

Ich hatte ein bisschen Kontakt mit anderen Interns und am Dienstag Abend wurde eine Intern-Movie-Night veranstaltet, was dann hieß dass wir uns zu Viert im großen Auditorium des Gebäudes, was schon einen gewissen Kino-Charakter hat, „Clockwork Orange“ anschauten. Für mich war der Film sicherlich eine gute Einführung in Britische Umgangsformen.

Handy

Ich wollte gut vorbereitet sein und bestellte mir eine SIM-Karte noch von Deutschland aus. Der (deutlich!) günstige Prepaid-Tarif war von 3 (was ein unglaublich generischer Name für eine Firma ist), und die Karte war dann auch am Freitag Abend auf dem Tisch im zu dem Zeitpunkt meinem Zimmer. Nur ist mein Handy (ein Siemens S35) leider leider zu alt für diese Art von SIM-Karte; da muss es schon ein 3G-Handy sein. Ich vermute dass das das Geschäftsmodell ist: An Leuten die nur Telefonieren werden sie mit 2p pro Minute nicht viel verdienen, und so hoffen sie wohl darauf, dass die Leute mit ihren Smartphones viel Daten verbraten. Ergo wollen sie Kunden ohne Smartphone gar nicht haben. Ich habe mir inzwischen eine andere SIM-Karte bestellt, die bald eintreffen sollte; die 10£ Guthaben für 3, die ich gekauft hatte, hatte ich noch nicht eingelöst und konnte ich zum Glück weiterverkaufen.

Cambridge selbst

...habe ich noch gar nicht gesehen. Am Wochenende war eine Debian-Mini-Konferenz in den Räumlichkeiten von ARM, und sonst war ich tagsüber schön brav arbeiten. Die touristische Erkundung der Stadt ist für dieses Wochenende geplant.

Sunday, November 17. 2013

Breaking News: Debian TC leaked decision on init system

Debian

According to the German news page “heisse news”, the Debian Technical Committee has made a decision on the question about the default init system in Debian: There will be none!

Instead, according to Ian “Vorlon” Bart, Debian will start to distribute a suspend-to-disk image to their users, with all daemons already started, completely eradicating the need for an init system. If you are able to read German, read all about it at Debian Technical Committee entscheidet sich gegen ein Init-System

Wednesday, November 13. 2013

Constructing a list in a Monad

Haskell

In Haskell, lists are ubiquitous. In real-world Haskell, monads are ubiquitous. So it should be an easy task to fill a list with values obtained in a monad, i.e. a list of n random numbers (in the Rand monad), or getting some input from the user, and storing it in a list, until the user chooses to finish the input.

The task

For now, assume a function getInput :: IO Int; we want to run it 10000 and then have the list of the values returned. Sounds simple and straight forward, but it is actually really hard to get the run-time behaviour that we naively and optimistically expect.

The expectation

In an imperative setting, we would have a simple counting loop. In the loop, we run getInput, allocate a new cell for the linked list, and append it to the list. Clearly, this

  • consumes no stack space and
  • at the end of the loop, the list is already fully evaluated in memory, ready to be used.

Can we achieve that with Haskell? Let’s look at a few alternatives (complete code available)

Attempt 1: The accumulator

I’ll start with the probably worst attempt. Unfortunately, from what I have seen from correcting Haskell exams, this is what beginners would write, especially if they have the above imperative algorithm in mind, and know about the “convert loops to recursion with accumulators” approach to solving Haskell problems:

accumAppend :: Int -> IO [Int]
accumAppend n = go n []
  where
    go 0 l = return l
    go n l = do {x <- getInput; go (n-1) (l++[x])}

To check the space usage of this, I pass -Kn to the GHC runtime and see what limit is just enough to let this program calculate accumAppend 10000 and fully evaluate the resulting list. It turns out that we need 328336 bytes of stack space.

So what about the second requirement; that the list is fully evaluated? Experienced Haskellers see it immediatelly: The accumulator is not used in the loop, so each iteration adds a thunk around the previous value, that would add the next entry to the end. Only when the list is actually used, these are run, each traversing the whole list, causing quadratic cost. We can verify this using ghc-vis:

Clearly (and not surprisingly) this is not the best solution.

Attempt 2: The accumulator (forced)

Lets try to fix the second issue, by making sure that the list is always fully evaluated. We import Control.DeepSeq and write

accumAppendSeq :: Int -> IO [Int]
accumAppendSeq n = go n []
  where
    go 0 l = return l
    go n l = do {x <- getInput ; go (n-1) $!! (l++[x])}

As the accumulator gets fully evaluated before being passed to the next invocation of go, the result will not contain thunks. But note that this has also fixed the stack consumption: The code now runs the smallest setting for -K, 8 bytes. This works as both go and deepseq are tail-recursive.

But this is still not the solution we are looking for, as the quadradic cost caused by using ++ is still there.

Attempt 3: The accumulator (reversed)

Since we know that l++[x] is expensive, but x:l is cheap, we can simply use this to update the accumulator. This has the slightly annoying consequence that the entries of the list are in the reverse order, but we can fix that in the base case:

accumReverse :: Int -> IO [Int]
accumReverse n = go n []
  where
    go 0 l = return (reverse l)
    go n l = do {x <- getInput ; go (n-1) (x:l)}

And indeed, we get noticably faster code that still runs in 8 bytes of stack. Unfortunately, we still don’t construct the final list directly.

Attempt 4: Naive recursion

Maybe we can do without an accumulator. The most naive such code would be

listRecurse :: Int -> IO [Int]
listRecurse n = go n
  where
    go 0 = return []
    go n = do {x <- getInput; r <- go (n-1); return (x:r)}

and I’d expect that most experienced Haskellers would write that code (if they are asked not to use a library function). And indeed, this code does create the final list directly. But it requires a large stack or 164616 bytes. The reason is that this is no longer tail recursive: After calling go again we need to take the result and prepend x

Attempt 5: library functions

Maybe we should simply not worry about the implementation, and use library functions? Clearly, the authors of such libraries have found the best solution. So how does

listReplicateM :: Int -> IO [Int]
listReplicateM n = Control.Monad.replicateM n getInput

fare? Unfortunately, not better than the naive recursion. In fact, the stack space requirement is the same 164616 bytes. The same holds when using special libraries for generating and consuming list, e.g. the Streams module from the vector package:

listStreams :: Int -> IO [Int]
listStreams n = MStream.toList $ MStream.replicateM n getInput

Attempt 6: Difference lists

It is time to dig deeper into our box of tricks. What if we have lists with constant time Snoc (a.k.a. appending a new element)? Then Attempt 3 would not require reversing the list. Such lists are provided by difference lists; there are libraries for that, but we can simply implement them using lambdas:

accumDList :: Int -> IO [Int]
accumDList n = go n id
  where
    go 0 l = return (l [])
    go n l = do {x <- getInput; go (n-1) (l . (x:))}

Indeed, no stack is required (8 bytes are enough). But we are cheating here: We are still not constructing the final list, but rather we combine functions that append elements to lists. So when accumDList returns, what we have in memory, is a thunk and sequence of partial function applications in the wrong order, and evaluating the thunk does basically the same thing as reverse in Attempt 3. It might be a bit faster, is still not satisfying enough:

Attempt 7: Unsafe functions

Even deepter in the box of tricks, somewhere in the grit and dust where one usually should not reach, there is a function that can help us out here: unsafeInterleaveIO. This allow us to modify the naive recursion in a way that first creates the Cons-cell, and then continues the loop:

listUnsafeInterleave :: Int -> IO [Int]
listUnsafeInterleave n = do {l <- go n; return $!! l}
  where
    go 0 = return []
    go n = do x <- getInput
              r <- unsafeInterleaveIO (go (n-1))
              return (x:r)

The stack consumption is 8 bytes. It is worth noting that the all to deepseq (in $!!) will actually drive the evaluation of go. Also, it guarantees that the unsafe effects of unsafeInterleaveIO are confined to the execution of listUnsafeInterleave, i.e. are actually safe.

 Run time statistics

I ran criterion over the functions (generating lists of length 1000), and found these results:

  • accumAppend: 6.5 ms
  • accumAppendSeq: 8.2 ms
  • accumReverse: 14.0 us
  • listRecurse: 8.0 us (same as listReplicateM and listStreams)
  • accumDList: 12.0 us
  • listUnsafeInterleave: 174.0 us

Conclusion

There are many ways to write a list-constructing list in Haskell, none are perfect – they either fill the heap, or do not construct the list directly (usually requiring a second pass through it), or rely on IO-specific unsafe functions. The naive recursion performs the best, but may cause a stack overflow (note, though that from GHC 7.8, the stack will be unlimited).  The next best option seems to be the difference lists

I’m still wondering: What would be required from Haskell, GHC or the monads in question to have a fully satisfactory solution here, i.e. one that is as fast as the naive recursion, as stack efficient as the difference list solution, and allocates no thunks, only list cells?

Wednesday, October 23. 2013

First citation

Just found out that I was cited academically for the first time: Pablo Buiras and Alejandro Russo’s paper “Lazy Programs Leak Secrets” at NordSec2013 builds upon my work “dup – Explicit un-sharing in Haskell”, which I had submitted to last year’s Haskell symposium and Haskell Implementers Workshop, but eventually only published on arXiv.

Saturday, October 5. 2013

Why PVP is better than no PVP

Haskell

This is a reply to Roman Cheplyaka’s post “Why PVP doesn't work”, where he argues that Haskell packages should not per default put upper bounds on their build dependencies (as mandated by the Package Versioning Policy), at least not without good reason.

I disagree, and I’d like to explain why. I assume that you are packaging your libraries and programs not only for your fellow developers, but also for users. Hackage has turned not only into a hub for developers sharing their libraries, but also for users to conveniently download stuff from. And when I say users, I include xmonad users (although they write a bit of Haskell for their configuration) and beginners (who we certainly don’t expect to understand and make sense of error messages that occur if some obscure crypto-related dependency of their favourite web framework fails to build). And for their benefit we should try hard to make sure “cabal install” either succeeds (great) or fails early with an error message that the user can understand as “I could  not find a package configuration of which the maintainers believe with good confidence that it works. Please talk to them.”

I speak with some experience, because as a maintainer of the >666 Haskell packages in Debian, I am, in a sense, a very heavy user. In the years after the PVP got commonly accepted, we could noticeably reduce the number of build failures that we encounter on our machines and the Debian build farms, simply because the meta data (which we transfer to the Debian package level) prevented such builds from being attempted. We now even have a build compatibility prediction system: We maintain a text file with all Haskell packages in Debian, together with a directory of patches (where we sometimes indeed override the packages’ Cabal file), and a script that runs cabal-install’s dependency checker against this day. This way, when I want to upgrade a package, I can simply change the version in the file and know what packages will be broken. So I change their version until I either find a fixed-point (and only then actually upload packages to the user) or find a problem, which I then report to the maintainers or start cooking up my own patches.

This works really well, but it only does because most maintainers are following the PVP. That’s why I argue: Please continue to do so.

(What we would probably need instead of less using the PVP is more tools in helping us with it. I could imagine a build bot that finds packages on Hackage with an upper bound on a package where a newer version exists, fetches those and automatically tries to build against the new version, and if it succeeds, sends a message to the maintainer: “Your dependency on bar in foo also builds against version 0.42 of bar; please check for incompatibilities that are not expressed in the type system and upload a new version of foo allowing  bar-0.42.” Isn’t that something the Stackage infrastructure can be used for?)

(What we could probably use as well (and is probably a stepping stone towards what I just said) is a way to tell cabal-install to ignore a certain build dependency version bound. This way we still prevent normal users from trying a dependency version that the maintainer did not test, but nevertheless make it as easy as possible for the advanced user to try nevertheless, and then hopefully report about it to the maintainer. Of course, other had that idea before, someone just has to make it happen.)

Thursday, October 3. 2013

Experimenting with the TI eZ430 Chronos

Digital World

For a while I have been eyeing with the TI eZ430 Chronos watch, a slightly bulky “sports watch” that not only comes with a built-in thermometer, barometer and accelerometer, but also a freely programmable micro controller (from the TI MSP430 family – hence the name). In addition it has a small radio chip included and can communicate wirelessly with the computer, or possibly other devices. All in all, a very geeky toy.

A week ago I managed to buy one quite cheaply via eBay (30€ including shipping). It took me a while to get an overview of the various resources about the device. Here is what I have learned.

  • Hardware: I have the new edition (the included debug board and wireless access point are white). This means that I cannot update the software of the watch via the wireless connection, and it means that most software written for it does not support the new altimeter sensor (yet).
  • Development: Debian is a very suitable development platform; the packages mspdebug and gcc-msp430 provide all I need to compile (make config && make) and upload (mspdebug rf2500 "prog ../foo.txt") new software.
  • Code: Besides the original software that comes with the device (which supports the new hardware), there are two main lines of community-driven developments: OpenChronos and openchronos-ng. The former is (as the name suggests) older and maintained mostly by forks in various places. The latter is newer, its UI deviates further from the original software and seems to be slightly more active.
  • Communication: Both of these have their own mailinglists (openchronos, where I did not get a reply yet, and ti-chronos-development, where my messages are still waiting for moderation). I found only one IRC channel, #openchronos on freenode, with similarly little activity.

After I found that out, I tried to hack a bit on the various software. The first issue I had (and still have) is that I cannot use the buttons of the device while it is attached to the debug board. They do work if forget to take out the battery, but supposedly that is bad for the battery. So my compile-upload-test-cycle becomes a compile-upload-detach-insert-battery-test-remove-battery-attach-cycle. I could not find out how to emulate button presses using mspdebug. Any suggestions are welcome.

The other problem was the new altimeter hardware: Neither OpenChronos nor openchronos-ng support that yet. I originally planned to port the driver from the official software to a random OpenChronos fork when I read that Richard Rondu did that to openchronos-ng yet. I found the code in a month-old merge-request.

I tried it, it worked, and I started to clean up the code a bit and add a variometer mode to it, e.g. displaying the current rate of climb – my ultimate goal is to use this as a surprisingly cheap variometer for paragliding. After a day of hacking and quickly lifting the watch from the room floor to the room ceiling and back I believe that it works okish, although quite a few parameter can benefit from more tweaking: sample rate (currently 20Hz), length of history (currently 2s) and the linear regression method (currently simply the difference between the average of the samples of the current second with the samples of the last second). As always, patches welcome, the code is in my fork on sf.net.

Next to do would be to enable some buzzing noise depending on the rate of change; during flight I don’t want to decipher a low-contract LCD screen. But it is questionable whether the buzzer is loud enough – we’ll see. I was also happy to hear that there are other zE430-hackers in Karlsruhe, one of them for example tries to make the alarm clock sleep-cycle-aware.

Sunday, September 29. 2013

Heidelberg Laureates Forum 2013

Mathe

During the last week I was attending the first Heidelberg Laureates Forum as one of the lucky 200 accepted young scientists. The HFL is a (from now on hopefully yearly) event that brings together Fields Medalists, Abel Prize laureates and Turing Award winners with young scientists (undergraduates, Ph.D. students and postdocs) from both fields in the city of Heidelberg. The extremely well organized week consisted of lectures from the laureates, some workshops held by postdocs, excursions and plenty of good food. Videos of the lectures are available (but don’t work on Linux, at least not for me ☹), and I have shot a few pictures of the event as well. I believe that my favourite lectures where Michael Atiyah’s “Advice to a Young Mathematician”, Vladimir Voevodsky’s “Univalent Foundations of Mathematics”, William Morton Kahan’s “Desperately Needed Remedies for the Undebuggability of Large-Scale Floating-Point Computations in Science and Engineering” and Alan Kay’s “Putting Turing to Work”.

Where are all the functional programmers?

During that event, one gets to talk to many other math and computer scientists researchers; sometimes just “Where are you from?” and “What do you do?”, sometimes long discussions. Unfortunately, I hardly found one who is into functional programming language research – is that only because the event was parallel to ICFP (which I really would have liked to attend as well), or is functional programming really just about 1% of all computer science?

What is a proof?

My other research interest lies in interactive theorem proving, especially using Isabelle. Of course that is a topic that one can discuss with almost everyone at that event, including the mathematicians. The reactions were rather mixed: On the one end of the spectrum, some mathematicians seriously doubt that they would ever trust a computer to check proofs and that it would ever be efficient enough to use. Others would not mind having “a button that tells whether their paper written in LaTeX is correct”, but were not keen to invest time or thought into making the proof readable by the computer. And then there were some (but very few!) who had not heard of theorem proving before and were very excited by the prospect of being able to obtain certainty about their proofs immediately and without having to bother other scientists with it.

During the mathematician’s panel discussions, where I posed the question “Do you see value in – or even a need for – machine-checked proofs in mathematics.”, Efim Zelmanov (Fields Medal 1994) said “a proof is what other mathematicians see as a proof”. I found this attitude a bit surprising – for me, a proof has always been a rigorous derivation within a formal system (say, ZFC set theory), and what we write in papers is a (less formal) description of the actual proof, whose existence we believe in. Therefore I was very happy to see Vladimir Voevodsky give a very committed talk about Univalent Foundations and how using that as the language for mathematics will allow more of mathematics to be cast in a formal, machine-checked form.

I got the chance to discuss this with him in person, as I wanted to hear his option on Isabelle, and especially on the usefulness of the style of structured proof that Isar provides, and which is closer to the style of proofs that mathematicians use in papers. He said that he enjoyed writing his proof in the style required in Type Theory and in Coq, and that maybe mathematicians should and will adjust to the language of the system, while I believe that a structured proof languages like Isar, independent of the underlying logic (HOL in this case; which is insufficient to form a base for all of abstract mathematics), is a very useful feature and that proof assistants should adjust to the mathematicians.

We also briefly discussed the idea of mine to work with theorem provers already with motivated students in high schools, e.g. in math clubs, and found that simple proofs about arithmetic of natural numbers could be feasible here, without being too trivial.

All in all a very rewarding and special week, and I can only recommend to try to attend one of the next forums, if possible.

(Page 1 of 31, totaling 455 entries) » next page
Nach oben