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.

Share Button

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.

Share Button

Devoxx 2014

Im Jahr 2014 habe ich die Devoxx in Antwerpen besucht.

Hier sind ein paar Notizen dazu:

Was ist Devoxx?

  • Devoxx ist eine Konferenz der belgischen Java-User-Group
  • Belgien ist dreisprachig, Konferenz aber 100% in Englisch
  • Lokation in riesigem Kinokomplex guter Sound, gute Sitze, gute Projektoren, „cool“
  • 8 tracks, bei Keynotes „overflow“
  • Gut organisiert (dies Jahr sicher), unterhaltsamer als andere Konferenzen…
  • Schwesterkonferenzen:
  • Devoxx FR
  • Devoxx PL
  • Devoxx UK
  • Voxxed (Berlin, Ticino,….)

Themen & Hauptsponsoren

  • Java / Oracle
  • Android / Oracle
  • Startups, Business, IT in Großfirmen / ING-Bank
  • Java-Server, JBoss, Deployment / Redhat
  • JVM-Sprachen
  • Web
  • SW-Architektur
  • Security
  • Was sonst noch so ins Umfeld passt und sich jemand traut, vorzutragen…

Scala und Java8

  • Viele Features von Scala sind mit java8-Lambdas auch in Java verfügbar
  • Problem: verschiedene Implementierung, Interoperabilität
  • Bestrebung Scala weiterzuentwickeln damit lambdas von Java und von Scala besser miteinander interoperabel sind.

Monads

  • Konzept aus der Kategorientheorie (5% der Mathematiker machen Algebra, 5% der Algebraiker machen Kategorientheorie, aber für funktionale Programmiersprachen plötzlich relevant)
  • Monoid (+, *, concat,…)
  • Funktor
  • Monad (de: Monade)
    Wikipedia de
    Wikipedia en
  • (T, \eta, \mu)
  • Beispiel List mit einem Functor F: (A\rightarrow B)\rightarrow (List[A]\rightarrow List[B])
    \mu ist flatten: List[List[A]]\rightarrow List[A]; \eta: A\rightarrow List[A]

Probability & Decisions

  • Thema: Software für automatische Steuerung
  • Heuristik auf Wahrscheinlichkeitstheorie
  • False positives / false negatives: was tut weh? (meistens beide…)
  • Wahrscheinlichkeitstheorie und Verwendung gut erklärt

Clojure

  • Clojure ist eine andere JVM-Sprache
  • Ein Lisp-Dialekt, zu erkennen daran, dass der Quelltext überwiegend aus runden Klammern besteht (+ (* 3 4) (* 5 6))…
  • Funktionales Paradigma stark unterstützt
  • Dynamische Typisierung (für uns: Alles als „Object“ deklariert, implizite Casts bei Methodenaufrufen)
  • Nach Java selbst, Scala, Groovy und Javascript die mir am fünfthäufigsten begegnende JVM-Sprache

MapReduce

  • „No one at Google uses MapReduce anymore“
  • Google hat das verallgemeinert
  • Optimierungen: spare Schritte, fasse zusammen etc.
  • Als Cloud-Service angeboten (Cloud Dataflow)

Key Note ING

  • ING versteht sich als „open bank“
  • Nicht gemeint, dass das Geld „offen“ rumliegt, aber offen für neue Ideen
  • Schnittstelle zur Bank ist Mobile-App
  • IT hat viel Einfluss („IT driven business“)
  • Man schaut, was gut machbar ist
  • Agile Prozesse (Scrum) vs. Enterprise IT
  • Umbau der IT auf diese agilen Prozesse schrittweise
  • „Enterprise IT is what does not work“

Material Design

  • Vortrag über GUI-Design mit Android und Web
    Material Design
  • Visuelle Ideen für beide Plattformen verfügbar
  • Polymerdesign für Web

SW-Architektur mit Spring

  • Spring 4.1
  • „works with WebSphere“
  • DRY
  • Lambda aus Java8 kann viele APIs vereinfachen statt anonymen inneren Klassen mit einer Methode
  • Generic Messaging Interface (war JMS nicht schon das???)
  • Caching, Achtung beim Testen abschaltbar
  • Testen auf http://start.spring.io/
  • Spring funktioniert mit Java gut, mit Groovy auch (aus demselben Haus…) mit Scala „experimentell“

Lambda_behave

  • High-Level testing-Framework
  • Verwendet Java8-Features (Lambda etc)
  • Beschreibung in natürlicher Sprache
  • Failure-Meldungen lesbar
  • Wie Cucumber…
  • Zufallsquelle konfigurierbar (extrem wichtig für manche Tests!!)

Builtin Types of Scala and Java

  • In Java gibt es „primitive“ (long, int, byte, char, short, double,…)
  • Probleme bei Arithmetik mit int, long & Co:  Überlauf findet unerkannt statt
  • Mit float und double Rundungsfehler
  • Mit BigInteger, BigDecimal, Complex, Rational fehleranfällige, umständliche und unlesbare Syntax
  • In Scala kann man a=b*c+d*e auch für neu definierte numerische Typen schreiben.
  • Anmerkung dazu: Oracle-Java-Leute finden Idee von Operator-Überladen für numerische Typen inzwischen interessant, solange man nicht Exceptions mit Collections multipliziert und durch Swing-Komponenten dividiert…
  • Spire library

Zukunft von Java (9, 10, …)

Teil I

  • Q&A-Sitzung (Fragen per Twitter schreiben)
  • Numerische Typen sind Thema. Dass primitive Typen sich so verhalten wie heute und quasi der „default“ sind, wird sich nicht ändern
  • Thema Generics und Type-Erasure (wo ist das Problem)?
  • Jigsaw vs. Jars vs. OSGi  noch offen, aber jar bleibt
  • Jigsaw-Repository  Wird man wohl bei maven-Central, Oracle funktioniert nicht so, dass sie jigsaw-Repository für third-Party bei sich hosten

Teil II

  • Benchmarking mit Java schwierig wegen hotspot-Optimierung
  • JMH gutes Tool dafür
  • Neue Ideen immer schwierig umzusetzen, weil man kompatibel zu alten Versionen sein will.
  • Java bekommt vielleicht „repl“

Teil III

  • Collection literals (für Java 7 versprochen!!!) sind für Java8 nicht gekommen, für Java9 unwahrscheinlich
  • Mit Value-Types aber eher zu haben, daher nicht vorher…
  • Für Set und List mittels
    new TreeSet(Arrays.asList(m1, m2, m3,…., mn))
    schon heute einigermaßen darstellbar
  • Für Maps wenn man sowas wie Pair-hätte, was wiederum auf „Tupel“ aufbaut, die kommen werden, wenn es Value-Types gibt

Teil IV

  • Tail-Recursion kann nun optimiert werden
  • Wegen Security-Manager, der Stacktrace analysiert hat, lange nicht möglich
  • C und Lisp können das seit Jahrzehnten…
  • Aussage: Generics sind schwierig, aber wenn man sie mal verstanden hat, sind sie leicht… Also „dranbleiben“
  • Covarianz und Contravarianz (Bei Array falsch gelöst)

Teil V

  • Arrays 2.0: Indizierung mit long möglich, ein bißchen wie List, aber mit Array-Syntax… (Studien und Papers, nicht konkret)
  • Listen haben heute extrem-Implementierung ArrayList und LinkedList. Wir wollen „sophisticated“ List vielleicht Hybrid
  • Checked-Exceptions: kritisches Thema, schwierig mit Generics und mit Lambda. Zu viele Exceptions sind checked. Z.B. bei close()

Semantische Quelltextanalyse

  • Hilfreich für High-Level-Testing-Tools
  • Statische und dynamische Analyse
  • Dataflow-Analyse: ungeprüfte Daten von außen  SQL-injection, aber auch CSS, HTML, JavaScript, JVM-Sprachen/Bytecode

Funktionale Ideen in Java

  • Funktional:
  • Funktionen oder Methoden sind „first class citizen“
  • Higher order Functions (konnte schon C)
  • Closure
  • Immutability (Funktion gibt immer dasselbe raus)
  • Unter der Tischdecke „lazy“-Konstrukte
  • Bei großen Strukturen immer Frage: Immutability vs. Performance
  • Aber Funktional ist Thread-freundlicher

50 new things in Java8

Teil I

  • Lambda (s.u.)
  • Streams (s.u.)
  • Default-Implementierungen in Interfaces
  • Date/Time (wie Joda-Time)
  • Optional (besser als null)
  • Libraries können mit Lambda arbeiten
  • Parallel (mit Vorsicht verwenden)

Teil II

  • String.join()
  • So was wie „find“ in Unix/Linux
  • Comparator schreiben einfacher
  • Maps of Maps, Maps of Collections einfacher
  • Sortieren besser: quicksort statt mergesort, parallelisierbar

Groovy für Android

  • Problem bei JVM-Sprachen außer Java: Bibliothek muss in jeder App mitkommen
  • Lösung: Tool zum jar-optimieren
  • Zweites Problem: dynamische Sprachen müssen auf Device „on demand“ kompiliert werden
  • Lösung: „statisch“ Programmieren, dynamische Features möglich, aber nicht performant

Lambdas

  • Lambdas sind anonyme Funktionen
  • Idee gegeben: Interface XY mit einer Methode uvw()
  • Statt
    XY xy = new XY() {
    public long uvw(long x) { return x*x }
    };
    neu
    XY xy = x -> x*x;
  • kürzer, lesbarer, wartbarer, man kann Interface oft sparen
  • Closure bedeutet, dass (final-)Variablen aus dem umgebenden Kontext dort eingebunden werden
  • Instanz-Methoden sind eigentlich auch Closure, sie binden die Instanz in der sie definiert sind Closure-mäßig ein.

 Streams

  • Streams sind im Dunstkreis von Collection, Iterable, Iterator, aber was anderes
  • Erlauben Methoden, die „Funktion“ auf alle Elemente loslassen
  • Elegant programmierbar sind Dinge wie
    • Summe
    • Produkt
    • Maximum
    • Erstes / Letztes Elment mit Eigenschaft
    • alle mit Eigenschaft
    • alle transformierten Elemente
  • Sinnvoll: nicht dasselbe wie Iterable, Iterator, Collection,…

 Links

Share Button

Scala Days in Berlin

English

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.

Share Button

Closures 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

Share Button

Getter und Setter

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.

Share Button

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.

Share Button

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.

Share Button

Besuch bei ScalaX

English

Gleich ein paar Wochen nach der Devoxx habe ich noch so eine Konferenz besucht, diesmal nur zwei Tage und unter dem Namen „Scala Exchange“ oder kurz #scalaX.
Es ging hauptsächlich um funktionale Programmierung und Architektur und das wiederum meistens recht „Scala-lastig“.
Die Vorträge waren um einiges anspruchsvoller als bei der Devoxx, aber das machte vielleicht auch den speziellen Reiz aus.

Interessante Vorträge waren unter anderem:

Share Button

Scala, Ruby, Perl,… – wann nimmt man was?

Wer einen goldenen Hammer hat, für den sieht jede Schraube wie in Nagel aus. Aber wir haben einen riesigen Werkzeugkasten und wie man sieht, überschneiden sich tatsächlich manche Werkzeuge in ihren Einsatzbereichen, aber das Universalwerkzeug ist nicht wirklich in Sicht oder doch nicht wirklich in allen Bereichen mit den Spezialwerkzeugen konkurrenzfähig.

Oft hat man ja Altlasten, also vorhandene Applikationen, die man erweitern oder ergänzen soll oder es sollen sogar neue, „in die Landschaft passende“ Applikationen hinzugefügt werden. Dann landet man bei Cobol, Railo, Fortran, C, Java, C#, C++, PL/SQL, PL/1, (Visual)Basic u.s.w. Wobei diese zum Teil sogar ihre sehr große „Nische“ haben, in der sie noch aktuell sind. Dass C für Systemprogrammierung noch sehr aktuell und fast konkurrenzlos ist, sei unbenommen.

Wenn keine Vorgaben durch Bibliotheken, Altlasten, IT-Landschaft u.s.w. bestehen, ist es natürlich interessant, in der zur Verfügung stehenden Zeit möglichst viel machen zu können. Eine Technologie, die einen zwingt, viel Zeit mit trivialen Aufgaben zu verbringen und die eigentlich interessanten Dinge in einem Wust von trivialem Code zu verstecken, den man nun einmal schreiben muss, darf man dann auch schon einmal hinterfragen. Letztlich sind zwei Wege vielversprechend, um mit wenig Code viel auszudrücken und letzlich in wenig Zeit viel zu entwickeln: Die funktionalen Sprachen wie z.B. F#, Clojure, Erlang, Elixir und Haskell. Oder die Skriptsprachen wie Ruby, Perl, Perl6 (wenn es mal fertig wird), Python und PHP. Natürlich überschneidet sich das ein Stück weit, weil einige funktionale Sprachen auch ein bißchen wie Skriptsprachen einsetzbar sind und einige Skriptsprachen auch gewisse funktionale Konstruktionen unterstützen.

Letztlich erweisen sich die funktionalen Sprachen als vielversprechend, wenn es darum geht, sehr leistungsstarke Applikationen zu entwickeln, die einen hohen Durchsatz und eine hohe Parallelisierung der Verarbeitung verwirklichen. Twitter soll mit Scala diesen Weg gegangen sein. Grundsätzlich bieten alle ernsthaften funktionalen Sprachen hier einige Möglichkeiten. F# lässt sich übrigens auch mit Mono kombiniert unter Linux verwenden. Vielleicht hat Erlang noch einen kleinen Vorteil, weil es schon auf VM-Ebene für diesen Einsatzbereich optimiert ist. Diese VM lässt sich aber auch mit Elixir verwenden. Aber man hat die Wahl zwischen mehreren Wegen.

Für viele Web-Applikationen hat sich Ruby als gut geeignet erwiesen, man sieht aber, dass es einige sehr gute PHP-Applikationen gibt. z.B. MediaWiki, die Software, mit der Wikipedia läuft. Allerdings zeichnet sich im Moment ein Trend ab, mehr von der Logik in Javascript auf der Client-Seite zu implementieren und serverseitig (fast) nur noch Webservices mit REST anzubieten, die die eigentliche Businesslogik und die Zugriffe auf die Daten zur Verfügung stellen. Diese REST-Services kann man natürlich in Ruby entwickeln; aber da gibt es viele Wege…

Ruby und vor allem Perl sind aber auch sehr stark, wenn es darum geht, Textdateien zu verarbeiten. Man kann diese nach Mustern durchsuchen, umgruppieren und umbauen und damit schöne Auswertungen machen. Für sehr große Datenmengen sollte man sich natürlich noch etwas eingehendere Gedanken machen, weil dann der Durchsatz und die Parallelisierung plötzlich mehr Bedeutung bekommen als das eigentlich Parsen des Texts. Aber man kann noch viel mehr…

Eine große Applikation kann diese Dinge auch kombinieren. GNU-Emacs ist eine sehr altes Beispiel, dass hier einen noch heute sehr aktuellen Ansatz verfolgt. Die Grundfunktionalität ist in C entwickelt und die weitergehenden Funktionen und Erweiterungen alle in Emacs-Lisp. So läßt sich ohne viel Aufwand einen Erweiterung einbinden, was nicht so leicht geht, wenn man erst einmal neu kompliieren muss. Die Idee lässt sich auch heute noch aufgreifen, wenn man eine Applikation z.B. in Scala entwickelt und dann die Möglichkeit anbietet, diese über Ruby- oder Groovy-Scripte anzusprechen, zu erweitern und zu konfigurieren.

Wenn man einmal an Häuser denkt, ist die Idee nicht so abwegig. Das eigentliche Haus ist relativ stabil aus Beton, Stein und Holz gebaut und bleibt in der Regel jahrzehntelang unverändert. Die Möbel sind selten aus Beton gegossen und eher flexibler (auch wenn sie vielerorts jahrzehntelang gleich stehen).

Share Button