Standard ML

Standard ML (SML) er et funktionsorienteret programmeringssprog som understøtter moduler, statisk typetjek og typeinferens. Sproget er populært til udvikling af compilere, forskning omkring programmeringssprog og udvikling af systemer til automatisk bevisførelse.

SML er en moderne dialekt af ML som blev brugt i bevisførelsesystemet LCF. Sproget udmærker sig blandt programmeringssprog med en formel specifikation som indeholder en operationel semantik (The Definition of Standard ML fra 1990, revideret i 1997), hvilket betyder at alle operationer i sproget har en formelt defineret betydning.

Sproget

Et Standard ML-program består af en række erklæringer som indeholder udtryk som enten er funktioner, værdier eller sammensatte udtryk som kan reduceres. Standard ML er et funktionsorienteret programmeringssprog med nogle imperative træk. Den primære abstraktion som benyttes er altså funktioner. For eksempel kan fakultetsfunktionen beskrives rekursivt således:

fun fakultet n =
    if n = 0 then 1 else n * fakultet (n-1)

En Standard ML-compiler kan således udlede at fakultet må være en funktion som tager et heltal som argument og returnerer et heltal (typen int → int), helt uden at disse typer angives eksplicit. Typeinferensen foregår ved hjælp af Hindley-Milner-algoritmen og gør at programmer i praksis kan udtrykkes kortere.

Samme funktion kan udtrykkes ved hjælp af mønstergenkendelse som vist i følgende eksempel:

fun fakultet 0 = 1
  | fakultet n = n * fakultet (n-1)

Mønstergenkendelsen fungerer således at man ikke betragter funktionsargumentet som navnet på én parameter, men et generelt mønster som skal passe med inputværdien. Mønstre prøves fra det øverste mønster og ned, så rækkefølgen har en betydning. Hvis mønstre har variable komponenter (for eksempel n), bliver disse bundet så man kan henvise til dem i den funktionskrop som hører til mønsteret (adskilt med tegnet =).

Typer

De primitive indbyggede typer i Standard ML er: int, real, char, string, bool. Hertil findes en række prædefinerede algebraiske typer og nogle indbyggede, sammensatte typer: tupler og lister. Tupler kan indeholde en fast mængde af værdier med forskellige typer, mens lister kan indeholde vilkårligt mange værdier af én type. For eksempel:

val land = ("Danmark", 5564219, "Der er et yndigt land...")
val sorteret = [1,1,2,3,5,8,13,21,34,55,89]

Foruden en række indbyggede typer, kan man lave synonymer (også kaldet aliaser) til eksisterende typer. For eksempel kan man definere et koordinat som to kommatal, eller en omkreds som et kommatal. Tegnet * i typerne nedenfor er udtryk for den indbyggede sammensatte tupel-type:

type koordinat = real * real
type omkreds = real

Efterfølgende kan man angive typen koordinat i stedet for real * real. Her er ikke tale om en konvertering af værdier.

Foruden synonymer til eksisterende typer er det også muligt at lave nye algebraiske typer. Det er nyttigt til at modellere en række ting. For eksempel kan man beskrive geometriske former i planet:

datatype form = Cirkel of koordinat * omkreds
              | Rektangel of koordinat * koordinat
              | Trekant of koordinat * koordinat * koordinat

Eller binære træer:

datatype tree = Leaf
              | Node of trae * int * trae

Eller køretøjer:

type hjul = int
type gear = int
type tophastighed = int
type hestekraefter = int
datatype koretoj = Bil of tophastighed * hestekraefter
                 | Tank of tophastighed * hestekraefter
                 | Cykel of hjul * gear

Det er efterfølgende muligt at konstruere funktioner som behandler disse typer ved hjælp af mønstergenkendelse:

fun antal_elementer Leaf = 0
  | antal_elementer (Node (venstre, n, hojre)) =
    1 + antal_elementer(venstre) + antal_elementer(hojre)

Det er værd at bemærke at algebraiske datatyper kan være rekursivt definerede, og funktioner som arbejder på disse er derfor ofte også rekursive. Det er også interessant at bemærke hvordan mønstergenkendelse og typeinferens fungerer: Alle tomme træer bliver grebet af første mønster mens ikke-tomme træer bliver matchet således at deres obligatoriske tre parametre (et venstre-træ, en værdi og et højre-træ) får navne som kan bruges i funktionskroppen.

 fun miljovenlig (Cykel _) = true
   | miljovenlig (_) = false

Man kan også udelade dele af en struktur ved at give dem det særlige variabelnavn _.

Højereordensfunktioner

Funktioner i Standard ML har såkaldt førsteklassestatus, hvilket vil sige at alle funktioner kan betragtes som værdier på lige fod med almindelige værdier som sandhedsværdier, tal, lister og tekst. En konsekvens ved dette er at funktioner kan tage andre funktioner som argument. Det er også muligt at erklære en funktion som ikke har et navn, men blot er en værdi (en såkaldt closure, lambda-udtryk eller anonym funktion).

Følgende er et eksempel som definerer plus som en funktion der tager en 2-tuple som input og returnerer summen af dens første- og andenkomponent:

val plus = (fn (x,y) => x+y)

En funktion kaldes "af højere orden" hvis den tager imod funktioner som argument eller returnerer funktioner som værdi. En strengere definition kræver at begge er tilfældet. Følgende er et eksempel på en funktion, K, som tager et argument x som input og returnerer en funktion, som tager et argument y som input, smider y væk og returnerer x; funktionen er skrevet på tre måder som alle er ækvivalente og gyldige:

fun K x y = x
fun K x = (fn y => x)
val K = (fn x => (fn y => x))

Følgende funktion, fikspunkt, tager imod en funktion f og en startværdi x og begynder at regne f(x), f(f(x)), f(f(f(x))) osv. indtil den finder et punkt hvor det ikke gør nogen forskel om man tilføjer en ekstra anvendelse af funktionen:

fun fikspunkt (f, x) =
    if f x = f (f x)
    then x
    else fikspunkt (f, f x)

Man kan sige at K og fikspunkt er højereordensfunktioner.

Undtagelser

Standard ML understøtter undtagelser ved brugen af to nøgleord: raise og handle. Man kan desuden definere sine egne undtagelser ved exception, der har en syntaks meget lignende den for abstrakte datatyper. Der findes en række indbyggede undtagelser: Empty, Div, Fail, Domain m.fl.

fun max [] = raise Empty
  | max [x] = x
  | max (x::y::xs) =
    if x > y
    then max (x::xs)
    else max (y::xs)

Moduler

Afsnit mangler.

Implementeringer

• MLTon er en optimerende compiler til hele programmer. Den producerer meget effektiv kode sammenlignet med andre Standard ML-compilere.
• Standard ML of New Jersey (forkortet SML/NJ) er en compiler med tilhørende værktøjer, biblioteker og interaktiv fortolker.
• Poly/ML er en compiler som producerer effektiv kode og understøtter hardware med flere kerner (igennem POSIX-tråde).
• Moscow ML er en compiler baseret på CAML Light-runtime-miljøet og understøtter moduler såvel som en stor del af SML Basis-biblioteket.
• HaMLet^[1] er en SML-fortolker som forsøger at være en tilgængelig og præcis referenceimplementation.
• ML Kit^[2] tilføjer en spildopsamler og regionsbaseret hukommelseshåndtering, sigtet mod realtidsapplikationer.
• SML.NET^[3] oversætter til Microsofts Common Language Runtime (CLR) og har udvidelser som muliggør linkning til andre .NET-kode.
• SML2c er en batch-compiler og oversætter kun erklæringer på modulniveau (dvs. signaturer, strukturer og funktorer) til C. Den er baseret på SML/NJ 0.67, men understøtter ikke SML/NJ's debugging og profiling. Programmer som kun består af moduler, og som virker i SML/NJ, kan oversættes med sml2c uden ændringer.
• Poplog-systemet implementerer en version af Standard ML samtidigt med Common Lisp og Prolog og tillader sammenblandingen af disse sprog.
• SML#^[4] er en konservativ udvidelse til Standard ML som tilføjer polymorfi på record-typer og evnen til at arbejde sammen med C-kode.
• Alice: en fortolker til Standard ML som tilføjer doven evaluering, samtidighed (trådprogrammering og distribuerede beregninger via RPC) og constraintprogrammering.

Disse systemer er alle open source og frit tilgængelige. De fleste er implementeret i Standard ML. Der findes ikke længere kommercielle Standard ML-implementeringer, men et firma kaldet Harlequin producerede engang en kommerciel IDE og compiler til Standard ML under navnet MLWorks. Firmaet eksisterer ikke længere.

Se også

• Funktionsprogrammering
• Rekursion
• Haskell (programmeringssprog)
• OCaml (programmeringssprog)

Noter

Eksterne henvisninger

• StandardML.dk Arkiveret 3. april 2013 hos Wayback Machine  (Webside ikke længere tilgængelig)