Schachteln für Fortgeschrittene

Angeregt von dieser Frage auf Stackoverflow will ich mich heute mit geschachtelten Listen beschäftigen: Kann man eine Methode schreiben, die sowohl eine Liste von Ints wie auch eine Liste von Int-Listen wie auch eine Liste von Listen von Int-Listen u.s.w. aufsummieren kann? Sicher, das geht auch in Java – allerdings nicht typsicher: Da es dort keine Möglichkeit gibt, einen allgemeinen „Listen-Stapel-Typ“ zu definieren, muss gecastet werden, und das wiederum heißt, das Laufzeitfehler auftreten können, wenn ein ungeeignetes Objekt (sagen wir eine String-Liste) übergeben wird.

Wie sieht die Haskell-Lösung aus?

class Summable a where
  total :: a -> Int

instance Summable Int where
  total = id  

instance Summable x => Summable [x] where
  total = sum . map total  

total ([[[1,2,3],[4,5]],[[6],[7,8,9,10]]] :: [[[Int]]])
--55

Aha, Typklassen! Wir definieren eine Typklasse „Summable“, die eine Funktion „total“ zum Aufsummieren enthält. Die Instanz für Int ist trivial: Wir geben einfach die Zahl selbst zurück (man hätte dafür auch total x = x schreiben können). Interessanter ist die Instanz für Listen, die eine sogenannte Context-Bound enthält: Wenn a in der Klasse Summable ist, dann ist auch eine Liste von a in der Klasse – genau die Art von „Rekursivität“, die wir brauchen. Deshalb darf man in der Definition von total auch die Funktion total auf die Elemente anwenden, da man ja weiß, dass sie auch Summable sind. In der letzten Zeile wird die Funktion ausprobiert (dass man u.U. die Typangabe :: [[[Int]]] braucht, hat nichts mit unseren Typklassen zu tun, sondern ist der „Monomorphismus-Restriktion“ geschuldet, und wäre bei nicht-numerischen Typen nicht notwendig).

Wie setzt man das nun in Scala um? Ich habe mich zuerst mit einer typklassenartigen Implementierung versucht, bin aber nicht so recht weitergekommen. Am Ende hat dann eine etwas direktere Vorgehensweise zum Ziel geführt:

object nestedTest {
  
  case class Summable(total:Int)
   
  implicit def intSummable(i:Int) = Summable(i)
  
  implicit def listSummable[T <% Summable](list:List[T]) = Summable(list.map(_.total).sum)
  
  def total[T <% Summable](t:T) = t.total
  
  def main(args: Array[String]) {
    println(total(1))
    println(total(List(1,2,3)))
    println(total(List(List(1),List(2,3))))
    //println(total(List(List("a"),List("b","c")))) 
    //--> error: No implicit view available from List[List[java.lang.String]] => nestedTest.Summable.
  }
}

Summable ist jetzt keine Typklasse, sondern einfach ein Wrapper um Int. Dann definiere ich entsprechende Konvertierungen. Wieder ist die Umwandlung von Int nicht besonders spannend, dafür die Definition der List-Variante. Der entscheidende Trick ist die Verwendung einer View-Bound T <% Summable. Das heißt, dass T in ein Summable "umwandelbar" sein muss, und genau das ist der Trick, um Scala die gewünschte "Rekursivität" beizubringen. Durch die Garantie der View-Bound ist es erlaubt, map(_.total) zu schreiben, denn wir wissen ja, dass T in ein Summable konvertiert werden kann, und Summable hat ein Feld namens total. Für die Bequemlichkeit definieren wir noch eine Top-Level-Funktion für total, um dem Anwender das Hantieren mit Summable zu ersparen. In der main-Methode werden nun verschiedene Varianten ausprobiert. Ein Aufruf mit einem unpassenden Argument scheitert, und das sogar mit einer recht verständlichen Fehlermeldung.

Ich hoffe, dass das Beispiel gezeigt hat, dass Scalas Typsystem dem von Java auch bei recht praktischen Aufgabestellungen überlegen ist, auch wenn man manchmal etwas frickeln muss. Haskell glänzt hier mit einer sehr einfachen Variante, aber es gibt auch Konstrukte, die sich besser mit Scala implementieren lassen (z.B. alles mit variabler Anzahl Argumente).

Ich fasse schon einmal den guten Vorsatz, das Blog nächstes Jahr nicht ganz so stiefmütterlich zu behandeln. An spannenden Themen soll es nicht mangeln: Da wäre das gerade frisch releaste Ceylon (allerdings mit noch enttäuschenden Funktionsumfang), Bauarbeiten an Scala und Java, die tolle Sprache Frege, die langsam erwachsen wird und ihr Vorbild Haskell, bei dem auch interessante Neuerungen anstehen, wenn man Simon Peyton Jones glaubt.

Dann wünsche ich allen ein Frohes Fest, einen Guten Rutsch und ein erfolgreiches 2012!

Werbeanzeigen

Multiples Pattern-Matching

Auf Stackoverflow habe ich schon häufiger die Frage gelesen, wie man es anstellt, dass beim Pattern-Matching nicht nur der erste passende Fall berücksichtigt werden, sondern alle passenden Fälle. Eingebaut gibt es das leider nicht, es ist aber auch nicht schwer zu realisieren. Hier eine recht elegante Version von Philippe:

class MatchAll[S](scrutinee : =>S) {
  def matchAll[R](patterns : PartialFunction[S,R]*) : Seq[R] = {
    val evald : S = scrutinee
    patterns.flatMap(_.lift(evald))
  }
}

implicit def anyToMatchAll[S](scrut : =>S) : MatchAll[S] = new MatchAll[S](scrut)

Und die Anwendung:

(2,4) matchAll (
  { case (2,_) => "starts with two" },
  { case (3,_) => "starts with three" },
  { case (_,4) => "ends with four" },
  { case (a,b) if a + b == 6 => "adds up to six" }
)

//--> ArrayBuffer(starts with two, ends with four, adds up to six)

Ich denke, dass man mit der im Vergleich zu match leicht veränderten Syntax gut leben kann, und fände es gut, wenn dieses Konstrukt auch in die Scala-Bibliotheken aufgenommen würde.

Scala für Android mit Eclipse leicht gemacht

Ich habe bisher keine Android-Ambitionen, aber sicher einige von euch, und so habe ich diesen sehr ausführlichen Beitrag mit Erlaubnis des Autors Yves für euch übersetzt. Da ich die Anleitung nicht selbst nachvollzogen habe, kann es eventuell zu Ungenauigkeiten gekommen sein, also korrigiert mich bitte, wenn euch etwas auffällt.

Scala für Android mit Eclipse leicht gemacht

Man kann mit Scala auf Android entwickeln, und es ist nicht besonders schwierig. Trotzdem habe ich ein paar Tage gebraucht um alle relevanten Informationen zu sammeln, und eine Konfiguration zum Laufen zu bringen. Ich denke, dass euch das interessieren könnte, insbesondere weil man nicht einmal 15 Minuten braucht, um eine Umgebung aufzusetzen.

Ich bin der Ansicht, dass man als Entwickler die Möglichkeit haben sollte, so oft compilieren und testen zu können wie nötig. Alles, was einen ausbremst, wie zusätzliche Schritte im Build-Prozess (Treeshaker, ProGuard mit einem Ant-Build), sollte vermieden werden. Ich gehe davon aus, dass während des Entwicklungsprozesses vorwiegend das Android Virtual Device anstatt das tatsächlichen Gerätes verwendet wird. Weiterhin setze ich voraus, dass du kein Ant verwenden willst, sondern wie ich den integrierten Eclipse-Buildprozess.

Wenn Android neu für dich ist (wie es für mich war), kann es nicht schaden, ein paar Grundlagen zu kennen (für Android SDK 12):

  • Eine Eclipse-Umgebung für Android aufzusetzen ist nicht schwer. Das ADT-Plugin ist einfach zu installieren und zu benutzen.
  • Wahrscheinlich möchtest du wenigstens ein Android Virtual Device (AVD) aufsetzen, um dein Programm testen zu können (wenn du auf einem echten Gerät testen willst, gilt dieser Tipp nicht für dich)
  • Eine Android-Anwendung ist eine einzelne .apk-Datei, und diese kann keine Bibliotheken außer denen von Android verwenden. Das heißt, dass die Anwendung alle Bibliotheken enthalten muss, die man verwenden will. Oder man kann das Gerät so manipulieren, dass es zusätzliche Bibliotheken lädt, aber das ist natürlich keine Lösung für Anwendungen, die verteilt werden sollen.
  • Man verwendet Java/Scala zur Entwicklung, aber Android benutzt eine eigene, spezielle VM (Dalvik), und der Code muss von .class-Dateien zu Plattform-Code compiliert werden. Das wird vom dx-Compiler erledigt (man kann ihn direkt in den SDK-Tools aufrufen, aber das ist normalerweise unnötig), der eine classes.dex-Datei erzeugt. Diese Datei enthält alle Klassen der Applikation, ähnlich wie ein Jar. Das dx-Tool und die Dalvik-Plattform akzeptieren nicht alles: Einige Klassen compilieren mit dx, werden aber nicht korrekt von Dalvik geladen, und das dx-Tool ist ziemlich beschränkt bezüglich der Menge an Code, mit der es zurechtkommt. Man verwendet Werkzeuge, um den Code und die Bibliotheken auf das absolute Minimum abzuspecken (Treeshaker, ProGuard.). Insbesondere kann dx nicht die vollständige Scala-Bibliothek verarbeiten (zu groß), und Dalvik kommt nicht mit Version 2.9.0 zurecht (es scheitert beim Laden).
  • Das SDK enthält einige nützliche Werkzeuge, besonders adb, womit man bestimmte Befehle an ein laufendes virtuelles Gerät senden kann (und wahrscheinlich auch an ein echtes, aber das habe ich nicht probiert). Insbesondere kann man mit dem „adb shell“-Kommando einige eingeschränkte Unix-Befehle senden. Die Details sind im SDK beschrieben. Aber vermutlich wirst du damit nicht allzuviell zu tun haben.

Demnach ist das Problem, was wir mit Scala haben, dass wir alles von uns benötigte aus der Scala-Bibliothek in die Android-Anwendung packen müssen, aber das funktioniert nicht, weil das Ergebnis zu groß für dx ist. Die normale Lösung ist, dem Build einen Schritt zum Zurechtstutzen des Codes hinzuzufügen, aber das erfordert die Verwendung einen eigenen Ant-Builds. Das beim ADT mitgelieferte ProGuard läuft nur, wenn man tatsächlich die Applikation auf ein Gerät exportiert, um sie dort auszuführen, aber nicht bei normalen Durchläufen, und selbst wenn das möglich wäre, würde natürlich der Schrumpf-Schritt jedesmal ausgeführt werden, wenn man speichert und neu compiliert. Das wollen wir nicht.

Stattdessen muss die Umgebung, die wir haben wollen, die Scala-Bibliotheken innerhalb des virtuellen Gerätes bereitstellen (so dass dem Build-Prozess entgehen). Dazu bedienen wir uns Tipps von folgenden Seiten:

Die erste Seite verlinkt eine Liste vorcompilierter Ramdisks für Android. Ich nehme api_10, aber du kannst auch andere verwenden. Die zweite Seite verweist auf einige vorcompilierte Jars für Android. Dazu später mehr.

Selbstverständlich wollen wir die aktuellsten verfügbaren Werkzeuge:

  • Eclipse 3.7 (Indigo)
  • Android SDK release 12
  • ADT Plugin
  • Scala 2.9.0; allerdings sind wir hier aufgeschmissen, weil diese Version von Scala nach dem Compilieren für Android nicht richtig lädt (es gibt ein Problem in den Collections-Packages), deshalb verwenden wir Scala 2.8.1, das funktioniert. Und da wir ein Plugin benötigen, das unter Eclipse 3.7 arbeitet, werden wir das experimentelle 2.8.2 Release verwenden (Update-Seite)

Nun zum Kern der Sache:

  • Lade Eclipse Indigo (3.7) herunter und installiere es
  • Lade das Android SDK 12 herunter und installiere es
  • Installiere das Android ADT Plugin
  • Setze den SDK-Pfad in Einstellungen => Android
  • Lade das Android Ramdisk Image von (A) für die von dir gewünschte(n) Version(en) herunter
  • Suche darin die für dich passende ramdisk.img-Datei und kopiere sie ins Verzeichnis {android-sdk}/platforms/android-XX/images (du solltest vorher eine Kopie der ursprünglichen ramdisk.img-Datei sichern)
  • Erstelle ein virtuelles Gerät entsprechen der gerade von dir geänderten Verion. Du kannst dazu den AVD-Manager verwenden, der in Eclipse integriert ist, nacdem das ADT-Plugin installiert wurde.
  • Starte das virtuelle Gerät. Das wird etwas dauern. Nutze die Zeit für die folgenden drei Schritte.
  • Installiere das Scala-Plugin für Version 2.8.2
  • Lade von (B) die vorbereiteten Scala-Bibliotheken mit Version 2.8.1 herunter (nciht vergessen, 2.9.0 lädt nicht korrekt in Android!)
  • Entpacke sie und öffne eine Shell (cmd unter Windows), und gehe dann in das Verzeichnis, in das du die 5 Scala Jars entpackt hast.
  • Nachdem das virtuelle Gerät bereit ist, sende die folgenden Befehle in der Shell:
    • {android-sdk}/platform-tools/adb shell mkdir -p /data/framework (wenn das nicht klappt, hast du etwas in einem der vorherigen Schritte vergessen)
    • {android-sdk}/platform-tools/adb push scala-library.jar /data/framework
    • {android-sdk}/platform-tools/adb push scala-collection.jar /data/framework
    • {android-sdk}/platform-tools/adb push scala-immutable.jar /data/framework
    • {android-sdk}/platform-tools/adb push scala-mutable.jar /data/framework
    • {android-sdk}/platform-tools/adb push scala-actors.jar /data/framework
    • {android-sdk}/platform-tools/adb shell sync
  • Schließe das virtuelle Geräte und starte es neu (ich bin nicht sicher, ob das erforderlich ist)
  • Erstelle ein neues Android-Projekt in Eclipse
  • Füge irgendwo eine Scala-Datei hinzu, und rechts-klicke dann auf das Projekt: Konfiguration => Scala Natur hinzufügen

Fertig! Du kannst nun sowohl in Java wie auch in Scala entwickeln. Ich würde dringend davon abraten die Android Activity-Klasse zu „scalafizieren“, die für dich erstellt wurde. Speichern und Kompilieren ist so schnell wie man es sich wünscht. Der Programmablauf ist nur durch die Art des Emulators beschränkt, nicht durch die Verwendung von Scala.

Ich überlasse euch selbst den letzten, ultimativen Schritt der Verteilung der Anwendung auf ein Gerät. Wenn ihr das Projekt korrekt konfiguert habt, denke ich aber, dass das ProGuard (der dann und nur dann verwendet wird, wenn die Anwendung wirklich exportiert wird) problemlos erledigen wird.

Yves

Resteverwertung

Als Ergänzung zu meinem Pattern-Matching-Artikel heute ein kleiner Trick, der mir eher zufällig über den Weg gelaufen ist.

Ich hatte dazumal folgendes Codebeispiel gebracht, um zu zeigen, wie man die restlichen Elemente einer Collection beim Pattern Matching erfolgreich ignorieren kann:

def test(list: List[String]) = list match {
  case List("1","2", _*) => "one, two ..."
  case _ => "dunno"
}

Jetzt fragt man sich natürlich, wie man vorgehen muss, wenn man den Rest eben nicht ignorieren will, sondern auch diesen an eine Variable gebunden haben möchte. Die „naive“ Lösung mit etwas wie rest* funktioniert jedenfalls schon einmal nicht. Aber es geht trotzdem, und zwar dank Klammeraffen:

def test(list: List[String]) = list match {
  case List("1","2", rest @ _*) => "one, two with rest " + rest
  case _ => "dunno"
}

test(List("1","2","3","4"))
//--> java.lang.String = one, two with rest List(3, 4)

Achtung, der Rest kann natürlich auch eine leere Liste sein. Für Listen ist dieser Trick eigentlich unnötig, denn hier hat man ja schon den Extraktor ::, aber das Ganze funktioniert natürlich auch für andere Extraktoren mit variabler Argumentanzahl, wie z.B. Seq.

So, dann wünsche ich fröhliches Extrahieren, vor allem meinen Erstlesern bei codekicker.de.

Wasch mich, aber mach mich nicht nass!

Es ist kein Geheimnis: Java macht keinen richtigen Spaß mehr, wenn man es mit anderen modernen Sprachen vergleicht. Was macht man, wenn man weiter die JVM und die unzähligen Java-Bibliotheken nutzen will? Richtig, man schaut kräftig beim Marktführer Scala ab, und schreibt eine eigene Sprache. Die natürlich besser ist. So geschehen bei Gosu, RedHat’s Ceylon und nun JetBrain’s Kotlin.

Ich finde das traurig. Richtig, es heißt „Konkurrenz belebt das Geschäft“, aber diese drei Sprachen sind unnötig wie ein Kropf. Es stimmt, Scala kann kompliziert sein und hat auch einige weniger schöne Stellen. Auf der anderen Seite ist es einsteigerfreundlich, innovativ und mächtig, aber vor allem ist es da. Es hat lange gebraucht, um wirklich Bewegung in die Sache zu bringen, eine Community aufzubauen, Tool-Support zu organisieren, ja überhaupt wahrgenommen zu werden. Was inzwischen fast wie ein Selbstläufer aussieht, ist das Ergebnis langer, harter Arbeit. Ich denke, die neuen Sprachschöpfer unterschätzen diesen Aspekt einer Sprache ganz gewaltig.

Viel eigene Innovation ist bei keinem der Kandidaten zu sehen. Aber was mich wirklich stört, ist der Versuch, sich nur die Rosinen aus dem Kuchen zu picken. Das ist nämlich die Art von Geisteshaltung, die Java’s Stillstand erst verursacht hat. Eine gute Sprache ist offen für neue Entwicklungen, und lenkt diese in geordnete Bahnen. Gerade diese Offenheit macht Scala so attraktiv. Doch die Strategie der neuen Sprachen ist die gleiche wie Java: Wasch mich, aber mach mich nicht nass! Features, die „zu kompliziert“ sind oder eventuell missbraucht werden können, werden abgelehnt. In Java waren das etwa Operator-Überladungen, Closures oder Konzepte zur Erweiterung von Interfaces (wie Extensionsmethoden oder Mixins). Jetzt werden aus den gleichen fadenscheinigen Gründen Dinge wie implizite Umwandlungen, abstrakte Typ-Member oder Typpolymorphismus höherer Ordnung abgelehnt – obwohl diese Ideen längst den Praxistest bestanden haben. Was immer wieder übersehen wird ist, dass viele Features, die für die tägliche Arbeit unnötig scheinen, in Bibliotheken und Frameworks essentiell sein können: Jeder, der in Scala eine Liste mapped, verwendet dabei Typpolymorphismus höherer Ordnung – aber er muss dazu nicht einmal wissen, was das ist.

Ich denke dass für viele Detail-Lösungen der neuen Sprachen auch Platz in Scala gewesen wäre, wenn die Macher auf Kooperation gesetzt hätten. Aber jetzt wird viel Arbeit und Gehirnschmalz in Dinge investiert, die es zum größten Teil schon gibt, und Projekte gestartet, die keinen Erfolg haben können. Ein Blick in die Geschichte zeigt, was mit gut gemeinten, aber zu konservativen Ansätzen passiert: Nice hatte viele gute Ideen und nette Details, aber nicht genug, um die Java-Community wirklich zu begeistern, und neue Perspektiven zu eröffnen.

Ich will kein aufgehübschtes Java, und auch kein weichgespültes Scala. Sicher ist es nett, wenn hier und da eine Syntax-Kante geglättet wird. Aber wenn mir am Ende die Ausdrucksstärke fehlt, um meine Gedanken in Code umzusetzen, nützt mir das alles nichts. Ich will keine Sprache zwischen Java und Scala – wenn überhaupt, dann zwischen Scala und Haskell, mit mehr Abstraktionsmöglichkeiten, nicht weniger. Scala ist sicher nicht der Endpunkt der Entwicklung, aber es schwimmt in die richtige Richtung. Nass, aber sauber.

Update

Hier noch ein interessanter Blog-Post, der in die gleiche Richtung und dabei etwas mehr ins Detail geht: Scala, Kotlin, Ceylon… let’s start by being honest.

Eigene Extraktoren

Heute nur ein paar Zeilen zu eigenen Extraktoren. Ich denke, einen guten Überblick über die verschiedenen Möglichkeiten gibt Jesse Eichar in seinem Daily Scala Blog. Ich will heute einen ganz einfachen Satz von Extraktoren vorstellen, mit denen man sich in vielen Fällen Guards sparen kann. Angenommen, wir haben folgenden Code:

case class Edge(from:String, to:String)

def makeEdge(p:(String,String)) = p match {
  case (from,to) if from != to => Edge(from, to)
  case _ => error("Can't create edge with identical end points")
}

Wäre es nicht schön, wenn wir einen Extraktor hätten, der auf Ungleichheit prüfen kann? Kein Problem:

object Ne {
   def unapply[T](pair:(T,T)):Option[(T,T)] = 
     if (pair._1 != pair._2) Some(pair) else None
}

def makeEdge(p:(String,String)) = p match {
  case Ne(from,to) => Edge(from, to)
  case _ => error("Can't create edge with identical end points")
}

Nach dem gleichen Schema lässt sich eine ganze Familie von Extraktoren basteln. Für Größenvergleiche benötigen wir zusätzlich einen impliziten Ordering-Parameter, und für den Gleichheits-Extraktor geben wir natürlich nur einen Wert zurück – zwei gleiche wären ja ziemlich witzlos. Hier die ganze Sammlung:

object Eq {
   def unapply[T](pair:(T,T)):Option[T] = 
      if (pair._1 == pair._2) Some(pair._1) else None
}

object Ne {
   def unapply[T](pair:(T,T)):Option[(T,T)] = 
     if (pair._1 != pair._2) Some(pair) else None
}

object Lt {
   def unapply[T](pair:(T,T))(implicit ord: Ordering[T]):Option[(T,T)] = 
     if (ord.lt(pair._1,pair._2)) Some(pair) else None
}

object Le {
   def unapply[T](pair:(T,T))(implicit ord: Ordering[T]):Option[(T,T)] = 
     if (ord.lteq(pair._1,pair._2)) Some(pair) else None
}

object Gt {
   def unapply[T](pair:(T,T))(implicit ord: Ordering[T]):Option[(T,T)] = 
     if (ord.gt(pair._1,pair._2)) Some(pair) else None
}

object Ge {
   def unapply[T](pair:(T,T))(implicit ord: Ordering[T]):Option[(T,T)] = 
     if (ord.gteq(pair._1,pair._2)) Some(pair) else None
}

Für eine Beschränkung habe ich leider noch keine Lösung gefunden, und zwar für Alternativen. Man kann zwar schreiben:

def g(p:(Int,Int)) = p match {
  case (10,20) | (20,10) => println("yes!")
  case _ => println("nope")
}

Aber es ist verboten, in den einzelnen Alternativen Variablen zu belegen, z.B.:

//doesn't work
def g(p:(Int,Int)) = p match {
  case (10,n) | (n,10) => println(n)
  case _ => println("nope")
}

Im Prinzip sollte das für den Compiler kein Problem sein, wenn in beiden Zweigen die gleiche Anzahl Variablen mit den gleichen Typen verwendet wird. Leider scheint es auch mit eigenen Extraktoren nicht möglich zu sein, das gewünschte Verhalten abzubilden. Oder hat jemand vielleicht eine zündende Idee?

So, ich denke das reicht für heute. Demnächst gibt es das Kohl-Ziege-Wolf-Puzzle in Haskell, aber das braucht noch etwas Feinschliff, vor allem der Kohl.

Überraschung programmiert mit asInstanceOf

Wer ein wenig Scala geschrieben hat, merkt schnell, dass man – insbesondere dank Pattern Matching – viel weniger casten muss als in Java. Die Methode zur Typkonvertierung hat absichtlich einen abschreckenden Namen bekommen: asInstanceOf. Und das zu Recht, denn Casts in Scala sind nicht sicherer als in Java.

Allerdings könnte man meinen, man sei sicher, nachdem der Cast „gelungen“ ist. Natürlich ist das schon in Java nicht der Fall, wenn man z.B. ein Objekt zu List<String> castet, das in Wahrheit eine List<Integer> ist. Der Cast gelingt, aber beim Zugriff auf ein Listen-Element gibt es einen lauten Knall. Aber wer Type Erasure in Java verstanden hat, sollte sich über dieses Verhalten eigentlich nicht wundern, denn wenn zur Laufzeit kein Parametertyp mehr existiert, kann man ihn auch nicht testen.

Neulich bin ich auf Stackoverflow auf ein anderes Problem gestoßen, dass es nur in Scala gibt: Man kann an eine Klasse mit asInstanceOf ungestraft andere Klassen oder Traits „anhexen“, ohne dass das beanstandet wird – natürlich nur, solange man nicht auf irgendwelche Member zugreifen möchte. Dabei kann die verhexte Klasse sogar final sein, wie z.B. Int:

trait Funny{ 
   def test { println("funny!") } 
}

def doubleIt(z: Int with Funny):Int = 2*z

val x = 5.asInstanceOf[Int with Funny] 

print(doubleIt(x)) // 10

print(x.test) // ClassCastException

Wir definieren hier ein Trait namens Funny, und eine Funktion namens doubleIt, die ein Int with Funny erwartet. Natürlich können wir diesen Typ nie wirklich konstruieren, denn Int ist final. Der Versuch, doubleIt mit einem normalen Int aufzurufen, würde übrigens schon beim Compilieren scheitern.

Als nächstes kreieren wir mit asInstanceOf ein Frankenstein-Monster namens x, das den gewünschten Typ besitzt, und ES IST LEBENDIG, ES LEBT!!!… Ähm, ich meine, man kann damit problemlos doubleIt aufrufen, und erhält das gewünschte Ergebnis.

Die letzte Zeile zeigt die dunkle Seite unseres Monsters: Es ist in Wirklichkeit gar nicht Funny, und wenn wir eine Methode des Traits aufzurufen versuchen, macht es puff und explodiert in einer ClassCastException.

Das gezeigte Verhalten ist natürlich ziemlich gefährlich, und man fragt sich, warum asInstanceOf-Aufrufe nicht testen, was da eigentlich für Typen von ihnen verlangt werden. Prinzipiell wäre das mit isInstanceOf möglich, aber vermutlich wären derartige Laufzeittests ziemliche Performance-Killer.

Was lernen wir daraus? Zum einen, dass man mit asInstanceOf den Typchecker wirklich „abschaltet“ und allen möglichen Unsinn anstellen kann – etwa Klassen vorzugaukeln, die es prinzipiell nicht geben kann. Zum anderen, dass man um asInstanceOf einen großen Bogen machen sollte, wenn man es nicht unbedingt braucht und nicht ganz genau weiß was man tut.

Scava

Während der Aufruf von Java-Code aus Scala meist recht unproblematisch ist, sieht es bei der Gegenrichtung nicht ganz so gut aus. Deshalb habe ich beschlossen, eine Java-Bibliothek zu schreiben, die den Aufruf von Scala-Code erleichtert. Ich habe das Projekt „Scava“ getauft.

Was bietet nun Scava? Die meisten Klassen sind Utility-Klassen, die über statische Member und Methoden Scala-Funktionalität zur Verfügung stellen. Ein Beispiel: Wenn man für einen Scala-Aufruf ein Ordering braucht, kann man ord.scava.math.Orderings importieren, das so aussieht:

 
public class Orderings {

    public static Ordering$ ORDERING = Ordering$.MODULE$;
    public static Ordering<Object> UNIT_ORDERING = scala.math.Ordering$Unit$.MODULE$; //???
    public static Ordering<Boolean> BOOLEAN_ORDERING = scala.math.Ordering$Boolean$.MODULE$;
    public static Ordering<Byte> BYTE_ORDERING = scala.math.Ordering$Byte$.MODULE$;
    public static Ordering<Character> CHAR_ORDERING = scala.math.Ordering$Char$.MODULE$;
    ... weitere statische Member ...

    public static <T> Ordering<T> fromLessThan(Function2<T, T, Boolean> cmp) {
        return ORDERING.<T>fromLessThan(cmp);
    }

    public static <T, S> Ordering<T> by(Function1<T, S> f, Ordering<S> ord) {
        return ORDERING.by(f, ord);
    }

    public static <T> Ordering<Option<T>> optionOrdering(Ordering<T> ord) {
        return ORDERING.<T>Option(ord);
    }

    ... weitere Methoden, z.B. für Tupel ...
}

Damit hat man also für viele Fälle schon die richtige Ordering. Die meisten Scava-Klassen sehen ähnlich aus.

Weiterhin bietet Scava Hilfe beim Implementieren von Funktionen. Da Function0 u.s.w. Traits sind, und Function1 und Function2 darüber hinaus auch noch spezialisiert (mit @specialized), ist es nämlich gar nicht so einfach, diese ordentlich in Java zu implementieren. Dafür bietet Scava die abstrakten Klassen F0, F1 u.s.w., bei denen schon „alles dran“ ist, außer der apply-Methode.

Natürlich ist das Projekt noch in der Anfangsphase. Für jede Art von Hilfe, Ideen, Testberichte, Unit-Tests und konstruktive Kritik wäre ich dankbar.

Nochmal Kruskal

Meine Kruskal-Implementierungen haben einen Haken: Das Verwalten der Knoten-Sets ist umständlich und langsam. Zumindest für die Scala-Version habe ich dafür jetzt eine bessere Variante: Ich habe einen eigenen Datentyp geschrieben, der intern eine Map von Knoten auf Knoten-Sets hält, aber speziell an die Aufgabe angepasste Operationen besitzt:

object Kruskal {

  case class Edge[A](v1:A, v2:A, d:Double)

  type LE[A] = List[Edge[A]]
  type OS[A] = Option[Set[A]]

  class SetMap[A](data:Map[A,collection.mutable.Set[A]] = Map[A,collection.mutable.Set[A]]()) {
    import collection.mutable.Set

    //checks if a value exists
    def contains(a:A) = data.contains(a);

    //checks if two values are in the same Set
    def sameSet(repr1:A, repr2:A) = data.get(repr1) == data.get(repr2)

    //adds a new Set with one initial value
    def add(a:A) = if (contains(a)) this else new SetMap(data + (a -> Set(a)))

    //adds a new value to an existing Set (specified by repr)
    def insert(a:A, repr:A) = if (contains(a) || ! contains(repr)) this else {
      val set = data(repr)
      set += a
      new SetMap(data + (a -> set))
    }

    //merges two sets (specified by two representants)
    def merge(repr1:A, repr2:A) = if(! contains(repr1) || ! contains(repr2)) this else {
       val set1 = data(repr1)
       val set2 = data(repr2) 
       if(set1 eq set2) this else {
         set1 ++= set2
         new SetMap(data ++ set2.map(a => a -> set1))
    }}
  }

  def kruskal[A](list: LE[A]) = list.sortBy(_.d).foldLeft((Nil:LE[A],new SetMap[A]()))(mst)._1

  def mst[A](t:(LE[A], SetMap[A]), e:Edge[A]) = {
    val ((es, sets), Edge(p,q,_)) = (t,e)
    (sets.contains(p), sets.contains(q)) match {
        case (false, false) => (e :: es, sets.add(p).insert(q,p))
        case (true, false) => (e :: es, sets.insert(q,p))
        case (false, true) => (e :: es, sets.insert(p,q))
        case (true,true) => if (sets.sameSet(p,q)) (es, sets) //circle
                            else (e :: es, sets.merge(p,q))
    }
  }
    
  def main(args:Array[String]) {
    println(kruskal(
        List(Edge('A,'B,7), Edge('A,'D,5),Edge('B,'C,8), Edge('B,'D,9),
             Edge('B,'E,7), Edge('C,'E,5), Edge('D,'E,15), Edge('D,'F,6),
             Edge('E,'F,8), Edge('E,'G, 9), Edge('F,'G,11))))
  }

}

Wie man sehen kann, braucht man keine Liste mehr zu durchsuchen, alle Operationen laufen auf der Map ab. Nur merge ist komplizierter, weil dabei stark in die Struktur der Map eingegriffen werden muss. Leider kann man obige Lösung nicht ohne weiteres auf Haskell übertragen, denn die verwalteten Sets sind veränderlich. Das ist ein Beispiel, wo veränderliche Daten für gute Performance sorgen, ohne übehaupt von außen sichtbar zu sein. Anstatt irgendwo ein Set zurückzugeben, arbeite ich mit „Repräsentanten“, also irgendeinem Wert im jeweiligen Set, was bei dieser Aufgabenstellung sogar bequemer ist.

Als positiver Nebeneffekt ist die Methode mst nun viel besser zu lesen – trotz der geschachtelten matches (korrigiert – danke für den Tipp an Lars).