Please send all questions & assignments to:
dsolarek@eng.utoledo.edu

Introduction and Overview

The version used in this course is Standard ML of New Jersey (SML/NJ). SML/NJ is a compiler, interactive system (interpreter), and programming environment for the Standard ML language.

History and Standards

Standard ML is one of the few languages with a full formal definition. It was first designed in 1983-1988 and was based on an older language (also called ml) but with many improvements, simplifications and extensions. (Robin Milner, Mads Tofte and Robert Harper, The Definition of Standard ML, MIT Press, 1990). There was a small revision to the language in 1997 along with the introduction of a standardised library and finalised as SML 97. (see Robin Milner, Mads Tofte and Robert Harper, The Definition of Standard ML (revised), MIT Press, 1997, ISBN: 0-262-63181-4). The name of the revised language remains Standard ML, but is also refered to as Standard ML '97 or SML '97 to distinguish it from the 1990 version, which is referred to as SML '90. It should be noted that the Standard ML core language is not a pure applicative programming language, it is a higher-order procedural language with an applicative subset.

Standard ML of New Jersey (SML/NJ) is an implementation of ML which was developed jointly at Bell Laboratories, Princeton University, and recently Yale University. It is under continuing development by researchers in the Languages and Applied Logic group at Bell Labs (Lucent) together with researchers at Princeton University and the University of Pennsylvania. The SML/NJ distribution includes CM (a separate compilation manager), ML-Yacc, ML-Lex, ML-Burg, the SML/NJ Library, Concurrent ML, eXene (a multithreaded X-windows toolkit), and the SML/NJ-C interface library.

Version 110 of SML/NJ (released in February 1998), is largely compliant with the new SML '97 Definition, including the new Basis library.

Functional Programming and SML/NJ

The basic mode of computation in SML/NJ, as in other functional languages, is the use of the definition and application of functions. In functional programming, the following are true:

• Programs are collections of definitions.
• The basic mode of computation is the construction and application of functions. Higher-order functions take functions as arguments and return functions as results.
• Functions are free from side effects (operations that permanently change the value of an identifier). NO assignment operation.
• Recursion is the only method of repetion.
• rule-based programming
• includes pattern matching
• Polymorphism permits functions to take arguments of various types
• Strong data typing, ML has a type inference system which which permits strong type checking without requiring declaration of the type of each variable.

SML Terminology

Structure

Standard ML has modules called structures. Structures facilitate the division of a large program into a number of smaller, independent units with well-defined, explicit connections. A large programming task may then be broken up so that several members of a programming team may independently produce structures which are assembled to form a single program.

Signature

We may wish to take the opportunity when collecting definitions into a structure to hide some of the declarations which played a minor role in helping the implementor to construct the major definitions of the structure. Thus, we require a interface for our structure. The Standard ML term for such an interface is a signature.

Polymorphic

Many functions do not need to know the type of their arguments in order to produce meaningful results. Such functions are thought of as having many forms and are thus said to be polymorphic.

Statement

The term statement has nor real meaning in ML (or SML), each SML program is made up from expressions and functional evaluations. Expressions and functions evaluate to values.

Expression

ML includes arithmetic, Boolean, string, if, while and list expressions.

Tuple

One of the SML structured data types is a tuple, a sequence of objects separated by commas and enclosed in parentheses (e.g., (145, "cat", 3.5, 6) ).

List

A list (a second SML structured data type) is a tuple consisting of objects of the same type.

Record

A tuple is a special case of a record (the third SML structured data type). In ML, a record is a series of labels and values (e.g., {label1=value1, label2=value2, ...} ). Components are selected with the #label operator.

 - #2((17,"abc", true));
 val it = "abc" : string
 - #rank({name = "bob",salary = 50000.99, rank=1});
 val it = 1 : int

Identifiers and Reserved Words

Identifiers are strings of symbols starting with a letter or an apostrophe (') and containing letters, digits, and the underscore character ( _ ). Identifiers beginning with the apostrophe are considered type identifiers.

SML Basics

The latest SML interpreter has been installed on the et105 server. You can telnet to your account on this machine by using et105.ni.utoledo.edu. Once connected to et105, activate the SML interpreter by typing sml at the UNIX prompt. The example below illustrates the activation of the SML interpreter on et105:

 et105:~/sml$ sml
 Standard ML of New Jersey, Version 110.0.6, October 31, 1999
 - 

• The ML prompt is the dash character (-).
• Expressions typed in are immediately evaluated and usually displayed together with the resulting data type.
• Expressions are terminated with semicolon (;).
• ML is case sensitive, so ABC differs from abc. All of the reserved words of the language, such as val and fun, must be in lower case and occurrences of a program identifier must use capitalization consistently.
• Comments in ML are enclosed in (* and *) delimiters. ML comments can be nested.

• read input from the user,
• evaluate it, and
• print the computed value (or an error message).

Using New Jersey Standard ML (SML/NJ) the following example illustrates a simple "Hello World" entry:

 - "Hello World";
 val it = "Hello World" : string

Here is a numeric expression that is also in its simplest form:

 - 456;
 val it = 456 : int

The following example illustrates a calculation. The expression 3+4 is evaluated to the value 7 and this result is displayed:

 - 3+4;
 val it = 7 : int

 - 4 + 4 +
 = 4;
 val it = 12 : int

 - 2=3;
 val it = false : bool

Print

 print("hi\n");
 hi
 val it = () : unit

The following is a variation on the "Hello World" example which uses print:

 - print("hello world!\n");
 hello world!
 val it = () : unit

 - fun PrintHello(x:int) = if x=2
 =  then print("Hello World\n")
 =  else print("Goodbye World\n");
 val PrintHello = fn : int -> unit

 - PrintHello(1);
 Goodbye World
 val it = () : unit
 - PrintHello(2);
 Hello World
 val it = () : unit

 - fun Doit() = PrintHello(2);
 val Doit = fn : unit -> unit
 - Doit();
 Hello World
 val it = () : unit

 - fun Notit() = PrintHello(3);
 val Notit = fn : unit -> unit
 - Notit();
 Goodbye World
 val it = () : unit

Simple Types

 4, 22                  int
 4.3, 10.5E3            real
 "hello", "12", "\n"    string
 #"w"                   char
 true, false            bool

 - 10.5E3;
 val it = 10500.0 : real
 - #"w";
 val it = #"w" : char

 - SML90.sqrt(4.0);
 val it = 2.0 : real
 - floor(it);
 val it = 2 : int
 - real(it);
 val it = 2.0 : real

 - SML90.exp(2.0);
 val it = 7.38905609893 : real
 - floor(it);
 val it = 7 : int

Explicit coersions between lists and strings are accomplished with the built-in functions explode and implode. The explode function converts from a string into a list and the implode function takes a string list and returns a single string.

Let

 let val x = ... in ... end;

 {
 int x;
 ...
 }

 - let val x = 4 in x+3 end;
 val it = 7 : int

 - val x=4;
 val x = 4 : int
 - val y = x+3;
 val y = 7 : int
 - x*x;
 val it = 16 : int
 - x*y;
 val it = 28 : int
 - val z=x+2*y;
 val z = 18 : int

SML Operators & Built-in Functions

 - 3+2;
 val it = 5 : int
 - 8-2;
 val it = 6 : int
 - 7*6;
 val it = 42 : int
 - 4 div 2;
 val it = 2 : int
 - 5 mod 2;
 val it = 1 : int
 - 12.0/3.0;
 val it = 4.0 : real
 - chr(65);
 val it = #"A" : char
 - SML90.sqrt(2.0);
 val it = 1.41421356237309 : real
 - SML90.sin 3.14159;
 val it = 2.65358979323E~06 : real
 - abs(2);
 val it = 2 : int
 - 3-7;
 val it = ~4 : int
 - abs(it);
 val it = 4 : int
 - abs(~7);
 val it = 7 : int

The ^ operator is used for string concatenation, for example:

 - "hello" ^ "world";
 val it = "helloworld" : string

 - not(true);
 val it = false : bool
 - true andalso false;
 val it = false : bool

As part of the evaluation process, SML determines the type of the output value.

Infix Identifiers

 infix  7  * / div mod
 infix  6  + - ^
 infixr 5  :: @
 infix  4  = <> > >= < <=
 infix  3  := o
 infix  0  before

Binding Names to Values

 - val three = 3;
 val three = 3 : int

 - three;
 val it = 3 : int

 - val five = 3+2;
 val five = 5 : int

 - three + five;
 val it = 8 : int

Expression-Based

 - (if (2=3) then 5 else 6) + 1;
 val it = 7 : int

 - if (2=3) then 5 else 6.5;
 stdIn:49.1-49.25 Error: types of rules don't agree [literal]
   earlier rule(s): bool -> int
   this rule: bool -> real
   in rule:
     false => 6.5
 GC #0.0.0.0.2.49:   (10 ms)

Defining Functions

 fun <fun_name> <parameter> = <expression>;

 fun double x = 2*x;
 fun inc x = x+1;
 fun adda s = s ^ "a";

 double 5;
 inc 99;
 adda "mom";

 - fun double x = 2*x;
 val double = fn : int -> int
 - double 4;
 val it = 8 : int
 - double(4);
 val it = 8 : int

 - fun triple(x) = 3*x; 
 val triple = fn : int -> int

 - triple(222); 
 val it = 666 : int

If we call a function with an inappropriate argument (one of the wrong type), we will get an error message, as shown below:

 - triple(2.0); 
 Error: operator and operand don't agree

 - fun max(x:int,y:int,z:int) = 
 =     if ((x>y) andalso (x>z)) then x 
 =        else (if (y>z) then y else z); 
 val max = fn : int * int * int -> int 
 - max(3,2,2); 
 val it = 3 : int

 fun power (x,k) : real =
   if k=1 then x
   else if k mod 2 = 0
       then   power(x*x, k div 2)
       else x*power(x*x, k div 2);

 - use "power.sml";
 [opening power.sml]
 GC #0.0.0.0.1.9:   (20 ms)
 val power = fn : real * int -> real
 val it = () : unit

 - power(3.4,3);
 val it = 39.304 : real

Recursive Definitions

These languages strongly encourage the use of recursion as a structuring mechanism in preference to iterative constructs such as while-loops.

Here is an example of a recursive function:

 - fun factorial(x) = if x=0 then 1
 =   else x*factorial(x-1);
 val factorial = fn : int -> int

 - factorial(7);
 val it = 5040 : int
 - factorial(12);
 val it = 479001600 : int

Lists

A list in SML is essentially a finite sequence of objects, all of the same type:

 - [1,2,3];
 val it = [1,2,3] : int list
 - [true,false, true];
 val it = [true,false,true] : bool list
 - [[1,2,3],[4,5],[6]];
 val it = [[1,2,3],[4,5],[6]] : int list list

All objects in a list must be of the same type:

 - [1,[2]];
 Error: operator and operand don't agree

The empty list is denoted by the following symbol:

 - [];
 val it = [] : 'a list

Operations on Lists

The function hd returns the first element of its argument list.

 - hd[1,2,3];
 val it = 1 : int
 - hd[[1,2],[3]];
 val it = [1,2] : int list

The function tl removes the first element of its argument lists, and returns the remaining list.

 - tl[1,2,3];
 val it = [2,3] : int list
 - tl[[1,2],[3]];
 val it = [[3]] : int list list

The types of the two functions are as follows:

 - hd;
 val it = fn : 'a list -> 'a
 - tl;
 val it = fn : 'a list -> 'a list

More List Operations

 - 5::[];
 val it = [5] : int list
 - 1::[2,3];
 val it = [1,2,3] : int list
 - [1,2]::[[3],[4,5,6,7]];
 val it = [[1,2],[3],[4,5,6,7]] : int list list

 - [1]::[2,3];
 Error: operator and operand don't agree

List can also be compared for equality:

 - [1,2,3]=[1,2,3];
 val it = true : bool
 - [1,2]=[2,1];
 val it = false : bool
 - tl[1] = [];
 val it = true : bool

Defining List Functions

For example, consider the problem of defining an SML function, call it concat, that takes as arguments two lists of the same type and returns the concatenated list. (This function is actually defined in the next section.)

For example, the following applications of the function concat should yield the indicated responses.

 - concat([1,2],[3]);
 val it = [1,2,3] : int list
 - concat([],[1,2]);
 val it = [1,2] : int list
 - concat([1,2],[]);
 val it = [1,2] : int list

• the empty list [] or
• of the form x::y.

 - [1,2,3]=1::[2,3];
 val it = true : bool

Concatenation of Lists

• If x is an empty list, then concatenating x with y yields just y.
• If x is of the form x1::x2, then concatenating x with y is a list of the form x1::z, where z is the results of concatenating x2 with y. In fact we can even be more specific by observing that x = hd(x)::tl(x).

This suggests the following recursive definition.

 - fun concat(x,y) = if x=[] then y
 =     else hd(x)::concat(tl(x),y);
 val concat = fn : ''a list * ''a list -> ''a list

 - concat([1,2],[3,4,5]);
 val it = [1,2,3,4,5] : int list
 - concat([],[1,2]);
 val it = [1,2] : int list
 - concat([1,2],[]);
 val it = [1,2] : int list
 - concat([],[]);
 val it = [] : ''a list

Array Summing Programs

(* original version of summing program *)
fun digit(c:char):int = 
 ord(c) - ord(#"0");

fun SumNext(V:char list) = 
 if V=[] then
 (
  print ("\n Sum=");
  0  
 )
 else
 (
  print(Char.toString( hd(V) ));
  SumNext(tl(V)) + digit(hd(V))
 );


fun SumValues(x:string):int =
 SumNext(explode(x));

fun ProcessData() = 
 (
  let 
   val infile = SML90.open_in("data.sml");
   val count = digit(hd(explode(SML90.input(infile,1))))
  in
   print (Int.toString (SumValues(SML90.input(infile,count))))
  end;   
  print("\n")
 );

Below, is another version of the program above which does not use depreciated functionality:

(* uses no depreciated elements *)
fun digit(c:char):int = 
 ord(c) - ord(#"0");

fun SumNext(V:char list) = 
 if V=[] then
 (
  print ("\n Sum=");
  0  
 )
 else
 (
  print(Char.toString( hd(V) ));
  SumNext(tl(V)) + digit(hd(V))
 );


fun SumValues(x:string):int =
 SumNext(explode(x));

fun ProcessData() = 
 (
  let 
   val infile = TextIO.openIn("data.sml");
   val myline = TextIO.inputLine(infile);
   val count = digit(hd(explode(myline)))
  in
   print (Int.toString (SumValues(substring(myline,1,count))))
  end;   
  print("\n")
 );

 555533

The first program should yield the following runtime sequence:

 - use "prog.sml";
 [opening prog.sml]
 val digit = fn : char -> int
 val SumNext = fn : char list -> int
 val SumValues = fn : string -> int
 val ProcessData = fn : unit -> unit
 val it = () : unit
 - ProcessData();
 55533
  Sum=21
 val it = () : unit

As with the first version, the second program will yield the following (or similar) runtime sequence:

 - use "prognew.sml";
 [opening prognew.sml]
 val digit = fn : char -> int
 GC #0.0.0.0.1.14:   (10 ms)
 val SumNext = fn : char list -> int
 val SumValues = fn : string -> int
 val ProcessData = fn : unit -> unit
 val it = () : unit
 - ProcessData();
 55533
  Sum=21
 val it = () : unit

To assure that you understand what these programs are doing, modify the data file and run each of the programs again.

Assignment

 - fun PrintHello(x:int) = if x=2
 =  then print("Hello World\n")
 =  else print("Goodbye World\n");
 val PrintHello = fn : int -> unit

1. telnet to the backup class server, et105.ni.utoledo.edu
2. create a sml directory
3. use the sml interpreter to run the PrintHello function (shown above) from the - prompt
4. use one of the UNIX editors (e.g., pico) to enter the array sum program listed above and use the sml interpreter to run this program
5. use one of the UNIX editors to enter the second version of the array sum program listed above and use the sml interpreter to run this program
6. compare your results for both programs
7. modify the data file and run each of these programs again

There have been visitors since 11/26/2003