Az ML modul rendszerének alapvetô elemei a szignatúrák és a struktúrák. A szignatúrák struktúrákat specifikálnak, szerepüket tekintve tehát más nyelvek interfészeihez, osztály típusaihoz, csomag specifikációihoz hasonlíthatjuk ôket, míg a szignatúrákat implementáló struktúrák az implementációk, osztályok vagy csomagok szerepét töltik be.
Szignatúrák
Egy szignatúra egy program modul, struktúra leírása, specifikációja. Egy struktúra tartalmazhat minden olyan deklarációt, amelyrôl eddig szó volt: típus konstruktorokat, kivételeket, kötéseket, és olyanokat is amelyek a modularizációt támogatják: alstruktúrákat és alstruktúrák megosztását. Egy szignatúra egy struktúra ezen deklarációink elemenkénti specifikációja. Egy struktúra megfelel egy szignatúrának vagy implementál egy szignatúrát, ha tartalmazza a szignatúrában specifikált, vagy azoknál általánosabb típusú deklarációkat.
Egy szignatúrakifejezés alakja a következô: sig specifikációk end
ahol specifikációk a következô alapelemekbol állhat:
- típus specifikációból, melynek alakja:
type típusváltozók típuskonstruktor[= típuskifejezés] - adattípus specifikációból, amely a típus specifikációkkal megegyezô alakú
- érték (kötés) specifikációból, melynek alakja:
val azonosító : típuskifejezés - kivétel specifikációból, melynek alakja:
exception kivételkonstruktor of típuskifejezés
A szignatúrakifejezéseknek egy szignatúrakötéssel nevet is adhatunk a következôképpen: signature azonosító = szignatúrakifejezés
Tekintsük a következô egyszerû példát, amelyben az a egy típusváltozó és használata által a sor alábbi specifikációja polimorf a sor elemtípusát illetôen:
signature QUEUE =
sig
type ‘a queue
exception Empty
val empty : ‘a queue
val insert : ‘a * ‘a queue -> ‘a queue
val remove : ‘a queue -> ‘a * ‘a queue
end
Már meglévô szignatúrákat kétféleképpen használhatjuk újra, új szignatúrák definiálásához: beágyazással és specializációval. Nézzünk ezekre egy-egy példát:
signature QUEUE_WITH_TEST =
sig
include QUEUE
val is_empty : ‘a queue -> bool
end
signature QUEUE_AS_LISTS =
QUEUE where type ‘a queue = ‘a list * ‘a list
A beágyazást tehát a szignatúra bôvítésére használhatjuk, míg a specializáció az implementációhoz visz közelebb, az absztrakt típusok reprezentációjának megadásával.
Fontos megjegyezni, hogy két szignatúra ekvivalens, ha a specifikációk páronként típusekvivalensek.
Struktúrák
Egy struktúra egy deklarációk sorozatából álló program egység. Egy
struktúrakifejezés alakja a következô: struct deklarációk end
ahol deklarációk a korábbi fejezetekben részletezett típus, adattípus, érték
(val vagy fun kötés), és kivétel deklarációk sorozata.
Struktúrakötéssel a struktúrakifejezéseket is köthetjük egy-egy azonosítóhoz a következôképpen: structure azonosító = struktúrakifejezés
Példaként tekintsük a fenti QUEUE szignatúra következô polimorf implementációját (a két listás reprezentációt az indokolja, hogy az ML-ben beépítetten támogatott lista típus, mûveleteit tekintve inkább veremként mûködik):
structure Queue =
struct
type a' queue = a' list * a' list
exception Empty
val empty = (nil, nil)
fun insert (x, (h,t)) = (x::h,t)
fun remove (nil,nil) = raise Empty
| remove (h,nil) = remove (nil, rev h)
| remove (h, x::t) = (x, (h,t))
end
Egy struktúra elemeire minôsített azonosítókkal hivatkozhatunk, például:
val q0 = Queue.insert( 0, Queue.empty )
Lehetôség van továbbá struktúrák megnyitására az open struktúraazonosítók paranccsal, aminek hatására az adott struktúrák deklarációi a környezet részévé és minôsítés nélkül elérhetôvé válnak. Amilyen kényelmes, épp olyan veszélyes is ez a lehetôség, hiszen így könnyen, akaratlanul is felüldefiniálhatunk egyes azonosítókat. Éppen ezért óvakodjunk struktúrák megnyitásától, és olyankor is csak a hatáskört korlátozó blokkokon belül éljünk ezzel a lehetôséggel(a deklarációs részben).
Megfelelés
Ahogyan minden (jól formált) kifejezésnek megvan a legáltalánosabb típusa, amelynek a típuskompatibilitás során van meghatározó szerepe, ugyanúgy minden (jól formált) struktúrának megvan a legáltalánosabb szignatúrája, amely a szignatúra megfelelés definíciójában játszik hasonló szerepet. Egy struktúra legáltalánosabb szignatúrája egy-az-egyben tartalmazza a struktúra típus, adattípus és kivétel deklarációit, és az érték deklarációkban (val vagy fun kötésekben) szereplô azonosítókat a hozzájuk kötött kifejezések legáltalánosabb típusával specifikálja.
Egy szignatúra Sig1 megfelel egy másik Sig2 szignatúrának, ha annak szigorításának tekinthetô a következô értelemben:
- Sig2-ben szereplô minden típuskonstruktor Sig1-ben is megtalálható, mégpedig azonos aritással és típusekvivalens definícióval. (Egy Sig1-beli típuskonstruktor specifikációja akkor is tartalmazhat definíciót, ha a neki megfelelô Sig2-beli típuskonstruktor nincsen definiálva.)
- Minden Sig2-beli adattípus Sig1-ben is kell, hogy szerepeljen, mégpedig páronként ekvivalens értékkonstruktorokkal.
- Minden Sig2-beli kivétel konstruktor Sig1-ben is kell, hogy szerepeljen, mégpedig ekvivalens argumentumokkal.
- Minden Sig2-beli érték specifikáció Sig1-ben is kell, hogy szerepeljen, mégpedig legalább olyan általános típussal.
- Egy Sig1-beli adattípus specifikáció megfelelhet egy Sig2-beli definíció nélküli (absztrakt) típusspecifikációnak, miközben az adattípus értékkonstruktorai Sig2-beli érték specifikációknak felelhetnek meg. Például
- Sig1 ezen kívül több komponenst is tartalmazhat és több típusegyenletnek is megfelelhet, de nem kevesebbnek.
datatype a' bintree = Root | Node a' of bintree * a' * a' bintree
megfelel a
type a' bintree
val Root : a' bintree
val Node : a' of bintree * a' * a' bintree -> a' bintree
specifikációknak
A definíció következménye, hogy a szignatúra megfelelés egy parciális rendezés, amely nem tesz különbséget ekvivalens szignatúrák között.
A fenti példák közül QUEUE_WITH_TEST és QUEUE_AS_LISTS megfelelnek a QUEUE szignatúrának, sôt látható, hogy általában minden szignatúra megfelel minden beágyazott szignatúrájának illetve minden specializált szignatúra megfelel annak a szignatúrának, amelybôl specializációval nyertük. A beágyazás és a specializáció tehát monoton mûveletek a megfelelésre mint részbenrendezésre nézve.
Végezetül egy struktúra pontosan akkor felel meg egy szignatúrának, amikor a legáltalánosabb szignatúrája. A fenti példában említett Queue struktúra tehát megfelel a QUEUE, sôt a QUEUE_AS_LISTS szignatúrának, de nem felel meg QUEUE_WITH_TEST-nek.
Megfeleltetés
A fentiekben elmondottakon túlmenôen lehetôség van struktúrák példányosítására olymódon, hogy egy struktúrakötés során egy azonosítónak megfeleltetünk egy kívánt szignatúrát és egy annak megfelelô, azaz azt implementáló struktúrát. Kétféle megfeleltetés lehetséges: átlátszó és átlátszatlan, amely elnevezések a struktúrában deklarált típusok reprezentációjának nyílt vagy rejtett voltára vonatkoznak. A két megfeleltetés deklarációja a következô szintaxis szerint történhet:
- structure azonosító : szignatúra = struktúra átlátszó megfeleltetés esetén, illetve
- structure azonosító :> szignatúra = struktúra átlátszatlan megfeleltetés esetén
Mindkét esetben követelmény, hogy struktúra a korábban vázolt szabályok szerint megfeleljen szignatúra-nak és mindkét esetben a megadott struktúra kötôdik mint implementáció az azonosítóhoz. A két deklaráció közötti eltérés abban áll, hogy míg az utóbbi (átlátszatlan) esetben az azonosítóhoz a deklarációban rögzített szignatúra kötôdik, addig az első (átlátszó) esetben az azonosítóhoz kötött szignatúra a deklarált szignatúrának az implementációból vett típusinformációkkal kiegészített szigorítása. Pontosabban a deklarációban szereplő struktúra legáltalánosabb szignatúrájából (amely a követelmények értelmében megfelel a deklarált szignatúrának) a deklarált szignatúra absztrakt típusainak struktúrabeli reprezentációja is megjelenik a megfeleltetett szignatúrában.
Tekintsük a következô példákat:
structure Q1 :> QUEUE = Queue
structure Q2 : QUEUE = Queue
structure Q3 :> QUEUE_AS_LISTS = Queue
Mindhárom struktúra azonos, a Queue-ból "örökölt" két listával reprezentált polimorf sort valósít meg azonos módon. A második deklarációban átlátszó megfeleltetést alkalmaztunk, míg az elsôben és a harmadikban átlátszatlant. Ennek eredményeképpen
- Q1-hez a QUEUE szignatúra kötôdik, absztrakt, tehát átlátszatlan a' queue típussal, tehát a Q1.remove(0::1::2,nil) kifejezés nem jól formált, mert a Q1.int queue és az int list * int list típusok nem ekvivalensek.
- a Q2-nek megfeleltetett szignatúra a QUEUE szignatúrából a Queue struktúrában szereplô két listás rereprezentációval kiegészített szignatúra, amely ekvivalens QUEUE_AS_LISTS -tel. Íly módon a Q2 struktúra használói számára a Q2.a' queue típus reprezentációja átlátszó, így például megengedettek a Q2.int queue sorok komponensein végrehajtott lista mûveletek.
- Q3-hoz a QUEUE_AS_LISTS szignatúra kötôdik, amely szintén propagálja a két listás reprezentációt a külvilág felé.
A második és a harmadik deklaráció tehát egyenértékû és jelen esetben az elsô változat ajánlott, amely, helyesen, elrejti a sor típus reprezentációját. A minél hatékonyabb modularizáció érdekében minden olyan esetben célszerû elrejteni egy szignatúrában szereplô típus reprezentációját, amikor csak lehetséges. Az átlátszóság elkerülhetetlen és értelmetlen abban az esetben, ha a szignatúra nem tartalmazza az absztrakt típus elemeinek létrehozásához szükséges érték konstruktorokat. Jó példa erre a következô specifikáció:
signature ORDERED =
sig
type t
var lt : t * t -> bool
end
Ez a szignatúra csak valamilyen konkrét reprezentációval együtt használható, hiszen nincsen lehetôség t típusú értékek deklarálására.
Fontos megjegyezni, hogy átlátható megfeleltetés során (a megfeleltetett, eredő szignatúra meghatározásához) szükség van az implementáló struktúra forráskódjára, tehát az implementáció változtatása maga után vonja a hivatkozó kódrészek újrafordítását, esetleg megváltoztatását. Átlátszatlan megfeleltetéssel ezzel szemben implementációtól független kliens kódot hozhatunk létre.
Eddigieket összefoglalva valósítsuk meg a map adattípust példaként!
signature map = sig
type (''a,'b) map
exception Ures
val create: (''a,'b) map
val set: (''a,'b) map *''a*'b -> (''a,'b) map
val get: (''a,'b) map*''a->'b
end
structure MapStr :> map = struct
type (''a,'b) map= (''a*'b) list
exception Ures
val create = []
fun get ([],e) = raise Ures
|get (((g,f)::t),e) = if g=e
then f
else get(t, e)
fun set ([], e,f) = [(e,f)]
|set ((h::t),e,f) = (e,f)::(h::t)
end;
val m=MapStr.set(MapStr.create,4,5);
val m2=MapStr.set(m,6,6);
val e=MapStr.get(m,5);
Érdemes elgondolkodni a Map print függvényének a megírásán! Ezt a kis apróságot az olvasóra bízom!
Funktorok
Nagyon hasznos eszköz az új modulok készítésére. Funktorok segítségével olyan struktúrát definiálhatunk, amelyet más struktúrákkal paraméterezhetünk.
A funktorok speciális többváltozós függvények, melyek bizonyos szignatúráknak megfelelő struktúrák teréről képeznek egy adott szignatúrának megfelelő struktúrák terére. A leképezés módját a funktor definíciója során adjuk meg. Az értelmezési tartományt szűkíthetjük az alapértelmezett Descartes szorzatról úgy, hogy megköveteljük egyes, a funktor paraméterrészében lévő szignatúrákban szereplő típusok ekvivalenciáját.
A következő példában egy t egyenlőséggel ellátott típust tartalmazó struktúrából csinálunk egy új struktúrát, amely ugyancsak megfelel a SIG szignatúrának, de a benne lévő t típus a paraméterben lévő típus direkt szorzata, az egyenlőség pedig a komponensenkénti egyenlőség.
- signature SIG =
sig
type t
val eq : t*t -> bool
end;
- functor F( P : SIG ) : SIG =
struct
type t = P.t * P.t
fun eq((x,y),(u,v)) = P.eq(x,u) andalso P.eq(y,v)
end;
> functor F( P : SIG ) : SIG //megj.: minden “>”-el kezdődő sor a fordító válasza
Most készítsünk a SIG szignatúrának megfelelő struktúrát és készítsük el a funktorunk segítségével az új t direktszorzatot tartalmazó SS struktúrát:
- structure S : SIG =
struct
type t = int
val eq : t*t->bool = op =
end;
> structure S =
struct
type t = int
val eq = fn : t*t->bool
end
- structure SS : SIG = F(S);
> structure SS =
struct
type t = int*int
val eq = fn : t*t->bool
end
Most szerepeljen egy példa arra mikor csonkítás történik.:
- structure T : SIG =
struct
type t = string * int
val eq : t*t->bool = op =
fun f(x:t) = (x,x)
end;
> structure T =
struct
type t = string * int
val eq : t*t->bool
end
- structure TT : SIG = F(T);
> structure TT =
struct
type t = (string*int)*(string*int)
val eq : t*t->bool
end
Funktorokat funktorok segítségével is definiálhatunk:
- functor G( P : SIG ) : SIG = F(F(P));
> functor G( P : SIG ) : SIG
- functor I( P : SIG ) : SIG = P;
> functor I( P : SIG ) : SIG
Az I használatára egy példa.:
- structure S =
struct
type t = int
val eq = op =
fun f(x) = x
end;
> structure S =
struct
type t = int
val eq = fn : int*int -> bool
val f = fn : 'a -> 'a
end
- structure S' = I(S);
> structure S' =
struct
type t = int
val eq = fn : int*int -> bool
end
Most legyen egy példa többváltozójú funktorra is, ahol még az értelmezési tartományt is szűkítjük. Itt egy olyan modult definiálunk, amely egy vermet és egy listát tartalmaz, de megkötjük hogy ugyazon elemtípust használják.
functor F(V : VEREM L : LIST sharing type V.Elem=L.Elem) : FSIG=struct ... end
Ez a típusokra vonatkozó megszorítás szignatúrák definiálása esetén is alkalmazható:
signature GSIG =
sig
structure Verem : VEREM
structure Lista : LISTA
sharing Velem.Elem=Lista.Elem
end
Egy másik példa:
signature PARSER_PIECES =
sig
structure SymboiTable : SYMBOLTABLE
structure AbstSyntax: ABSTSYNTAX
sharing SymbolTable.Symbol = AbstSyntax.Symbol
end;
Modulok fordítása (Moskov ML fordítóval)
| Kiterjesztés | Tartalom |
| * .sig * .sml * .ui * .uo |
|
A unitid nevű modul fordítása és a mosml környezetébe való betöltése:
mosmlc -c -structure unitid.sig unitid.sml
mosml
> load "unitid";
Itt a unititid.sig fájl egy darab szignatúra definíciót kell tartalmazzon, a unitid.sml pedig ennek a szignatúrának megfelelő struktúrát.
Egy példa a verem modulra:
A specifikáció stack.sig tartalma:
signature STACK =
sig
type 'a stack
exception Empty
val empty : 'a stack
val push : 'a stack * 'a -> 'a stack
val pop : 'a stack -> 'a stack
end
Az implementáció stack.sml tartalma:
structure STACK :> STACK =
struct
datatype 'a stack = empty | push of 'a stack * 'a
exception Empty
fun pop(empty)= raise Empty
|pop(push(s,e))=s
end
a mosmlc –structure stack.sig stack.sml parancsal fordítva megkapjuk a stack.ui és a stack.uo lefordított egységeket.
A mosml környezetben a load “stack” parancsal be is tölthetjük a lefordított modult(fordítás után már nincs szükség a forrásállományokra).
Megjegyzés: az implementációs modulban a struktúrát csak átlátszatlan megfeleltetéssel hozhatjuk létre( :> és nem :), hiszen ha nem így tennénk az implementáció(pontosabban az implementációs modulban lévő reprezentáció) megváltoztatásakor nem lenne elég csak a modult újrafordítani, hanem az összes ezen modult felhasználó más programegységet is újra kellene fordítani, holott a modulokra bontás egyik alapvető koncepciója, hogy egymástól függetlenül fordítható programegységeket lehessen létrehozni. Átlátszó megfeleltetés esetén a legáltalánosabb szignatúra változna.
Funktorok segítségével is hozhatunk létre modulokat:
evaluate.sig tartalma:
functor Eval : functor(R:Reduce) ->
sig
val eval: Expr.expr -> int
val test: Expr.expr -> bool
end
evaluate.sml tartalma
functor Eval(R:Reduce) =
struct
local open Expr in
fun eval (Cst n) = n
| eval (Neg e) = ~ (eval e)
| eval (Plus (e1, e2)) = eval e1 + eval e2;
fun test e = (eval e = eval (R.reduce e))
end
end