Chris Reade's

Introduction

These web pages are designed for beginners learning to use Standard ML and also as a complement to the book Elements of Functional Programming Very occasional reference to Java is made for comparison, although familiarity with Java is not essential for reading these pages.

Why Functional Programming?

HOT Languages

An important feature of recent modern programming languages (like ML and Java) is that they are HOT. That is, they are Higher Order and Typed. Higher order means that the building blocks of programs can be treated as data to be manipulated by programs, so programs can be built by programs rather than from scratch every time. In the case of OO languages like Java, this means objects can contain methods which manipulate objects; In the case of ML, functions can pass around and use functions. The flexibility and power this gives for programming is enormous BUT it is also dangerous because small slips in design can wreak havoc if not pinpointed early. Strong type systems which prevent all programs with type errors from being executed are a must when working at this level of abstraction. Ideally, static type systems are needed (these do all the necessary type checking at compile time and catch errors much earlier).

Problems with Procedural Programming

Programming languages developed as an abstraction from machine control languages. Most programming languages in use today are procedural languages which still reflect these origins. In particular, they still have an explicit flow of control (sequences and loops of basic effects) and an explicit interaction with memory (assignment statements).

There are two major problems with programs written in these languages: firstly, they have a bottleneck (known as the von-Neumann bottleneck) caused by continuous transfering of data to and from memory with assignments; and, secondly they can become very unstructured and hard to maintain or adapt for reuse when larger programs are written.

Structured programming and later Object-oriented programming were organisational techniques used to alleviate the latter problem by giving better structure to procedural programs. In particular, localising state (variables) as much as possible, and grouping procedures (methods) with data was seen as a route to provide for simpler maintenence of programs.

Pure functional programming goes a step further by removing state altogether, effectively automating the control flow and memory management. This is done by using a language based on expression evaluation (rather than statement execution) so that the compiler takes on the task of organising the details of the computation. The programmer can then concentrate on what is to be put together to do calculations, and not the details of how the book keeping and storing of intermediate values is to be done.

It is perhaps surprising that everything that can be done with conventional (sequential) programming languages can also be done with pure expression evaluation (even interactive programming) and there does not need to be any loss in performance. What is gained, is that programs can be developed much faster (and with much more likelihood of correct behaviour) by simplifying the programmer's task.

In fact ML is not a pure functional language in that it is possible to write procedural programs (with assignments and side-effects) in ML. However, a pure functional style is encouraged by the language and we will focus on this style. [In practice, we use some simple control to do I/O procedurally because the pure approach to interaction uses techniques which are too advanced for this introductory module].

A crude summary would be to say that functional programming involves designing functions which are similar to procedures or methods but without the use of (assignable) variables.

A simpler model of computation

If you try to think about the relationship between (1) the behaviour of an executing program and (2) the source text of the program, you need to have a model of how the program is being executed. A big advantage of the purely functional approach is that there is a much simpler model. The model is just one of calculating expressions (similar to arithmetic calculations done in school algebra) and does not require a model of memory, variable assignment or effects over time. [These more abstract models of computation which do not rely on an underlying machine model were known about in the 1930s before modern computers were developed. They strongly influenced the design of functional programming languages which declare or describe rather than instruct.]

Here are some pictures illustrating very simple functional and procedural programs as flow graphs.

About the Workshop

The ML Workshop is a series of small exercises and examples designed to help beginners understand the basic concepts of functional programming and Standard ML and to be used as a supplement to reading a text book such as Elements of Functional Programming by Chris Reade published by Addison Wesley, 1989 (Referred to as [Reade89] from now on)

Although ML is highly suitable for building large systems (with a very advanced module system), this aspect of ML will not be covered in this workshop. Examples are kept small to illustrate ideas and to build highly reusable tools for subsequent programming, prototyping and experimenting.

Although the examples are small and may appear trivial in nature to begin with, you should soon see how quite sophisticated tools can be built relatively quickly. Much of the material in these exercises is discussed in the above book but note that the book predates the 1997 ML standard and library (hence these supplementary web pages).

When doing any exercise it is recommended that you keep records, plan and take time to reflect on and analyse work. You should pay particular attention to the following responses when you enter expressions and definitions in an interactive ML session:

Error Messages (Syntax or otherwise)
Type information and presentation of values

Keep a record (e.g of responses you don't understand, errors, unexpected behaviour...) and discuss with others any problems or things you find interesting/unexpected. Try to predict responses as you become familiar with ML.

Using ML

There are several implementations of ML available and these work on various platforms. It would be nice to say these all implement exactly the same language [Which has a fully formally specified definition], but this is not quite true. However, it is nearly true, and Standard ML is a remarkably stable language.

Prior to 1997, there was no standardised library (apart from a very small collection of commonly used functions and types), so implementations varied widely in the non-standard additions they provided.

In 1997 a standard library was designed, accompanied by a (very small) modification to the definition of the language. The changes to the language are almost unnoticable and most programs written for the earlier standard (SML '90) will easily work the the 1997 version of standard ML (SML '97). [The most noticable change is probably the introduction of a new character type. In SML '90, characters were regarded as strings of size 1. In SML '97, a separate type of characters (distinct from strings) is used.]

Running ML

Although ML is compiled, implementations give the appearance of an interpreted language because there is an interactive front end for ML. That is, unlike Java or C or Pascal, you can begin a dialog with the ML system then enter definitions and expressions for evaluation interactively. Each definition and expression is compiled as you enter it then it is evaluated and the result is returned at the prompt. [The ML system keeps track of compiled code for you so you only need to worry about source code].

This applies to all implementations of the standard. In the rest of this text, we illustrate the ML responses using SML of New Jersey.

A Quick trial (SML of New Jersey)

The top level prompt asking you to enter a definition or expression is:
-
Expressions can run over several lines, and should be terminated with a ';' (followed by <return> ). The prompt:
=
indicates that the system is waiting for completion of an expression. If this was unexpected, you may have forgotten the ';' or a closing ' " ' or a closing ')'.

Try entering 3+5; <return> and you should see

-   3+5;
val it = 8 : int           (this line is ML's response)
-

Then try entering 3 <return> +5; <return> to get

-   3
=   +5; 
val it = 8 : int
-

Now try entering the following definitions

val yearMins = 365*24*60;
val yearSecs = yearMins*60;
(65-16) * yearSecs ;

Copy and Paste and Loading Files

When you type definitions and expressions directly to the ML console, they are compiled straight away and are available for immediate use. However, you will want to keep non-trivial definitions, you should prepare them in a file with a text editor. You can then load them during the interactive session (either by copy and paste into an ml session window or using use - see below). This allows you to experiment and build up your own working environment within the language. When you terminate a session your compiled definitions will be forgotten. There is no need for you to keep compiled code as quite large programs will compile in seconds.

During an ML session, you can type in an expression for evaluation with the form

use "filename";

The definitions in the file will be read in, compiled and evaluated as though typed at the prompt. The filename should be a path relative to where you started ML from (usually your home directory). So if 'myfile' is in a directory 'myML' in your home directory, load it with

 use "myML/myfile";

Print Depth

SML of New Jersey (v110) only prints a small part of large data values and then prints "...". To change the low limits set as default use printdepth.sml.