Introduction to functional programming and ML

Introduction

A function f from a set X to a set Y is a correspondance that assigns each element of x is an element ofX a unique element y is an element ofY. The element y is called the image of x under f, and is denoted by f(x). The set X is called the domain of the function. The range of the function consists of all images of the elements of X.

A functional programming language takes the definition of function literally. A program is a set of functions, which map input sets to output sets. The power of a functional programming language is the ability to express computation as a function from input to output.

In functional programming, sets are represented by types. A type is just a set of values; the set can be finite or infinite. The set of all integers is a type, and it is an infinite set; the set of boolean values (true and false) is a type, and it is finite. Many programming languages have predefined types, such as integer or boolean (although they may restrict the integer type to a subset of all integers). We will assume these two types for now. An important part of our exploration into functional programming will be the invention of new types to represent data, and functions which manipulate these types during computation.

An important motivation for functional programming is called referential transparency. That is, given a function f:X -> Y, and the equality y=f(x), we can rewrite any expression that uses y by substituting f(x) (or vice versa). This is a natural thing to do in mathematics, but it may not be obvious that it is a good thing to do in a computer program. One goal in studying functional programs (ie, programs in a functional programming language) is to learn how to get referential transparency to work towards program correctness. If a function is correct (ie, it computes the correct image for each element in the domain), then it will be correct no matter where it is used. This is not always the case with "functions" defined in programming languages like C or C++. In a strict functional programming language, it is always true.

In a functional programming language, a function (ie, a mapping from a set to another set) is a thing, in the way that "true" is a thing, or the integer 3 is a thing. If we can have sets of integers or booleans, we can also have sets of functions. For this reason, the set of all functions is a type, just like integers are a type.

In functional programming languages, functions are considered to be first-class citizens. This means that functions enjoy the same privileges as values of other types. In particular, functions can be

1. associated with names
2. passed as arguments to functions
3. returned as values of functions

For our purposes, functions take exactly one argument, and map to exactly one value. While this may seem restrictive, it is not. A function like addition maps a pair of numbers to a number. It is sufficient to realize that a pair is a single thing, even though it has two components. This idea generalizes. We can express functions of n-tuples to m-tuples, for any n,m >= 0. Consider a function which maps a pair of numbers (x,y) to the pair (y,x). There are two numbers in each tuple, but each tuple is a single thing.

The benefit of functional programming is that there is a uniformity to the model of computation: almost every computation is a function evaluation (there are necessary exceptions, which will be made clear). Our data is in the form of types, and our computation takes the form of function evaluation.

Introduction to ML

Interaction with ML is usually in the form of declaration, definition, and evaluation; we will get to these forms of expression shortly.

ML is a typed language. It is strongly typed in the sense that the value of every expression belongs to a type. This means that when you enter an expression in the ML system, it must be well-defined enough that the system can respond by giving you the value of the expression, as well as the type of that expression. To aid in this, ML also has a type inference system, which is able to infer the type of an expression in most cases. If ML cannot infer the type of your expression, it generates an exception, and an error message is printed to the screen.

The advantage of strongly typed langauges is that many programming errors can be eliminated by requiring the programmer to adhere to strict type constraints.

A strongly typed language often requires that type information be completely defined at compile time. For example, C or Pascal requires that all functions and procedures be given compile-time information about the types of their arguments.

In contrast, ML has a polymorphic type system: some type information can be supplied at run-time, allowing a single function to be applied to a variety of different types. Polymorphic functions still have type information at compile-time; however, they make use of what are called type variables, which allow a type to be specified at run-time. For example, a function which computes the length of a list need not know at compile time the type of the list's elements. Thus we can write one function, compile it, and at run-time ask for the length of any kind of list.

The language ML has a simple syntax for simple contructs. For example, the boolean type is called bool and has values true,false. Likewise the type called int represents a subset of the set of all integers; non-negative elements of int are written in the familar way: 0,1,2,3,/ldots; negative elements are written using the tilde ~, instead of a hyphen -. The hyphen is used to denote subtraction.

The following table lists the simple types of ML.

Type	Examples
unit	()
bool	true, false
int	0, 1, ~1, 2, ~2, ...
real	0.0, 1.0, ~1.0, 2.0E17, ~2.423478E 54, ...

Note the type unit, which has only a single element, namely ().

ML has a large number of functions which are primitive, such as arithmetic functions for integers, and logical functions like negation for boolean values.

The type fn is the type containing all functions; we'll discuss this more later.

Environment model of evaluation

In ML, names and values are added to the environment using the following syntax:

- val x = 5;
> val x = 5 : int;

ML responds with no small amount of detail. ML indicates its reply by starting with the character >, and then telling what it has done. In this case, it replies that it has recorded an association between the value 5 and the name x.

The keyword val is not optional. It tells the system not to evaluate the left hand side, but only the right hand side. If val were left out, the system would try to evaluate the expression x = 5; in this context, the = denotes a function from pairs of ints to bool. If x is an int in the environment, x = 5 will evaluate to true or false, depending on the value of x. If x is some other type, x = 5 raises an exception, and ML complains that there is a type mismatch. Finally, if x is not defined in the environment, ML raises an exception because it cannot evaluate x=5, since x has no value it can find.

Functions in ML are defined slightly differently (but this is for the programmer's convenience). The definition

- fun f x = 2*x;

> val f = fn : int -> int;

- val f = (fn x => 2*x);

ML replies

> val f = fn : int -> int

Now that f is a part of the environment, we are free to use it in expressions:

- f 10;
val it = 20 : int

The system responded to the expression f 10 by saying that the name it currently holds the int 20. Everytime you enter an expression which does not change the environment, the ML system remembers the value with the name it. You can use this name as if you defined it yourself, and it is helpful when you are evaluating a complicated expression in smaller pieces.

The environment changes with each definition. Value definitions hide previous values with the same name. For example, suppose we made the following three definitions:

- fun f x = 2*x;
val f = fn : int -> int
- fun g y = (f y) + 1;
val g = fn : int -> int
- fun f x = 3*x;

This point is important for program correctness: you cannot break a correct program by changing the value of some name it uses. Consider what might happen if you (accidentally) changed the value for pi, for example. On the down side, when you are debugging a program, you must remember to re-compile all the parts of the program which change, everytime it changes.

The mechanism behind this is dynamic creation of environments. Everytime you evaluate an expression, a new environment is created, which remembers the names you've defined. A new environment will hide the value of a name, if it has some object with the same name as some old environment, as in the above example.

Initially, there are two environments. The first is the PRIMITIVE environment. It is in this environment that all the built-in name-value associations are made. The second is the USER environment, which is initially empty.

The USER environment is linked to the PRIMITIVE environment through the static link of the USER environment. The static link is the one followed to find the value associated with a name.

Expressions are evaluated with respect to the current environment. The current environment can change during the evaluation of an expression. When a new environment is created, it becomes the current environment. The dynamic link of a newly minted environment refers to the environment which was previously the current environment.

Names are defined within a certain environment. So far, we have seen variables and functions defined in the user environment. Variables and functions can be local to a function as well. To start, the argument for a function is a name in the function's own environment, which is created at the time the function is called. Its value will be the value of the argument which is given to the function. For our example f 3 above, the name x exists in an environment for f, and it gets its value in the function call.

Local variables can be added to functions by the following syntax:

fun f x = 
 let 
   val y = x + 1
 in
   2*y
 end;

The last major piece to play in the functional programming paradigm is the evaluation convention. ML uses call-by-value, which works the following way:

Types

Simple types

ML has the following simple (non-recursive) types:

Type	Examples
unit	()
bool	true, false
int	0, 1,  1, 2,  2, ...
real	0.0, 1.0,  1.0, 2.0E17,  2.423478E 54, ...
record	first=105.4, second=12

The type fn is also a basic type, but we'll discuss this more later.

Tuples and records

- val person = {name="Wolfie", age=35, weight_kg=68.5, sibling_names=["Ardelia", "Jane"]};
val person =
  {age=35,name="Wolfie",sibling_names=["Ardelia","Jane"],weight_kg=68.5}
  : {age:int, name:string, sibling_names:string list, weight_kg:real}
- 

Two records of the same type are equal if the values of their corresponding labelled fields are equal.

Records with a particular structure turn out to be so useful that ML has a special shorthand for them...tuples.

If e₁ has type alpha and e₂ has type beta, then the pair (e₁, e₂) has type alpha*beta. Remember, though, that this is just shorthand for the record {1=e₁, 2=e₂}; the type of this record is then (equivalently) {1:alpha, 2:beta}.

The n-tuple formed from e₁ of type alpha₁, e₂ of type alpha₂, ...e_n of type alpha_n, which is written (e₁, e₂, ...e_n), has type alpha₁ * alpha₂ * ...* alpha_n.

Recursive types

The list 3::4::5::[] can be written in many ways. For example, it may be written as [3,4,5], or as 3::[4,5]. Note that the Prolog form [3|[4,5]] corresponds to 3::[4,5] in ML, with no surrounding square brackets.

Notice that the type of a list is given in the above table as 'a list. "'a" is a type variable, or a variable that ranges over all types in ML (including user-defined types). A particular list will be of a specific type. Thus, the list [3,4,5] is of type int list, because the elements of the list are integers. Notice that, unlike Prolog, ML does not allow lists with elements of differing types. The list [3,4.0,true] is not well-formed in ML.

Functions

In ML, all functions take exactly one argument and return exactly one value. Though this may sound restrictive, it is not. Multiple arguments and returned values can be simulated using tuples. Functions taking no arguments or returning no value can be simulated by functions which map from or to the type unit, respectively.

Here are some examples of function declarations.

- fun f x = x + 1;
val f = fn : int -> int
- fun g(x) = x + 2;
val g = fn : int -> int
- fun h(x,y) = x + y;
std_in:4.16 Error: overloaded variable cannot be resolved: +
- fun h(x:int,y) = x + y;
val h = fn : int * int -> int
- fun h(x,y):int = x+y;
val h = fn : int * int -> int
- fun h(x,y) = x:int + y;
std_in:6.22 Error: unbound type constructor: y
std_in:6.20 Error: unbound type constructor: +
- fun h(x,y) = (x:int) + y;
val h = fn : int * int -> int
- fun h(x,y) = x + y:int;
val h = fn : int * int -> int

Type inference

Weakly typed languages have the advantage that they are very flexible. It is easy to define functions/predicates which work with different types of data. The downside is that run-time type errors can occur. Since there is no type information in the program, the compiler/interpreter cannot ensure that expressions are properly typed.

Strongly typed languages can enforce type constraints, but they do not afford the programmer the same flexibility that weakly typed languages do.

ML has a polymorphic type system. This allows ML to offer type security, if you will, while still giving the programmer some of the flexibility of type-generic functions.

As an example, consider the following function (the identity function):

fun f x = x;

- f 1;
val it = 1 : int
- f 1.0;
val it = 1.0 : real
- f [1,2,3];
val it = [1,2,3] : int list
- f "Hi!";
val it = "Hi!" : string
-

For the function f defined above, ML recognizes that it is not specific to any one type, and assigns the function f a polymorphic type:

val f = fn : 'a -> 'a

What is the difference between overloading and polymorphism? To begin with names can be overloaded, while functions can be polymorphic.

If there are multiple functions which share a common name, we say that this shared name is overloaded. Here is an example. Because the internal representation of integers is different from that of reals, the function which calculates the sum of two integers is different from that which calculates the sum of two reals. Because of the close relationship between addition of integers and addition reals in mathematical terms (the integers are a subset of the reals), it is convenient to refer to their respective addition functions by the same name, "+".

If a single function accpets arguments of different types, then it is called polymorphic. The identity function above is a perfect example. Another example is a function which counts the number of elements in a list:

fun g ([]) = 0
  | g (hd::tl) = 1+g(tl);

val g = fn : 'a list -> int

- g [1,2,3,4,5];
val it = 5 : int
- g [[],[],[],[]];
val it = 4 : int
-

Boolean operations and if-then-else expressions

1. logical and (called andalso in ML)

   If e₁ and e₂ are boolean expressions, then e₁ andalso e₂ is a boolean expression. The value of this expression is determined by first evaluating e₁; if its value if false, the value of the whole expression is false, else the value of the whole expression is the value of e₂.

2. logical or (called orelse in ML)

   If e₁ and e₂ are boolean expressions, then e₁ orelse e₂ is a boolean expression. The value of this expression is determined by first evaluating e₁; if its value if true, the value of the whole expression is true, else the value of the whole expression is the value of e₂.

3. logical negation (called not in ML)

   If e is boolean expression, then not e is a boolean expression. The value of this expression is false if the value of e is true, and true is the value of e is false.

Consider now the conditional expression if e₁ then e₂ else e₃. e₁ must be of type bool, while the type of e₂, call it sigma, must be the same as the type of e₃. The type of a conditional expression is then also sigma.

Local bindings

ML has two forms for establishing local bindings: the let form and the local form. The let form is used to locally bind a name to a value in the scope of an expression. The local form binds a name to value in the scope of a declaration.

Bindings local to expressions

let D in E end

D can have the form D₁; D₂; ... D_n. The D_i's are evaluated in order, making earlier name-value bindings available for later declarations. The expression E is then evaluated, whose value is the value of the whole let expression.

- let fun f x = x + 1 in f 3 end;
val it = 4 : int

A let expression of the form

let Name₁ = Value₁; Name₂ = Value₂; ... Name_n = Value_n in E end;

is equivalent to an anonymous function application (see a later section of the notes for a discussion of anonymous functions).

(fn Name₁ =>

(fn Name₂ =>

...

(fn Name_n => E)...)) Value₁ Value₂ ... Value_n

Bindings local to declarations

local D in Decl end

D can have the form D₁; D₂; ... D_n. The D_i's are evaluated in order, making earlier name-value bindings available for later declarations. The declaration Decl is then processed.

Notice that local D in Name=Value end is not equivalent to Name = let D in Value end:

- local val x = y+1 in fun foo y = x end;
std_in:2.15 Error: unbound variable or constructor: y
- fun foo y = let val x = y+1 in x end;
val foo = fn : int -> int

Parallel (simultaneous) declarations

val V1 = E1
and V2 = E2
and ...
and Vn = En

fun F1 = E1
and F2 = E2
and ...
and Fn = En

In both cases, the Ei's are evaluated first, then these values are bound to the appropriate names. In the case of function declarations, mutally recursive function defintions are expressed in this manner. This is similar to the letrec form in Scheme.

Here are some examples. Parallel value declarations can be used to "swap" the values associated with names (of course, we are really just establishing new bindings, not replacing the old ones).

- val a=1;
val a = 1 : int
- val b=2;
val b = 2 : int
- val a=b and b=a;
val a = 2 : int
val b = 1 : int

Here's an example of a mutually recursive function declaration.

- fun f(x) = g(x-1)
and g(y) = if y<0 then 0 else f(y-2);
= val f = fn : int -> int
val g = fn : int -> int