• General
• Identifiers
• Types
• Built-In Functions
  • Standard Boolean operators
  • Standard arithmetic operators
  • Coercions
  • Comparisons
  • Operations with strings
  • Operations on characters
  • Operations on lists
  • Operations on tuples
  • Functions with side effects
• Expressions (but not statements)
  • Case expressions and matches
  • If expressions
  • Sequence of expressions
  • Exceptions
• Functions
  • Patterns in functions
  • Mutually recursive functions
  • Local variables in functions
  • Anonymous functions
  • Polymorphic functions
  • Higher-order functions
  • Curried functions
  • Redefining functions

General

This paper describes the 1997 version of Standard ML. There are a very few differences from the earlier (1990) version of ML, and most implementations of Standard ML are very similar. CAML is another dialect of ML, and is not covered here.

ML is case-sensitive.

ML is interactive; you start it up, then you type expressions (at the prompt) to be evaluated. Every expression ends with a semicolon. ML responds with both the value and the type of the result. Example:

- 3 * 4;
> val it = 12 : int
-

In this example, it stands for the English word "it." You can read this response as: Its value is 12, and its type is int. The value of it is always the value most recently computed at the prompt.

To define a value, use the form:

val pi = 3.1416;

ML is an expression-oriented language, not a statement-oriented language. That is, everything in it is considered to be an expression and to have a value. A few expressions that are executed for their side effects rather than their value (mostly output expressions) return the unit, (), as their value--this is like void in C or Java.

To define a function, use the form:

fun average (x, y) = (x + y) / 2.0;

ML is strongly typed; however, it almost always figures out the types for itself. If you need to help it along, you can specify the type of any identifier by following it by a colon and the name of the type. For example, in the function

fun max (x, y) = if x > y then x else y;

the variables x and y could be int, real, char, or string; if you don't specify, ML assumes that they are int. To define this function to use char values, give ML a hint by attaching :char to any one of the variables, anyplace in the function. For example, you could say

To execute the expressions in file myFile.sml (usually definitions that you are testing), use

use "myFile.sml";

Predefined ML functions are in groups called structures, organized around some particular data type. A structure is like a function library. The collection of these structures is called the common basis. The most common functions are in the "top-level environment," which means you don't have to do anything special to use them. For less commonly used functions, you have to either prefix the function name with the name of the structure, or you have to "open" the structure. Opening the structure means making the contents visible to the program.

For example, abs (absolute value) is defined for real numbers in the top-level environment, so we can say

- abs 10.0;
> val it = 10.0 : real

but if we want to take the square root of a real number, we need to say either

- Math.sqrt 10.0;
> val it = 3.16227766 : real

or

- open Math;
> (* long list of functions, including sqrt, omitted *)
- sqrt 10.0;
> val it = 3.16227766 : real

Finally, comments are indicated as:

(* This is a comment (* and comments may be nested. *) *)

Identifiers

There are two kinds of identifiers.

• Alphanumeric identifiers start with ' or with a letter and consist of letters, digits, underscores, and single quotes (called "primes" in mathematics; for example, x' would be read as "x prime."). Alphabetic identifiers are usually used for names of variables and functions.
  
• Symbolic identifiers are composed of any characters except those used in alphanumeric identifiers, or the characters ( ) [ ] { } " , . or whitespace. They are usually used for operators, for example,  +  ++  :=  <<<

Alphanumeric identifiers beginning with a ' (single quote) are used only for type identifiers. Often ML will use 'a to indicate a variable (unknown or arbitrary) type. For example, 'a list means a list whose elements are of type 'a. Additional variable types are indicated by 'b, 'c, and so on.

The variable _ (an underscore all by itself) is used as a "wildcard" or "don't care" variable.

Types

There are several primitive types in ML; the following table gives the most important ones.

Primitive type	Examples	Notes
int	0, 5, 42, ~17, 0x00FF	~ is used for unary minus; there is no unary + 0x starts a hexadecimal number
real	0.0, ~5.3, 1.7e14, 1e~10	Can't start or end with a decimal point
boolean	true, false	These are the only boolean values.
string	"", "One\nTwo"	"\n" is newline, "\t" is tab, "\\" is backslash
char	#"a", #"\n"	# before a string of length 1
unit	()	This is a value. It is the only value of its type, and is often used when the value isn't important (much like void in C).

There are two special real constants in ML:

• inf (infinity) represents the result of dividing a positive real number by 0.0, and
• nan (not a number) represents the result of the division 0.0/0.0.

There are three families of constructed types in ML: lists, tuples, and functions. Functions are first-class objects: they can be created, manipulated, passed as parameters, and otherwise treated like other kinds of values. (However, when ML prints the result of an expression, and that result is a function, ML doesn't print out the entire function; it just prints the word fn.) Every function takes exactly one parameter as input and returns one value as its result; however, that parameter and that result may each be of a constructed type, such as a tuple.

The following table gives a few examples of constructed types. Pay special attention to the second column, which shows how ML expresses type information.

Example expression	Expression type	Notes
[2, 3, 5, 7, 11]	int list	Lists may be of any length, but all elements must be of the same type.
nil	'a list	The empty list can be represented by [] or by nil. The type of this list is allowed to be unknown.
(5, "hello", ~16)	int * string * int	The type of a tuple depends on its length and the types in each position.
("abc", [1, 2, 3])	string * int list	Tuples can contain lists, and vice versa.
(3.5)	real	A tuple with one element is the same as that one element.
fun double x = 2.0 * x;	real -> real	All functions take exactly one parameter, and parentheses are optional.
fun sum (x, y) = x + y;	int * int -> int	In this example the one parameter is a tuple.
fun hi () =   print "hello\n";	unit -> unit	In this example the one parameter is the "unit," and so is the result.
(double, [sum])	(real -> real) * (int * int -> int) list	Functions are values, and can be put into lists and tuples.

Built-In Functions

Standard boolean operators:

Function	Examples	Notes
not : bool -> bool	not true, not (i = j)	(Prefix) Unary negation.
andalso : bool * bool -> bool	(i = j) andalso (j = k)	(Infix, left associative) Conjunction, with short-circuit evaluation. "and" is a keyword with a different meaning.
orelse : bool * bool -> bool	(i = j) orelse (j = k)	(Infix, left associative) Disjunction, with short-circuit evaluation.

 

Standard arithmetic operators:

Function	Examples	Notes
~ : int -> int ~ : real -> real	~5, ~limit ~1e10, ~average	(Prefix) Unary negation.
* : int * int -> int * : real * real -> real	2 * limit, 3.1416 * r * r	(Infix, left associative) Multiplication; operands and result are all of same type.
/ : real * real -> real	7.0 / 3.5, score / average	(Infix, left associative) Division of real numbers.
div : int * int -> int	limit div 2	(Infix, left associative) Integer division with truncation.
mod : int * int -> int	limit mod 2	(Infix, left associative) Modulus.
+ : int * int -> int + : real * real -> real	2 + 2, limit + 1 score + 1.0	(Infix, left associative) Addition of reals or of integers.
- : int * int -> int - : real * real -> real	2 - 2, limit - 1 score - 1.0	(Infix, left associative) Subtraction of reals or of integers.

Coercions

Function	Examples	Notes
real : int -> real	real i, real (limit)	Convert integer to real.
round : real -> int	round (average)	Numbers ending in .5 are rounded to an even number.
trunc : real -> int	trunc average	Fractional part is discarded.
floor : real -> int	floor average	Largest integer not greater than argument.
ceil : real -> int	ceil (average + 3.0)	Smallest integer not less than argument.
ord : char -> int	ord #"a"	ASCII value of character.
chr : int -> char	chr 97	Character corresponding to ASCII value; argument must be in range 0..255.
str : char -> string	str initialLetter	Convert single character to string of length 1.

Comparisons

Function	Examples	Notes
< : 'a * 'a -> bool	i < 0	Less than. a' can be int, real, char, or string.
<= : 'a * 'a -> bool	x <= 0.0	Less than or equal to. a' can be int, real, char, or string.
= : 'a * 'a -> bool	s = "abc"	Equals. a' can be int, char, or string, but not real.
<> : 'a * 'a -> bool	ch <> #"\n"	Not equal. a' can be int, char, or string, but not real.
>= : 'a * 'a -> bool	i >= j	Greater than or equal to. a' can be int, real, char, or string.
> : 'a * 'a -> bool	x > y	Greater than. a' can be int, real, char, or string.

Operations with strings

The operators <  <=  =  <>  >=  > can be applied to strings for lexical comparisons.

Function	Examples	Notes
^ : string * string -> string	"Hello, " ^ name	Infix concatenation of two strings.
concat : string list -> string	concat ["ab", "c", "de"]	String concatenation.
size : string -> int	size "hello"	Number of characters in string.
explode : string -> char list	explode inputString	Convert string to list of characters.
implode : char list -> string	implode [#"h", #"i"]	Convert list of characters to string.
Int.toString : int -> string	print (Int.toString 5);	Convert int to string.
Real.toString : real -> string	print (Real.toString 3.1416);	Convert real to string.
Bool.toString : bool -> string	print (Int.toString (5 < 3));	Convert bool to string.
Char.toString : char -> string	print (Char.toString #"a");	Convert single character to string of length 1. Same as str.

Operations on characters

The operators <  <=  =  <>  >=  > can be applied to characters.

Functions that begin with Char. are in the Char structure. Enter open Char; to use these functions without typing Char. each time (open will also display a list of the functions thus made available).

Char.contains and Char.notContains use currying: Char.contains "aeiou" returns a function of type char -> bool that will return true if given a vowel as an argument. For example, the following two expressions are equivalent (and both return true):

Char.contains "aeiou" #"e";
(Char.contains "aeiou") #"e";

Function	Notes
Char.succ : char -> char	Get the next character in the ASCII sequence; same as chr (ord #"a" + 1).
Char.pred : char -> char	Get the previous character in the ASCII sequence; same as chr (ord #"a" - 1).
Char.toUpper : char -> char	Given a lowercase letter, return the corresponding capital letter. Given any other character, return that same character.
Char.toLower : char -> char	Given a capital letter, return the corresponding lowercase letter. Given any other character, return that same character.
Char.isAlpha : char -> bool	Test if character is alphabetic.
Char.isUpper : char -> bool	Test if character is a capital letter.
Char.isLower : char -> bool	Test if character is a lowercase letter.
Char.isDigit : char -> bool	Test if character is a digit.
Char.isHexDigit : char -> bool	Test if character is a hexadecimal digit. Hex digits A thru F may be uppercase or lowercase.
Char.isAlphaNum : char -> bool	Test if character is alphabetic or numeric.
Char.isAscii : char -> bool	Test if character is a seven-bit character.
Char.isSpace : char -> bool	Test if character is whitespace (blank, tab, newline, etc.)
Char.isPrint : char -> bool	Test if character is printable (including whitespace).
Char.isGraph : char -> bool	Test if character is printable and not whitespace.
Char.contains : string -> char -> bool	Test if the string contains the given character.
Char.notContains : string -> char -> bool	Test if the string does not contain the given character.

Operations on lists

A list is a set of elements, all of the same type, enclosed in brackets and separated by commas. Example: ["hello", "bonjour", "guten Tag"]. The type of this example is string list.

The empty list is represented by [] or by nil.

Function	Examples	Notes
hd : 'a list -> 'a	hd [3, 5, 7]	The "head" of a list is its first element. Same as car in LISP.
tl : 'a list -> 'a list	tl [3, 5, 7]	The "tail" of a list is the list with its first element removed. Same as cdr in LISP.
:: : 'a * 'a list -> 'a list	1 :: [3, 5, 7] 1 :: 3 :: 5 :: 7 :: nil	(Infix, right associative) Inserts an element as the new head of a list. Same as cons in LISP.
@ : 'a list * 'a list -> 'a list	[1, 3, 5] @ [7, 9]	(Infix, right associative) Append two lists. Same as append in LISP.
explode : string -> char list	explode inputString	Convert string to list of characters.
implode : char list -> string	implode [#"h", #"i"]	Convert list of characters to string.
List.rev : 'a list -> 'a list	rev [1, 2, 3]	Reverse the list.
List.take : ('a list * int) -> 'a list	List.take ([1,2,3,4,5], 3)	Return a new list consisting of the first int elements of the given list.
List.drop : ('a list * int) -> 'a list	List.drop ([1,2,3,4,5], 3)	Return a new list with the first int elements removed.

Operations on tuples

If T is a tuple of three elements, then #1(T) is the first element, #2(T) is the second element, and #3(T) is the third element. #4(T) would be an error. This works only for integer constants; if n is a variable, #n(T) is illegal syntax.

Functions with side effects

The most useful functions with side effects are the I/O functions. Since ML automatically prints the values of expressions entered at the prompt, you can often avoid doing any explicit I/O.

The most commonly used output function is print, which prints only strings. If you want to print something other than a string, it is your responsibility to convert it to a string. For example, if N is an integer, Int.toString (N) is its string representation.

Function	Examples	Notes
print : string -> unit	print "Hello\n"	print only prints strings.

The function print is automatically available. If you want to use other I/O functions, you should open the TextIO library by saying

open TextIO;

(or you can prepend TextIO. to each of the function names in the following table). TextIO provides the streams stdIn, stdOut, and stdErr; you don't need to explicitly open these streams. An instream is an input stream; an outstream is an output stream.

Function	Notes
openIn : string -> instream	The argument is the name of a file to be opened for reading.
endOfStream : instream -> bool	Tests for end of file.
inputN : instream * int -> string	Reads int characters and returns them as a string. Will wait for input from a terminal, or return fewer characters if at the end of a file.
inputLine : instream -> string	Reads up to \n; if no \n, one is added, unless the line is completely empty.
input : instream -> string	Reads some system-defined number of bytes from the input stream.
input1 : instream -> char option	Result is either NONE or SOME <char>. These values can be used in patterns.
lookahead : instream -> char option	Peeks at next character, if any.
canInput : instream * int -> bool	Test if at least int characters remain.
closeIn : instream -> unit	Close the input stream.

Function	Notes
openOut : string -> outstream	The argument is the name of a file to be opened for writing.
openAppend : string -> outstream	The argument is the name of a file to be opened for appending.
output : outstream * string -> unit	Write the string to the file.
flushOut : outstream -> unit	Flush the output buffer, thus ensuring that all data that has been written to the file actually makes it there.
closeOut : outstream -> unit	Close the file.

Expressions (but not statements)

ML is a purely functional language: everything is built from functions. Functions return values. Statements don't return values, they have side effects. There are no statements in ML. Things in ML that look like statements are actually expressions, and return values.

The state of a program is the collection of values in the environment. Statements, especially assignment statements, have side effects--that is, they change the state of a program by altering values in the environment. To understand what a program is doing, you have to know the state of the program. Since states can be very large, understanding a program can be difficult.

ML claims to be stateless. That is, you don't need to know about any environmental variables in order to understand a program. Everything you need is either in the function parameters or in the execution stack (the set of function calls that got you to this point). In theory, this should make an ML program easier to understand than a program in a nonfunctional language. There is actually some truth in this point of view.

Because you can define and redefine values and functions at the prompt, the argument that ML is stateless is a little difficult to justify. However, if all your functions are defined in a file, and you just read in that file and use the functions, the stateless nature of ML is more obvious.

Case expressions and matches

The case expression looks like this:

case <expression> of <match>

where a <match> has the form:

   <pattern1> => <expression1> |
   <pattern2> => <expression2> |
   . . .
   <patternN> => <expressionN>

First, the initial <expression> is evaluated, then its value is compared against each of the <patterns>. When a matching <patterni> is found, the corresponding <expressioni> is evaluated and becomes the value of the case expression.

The most common patterns are

•  a variable (matches anything),
•  a tuple, such as (x, y),
•  a literal (constant) value, such as 5 or "abc",
•  an expression x::xs, to match the head and tail of a nonempty list, and
•  an as expression to have a name for the entire actual parameter as well as its parts; for example, L as x::xs, which matches the same things as x::xs, but also assigns to L the entire list.

Examples:

case (N + 1) of 1 => "a" | 2 => "b" | 3 => "c" | 4 => "d";

case myList of [] => "empty" | x::xs => "nonempty";

Because every expression must have a value, ML will warn you if it does not think you have a pattern for every possible case.

When expressions are nested, it can be difficult to tell exactly where the case expression ends. As with any expression, it doesn't hurt to put parentheses around it, as for example,

(case (N + 1) of 1 => "a" | 2 => "b" | 3 => "c" | 4 => "d");

If expressions

The if expression looks like this:

if <boolean expression> then <expression1> else <expression2>

If the <boolean expression> is true, then <expression1> is evaluated and is the value of the expression, otherwise <expression2> is evaluated and is the value of the expression.

Since the if expression is an expression and not a statement, it must have a value; therefore, the else part is required.

The if expression is really shorthand for the following case expression:

case <boolean expression> of true => <expression1> | false => <expression2>

When the ML compiler detects an error in an if expression, it reports the error as though it occurred in the corresponding case expression.

Sequence of expressions

We can execute a sequence of expressions by separating them with semicolons and enclosing the group in parentheses; the value of the sequence is the value of the last expression in the sequence. Any values produced by earlier expressions are discarded. This is only useful with expressions that are evaluated for their side effects.

(print "Hello, "; print name; print "\n");

Expressions with side effects in ML are like the mad relative that lives in the attic and that no one likes to talk about. However, printing output is a side effect, and output is about the only use of side effects in ML. Output operations produce the unit, (), as their value. ML therefore expects all the expressions (except the last) in a semicolon-separated list to have a unit value, and will warn you if that isn't the case.

Exceptions

An "exception" is an error. You can declare new types of exceptions, with or without a parameter, as follows:

exception <name> ;
exception <name> of <type> ;

To signal that one of these exceptions has occurred, use

raise <name> ;

The way you use exceptions is as follows:

<expression> handle <match>

where <expression> can perhaps raise an exception; if it does, the first rule in <match> that matches the expression will be executed. If you raise an exception and fail to handle it, ML will give you an "uncaught exception" error.

Example:

exception WrongOrder of int*int;

fun fromTo(m, n) =
  if m > n then raise WrongOrder(m, n)
  else if m = n then [m]
       else m::fromTo(m + 1, n);

fun makeList(m, n) = fromTo(m, n)
  handle WrongOrder(m, n) => (print("Error"); []);
    

Functions

The usual form of a function definition is

fun <name> <parameter> = <expression> ;

A function only has one parameter, but that parameter is frequently a tuple, for example,

fun max (x, y) = if x > y then x else y;

Because a function has only one parameter, the following is legal:

val pair = (3, 5);
max pair;

(The value 5 is returned.)

It doesn't hurt to use a tuple of length 1 in place of a single parameter; the following are equivalent definitions:

fun score  x  = if x < 0 then 0 else x;
fun score (x) = if x < 0 then 0 else x;

Functions that don't use their parameter must still have one; they can be given the unit as the parameter:

fun tab () = print "\t";

Similarly, a function can only return one value, but that value can easily be a tuple. For example,

fun vectorAdd ((x1, y1), (x2, y2)) = (x1 + x2, y1 + y2);

Functions are values, and the definitions given above are syntactic sugar. Specifically,

(The rec stands for "recursive," and can be omitted for non-recursive functions.)

Patterns in functions

Functions use patterns as formal parameters, and parameter transmission is by pattern matching. Examples:

fun length (nil) = 0
|   length (x :: xs) = 1 + length xs;

fun member (X, nil) = false
|   member (X, x::xs) =
       if (X = x)
          then true
          else member (X, xs) ;

As noted above, the usual form of a function definition is

fun <name> <parameter> = <expression> ;

but this is actually implemented using matches, as

val rec <name> = fn <match> ;

(The rec stands for "recursive" and may be omitted for nonrecursive functions.) As an example, here is an alternate definition for length:

val rec length = fn
    nil   => 0
|   x::xs => 1 + length xs;

Mutually recursive functions

Functions must be defined before they are used. To define mutually recursive functions, use fun...and...and.... The following example (to return every other element of a list) is from Elements of ML Programming by Jeffrey D. Ullman:

fun
   take (L) =
      if L = nil then nil
      else hd(L) :: skip(tl(L))
and
   skip (L) =
      if L = nil then nil
      else take(tl(L)) ;

Local variables in functions

It is sometimes convenient to declare local variables and functions using let...in...end. For example,

fun circleData (radius) =
   let
      val pi = 3.1415926536;
      val circumference = two * pi * radius;
      fun area radius = pi * radius * radius
   in
      (circumference, area (radius))
   end;

Anonymous functions

Matches can also be used to define anonymous functions:

(fn x => x + 1) 3

(Result is 4.) Anonymous functions cannot be recursive because, being anonymous, they have no name by which you can call them.

Polymorphic functions

In other languages, "polymorphic" means that you have two or more functions with the same name; in ML it means that a single function can handle more than one type of parameter.

An example of a built-in polymorphic function is the list function hd; it returns the first element of any type of list.

ML functions that you write will be polymorphic if their parameters are used only with polymorphic functions and operators. For example, the following function to reverse the two components of a 2-tuple is polymorphic:

fun revPair (x, y) = (y, x);

To write a polymorphic function, you need to avoid:

• arithmetic operators (because ML needs to know whether the arithmetic is integer or floating point),
• the inequality comparisons <, <=, >, >=
• string concatenation
• boolean operators
• type conversion operators.

You can use:

• lists and the list operators hd, tl, ::, @, along with the constant nil
• tuples, along with #1, #2, and so on
• the equality tests = and <>.

Higher-order functions

A higher-order function is one which takes a function (or a function-containing structure) as an argument, or produces a function (or function-containing structure) as its result, or both. For example,

- fun try (f, x) = f x;
> val try = fn : ('a -> 'b) * 'a -> 'b
- try (hd, [1,2,3]);
> val it = 1 : int
- try (tl, [1,2,3]);
> val it = [2, 3] : int list

Notice in particular the type returned when try is defined: ('a -> 'b) * 'a -> 'b. Here, ('a -> 'b) is a function from type 'a to type 'b, type 'a is the needed parameter type, and 'b is the result type.

To use an infix operator as a function, precede it by the word op. For example, op + (3,5) is the same as 3+5. Hence,

- try (op +, (3, 5));
> val it = 8 : int

Curried functions

As was stated earlier, every function takes exactly one argument and produces one result.

A curried function is a higher-order function that takes an argument and produces as result a new function with that argument embedded in the function. For example,

- fun incr x y = x + y;
> val incr = fn : int -> int -> int
- incr 5 3;
> val it = 8 : int
- (incr 5) 3;
> val it = 8 : int
- val incr5 = incr 5;
> val incr5 = fn : int -> int
- incr5 3;
> val it = 8 : int

Notice the way the function incr is defined, as if it had two blank-separated arguments. In fact, incr takes one argument, x, and produces the curried function (incr x), which then has y as an argument. Now incr can be called as incr 5 3 or as (incr 5) 3, but cannot be called as incr (5, 3). This is because incr takes one argument, an integer, and returns a function as a result; it does not take a tuple as an argument.

The fact that incr 5 returns a function as a result is further emphasized in the assignment of this value (a function that adds 5 to its argument) to the variable incr5,. Note also that we can use val rather than fun because we don't need to specify a parameter; a function is just another kind of value. We could, if we wished, have defined incr5 by  fun incr5 (x) = incr 5 x; with exactly the same result.

map

map is a curried function that takes a function that applies to one thing of type 'a and produces a function that applies to a list 'a. For example,

- round 3.75;
> val it = 4 : int
- map round [2.7, 3.1, 3.8, 9.4, 6.5];
> val it = [3, 3, 4, 9, 6] : int list
- (map round) [2.7, 3.1, 3.8, 9.4, 6.5];
> val it = [3, 3, 4, 9, 6] : int list

List.filter

The function List.filter takes a boolean test and returns a function that will extract from a list those elements that pass the test.

- List.filter (fn x => x > 0) [3, 0, 2, ~5, ~8, 4];
> val it = [3, 2, 4] : int list

Redefining functions

Important: When you define a function, you may use other values (including other functions) in the definition. Later changes to those values do not change the meaning of the function you have defined. For example, look at the following sequence (for clarity, only the last response by ML is shown):

- val x = 3;
- fun aa () = 5;
- fun bb () = aa () + x;
- val x = 17;
- fun aa () = 83;
- bb ();
> val it: int = 8

Here, bb() was defined in terms of aa() and x. Later changes to aa() and x do not affect the definition of bb().

The above may seem strange, but there is a parallel in algorithmic languages. Consider the sequence of statements a := 5; b := a; a := 10; You would not expect the value of b to change just because the value of a changed. In ML, functions are values, and they are treated just like any other values.

A definition is said to have referential transparency if its meaning does not depend on the context it is in. Functions in ML have referential transparency, that is, changing the context (other variables and other functions) does not change the meaning of any functions you have already defined. This fact can be crucial when you are debugging a program, because you are likely to be redefining functions fairly frequently.

(To be continued)