Nachdem mein Interesse an Perl 6 schon eine Weile lang ungebrochen ist, und es im Internet noch nicht viel deutschsprachiges gibt, habe ich eine neue Seite aufgemacht: Perl 6 – Programmieren für Faule.

Der Slogan gefällt mir noch nicht so ganz, vielleicht hat ja noch jemand eine Anregung für mich.

In Zukunft werden neue Beiträge mit dem Thema Perl 6 wohl eher auf dem dortigen Blog landen als hier.

Über Feedback freue ich mich immer.

Im SVN-Repository von pugs gibt es viele Testcases, unter anderem ein Verzeichnis mit “99 Problems”.

Diese Probleme beziehen sich auf eine Liste von Programmieraufgaben, ursprünglich für die Programmiersprache Logo vorgesehen.

Etwa zwei Drittel dieser Probleme sind schon in Perl 6 gelöst, ein paar interessante sind noch übrig.

Gestern habe ich mich an den Huffman-Code (Problem 50) gemacht.

Das Problem

Der Huffman-Code dient der Komprimierung, und zwar hat man einige Zeichen und ihre Häufigkeiten in einem Text gegeben, und soll anhand dessen für jeden Buchstaben eine Bitsequenz erstellen, sodass die Länge des ganzen Textes minimiert wird.

Tendenziell gilt also, dass häufigere Zeichen eine kürzere Sequenz bekommen. Das führt zu einem Problem: die Sequenzen müssen “präfixfrei” sein, d.h. keine Sequenz darf eine andere als ihern Anfang enthalten.

Wenn ‘a’ also z.B. als ‘10′ kodiert wird, darf kein anderes Zeichen mit ‘10′ anfangen – sonst wüsste man beim lesen der kodierten Daten nicht, ob das ein ‘a’ ist oder eines der Zeichen, die mit ‘10′ anfangen.

Wie geht man also vor?

Der Algorithmus

Der Algorithmus ist erstaunlich einfach. Wenn man ihn mit Stift und Papier nachvollzieht, malt man einfach für jeden Buchstaben eine Box um den Buchstaben, und schreibt die Häufigkeit des Buchstabens hinein:

Dann schreibt man über die beiden Buchstaben mit den niedrigsten Werten für die Häufigkeiten die Summe der Häufigkeiten, und verbindet die Summe und die beiden Werte mit Geraden:

Der Übersichtlichkeit wegen wurden die beiden Buchstaben nach unten verschoben.

Das ganze wiederholt man, wobei man ab dem zweiten Schritt die beiden ersetzten Buchstaben nicht mehr betrachtet, sondern nur noch ihre Summe:

Damit fährt man fort, bis alle Buchstaben verbunden sind:

Und am Ende:

Jetzt fehlt nur noch ein Schritt: an jede Verbindungslinie eine 0 oder eine 1 einzeichnen, und zwar immer zu dem niedrigeren Wert eine 0 und zum höheren eine 1. Umgekehrt ginge es genau so, man muss sich nur auf eine Art festlegen.

Wenn man jetzt die Kodierung eines Buchstaben wissen will, folgt man dem Baum von der Wurzel (oben) bis zu dem Buchstaben, und notiert sich die an den Verbindungen stehenden Nullen und Einser. Ein ‘a’ wird in diesem Beispiel also als ‘0′ kodiert, ein ‘e’ als ‘1101′.

Mit den verwendeten Häufigkeiten kommt man in Summe auf 100 Zeichen. Wenn man diese “ganz normal” mit einer festen Anzahl an Bits pro Zeichen kodiert, benötigt man 4 Bit pro Zeichen, und damit 300 Bit. Mit dieser Huffmankodierung benötigt man nur 224 Zeichen, man hat also etwa ein Viertel der Datenmenge eingespart.

Perl6-Implementierung

Und hier kommt die Implementierung in Perl 6:

use v6-alpha;
use Test;
plan 1;

# die Häufigkeiten
my @fr = (
        ['a', 45],
        ['b', 13],
        ['c', 12],
        ['d', 16],
        ['e', 9 ],
        ['f', 5 ],
         );

# Das erwarten wir, wird später zum Testen verwendet
my %expected = (
        'a' => '0',
        'b' => '101',
        'c' => '100',
        'd' => '111',
        'e' => '1101',
        'f' => '1100'
        );

my @c = @fr;

# hier wird der Baum aufgebaut
while @c.elems > 1 {
    # nach dem zweiten Element der Arrays sortieren:
    @c = sort { $^a[1] < => $^b[1] }, @c;
    my $a = shift @c;
    my $b = shift @c;
    unshift @c, [[$a[0], $b[0]], $a[1] + $b[1]];
}

my %res;

# diese Funktion durchläuft rekursiv den Baum und speichert die
# Ergebnisse im Hash %res ab
sub traverse ($a, Str $code = ""){
    if $a.WHAT eq "Str" {
        %res{$a} = $code;
    } else {
        traverse($a[0], $code ~ '0');
        traverse($a[1], $code ~ '1');
    }
}

traverse(@c[0][0]);

# und jetzt der Vergleich mit dem erwarteten:

is(%res, %expected, "Huffman tree builds correctly");

Der schwierigste Teil ist erledigt: Der Baum ist gebaut, und aus dem Baum wurde die Kodierung extrahiert. Wenn man jetzt tatsächlich Text kodieren will, muss man ihn Zeichen für Zeichen durchlaufen, und jedes Zeichen $c durch %res{$c} ersetzen. Um es binär darzustellen, müsste man das Ergebnis noch durch die Funktion pack jagen.

Perl 6 bringt als eine der vielen Neuerungen ein ausgefeiltes Objektmodell (das man zum Teil in Perl 5 auch schon mit Moose genießen kann).

Eines der neuen Features ist “Design By Contract” (siehe z.B. Bertrand Meyer: Object-oriented Software Construction für eine sehr ausführliche Beschreibung der Idee).

Die Idee ist, Vorbedingungen, “Preconditions” in Methoden zu deklarieren, die beim Aufruf der Funktion sichergestellt sein müssen, und die vom Compiler oder Interpreter zur Laufzeit überprüft werden:

class Math {
    method sqrt(Num $x) {
        PRE {
            $x > 0
        }
        # hier die Wurzel berechnen
        return $wurzel;
    }
}

Ähnlich kann eine Methode mit Postconditions dem Aufrufer versichern kann, dass bestimmte Bedingungen nach dem Aufrufen der Methode erfüllt sind:

class Math {
    method sqrt(Num $x) {
        PRE {
            $x > 0
        }
        # hier die Wurzel berechnen
        return $wurzel;
        POST {
            abs($wurzel**2 - $x) < 0.00001
        }
   }
}

Wenn eine Klasse davon erbt, erbt sie automatisch auch die PRE- und POST-Blöcke. Allerdings kann eine erbende Klasse die Preconditions schwächen (d.h. mit einer neuen ODER-verknüpfen) und Postconditions verstärken (also mit bisheren UND-verknüpfen):

Class ComplexMath is Math {
    method sqrt(Num $x) {
        PRE {
            1;
        }
        # hier kommt die Berechnung
    }
}

Da man aus beliebigen komplexen Zahlen die Wurzel ziehen kann, braucht man die Vorbedingung nicht mehr, sie liefert hier immer 1, also True, zurück.

Dann sollte man noch anmerken, dass das Beispiel hier natürlich überflüssig ist, weil Perl 6 von Haus aus eine sqrt()-Funktion hat, die auch mit komplexen Zahlen umgehen kann.

[tags]perl, perl 6, design by contract, dbc, precondition, postcondition[/tags]

Perl6 bietet eine Fülle neuer Operatoren, die einen auf den ersten Blick erschlagen. Daher hier nur ein paar besonders nette.

Der Zip-Operator verschachtelt listen:

 (1 .. 4) Y <a b c d>
# liefert ((1, "a"), (2, "b"), (3, "c"), (4, "d"))

Die Spitzen Klammern sind die neue Schreibweise für qw(), also für eine Liste von Worten, mit Leerzeichen getrennt.

Natürlich kann man den Zip-Operator auch mehrfach anwenden:

(1 .. 4) Y <a b c d> Y <a B C D>;
# gibt ((1, "a", "A"), (2, "b", "B"), (3, "c", "C"), (4, "d", "D"))

Wer öfter mit Listen von Zahlen rumhantieren muss, wird sich über die “reduzierenden” Operatoren in Eckigen Klammern freuen, [+] zum Beispiel:

[+] (1, 2, 4);
# gibt 1+2+4 = 7

Das funktioniert mit beliebigen numerischen Operatoren, z.B. die Fakultät lässt sich schon schreiben:

[*] (1 .. 10);
# wird zu 1 * 2 * .. * 10 = 3628800

Der “Hyperoperator” verknüpft Arrays mit Arrays:

(1 .. 4) >>+<< (2 .. 5); # gibt (1+2, 2+3, 3+4, 4+5) = (3, 5, 7, 9)
(2, 3) >>**<< (2, 3); #gibt (2**2, 3**3) = (4, 27)

Hier ist ** der Potenzoperator, und der Hyperoperatore >>…<< sorgt dafür, dass er elementweise auf die Arrays angewandt wird.

Fehlende Elemente werden durch sinnvolle Defaults ersetzt, also 0 bei Addition und 1 bei Multiplikation:

(1, 2, 3) >>+<<(1, 2); # gibt (2, 4, 3)
(1, 2, 3) >>*<<(1, 2); # gibt (1, 4, 3)

Wenn eines der Array aber nur ein Element hat, wird dieses auf das gesamte andere Array angewandt:

(1, 2, 3) >>*<< 2;  # gibt (2, 4, 6), jedes Element verdoppelt

[tags]perl, perl6, operator, programmieren[/tags]

Mit pugs existiert bereits ein erste, wenn auch nicht vollständige Perl6-Implementierung.

Perl 5 war ja schon eine tolle Sprache, aber sie hatte auch ein paar Nachteile (was ein Perl-Hacker natürlich niemals zugeben würde). Perl6 beseitigt viele davon, und fügt jede Menge tolle, neue Features hinzu.

In Perl 5 hat man bei Funktionsdeklarationen keine Liste von Parametern angegeben, sondern die Parameter automagisch aus dem dem Array @_ geholt:

sub fakultaet {
    my $i = shift;
    if ($i < 2){
        return 1;
    } else {
        return $i * fakultaet($i - 1);
}

Das ist zwar sehr flexibel, aber nicht immer schön. Mit Perl6 geht es jetzt besser:

use v6;
sub fakultaet($i){
     if $i < 2 {
     ...

Man kann auch dazu sagen, dass man gerne einen Integer möchte (die Verallgemeinerunger der Fakultät auf die Gammafunktion ist recht komplex, wir sind zu faul sie zu implementieren):

use v6;
sub fakultaet($i is Int){
    if $i < 2 {
    ...

Damit hat man Typsicherheit und Effizienz gewonnen.

Auch kann man in Perl6 Defaultwerte für Argumente angeben:

sub fuga($i is Int, $j is Int = $i){
	return $j == 1 ?? $i !! $i ** fuga($i, $j-1);
}

(Der ?? !! Operator ist die Neufassung des Ternären Operats (bedingung) ? wahr : falsch, d.h. wenn die Bedingung vor ?? bzw ? zutrifft wird der Ausdruck wahr zurückgeliefert, wenn nicht wird der Ausdruck falsch zurückgeliefert).

Was macht unsere nette fuga-Funktion? fuga(1) liefert 1, fuga(2) liefert 2², fuga(3) liefert 3^{(3^3)} usw, erfunden von Richard P. Feynman.

Aus Sicht des Perl6-Entwicklers interessant ist, dass dem Parameter $j ein Defaultwert zugewiesen wird, der in diesem Falle sogar noch von dem ersten Parameter abhängt – wenn das mal keine Magie ist!
[tags]perl, perl6, pugs, funktion[/tags]