Functional core of Objective CAML
Like all functional languages, Objective CAML is an expression oriented language,
where programming consists mainly of creating functions and applying them.
The result of the evaluation of one of these expressions is a value in the
language and the execution of a program is the evaluation of all the
expressions which comprise it.
Primitive values, functions, and types
Integers and floating-point numbers, characters, character strings, and
booleans are predefined in Objective CAML.
Numbers
There are two kinds of numbers: integers1 of type int and
floating-point numbers of type float. Objective CAML follows the IEEE
754 standard2 for representing double-precision floating-point numbers.
The operations on integers and floating-point numbers are described in
figure 2.1. Let us note that when the result of an integer
operation is outside the interval on which values of type
int are defined, this does not produce an error, but the result is an integer
within the system's interval of integers. In other words, all integer
operations are operations modulo the boundaries of the interval.
| integer numbers |
floating-point numbers |
| + |
addition |
| - |
subtraction and unary negation |
| * |
multiplication |
| / |
integer division |
| mod |
remainder of integer division |
|
| +. |
addition |
| -. |
subtraction and unary negation |
| *. |
multiplication |
| /. |
division |
| ** |
exponentiation |
|
# 1 ;;
- : int = 1
# 1 + 2 ;;
- : int = 3
# 9 / 2 ;;
- : int = 4
# 11 mod 3 ;;
- : int = 2
(* limits of the representation *)
(* of integers *)
# 2147483650 ;;
- : int = 2
|
# 2.0 ;;
- : float = 2
# 1.1 +. 2.2 ;;
- : float = 3.3
# 9.1 /. 2.2 ;;
- : float = 4.13636363636
# 1. /. 0. ;;
- : float = inf
(* limits of the representation *)
(* of floating-point numbers *)
# 222222222222.11111 ;;
- : float = 222222222222
|
Figure 2.1: Operations on numbers.
Differences between integers and floating-point numbers
Values having different types such as float and int
can never be compared directly. But there are functions for conversion
(float_of_int and int_of_float) between one and the
other.
# 2 = 2.0 ;;
Characters 5-8:
This expression has type float but is here used with type int
# 3.0 = float_of_int 3 ;;
- : bool = true
In the same way, operations on floating-point numbers are distinct from
those on integers.
# 3 + 2 ;;
- : int = 5
# 3.0 +. 2.0 ;;
- : float = 5
# 3.0 + 2.0 ;;
Characters 0-3:
This expression has type float but is here used with type int
# sin 3.14159 ;;
- : float = 2.65358979335e-06
An ill-defined computation, such as a division by zero, will raise an
exception (see page ??) which interrupts the
computation. Floating-point numbers have a representation for infinite
values (printed as Inf) and ill-defined computations (printed as
NaN3). The main functions on
floating-point numbers are described in figure 2.2.
| functions on floats |
trigonometric functions |
| ceil |
|
| floor |
|
| sqrt |
square root |
| exp |
exponential |
| log |
natural log |
| log10 |
log base 10 |
|
| cos |
cosine |
| sin |
sine |
| tan |
tangent |
| acos |
arccosine |
| asin |
arcsine |
| atan |
arctangent |
|
# ceil 3.4 ;;
- : float = 4
# floor 3.4 ;;
- : float = 3
# ceil (-.3.4) ;;
- : float = -3
# floor (-.3.4) ;;
- : float = -4
|
# sin 1.57078 ;;
- : float = 0.999999999867
# sin (asin 0.707) ;;
- : float = 0.707
# acos 0.0 ;;
- : float = 1.57079632679
# asin 3.14 ;;
- : float = nan
|
Figure 2.2: Functions on floats.
Characters and Strings
Characters, type char, correspond to integers between 0 and 255
inclusive, following the ASCII encoding for the first 128. The functions
char_of_int and int_of_char support conversion
between integers and characters.
Character strings, type string, are sequences of characters of
definite length (less than 224-6). The concatenation operator is
.
The functions int_of_string, string_of_int,
string_of_float and float_of_string carry out the
various conversions between numbers and character strings.
# 'B' ;;
- : char = 'B'
# int_of_char 'B' ;;
- : int = 66
# "is a string" ;;
- : string = "is a string"
# (string_of_int 1987) ^ " is the year Caml was created" ;;
- : string = "1987 is the year Caml was created"
Even if a string contains the characters of a number, it won't be possible
to use it in operations on numbers without carrying out an explicit
conversion.
# "1999" + 1 ;;
Characters 1-7:
This expression has type string but is here used with type int
# (int_of_string "1999") + 1 ;;
- : int = 2000
Numerous functions on character strings are gathered in the
String module (see page ??).
Booleans
Booleans, of type bool, belong to a set consisting of two values:
true and false. The primitive operators are described in
figure
2.3. For historical reasons, the ``and'' and ``or'' operators
each have two forms.
| not |
negation |
| && |
sequential and |
| || |
sequential or |
|
| |
| & |
synonym for && |
| or |
synonym for || |
| |
|
Figure 2.3: Operators on booleans.
# true ;;
- : bool = true
# not true ;;
- : bool = false
# true && false ;;
- : bool = false
The operators && and ||, or their synonyms,
evaluate their left argument and then, depending on its value, evaluate
their right argument. They can be rewritten in the form of conditional
constructs (see page ??).
| = |
structural equality |
| == |
physical equality |
| <> |
negation of = |
| != |
negation of == |
|
| < |
less than |
| > |
greater than |
| <= |
less than or equal to |
| >= |
greater than or equal to |
|
Figure 2.4: Equality and comparison operators.
The
equality and comparison operators are described in figure
2.4.
They are polymorphic, i.e., they can be used to compare two integers as
well as two character strings. The only constraint is that their two
operands must be of the same type (see page ??).
# 1<=118 && (1=2 || not(1=2)) ;;
- : bool = true
# 1.0 <= 118.0 && (1.0 = 2.0 || not (1.0 = 2.0)) ;;
- : bool = true
# "one" < "two" ;;
- : bool = true
# 0 < '0' ;;
Characters 4-7:
This expression has type char but is here used with type int
Structural equality tests the equality of two values by traversing their
structure, whereas physical equality tests whether the two values occupy
the same region in memory. These two equality operators return the same
result for simple values: booleans, characters, integers and constant
constructors (page ??).
Warning
Floating-point numbers and character strings are considered structured
values.
Unit
The unit type describes a set which possesses only a single
element, denoted: ().
# () ;;
- : unit = ()
This value will often be used in imperative programs
(3, page ??) for functions which carry out
side effects. Functions whose result is the value () simulate the
notion of procedure, which doesn't exist in Objective CAML, just as the type void does in the C language.
Cartesian product, tuple
Values of possibly different types can be gathered in pairs or more generally in
tuples. The values making up a tuple are separated by commas. The type
constructor * indicates a tuple. The type int * string
is the type of pairs whose first element is an integer (of type
int) and whose second is a character string (of type
string).
# ( 12 , "October" ) ;;
- : int * string = 12, "October"
When there is no ambiguity, it can be written more simply:
# 12 , "October" ;;
- : int * string = 12, "October"
The functions fst and snd allow access to the first and
second elements of a pair.
# fst ( 12 , "October" ) ;;
- : int = 12
# snd ( 12 , "October" ) ;;
- : string = "October"
These two functions accept pairs whose components are of any type
whatsoever. They are polymorphic, in the same way as equality.
# fst;;
- : 'a * 'b -> 'a = <fun>
# fst ( "October", 12 ) ;;
- : string = "October"
The type int * char * string is that of triplets whose first element
is of type int, whose second is of type char, and whose third
is of type string. Its values are written
# ( 65 , 'B' , "ascii" ) ;;
- : int * char * string = 65, 'B', "ascii"
Warning
The functions fst and snd
applied to a tuple, other than a pair, result in a type error.
# snd ( 65 , 'B' , "ascii" ) ;;
Characters 7-25:
This expression has type int * char * string but is here used with type
'a * 'b
There is indeed a difference between the type of a pair and that of a
triplet. The type int * int * int is different from the types
(int * int) * int and int * (int * int). Functions to
access a triplet (and other tuples) are not defined by the core library.
One can use pattern matching to define them if need be (see page
??).
Lists
Values of the same type can be gathered into a list. A list can either be
empty or consist of elements of the same type.
# [] ;;
- : 'a list = []
# [ 1 ; 2 ; 3 ] ;;
- : int list = [1; 2; 3]
# [ 1 ; "two" ; 3 ] ;;
Characters 14-17:
This expression has type int list but is here used with type string list
The function which adds an element at the head of a list is the infix
operator :: . It is the analogue of Lisp's cons.
# 1 :: 2 :: 3 :: [] ;;
- : int list = [1; 2; 3]
Concatenation of two lists is also an infix operator @.
# [ 1 ] @ [ 2 ; 3 ] ;;
- : int list = [1; 2; 3]
# [ 1 ; 2 ] @ [ 3 ] ;;
- : int list = [1; 2; 3]
The other list manipulation functions are defined in the List
library. The functions hd and tl from this library give
respectively the head and the tail of a list when these values exist.
These functions are denoted by List.hd and List.tl to
indicate to the system that they can be found in the module
List4.
# List.hd [ 1 ; 2 ; 3 ] ;;
- : int = 1
# List.hd [] ;;
Uncaught exception: Failure("hd")
In this last example, it is indeed problematic to request retrieval of the
first element of an empty list. It is for this reason that the system
raises an exception (see page ??).
Conditional control structure
One of the indispensable control structures in any programming language is
the structure called conditional (or branch) which guides the
computation as a function of a condition.
Syntax
if expr1 then expr2 else
expr3
The expression expr1 is of type bool. The expressions
expr2 and expr3 must be of the same type, whatever it
may be.
# if 3=4 then 0 else 4 ;;
- : int = 4
# if 3=4 then "0" else "4" ;;
- : string = "4"
# if 3=4 then 0 else "4";;
Characters 20-23:
This expression has type string but is here used with type int
A conditional construct is itself an expression and its evaluation
returns a value.
# (if 3=5 then 8 else 10) + 5 ;;
- : int = 15
Note
The else branch can be omitted, but in this case it is implicitly
replaced by else (). Consequently, the type of the expression
expr2 must be unit (see page ??).
Value declarations
A declaration binds a name to a value. There are two types: global
declarations and local declarations. In the first case, the
declared names are known to all the expressions following the declaration;
in the second, the declared names are only known to one expression. It is
equally possible to simultaneously declare several name-value
bindings.
Global declarations
Syntax
let name = expr ;;
A global declaration defines the binding between the name name and
the value of the expression expr which will be known to all
subsequent expressions.
# let yr = "1999" ;;
val yr : string = "1999"
# let x = int_of_string(yr) ;;
val x : int = 1999
# x ;;
- : int = 1999
# x + 1 ;;
- : int = 2000
# let new_yr = string_of_int (x + 1) ;;
val new_yr : string = "2000"
Simultaneous global declarations
Syntax
| let name1 = expr1 |
| and name2 = expr2 |
| : |
| and namen = exprn ;; |
A simultaneous declaration declares different symbols at the same level.
They won't be known until the end of all the declarations.
# let x = 1 and y = 2 ;;
val x : int = 1
val y : int = 2
# x + y ;;
- : int = 3
# let z = 3 and t = z + 2 ;;
Characters 18-19:
Unbound value z
It is possible to gather several global declarations in the same phrase;
then printing of their types and their values does not take place until the
end of the phrase, marked by double ``;;''.
These declarations are evaluated sequentially, in contrast with a simultaneous
declaration.
# let x = 2
let y = x + 3 ;;
val x : int = 2
val y : int = 5
A global declaration can be masked by a new declaration of the same name
(see page ??).
Local declarations
Syntax
let name = expr1 in
expr2;;
The name name is only known during the evaluation of
expr2. The local declaration
binds it to the value of expr1.
# let xl = 3 in xl * xl ;;
- : int = 9
The local declaration binding xl to the value 3 is only
in effect during the evaluation of xl * xl.
# xl ;;
Characters 1-3:
Unbound value xl
A local declaration masks all previous declarations of the same name, but
the previous value is reinstated upon leaving the scope of the local
declaration:
# let x = 2 ;;
val x : int = 2
# let x = 3 in x * x ;;
- : int = 9
# x * x ;;
- : int = 4
A local declaration is an expression and can thus be used to construct
other expressions:
# (let x = 3 in x * x) + 1 ;;
- : int = 10
Local declarations can also be simultaneous.
Syntax
| let |
name1 = expr1 |
| and |
name2 = expr2 |
| : |
| and |
namen = exprn |
| in |
expr ;; |
# let a = 3.0 and b = 4.0 in sqrt (a*.a +. b*.b) ;;
- : float = 5
# b ;;
Characters 0-1:
Unbound value b
Function expressions, functions
A function expression consists of a parameter and
a body. The formal parameter is a variable name and the body an
expression. The parameter is said to be abstract. For this reason,
a function expression is also called an abstraction.
Syntax
function p -> expr
Thus the function which squares its argument is written:
# function x -> x*x ;;
- : int -> int = <fun>
The Objective CAML system deduces its type. The function type
int -> int indicates a function expecting a parameter of
type int and returning a value of type int.
Application of a function to an argument is written as the function
followed by the argument.
# (function x -> x * x) 5 ;;
- : int = 25
The evaluation of an application amounts to evaluating the body of the
function, here x * x, where the
formal parameter, x, is replaced by the value of the argument (or
the actual parameter), here 5.
In the construction of a function expression, expr is any
expression whatsoever. In particular, expr may itself be a
function expression.
# function x -> (function y -> 3*x + y) ;;
- : int -> int -> int = <fun>
The parentheses are not required. One can write more simply:
# function x -> function y -> 3*x + y ;;
- : int -> int -> int = <fun>
The type of this expression can be read in the usual way as the type of a
function which expects two integers and returns an integer value. But in
the context of a functional language such as Objective CAML we are dealing
more precisely with the type of a function which expects an integer and
returns a function value of type
int -> int:
# (function x -> function y -> 3*x + y) 5 ;;
- : int -> int = <fun>
One can, of course, use the function expression in the usual way by
applying it to two arguments. One writes:
# (function x -> function y -> 3*x + y) 4 5 ;;
- : int = 17
When one writes f a b, there is an implicit parenthesization on
the left which makes this expression equivalent to: (f a) b.
Let's examine the application
(function x -> function y -> 3*x + y) 4 5
in detail. To compute the value of this expression, it is necessary to compute the
value of
(function x -> function y -> 3*x + y) 4
which is a function expression equivalent to
function y -> 3*4 + y
obtained by replacing x by 4 in 3*x + y.
Applying this value (which is a function) to 5 we get the
final value 3*4+5 = 17:
# (function x -> function y -> 3*x + y) 4 5 ;;
- : int = 17
Arity of a function
The number of arguments of a function is called its arity. Usage
inherited from mathematics demands that the arguments of a function be
given in parentheses after the name of the function. One writes: f(4,5).
We've just seen that in Objective CAML, one more usually writes:
f 4 5. One can, of course, write a function
expression in Objective CAML which can be applied to (4,5):
# function (x,y) -> 3*x + y ;;
- : int * int -> int = <fun>
But, as its type indicates, this last expression expects not two, but only
one argument: a pair of integers. Trying to pass two arguments to a
function which expects a pair or trying to pass a pair to a function which
expects two arguments results in a type error:
# (function (x,y) -> 3*x + y) 4 5 ;;
Characters 29-30:
This expression has type int but is here used with type int * int
# (function x -> function y -> 3*x + y) (4, 5) ;;
Characters 39-43:
This expression has type int * int but is here used with type int
Alternative syntax
There is a more compact way of writing function expressions with several
parameters. It is a legacy of former versions of the Caml language.
Its form is as follows:
Syntax
fun p1 ...pn
-> expr
It allows one to omit repetitions of the function keyword and the arrows.
It is equivalent to the following translation:
function p1 -> -> function pn -> expr
# fun x y -> 3*x + y ;;
- : int -> int -> int = <fun>
# (fun x y -> 3*x + y) 4 5 ;;
- : int = 17
This form is still encountered often, in particular in the libraries provided with
the Objective CAML distribution.
Closure
Objective CAML treats a function expression like any other expression and is able
to compute its value. The value returned by the computation is a
function expression and is called a closure. Every Objective CAML
expression is evaluated in an environment consisting of name-value
bindings coming from the declarations preceding the expression being
computed. A closure can be described as a triplet consisting of the name
of the formal parameter, the body of the function, and the environment of
the expression. This environment needs to be preserved because the body of
a function expression may use, in addition to the formal parameters, every other
variable declared previously. These variables are said to be ``free'' in the
function expression. Their values will be needed when the function
expression is applied.
# let m = 3 ;;
val m : int = 3
# function x -> x + m ;;
- : int -> int = <fun>
# (function x -> x + m) 5 ;;
- : int = 8
When application of a closure to an argument returns a new closure, the
latter possesses within its environment all the bindings necessary for a
future application. The subsection on the scope of variables (see page
??) details this notion. We will return to the
memory representation of a closure in chapter 4 (page
??) as well as chapter 12 (page
??).
The function expressions used until now are
anonymous. It is rather useful to be able to name them.
Function value declarations
Function values are declared in the same way as other language values, by
the let construct.
# let succ = function x -> x + 1 ;;
val succ : int -> int = <fun>
# succ 420 ;;
- : int = 421
# let g = function x -> function y -> 2*x + 3*y ;;
val g : int -> int -> int = <fun>
# g 1 2;;
- : int = 8
To simplify writing, the following notation is
allowed:
Syntax
let name p1 ... pn
= expr
which is equivalent to the following form:
let name = function p1 -> -> function pn -> expr
The following declarations of succ and g are equivalent
to their previous declaration.
# let succ x = x + 1 ;;
val succ : int -> int = <fun>
# let g x y = 2*x + 3*y ;;
val g : int -> int -> int = <fun>
The completely functional character of Objective CAML is brought out by the
following example, in which the function h1 is obtained by the
application of g to a single integer. In this case one speaks of
partial application:
# let h1 = g 1 ;;
val h1 : int -> int = <fun>
# h1 2 ;;
- : int = 8
One can also, starting from g, define a function h2
by fixing the value of the second parameter, y, of g:
# let h2 = function x -> g x 2 ;;
val h2 : int -> int = <fun>
# h2 1 ;;
- : int = 8
Declaration of infix functions
Certain functions taking two arguments can be applied in infix form. This
is the case with addition of integers. One writes 3 + 5 for the
application of + to 3 and 5. To use the
symbol + as a regular function value, this must be syntactically
indicated by surrounding the infix symbol with parentheses. The syntax is
as follows:
Syntax
( op )
The following example defines the function succ using
( + ).
# ( + ) ;;
- : int -> int -> int = <fun>
# let succ = ( + ) 1 ;;
val succ : int -> int = <fun>
# succ 3 ;;
- : int = 4
It is also possible to define new operators. We define an operator
++, addition on pairs of integers
# let ( ++ ) c1 c2 = (fst c1)+(fst c2), (snd c1)+(snd c2) ;;
val ++ : int * int -> int * int -> int * int = <fun>
# let c = (2,3) ;;
val c : int * int = 2, 3
# c ++ c ;;
- : int * int = 4, 6
There is an important limitation on the possible operators. They must
contain only symbols (such as *, +, @, etc. ) and
not letters or digits. Certain functions predefined as infixes are
exceptions to the rule. They are listed as follows:
or mod land lor lxor lsl lsr asr.
Higher order functions
A function value (a closure) can be returned as a result. It can equally
well be passed as an argument to a function. Functions taking function
values as arguments or returning them as results are called higher order.
# let h = function f -> function y -> (f y) + y ;;
val h : (int -> int) -> int -> int = <fun>
Note
Application is implicitly parenthesized to the left, but function types are
implicitly parenthesized to the right. Thus the type of the function
h can be written
(int -> int) -> int -> int
or
(int -> int) -> (int -> int)
Higher order functions offer elegant possibilities for dealing with lists.
For example the function List.map can apply a function to all the
elements of a list and return the results in a list.
# List.map ;;
- : ('a -> 'b) -> 'a list -> 'b list = <fun>
# let square x = string_of_int (x*x) ;;
val square : int -> string = <fun>
# List.map square [1; 2; 3; 4] ;;
- : string list = ["1"; "4"; "9"; "16"]
As another example, the function List.for_all can find out
whether all the elements of a list satisfy a given criterion.
# List.for_all ;;
- : ('a -> bool) -> 'a list -> bool = <fun>
# List.for_all (function n -> n<>0) [-3; -2; -1; 1; 2; 3] ;;
- : bool = true
# List.for_all (function n -> n<>0) [-3; -2; 0; 1; 2; 3] ;;
- : bool = false
Scope of variables
In order for it to be possible to evaluate an expression, all the variables
appearing therein must be defined. This is the case in particular for the
expression e in the declaration let p = e. But
since p is not yet known within this expression, this variable can
only be present if it refers to another value issued by a previous
declaration.
# let p = p ^ "-suffix" ;;
Characters 9-10:
Unbound value p
# let p = "prefix" ;;
val p : string = "prefix"
# let p = p ^ "-suffix" ;;
val p : string = "prefix-suffix"
In Objective CAML, variables are statically bound. The environment used to
execute the application of a closure is the one in effect at the moment of
its declaration (static scope) and not the one in effect at the moment of
application (dynamic scope).
# let p = 10 ;;
val p : int = 10
# let k x = (x, p, x+p) ;;
val k : int -> int * int * int = <fun>
# k p ;;
- : int * int * int = 10, 10, 20
# let p = 1000 ;;
val p : int = 1000
# k p ;;
- : int * int * int = 1000, 10, 1010
The function k contains a free variable: p. Since the latter
is defined in the global environment, the definition of k is
legal. The binding between the name p and the value 10
in the environment of the closure k is static, i.e., does not
depend on the most recent definition of p.
Recursive declarations
A variable declaration is called recursive if it
uses its own identifier in its definition. This facility is used
mainly for functions, notably to simulate a definition by recurrence. We
have just seen that the let declaration does not support this.
To declare a recursive function we will use a dedicated syntactic construct.
Syntax
let rec name = expr ;;
We can equally well use the syntactic facility for defining function values
while indicating the function parameters:
Syntax
let rec name p1 ...pn
= expr ;;
By way of example, here is the function sigma which computes the
sum of the (non-negative) integers between 0 and the
value of its argument, inclusive.
# let rec sigma x = if x = 0 then 0 else x + sigma (x-1) ;;
val sigma : int -> int = <fun>
# sigma 10 ;;
- : int = 55
It may be noted that this function does not terminate if its argument is
strictly negative.
A recursive value is in general a function. The compiler rejects
some recursive declarations whose values are not functions:
# let rec x = x + 1 ;;
Characters 13-18:
This kind of expression is not allowed as right-hand side of `let rec'
We will see however that in certain cases such declarations are allowed (see
page ??).
The let rec declaration may be combined with the
and construction for simultaneous declarations. In this case, all
the functions defined at the same level are known within the bodies of each
of the others. This permits, among other things, the declaration of
mutually recursive functions.
# let rec even n = (n<>1) && ((n=0) or (odd (n-1)))
and odd n = (n<>0) && ((n=1) or (even (n-1))) ;;
val even : int -> bool = <fun>
val odd : int -> bool = <fun>
# even 4 ;;
- : bool = true
# odd 5 ;;
- : bool = true
In the same way, local declarations can be recursive. This new definition
of sigma tests the validity of its argument before carrying out
the computation of the sum defined by a local function sigma_rec.
# let sigma x =
let rec sigma_rec x = if x = 0 then 0 else x + sigma_rec (x-1) in
if (x<0) then "error: negative argument"
else "sigma = " ^ (string_of_int (sigma_rec x)) ;;
val sigma : int -> string = <fun>
Note
The need to give a return value of the same type, whether the argument is
negative or not, has forced us to give the result in the form of a
character string. Indeed, what value should be returned by sigma when its
argument is negative? We will see the proper way to manage this problem,
using exceptions (see page ??).
Polymorphism and type constraints
Some functions execute the same code for arguments having different types.
For example, creation of a pair from two values doesn't require
different functions for each type known to the
system5. In the same way, the function to access the first field of a pair doesn't
have to be differentiated according to the type of the value of this first
field.
# let make_pair a b = (a,b) ;;
val make_pair : 'a -> 'b -> 'a * 'b = <fun>
# let p = make_pair "paper" 451 ;;
val p : string * int = "paper", 451
# let a = make_pair 'B' 65 ;;
val a : char * int = 'B', 65
# fst p ;;
- : string = "paper"
# fst a ;;
- : char = 'B'
Functions are called polymorphic if their return value or one of their
parameters is of a type which need not be specified. The type synthesizer
contained in the Objective CAML compiler finds the most general type for each
expression. In this case, Objective CAML uses variables, here 'a and
'b, to designate these general types. These variables are
instantiated to the type of the argument during application of the
function.
With Objective CAML's polymorphic functions, we get the advantages of being
able to write generic code usable for values of every type, while still
preserving the execution safety of static typing. Indeed, although
make_pair is polymorphic, the value created by
(make_pair 'B' 65) has a well-specified type which is different
from that of (make_pair "paper" 451). Moreover, type
verification is carried out on compilation, so the generality of the code
does not hamper the efficiency of the program.
Examples of polymorphic functions and values
The following examples of polymorphic functions have functional parameters
whose type is parameterized.
The app function applies a function to an argument.
# let app = function f -> function x -> f x ;;
val app : ('a -> 'b) -> 'a -> 'b = <fun>
So it can be applied to the function odd defined previously:
# app odd 2;;
- : bool = false
The identity function (id ) takes a parameter and returns it as is.
# let id x = x ;;
val id : 'a -> 'a = <fun>
# app id 1 ;;
- : int = 1
The compose function takes two functions and another value and
composes the application of these two functions to this value.
# let compose f g x = f (g x) ;;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
# let add1 x = x+1 and mul5 x = x*5 in compose mul5 add1 9 ;;
- : int = 50
It can be seen that the result of g must be of the same type as
the argument of f.
Values other than functions can be polymorphic as well. For example, this is
the case for the empty list:
# let l = [] ;;
val l : 'a list = []
The following example demonstrates that type synthesis indeed arises from
resolution of the constraints coming from function application and not from the value
obtained upon execution.
# let t = List.tl [2] ;;
val t : int list = []
The type of List.tl is 'a list -> 'a list, so this
function applied to a list of integers returns a list of integers. The
fact that upon execution it is the empty list which is obtained doesn't
change its type at all.
Objective CAML generates parameterized types for every function which doesn't use
the form of its arguments. This polymorphism is called
parametric polymorphism6.
Type constraint
As the Caml type synthesizer generates the most general type, it may be
useful or necessary to specify the type of an expression.
The syntactic form of a type constraint is as follows:
Syntax
( expr : t )
When it runs into such a constraint, the type synthesizer will take it into
account while constructing the type of the expression. Using type
constraints lets one:
-
make the type of the parameters of a function visible;
- forbid the use of a function outside its intended context;
- specify the type of an expression, which will be particularly useful
for mutable values (see page ??).
The following examples demonstrate the use of such type constraints
# let add (x:int) (y:int) = x + y ;;
val add : int -> int -> int = <fun>
# let make_pair_int (x:int) (y:int) = x,y;;
val make_pair_int : int -> int -> int * int = <fun>
# let compose_fn_int (f : int -> int) (g : int -> int) (x:int) =
compose f g x;;
val compose_fn_int : (int -> int) -> (int -> int) -> int -> int = <fun>
# let nil = ([] : string list);;
val nil : string list = []
# 'H'::nil;;
Characters 5-8:
This expression has type string list but is here used with type char list
Restricting polymorphism this way lets us control the type of an expression
better by constraining the polymorphism of the type deduced by the system.
Any defined type whatsoever may be used, including ones containing type
variables, as the following example shows:
# let llnil = ([] : 'a list list) ;;
val llnil : 'a list list = []
# [1;2;3]:: llnil ;;
- : int list list = [[1; 2; 3]]
The symbol llnil is a list of lists of any type whatsoever.
Here we are dealing with constraints, and not replacing Objective CAML's type
synthesis with explicit typing. In particular, one cannot
generalize types beyond what inference permits.
# let add_general (x:'a) (y:'b) = add x y ;;
val add_general : int -> int -> int = <fun>
Type constraints will be used in module interfaces (14)
as well as in class declarations (15).
Examples
In this section we will give several somewhat elaborate examples of
functions. Most of these functions are predefined in Objective CAML. We will
redefine them for the sake of ``pedagogy''.
Here, the test for the terminal case of recursive functions is implemented
by a conditional.
Hence a programming style closer to Lisp. We will see
how to give a more ML character to these definitions when we present
another way of defining functions by case (see page
??).
Length of a list
Let's start with the function null which
tests whether a list is empty.
# let null l = (l = []) ;;
val null : 'a list -> bool = <fun>
Next, we define the function size to compute the length of a list
(i.e., the number of its elements).
# let rec size l =
if null l then 0
else 1 + (size (List.tl l)) ;;
val size : 'a list -> int = <fun>
# size [] ;;
- : int = 0
# size [1;2;18;22] ;;
- : int = 4
The function size tests whether the list argument is empty.
If so it returns 0, if not it returns 1 plus the value
resulting from computing the length of the tail of the list.
Iteration of composition
The expression iterate n f computes the value f
iterated n times.
# let rec iterate n f =
if n = 0 then (function x -> x)
else compose f (iterate (n-1) f) ;;
val iterate : int -> ('a -> 'a) -> 'a -> 'a = <fun>
The iterate function tests whether n is 0, if yes it returns the
identity function, if not it composes f with
the iteration of f n-1 times.
Using iterate, one can define exponentiation as iteration of
multiplication.
# let rec power i n =
let i_times = ( * ) i in
iterate n i_times 1 ;;
val power : int -> int -> int = <fun>
# power 2 8 ;;
- : int = 256
The power function iterates n times the function expression
i_times, then applies this result to 1, which does indeed
compute the nth power of an integer.
Multiplication table
We want to write a function multab which computes the multiplication
table of an integer passed as an argument.
First we define the function apply_fun_list such that, if
f_list is a list of functions, apply_fun_list x f_list
returns the list of results of applying each element of
f_list to x.
# let rec apply_fun_list x f_list =
if null f_list then []
else ((List.hd f_list) x)::(apply_fun_list x (List.tl f_list)) ;;
val apply_fun_list : 'a -> ('a -> 'b) list -> 'b list = <fun>
# apply_fun_list 1 [( + ) 1;( + ) 2;( + ) 3] ;;
- : int list = [2; 3; 4]
The function mk_mult_fun_list returns the list of
functions multiplying their argument by i,
for i varying from 0 to n.
# let mk_mult_fun_list n =
let rec mmfl_aux p =
if p = n then [ ( * ) n ]
else (( * ) p) :: (mmfl_aux (p+1))
in (mmfl_aux 1) ;;
val mk_mult_fun_list : int -> (int -> int) list = <fun>
We obtain the multiplication table of 7 by:
# let multab n = apply_fun_list n (mk_mult_fun_list 10) ;;
val multab : int -> int list = <fun>
# multab 7 ;;
- : int list = [7; 14; 21; 28; 35; 42; 49; 56; 63; 70]
Iteration over lists
The function call fold_left f a [e1; e2; ... ; en]
returns f ... (f (f a e1) e2) ... en. So there are n
applications.
# let rec fold_left f a l =
if null l then a
else fold_left f ( f a (List.hd l)) (List.tl l) ;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
The function fold_left permits the compact definition of a
function to compute the sum of the elements of a list of integers:
# let sum_list = fold_left (+) 0 ;;
val sum_list : int list -> int = <fun>
# sum_list [2;4;7] ;;
- : int = 13
Or else, the concatenation of the elements of a list of strings:
# let concat_list = fold_left (^) "" ;;
val concat_list : string list -> string = <fun>
# concat_list ["Hello "; "world" ; "!"] ;;
- : string = "Hello world!"