Quicksort in Red

Posted by in red

Mein letzter Beitrag ist einige Zeit her, denn ich habe mich mit Red beschäftigt. Die Sprache steckt noch mehr als in den Kinderschuhen, da sie erst seit 2011 entwickelt wird.

Interessant ist sie deswegen, weil sich die Erfinder das Ziel gesetzt haben, eine FullStack-Language zu entwickeln, mit der man auf jedem Abstraktionsniveau arbeiten kann. Außerdem ist die Syntax mehr als außergewöhnlich, da viele Befehle wie einfache Sätze geschrieben werden können. Ein erfrischendes Konzept, wenn man Unsprachen wie PHP als Vergleich heranzieht.

Schön ist auch die sehr freundliche Community, die sich vor allem auf StackOverflow im Chat widerfindet. Mir wurde prompt geholfen und ich fühlte mich herzlich empfangen. Allerdings braucht man zum Posten mindestens eine Reputation von 20, aber wenn man eine Frage zu Red auf Stackoverflow einstellt, sollte man das schnell erreichen können. Oder man kontaktiert die Entwickler, die einem in diesem Fall auch gerne aus der Patsche helfen.

Das erste Progrämmchen

Zum Einstieg habe ich mich an einem Quicksort versucht. Da ist ziemlich viel zu tun. Rekursion, Listenmanipulation, Schleifen und if-Abfragen.

Ich stelle den Code zuerst im Ganzen vor, um ihn danach Stück für Stück zu erklären. Ich bin kein Red-Experte, deswegen kann ich nicht alles in vollem Detail erklären und vielleicht ist Manches auch ganz einfach falsch. Ich bitte um Nachsicht und/oder Kommentare 🙂

Die Version, die ich benutze, ist für dieses Beispiel 0.4.2.

Der sogenannte Header ist Pflicht in jeder Red-Datei, da er zu Identifizierung der Sprache für den Compiler eingesetzt wird. Man kann ihn mit der Shebang-Zeile vergleichen, die in unixoiden Betriebssystemen das ausführende Programm anzeigt.

Kommen wir zur Funktionsdeklaration, die wir für unseren Quicksort-Algorithmus brauchen. Die Notation für Funktionen unterscheidet sich fast nicht von der, die für Variablen verwendet wird. Sie beginnt immer mit identifier: . Dieses Konzept wird konsequent durchgezogen und erleichtert das Erlernen der Syntax eindeutig. Zur Definition von Funktionen gibt es zwei Möglichkeiten: func und function. Bei func hat man zwei aufeinanderfolgende Blöcke und die Notation sieht dann vereinfacht so aus:

Während die Definition mit function auch optional einen weiteren Block erlaubt, der an zweiter Stelle eingebracht wird.

Im zweiten Block werden lokale Variablen untergebracht, deren Scope auf die Funktion beschränkt bleiben soll. Für mich als Java-Entwickler ist das Prinzip ungewohnt, dass ich etwas explizit als lokal definieren muss, aber da Red Funktionen-Schachtelung erlaubt, ist es anscheinend sinnvoll. Das ganze nennt sich definitional Scoping. Will man eine Variable innerhalb der Funktion im lokalen Scope haben, dann muss man sie bei func explizit als \local auszeichnen. Bei function kommen lokale Variablen einfach in den zweiten Block, und alle Variablen die innerhalb des Rumpfes deklariert werden sind ebenfalls lokal.

Parameter

Meine Funktion quicksort bekommt einen Parameter übergeben der vom Typ block! ist. Das ist auch gleichzeitig eine Liste, wie man sie aus Rebol kennt. Zum Nachlesen hier die Dokumentation. Zurückgegeben wird wieder ein block!. Streng genommen brauche ich das return gar nicht, denn der Rückgabewert wird immer aus der letzten Anweisung berechnet. Aber zur Dokumentation habe ich es eingefügt. Außerdem kann dann der Compiler effizienter Arbeiten 😉

Funktionsrumpf

Zuerst müssen wir den Parameter in eine lokale Variable schreiben. Warum man das machen muss wird in dieser Dokumentation gut erklärt. Die copy Anweisung benutze ich bei allen Listen in meiner Funktion, sonst würde nämlich ein tieferer Aufruf in unserem Rekursionsbaum die Variablenwerte in einem höheren überschreiben.

Der folgende Rekursionsabbruch erklärt sich wie bei Red so oft von selbst ohne weitere Erklärung.

Anschließend holen wir uns das pivot-Element aus der Liste und entfernen es danach. Warum man es nicht herausholen kann und gleich entfernen, konnte ich bis jetzt nicht herausfinden.

Dieses fügen wir dann auch sofort in die später sortierte Liste sortedList ein. Die Syntax kann man hier wie einen Satz lesen und ist sofort verständlich. Selbst meine Mutter könnte sagen, was dort passiert ;):

Liste durchlaufen und sortieren

Es gibt ein paar Wege um Listen zu durchlaufen. Der Einfachheit halber nehme ich forall und greife auf das aktuelle Element mit first zu.

Bei meiner Recherche zu Abfragen kam heraus, dass es zwar if gibt, aber kein else. Dafür gibt es either. Wenn man ein bisschen darüber nachdenkt, gibt es dafür eine gute Erklärung. Mit if/else in anderen Sprachen hat man sich eine Doppeldeutigkeit eingehandelt. Nach einem if kann ein else kommen, muss aber nicht. Das macht das Lesen von Code ein bisschen schwieriger, als wenn ich either lese und sofort weiß, es werden zwei Blöcke mit Anweisungen kommen.

Die Synatx ist wie man erwartet either CONDITION. Die Condition in unserem Fall ist ein einfacher Vergleich von Integern.

Liste zusammenfügen

Am Ende müssen wir nur noch die Listen richtig zusammenzufügen. Alle kleineren Elemente müssen sortiert links vom Pivot-Element eingefügt werden. Mit insert fügen wir die mit der quicksort-Funktion sortierte Liste am Anfang unserer sortedList hinzu:

insert sortedList (quicksort (copy smallerList))

Gleiches gilt für die sortierte Liste der größeren Elemente, das wir mit dem bereits bekannten append anhängen.

Probleme und Beobachtungen auf dem Weg

Wirklich große Probleme beim Schreiben meines ersten Red-Programms gab es keine. Schwierig war es lediglich, Dokumentation über die Funktionen zu beschaffen. Da sich Red sehr an Rebol orientiert, war das praktisch meine erste Anlaufstelle. Für die Syntax habe ich mich an der Red/System-Spezifikation orientiert.

Positiv überrascht hat mich die einfache Installation unter Linux. Herunterladen, in /usr/bin kopieren und Programm ausführen!

Richtig tricky wurde es bei der Sache mit definitional Scopes. Ich hatte für einfache Listen wie [5 1 3] ein Ergebnis wie [1 3 1 3 1] und ich konnte nicht logisch erklären warum. Erst wie ich alle Variablen lokal gemacht hatte (mit function in der Funktionsdefinition) und zur Initialisierung von lokalen Listen copy verwendet habe, hat es gefunkt.

Resourcen

Red/System Spezifikation (Englisch)