# SML/NJ Lecture slide: [click here](https://www.kdocs.cn/p/107488041032) Pattern matching, type inference, data types, pattern matching, continuations.\ Readings: Ullman, ch 1-4, 5 (optional) [Syntax in SML](http://rigaux.org/language-study/syntax-across-languages-per-language/SML.html): SML syntax fast loop-up book\ [SML Help](https://smlhelp.github.io/book/index.html): SML tutorial written by TAs at CMU. ### Overview * Functional: functions as first-class values * Garbage collected * Strict evaluation (applicative order) * No coercion * Strong and static typing * parametric polymorphism * structural equivalence * all with type inference * Advanced module system * Exceptions * Miscellaneous features * datatypes (merge of enumerated literals and variant records) * pattern matching * `ref` type constructor (like const pointers) ```smlnj (* Comments *)val k = 5; List operations ``` ```smlnj 1::[2,3]; => val it = [1, 2, 3] : int list (* whether empty or not *) null [1, 2]; => val it = false : bool hd [1, 2, 3]; => val it = 1 : int tl [1, 2, 3]; => val it = [2,3] : int list (* concatenation of lists *) [1, 2, 3] @ [2, 3, 4]; => val it = [1,2,3,2,3,4] : int list ``` ### Functions ```sml (* named *) fun abs x = if x >= 0.0 then x else ~x; (* anonymous *) fn x => if x >= 0.0 then x else ~x; (* pattern-matching style *) fun length [] = 0 | length (x::xs) = 1 + length xs; (* multiple arguments *) fun add (a, b) = a + b; (* pass a tuple *) fun add a b = a + b; (* currying *) ``` Type notation `α → β → δ` means `α → (β → δ)` ### `let` local scope ```sml fun findroot (a, x, acc) = let val nextx = (a / x + x) / 2.0 in if abs (x - nextx) < acc * x then nextx else findroot (a, nextx, acc) end ``` ### Records Type declaration ```sml type vec = {x: real, y: real}; ``` Variable declaration ```sml val v = {x=2.3, y=4.1}; ``` Field selection: `#x v` Pattern matching in a function: ```sml fun dist {x, y} = sqrt (pow (x, 2.0) + pow (y, 2.0)); ``` ### Tuples Tuples are actually records: ```sml ("I", "Love", "Programming", "Languages"); ``` is actually: ```sml {1="I", 2="Love", 3="Programming", 4="Languages"} ``` Index starting from `1`. ### Datatypes For example: ```sml datatype tree = Leaf of int | Node of tree * tree; ``` `tree` is a type constructor. `Leaf` and `Node` are data constructors: * `Leaf : int → tree` * `Node : tree * tree → tree` #### Pattern matching for datatypes We can define functions by pattern matching: ```sml fun sum (Leaf t) = t | sum (Node (t1, t2)) = sum t1 + sum t2; ``` or ```sml fun sum x = case x of Leaf t => t | Node (t1, t2) => sum t1 + sum t2; ``` Functions accepting data constructors as arguments must provide an exhaustive definition(cover every data constructor for the datatype). #### Parameterized datatypes (with type variables) ```sml datatype 'a gentree = Leaf of 'a | Node of 'a gentree * 'a gentree; val names = Node (Leaf "this", Leaf "that"); ``` ### Common idiom: option `option` is a built-in datatype: ```sml datatype 'a option = NONE | SOME of 'a; ``` A lookup function using option: ```sml fun lookup eq key [] = NONE | lookup eq key ((k,v)::kvs) = if eq (key, k) then SOME v else lookup eq key kvs; ``` Type of `lookup` is `(α1*α2→bool) → α1 → (α2*β)list → βoption`. ### Signature and structures An ML signature specifies an interface for a module. ```sml signature STACKS = sig type stack exception Underflow val empty : stack val push : char*stack->stack val pop : stack->char*stack val isEmpty : stack->bool end ``` A structure implementing it would be: ```sml structure Stacks : STACKS = struct type stack = char list exception Underflow val empty=[] val push=op:: fun pop (c::cs) = (c, cs) | pop [] = raise Underflow fun isEmpty [] = true | isEmpty _ = false end ``` #### Signature ascription **Opaque ascription** (`:>`) hides the identity of types beyond that which is conveyed in the signature. That is, additional type information provided by the structure will be considered abstract.\ **Transparent ascription** (`:`) exposes the identity of types beyond that conveyed in the signature. That is, additional type information provided by the structure will augment the signature. * both prohibit the introduction of identifiers not already present in the signature. This is *component hiding*. * both permit types (in structures) which are broader than the signature. Examples: ```sml signature SetSignature = sig type ’a set val empty : ’’a set val singleton : ’’a -> ’’a set end; structure Set = struct type ’a set = ’a list; val empty = []; fun singleton a = [a] val aux = []; end; (* Opaque ascription *) structure Set2 :> SetSignature = Set; Set2.aux ; (* error - component hiding *) Set2.singleton (2) = [2]; (* error - list representation hidden *) (* Transparent ascription *) structure Set2 : SetSignature = Set; Set2.aux ; (* error - component hiding *) Set2.singleton (2) = [2]; (* okay *) ``` ### Functor A functor creates a structure from a structure. ```sml signature TOTALORDER = sig type element; val lt : element * element -> bool; end ; functor MakeBST (Lt : TOTALORDER): sig type ’label btree; exception EmptyTree; val create : Lt.element btree; val lookup : Lt.element * Lt.element btree -> bool ; val insert : Lt.element * Lt.element btree -> Lt.element btree; val deletemin : Lt.element btree -> Lt.element * Lt.element btree; val delete : Lt.element * Lt.element btree -> Lt.element btree; end = struct open Lt ; datatype ’label btree = Empty | Node of ’label * ’label btree * ’label btr... val create = Empty; fun lookup (x, Empty) = ...; fun insert (x, Empty) = ...; exception EmptyTree; fun deletemin (Empty) = ...; fun delete (x , Empty) = ...; end; ``` Invoke the functor: ```sml structure String : TOTALORDER = struct type element = string ; fun lt (x, y) = let fun lower (nil) = nil | lower (c::cs ) = (Char.toLower c)::lower(cs); in implode(lower(explode(x))) < implode(lower(explode(y))) end ; end ; structure StringBST = MakeBST (String); ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://notes.dizy.cc/programming-languages/sml-nj.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.