SML is a compiler for the Standard ML language. It’s what we’ll be using in CPSC 312 to run our ML programs, or just to test out individual statements. Just like SWI-Prolog, SML has a command line where we can enter commands.
To start SML, type sml at the unix prompt. To exit, press control-D. Here is what an SML session might look like (user input is in red):
|
cs312@pender% sml
|
The dash (-) is the interactive SML prompt. The equal sign (=) prompt means that SML is waiting for you to complete the input. For example, this prompt appears while entering the cat() function (don't confuse this continuation prompt with the equal sign used to bind names with values).
Two other things you might be wondering about regarding the code above are the ~ and the ^. These are both built-in SML functions. ~ is the unary minus, used to express negative numbers. ^ is a binary function that concatenates two strings. A useful list of other such predeclared identifiers is located in the very back of ML for the Working Programmer.
We can enter expressions directly at the interactive prompt, and SML will evaluate them. Unbound expressions are bound to the special name it. We can use it in later expressions (such as size it; where we determine the length of the string returned by cat();). Be careful when using it though, since it will be overwritten by any other unbound expression we ask SML to evaluate.
To load a file into SML, use the use function. For example:
|
- use "myfile.sml"; |
After each command or expression is entered, SML responds with the binding that occured.
To exit from SML, press ^D (hold the control key down and give the [d] key a tap.
There are three basic definition type forms, one for values, one for functions, and one for types. We will only consider values and functions now.
To bind a name to a value, use val. The general form is:
val name = expression;
Where name is the name to bind the value to returned after evaluating expression. Some examples:
|
- val boolean_value = false;
|
SML figures out that 25 is an integer -- since 5 is an integer, SML uses integer multiplication which returns an integer.
To create a function, we essentially bind a function to a name (the function is a value). The general forms are:
fun name parameters = code;
fun name parameters_1 = code |
name parameters_2 =
code |
...
name parameters_3 =
code;
Where parameters is the list of parameters for the function, and code is the body of the function, made up of expressions. Some examples of parameters are:
We now explain these parameters:
SML is not fussy about parentheses the way Scheme is. It is okay to add extra parentheses to specify precidence.
Some examples of simple functions are:
|
- fun double x = 2 * x;
|
For function double, SML determines that x is of type integer because 2 is an integer, so * is an integer multiplication operator, so the function double returns an integer. We can see that SML has determined that double is a function value for a function that accepts an integer and returns an integer. If we wanted double to double real numbers instead, we could simply replace the 2 with 2.0 to make SML perform real multiplication instead of integer multiplication.
Function sqr accepts a real and returns a real because x was specified as real, so real multiplication was chosen which returns a real value. Without the type coercion, sqr would have the type: int -> int.
concat takes two string inputs, represented as string*string (the Cartesian product of the types), and returns a string. The interface for concat is thus: string*string->string
cons just performs a list cons operation. SML cannot determine the type for x, so it specifies 'a which means 'any type'. Because of the consing (::) operation, SML knows that y must be a list, but its type depends on the type of x, hence y is of type 'a list. The interface for cons is determined to be: 'a * 'a list -> 'a list. Our cons function would work with lists of any type (polymorphism), providing that every element in the second argument (which is a list) is of the same type as the first argument. For example, cons( 2.0, [ 3.4, 5.6 ] ); would return the list [2.0,3.4,5.6], but cons( 2, [ 3.4, 5.6 ] ); would give us an error since the first argument is an integer and the second argument is a list of reals.
SML lets us create multiple functions with the same name, but matching different patterns for the parameters. This is done using the bar (|) symbol to separate the definitions. For example, this procedure, with a base case and a tail-recursive case, adds up all the number between n and 0:
|
- fun sum 0 = 0 |
|
This function, also with a base case and a tail-recursive case, sums up all the elements in a list:
|
- fun sum [] = 0 |
|
Note that, just as in Prolog, the order of these cases matters. See what happens with one of these functions if you put the recursive case before the base case.
It is important that the parameter patterns cover all the input cases. Parameter pattern matching is not as general as in Prolog. Input names cannot be bound to values as they could in Prolog (output must be returned). The same variable cannot appear more than once in the input (SML does not unify the way the Prolog does).
A list can be written as [1,2,3], much like Prolog. Lists in SML must have elements that are all of the same type.
Functions return the value of the last expression evaluated.
The if-then-else expression is very useful, expecially for our examples below. The general form of the if-then-else is:
if cond then
true_expression
else
false_expression
Where cond is an expression (the condition) that results in a boolean value. The true_expression is the expression evaluated if cond is true, and the false_expression is the expression evaluated if cond is false.
SML has the comparison operators: <=, =, >= that compare integers
or reals and return a boolean result.
(define fib
(lambda (n)
(if (<= n 1)
1
(+ (fib (- n 1) (- n 2)))))
(fib 6)
13
Write a more efficient version called fast_fib. Do not use any if then else statements. Assume n is always greater than zero.
2) The following C++ code:
#include <iostream.h>
int a = 5;
int f()
{
return a;
};
void main()
{
a = -10;
cout << f() << endl;
a = 20;
cout << f() << endl;
};
Would display:
-10
20
to the console. Write the equivalent SML code (not necessarily the code that will give equivalent output). What values are returned, and why?
3) Convert the following Prolog code into SML:
member(X,[X|_]).
member(X,[_|Xs]) :- member(X,Xs).
append([],X,X).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
For the append/3, write a version that mimics the recursive form of Prolog, and write a form that is not recursive.
Try the following queries as equivalent SML statements:
member(X,[1,2,3]).
member(2,[1,2,3]).
member(4,[1,2,3]).
member(3,[1,'hello','there']).
member('hello',['why','hello','there']).
For each SML version of append, try these queries as equivalent SML statements:
append([1,2,3],[4,5,6],X).
append([1,2,3],['a','b','c'],X).
Note how the ML code is much more intuitive and readable than the Scheme code, largely due to the use of infix notation:
fun fib n = if (n <= 1) then 1 else fib(n-1) + fib(n-2);
fib 6;
val it = 13 : int
(* fast_fib_helper (n,prev,curr) where n is the decrementing counter
*)
(* prev is previous fibonacci value, curr is current fibonacci value
*)
(* we must declare fast_fib_helper before fast_fib since SML is statically
*)
(* linked and fast_fib calls fast_fib_helper. the initial call
to fast_fib_helper *)
(* should set prev to 1 and curr to 1 *)
fun fast_fib_helper (0,prev,curr) = prev |
fast_fib_helper (1,prev,curr) =
curr |
fast_fib_helper (n,prev,curr) =
fast_fib_helper(n - 1,curr,prev + curr);
val fast_fib_helper = fn : int * int * int -> int
fun fast_fib n = fast_fib_helper (n,1,1);
val fast_fib = fn : int -> int
fast_fib 6;
val it = 13 : int
2)
val a:int = 5;
val a = 5 : int
fun f () = a;
val f = fn : unit -> int
val a = ~10;
val a = ~10 : int
f();
val it = 5 : int
val a = 20;
val a = 20 : int
f();
val it = 5 : int
SML is statically linked, so it uses the values bound at the time the function was created.
3)
fun member (x,[]) = false |
member (x,y::xs) = if (x = y) then
true
else
member (x,xs);
val member = fn : ''a * ''a list -> bool
member(X,[1,2,3]);
stdIn:57.8 Error: unbound variable or constructor: X
member(2,[1,2,3]);
val it = true : bool
member(4,[1,2,3]);
val it = false : bool
member(3,[1,"hello","there"]);
stdIn:65.10-65.29 Error: operator and operand don't agree [literal]
operator domain: int * int list
operand:
int * string list
in expression:
1 :: "hello" :: "there" :: nil
member("hello",["why","hello","there"]);
val it = true : bool
fun append ([],x: 'a list) = x |
append (x::xs,y: 'a list) = x::append(xs,y);
val append = fn : 'a list * 'a list -> 'a list
append([1,2,3],[4,5,6]);
val it = [1,2,3,4,5,6] : int list
append([1,2,3],["a","b","c"]);
stdIn:70.1-70.30 Error: operator and operand don't agree [literal]
operator domain: int list * int list
operand:
int list * string list
in expression:
append (1 :: 2 :: <exp> :: <exp>,"a" ::
"b" :: <exp> :: <exp>)
fun append (x,y) = x @ y;
val append = fn : 'a list * 'a list -> 'a list
append([1,2,3],[4,5,6]);
val it = [1,2,3,4,5,6] : int list
append([1,2,3],["a","b","c"]);
stdIn:73.1-73.30 Error: operator and operand don't agree [literal]
operator domain: int list * int list
operand:
int list * string list
in expression:
append (1 :: 2 :: <exp> :: <exp>,"a" ::
"b" :: <exp> :: <exp>)