# Opal (programming language)

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 `FUN`used 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 `FUN`may also be in the implementation part, but such functions can then only be used in the respective structure.

The functions are `DEF`implemented in the source code with the keyword (see examples). Also in the implementation, the word describes `DATA`a self-defined data type, the signature of which can also `.sign`be made `TYPE`known 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
IN
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)
```

... 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 `DATA`adds 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