Zum Inhalt springen

Opal (Programmiersprache)

aus Wikipedia, der freien Enzyklopädie

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

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: <syntaxhighlight lang="erlang"> 

  FUN f: nat ** nat -> nat

</syntaxhighlight>

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

Fibonacci

Ein Beispiel für eine Implementierung der Fibonaccifunktion unter Verwendung einer Lambda-Abstraktion: <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

Eine effizientere Implementierung der obigen Folge unter Verwendung von Dijkstra-IF sowie Overloading. <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

Quicksort

Ein Beispiel für eine Implementierung des Quicksortalgorithmus: <syntaxhighlight lang="erlang"> 

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.

</syntaxhighlight>

Selectionsort

Ein Beispiel für eine Implementierung des Selectionsortalgorithmus: <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

Insertionsort

Ein Beispiel für eine Implementierung des Insertionsortalgorithmus: <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

Mergesort

Ein Beispiel für eine Implementierung des Mergesortalgorithmus: <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

Beispiele für Datentypen

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 <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

… eines Summentyps <syntaxhighlight lang="erlang"> 

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

</syntaxhighlight>

… eines Aufzählungstyps <syntaxhighlight lang="erlang"> 

DATA traffic_light == red
                   yellow
                   green

</syntaxhighlight>

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 <syntaxhighlight lang="erlang"> 

-- 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

</syntaxhighlight>

Literatur

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

Weblinks

  • {{#switch:
   |0|=Vorlage:Toter Link/Core{{#if: https://projects.uebb.tu-berlin.de/opal/trac/
       | {{#if: Webseite des OPAL-Projektes | Webseite des OPAL-Projektes }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://projects.uebb.tu-berlin.de/opal/trac/
      | {{#if:{{#invoke:URLutil|isWebURL|https://projects.uebb.tu-berlin.de/opal/trac/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: Webseite des OPAL-Projektes
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 2021-04
       | {{#if:{{#invoke:DateTime|format|2021-04|F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://projects.uebb.tu-berlin.de/opal/trac/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://projects.uebb.tu-berlin.de/opal/trac/
       | {{#if:{{#invoke:URLutil|isWebURL|https://projects.uebb.tu-berlin.de/opal/trac/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 2021-04
         | {{#if:{{#invoke:DateTime|format|2021-04|F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://projects.uebb.tu-berlin.de/opal/trac/ }}

   |0|=Vorlage:Toter Link/Core{{#if: https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/
      | {{#if:{{#invoke:URLutil|isWebURL|https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 2021-04
       | {{#if:{{#invoke:DateTime|format|2021-04|F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/
       | {{#if:{{#invoke:URLutil|isWebURL|https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 2021-04
         | {{#if:{{#invoke:DateTime|format|2021-04|F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://projects.uebb.tu-berlin.de/opal/dosfop/2.4/bibopalicaman/ }}

   |0|=Vorlage:Toter Link/Core{{#if: http://opal.gehaxelt.in/
       | {{#if: Opal-Programme online schreiben und ausführen | Opal-Programme online schreiben und ausführen }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://opal.gehaxelt.in/
      | {{#if:{{#invoke:URLutil|isWebURL|http://opal.gehaxelt.in/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: Opal-Programme online schreiben und ausführen
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 2021-04
       | {{#if:{{#invoke:DateTime|format|2021-04|F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://opal.gehaxelt.in/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2021-04 | , festgestellt im {{#invoke:DateTime|format|2021-04|F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://opal.gehaxelt.in/
       | {{#if:{{#invoke:URLutil|isWebURL|http://opal.gehaxelt.in/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 2021-04
         | {{#if:{{#invoke:DateTime|format|2021-04|F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://opal.gehaxelt.in/ }}
Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Opal_(Programmiersprache)&oldid=449266“