Az ML programozási nyelv

Típusok

Szigorú típusosság

Nem minden funkcionális programozási nyelv gyengén típusos. Az ML egy olyan funkcionális programozási nyelv, amely szigorúan típusos, és statikus típusellenőrzéssel rendelkezik (tehát fordítási/értelmezési időben történik a típusellenőrzés). Az ML -ben erős típus-kitalálás is van. Nem úgy mint a legtöbb programozási nyelvben, az ML programozónak nem kell specifikálnia minden esetben a függvények argumentumainak és visszatérési értékeinek a típusát, mivel az interpreter nagyon jó a helyes típus megtalálásában. Például, mivel az értelmező tudja, hogy a 2 egész szám, kitalálja, hogy a visszatérési értéknek is egész számnak kell lennie. Az ML értelmező érték - típus párokat ad vissza:

2+2; val it = 4 : int

Felhasználói túlterhelés nincs, mert aláássa a típuslevezetést.

Egyszeru típusok és típuskonstrukciók

Az ML -ben megtalálható egyszerű típusok:

Ezekből objektumokat konstruálhatunk rendezett n -esek (tuple), listák, függvények és rekordok segítségével. Saját alaptípust is készíthetünk - erről részletesebben később lesz szó. Egy rendezett n -es (akár különböző típusú) objektumok sorozata. Néhány rendezett n -es:

( 2, "Andrew" ) : int * string
( true, 3.5, "x") : bool * real * string
( (4,2), (7,3) ) : (int * int) * (int * int)

Amíg a rendezett n -esekben különböző típusú objektumok lehetnek, de fix hosszan, addig a listákban megegyező típusú objektumok lehetnek, de tetszőleges hosszan. Néhány lista:

[ 1, 2, 3 ] : int list
[ "Andrew", "Ben" ] : string list
[ (2,3), (2,2), (9,1) ] : (int * int) list
[ [], [1], [1,2] ] : int list list

Konstrukciós művelettel:

3::5::nil : int list
[ ["Laci","Levi"], "Peti"::nil ] : string list list

Megjegyzés: az [1,2] és az [1,2,3] objektumoknak ugyanaz a típusa, nevezetesen egész számokból álló lista, de az (1,2) és az (1,2,3) különböző típusúak! Az egyik "int * int", míg a másik "int * int * int". Fontos ismernünk az egyes objektumok típusait. Amíg valaki az ML -t tanulja, a legtöbb hiba a nem megfelelő típuskezelésből származik.

Polimorfizmus

Segítségével írhatunk generic függvényeket - tehát a típusát a függvénynek nem kell megadni. (Időnként azért nem árt; típusa pl.: 'a->'a -a szerk.) Például, vegyünk egy olyan függvényt (length) amely visszaadja egy lista hosszát. Természetesen ez egy előre definiált függvény. Nem számít, hogy milyen típusú listának kívánjuk meghatározni a hosszát. Ennek a függvénynek a típusa így:

length: 'a list -> int

az 'a típusváltozó minden ML típus előtt állhat.

MJ: A list ekkor önmagában nem is egy típus, hanem egy postfix pozíciójú típusoperátor függvény. Az 'a típusváltozóval együtt alkot típust ebben a példában.

Amikor a függvényeket úgy definiáljuk, hogy a paraméterének vagy a visszatérési értékének típusát nem adjuk meg, akkor a fordító ezeket automatikusan vezeti le a függvény definíciója alapján. Ha a definícióban nem használjuk ki valamely típus speciális műveletét, akkor típusváltozó lesz a típusa az argumentumnak vagy a visszatérési értéknek. A fenti példában ez az 'a (ejtsd: alfa). Ekkor a függvény bármely típusú paraméterrel meghívva működni fog és a visszatérési értéke e típusok alapján lesz meghatározva. Pl.: ha a max: 'a list -> 'a függvényt int list típusú paraméterrel hívjuk meg, akkor int típusú értéket ad vissza. Nem csak 'a típusváltozó van az ML-ben, ugyanis lehetséges, hogy a típus felhasználása közben szükségünk van az egyenlőségre. Ekkor a fordító egyenlőségi típust vezet le, amelyet ''a -val jelöl(két percjel és nem aposztróf). Ez esetben a paraméterek között az egyenlőségi típus helyén nem adhatunk át függvényt, vagy bármely más nem egyenlőségi típust.

A polimorfizmus több válfaját alkalmazzuk a programozásban:

Polimorf típusellenőrzés

A típus nélküli és a gyengén típusos nyelvek a programozónak nagyobb szabadságot adnak, de a tévedés lehetősége is nagyobb. Az erősen típusos nyelvek a programozót jobban korlátozzák, de biztonságosabbak. Az SML-ben polimorf típusellenőrzés van: a szigorú típusellenőrzés flexibilis, automatikus típuslevezetéssel (type derivation, type inference) társul.

Nézzük a következő definíciót!

fun id x = x

Milyen típusú itt az x? Mindegy! A id függvény ún. polimorf függvény, az x pedig politípusú azonosító. A típussémák elméletében a politípus jele α,ß, γ stb, az SML-ben ’a, ’b, ’c stb. Az SML-értelmező válasza a fenti definícióra tehát a következő:

val id = fn : ’a -> ’a

A percjellel kezdődő típusneveket (’a-t, ’b-t, ’c-t stb.) típusváltozónak nevezzük, és alfának, bétának, gammának stb. olvassuk.

Az egyenlőségvizsgálatot is megengedő ún. egyenlőségi típusok (equality types) típusváltozóinak jelölésére két percjellel kezdődő neveket használunk: ’’a, ’’b, ’’c stb.

A polimorf típus: típusséma. Amikor a típusváltozót konkrét típussal helyettesítjük, e séma egy-egy példányát kapjuk.

Nézzünk két újabb, nagyon egyszerű példát polimorf függvények definiálására! Egy pár első, ill. második tagjának kiválasztására használhatók az alábbi projekciós függvények, ahol ’a és ’b nem feltétlenül különböző típusok:

(* fst : ’a * ’b –> ’a *) fun fst(x, _) = x (* snd : ’a * ’b –> ’b *) fun snd(_, y) = y

Egyenlőségvizsgálat polimorf függvényekben

Képzeljük el azt a függvényt, amelyik megvizsgálja, hogy egy ls listában benne van-e egy bizonyos e elem. Polimorf-e ez a függvény? A lista minden eleméről el kell tudni dönteni, hogy egyenlő-e e-vel. Csakhogy az egyenlőségvizsgálatot nem minden függvényre és absztrakt típusra lehet elvégezni! Miért is nem?

Az egyenlőség tehát csak korlátozott értelemben polimorf. Egyenlőségi típusnak (equality type) nevezzük az olyan típust, amelyen az egyenlőségvizsgálat elvégezhető. Amint már említettük, az ilyen típusváltozókat az SML két percjelből (prime-ból) és egy betűből álló azonosítóval (’’a, ’’b, ’’c stb.) jelöli. Pl.:

op =; val it = fn : ’’a * ’’a -> bool

Most már definiálhatjuk az isMem (eleme) függvényt, ill. operátort:

(*isMem(x, ys) = x eleme-e ys-nek isMem : ’’a * ’’a list -> bool*) fun isMem (x, y::ys) = x = y orelse isMem (x, ys) | isMem (_, [] ) = false; infix isMem;

Polimorf halmazműveletek

A newMem függvény egy új elemet rak be egy listába, ha az elem még nins benne:

(* newMem(x, xs) = [x] és xs listaként ábrázolt uniója
newMem : ’’a * ’’a list -> ’’a list *) fun newMem (x, xs) = if x isMem xs then xs else x::xs;

newMem halmazt hoz létre (ha a sorrendtől eltekintünk). A setof függvény halmazt készít egy lsitából úgy, hogy kiszedi belőle az ismétlődő elemeket:

(* setof xs = xs elemeinek listaként ábrázolt halmaza setof : ’’a list -> ’’a list*) fun setof (x::xs) = newMem (x, setof xs) | setof [] = [];

A setof függvénynek elég rossz a hatékonysága. Szerencsésebb, ha a halmazokat a megszokott halmazműveletekkel kezeljük. Most továbbra is egyszerű listaként ábrázoljuk őket, de később valamilyen hatékonyabb tárolást választhatunk, pl. rendezett listát vagy bináris fát.

Öt halmazműveletet definiálunk:

(* union(xs,ys) = az xs és ys elemeiből álló halmazok uniója
union : ’’a list * ’’a list -> ’’a list *) fun union (x::xs, ys) = newMem (x, union(xs, ys)) | union ([], ys) = ys; (* inter(xs,ys) = az xs és ys elemeiből álló halmazok metszete inter : ’’a list * ’’a list -> ’’a list *) fun inter (x::xs, ys) = let val zs = inter(xs, ys) in if x isMem ys then x::zs else zs end |inter ([], _) = []; (* isSubset(xs,ys) = az xs elemeiből álló halmaz részhalmaza-e az ys elemeiből álló halmaznak
isSubset : ’’a list * ’’a list -> bool *) fun isSubset (x::xs, ys) = (x isMem ys) andalso isSubset(xs, ys) | isSubset ([], _) = true; infix isSubset;

A listák egyenlőségvizsgálata belső művelet az SML-ben. Halmazokra mégsem használható, mert pl. a [ 3, 4 ] és a [ 4, 3, 4 ] listák ugyan különböznek, de mint halmazok egyenlőek. Halmazként egyenlő pl. [ 3, 4 ] és [ 4, 3 ] is.

(* isSetEq(xs,ys) = az xs és ys elemeiből álló halmazok egyenlők-e
isSetEq : ’’a list * ’’a list -> bool *) fun isSetEq (xs, ys) = (xs isSubset ys) andalso (ys isSubset xs);

A hatványhalmaz egy halmaz összes részhalmazának a halmaza, az eredeti halmazt és az üres halmazt is beleértve. Jelöljük S-sel az eredeti halmazt. S hatványhalmazát úgy állíthatjuk elő, hogy S-ból kiveszünk egy x elemet, és azután rekurzív módon előállítjuk az S – {x} hatványhalmazát. Ha tetszőleges T halmazra T Í S és T E {x} Í S, így mind T, mint T E {x} eleme S hatványhalmazának. A pws függvényben a base argumentum gyűjti a hatványhalmaz elemeit; kezdetben üresnek kell lennie.

(* pws(xs, base) = az xs halmaz hatványhalmazának és a base halmaznak az uniója
pws : ’a list * ’a list -> ’a list list *) fun pws (x::xs, base) = pws (xs, base) @ pws (xs, x::base) | pws ([], base) = [base];

A pws(xs, base) @ pws(xs, x::base) kifejezésben pws(xs, base) valósítja meg az S – {x} rekurzív hívást (hiszen x::xs felel meg S-nek), azaz állítja elő az összes olyan halmazt, amelyekben x nincs benne, pws( xs, x::base) pedig ugyancsak rekurzív módon base-ben gyűjti az x elemeket, vagyis előállítja az összes olyan halmazt, amelyben x benne van. Halmazegyenlettel pws eredménye így adható meg:

pws(S, B) = {T E B| T Í S} (* powerset xs = az xs halmaz hatványhalmaza powerset : ’a list -> ’a list list *) fun powerset xs = pws(xs, []);

Kötések

Kötések segítségével úgy hivatkozhatunk egy objektumra, mint egy szimbolikus névre. Megjegyzés: a címke nem ugyanaz, mint a változó a 3 -ik generációs programozási nyelvekben. A kulcsszó amivel kötéseket hozhatunk létre a val. A kötések a környezet részévé válnak. Egy tipikus ML folyamat során kötéseket hozunk létre így gazdagítva a globális környezetet (és kifejezés kiértékelést). Ha egy olyan kifejezést adunk meg az ML értelmezőnek, amelynek nincs kötése, az automatikusan az it -hez kötődik. A nevekhez új értéket is lehet kötni, de azok a függvények amelyeknek a definíciójában felhasználtuk a névhez kötött értéket, azok továbbra is a régi értéket használják, mely az alábbi példán is látható.

Adattagoló kötések

Lehetőség van mintaillesztést is magában foglaló kötések deklarálására, amelyeket jól használhatunk összetett kifejezések tagolására. Egy lista fejelemének leválasztását például megoldhatjuk egy (egyébként hasznos) szelektor függvény segítségével:

fun fej x::xs = x ... val n = fej lista

de ugyanezt egyszerűbben megtehetjük egy adattagoló kötéssel:

val n::_ = lista

Egy másik példa:

val (_,n,_)= (3,4,5); val n = 4 : int

Adattagoló kötések használata elsősorban akkor lehet előnyös, ha egy olyan speciális tagolásra van szükség, amelyre nem akarunk külön függvényt definiálni, azonban ne felejtsük el, hogy a mintaillesztés sikertelensége futási időben egy Bind kivételt vált ki.

Kötések hatásköre, láthatósága

A változók értéke nem változik, ugyanazt a nevet viszont lehet több deklarációban használni, ilyenkor az új deklaráció eltakarja a régit. Minden deklaráció hatóköre statikus, a kiértékelési sorrendtől független.

val x = 1; fun f (x:int) = x+x; fun g (y:int) = x+y; val (x,y) = (2,3); (* x=2, y=3, f 5 értéke 10, g 6 értéke 11*)

Az ML-ben lehetőség van a változók kötéseinek hatáskörének korlátozására, azaz lokális kötések létrehozására a következő nyelvi szerkezettel:

let deklarációk in kifejezés end

Lokális kötések létrehozására több okból is szükség lehet: egy összetett kifejezés átláthatóbbá tétele érdekében, vagy ha egy kifejezésben egy többször előforduló részkifejezést, a kiértékelésének mellékhatása miatt csak egyszer szeretnénk kiértékelni, például:

let val n = read_integer() in n*n end

Vagy pl: másodfokú egyenletmegoldó:

fun gyokok (a,b,c) = let val D = Math.sqrt (b*b - 4.0*a*c) in if D >= 0 then ((-b-D)/(2.0*a),(-b+D)/(2.0*a)) else (Real.posInf, Real.posInf) end (* A “D” itt már nem érhet el *)

Természetesen lehetőség van ilyen hatáskört lokalizáló blokkok tetszőleges egymásba ágyazására. A láthatóság szabályai a struktúrált programozási nyelvekben megszokott módon alakulnak: beágyazott let blokkokban szereplő lokális kötések eltakarják az azonos változókra vonatkozó blokkon kívüli kötéseket, valamint az azonos nevű formális paramétereket. Például n értéke a következő deklarációk után 25 lesz:

val m : int = 2 val n : int = let val m : int = 3 val n : int = m*m in m*n end - m

Nem csak kifejezésekben lehet lokális kötéseket létrehozni, hanem deklarációkban is, persze ezek ritkábban használatosak. A szintaxis a következő:

local deklarációk in deklaráció end
Pl.: local val n=5 in fun ot()=n end; :ez után az ot() 5-öt ad eredményül
Vagy pl: A jól ismert faktorképzés:

local fun fact' (0,p) = p | fact' (n,p) = fact' (n-1,n*p) in fun fact n = fact' (n,1) end (* fact' itt már nincs *)

Szintaktikus cukorkák

Az ML -ben megtalálhatóak az ún. szintaktikus cukorkák, amik lehetővé teszik, hogy ínfix operátokat / függvényeket írjunk, vagy a beépített függvényeket ínfix módon használjuk, és így áttekinthetőbbé tegyük programjainkat. Például a szintaktikus cukorkák nélkül a 3 + 5 -t, add(3, 5) -nek kellene írnunk, ami sokkal kevésbé átlátható kódot eredményezne. Például elhagyhatjuk a zárójeleket, a cons (::) operátor (amelyről részletesen a listáknál olvashatunk) infixé tételével. Az infixr kulcsszó biztosítja a jobbról asszociativitást:

infixr ::; datatype 'a list = nil | :: of 'a * 'a list;

Ezzel megkaptuk a lista adattípus definícióját. Megjegyzés: az [ 1,2,3 ] jelölés egy további kiegészítés.

Operátorok és precedenciájuk

Az ML-ben nem lehet az operátorokat túlterhelni. Persze ez nyilvánvaló, hiszen ellenkező esetben nem tudná azon kifejezések típusát levezetni, amelyek az operátort tartalmazzák. Van viszont egy igen jó tulajdonsága, nevezetesen lehet új operátorokat bevezetni, melyeket nem csak ínfix, hanem akár postfix vagy prefix formában is használhatunk, és itt még nem álltak meg a nyelv készítői, ugyanis az operátoroknak meg lehet változtatni a precedenciáját is (ezért van értelme a prefix operátornak, ugyanis a függvény precedenciáját nem lehet megváltoztatni). Az ínfix operátor alapértelmezésben balra köt (bal asszociatív), de lehet jobbra kötőnek is definiálni (gondoljuk meg, ez milyen jól jön például a hatványozás operátoránál).

Saját adattípus létrehozása

Mint a legtöbb modern programozási nyelvben, az ML -ben is lehetséges saját adattípust létrehozni. Miután létrehoztuk az adattípusunkat, készíthetünk függvényeket, amelyek az új adattípust használják, és a mintaillesztést is ugyanúgy használhatjuk, mint a beépített adattípusok esetében.

Felsorolási (enumerated) típusok

Talán a legegyszerűbb példa felsorolási típusokra a C -ben vagy a Pascal -ban található.

datatype direction = north | east | south | west;

Négy konstruktor készül ezen deklaráció hatására, amiket mintaként (pattern) használhatunk függvények definiálásakor. Például készítsünk egy olyan right függvényt amely visszaadja azt az irányt amit 90 fokkal jobbra fordulva kapunk az eredetiből:

fun right north = east| right east = south | right south = west | right west = north;

Ahogyan várható volt, ezeket a függvényeket pont úgy kezelhetjük, mint bármelyik másik (akár beépített) függvényt. Például:

val aboutface = right o right; val left = ...

A mintaillesztés működik adatkonstruktorokkal:

datatype szin = makk | tok | zold | piros fun duplaz piros = true | duplaz _ = false

Paraméteres adattípusok

Alkothatunk olyan típusokat is amelyek adatokat hordoznak - ezek hasonlóak a Ada variáns rekord típusához. Minden változat (variáns) tartalmaz egy konstruktort és különböző komponenseket. Például: a pénz típus lehet kézpénz vagy csekk.

datatype money = cash of int | cheque of string * real;

A kézpénz (cash) szereplő egész szám pennie -k számát adja meg, a csekk típus egy bank nevét és a számla egyenlegét tartalmazza font -ban. Például:

val guardian = cash 45; val flat = cheque("Abbey National", 36500.00); val busfare = cash 50;

Mintaillesztést is használhatunk ezekre a típusokra, például:

fun worth(cash x) = x | worth(cheque("BCCI",_)) = 0 | worth(cheque("Baring",_)) = 0 | worth(cheque(_,amount)) = floor(100.0*amount);

A floor egy beépített függvény amivel valós számokat tudunk egésszé konvertálni.

Még egy példa a paraméteres adattípus

datatype int_real = INT of int | REAL of real val n = INT 1 fun toStr (INT i) = Int.toString i | toStr (REAL r) = Real.toString r

A paraméteres adatkonstruktor függvényként is használható, például az INT típusa függvényként int -> int_real.

Polimorf adattípus

A típuskonstruktornak is lehet paramétere, egy vagy több típusváltozó:

datatype 'a option = NONE | SOME of 'a

Ahol szükséges, ott a fordító automatikusan behelyettesíti a konkrét típust, például a SOME 1 kifejezés típusa int option.

Több típusparaméter is megadható:

datatype ('a,'b) two_opt = ZERO | ONE of 'a | TWO of 'a*'b

Rekord típus

A rekord a direkt szorzat általánosítása: a komponensekhez nevet lehet rendelni, így több adat is könnyen kezelhető
A rekord érték létrehozása:
{ nev=”Vajda Péter”, cím=”Bp.”, szul=”1982” }

Ennek a rekordnak a típusát így írhatjuk le:

Type szemely = {nev:string, cím:string, szul:int}

Szelekciós függvény: #nevm #cim
Teljes minta:

Fun nevcim {nev=n, cím=c, szul=_}

Rövidítési lehetőség a változók nevére:

Fun nevcim {nevm cím, szul} = nev ^”,” ^ cím

A nem használt mezők elhagyhatók, ha ismert a pontos típus:

Fun nevcim ({nevm cím, …}:személy) = nev ^”,” ^ cím

Ilyenkor nyilván meg kell adni a típusát!

Absztrakt adattípus

Amíg kicsik és egyszerűek a programok, struktúrájuk moduláris. Amikor nagy programokat írunk, néhány eljárást egységesítünk adattípus segítségével. ML-ben az adattípus strukturája pedig abstype ... with ... end.

Most implementálni fogjuk a halmaz absztract adattípusát.

abstype ‘a set = null | ins of ‘a * ‘a set with val emptyset = null val addset = ins fun memberset (x, null) = false | memberset (x, ins(v,s)) = x = v orelse memberset (x, s) end

Ha megengedett az egyenlőség a halmazokban, a következőképpen fogjuk implementálni.

abstype ‘a set = null | ins of ‘a * ‘a set with val emptyset = null val addset = ins fun memberset (x, null) = false | memberset (x, ins(v,s)) = x = v orelse memberset (x, s) local fun subset (null, _) = true | subset (ins(x, s1), s2) = memberset (x, s2) andalso subset (s1, s2) in fun equal (s1, s2) = subset (s1, s2) andalso subset (s2, s1) end end

Programozás abstract adattípussal

Itt implementáljuk a halmaz adattítpust, mint rendezett listát.

abstype ‘a ordered_set = Set of ((‘a * ‘a) ‘a bool) * ‘a list with fun emptyset (op <=) = Set (op <=, [ ]) fun addset (x, Set (op <=, s)) = let fun ins [ ] = [ x ] | ins (s as h::t) = if x = h then s else if x <= h then x :: s else h :: ins t in Set (op <=, ins s) end fun memberset (x, Set (_, [ ])) = false | memberset (x, Set (op <=, h::t)) = h <= x andalso (x = h orelse memberset (x, Set (op <=, t))) end