ML Estàndard

De Viquipèdia
Dreceres ràpides: navegació, cerca

L' Standard ML o SML o ML Estàndard é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 que 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"[modifica | modifica el codi]

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

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

Instruccions per a l'intèrpret[2]

  • la grafia del digui? (ang:prompt) 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" ;
- val run = print "Hola Món\n" ;

Hola Món
val run = () : unit

També podem obtenir els compiladors MLton[3] i MLkit.[4]

Característiques[modifica | modifica el codi]

Vegeu ref.[5]

Generals[modifica | modifica el codi]

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

Identificadors[modifica | modifica el codi]

Vegeu ref.[6]

Sintaxi[modifica | modifica el codi]

Vegeu enllaç.[7] 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[modifica | modifica el codi]

(* comentari multilínia
 *)

Tipus[modifica | modifica el codi]

Tipus bàsics[modifica | modifica el codi]

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 
     (* paraula de màquina, ops. de naturals o sense signe
                                       , implementa les operacions a nivell de bit 
        , consulteu precisions amb ([Large]Word.fromInt ~1)
        , opcionalment hi pot haver Word<N>.word (word<N> per abreviar)
        , els intercanvis entre tipus de dif. llargada 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[modifica | modifica el codi]

Tipus producte[modifica | modifica el codi]
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[modifica | modifica el codi]
datatype color = Vermell | Blau | Verd
Tipus suma (unió discriminada)[modifica | modifica el codi]
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[modifica | modifica el codi]
 (* parametritzats
    'a  : les variables de tipus es prefixen amb l'apòstrof
    ''a : doble apòstrof implica requeriment que el tipus de la variable implementi igualtat
  *)
 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 resultats ''opcionals'' 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[modifica | modifica el codi]

'a list (estruct. 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 ListPair *)

Tipus amb allotjament lineal[modifica | modifica el codi]

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 amb temps d'accés constant *)

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

vectors mudables:
'a array ( estruct. Array) (* seqüència mudable amb temps d'accés constant *)

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

Sinònims de tipus[modifica | modifica el codi]

type nom_de_tipus ;  (* tipus abstracte *)
 
type arbre_de_tires = string arbre

Tipus que implementa igualtat[modifica | modifica el codi]

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

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); (!=): no == ; (?=): igualtat bit a bit sense tenir en compte el signe quan és zero.

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

eqtype tipus_eq      (* tipus que implementa igualtat *)[9]
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.[10]

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[modifica | modifica el codi]

val a : tipus

Expressions[modifica | modifica el codi]

Lligams[modifica | modifica el codi]

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[modifica | modifica el codi]

Vegeu ref.[11]

Alternatives[modifica | modifica el codi]

if condició then expressió else expressió

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

Funcions[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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

definició d'operadors[modifica | modifica el codi]

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ó[modifica | modifica el codi]

let
    val a = expressió
in
    a+1
end

declaracions d'àmbit local a nivell de declaracions[modifica | modifica el codi]

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

encaixos de patrons[modifica | modifica el codi]

_ é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[modifica | modifica el codi]

(expr) handle Exc1 => expr1
            | Exc2 => 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[modifica | modifica el codi]

el tipus d'una estructura: Signatura[modifica | modifica el codi]

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

signature SigConjunt =
sig
  type ''a conj   (* conjunt d'elements de tipus ''a *)
  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[modifica | modifica el codi]
  • 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[modifica | modifica el codi]

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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

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 =
 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 *)
(* Error: unbound variable or constructor: posterior in path M.posterior *)

tipus opacs: adscripció opaca (:>) d'una estructura a una signatura[modifica | modifica el codi]

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 =
 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ó[modifica | modifica el codi]

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[modifica | modifica el codi]

Hi ha dos sistemes diferents

suportat per MLton i MLkit

  • Compilation Manager[13]

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

Arrencada[modifica | modifica el codi]

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.[modifica | modifica el codi]

Mlton[modifica | modifica el codi]
mlton aplic.sml
./aplic

cas d'aplic. multifitxer o ús de biblioteca de funcionalitat addicional,[16] cal crear .mlb[17]

(* 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[modifica | modifica el codi]
mlkit aplic.sml
./run

cas d'applic. multifitxer, crear fitxer ".mlb" [18]

(* projecte.mlb *)
$(SML_LIB)/basis/basis.mlb
lib.sml
principal.sml
mlkit projecte.mlb
./run
SML de New Jersey[modifica | modifica el codi]

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

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 
(* fi de fitxer *)
(* fitxer nj_hola.cm *)

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

(* fi de fitxer *)

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

dóna la següent sortida:

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

Efectes laterals[modifica | modifica el codi]

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

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

Programació imperativa (canvis d'estat)[modifica | modifica el codi]

  • 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)

val repeticio = while expr_booleana do expressió

Compiladors[modifica | modifica el codi]

  • SMLNJ: SML de New Jersey[1] projecte de Bell Labs, Lucent Technologies i les universitats de Princeton i Yale.[20] Plataformes: llista[21]
  • MLton: [3] coordinat per la Univ. de Chicago [1] Plataformes: un munt[22]
  • MLkit: [4] 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.[23] Plataformes: x86

Comparació de rendiment dels compiladors de SML[24]

Biblioteca bàsica[modifica | modifica el codi]

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

Les funcions i símbols predefinits,[26] accessibles sense qualificar, són l'estructura "General",[27] la "List" i part de la "Option"[28] 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[modifica | modifica el codi]

Precisió dels tipus bàsics[modifica | modifica el codi]

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

Referències[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

Guies d'aprenentatge[modifica | modifica el codi]