Karl Brodowsky's IT-Blog – Seite 32 – IT Sky Consulting GmbH

Scala Days in Berlin 2014

Am 16., 17. und 18. Juni 2014 war ich bei der Konferenz „Scala Days“ in Berlin. Wie so oft bei diesen Veranstaltungen gibt es einen Haufen Vorträge, in diesem Fall bis auf die jeweilige „Keynote“ jeweils vier gleichzeitig. Das Veranstaltungslokal war wie bei der Devoxx in Antwerpen ein Kino, allerdings in diesem Fall schon lange umgewidmet für andere Zwecke, aber gute Projektoren gab es noch. Große Themen waren Fragen des Compilerbaus und wie man mit der richtigen funktionalen Perspektive aus der relativ einfachen Aufgabe, einen Interpreter zu schreiben, zu der schwierigen Aufgabe kommt, einen Compiler zu schreiben. Das hilft sicher, Sprachkonstrukte in Scala zu verstehen, aber die Idee wurde auch auf andere Felder angewendet, etwa um SQL-Queries zu kompilieren und zu optimieren oder um mit einem aus Compilercode gebauten Programm Quelltexte zu analysieren.

Ein anderes großes Thema waren „Streams“, die für Webservices nützlich sein sollen. Im Gegensatz zu klassischen Webservices, bei denen man den ganzen Request erstmal in Empfang nimmt, wurden auch Konzepte behandelt, um sehr große oder quasi unbegrenzte Requests zu verarbeiten. Dazu muss man diese natürlich schon verarbeiten, sobald eine gewisse nutzbare Datenmenge angekommen ist.

Ein kleines, aber interessantes Thema war die Entwicklung von Android-Apps mit Scala. Bekannt ist als Ansatz dafür natürlich Scaloid, aber hier wurde Macroid, ein alternativer Ansatz vorgestellt. Es sah vielversprechend aus, dass man mit weniger Code gute Android-Apps schreiben kann. Eine große Sorge ist, dass diese Scala-Apps den Speicher sprengen. Weil sie zusätzlich zu den vorinstallierten Java-Libraries noch Scala-Libraries brauchen, die etwa 5 MB groß sind, vergeht einem schnell der Appetit, außer man setzt gerootete Android-Devices voraus, auf denen die Scala-Libraries vorinstalliert sind. Das Thema verliert aber ein bißchen seinen Schrecken, weil der Build-Prozess einen Schritt enthält, in dem unnötige Klassen aussortiert werden, so dass am Ende nur das installiert wird, was man wirklich braucht. Wenn man so weit geht, Akka auf dem Mobiltelefon laufen zu lassen, wird das aber spannend, weil Akka viel Reflection und damit sehr viel fehleranfällige Konfiguration für diesen Optimierungsschritt benötigt.

Interessant war auch das Thema API-Design. Vieles war deckungsgleich mit Dingen, die ich bei einer API-Design-Schulung für Perl von Damian Conway vor ein paar Jahren gehört hatte, aber es gibt natürlich Scala-spezifische Themen, die auch interessant sind. Es ist erstaunlisch schwierig, Binärkompatibilität von Klassen zu erzielen und zwingt auch zu unschönen Kompromissen. Aber die gehören wohl auch in der Scala-Welt zum Leben.

Closures in C and Scala

Deutsch

Are closures at all possible in C, without falling back to writing some interpreter in C and using that interpreted langauge?

Function pointers alone are far less than what is needed for closures. But they are one of the building blocks. It is quite hard to get the signature right, but a typedef proves to be useful.

The next issue is that C does not allow inner functions by default and that it is not possible to automatically include a context, which is essential for the concept of closures.

But it is surprisingly easy to overcome that issue:

The function is defined before the function within which it should be meant to be defined. It has an additional parameter for some „context“-struct, which can be used to include variables from that context.
struct closure; typedef int (*fun_type)(const struct closure *context, const int param);

This struct includes the variables and a function pointer:
struct closure { int x; fun_type fun; };

Now the function definition in languages that support closures still have to be provided in some way and this is done anonymously with some mechanism called lambda or so, within another function or method whose variables are implicitely included. In a way methods can be considered a special case of this, since they include access to attributes of the enclosing object. In C all functions are defined in the regular way, but this time the fun_type signature needs to be observed. References to enclosed variables need to be bound by explicitely putting them into the context:
int f(const struct closure *context, const int param) { return (context->x) + param; }

The second order function that returns the closure can now be defined. We only have to accept the C notation, but it is fully equivalent to closures, just a little bit more noise:
struct closure *adder(int x) { struct closure *result = malloc(sizeof(struct closure)); result->x = x; result->fun = f; return result; }

Off course memory management is always an issue to observe in C…

Now the whole thing can be used like this:
int main(int argc, char *argv[]) { int retcode; if (argc < 2) { usage(argv[0], "not enough parameters"); } int x = atoi(argv[1]); int y = atoi(argv[2]); struct closure *cl = adder(x); int i; for (i = 0; i < y; i++) { printf("cl(%d)=%d\n", i, cl->fun(cl, i)); } }

The complete example can be found on github.

Off course the same is much shorter and more elegant in Scala:
object Closure { def main(args : Array[String]) : Unit = { val x : Int = args(0).toInt val y : Int = args(1).toInt val f : ((Int) => Int) = adder(x); val arr = (1 to y).map(f) println(arr.toString) }

def adder(x : Int) : ((Int) => Int) = { (y => x+y) } }

Even this can be found on
github.

Is there a way to achieve Closures in C describes numerous approaches to this issue.

Closures III (in C)

English

Geht so etwas überhaupt?

Ein Element sind die Funktionspointer. Es ist immer recht schwierig, die Signatur davon richtig zu treffen, aber ein typedef hilft.

Die nächste Schwierigkeit ist, dass C normalerweise keine inneren Funktionen erlaubt und dass man auch keinen Kontext einbinden kann.

Das lässt sich lösen:

Die Funktion hat einen weiteren Parameter für ein Context-Struct, in dem die Variablen eingebunden werden.
struct closure; typedef int (*fun_type)(const struct closure *context, const int param);

Das sieht so aus, dass dort die Variable(n) und ein Funktionspointer enthalten sind:
struct closure { int x; fun_type fun; };

Nun muss man die Funktionen ja in für Closures gemachten Programmiersprachen trotzem noch hinschreiben, aber anonym und am richtigen Ort.
In C muss man alle möglichen Funktionen regulär, aber mit der fun_type-Signatur von oben definieren. Die Referenzen auf die eingebundenen Variablen müsse vom context-Parameter kommen, statt implizit verfügbar zu bleiben, z.B.:
int f(const struct closure *context, const int param) { return (context->x) + param; }

Die Funktion 2. Ordnung, die die Closure zurückgibt, kann man nun auch definieren, man muss nur die C-Schreibweise akzeptieren und statt die Funktion an Ort und Stelle zu definieren eine der vorher definierten Funktionen referenzieren. Auch das ist äquivalent zu Closures:
struct closure *adder(int x) { struct closure *result = malloc(sizeof(struct closure)); result->x = x; result->fun = f; return result; }

Und so kann man das ganze dann verwenden:
int main(int argc, char *argv[]) { int retcode; if (argc < 2) { usage(argv[0], "not enough parameters"); } int x = atoi(argv[1]); int y = atoi(argv[2]); struct closure *cl = adder(x); int i; for (i = 0; i < y; i++) { printf("cl(%d)=%d\n", i, cl->fun(cl, i)); } }

Das komplette Beispiel ist auf github.

In Scala sieht das natürlich viel kürzer aus:
object Closure { def main(args : Array[String]) : Unit = { val x : Int = args(0).toInt val y : Int = args(1).toInt val f : ((Int) => Int) = adder(x); val arr = (1 to y).map(f) println(arr.toString) }

def adder(x : Int) : ((Int) => Int) = { (y => x+y) } }

Auch das ist auf Github

Getter und Setter

English

In der objektorientierten Programmierung gilt es als fortschrittlich, getter und setter zu verwenden, statt auf Attribute direkt zuzugreifen, weil das einem die Flexibilität gibt, später auf berechnete Attribute umzuschwenken. Etwas hässlich ist das, weil die getter und setter, etwas willkürlich den Attributnamen mit so einem vorangestellten „get“ oder „is“ oder „set“ und eventueller Umwandlung der Groß- und Kleinschreibung einzelner Zeichen versehen. Eine subtile Besonderheit ist, dass es verwirrend wird, wenn Attributnamen mit „get“, „is“ oder „set“ beginnen. Gerade Boolean-Attribute ist man versucht mit „hasSomething“, „isSomething“, „doesSomething“, „canSomething“, „mustSomething“,… o.ä. zu benennen, was dann zu dem Getter „getIsSomething()“ oder „isIsSomething()“ führt. Oder man lässt in dem Fall das Präfix weg, aber nur beim Getter…

Schöner ist es, wenn man Getter und Setter natürlich bennen kann, wie das z.B. in C#, Ruby und Scala der Fall ist: Man schreibt den Getter so, als würde man das Attribut public machen und darauf zugreifen, aber hat durch die entsprechenden Sprachkonstrukte die Möglichkeit, die Getter und Setter durch andere Implementierungen zu ersetzen, wenn der Bedarf besteht. Es gibt sicher wichtigeres, aber das ist zumindest schöner, lesbarer und deshalb weniger fehleranfällig. Und sprachlich auch sauberer als diese „halb-magic“-Bedeutung von „get…“, „set…“ und „is…“.

Im Grunde genommen sind aber auch Zugriffe auf Listen und Maps oft eine Art Getter und Setter:
y=a.get(pos) könnte man auch als y=a[pos] schreiben wollen, entsprechend a.put(pos, x) auch als a[pos]=x. Dasselbe gilt für Maps mit u=m.get(k), was schöner und intuitiver als etwas in der Art von u=m[k] wäre. Oder statt m.put(k, v) so etwas wie m[k]=v. Aus genügend abstrakter Sicht ist das nicht so wichtig, aber wenn die Lesbarkeit sich verbessert, macht man weniger Fehler und so hat man pragmatisch gesehen einen kleinen Qualitäts und Effizienzgewinn mit der Zuweisungsschreibweise.

Nun sind aber Setter in Wirklichkeit oft problematisch. Es ist immer gut, Objekte immutable zu haben, weil man sie dann problemloser zwischen Threads herumreichen kann, ohne dass es zu Fehler bei gleichzeitigen Zugriffen kommen kann. Nun stellt sich aber die Frage, wie man dann das Objekt konstruieren soll. Ein Konstruktor mit positionalen Parametern ist zwar möglich, aber oft nicht sehr lesbar, wenn die Parameterliste nicht völlig überschaubar und klar ist. So etwas wie benannte Parameter könnte sehr viel helfen. Ein anderes Muster ist es, ein temporäres Objekt mit Settern aufzubauen und dann daraus das eigenteliche unveränderliche (immutable) Objekt zu generieren. Man kann dafür spezielle Setter nehmen, die jeweils das veränderte Objekt zurückgeben und das etwa so etwas schreiben wie
SomethingImmutable s = new SomethingTemp().setX(x).setY(y).setZ(z).toSomething(),
was nicht superschön ist, aber wenn man auf Java Wert legt, doch eine Möglichkeit.

Hier zeigt sich auch, warum es so schön ist, wenn man Listen und Maps und vielleicht andere Collections einfach mit allen Elementen konstruieren und dann gleich immutable machen kann. In Java geht das für Listen immerhin schon mit
Collections.immutableList(Arrays.asList(a, b, c, d, e, f, g, h))
machen. Wobei diese Konstruktion relativ neu ist und wegen der Konstruktionsphase Collections nicht defaultmäßig immutable sein können. Immerhin könnte man ein
Arrays.asImmutableList(T..t)
definieren. Oder eine Methode auf List
.immutable().
Schöner (klarer, lesbarer, weniger fehleranfällig) wäre es aber, wenn man das als
[a, b, c, d, e, f, g, h]
schreiben könnte. Für die Ausgabe von Listen mittels toString() wird so etwas ja schon verstanden. Für das Konstruieren von Maps gibt es in anderen Programmiersprachen auch Schreibweisen, die etwa so aussehen wie
m = { k1 => v1, k2 => v2, k3 => v3, k4 => v4}.
Will man sich normalerweise dafür interessieren, welche Map-Implementierung jetzt genommen wird? So etwas ließe sich als
m = new TreeMap{k1 => v1, k2 => v2, k3 => v3, k4 => v4}
schreiben. Solche Dinge waren für Java 8 vorgesehen, sind aber wohl in letzter Minute rausgeflogen oder auf Java 9 verschoben worden.

Neue Projekte

Ab 1. September 2014 bin ich für neue Projekte verfügbar.

Division mit Rest

Die Division mit Rest ist in vielen Programmiersprachen enthalten und man könnte meinen, dass klar ist, was damit gemeint ist. Meistens wird diese Restbildung mit „%“ geschrieben, was alle von C übernommen haben und was auch gut ist. Außer man will etwas mit Prozentrechnung programmieren und ist vom Taschenrechner für % etwas anderes gewohnt.

Aber man sollte etwas vorsichtig sein.

Zunächst gilt bei vielen Programmiersprachen die Regel, dass „immer“

$a = ( a/b) * b + a \% b$

gilt. Das ist schön, aber manche Programmiersprachen finden es logischer, wenn $a/b$ eine Fließkommazahl oder eine rationale Zahl ergibt. Eine „ganzzahlige gerundete Division“ wäre natürlich zusätzlich cool, aber wenn man es so ausdrückt, fällt schon auf, wo die Schwierigkeit liegt. Setzen wir mal einen positiven Divisor voraus…. Wie wird hier gerundet? Je nach Rundungsverfahren ist für $r = a \% b$ immer $r \ge 0$ (Ruby) oder nur $r \ge 0$ für $a \ge 0$ und für negative $a$ ist es $r \le 0$ (Scala). Denkbar wäre aber auch, dass $-\frac{a}{2} \le r < \frac{a}{2}$ gilt.
Leider ist es ein bisschen schwierig, eine elegante Schreibweise zu finden, um die Rundungsmethode für das % zu definieren.

In der Praxis benötigt man diese Reste oft für weitere Verarbeitungen. Was macht man nun mit den negativen Resten?
Oft ist es sinnvoll, $a$ zu negativen Resten hinzu zu addieren. Dann hat man immer noch einen legitimen Rest, aber mit dem richtigen Vorzeichen, etwa das, was bei Ruby sowieso herauskäme.

Millibytes

Wir lernen alle paar Monate oder mindestens alle paar Jahre neue Begriffe wie Kilobyte, Megabyte, Gigabyte, Terabyte, Petabyte und Exabyte kennen. Man muss immer aufpassen, weil damit die Potenzen von 1024 oder die von 1000 gemeint sein können. 1024 ist praktischer in der Informatik, aber 1000 ist praktischer für Anbieter von Festplatten, weil sie dann ein eindrucksvolleres Schild auf die Ware kleben können, ohne sehr unehrlich zu sein. Und bei Terabytes macht der Unterschied schon etwa 10% aus und es wird mehr wenn wir Exabytes oder Hepabytes oder Okabytes oder was auch immer man da erfinden wird, verwenden. Im Moment betrifft das Problem nur große Firmen wie Google und Google achtet bei der Einstellung von neuen Mitarbeitern sehr auf ein gewisses Mindestniveau, so dass sie nicht gefährdet sind, sich beim Festplattenhersteller wegen dieser 10-20% über den Tisch ziehen zu lassen.

Aber wie sieht es aus mit Millibytes? Das klingt komisch. Kleiner als ein Byte geht nicht, außer man überlegt etwas länger und kommt darauf, dass es noch Bits gibt, also Achtelbytes. Jedes Bit ist eine Antwort auf eine Frage, die nur mit Ja oder Nein beantwortet werden kann. Ein kleiner Nebenaspekt kommt mit Binärdaten ins Spiel. Diese sind üblicherweise als eine Sequenz von Bytes dargestellt. In Wirklichkeit sollte es eine Sequenz von Bits sein, das heißt, wir sollten genaugenommen beim letzten Byte wissen, welche Bits noch dazugehören und welche nur Füllbits sind, die wir ignorieren müssen. Das lässt sich durch entsprechende Binärformate in den Griff bekommen, wenn man angibt, wieviele Bits die Daten lang sind und dann die Bytes folgen.

Aber gibt es halbe Bits? Oder Millibits? So absurd ist die Idee nicht. Wenn wir eine Netzwerkverbindung haben, die absolut zuverlässig funktioniert, dann ist ein Bit das ankommt definitiv dasselbe wie das, was reingeschickt wurde. Es enthält also den Gegenwert von einem Bit Information darüber, was eingegeben wurde. Wenn der Kanal nun gar nicht funktioniert und zufällige Bits rauskommen, ist deren Informationsgehalt 0. Man erfährt gar nichts darüber, was gesendet wurde. Typische Verbindungen liegen irgendwo dazwischen. Das Bit was rauskommt, hat also etwas mit dem was reingesteckt wurde, zu tun, ist aber nicht 100% zuverlässig. Mit fehlerkorrigierenden Codes kann man die Zuverlässigkeit auf Kosten der Kapazität steigern. Analysiert man die ganze Situation, stellt man fest, dass ein physikalisch empfangenes Bit weniger als ein Bit Information bringt. Man braucht im Durchschnitt etwas mehr als ein übertragenes Bit, um ein Bit wirkliche Information von der Quelle wirklich mit einer gewünschten Zuverlässigkeit zu ermitteln. Die Zuverlässigkeit wird nie 100% erreichen, aber theoretisch 99.9999% mit so vielen Neunen wie man will. Am Ende des Tages bringt uns ein Bit, das physikalisch übertragen wird, also durchschnittlich nur 0.7, 0.95 oder 0.00012 Bits tatsächliche Information, weil es im Kontext der Fehlerkorrektur mit anderen Bits kombiniert werden muss. Und das sind dann 700, 950 oder 0.12 Millibits bzw. 87.5, 118.75 oder 0.015 Millibytes. Die Diskussion wegen 1024 und 1000 ist auch hier relevant, aber ich überlasse sie gerne den Lesern…

Flashsort in Ruby

English

Es gibt auf github eine einfache Implementierung von Flashsort in Ruby, nachdem hier auf github schon eine Implementierung in C zu finden ist. Die C-Implementierung ist typischerweise schneller als die libc-Funktion qsort, aber letztlich hängt das von den Daten ab und davon, wie gut die metric-Funktion ist, die man zusätzlich zur Vergleichsfunktion bei Flashsort liefern muss. Man kann sich diese metric-Funktion als eine Art monotone Hashfunktion vorstellen, also gilt

$\bigwedge_{a,b: a\le b} m(a) \le m(b)$

Diese zusätzlich benötigte Funktion oder Methode ist nicht wirklich vorhanden, außer bei numerischen Werten, was den Einsatz von Flashsort etwas erschwert. Entscheidend für eine gute Performance ist eine gute metric-Funktion, allerdings sind bei typischen Text-Dateien schon ziemlich triviale Implementierungen ganz brauchbar.

In diesem Blogbeitrag sind weitere Sortieralgorithmen für Ruby gezeigt.

Advanced Akka

In der vergangenen Wochenende hat sich die Möglichkeit ergeben, an der Type-Safe-Schulung über „Advanced Akka“ teilzunehmen. Akka ist ein Framework zur Parallelisierung und Verteilung von Verabeitungsoperationen einer größeren Applikation, das auf Scala basiert. Akka ist selbst in Scala geschrieben, aber es wurde darauf geachtet, dass es auch mit Java benutzbar ist. Unabhängig von der konkreten Implementierung ist es aber auch konzeptionell interessant, weil Akka Ideen umsetzt, wie man massiv parallele Applikationen entwickeln kann. Erlang, LFE und Elixir verwenden zum Beispiel ähnliche Konzepte, vielleicht noch etwas radikaler, während Scala ja einen „sanften“ Übergang zur funktionalen Welt ermöglichen soll, ähnlich wie C++ für den Einstieg in die Objektorientierung von ein paar Jahren.

Im Fall, dass man Akka verteilt betreibt, sind natürlich wieder die Serialisierungsmechanismen interessant. Man sollte das berücksichtigen und zumindest nicht zu feingranulare Zugriffe über das Netzwerk verteilt durchführen, wenn die Parallelisierung eine hohe Performance bieten soll.

Systemprogrammierung für Posix und Win32

Systemprogrammierung macht man in beiden Fällen mit C, da sollte es einige Ähnlichkeiten zwischen den Systemen geben und wenn man genau schaut, sieht man die auch. Aber auf den ersten Blick sehen die entsprechenden C-Programme sehr verschieden aus. Das überrascht nun wieder, da doch eigentlich mit der Programmiersprache C auch die libc standardisiert ist und das sogar einigermaßen eingehalten wird. Leider ist die libc gerade im betriebssystemnahen Bereich mehr oder weniger auf die Schnittmenge vieler Systeme zugeschnitten und stellt einiges an Funktionalität der darunter liegenden Betriebsysteme nicht zur Verfügung. So kann man vieles generisch programmieren, aber es gibt doch immer wieder Bereiche, in denen es vorteilhaft oder sogar fast zwingend notwendig ist, eine betriebssystemspezifische Implementierung zu wählen.

Rein optisch sieht man den Unterschied sofort. Die typischen Win32/Win64-Programme verwenden schon Funtionsnamen mit Camel-Case und großen Anfangsbuchstaben und bevorzugt sehr lange Namen für Funktionen, Variablen, Konstanten und Macros und sehr lange Parameterlisten. So werden die MS-Windowsprogramm lang, aber man kann wenigstens oft sehen, was in etwa gemeint ist. Letztlich muss man aber die Konzepte verstanden haben und Zugriff auf eine Funktions- und API-Referenz haben, ob das nun Man-Pages oder die Webseite einer großen Firma ist, ist sekundär. Eigentlich ist dieser Unterschied auch nicht so wichtig, weil man sich an andere Schreibweisen für die konzeptionell gleiche Sache schnell gewöhnen kann. Ärgerlich ist nur, dass man wirklich alles zweimal schreiben muss. In der Praxis wird man vielleicht die I/O- und IPC-Funktionalität, die die Software benötigt, an der man arbeitet, in einer oder mehreren Bibliotheken behandeln, wohlgemerkt spezifisch das, was man braucht und nicht eine generische Verallgemeinerung beider APIs, die nie fertig und nie richtig gut wird. Die restliche Programmlogik kann man vielleicht generisch gestalten.

Es gibt auch Möglichkeiten, unter MS-Windows mehr oder wenigeer viele der unter Posix (Linux, Unix, MacOSX, etc.) bekannten Funktionen unter MS-Windows zu benutzen. Mit cygwin bekommt man die meisten, das ist sozusagen so eine generische Schicht, aber auch die nativen Win32/Win64-Bibliothken enthalten oft über das geforderte Minimum hinaus Funktionen, die so typischerweise unter Posix üblich sind, z.B. open(), close(), read() und write().

Möglichkeiten zur Generierung von Nebenläufigkeit mit Prozessen und Threads sind in beiden Systemen vorhanden, aber auch hier mit subtilen semantischen Unterschieden, die es einem schwer machen können. Interprozesskommunikation haben beide Systeme und man kann natürlich auch recht vie l mit TCP/IP-lösen, was dann generisch ist.
Die bekannte Thematik mit „/“ vs. „\“ als Datei-Pfad-Trennzeichen kann man dagegen leicht lösen, indem man konsequent „/“ verwendet. Das verstehen die Win32- und Win64-API-Funktionen gut.

Die leidige Problematik mit den Zeilenwecheln mit ctrl-M ctrl-J vs nur Ctrl-J ist auch nicht so schlimm, wie man meint. Man kann eine Datei unter MS-Windows binär anlegen und dann wird das Ctrl-M nicht eingefügt. Und über weite Strecken werden beide Konventionen auf beiden Systemen problemlos verstanden und können entsprechend eingesetzt werden. Sinnvoll ist nur, dass man das definiert und sich auf einen Weg einigt.