Frank Steiner:

A Difference-List Transformation for Functional Logic Languages
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Abstract 

Neben den aus der funktionalen Programmierung bekannten
Transformationen wie Deforestation etc., gibt es auch in der
Logikprogrammierung Optimierungsverfahren fuer listenverarbeitende
Funktionen/Praedikate.  Die bekannsteste Optimierung ist die
Verwendung von Differenz-Listen, die z.B. die Verknuepfung von 2
Listen in konstanter Zeit ermoeglicht.  In der Logikprogrammierung
kann dies u.a. dazu benutzt werden, rekursive Praedikate, die die
Ergebnislisten ihrer rekursiven Aufrufe konkatenieren (wie
z.B. quicksort), in wesentlich effizientere Praedikate zu uebersetzen.
Dabei werden mit Hilfe zusaetzlicher Parameter die Teillisten schon
waehrend der rekursiven Aufrufe akkumuliert anstatt die Ergebnisse am
Ende zu konkatenieren.

Eine direkte Uebernahme von Differenz-Listen in funktional-logische
Programmiersprachen wie z.B. Curry ist u.a. aufgrund der geforderten
Links- linearitaet der Regelseiten nicht moeglich. Dennoch kann mit
Hilfe der Differenz-Listen als voruebergehendes Konstrukt eine
Transformation durchgefuehrt werden, an deren Ende wieder ein
gueltiges funtional-logisches Programm steht, das nun mit Hilfe
akkumulierender Parameter eine wesentlich effizientere Verarbeitung
von Listen ermoeglicht.  Beispielsweise kann so die folgende
ineffiziente Version von reverse

rev []     = []
rev (x:xs) = rev xs ++ [x]

mit Laufzeit O(n!) in die effizientere, akkumulierende Version

rev y = rev* y []

rev* []     y = y
rev* (x:xs) y = rev xs (x:y)

mit linearer Laufzeit ueberfuehrt werden.

Wir haben anhand von Curry einen Algorithmus entwickelt, der die
Moeglichkeit fuer eine solche Transformation erkennen und diese dann
automatisch durchfuehren kann.