Opal (programming language)

from Wikipedia, the free encyclopedia

OPAL ( Optimized Applicative Language ) is a functional programming language that was developed in 1986 at the TU Berlin under the direction of Peter Pepper . The language mainly served as a test environment. In the beginning, it was first about implementing the language efficiently. Later, the entire field of functional concepts was included. These include in particular:

Unlike other functional languages ​​like Haskell , OPAL is not standardized. This allows developers to experiment a lot with various features that they find interesting.

The rough structure of an OPAL program

OPAL programs (structures, see also Algebraic Structure ) consist of a signature part (file extension .sign) and an implementation part (file extension .impl). In the signature part, the types as well as the definition and value ranges of all functions are described. The keyword is FUNused for this: 

   FUN f: nat ** nat -> nat

declares a function f , for example , whose domain represents a tuple of two values ​​of the type nat(for natural numbers) and whose value range also represents the type nat. The keyword FUNmay also be in the implementation part, but such functions can then only be used in the respective structure.

The functions are DEFimplemented in the source code with the keyword (see examples). Also in the implementation, the word describes DATAa self-defined data type, the signature of which can also .signbe made TYPEknown globally in the file .

Examples

Fibonacci

An example of an implementation of the Fibonacci function using a lambda abstraction : 

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

A more efficient implementation of the above sequence using Dijkstra IF as well as 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

An example of an implementation of the quicksort algorithm : 

 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.

Selection location

An example of an implementation of the selection sorting algorithm : 

 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

Insertion location

An example of an implementation of the insertion sorting algorithm : 

 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

Merge sort

An example of an implementation of the merge sort algorithm : 

 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

Examples of data types

While in theory a distinction is made between different forms of data types , OPAL only has one construct to define your own types.

An example of an implementation of a product type 

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

... of a total type 

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

... of an enumeration type 

 DATA traffic_light == red
                    yellow
                    green

The OPAL compiler replaces data type declarations (TYPE) internally with the so-called "induced signature". The keyword also DATAadds implementations of the functions, which then give the programmer the opportunity to generate values ​​of the self-defined type, to access the individual elements of the data structure and to differentiate between variants:

E.g. the induced signature for the sum type 

 -- 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
 -- Diskrimitatorfunktionen
  FUN cube?: object3D -> bool
  FUN cylinder?: object3D -> bool
  FUN sphere?: object3D -> bool

literature

  • Peter Pepper: Functional programming in OPAL, ML, HASKELL and GOFER . Springer-Verlag, 1999, ISBN 3-540-64541-1

Web links