Az ML programozási nyelv

Vezérlési szerkezetek

Az ML egy funkcionális programozási nyelv, így nem az imperatív programozási nyelvekben megszokott vezérlési szerkezeteket találjuk meg benne. A könnyebb megértés kedvéért azonban párhuzamot húzhatunk a funkcionális programozási nyelvekben megtalálható és az imperatív programozási nyelvekben meglévő vezérlési szerkezetek között. A szekvenciával a függvény kompozíció állítható párhuzamba, az elágazással a mintaillesztés, és a ciklussal pedig a rekurzió.

Függvény kompozíció

A függvénykompozíció operátora az "o". Segítségével függvényekből függvényeket gyárthatunk. Az egyik függvény kimenete lesz a következő függvény bemenete. Például:

val first = hd o explode; val second = hd o tl o explode;

Ezek a függvények egy karaktert vesznek el egy stringből. Egy függvénykompozíciós láncban mindig a legutolsó függvény kerül legelőször végrehajtásra.

Elágazás

Standard ML elágazás lehetőséget ad arra, hogy a függvényt alábbi példa szerint definiáljuk: a következő day eljárás leképezi az egész értékű számokat szöveges napokra.

val day = fn 0 => "Monday" | 1 => "Tuesday" | 2 => "Wednesday" | 3 => "Thursday" | 4 => "Friday" | 5 => "Saturday" | _ => "Sunday"

A _ esetén az eljárás leképez minden más értéket, amely nem szerepel a fenti listán, Sunday értékre.

Mintaillsztés

Az eddigi példákban olyan függvények szerepeltek amelyek egyetlen egyenlettel voltak definiálva. Ha olyan függvényre van szükségünk amely különbözőképpen viselkedik különböző bemenetekre használhatunk "if then else" struktúrát vagy "case" kifejezést. Ugyan használhatjuk az "if then else" -t, de a mintaillesztés (pattern matching) ajánlott. Például: ha egy angol szó jelenideju alakját akarjuk átalakítani a múltideju alakjára általában egy "ed" -et rakunk a végére. A "past" függvény ezt csinálja.

past "clean" = "cleaned"
past "polish" = "polished"

Azonban vannak rendhagyó igék amik speciális eseteket jelentenek, például: run -> ran

fun past "run" = "ran" | past "swim" = "swam" | past x = x ^ "ed";

Amikor a függvényhívás kiértékelődik, a rendszer megpróbálja illeszteni a bemenetet (az aktuális paramétert) minden egyes egyenlettel a kifejezésben. Tehát a past "swim" illesztődik a második esetre. Az utolsó esetben az "x" szabad változóra illeszkedik minden olyan string, amely nem illeszkedett az előzőek valamelyikére. Pl.: a past "strench" kiértékelésénél az ML nem tudja illeszteni a bemenetet egyik esetre sem az első kettő közül, így az utolsó eset kerül végrehajtásra, így az eredmény "strench"^"ed" azaz "stenched" lesz.

Nem teljesség

Amikor egy olyan függvényt adunk meg az ML -nek, mint például a

fun last [h] = h | last(h::t) = last t;

egy figyelmeztetést (warning) kapunk:

std_in:217.1-218.23 Warning: match non exhaustive
h :: nil => ...
h :: t => ...

A függvény azért működik, azonban az ML figyelmeztet minket, hogy nincs minden esetre definiálva a függvény (a fenti esetben a nil -re nincs definiálva). A "last nil" kifejezés jól formált (megfelel a típusokra vonatkozó szabályoknak), de a függvény nincs rá definiálva. Ez egy nem teljes vagy parciális függvény ellentétben azokkal a teljes vagy totális függvényekkel amiket eddig láttunk. Bizonyos esetekben egy parciális függvény nagyon hasznos lehet, és nincs értelme a függvényt teljessé tenni (mint a last függvény esetében). Azonban, ha sikerül figyelmeztetések (warning -ok) nélkül lefordítanunk egy programot, az (majdnem) garantálja, hogy futásidejű hibát nem fogunk kapni.

Minták átfedése

Mivel a [h] minta azonos a h::nil mintával, újraírhatjuk a last függvényt a következőképpen:

fun last(h::nil) = h | last(h::t) = last t;

A bal oldalon szereplő mintákat megvizsgálva láthatjuk, hogy átfedés van a két ág között. Az 5::nil kifejezés mindkettő mintára illeszkedik (h -hoz az 5 -öt, t -hez a nil -t rendelve). Nyilvánvaló, hogy az első eset az, amit akarunk, és csakugyan az ML mindig abban a sorrendben próbálja meg illeszteni a mintákat, amilyen sorrendben felsoroltuk őket.

Megjegyzés: nem ez az első példa ahol a minták át vannak fedve.

Feltételek

Ahol lehetséges mintaillesztést használunk, hogy a különböző esetekkel "elbánjunk", azonban ez néhány esetben nem lehetséges. Visszatérünk ahhoz a példánkhoz, amikor angol szavak jelen idejű alakjához a múlt idejű alakot rendeltük. A szavak végére általában egy "ed" -et kell ragasztanunk, azonban, ha a szó "e" -re végződik, akkor csak egy "d" -t (persze a rendhagyó igéktől most eltekintünk). Megvizsgálhatjuk a bemenet utolsó karakterét az explode függvényt alkalmazva, aztán a rev függvényt, aztán a hd -t. A past függvény továbbfejlesztett változata:

past "turn" = "turned"
past "insert" = "inserted"
past "change" = "changed"

A speciális eseteket ugyanúgy kezeljük mint eddig.

fun past "run" = "ran" | past "swim" = "swam" | past x = if hd(rev(explode x))="e" then x^"d" else x^"ed";

Rekurzió

Rekurzív függvényeket használva olyan eredményeket érhetünk el, amik ciklusokat igényelnének egy tradícionális programozási nyelvben. Azonban a rekurzív függvények sokkal rövidebbek és átláthatóbbak. Az olyan függvényeket nevezzük rekurzív függvényeknek, amik önmagukat hívják direk vagy indirekt módon.
A következő példákban pontosan két mintát használunk a függvények definiálásához. Az első az alapesetet kezeli, ami tipikusan 0 vagy 1, a második illeszkedik minden más mintára (számra). Egy tipikus rekurzív függvény a fun(0) = ?? egyenletet használja arra az esetre, mikor a bemenet 0, és az | f(n) = ?? egyenletet, amikor n 1, 2, 3... Hagyományos itt is a faktoriális függvény lesz az első bemutatott rekurzív függvény:

n n!
0 1
1 1*0! = 1*1 = 1
2 2*1! = 2*1 = 2
3 3*2! = 3*2 = 6
4 4*3! = 4*6 = 24
5 5*4! = 5*24 = 120
6 6*5! = 6*120 = 720
7 7*6! = 7*720 = 5040
...
12 12*11*10*..2*1 = 479001600

Egy matematikus így definiálhatná a faktoriális függvényt:
0! = 1
n! = n.(n-1)! ha n>0

A prefix "factorial" kulcsszót használva a postfix "!" helyett, és * -al jelölve a szorzást, a faktoriális számítás az ML -ben:

fun factorial 0 = 1 | factorial n = n * factorial(n-1);

Ez megegyezik a matematikai definícióval és implementáció gyanánt is szolgál. Hogy megvizsgáljuk hogyan működik ez, nézzük a factorial 3 végrehajtását. Mivel a 3 -at nem lehet a 0 -ra illeszteni, a második egyenletet használja a rendszer, és a 3 az n -hez kötődik, aminek az eredménye:

factorial 3 = 3 * factorial(3-1) = 3*factorial(2)

Ez a factorial függvény újabb meghívását eredményezi, még mielőtt a szorzás megtörténne. Amikor a factorial 2 értékeli ki rendszer, ismét a második egyenlet használja, de most n -hez a 2 -t köti:

factorial 2 = 2 * factorial(2-1) = 2*factorial(1)

Ehhez hasonlóan ez a következő hívást generálja:

factorial 1 = 1 * factorial 0

A factorial 0 kifejezés viszont már az első egyenlettel kerül meghatározásra, és így az 1 eredményt adja vissza. Most visszafejthetjük a rekurziót:

factorial 0 = 1 factorial 1 = 1 * factorial 0 = 1*1 = 1 factorial 2 = 2 * factorial 1 = 2*1 = 2 factorial 3 = 3 * factorial 2 = 3*2 = 6

Még egy alapvető példa: Fibonacci számok előállítása

(* for n>=0, fib n az n. Fibonacci szám *) fun fib 0 = 1 | fib 1 = 1 | fib (n:int) = fib (n-1) + fib (n-2)

Ezzel viszont van egy kis baj:
20-30 felett már eléggé időigényes kivárni a kiértékelést:

Hiszen ez egy exponenciális algoritmus!

Mégis hogy lehet orvosolni az ilyen típusú függvények hibáit, ha nincs ciklusunk és váltózóink?

Erre egy egyszerű példa:

(* for n>=0, fib' n kiszámolja a (a, b), ahol a az n. Fibonacci szám, és b az (n-1)-dik *) fun fib' 0 = (1, 0) | fib' 1 = (1, 1) | fib' (n:int) = let val (a:int, b:int) = fib' (n-1) in (a+b, a) end

Nyilván ez már sima lineáris rekurzív algoritmus!

Megjegyzés: egy rekurzív függvény minden végrehajtása helyet foglal a veremből, így a memória-felhasználás szempontjából egy rekurzív program kevésbé hatékony, mint a neki megfelelő ciklust használó program.

Figyelmeztetés: Nagyon könnyű nem-befejeződő rekurzív programokat írni. Például, ha megpróbáljuk a factorial ~1 -et végrehajtani (ahol a ~ jel az unáris minusznak felel meg). Egy nem-termináló program megszakításához nyomjuk meg a Control-C gombokat. Figyeljünk ezekre a nem-termináló programokra, mert néhány ilyen program félelmetes ütemben fogyasztja a rendszer erőforrásait (processzoridő, memória, stb). Ne hajtsuk végre a következő (rossz) programot:

fun bad x = (bad x)^(bad x);

If .. then .. else ..

Néha a mintaillesztés nem megfelelő. Például ha értékeket akarunk összehasonlítani, az "if .. then .. else" struktúra hasznos. Az "if B then S1 else S2" kifejezés leteszteli a B logikai kifejezést, és ennek eredményétől függően ad vissza S1 -et vagy S2 -t. Például:

if 1 = 0 then "Én vagyok a Mikulás." else "Valaki más a Mikulás.";

A következő függvény egy s stringről állít nekünk valamit. Egy szó (string) palindrom, ha a szó ugyanaz elölről és hátulról olvasva.

fun pali s = if explode s = rev(explode s) then s ^ " is a palindrome." else s ^ " is not a palindrome.";

Továbbmenve: a kifejezés mindkét esetben ugyanaz, kivéve, hogy a "not" szócska az egyik esetben nem szerepel, így azt is tehetjük, hogy:

fun pal2 s = s^" is "^(if explode s = rev(explode s) then "" else "not ") ^"a palindrome.";

Megjegyzés: Néhány programozási nyelvben az "else" ág opcionális. Ennek nem lenne értelme az ML -ben, mert egy kifejezésnek mindenképpen vissza kell adnia értéket.

Származtatott alak

Standard ML-ben alkalmazhatjuk a mintaillesztést, mint egy primitiv operátort. A bemenetet (az aktuális paramétert) minden egyes egyenletre lehet illeszteni.

A származtatott alak segítségével a függvény deklaráció egyszerűbb, rövidebb lehet.
De nem ez adja a nyelv erősségét, csak a definiálandó függvények olvashatóságát teszi kellemesebbé.
A szintaktikus konstruktorokat melyeket azért építettek a Standard ML nyelvbe, hogy egyszerűbben írhassuk meg a programokat, származtatott alaknak nevezzük.

A származtatott alak "fun" kulcsszóval jelöli a függvényt. A kulcsszó után jön az azonosító és a mintaillesztés.
Például az egész számokon értelmezett következő függvény:

fun succ x = x + 1.

A sum függvény pedig:

fun sum 1 = 1 | sum n = sum (n-1) + n

Akkor van szükségünk a származtatott alakra, amikor a curry függvénynek több argumentuma van.
A curry, uncurry és kompozíció függvény definiálása sokkal kompaktabb, ha a következőképpen írjuk le:

fun curry f x y = f (x, y) fun uncurry f (x, y) = f x y fun compose (f, g) x = f (g x)

Egy másik jelölés is van definiálva a függvények használatának a feltételeire. Egy nyilvánvaló példa a case...of alakra a reduce függvény implementálásában:
A reduce függvény:

reduce (g, e, m, n, f) = g(e, g(f(m), g(f(m+1),...g(f(n(1), g(f(n)))

Standard ML származtatott alakban:

fun reduce (g, e, m, n, f) = case m > n of true => e | false => g (reduce(g, e, m, n-1, f), f n)

Szekvencia

Az ML programokban pontosvesszővel elválasztott utasítások és definíciók vannak, melyek mindegyike rendelkezik visszatérési értékkel. A függvénydefiníciókban az utasítások helyett írhatunk zárójelbe tett pontosvesszővel elválasztott utasításokat. Ez balról jobbra fog kiértékelődni a visszatérési értéke pedig az utolsó utasításé lesz. Egy példa.:

fun nhello 0 s = print "." |nhello i s = (print s;nhello (i-1) s);

Azonban meg lehet tenni hogy a szekvencia első utasításé legyen a visszatérő érték.
Ezt a before kulcsszóval érhetjük el:
pl: (ut1 before ut2)
Ekkor ut1 visszatérési értéke az eredmény!