Opal (Programmiersprache)

Van Wikipedia, de gratis encyclopedie

OPAL (Optimized Applicative Language) ist eine funktionale Programmiersprache, die 1986 an der TU Berlin unter der Leitung von Peter Pepper entwickelt wurde. Die Sprache diente dort vor allem als Testumgebung. Anfangs ging es zunächst darum, die Sprache effizient zu implementieren. Später wurde das komplette Feld funktionaler Konzepte mit einbezogen. Dazu gehören insbesondere:

Im Gegensatz zu anderen funktionalen Sprachen wie Haskell ist OPAL nicht standardisiert. Das erlaubt den Entwicklern, viel mit diversen Merkmalen, die sie für interessant erachten, zu experimentieren.

Der grobe Aufbau eines OPAL-Programms[Bearbeiten | Quelltext bearbeiten]

OPAL-Programme (Strukturen, siehe auch Algebraische Struktur) bestehen aus einem Signaturteil (Dateiendung .sign) und einem Implementationsteil (Dateiendung .impl). Im Signaturteil werden die Sorten sowie die Definitions- und Wertebereiche aller Funktionen beschrieben. Hierzu wird das Schlüsselwort FUN gebraucht: 

   FUN f: nat ** nat -> nat

deklariert beispielsweise eine Funktion f, deren Definitionsbereich ein Tupel aus zwei Werten vom Typ nat (für natürliche Zahlen) und deren Wertebereich ebenfalls die Sorte nat darstellt. Das Schlüsselwort FUN darf auch im Implementationsteil stehen, solche Funktionen können dann aber nur in der jeweiligen Struktur verwendet werden.

Im Quellcode werden die Funktionen mit dem Schlüsselwort DEF implementiert (siehe Beispiele). Ebenfalls in der Implementation wird mit dem Wort DATA ein selbstdefinierter Datentyp beschrieben, dessen Signatur in der .sign-Datei mittels TYPE auch global bekanntgegeben werden kann.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Fibonacci[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel für eine Implementierung der Fibonaccifunktion unter Verwendung einer Lambda-Abstraktion: 

    DEF fibo == \\n.       IF n = 0 THEN 0       IF n = 1 THEN 1       IF n >= 2 THEN fibo(n-1)+fibo(n-2) FI

Eine effizientere Implementierung der obigen Folge unter Verwendung von Dijkstra-IF sowie Overloading. 

 FUN fib: nat -> nat  DEF fib(x) ==    IF x=0 THEN 0    IF x=1 THEN 1    IF x>1 THEN fib(2, 1, 1, x)    FI   FUN fib: nat ** nat ** nat ** nat -> nat  -- idx : momentaner Index  -- p1 : fib(idx)  -- p2 : fib(idx-1)  -- max : der Index des zu berechnenden Folgengliedes  -- Beispiel: fib(6) -> fib(2, 1, 1, 6) -> fib(3, 2, 1, 6) -> fib(4, 3, 2, 6) ->  -- fib(5, 5, 3, 6) -> fib(6, 8, 5, 6) => 8  DEF fib(idx, p1, p2, max) ==    IF idx<max THEN fib(idx+1, p1+p2, p1, max)    IF idx=max THEN p1    FI

Quicksort[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel für eine Implementierung des Quicksortalgorithmus: 

 FUN sort: seq[nat] -> seq[nat]  DEF sort(<>) == <>   -- Die leere Sequenz (geschrieben als <>) ist bereits sortiert   DEF sort(a :: R) ==    LET      Small == (_ < a) | R        -- Sei Small die Sequenz R, gefiltert mit der Funktion "< a". Small besteht damit aus allen Elementen in R, die kleiner sind als a        -- Small entsteht aus der Applikation der Funktion "|" (Filter) auf die Argumente "(_ < a)", einer Funktion nat -> bool, und der Sequenz "R"        -- Opal erlaubt die Prefix-, Infix- und Postfix-Notation, sowie die Vergabe von Identifikatoren aus Sonderzeichen.        --  Der o.a. Ausdruck ist identisch zu "| ( _ < a, R)"      Medium == a :: (_ = a) | R        -- Medium enthält das erste Element a und alle Elemente in R, die gleich a sind      Large == (_ > a) | R        -- Large ist dann die Sequenz, die alle Zahlen aus R enthält, die größer als a sind    IN      sort(Small)++Medium++sort(Large)      -- Das Resultat ist die Konkatenation der ihrerseits sortierten Sequenz Small, Medium und der sortierten Sequenz Large.

Selectionsort[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel für eine Implementierung des Selectionsortalgorithmus: 

 FUN ssort: seq[nat] -> seq[nat]  DEF ssort(<>) == <>  DEF ssort(liste) ==    LET      minimum == min(liste)      restliste == cut(minimum,liste)    IN      minimum :: ssort(restliste)  FUN cut: nat ** seq[nat] -> seq[nat]  DEF cut(x,a::A) ==    IF a = x THEN A    ELSE a :: cut(x,A) FI  FUN min: seq[nat] -> nat  DEF min(a::A) == minHelp(a,A)  FUN minHelp: nat ** seq[nat] -> nat  DEF minHelp(a,<>) == a  DEF minHelp(a,A) ==    IF a < ft(A) THEN minHelp(a,rt(A))    ELSE minHelp(ft(A),rt(A)) FI

Insertionsort[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel für eine Implementierung des Insertionsortalgorithmus: 

 FUN isort: seq[nat] -> seq[nat]  DEF isort(<>) == <>  DEF isort(a::A) == a insert isort (A)  FUN insert: nat ** seq[nat] -> seq[nat]  DEF x insert <> == x :: <>  DEF x insert (a::A) ==    IF x <= a THEN x::(a::A)    ELSE a::(x insert A)    FI

Mergesort[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel für eine Implementierung des Mergesortalgorithmus: 

 FUN msort: seq[nat] -> seq[nat]  DEF msort(<>) == <>  DEF msort(a:: <>) == a:: <>  DEF msort(liste) ==    LET      i == #(liste)/2      (links, rechts) == split(i,liste)    IN      msort(links) merge msort(rechts)  FUN merge: seq[nat] ** seq[nat] -> seq[nat]  DEF <> merge <> == <>  DEF a merge <> == a  DEF <> merge a == a  DEF (a::A) merge (b::B) ==    IF a <= b THEN a::( A merge (b::B) )    ELSE b::( B merge (a::A) )    FI

Beispiele für Datentypen[Bearbeiten | Quelltext bearbeiten]

Während in der Theorie zwischen verschiedenen Formen von Datentypen unterschieden wird, hat OPAL nur ein Konstrukt, um eigene Typen zu definieren.

Ein Beispiel für eine Implementierung eines Produkttyps 

 DATA point3D == point3D(x:real, y:real, z:real)

… eines Summentyps 

 DATA object3D == cube(width: real, height: real, length: real, location: point3D)                  cylinder(height: real, radius: real, location: point3D)                  sphere(radius: real, location: point3D)

… eines Aufzählungstyps 

 DATA traffic_light == red                     yellow                     green

Datentypdeklarationen (TYPE) ersetzt der OPAL-Compiler intern durch die sogenannte „induzierte Signatur“. Das Schlüsselwort DATA fügt auch Implementierungen der Funktionen hinzu, die dem Programmierer dann die Möglichkeit geben, Werte der selbstdefinierten Sorte zu erzeugen, auf die einzelnen Elemente der Datenstruktur zuzugreifen und zwischen Varianten zu unterscheiden:

Z. B. die induzierte Signatur für den Summentyp 

 -- Sorte   SORT object3D  -- Konstruktorfunktionen   FUN cube: real ** real ** real ** point3D -> object3D   FUN cylinder: real ** real ** point3D -> object3D   FUN sphere: real ** point3D -> object3D  -- Selektorfunktionen   FUN width height length radius: object3D -> real   FUN location: object3D -> point3D  -- Diskriminatorfunktionen   FUN cube?: object3D -> bool   FUN cylinder?: object3D -> bool   FUN sphere?: object3D -> bool

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Peter Pepper: Funktionale Programmierung in OPAL, ML, HASKELL und GOFER. Springer-Verlag, 1999, ISBN 3-540-64541-1

Weblinks[Bearbeiten | Quelltext bearbeiten]

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Opal_(Programmiersprache)&oldid=210955320“