A Miranda programozási nyelv

Felhasználó által definiálható típusok

Felhasználó által definiálható típusok

Az adatsruktúrák új típusok definícióival vannak megadva. Ennek a célnak az elérése érdekében lehetõség van típusok definíciójára algebrai és absztrakt típusdefiníciók révén. Így a típus specifikálja a felhasználó által definiált adatstruktúra minden legális elõfordulását. Az algebrai adattípussal az új adatstruktúra (mint pl.: a rekord) rekurzívan definiálható, már létezõ adatstruktúrák összekapcsolásával. Minden rekord tartalmaz egy megkülönböztetõ adatkonstruktort és nulla vagy több más objektumot, melyeket az adatkonstruktor argumentumainak nevezünk. Az adatkonstruktor egy azonosító, mely egyértelmûen megadja az objektum típusát. Az absztrakt adattípus lehetõvé teszi az adatstruktúrák oly módon való létrehozását, hogy azok aktuális implementációja rejtve legyen a felhasználó elõtt. Az ilyen adatstruktúrákon csak az ún. absztrakt leírással specifikált függvényeket lehet alkalmazni. Az ilyen függvények konkrét definíciója akár a specifikációtól elkülönítve is megadható.

Algebrai adattípus

A (rekurzív) algebrai adattípusok definíciója felsorolja az új adatkonstruktorokat az argumentumaikkal együtt. Az algebrai típusdefiníciók minden lehetséges fajtája egy egyedi megkülönböztetõ adatkonstruktorral kezdõdik. Egy ilyen adatkonstruktor csak egy algebrai típus egy alternatívájában fordulhat elõ. Példák algebrai típus definíciókra:

day ::= Mon | Tue | Wed | Thu | Fri | Sat | Sun
numlist ::= Nillist | Numlist num numlist numtree ::= Niltree | Node num
numtree numtree

Ebben a definícióban van elõre definiált típus (num), a felhasználó által definiált algebrai típus (day, numlist, numtree) és a felhasználó által definiált adat konstruktor (Mon,...,Sun, Nillist, Numlist, Niltree, Node).
Az adatkonsruktorok feltûnhetnek függvény definíciók kifejezéseiben, melyek új objektumát hozzák létre a specifikált algebrai típusnak; mintáiban, adott formájú struktúrák kiválasztására vagy vetítõ függvények képzésére az adatkonstruktor argumentumaihoz való hozzáférés érdekében. Algebrai típus objektumainak konstruálása:

payment_day:: day
payment_day = fri

tree1:: numtree
tree1 = Node 1 (Node 3 Niltree Niltree) Niltree

Az adatkonstruktort, mint mintát használva, a következõ függvény a numtree tükörképét eredményezi:

mirror Niltree = Niltree
mirror (Node n l r) = Node n (mirror r) (mirror l)

Az algebrai adattípus definíciójában egy új megkülönböztetõ konstruktor szükséges minden új típushoz és minden új alternatívához. Ez lehetõvé teszi például általános Nil definiálását. Minden új típushoz szükséges egy saját speciális konstruktor a típus üres objektumának jelölésére.
Az algebrai típusok lehetnek polimorfak. Egy vagy több általános típusváltozó használható paraméterként a típus definícióban. Polimorf típus definíció:

tree* ::= Niltree | Node * (tree*) (tree*)

Ezt a polimorf algebrai típus definíciót lehet használni például a következõ módon:

numtree == tree num.

Ezen a módon a fatípusok családját lehet definiálni (ez tartalmazza pl. a következõ típusokat: tree num, tree bool, tree (num->num) ...).
Fontos tudni, hogy elvben a Miranda minden elõre definiált típusa definiálható polimorf algebrai típus definíciókkal. Az elõre definiált típusok algebrai típus definíciója:

bool ::= True | False
char ::= a | b | ...
[*] == list * ::= Nil | Cons * (list *)
(*,**) == tuple2 * ** ::= Tuple2 * **

De az elõre definiált típusok algebrailag való definiálása a gyakorlatban kényelmetlen és használhatatlan mind idõben, mind méretre.

Absztrakt adattípus

A konkrét típusok (melyeket a ::= vagy a ==-vel vezettünk be) kiegészítéseképp a Miranda lehetõvé teszi absztrakt adattípusok megvalósítását is, melyek implementációja rejtve marad a program többi része elõl. Rögtön egy példát nézve lássuk a szabványos verem absztrakt megvalósítását jelen esetben listák segítségével:

abstype stack * with empty:: stack *
                  isempty:: stack *->bool
                      push:: *->stack *->stack *
                       pop:: stack *->stack *
                       top:: stack *->*
stack * == [*]
empty = []
isempty x = (x=[])
push a x = (a:x)
pop (a:x) = x
top (a:x) = a

Láthatjuk, hogy az absztrakt adattípus definíciója két részbõl áll. Az elsõ a deklarációs rész az abstype ... with ..., ahol a with utáni neveket az absztrakt adattípus szignatúrájának nevezzük. Ezek a nevek a látható felület az absztrakt adattípus és a program többi része között. Ezek után néhány megszorítás következik a szignatúrákban felsorolt nevekre, egyenletek formájában. Ezeket hívjuk implementációs egyenleteknek. Az implementációs egyenleteknek nem kell közvetlenül a megfelelõ abstype definíció mögött állni, akárhol elhelyezkedhetnek a leírásban.