Rundung mit Summe

English

Häufig muss man einige Zahlen auf einmal runden, aber die Summe soll hinterher „aufgehen“. Das kann man „summenerhaltendes Runden“ nennen, wobei unter Umständen auch die Summe gerundet wird. Der häufigste Fall sind Prozentwerte und wenn die gerundeten Zahlen nicht zusammen 100% ergeben, versteht das niemand. Da kann es schon besser sein, etwas schwieriger verständliche Dinge hinter den Kulissen zu tun. Kurz gesagt ist unsere Frage, ob die Rundung ein Endomorphismus der additiven Gruppe ist. Das bedeutet, dass $\bigwedge_{x,y\in M} r(x+y)=r(x)+r(y)$ . Auf den resten Blick sieht das vernünftig aus und die Fehler heben sich ja oft irgendwie weg. Aber wir können für eine gängige Rundungsmethode ein Gegenbeispiel finden: $x=1.4, y=2.3, z=3.3$ . Wir haben $x+y+z=7$ . Jetzt wird das gerundet und ergibt $r(x)=1 \wedge r(y)=2 \wedge r(z)=3 \bigrightarrow r(x)+r(y)+r(z)=6 \ne 7$ . Ein Gegenbeispiel reicht und es ist kein Endomorphismus.

Ist das ein ganz neues Konzept? Es wird ja offensichtlich in fast allen Druckerzeugnissen, die irgendwie Prozentwerte so angeben, für die Gesamtsumme „gemogelt“. Aber es stellt sich heraus, dass das auch hochoffiziell alle vier Jahre passiert. Wir haben irgendwelche Ereignisse, die sich „Wahlen“ nennen und da kann man Parteien oder Listen für ein Parlament eine Stimme geben. Das Parlament hat meistens eine vorgegebene Anzahl von Sitzen, wenn wir mal Spezialitäten wie 5%-Sperrklausel und Überhangmandate in der deutschen Wahlpraxis vergessen, um es noch halbwegs für Logik zugänglich zu halten. Man stelle sich nur vor, was passiert, wenn 40 Parteien antreten und je 2.5% erhalten, um zu sehen, dass das System nicht korrekt ist, im Sinne einer korrekten Software. Nun sollte man meinen, die Parlamentssitze werden einfach im Verhältnis der Stimmen aufgeteilt. Wenn man $n$ Parlamentssitze hat, werden die Stimmenanteile in Prozent auf Vielfache von $\frac{100}{n}$ gerundet und zwar so, dass es am Schluss aufgeht. Es gibt viele Verfahren, um das zu bewerkstelligen und je nachdem, welches Verfahren man auswählt, kann bei denselben Stimmenzahlen die Sitzverteilung geringfügig variieren. Habe ich das Wort „Mogeln“ oben erwähnt? Es muss wohl Zufall sein. Welches Verfahren gerade am gerechtesten ist, wechselt also von Jahr zu Jahr immer wieder ein bisschen.

Wenn wir nicht gerade eine Wahlauswertungssoftware schreiben, ist in den meisten Fällen diese Frage weniger aufgeladen. Es soll in einem Text eine Summe von mehreren gerundeten Werten eingehalten werden und die Rundung soll „einigermaßen vernünftig“ erfolgen. Der oberflächliche Leser wird zufrieden sein, der etwas kritischere auch, weil die Summe stimmt und der Leser, der sich richtig Gedanken macht wird es auch verstehen, dass man da mogeln musste und dass man das einigermaßen sinnvoll getan hat. Man beachte, dass diese Thematik einige Überraschungen birgt, z.B. das Alabama-Paradoxon und das Wählerzuwachsparadoxon.

Wie in Restklassenrundung beschrieben, gehen wir von Mengen $M$ und $N \subseteq M$ mit einer Metrik $d: M\times M \rightarrow {\Bbb R_+}, (m, n) \mapsto d(m,n) \ge 0$ aus und wollen Abbildungen $r : M \rightarrow N$ betrachten, bei denen $d(x, r(x))$ klein bleibt und eventuell ein paar weitere Bedingungen erfüllt sein sollen. Da aber die Korrektur schon Teil der Abbildung sein soll, interessiert uns hier eigentlich eher so etwas wie eine Abbildung
$s: M^n \rightarrow N^n, (m_1,\ldots,m_n) \mapsto (n_1,\ldots n_n)$ mit $\sum_{i=1}^n m_i = \sum_{i=1}^n n_i$ und für alle $i$ ist $d(m_i,n_i)$ „klein“. Reine Auf- oder Abrundung kann also nicht die Lösung sein, da das nie aufgeht. Wir könnten die Fehlerquadrate minimieren, was den Vorteil hat, das große absolute Abweichungen sich stärker auswirken, so dass eine gleichmäßige Verteilung der Korrektur besser wegkommt, also z.B.
$\sum_{i=1}^n (d(m_i, n_i))^2$ ist minimal. Es lassen sich Beispiele konstruieren, wo das nicht eindeutig ist. In dem Fall kann man entweder eine Regel festlegen oder mit Zufallszahlen ermitteln welche der passenden Möglichkeiten zum Zuge kommt. Man kann auch versuchen, die relativen Fehler zu minimieren, also so etwas wie
$\sum_{i=1: m_i \ne 0}^n (\frac{d(m_i,n_i)}{d(m_i,m_i)})^2$ , wobei man die Summanden mit $m_i=0$ weglassen muss, was nicht stört, wenn $0\in N$ ist, man also sowieso $0$ auf $0$ runden will.
Eine Alternative ist, sich einfach an den Sitzzuteilungsverfahren für Parlamente zu orientieren und deren Algorithmen sinngemäß für die hier beschriebene Aufgabe anzupassen:

Oft sind die Anforderungen an die „Qualität“ der Rundung niedriger als bei der Zuteilung von Parlamentssitzen, aber es lohnt sich schon, sich hierüber einige Gedanken zu machen statt einfach irgendwie mit einem naiven Ansatz zu runden.

Frage: Wie verhalten sich die oben aufgeführten Sitzzuteilungsverfahren zur Minimierung der absoluten und relativen Fehlerquadrate?

Bei genügendem Interesse kann ich einmal eine Implementierung für so eine Rundung hinzufügen.

Gelegentlich begegnen uns auch Probleme, die dem hier geschilderten sehr ähnlich sind oder die sich darauf zurückführen lassen. Wer hätte gedacht, dass die Zuteilung von Parlamentssitzen eigentlich eine Rundung ist?

Random-Access and UTF-8

Deutsch

It is a nice thing to be able to use random access files and to have the possibility to efficiently move to any byte position for reading or writing.

This is even true for text files that have a fixed number of bytes per character, for example exactly one, exactly two or exactly four bytes per character. Maybe we should prefer the term „code point“ here.

Now the new standard for text files is UTF-8. In many languages each character is usually just one byte. But when moving to an arbitrary byte position this may be in the middle of a byte sequence comprising just one character (code point) and not at the beginning of a character. How should that be handled without reading the whole file up to that position?

It is not that bad, because UTF-8 is self synchronizing. It can be seen if a particular byte is the first byte of a byte sequence or a successive one. First bytes start with 0 or 11, successive bytes start with 10. So by moving forward or backward a little bit that can be handled. So going to a rough position is quite possible, when knowledge of the average number of bytes per character for that language is around.
But when we do not want to go to a rough character position or to an almost exact byte position, but to an exact character position, which is usually the requirement that we have, then things get hard.

We either need to read the file from the beginning to be sure or we need to use an indexing structure which helps starting in the middle and only completely reading a small section of the file. This can be done with extra effort as long as data is only appended to the end, but never overwritten in the middle of the file.

But dealing with UTF-8 and random access is much harder than with bytes. Indexing structures need to be maintained in memory when accessing the file or even as part of the file.

2015

Frohes neues Jahr!
Happy New Year
Gott nytt år!
Godt Nyttår!
¡Próspero año nuevo!
Bonne année!
FELIX SIT ANNUS NOVUS
Felice Anno Nuovo!
Весёлого нового года!
السنة الجديدة المبتهجة
Een gelukkig nieuwjaar!

Residue Class Rounding

Deutsch

If you do not know what residue classes are, just read on, it will be explained to the extent needed later on.

The concept of rounding seems familiar, but let us try to grab it a little bit more systematically.

Let us assume a set $M$ of numbers and a subset $N \subseteq M$ of it, whose elements can be represented in the programming or software environment we are having in mind. We want to use a metric $d : M \times M \rightarrow \Bbb R_+, (x, y) \mapsto r=d(x,y)>=0$ . Usually we have three requirements for $d$ :

Identity of indiscernibles: $d(x,y) = 0 \iff x = y$
Symmetry: $d(x,y)=d(y,x)$
Triangular inquation: $d(x,z) \le d(x,y) + d(y,z)$

Usually the number that we are dealing with can be considered to be within the world of real or complex numbers, we can hence assume that $M \subseteq \Bbb C$ , often even $M \subseteq \Bbb R$ or if we are honest $M \subseteq \Bbb Q$ . Then we are usually working with $d(x,y) = |x-y|$ , which is kind of implicitly clear. If you do not know complex numbers, just think of real or even rational numbers, which is the most common case anyway. Off course the concepts for rounding of $p$ -adic numbers are really interesting and beautiful, but since I do not want to explain $p$ -adic numbers here, I will not extend on this issue.

What is our intuitive understanding of rounding?
Maybe just a map
$r: M \rightarrow N, x \mapsto r(x)$ ,
that is chosen with certain constraints for each x in such a way that $d(x, r(x))$ is minimal.
We need the constraints to enforce uniqueness if multiple values $y\in N$ with minimal $d(x,y)$ exist. The classical case of rounding to integral numbers has to answer the question of how to round $0.5$ . If $N$ is a subset of the real numbers, which is „usually“ the case, we have ordering. We can choose between the following constraints:

ROUND_UP: $|r(x)|\ge |x|$ Z.B. $r(0.4)=1$ and $r(0.5)=1$ and $r(-0.5)=-1$
ROUND_DOWN: $|r(x)|\le |x|$ Z.B. $r(0.6)=0$ and $r(0.5)=0$ and $r(-0.5)=0$
ROUND_CEILING: $r(x) \ge x$ Z.B. $r(0.4)=1$ and $r(0.5)=1$ and $r(-0.5)=0$
ROUND_FLOOR: $r(x) \le x$ Z.B. $r(0.6)=0$ and $r(0.5)=0$ and $r(-0.5)=-1$
ROUND_HALF_UP: Minimize $d(r(x),x)$ , but if multiple optimal values exist for $r(x)$ , pick the one furthest away from 0, for example $r(0.4)=0$ and $r(0.6)=1$ and $r(0.5)=1$ and $r(-0.5)=-1$
ROUND_HALF_DOWN: Minimize $d(r(x),x)$ , but if multiple optimal values exist for $r(x)$ , pick the one closest to 0, for example $r(0.4)=0$ and $r(0.6)=1$ and $r(0.5)=0$ and $r(-0.5)=0$
ROUND_HALF_CEILING: Minimize $d(r(x),x)$ , but if multiple optimal values exist for $r(x)$ , pick the largest, for example $r(0.4)=0$ and $r(0.6)=1$ and $r(0.5)=1$ and $r(-0.5)=0$
ROUND_HALF_FLOOR: Minimize $d(r(x),x)$ , but if multiple optimal values exist for $r(x)$ , pick the smallest, for example $r(0.4)=0$ and $r(0.6)=1$ and $r(0.5)=0$ and $r(-0.5)=-1$
ROUND_HALF_EVEN: Minimize $d(r(x),x)$ , but if multiple optimal values exist for $r(x)$ , pick the one with even last digit. Please observe that this constraint is useful in the classical case, but it cannot be generalized. For example: $r(0.4)=0$ and $r(0.6)=1$ and $r(0.5)=0$ and $r(-0.5)=0$ and $(1.5)=2$
ROUND_UNNECESSARY: This constraint does not work in the mathematical sense (or only with ugly abusive math formulas), but programmatically we can do that: We try $r(x)=x$ and throw an exception if not $x\in N$ .

Usually we are thinking in the decimal system (even though our computers prefer something else, but the computer should serve us and not vice versa..). So we pick a power of ten $10^n$ with $n \in \Bbb N_0$ , so $n \ge 0$ . Now we simply define
$N = \{ x \in M : 10^n x \in \Bbb Z\}$ ,
which means that $N$ contains all numbers of $M$ with a maximum of $n$ digits after the decimal point. This rounding works quite well with something like LongDecimal in Ruby or BigDecimal in Scala or Java, but BigDecimal offers fewer rounding modes than LongDecimal for Ruby.

Now we look at the residue class rounding. We assume such a power of ten $10^n$ . Then we need an integral number $m \ge 2$ and a set of numbers $R \subseteq \{0,...,m-1\}$ , we call them residues. Now we define $N = \{ x \in M : 10^n x \in {\Bbb Z} \wedge \bigvee_{r \in R} 10^n x \equiv r \mod{m}\}$ .
That means that if we fill the number with zeros to the given number of places after the decimal point, remove the decimal point and perform a division with residue of this number by $m$ , the residue lies in $R$ . In this case ROUND_HALF_EVEN can become difficult to implement and ambiguous, so we might need to sacrifice it. But even worse, we have to deal with the case that 0 is not in $R$ and provide rules how to round 0. The candidates have self-explanatory names:

ZERO_ROUND_TO_PLUS
ZERO_ROUND_TO_MINUS
ZERO_ROUND_TO_CLOSEST_PREFER_PLUS
ZERO_ROUND_TO_CLOSEST_PREFER_MINUS
ZERO_ROUND_UNNECESSARY

An important application of this is $m=10$ and $R=\{0, 5\}$ . This is used in Switzerland and probably other currency regions for rounding money amounts to multiples of 5 Rappen (0.05 CHF). This has already been described in „Rounding of Money Amounts„. If we have $m=10$ and $R=\{0,1,2,3,4,5,6,7,8,9\}$ we have the usual non-CHF-rounding case. Maybe there are even cases for $m=10$ and $R=\{0,2,4,6,8\}$ . But the concept is more general, if you like to use it.

Weihnachten 2014

Frohe Weihnachten!
Merry Christmas!
God Jul!
¡Feliz Navidad!
Joyeux Noël!
Natale hilare!
С Рождеством!
ميلاد مجيد
Buon Natale!
God Jul!
Prettige Kerstdagen!

Restklassenrundung

English

Das Konzept der Rundung kennt man grundsätzlich. Aber versuchen wir es etwas systematischer zu erfassen.

Man hat eine Menge $M$ von Zahlen und eine Teilmenge $N \subseteq M$ davon, deren Elemente in der verwendeten Programmierumgebung dargestellt werden. Dazu hat man noch eine Metrik $d : M \times M \rightarrow \Bbb R_+, (x, y) \mapsto r=d(x,y)>=0$ . Man verlangt normalerweise noch gewisse Eigenschaften von $d$ :

Positive Definitheit: $d(x,y) = 0 \iff x = y$
Symmetrie: $d(x,y)=d(y,x)$
Dreiecksungleichung: $d(x,z) \le d(x,y) + d(y,z)$

Typischerweise sind die Zahlen, mit denen wir uns meistens beschäftigen, in der Welt der reellen und komplexen Zahlen gedacht, man kann also fast immer sicher sein, dass $M \subseteq \Bbb C$ ist, meistens sogar $M \subseteq \Bbb R$ oder wenn wir ehrlich sind sogar $M \subseteq \Bbb Q$ . Dann ist normalerweise $d(x,y) = |x-y|$ . Wer die komplexen Zahlen noch nicht kennt, denke einfach an reelle und rationale Zahlen, das ist das, womit wir normalerweise bewusst zu tun haben. Dabei sind natürlich Konzepte wie Rundung speziell in $p$ -adischen Zahlen hochinteressant, aber dafür muss ich die erstmal erklären und das lasse ich heute…

Was stellen wir uns nun unter einer Rundung vor?
Vielleicht eine Abbildung
$r: M \rightarrow N, x \mapsto r(x)$ ,
die mit gewissen Nebenbedingungen für jedes x jeweils so gewählt wird, dass $d(x, r(x))$ minimal ist.
Die Nebenbedingungen brauchen wir einerseits, um es eindeutig zu machen, wenn mehrere Werte $y\in N$ existieren, für die $d(x,y)$ minimal ist. Der klassische Fall ist das Runden auf ganzzahlige Werte und die Frage mit der $0.5$ . Wenn $N$ eine Teilmenge der reellen Zahlen ist, was ja „meistens“ der Fall ist, hat man eine Anordung. Da kommen dann die folgenden Constraints zum Tragen (Beispiel immer mit Rundung auf ganze Zahlen):

ROUND_UP: $|r(x)|\ge |x|$ Z.B. $r(0.4)=1$ und $r(0.5)=1$ und $r(-0.5)=-1$
ROUND_DOWN: $|r(x)|\le |x|$ Z.B. $r(0.6)=0$ und $r(0.5)=0$ und $r(-0.5)=0$
ROUND_CEILING: $r(x) \ge x$ Z.B. $r(0.4)=1$ und $r(0.5)=1$ und $r(-0.5)=0$
ROUND_FLOOR: $r(x) \le x$ Z.B. $r(0.6)=0$ und $r(0.5)=0$ und $r(-0.5)=-1$
ROUND_HALF_UP: Minimiere $d(r(x),x)$ , aber wenn es mehrere optimale Werte für $r(x)$ gibt, wähle den am weitesten von 0 entfernten, z.B. $r(0.4)=0$ und $r(0.6)=1$ und $r(0.5)=1$ und $r(-0.5)=-1$
ROUND_HALF_DOWN: Minimiere $d(r(x),x)$ , aber wenn es mehrere optimale Werte für $r(x)$ gibt, wähle den am nächsten an 0, z.B. $r(0.4)=0$ und $r(0.6)=1$ und $r(0.5)=0$ und $r(-0.5)=0$
ROUND_HALF_CEILING: Minimiere $d(r(x),x)$ , aber wenn es mehrere optimale Werte für $r(x)$ gibt, wähle den größten, z.B. $r(0.4)=0$ und $r(0.6)=1$ und $r(0.5)=1$ und $r(-0.5)=0$
ROUND_HALF_FLOOR: Minimiere $d(r(x),x)$ , aber wenn es mehrere optimale Werte für $r(x)$ gibt, wähle den kleinesten, z.B. $r(0.4)=0$ und $r(0.6)=1$ und $r(0.5)=0$ und $r(-0.5)=-1$
ROUND_HALF_EVEN: Minimiere $d(r(x),x)$ , aber wenn es mehrere optimale Werte für $r(x)$ gibt, wähle den mit gerader Endziffer. Achtung, dieser Constraint ist im „klassischen“ Fall anwendbar, aber nicht allgemeingültig. Z.B.: $r(0.4)=0$ und $r(0.6)=1$ und $r(0.5)=0$ und $r(-0.5)=0$ und $(1.5)=2$
ROUND_UNNECESSARY: Dieser Constraint ist im mathematischen Sinne nicht geeignet (oder nur mit hässlichen Verrenkungen), aber programmatisch können wir das: Wir nehmen $r(x)=x$ und schmeißen eine Exception wenn nicht $x\in N$ schon gilt.

Typischerweise denken wir im Dezimalsystem und dann wählen wir eine Zehnerpotenz $10^n$ mit $n \in \Bbb N$ , also $n \ge 0$ . Nun ist einfach
$N = \{ x \in M : 10^n x \in \Bbb Z\}$ ,
also umgangsprachlich sind in $N$ alle Zahlen aus $M$ mit maximal $n$ Stellen nach dem Komma. Diese Rundung funktioniert ganz gut mit so etwas wie LongDecimal in Ruby oder BigDecimal in Scala oder Java, wobei BigDecimal weniger Rundungsmodi anbietet als LongDecimal für Ruby.

Nun kommen wir zur Restklassenrundung. Wir gehen wieder von dieser Zehnerpotenz $10^n$ aus. Dann brauchen wir noch eine natürlich Zahl $m \ge 2$ und eine Menge von Resten $R \subseteq \{0,...,m-1\}$ . Nun ist
$N = \{ x \in M : 10^n x \in {\Bbb Z} \wedge \bigvee_{r \in R} 10^n x \equiv r \mod{m}\}$ .
Das bedeutet, wenn wir mit Nullen auf die angegebene Anzahl von Nachkommastellen auffüllen, das „Komma“ (normalerweise als „.“ geschrieben) weglassen und dann diese Zahl mit Rest durch $m$ teilen, der dabei herauskommende Rest in $R$ liegt.
In diesem Fall wird es mit dem ROUND_HALF_EVEN eventuell schwierig, da es undefiniert oder mehrdeutig werden kann. Aber wir müssen auch den Fall abdecken, dass die 0 nicht in $R$ ist und Regeln angeben, wohin die 0 gerundet werden soll. Die Kandidaten sind hier mit selbsterklärenden Namen versehen:

ZERO_ROUND_TO_PLUS
ZERO_ROUND_TO_MINUS
ZERO_ROUND_TO_CLOSEST_PREFER_PLUS
ZERO_ROUND_TO_CLOSEST_PREFER_MINUS
ZERO_ROUND_UNNECESSARY

Ein wichtiger Anwendungsfall ist hier $m=10$ und $R=\{0, 5\}$ . So kann man in der Schweiz Geldbeträge auf Vielfache von 5 Rappen (0.05 CHF) runden. Dies wurde in Rundung bei Geldbeträgen bereits genauer beschrieben.

English or German / Englisch oder Deutsch

Currently I am writing blog articles in German and translate them to English, if I consider them interesting for a wider audience. I am considering to do it the other way round and write articles in English and provide a German translation of some of them. I am creating a poll for this.
Find the poll in the upper left corner of the Start page.

Zur Zeit schreibe ich alles auf Deutsch und übersetze Artikel auf Englisch, wenn sie von allgemeinerem Interesse sind. Ich überlege, es umgekehrt zu machen und die Artikel ab 1. Januar 2015 auf Englisch zu schreiben und bei Interesse einzelne auf Deutsch zu übersetzen. Ich starte eine Umfrage dazu.
Die Umfrage steht in der linken oberen Ecke der Startseite.

Scala Exchange 2014

Deutsch

I have been visiting the conference Scala eXchange ( #scalaX ) organized by Skillsmatter in London.

Here is some information about the talks that I have attended and the highlights:

The Binary Compatibility Challenge

Martin Odersky

Examples can be constructed for each of the four combinations of binary and source code compatibility.
We wish more of both. The talk is mostly about binary compatibility.
For Scala the conflict is innovation vs compatibility. Java chose one extreme to retain compatibility at any cost, which is considered more like a constraint then a restriction by the Java developers. It is easier for them because they control the JVM which is again close to the Java language. Clojure, Ruby, JRuby, Perl, Python, PHP and some others have less problems with this issue because the software is distributed as source code and compiled when run, just in time.
Reproducible builds are hard to achieve in Scala, just think of the many build tools like ivy, gradle, maven, sbt, ant, make (yes, I have seen it),…
The idea is to split the around 30 steps of compilation of scala into two groups. The first group could yield an intermediate format after around 10 internal compilation steps, which might be stored as tree of the program in a clever binary format. This could be a good compromise and address some of the issues, if kept stable. More likely will programs be combinable compatibly with this format than with binary or source only. It would also save time during compilation, which is a desirable improvement for scala.

REST on Akka: Connect to the world

Mathias Doenitz

Akka-http is the spray 2.0 or successor of spray. It follows the lines of spray, but improves on some of the shortcomings.
It should be used for reactive streams in Akka and is important enough to be part of core Akka.
TCP-flow-control can be used to implement „back pressure“.

Bootstrapping the Scala.js Ecosystem

Haoyi Li

Scala shall be compiled to as second alternative instead of JVM. The target is the browser, not so much server side JavaScript, where the JVM is available and better.
Advantage for applications: Some code can be used on both sides, for example HTML-tag-generation, validation etc. This is more elegant than using two languages. Also Scala might be considered a more sane language for the browser than JavaScript, although JavaScript is not such a bad language, but suffers like PHP and VBA from being used by non-developers who come from web design side and try a little JavaScript as part of their work, tripping into each of the pitfalls that we developers have already had some time ago when we had our first experience.
Libraries prove to be hard. They are huge and it is hard to transfer them. Optimization is needed to deal with this, like for Android development.
Reflection is not available on scala.js. Many things do not work because of that, but enough things to make it useful do work.
Serialization is another challenge, because many frameworks rely on reflection, but there seems to be a solution for that.
Integer types are a little bit crappy. JS only has double which can do 53 bit integers. Long has to be built from two doubles.

Introduction to Lambda Calculus

Maciek Makowski

Very theoretical talk. Lamba calculus is pure math or even more theoretical, pure theoretical informatics, but it can be made a complete programming language with some thinking. It can be used for dealing with issues like computability. Many nice proofs are possible. The theoretical essence of functional programming languages is there. Some key words: „Church Rosser Theorem“, „Programming with Lambda-Calculus“, „numbers as lambda expressions“ (church encoding), „y combinator“, „fixed point combinator“, „lambda cube“, „fourth dimension for Subtypes“, ….
Very small language, great for proofs, not relevant or applicable for practical purposes.

State of the Typelevel

Lars Hupel

Typelevel is inpired by Haskell. Libraries by them are scalaz, shapeless, spire, scalaz-stream, monocle and more.
We should strive to get correct programs and optimize where the needs arises.
The JVM integers are not good. Think of the silent overflow. Floats (float and double) are good for numerical mathematicians and scientists with knowledge in this area, who can deal with error propagation an numerical inaccuracy.
Off course numbers can be seen as functions, like this:
$x=f(.)$ mit $\bigwedge_{n \in \Bbb N: n>0} \frac{f(n)-1}{n} < x < \frac{f(n)+1}{n}$ Equality of real numbers cannot be decided in finite time. What is "Costate command coalgebra"? Monocle provides "lenses" and similar stuff known from Haskell... Good binary serialization formats are rare in the JVM world. How should the fear of scalaZ and monads be overcome? Remember: "A monad is a monoid in the category of endofunctors. So what is the problem?" as could be read on Bodil Stokke’s T-shirt.

Slick: Bringing Scala’s Powerful Features to Your Database Access

Rebecca Grenier

Slick is a library that generates and executes SQL queries. The conceptional weaknesses of JPA and Hibernate are avoided.
It has drivers for the five major DBs (PostgreSQL, mySQL/mariaDB, Oracle, MS-SQL-Server and DB2) and some minor DBs, but it is not free for the three commercial DBs.
Inner and outer joins are possible and can be written in a decent way.
With database dictionaries slick is now even able to generate code. Which I have done, btw. a lot using Perl scripts running on the DDL-SQL-script. But this is better, off course…

Upcoming in Slick 2.2

Jan Christopher Vogt

Monads haunt us everywhere, even here. Time to learn what they are. I will be giving a talk in the Ruby-on-Rails user group in Zürich, which will force me to learn it.
Here they come: monadic sessions….
Sessions in conjunction with futures are the best guarantee for all kinds of nightmares, because the SQL is sometimes executed when the session is no longer valid or the transaction is already over. When dealing with transactional databases a lot of cool programming patterns become harder. Just think of the cool java guys who execute stuff by letting a EJB-method return an instance of an inner class with the DB-session implicitely included there and calling a method which via JPA indirectly and implicitely does DB-access long after the EJB-method is over. Have fun when debugging this stuff. But we know about it and address it here.
At least Slick is theoretically correct, other than JPA which I conject to be theoretically incorrect, apart from the shortcomings of the concrete implementations.
Several statements can be combined with andThen or a for-comprehension. Be careful, by default this uses separate sessions and transactions, with very funny effects. But threads and sessions are expensive and must not be withheld during non-running non-SQL-activities by default. Reactiveness is so important. Futures and thread pools look promising, but this fails miserably when we have blocking operations involved, that will occupy our threads for nothing.
We would like to have assynchronous SQL-access, which can be done on DB- and OS-level, but JDBC cannot. So we have to work around on top of JDBC. Apart from using a reasonably low number of additional threads this approach seems to be viable.
Statically type checked SQL becomes possible in the future.

No more Regular Expressions

Phil Wills

I love the regex of Perl. Really. So why do effort to give up something so cool, even in non-perl-languages?
It is not as bad as it sounds. We retain regular expressions as a concept, just do not call them like that (for marketing reasons I assume) and write them differently. Writing them as strings between // is very natural in Perl, but it breaks the flow of the language in Scala. A typical programmatical scala-like approach is more natural and more type safe. And more robust in case of errors. org.paraboiled2 can be used. Capture is unfortunately positional, unlike in newer Perl-regex, where captures can be named. But it hurts less here.

Scala eXchange – Q&A Panel

Jon Pretty, Kingsley Davies, Lars Hupel, Martin Odersky, and Miles Sabin

Interesting discussions…

Why Scala is Taking Over the Big Data World

Dean Wampler

‚“Hadoop“ is the „EJB“ of our time.‘
MapReduce is conceptionally already functional programming. So why use Java and not Scala?
Some keywords: „Scalding“, „Storm“, „Summing bird“, „Spark“.
Scala can be more performant than python, which is so popular in this area, but migration has to be done carefully.

Case classes a la carte with shapeless, now!

Miles Sabin

Example: tree structure with backlinks. Hard to do in strict immutabilty. Shapeless helps.

Reactive Programming with Algebra

André Van Delft

Algebra can be fun and useful for programming. Algebraic interpretations were introduced.
Page is subscript-lang.org.
Algebra of communicationg processes. It is very powerful and can even be applied to other targets, for example operation of railroad systems.
Every program that deals with inpout is in its way a parser. So ideas from yacc and bison apply to them.

High Performance Linear Algebra in Scala

Sam Halliday

Lineare Algebra has been addressed extremely well already, so the wheel should not be reinvented.
TL;D, Netflix and Breeze.
Example for usage of that stuff: Kalman Filter.
netlib has reference implementation in Fortran, a well defined interface and a reliable set of automatic tests. How do we take this into the scala world?
Fortran with C-Wrapper for JNI. (cblas)
compile Fortran to Java. really.
Alternate implementations of the same test suite in C.
High-Performance is not only about speed and memory alone, but about those under the given requirements concerning correctness, precision and stability.
Hardware is very interesting. The CPU-manufacturers are talking with the netlib team.
Can GPU be used? Off course, but some difficulties are involved, for example transfer of data.
FPGA? maybe soon? Or something like GPU, without graphics and operating on the normal RAM?
We will see such stuff working in the future.

An invitation to functional programming

Rúnar Bjarnason

Referential transparency, something like compatibility with the memoize pattern.
Pure functions…
Parallelization..
Comprehensiveness.. The all time promise, will it be kept this time?
Functional programming is not good for the trenches of real life project, but for getting out of the trenches. This should be our dream. Make love not war, get rid of trenches…

Building a Secure Distributed Social Web using Scala & Scala-JS

Henry Story

Spargl is like SQL for the „semantic web“.
Developed with support from Oracle.
We can have relativiity of of truth while retaining the absolute truth. The speech was quite philosophical, in a good way.
Graphs can be isomorphic, but have a different level of trust, depending on where the copy lies.
Linked data protocol becomes useful.
How is spam and abuse avoided? WebID?
We are not dealing with „Big Data“ but with massively parallel and distributed „small data“.

TableDiff – a library for showing the difference between the data in 2 tables

Sue Carter

What is the right semantics for a diff?
What do we want to see? How are numbers and strings compared when occurring in fields?
Leave timestamps that obviously differ but do not carry much information out.

Evolving Identifiers and Total Maps

Patrick Premont

Idea is to have a map where get always returns something non-null. Smart type concepts avoid the compilation of a get call that would not return something.
Very interesting idea, but I find it more useful as theoretical concept rather than for practical purposes. The overhead seems to be big.

Summary

Overall it was a great conference.

Scala Exchange 2014

English

Ich war am 8. und 9. Dezember 2014 auf der Konferenz Scala Exchange ( #scalaX ) in London.

Von mir besuchte Vorträge waren etwa folgende:

The Binary Compatibility Challenge

Martin Odersky

Es gibt Beispiele von allen vier Kombinationen von Sourcecode- und Binärkompatibilität.
Man wünscht sich von beidem mehr, Schwerpunkt heute aber Binärkompatibilität.
Konflikt für Scala: Innovation vs. Kompatibilität. Java hat den einen Extrempfad gewählt, Kompatibilität über alles, hat es aber auch leichter gehabt, weil Java die JVM mit „kontrolliert“. Clojure, Ruby, JRuby, Perl,… haben alle kein Problem mit Binärkompatibilität, weil sie in der Regel „just in time“ compiliert werden, also nur Quelltexte herumgereicht werden.
Reproduzierbare Builds sind in Scala schwierig, man denke alleine an die viele Build-Tools (ivy, gradle, maven, sbt,…)
Idee: nach etwa 10 der etwa 30 Schritte des Kompilierens den Baum des Programms in einem cleveren Binärformat speichern. Dieses Format ist ein bessere Kompromiss und von dort kann man leichter fertig-kompilieren.

REST on Akka: Connect to the world

Mathias Doenitz

Akka-http ist quasi Spray 2.0 oder Nachfolger für Spray.
Das sollte wegen der reactive Streams in Akka sein.
Verwende TCP-Flow-Control für „Backpressure“.

Bootstrapping the Scala.js Ecosystem

Haoyi Li

Scala wird nach Javascript statt JVM compiliert. Target ist eindeutig der Browser, weniger serverseitiges JS, wo man ja die JVM meist einsetzen kann.
Vorteil für Web-Applikationen: selbe Tag-Generierung, Validierung etc. auf Browser- und Serverseite. Eleganter als zwei Sprachen.
Einschränkungen: Libraries zu übertragen ist schwierig, da sie groß sind.
Keine Reflection auf scala.js verfügbar. Damit geht vieles nicht, aber es bleibt genug, was geht. Serialisierung eine Herausforderung, aber gelöst.
Testing riesige Herausforderung, gelöst halbwegs mit Teilmenge von scalatest.
Integer-Typen sind ein bisschen ein Gebastel, weil JS nur double kennt, was 53 bit entspricht. Long muss also mit zwei doubles nachgebildet werden.

Introduction to Lambda Calculus

Maciek Makowski

Sehr theoretischer Vortrag. Lambdacalculus wie Programmiersprache, Berechenbarkeitstheorie etc. Viele schöne Beweise möglich. Die theoretische Essenz der funktionalen Programmierung ist das. Stichworte: „Church Rosser Theorem“, „Programmierung mit Lambda-Kalkül“, „Zahlen als Lambda-Ausdrücke“ (church encoding), „y combinator“, „fixed point combinator“, „lambda cube“, „vierte Dimension für Subtypen“, ….
Sehr kleine Sprache, toll für Beweise, nicht für die Praxis brauchbar.

State of the Typelevel

Lars Hupel

Typelevel ist von Haskell inspiriert. Bibliotheken u.a. scalaz, shapeless, spire, scalaz-stream, monocle,….
Wir sollten anstreben, korrekte Programme zu schreiben und optimieren wenn nötig.
Die JVM-Integer-Typen sind nicht gut. Fließkommazahlen sind gut für numerische Mathematiker und in dem Bereich gebildete Wissenschaftler, die sich mit Fehlerfortpflanzung auskennen.
Natürlich behandeln wir Zahlen als Funktionen, z.B.
$x=f(.)$ mit $\bigwedge_{n \in \Bbb N: n>0} \frac{f(n)-1}{n} < x < \frac{f(n)+1}{n}$
Gleichheit von Reelen Zahlen ist nicht in endlicher Zeit entscheidbar.
Was ist „Costate command coalgebra“? Monocle behandelt „lenses“ und ähnliche Dinge, die man aus Haskell kennt…
Gute binäre Serialisierungsformate sind in der JVM-Welt rar.
Wie geht man mit der Angst vor scalaZ und Monaden um?

Slick: Bringing Scala’s Powerful Features to Your Database Access

Rebecca Grenier

Slick ist eine Library, die SQL-Queries generiert und dann ausführt. Die konzeptionellen Schwächen von JPA werden geschickt umgangen.
Hat Treiber für die fünf großen DBs und einige kleinere. Aber für Oracle, DB2 und MS-SQL-Server nicht frei.
Innere und äußere Joins sind verfügbar und elegant zu schreiben. Slick kann mit dem Datenbank-Dictionary sogar Code generieren.

Upcoming in Slick 2.2

Jan Christopher Vogt

Monaden kommen auch hier vor. Zeit das endlich zu lernen. Ich werde einen Vortrag in der Ruby-on-Rails-Usergroup darüber halten, dann muss ich es lernen.
Monadische Sessions…
Sessions in Kombination mit Futures gibt lustige Albträume.
Wenigstens ist Slick theoretisch korrekt, im Gegensatz zu JPA.
Mehrere Statements kombinieren mit andThen oder for. Achtung, default verschiedene Sessions.
Threads sind teuer, Reactiveness ist wichtig. Futures und Threadpools, geht aber schief beim „blocking“.
JDBC kann nicht assynchron. Workaround oberhalb von JDBC scheint aber ausreichend zu sein und nur ein paar mehr Threads zu brauchen als die richtige Lösung, also verantwortbar.
Statisch gechecktes SQL?

No more Regular Expressions

Phil Wills

Ich mag Regex in Perl sehr. Warum also so etwas aufgeben?
Nun, man gibt es nicht wirklich auf, ändert nur die Schreibweise.
Die Schreibweise als String ist in Perl natürlich, in Scala ein Fremdkörper.
Daher typische programmatische Schreibweise angemessener, aber auch robuster bei Fehlern.
Verwende org-paraboiled2
Capture lieder positionell, tut aber viel weniger weh als bei klassischen regex.

Scala eXchange – Q&A Panel

Jon Pretty, Kingsley Davies, Lars Hupel, Martin Odersky, and Miles Sabin

Einige interessante Diskussionen…

Why Scala is Taking Over the Big Data World

Dean Wampler

Zitat (übersetzt): ‚“Hadoop“ ist das „EJB“ unserer Zeit.‘
MapReduce ist konzeptionell eigentlich schon funktionales Programmieren. Warum also Java und nicht Scala??
Stichwörter: „Scalding“, „Storm“, „Summing bird“, „Spark“.
Scala kann performanter als Python sein, das hier beliebt ist. Aber nicht überstürzt ablösen.

Case classes a la carte with shapeless, now!

Miles Sabin

Beispiel: Baum mit Rücklinks. Schwierig mit konsequenter Immutability. Shapeless hilft.

Reactive Programming with Algebra

André Van Delft

Algebra kann Spaß machen und nützlich für die Programmierung sein. Algebraische Interpretation eingeführt.
Webseite subscript-lang.org.
Algebra der kommunizierenden Prozesse. Sehr mächtig, auch für andere Gebiete anwendbar, etwa Betrieb von Bahnsystemen.
Jedes Programm, das Eingaben behandelt, ist auf eine Art ein Parser, also Ideen von yacc und bison interessant auch hier.

High Performance Linear Algebra in Scala

Sam Halliday

Lineare Algebra ist sehr gut gelöst, also sollte man das Rad nicht neu erfinden.
TL;D, Netflix und Breeze. Anwendungsbeispiel: Kalman Filter.
netlib hat Referenzimplementierung in Fortran. Wie bringt man das in die Scala-Welt?
Fortran mit C-Wrapper versehen, für JNI erreichbar. (cblas)
Fortran nach Java kompilieren. Ja.
Alternative Implementierung mit derselben Testsuite in C.
High-Performance geht nicht nur um Geschwindigkeit per se, sondern immer unter dem Aspekt der Korrektheit, Genauigkeit und Stabilität.
Hardware ist interessant: Die CPU-Hersteller reden mit dem netlib-Team.
Kann man GPU benutzen? Ja, aber Transfer der Daten schwierig.
FPGA? Vielleicht bald?
Oder sowas wie GPU, aber ohne echte Grafik und mit dem normalen RAM?

An invitation to functional programming

Rúnar Bjarnason

Referenzielle Transparenz, etwa die Kompatibilität mit dem Memoize-Pattern.
Pure Functions…
Parallelisierung
Verständlichkeit ist das ewige Versprechen. Warum wird es diesmal gehalten?
Funktionale Programmierung ist nicht gut für die „Schützengräben“ der reellen Aufgaben.
Aber gut, um aus den Schützengräben rauszukommen in vernünftigere Welten… So der Anspruch…

Building a Secure Distributed Social Web using Scala & Scala-JS

Henry Story

Spargl ist wie SQL für das „semantic web“.
Entwickelt mit Unterstützung von Oracle.
Wir können Relativität der Wahrheit haben, während wir die absolute Wahrheit aufrechterhalten. Der Vortrag war recht philosophisch.
Graphen können isomorph sein, aber verschieden hohes Vertrauen genießen, je nachdem, wo sie liegen.
Linked Data Protocol kommt ins Spiel
Wie verhindert man Spam und Missbrauch? WebID?
Hier geht es nicht um „Big Data“, sondern um massiv verteilte und parallele „small data“.

TableDiff – a library for showing the difference between the data in 2 tables

Sue Carter

Was ist für ein Diff die richtige Semantik?
Was will man sehen? Wie werden Zahlen und Zeichenketten in den Feldern verglichen?

Evolving Identifiers and Total Maps

Patrick Premont

Idee ganz kurz: eine Map, deren Get immer etwas zurückgibt. Durch geschickte Typ-Konzepte wird verhindert, dass ein Aufruf, der ins Leere greifen würde, überhaupt compiliert.
Interessante Idee, finde sie aber eher theoretisch nützlich.

Devoxx 2014 in Belgium

Deutsch

2013

2012

In 2014 I have visited the Devoxx conference in Antwerp in Belgium.

Here are some notes about it:

What is Devoxx?

Devoxx ist a conference organized by the Belgian Java User Group.
Belgium is trilingual (French, Flemish and German), but the conference is 100% in English.
The location is a huge cinema complex, which guarantees for great sound, comfortable seats and excellent projectors. It is cool.
8 tracks, overflow for keynotes
Well organized (at least this year), more fun than other conferences…
sister conferences:

Devoxx FR
Devoxx PL
Devoxx UK
Voxxed (Berlin, Ticino,….)

Topics & main Sponsors

Java / Oracle
Android / Oracle
Startups, Business, IT in enterprises / ING-Bank
Java-Server, JBoss, Deployment / Redhat
JVM-languages
Web
SW-Architecture
Security
Whatever roughly fits into these lines and is considered worth being talked about by the speaker and the organizers…

These are some of the talks that I have attended:

Scala and Java8

Many conceptional features of Scala have become available in Java 8 with lambdas.
Problem: different implementation and interoperability between Java and Scala.
Development of Scala will make lambdas of Scala and Java interoperabel.

Monads

Concept from category theory. (5% of mathematicians do algebra, 5% of algebraians do category theory, but this very abstract and very theoretical piece of math suddenly becomes interesting for functional programming. Off course our functional programming world lacks the degree of infiniteness that justifies the theory at all, but concepts can be applied anyway)
Monoid (+, *, concat,…)
Functor
Monad
Wikipedia

Wikipedia de

$(T, \eta, \mu)$
example: List with a functor $F: (A\rightarrow B)\rightarrow (List[A]\rightarrow List[B])$
$\mu$ is flatten: $List[List[A]]\rightarrow List[A]$ ; $\eta: A\rightarrow List[A]$

Probability & Decisions

Example: Software for automatic steering of house infrastructure
Heuristics and probability theory
False positives / false negatives: what hurts? (usually both)
Very good explanation of probability theory and its use

Clojure

Clojure is another JVM-language
It is a Lisp-Dialekt, recognizable by its source having an abundance of opening and closing parentheses: (+ (* 3 4) (* 5 6))…
strong support for functional programming.
Dynamically typed (for us: Just think of everything being declared as „Object“ and implicit casts being performed prior to method calls.
After Java itself, Scala, Groovy and Javascript it appears to me to be the fifth most common JVM-language

MapReduce

„No one at Google uses MapReduce anymore“
Google has replaced it with more general and more performance sensitive concepts and implementations.
Optimized: save steps, combine them etc.
Can be used as cloud service (Cloud Dataflow)

Key Note ING

ING considers itself to be an „open bank“
Not the money is lieing around openly for burglers to play with it, but they claim to be open for new ideas.
Mobile app is the typical interface to the bank.
IT has a lot of influence („IT driven business“)
Feasability from the IT side is considered important
Agile Prozesses (Scrum) vs. Enterprise IT
IT has slowly moved to these agile processes.
„Enterprise IT is what does not work“

Material Design

GUI-Design with Android and Web Material Design
Visual ideas available for both platforms
Polymer design for Web

SW-Architecture with Spring

Spring 4.1
„works with WebSphere“
DRY
Lambda from Java8 can simplify many APIs out of the box by just replacing one-method anonymous and inner classes.
Generic Messaging Interface (wasn’t JMS that already???)
Caching, be careful when testing, but can be disabled.
Test on start.spring.io
Spring works well with Java. Also with Groovy, which comes from the same shop as spring. Combination with Scala „experimental“

Lambda_behave

High-Level testing-Framework
Uses Java8-Features (Lambda etc.)
Description in natural language.
Failure-messages are human readable
Like Cucumber…
Source of randomness can be configured. This is very important for monte-carlo-testing, simulations and the like.

Builtin Types of Scala and Java

In Java we find „primitive types“ (long, int, byte, char, short, double,…)
Probleme with arithmetic with int, long & Co: Overflow happens unnoticed
With float and double Rounding errors
With BigInteger, BigDecimal, Complex, Rational error prone, clumpsy and unreadable syntax.
In Scala we can write a=b*c+d*e even for newly defined numerical types.
Remark: Oracle-Java-guys seem to consider the idea of operator overloading for numerical types more interesting than before, as long as it is not used for multiplying exceptions with collections and the like.
Spire library

Future of Java (9, 10, …)

Part I

Q&A-meeting (questions asked via twitter)
Numerical types are in issue. That primitive types behave as they do and are kind of the default won’t change.
Generics and type erasure (where is the problem)?
Jigsaw vs. Jars vs. OSGi still open how that will fit together, but jar is there to stay.
Jigsaw repository: Could well be located with maven central. Oracle does not work in such a way that this being hosted directly by Oracle is likely to happen, if third party software is there as well.

Part II

Benchmarking with Java is hard because of hot spot optimization
JMH is a good tool
New ideas are always hard to introduce because of the requirement of remaining compatible with old versions.
Java might get a „repl“ some day, like irb for Ruby…

Part III

Collection literals (promised once for Java 7!!!) did not make it into Java 8, unlikely for Java 9
With upcoming value types this might be more reasonable to find a clean way for doing that.
For Set and List somthing like
new TreeSet(Arrays.asList(m1, m2, m3,…., mn))
works already now
For maps something like a pair would be useful. Tuples should come and they should be based on value types. The rest remains as an exercise for the reader.

Part IV

Tail-Recursion can now be optimized in an upcoming version.
Because of the security-manager, that analyzed stacktraces this was impossible for a long time. (weird!!!)
C and Lisp have been doing this for decades now…
Statement: Generics are hard, but having understood them once they become easy. So keep trying….
Covarianz und Contravarianz (Bei Array falsch gelöst)

Part V

Arrays 2.0: indexing with long could become an issue. Some steps towards list, but with array syntax. (studies and papers only)
Lists have two extreme implementations: ArrayList and LinkedList. We would love to see more „sophisticated“ Lists, maybe some hybrid of both
Checked exceptions: critical issue, it was a problem with generics and lambda. And way too many exceptions are checked, just think of whatever close()-methods can throw, that should not be checked.

Semantic source code analysis

Useful for high level testing tools
Static and dynamic analysis
Dataflow analysis: unchecked data from outside, think of SQL-injection, but also CSS, HTML, JavaScript, JVM languages and byte code

Functional ideas in Java

Functional:

Functions or methods are „first class citizens“
Higher order functions (C could that already)
Closures
Immutability (function always returns the same result)
„lazy“-constructions can be possible though
For big structures we always have the question of immutability vs. performance
But functional is much more thread-friendly

50 new things in Java8

Part I

Lambda (see below)
Streams (see below)
Default implementations in interfaces
Date/Time (loke Joda time)
Optional (better than null)
Libraries can work with lambda
Parallel (use with care and only when needed and useful)

Part II

String.join()
Something like „find“ in Unix/Linux
Writing comparators is much easier
Maps of Maps, Maps of Collections easier
Sorting is better: quicksort instead of mergesort, can be parallelized

Groovy for Android

Problem with JVM languages other than Java: library has to be included in each app. 🙁
Solution: jar optimization tool helps
Second problem: dynamic languages have to be compiled on demand on the device
Solution: „static“ programming, dynamic features possible but not performing well

Lambdas

Lambdas are anonymous functions
Idea given: interface XY with one method uvw()
Instead of
XY xy = new XY() { public long uvw(long x) { return x*x } };
new
XY xy = x -> x*x;
shorter, more readable, easier to maintain, interface becomes superfluous in many cases.
Closure means that final variables from the surrounding context can be included
Instance methods can be seen as closures also, the include the instance in a closure like way.

Streams

Streams are somewhere in the vicinity of Collection, Iterable, Iterator and the like, but something new.
They have methods that allow a function to be applied on all elements
Elegant for programming stuff like

Sum
Product
Maximum
Minimum
First / last / any element with certain property
all elements with a certain property
all transformed Elements…

It turns out to be a wise decision to make it different from Iterable, Iterator, Collection,… and rather provide wrapping capabilities where needed.