ML Estàndard

ML Estàndard

Tipus	dialect (en) , llenguatge de programació procedural, llenguatge interpretat i llenguatge de programació funcional
Data de creació	1983
Desenvolupador	Robin Milner
Paradigma de programació	programació procedimental, llenguatge imperatiu, programació modular i programació funcional
Dialecte de	ML
Influenciat per	ML
Extensió dels fitxers	sml
Etiqueta d'Stack Exchange	Etiqueta
Pàgina web	smlfamily.github.io

L'ML Estàndard, conegut per les sigles SML, de l'anglès Standard ML, és un llenguatge de programació funcional per a aplicacions de tota mena, amb comprovació de tipus en temps de compilació, i inferència de tipus.

És popular entre desenvolupadors de compiladors, i investigadors de llenguatges de programació, així com demostradors de teoremes.

SML és un descendent modern del llenguatge de programació ML emprat en el projecte de demostració de teoremes "Lògica per a funcions computables".

Es distingeix entre altres llenguatges de programació en què té una especificació formal i semàntica operacional proposades a "La Definició de Standard ML (1990)" i revisada i simplificada en l'edició de 1997.

Programa "Hola Món"

Podem descarregar l'intèrpret sml de SML de New Jersey

• cas de Linux, del paquet smlnj
• altrament el podeu descarregar d'aquí.

Instruccions per a l'intèrpret

• la grafia de l'apuntador (el text que l'intèrpret escriu per indicar que espera l'entrada) normal de l'intèrpret és '-'. Si la comanda és incompleta (ex. ens hem deixat el punt i coma final) canvia a '='
• Per carregar un fitxer sml la comanda és: use "nomfitxer" ;

$sml
- val run = print "Hola Món\n" ;

 Hola Món
 val run = () : unit

També podem obtenir els compiladors MLton i MLkit.

Característiques

Vegeu ref.

Generals

• Avaluació primerenca (Semàntica estricta). Les expressions s'avaluen i associen als símbols lligats seguint l'ordre de les declaracions.

Identificadors

Vegeu ref.

Sintaxi

Vegeu enllaç. Les instruccions, excepte la darrera, se separen amb punt i coma. Els punt i coma a fi de línia es poden estalviar.

Per especificar més d'una instrucció en una expressió (per ex. prints, o assignacions, a més de l'expressió de retorn) cal no ometre els punt-i-coma de separació.

 val nom = let
 val a = expr1 
 val b = expr2
 in
 expr3; expr4; expr_a_retornar
 end

Comentaris

 (* comentari multilínia
 *)

Tipus

Tipus bàsics

Consulteu-ne les operacions a la biblioteca SML Basis

unit (* tipus buit *)
literals: ()

bool (estructura Bool)
literals: true, false
ops: not b
a orelse b
a andalso b

int (estruct. Int), LargeInt.int (* sencers 
(consulteu Int.precision i LargeInt.precision a la vostra implementació) Vegeu secció

, atenció: el signe menys de l'oper. unària (un sol operand) es fa

amb la tilde (tecles AltGr+4 seguit d'espai),
no amb el guió, reservat per a la oper. binària *)
literals: 0, ~1, (5-4), 0x7F

word (estruct. Word), Word8.word (word8), LargeWord.word 
(* ops. de naturals amb aritmètica modular

, implementa les operacions a nivell de bit , consulteu precisions amb ([Large]Word.fromInt ~1) , opcionalment hi pot haver Word<N>.word (word<N> per abreujar) , els intercanvis entre tipus de dif. precisió es poden fer passant pel tipus LargeWord

*)
literals: 0w0, 0w1, 0wx7F
ops de conversió: Word<N>.{ toLarge | toLargeX (amb extensió de signe) | fromLarge | toInt | ... }
algunes op. binàries Word<N>.{andb | orb | xorb | << | >> | ~>> | + | - | * | div | mod | ...} (a, b) 
(* no hi ha defs infix *)
algunes op. unàries Word<N>.{~ (complement a dos) | notb (negació bit a bit) }

real (estruct Real), LargeReal.real (* reals de coma flotant 
(consulteu Real.precision i LargeReal.precision: són idèntiques en algunes implementacions *)
literals: 0.5 ~1.5
(* els reals no es consideren un tipus que implementi igualtat.
(a = b) no està definit, tampoc es pot emprar en un "case expr_real of"
cal utilitzar Real.== en posició prefix *)
Real.== (x, 2.5) (* igualtat excepte si són NaNs (no-numèrics) *) 
Real.!= (* no Real.==)
Real.?= (* igualtat bit a bit, sense tenir en compte el signe del zero *)

char (estruct. Char)
literals: #"A" (* caràcter A *)

Tipus algebraics

Tipus producte

tuples: 'a * 'b * ...

literals: (a, b) (a, b, c)
tipus de (5, 3.2) és: int * real
tipus de (5, [3.2]) és : int * real list
#1 (a, b) = a (* #1: primer elem. o camp *)
#2 (a, b) = b

registres:
tipus (exemple): {marca: string, rodes: int}

valor: val cotxe_de_l_avi = {marca = "hispano_suiza", rodes = 4}

camp: val marca_del_cotxe = #marca cotxe_de_l_avi 

enumeracions

 datatype color = Vermell | Blau | Verd

Tipus suma (unió discriminada)

 datatype arbre_sencers = Fulla of int | Branca_sencers of int * arbre_sencers * arbre_sencers ;

 val a = Fulla 3 ;
 val b = Branca_sencers (5, a, a) ;

Tipus polimòrfics

Tipus parametritzats. Cas de prefix

• un apòstrof: com ('a) indica variable de tipus
• doble apòstrof: com (''a) afegeix requeriment que la variable implementi igualtat (per a tipus eqtype)

 datatype 'a arbre = Arbre_buit | Branca of 'a * 'a arbre * 'a arbre ;

 (* cas de més d'un paràmetre, es posen en tupla *)
 datatype ('a, 'b) un_o_altre = Esquerra of 'a | Dreta of 'b ;


tipus ('a option) per a paràmetres opcionals i com a resultat de funcions definides parcialment:

 'a option (estruct. [http://sml.sourceforge.net/Basis/option.html Option])
 datatype 'a option = NONE | SOME of 'a
 ús:
 case expr of NONE => ... (* cas de no definit *)
 SOME v => f(v) (* cas definit *)

Llistes

 'a list (estruct. [http://sml.sourceforge.net/Basis/list.html List])
 datatype 'a list = nil | :: of 'a * 'a list (* nil | ''Cons'' de ('a * llista de 'a) *)

 literals: nil, [], [1,2,3]
 [] = nil ;
 [ 1, 2, 3] = 1 :: 2 :: 3 :: nil ;
 ops:
 1 :: [2, 3] = [1, 2, 3]
 [ 1, 2] @ [3, 4] = [1, 2, 3, 4] ;
 hd [1, 2, 3] = 1 ;
 tl [1, 2, 3] = [2, 3] ;

 (* ops. sobre parelles de llistes a [http://sml.sourceforge.net/Basis/list-pair.html ListPair] *)

Tipus amb allotjament lineal

string (estruct. String)
literals: "abc"
"abc" ^ "def" = "abcdef" 
String.sub("abc", 0) = #"a" (* subelement (caràcter) a la posició x *)
String.str(#"a") = "a" (* caràcter a string *)

(* ops. sobre subseqüències a l'estructura Substring *)

vectors immutables:
'a vector (estruct. Vector) (* seqüència immutable d'accés aleatori (cost O(1)) *)

(* ops. sobre subseqüències a l'estructura VectorSlice *)

vectors mudables:
'a array (estruct. Array) (* seqüència mudable d'accés aleatori (cost O(1)) *)

(* ops. sobre subseqüències a l'estructura ArraySlice *)

Sinònims de tipus

 type nom_de_tipus; (* tipus abstracte *)

 type arbre_de_tires = string arbre

clàusula eqtype t: estableix que el tipus implementa igualtat

El símbol = està sobrecarregat per les operacions d'igualtat de diversos tipus, però no tots els tipus l'implementen.

En els patrons només es poden emprar literals de tipus que implementin igualtat.

Els Reals no es considera que implementen igualtat. Tenen una operació de comparació específica amb doble signe igual (==) igualtat exceptuant NaNs (no-numèrics); (!=): negat de (==); (?=): igualtat bit a bit sense tenir en compte el signe quan és zero.

Els Arrays tenen una igualtat especial (igualtat de referències), són iguals només si són el mateix (creats en la mateixa crida).

eqtype tipus_eq (* tipus que implementa igualtat *)
ops:
(a = b) 
(* en un case, el tipus de l'expressió i dels patrons que es comparen han de ser eqtype *)
(case expr of patró1 => expr1 | patró2 => expr2 | ...) 

Per explicitar el requeriment que un tipus implementi igualtat, les operacions polimòrfiques que fan servir igualtat sobre alguns dels paràmetres, han de distingir-ne els paràmetres de tipus mitjançant el prefix de doble apòstrof.

 fun cerca (llista: ’’a list, y: ’’a) = (* doble apòstrof degut a (x=y) *)
 (case llista of nil => false
 | x::xs => (x=y) orelse cerca (xs, y)
)

Restricció de tipus

 val a : <tipus>

Expressions

Lligams

Associació d'un símbol a una expressió

 val v_a = <expressió>

 val (v_a, v_b) = <expressió_que_retorna_tupla2>

 val {camp_a = v_a, camp_b = v_b} = <expressio que retorna registre amb camp_a i camp_b>

Operadors

Vegeu ref.

Alternatives

 if <condició> then <expressió> else <expressió>

 case <expressió> of 
 <patró> => <expressió>
 | <patró> => <expressió>

Funcions

 fun incr n = n +1 ;

 (* equivalent: lligam d'un símbol amb una funció anònima *)
 val incr = fn n => n +1 ;

 (* amb recursivitat *)
 val rec fact_rf = fn (acum, 0) => acum
 | (acum, n) => fact_rf (acum * n, n-1) ;

 (* amb restricció / declaració de tipus *)
 val fact : int -> int = fn 0 => 1 
 | n => if n > 0 then fact_rf (1, n) 
 else raise Fail "arg. il·legal" ;

 (* definicions simultànies (''and'') relacionades circularment *)
 fun parell 0 = true
 | parell n = senar (n-1)
 and senar 0 = false
 | senar n = parell (n-1)

 (* retornant més d'un valor *)
 fun meitat_i_doble(x:int):int*int = (x div 2, 2*x) ;

Funcions Currificables

Vegeu currificació.

 fun suma_curri (x:int) (y:int) = x + y; (* tipus suma_curri: int -> int -> int *)
 fun suma_tupla (x:int, y:int) = x + y; (* tipus suma_tupla: int * int -> int *)

 val suma3 = suma_curri 3; (* tipus suma3 : int -> int *)
 val result = suma3 7; (* aplica suma3 a 7 *)

 (* funcions curry i uncurry permeten aplicar funcions 
 a paràmetres agrupats / desagrupats de manera diferent a la definida 
 i en el cas de curry per a poder definir funcions fixant una part dels paràmetres
 *)
 fun curry f x y = f (x, y)
 fun uncurry f (x, y) = f x y

 (curry suma_tupla) 3 4; (* aplica func de tupla a params. desagrupats *)
 val suma_amb3_currificada = (curry suma_tupla) 3 ;

 (uncurry suma_curri) (3, 4); (* aplica func de params en seqüència a una tupla *)

Composició de funcions

 fun aplica_comp f g x = (f o g) x; (* (f . g) operador estàndard lletra 'o' *)

definició d'operadors

 val << = Word.<< (* declara l'op. << per a l'ús en l'àmbit actual *)
 infix 5 << (* permet la posició infix de l'operació amb la precedència especificada.
 ''infixr'' cas d'associativitat per la dreta *)

 (* (op <<) ''op'' permet referirnos a l'operador com a funció, 
 i evitar que l'analitzador sintàctic doni error a (<<) per no haver-lo posat en posició infix *)

 (op <<): word * word -> word

declaracions d'àmbit local dins d'una expressió

 let
 val a = <expressió>
 in
 a+1
 end

declaracions d'àmbit local a nivell de declaracions

 local
 fun incr n = n+1 
 in
 val a = incr 5
 end

encaixos de patrons

'_' és el comodí

 fun llargada nil = 0
 | llargada (_::cua) = 1 + llargada cua ;

• as patterns: v com <patró>

 fun prova (v as (_::_)) = ... (* la variable v contindrà el terme encaixat *)

• encaix de registres

 fun admet_cotxe ({marca = v_marca, data_fabric = v_data_fabric}) = ...

excepcions

 (expr) handle Excepció1 => expr1
 | Excepció2 => expr2

ex.:

 exception ExcNo_hi_es of string ;

 fun cerca' (str, nil) = raise ExcNo_hi_es (str ^ " no hi és")
 | cerca' (str, cap::cua) = if str = cap then print (str ^ " trobada\n")
 else cerca' (str, cua)

 fun cerca (str: string, dades: string list) = 
 (cerca' (str, dades); true) 
 handle ExcNo_hi_es msg => (print ("ExcNo_hi_es: " ^ msg ^ "\n"); false)
 | _ => (print "altra excepció\n"; false)

Mòduls

el tipus d'una estructura: Signatura

Col·lecció d'especificacions (type, datatype, exception i tipus de variables).

signature SigConjunt =
sig
 type ''a conj (* conjunt d'elements de tipus ''a, doble apòstrof: requeriment que implementi igualtat *)
 val conjunt_buit : ''a conj
 exception ExcNo_hi_es
 val afegir_a_conjunt: ''a * ''a conj -> ''a conj
 val membre_de_conjunt : ''a * ''a set -> bool
end

herència en signatures

• especialització afegint funcions

signature SigConjunt_amb_EsBuit =
sig
 include SigConjunt
 val es_buit: ''a conj -> bool
end

• especialització per refinament de tipus

signature SigConjunt_Com_A_Llista = 
 SigConjunt where 
 type ''a conj = ''a list ;

estructures

 structure Conjunt =
 struct
 type 'a conj = 'a list ;
 val conjunt_buit = [] ;
 exception ExcNo_hi_es of string ;
 val afegir_a_conjunt (x, conj) = op :: ;
 val membre_de_conjunt = ListUtils.member ;
 end

Functors: Estructures paramètriques

• L'argument formal pot ser una signatura o una seqüència sig .. end.
• El paràmetre actual pot ser una estructura o una seq. struct .. end.

 functor ParellGeneric (Q : sig 
 type tipus_elem 
 end 
) =
 struct 
 type tip_parell = Q.tipus_elem * Q.tipus_elem 
 end ;

 structure ParellDeSencers = ParellGeneric(struct 
 type tipus_elem = int 
 end); 
 (* structure ParellDeSencers : sig type tip_parell = int * int end *)

 val s_parell : ParellDeSencers.tip_parell = (3, 4) ;

adscripció transparent (:) d'una estructura a una signatura

Els constructors de tipus queden accessibles. Es diu que la signatura queda augmentada amb els tipus concrets.

Els elements de l'estructura no descrits a la signatura quedaran d'ús intern o accés privat (no exportats).

 signature S = 
 sig
 type t
 val zero : t
 val succ : t -> t
 val anterior : t * t -> bool
 end

 structure M : S (* adscripció transparent *) =
 struct
 type t = int
 val zero = 0
 fun succ a = a +1
 fun anterior (a, b) = a < b
 fun posterior (a, b) = a > b
 end

 (* a l'intèrpret sml *)

 M.succ M.zero ;
 (* val it = 1 : M.t *)

 M.anterior (M.zero, M.succ M.zero) ;
 (* val it = true : bool *)

 M.posterior (M.zero, M.succ M.zero); (* posterior no és a la signatura, queda inaccessible (només d'accés intern) *)
 (* Error: unbound variable or constructor: posterior in path M.posterior *)

adscripció opaca (:>) d'una estructura a una signatura (tipus opacs)

Els tipus queden opacs i no se'n podran emprar els constructors. Només se'n podran manipular els elements per les operacions de la signatura.

Els elements de l'estructura no descrits a la signatura quedaran d'ús intern o accés privat.

 signature S = 
 sig
 type t
 val zero : t
 val succ : t -> t
 end

 structure M :> S (* adscripció opaca *) =
 struct
 datatype dt = A | B | C
 type t = dt
 val zero = A
 val succ = fn A => B
 | B => C
 | C => A
 end

 (* a l'intèrpret sml *)

 M.zero ;
 (* val it = - : M.t *) (* el valor no es mostra *)

 M.succ M.A; (* constructor inaccessible *)
 (* Error: unbound variable or constructor: A in path M.A *)

 M.succ M.zero; (* així sí que s'accepta l'operació *)
 (* val it = - : M.t *)

importació

val a = Conjunt.conjunt_buit

open Conjunt (* importa els símbols del mòdul Conjunt a l'àmbit actual (ja no caldrà prefixar-los) *) 
val a = conjunt_buit

Els fitxers que contenen les estructures emprades, les localitza el compilador de la manera següent:

cas d'aplic. d'un sol mòdul

el compilador les busca a la Biblioteca Basis instal·lada

cas d'aplic. multi-mòdul

cal declarar els diferents fitxers de codi en un fitxer de projecte. Vegeu secció

Aplicacions multi-mòdul

Hi ha dos sistemes diferents

• MLBasis

suportat per MLton i MLkit

• Compilation Manager

suportat per SML/NJ i fins ara per MLton que n'abandona el suport en futures versions.

Arrencada

Per ex.:

 val rec processa_args: string list -> unit = 
 fn nil => ()
 | arg::cua => let val _ = print (arg ^ "\n") 
 in processa_args cua
 end

 (* darrer lligam del fitxer *)

 val main: OS.Process.status = 
 let
 val args = CommandLine.arguments ()
 val nomprog = CommandLine.name ()
 in
 case args of
 nil => let val _ = print ("us: " ^ nomprog ^ " parametres per bla bla bla\n") 
 in OS.Process.exit OS.Process.failure
 end
 | _ => let val _ = processa_args args 
 in OS.Process.success
 end
 end

Compilació i exec.

Mlton

mlton aplic.sml
./aplic

cas d'aplicació multi-mòdul o bé si fem servir alguna biblioteca de funcionalitat addicional, cal crear un fitxer de projecte .mlb

(* hola-mon.mlb *)
$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/basis/mlton.mlb (* funcionalitat addicional basis-extra *)
hola-mon.sml 

mlton hola-mon.mlb
./hola-mon

MLKit

mlkit aplic.sml
./run

cas d'aplicació multi-mòdul, crear fitxer de projecte ".mlb"

(* projecte.mlb *)
$(SML_LIB)/basis/basis.mlb
lib.sml
principal.sml

mlkit projecte.mlb
./run

SML de New Jersey

Permet compilar a un format anomenat heap-image. Vegeu Compilation Manager.

Cal construir el programa com a biblioteca i exportar (ho fa el ml-build) una funció inicial (la típica main) amb tipus (nom_del_programa * llista_de_params_de_la_comanda retornant codi de finalització :OS.Process.status) com a l'exemple següent:

(* fitxer nj_hola.sml *)

structure Nj_hola =
struct
	val rec processa_args: string list -> unit = 
 fn [] => ()
	 | (cap::cua) => (print ("arg: " ^ cap ^ "\n") ;
 processa_args cua
) ;

	fun main (nomprog:string, args:string list): OS.Process.status =
 if List.length args = 0 then let val _ = print "falten arguments\n"
 in OS.Process.exit 1
 end
 else
 let val _ = print ("hola soc el programa " ^ nomprog ^ "\n") ;
 val _ = processa_args args ;
 in OS.Process.success 
 end
end

Fitxer de projecte segons especificació "Compilation Manager":

(* fitxer nj_hola.cm *)

Library
 structure Nj_hola
is
 $/basis.cm
 nj_hola.sml

Compilació amb ml-build, genera fitxer de tipus heap-image amb nom com a nom_sortida "." arquitectura "-" sistema_operatiu

ml-build nj_hola.cm Nj_hola.main nj_hola

ha generat nj_hola.x86-linux; execució:

sml @SMLload=nj_hola.x86-linux arg1 arg2

dona la següent sortida:

hola sóc el programa /usr/lib/smlnj/bin/sml
arg: arg1
arg: arg2

Efectes col·laterals

 val _ = ''expressió'' (* expressió d'efectes laterals descartant resultat *)

 (* per ex.: *) 
 val _ = print "abc" 
 val _ = Array.update(arr, i, x)

Programació imperativa (canvis d'estat)

• ref introdueix una referència a l'allotjament d'un altre objecte
• ! és l'operador invers que ens revela el valor de l'objecte referit per la variable
• := assigna un valor a l'objecte referit per la variable, modificant-ne l'estat

 val a = ref 5
 a := !a +1 (* assignació -- atenció: qualsevol assignació retorna ''unit'' com a valor d'expressió*)

 val result = a := !a + 1; !a (* ara retornarà el valor allotjat *)

Clàusula "while" (resultat que depèn d'un estat consultat per l'expr_booleana)

EBNF: repetició = "while", expr_booleana, "do", expressió.

Compiladors

• SMLNJ: SML de New Jersey projecte de Bell Labs, Lucent Technologies i les universitats de Princeton i Yale. Plataformes a la ref.
• MLton: coordinat per la Univ. de Chicago Plataformes: un munt
• MLkit: Compilador amb gestió de memòria basada en regions, capaç de no incrementar l'ús de memòria en les iteracions, si es segueixen les directrius proposades. Coordinat per la Univ. de Copenhaguen. No suporta múltiples fils d'execució (ang:threads). Suport incomplet dels nombres reals. Plataformes: x86

Comparació de rendiment dels compiladors de SML

Biblioteca bàsica

L'API d'elements bàsics del llenguatge s'anomena SML Basis Library i en trobareu les definicions aquí.

Les funcions i símbols predefinits, accessibles sense qualificar, són l'estructura "General", la "List" i part de la "Option" de la SML Basis Library.

Atenció: la majoria dels operadors binaris definits en estructures de l'API no inclouen la declaració infix. per tant han de precedir la parella d'operands, per ex.:

Word.<< (operand1, 0w7) (* desplaçament de bits cap a l'esquerra; en assemblador:shl *)

Curiositats

Precisió dels tipus bàsics

funcions:

val precisioSencers: int option -> string = fn prec => case prec of
					NONE => "precisió arbitrària"
					| SOME v => Int.toString v ^ " bits"

val precisioReals: int -> string = fn prec => Int.toString prec ^ " bits"

En un ord. x86 Pentium de 32 bits tenim els següents resultats

estructura del tipus	expressió	valor als compiladors
		sml (smlnj)	mlkit	mlton
Int	precisioSencers Int.precision	31 bits	31 (predeterminat), 32 (cas de --no_gc)	32 bits
LargeInt	precisioSencers LargeInt.precision	arbitrària	arbitrària	arbitrària
Real	precisioReals Real.precision	53 bits	precisió no implementada	53 bits
LargeReal	precisioReals LargeReal.precision	53 bits	precisió no implementada	53 bits
Word	Word.toString (Word.fromInt ~1)	7FFFFFFF	7FFFFFFF (predet.), FFFFFFFF (cas de -no_gc)	FFFFFFFF
LargeWord	LargeWord.toString (LargeWord.fromInt ~1)	FFFFFFFF	FFFFFFFF	FFFFFFFFFFFFFFFF

Vegeu també

• Objective Caml

Enllaços externs

• SML a SourceForge.net - web de coordinació de projectes del llenguatge SML
• Què és SML (anglès)
• Guia-presentació de SML (anglès) Presentació introductòria de bona legibilitat.
• Programming in Standard ML '97: A Tutorial Introduction (anglès) Una bona guia (en PDF).