Standard ML of New Jersey (SML/NJ) is a high-level functional and general-purpose programming language. It is the newest member of a family of languages tracing its origins to the ML language developed at Edinburgh University by Mike Gordon, Robin Milner, and Chris Wadsworth during the 1970's. SML is a synthesis of many of that ideas were explored in the variant languages, notably Luca Cardelli's dialect (``ML under UNIX'', 1984), and in the functional language HOPE developed by Rod Burstall, Dave MacQueen, and Don Sannella (``HOPE'' : An Experimental Applicative Language, 1980).The latest release of SML of New Jersey we used is version 0.93 issued on February 15, 1993.([Har89] p.2)
SML, as a functional programming language, provides a series of useful and convenient mechanisms such as functions and module system, polymorphic types and abstract data type definitions to aid the programmer to develop and manage large and complex programs and re-use the components of the program. Its strong type checking system guarantees that programs are correctly typed before they are run. The SML module system is very good for ``programming in the large''. When programming in the large, there may be many programmers working at one time. So, decomposing a large and complex program into a collection of relatively independent modules with well-defined interfaces is very important. After decomposing a large program into modules, programmers can design different modules. Finally, they compile and link their modules together to become a large program. Now, let's talk about the SML module system briefly.
A module is a collection of declarations viewed as a unit or the environment defined by those declarations. SML has a sophisticated module system for large program design. We can divide a large program into several small parts. Finally these parts of the program are put together by functors.
The SML module system has three components:
Based on these three components, the following principal steps must be followed:
We will use an example, binary search tree, to see how the three components act in a program.
First, we define a signature called SEARCH_TREE to specify the types of Search.
signature SEARCH_TREE =
sig
type item
datatype tree = Empty
| L of item
| N of item * tree * tree
val lessthan : item * item -> bool
val equalto : item * item -> bool
val Bsearch : item * tree -> bool
end; (* end of signature SEARCH_TREE *)
Second, we define a signature called ITEM to specify the types of the parameters of Search_Tree.
signature ITEM =
sig
type item
val lessthan : item * item -> bool
val equalto : item * item -> bool
end; (* end of signature ITEM *)
Third, we define a functor called Search_Tree and use the signature ITEM as the type of the parameter and use the signature SEARCH_TREE as the type of the structure. Inside the functor Search_Tree, we define a function called Bsearch (means search for the key in binary search tree).
functor Search_Tree(Item: ITEM): SEARCH_TREE =
struct
type item = Item.item
fun lessthan(p:item, q:item) : bool = Item.lessthan(p,q)
fun equalto(p:item, q:item) : bool = Item.equalto(p,q)
infix lessthan;
infix equalto;
datatype tree = Empty
| L of item
| N of item * tree * tree;
fun Bsearch(i, Empty) = false
| Bsearch(i, L x) = if i equalto x then true
else false
| Bsearch(i, N(x, l, r)) =
if i equalto x then true
else if i lessthan x then Bsearch(i, l)
else if x lessthan i then Bsearch(i, r)
else false;
end; (* end of functor Search_Tree *)
Finally, we define two different structures. One is IntItem. It is an actual parameter of the functor Search_Tree and indicates all the type items used in the functor are integer types. The other one is StringItem. It indicates that all the types used in the functor are string types.
structure IntItem =
struct
type item = int
fun lessthan(i:item, j) = i < j
fun equalto(i:item, j) = i = j
end; (* end of structure IntItem *)
structure StringItem =
struct
type item = string
fun lessthan(i:item, j)
= if (size i = 0)
then true
else if (size j = 0)
then false
else if (ord(i)<>ord(j))
then ord(i) <= ord(j)
else lessthan(substring
(i,1,size(i)-1),
substring
(j,1,size(j)-1))
fun equalto(i:item, j)
= if (i="" andalso j="") then true
else if (size i <> size j) then false
else if (ord(i) <> ord(j)) then false
else equalto(substring
(i,1,size(i)-1),
substring
(j,1,size(j)-1))
end; (* end of structure StringItem *)
We apply the functor Search_Tree to IntItem and create a new structure called IntBinarySearch:
- structure IntBinarySearch = Search_Tree(IntItem);
structure IntBinarySearch : SEARCH_TREE
When we call the function Bsearch, we need to use the compound name
like
IntBinarySearch.Bsearch. This can grow excessively long when
structures are nested. In order to shorten this compound name, we need
to use a open declaration. After using the open declaration, for instance,
- open IntBinarySearch;
open IntBinarySearch
we can use the function Bsearch directly.
Now, let's define an integer binary search tree:
- val IntTree = N(7, L 1, N(18, L 8, L 28));
val IntTree = N (7,L 1,N (18,L #,L #)) : tree
The IntTree will look like:
IntTree = 7
/ \
1 18
/ \
8 28
- Bsearch(1,IntTree); (* Search if 1 is in the tree or not *)
val it = true : bool (* Yes *)
- Bsearch(28,IntTree); (* Search if 28 is in tree or not *)
val it = true : bool (* Yes *)
- Bsearch(3, LeafOnly); (* Search if 3 is in that leaf *)
val it = false : bool (* No *)
We apply the functor Search_Tree to StringItem and create a new structure called StringBinarySearch:
- structure StringBinaryTree = Search_Tree(StringItem);
structure StringBinaryTree : SEARCH_TREE
Then, open structure StringBinaryTree:
- open StringBinaryTree;
open StringBinaryTree
Now, let's define a string binary search tree:
- val StringTree
= N("brown", L "blue", N("yellow", L "red", L "white"));
val StringTree
= N ("brown",L "blue",N ("yellow",L "red",L "white")) : tree
The StringTree will look like:
StringTree = "brown"
/ \
"blue" "yellow"
/ \
"red" "white"
- Bsearch("red", StringTree);
(* Search "red" is in the tree or not *)
val it = true : bool (* Yes *)
- Bsearch("black", StringTree);
(* Search "black" is in the tree or not *)
val it = false : bool (* No *)
In our project, we will use the module facility of SML to design our programs to create a COSY environment.