2.17. ML

ML er et funktionsprogrammeringssprog der har stærkt typetjek med polymorfi, højereordensfunktioner, funktionsdefinition ved mønstergenkendelse, håndterbare undtagelser (eng. exceptions), strikt evaluering og et avanceret modulsystem. Det betyder at rigtig mange programmeringsfejl bliver opdaget allerede når man oversætter et program, ikke først når man kører det. ML blev oprindelig (ca. 1974) udviklet som metasprog (meta-language) til logiske bevissystemer, men sproget viste sig at være særdeles velegnet til en lang række andre formål.

I dag (2001) findes der to væsentlige varianter af sproget ML: Standard ML (SML) og Objective Caml (OCaml). Der findes ganske omfattende biblioteker af nyttige funktioner til såvel Standard ML (se SML Basis Library) som OCaml. Desuden har de enkelte implementationer deres egne udvidelser til f.eks. databaseadgang, generering af HTML-kode, PNG-billeder, osv.

ML er især udbredt på universiteter og forskningsinstitutioner, og benyttes i mindre grad i industriel sammenhæng. I Danmark undervises der i Standard ML ved blandt andet Danmarks Tekniske Universitet, Københavns Universitet (DIKU), Aarhus Universitet, Aalborg Universitet og IT-højskolen i København.

2.17.1. Brug af ML

Der findes flere implementationer af SML. Både SML of New Jersey og MoscowML giver mulighed for at lege med SML ved en 'læs-beregn-udskriv løkke' hvor man interagerer direkte med fortolkeren. Man skriver sine skriver sine udtryk ind, fortolkerne beregner dem og skriver svaret ud. En session med SML kunne derfor se således ud:


Standard ML of New Jersey v110.42 [FLINT v1.5], October 16, 2002
- val prim = [18,43,23,10,88];
val prim = [18,43,23,10,88] : int list
- fun sum []      = 0
=   | sum (x::xs) = x + sum xs;
val sum = fn : int list -> int
- val res = sum prim;
val res = 182 : int
- 

2.17.2. Eksempel på SML

Det følgende eksempel forsøger vise en række af de ting der er specielle for SML og andre funktionsorienterede sprog. SML udleder selv typer for funktioner, og de udledte typer er her indsat over funktionsdefinitionerne i kommentarer (* ... *).

Først defineres en funktion map:


(* Type: ('a -> 'b) -> 'a list -> 'b list *)
fun map f nil = nil
  | map f (x::xs) = f(x) :: map f xs;

Typen fortæller at funktionen map som argumenter tager en anden funktion der tager et argument af typen 'a og returnerer en værdi af typen 'b. Det andet argument til map er en liste hvor elementerne har typen 'a og så returnerer map en liste af elementer af typen 'b. Men hvad er 'a og 'b?

'a er en typevariabel. Hvis man kalder map med en funktion der tager et heltal som argument vil 'a blive bundet til typen int. Dette kaldes typepolymorfi. map arbejder bare på lister og er ligeglad med hvad funktionen f gør ved elementerne.

Funktionen er defineret med mønstergenkendelse. Det vil sige at der er listet en række tilfælde af definitionen op hvor SML så vil vælge den første der passer. nil og (x::xs) er mønstre som SML sammenligner med hvad funktionen bliver kaldt med. nil er den tomme liste og (x::xs) er en liste hvor det første element bliver bundet til variablen x og resten af listen bliver bundet til variablen xs.

:: er en infix-operator der laver listesammensætning. map tager altså en funktion og en liste og udføre funktionen på alle elementerne i listen. Da map tager en anden funktion som argument kaldes den en højereordensfunktion.

Følgende enkle funktion tager et heltal og ganger det med 2:


(* Type: int -> int *)
fun double n = 2 * n;

Ikke noget specielt her.

Nu vil vi så anvende ovenstående to funktioner til at lave en funktion der tager en liste af heltal og fordobler dem:


(* Type: int list -> int list *)
val doublelist = map double;

Bemærk at vi her bruger val og ikke fun. Det er fordi vi egentligt ikke laver en ny funktion men tildeler navnet doublelist en værdi (funktioner er nemlig lige så meget værdier som heltal er).

Det næste man bemærker er at map kaldes med kun et argument. Men map havde da to argumenter? Dette kaldes 'currying'. Vi kalder map med det første argument, det returnerer en funktion der tager resten af argumenterne.

Vi kunne også have undladt at definere funktionen double og bruge en anonym funktion:


(* Type: int list -> int list *)
val doublelist = map (fn x => 2 * x);

Den slags anonyme funktioner bruges ganske ofte i SML.

2.17.3. Iteration i SML

SML indeholder ikke de løkkestrukturer man normalt bruger. Skal man beregne noget iterativt bliver man derfor nødt til selv at lave nogle funktioner der klarer det for sig. Man kunne for eksempel bruge følgende funktion:


(* Type: ('a -> 'a) -> int -> 'a -> 'a *)
fun iterate f 0 x = x
  | iterate f i x = iterate f (i-1) (f x);

iterate tager en funktion f og udfører den et antal gange på værdien x.