16
Jan
10

Wie funktional ist Scala?


Nachdem ich ein wenig über die funktionale Sprache Clean gelesen hatte, wollte ich auch mal ein Beispiel selber programmieren. Das fiel mir erstaunlich leicht, denn Clean ähnelt der Sprache Haskell, mit dem ich auch schon ein wenig herumgespielt habe. Das Ergebnis ist sicher kein Meilenstein funktionaler Programmierung, aber das Programm läuft. Hier sind also meine acht Damen in Clean:

//Clean 2.2
module Queens
import StdEnv

Start = queens []

queens list 
    | length list == 8 = [list]
    | otherwise = flatten (map (\x = queens [x:list]) (filter (valid list) [1..8]))
    where 
    valid t h = not (isMember h t || diagonal (+) (h+1) t || diagonal (-) (h-1) t)
        where
        diagonal _ _ [] = False
        diagonal op n [h:t] = n == h || diagonal op (op n 1) t

So sieht Code aus, mit dem man OO-Programmierer erschrecken kann. Aber mit ein paar zusätzlichen Informationen klärt sich das Bild: Ergebnis der Berechnung soll eine Liste von Int-Listen sein. Dabei hat jede Int-Liste acht Stellen und gibt eine Brettposition wieder (die n-te Zahl gibt dabei an, in welcher Spalte die Dame in der n-ten Reihe steht). Hat unsere Liste die gewünschte Länge 8, sind wir fertig. Andernfalls (otherwise) nehmen wir die Spaltenpositionen von 1 bis 8, behalten nur die, die nicht von den vorangegeangenen bedroht werden (filter(valid list)), fügen die jeweilige Position an die vorhandene Liste, rufen damit Queens rekursiv auf und liefern die Ergebnisse der einzelnen Aufrufe zusammengefügt (flatten) zurück. Die Unterfunktion valid hat drei Bedrohungsarten zu berücksichtigen: gleiche Spalte und gleiche Diagonale aufsteigend oder absteigend. Für die Diagonalen gibt es eine Unter-Unterfunktion diagonal, bei der auch der Operator mitgeliefert wird, der die Richtung der Diagonale bestimmt (also, ob zur vorhandenen Position +1 oder -1 in der nächsten Zeile gerechnet wird). Eigentlich ganz logisch, wenn man sich nicht von der Syntax erschrecken lässt.

Nun wird Scala oft als objektorientierte Sprache mit etwas funktionalem Flair beschrieben. Das ist auch wenig verwunderlich, schließlich läuft Scala auf der JVM, und die Kompatibilität zu Java wird (zu recht) immer wieder betont. Codeschnipsel, die Scala als “besseres Java” propagieren sollen, tun ein übriges, um dieses Bild zu festigen. Dabei wird übersehen, dass Scala viel, viel weiter in Richtung funktionaler Programmierung geht als andere gebräuchliche OO-Sprachen, und damit meiner Meinung nach ziemlich genau in der Mitte zwischen den Paradigmen steht. Wie sieht nun mein Beispiel in Scala aus, wenn ich versuche, mich möglichst dicht ans Original zu halten?

object Queens {
  def main(args: Array[String]) { println(queens(Nil)) }
   
  def queens(list: List[Int]):List[List[Int]] = list match {
    case full if full.size == 8 => List(full)
    case _ => def valid(t:List[Int])(h:Int) = {
        def diagonal(op: (Int,Int)=>Int, n:Int, li:List[Int]): Boolean = li match {
          case Nil => false
          case h :: t => n == h || diagonal(op, op(n,1), t)
        }
        ! (t.contains(h) || diagonal(_+_, h+1, t) || diagonal(_-_, h-1, t))
      }
      (1 to 8 toList).filter(valid(list)).map(n => queens(n :: list)).flatten
  }
}

Ich finde, das sieht ziemlich ähnlich aus. Scala hat im Gegensatz zu Haskell und Clean nur eine partielle Typinferenz (der übliche Hindley-Milner-Algorithmus verträgt sich mit OO und vor allem Methodenüberladung nicht), so dass die Aufruftypen und bei rekursiven Funktionen auch die Rückgabetypen angegeben werden müssen. Lokale Funktionsdefinitionen funktionieren ähnlich wie das originale where, wobei man die lokale Funktion besser vor der Benutzung definiert. Der rekursive Aufruf von queens verwendet die gleichen Funktionen wie das Original. In diesem Fall finde ich, dass die objektorientierte Schreibweise vorteilhafter ist: Nimm die Positionsliste, filtere sie nach gültigen Positionen, rufe queens mit der um die jeweilige neue Position ergänzte Liste rekursiv auf, und füge die Ergebnisse zusammen. Man erhält also eine Abarbeitungsreihenfolge in Leserichtung, und nicht umgekehrt.

Der vorgestellte Code zeigt, wie weit man sich in Scala von Java wegbewegen kann, denn dort könnte man nicht einmal annähernd etwas ähnliches schreiben. Wenn man es will, ist mit Scala ein sehr funktionaler Stil möglich, nicht ganz wie in Haskell oder Clean, aber doch sehr dicht dran. Aber das Schöne ist, dass man dazu nicht gezwungen wird. Es ist immer gut, wenn man sich entscheiden kann. Funktionale Programmierung ist keine “Silver Bullet”, aber es lohnt, sich damit zu beschäftigen.

Nachtrag:
Martin Odersky hat gerade einen Artikel veröffentlicht, in dem er Scala als “postfunktionale Sprache” bezeichnet, und auch auf andere Diskussionen um Scalas “Funktionalität” verweist. Die neue Bezeichnung gefällt mir. Und Java könnte man dann unter den “dysfunktionalen Sprachen” einordnen :-D

About these ads

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ photo

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s


Follow

Erhalte jeden neuen Beitrag in deinen Posteingang.

%d Bloggern gefällt das: