static dynamic
----------------------------------------------
before execution during execution
compilers (fast) interpreters (slow)
I said, for example, that in Python if you define a function that
takes two arguments called a and b and it returns the value a + b,
Python doesn't check in advance that it makes sense to add a and b
together. That means that it can lead to runtime errors. OCaml, by
contrast, does extensive type checking before any code is allowed to
run. That's why we describe OCaml as having static type checking.I also mentioned that I expect most students will use the Ed system to write and run OCaml programs, but there are other options. The unix machines operated by the Allen School have OCaml available. I demonstrated by connecting to attu and creating a file called test.ml in emacs with the following lines of code:
let f(n) = 2 * n
let g(a, b) = a * b
I use emacs, but you can use any editor to create a file. Then I gave
the command "ocaml" at the operating system prompt and gave a command
to #use the file I had created:
[reges@attu7 ~]$ ocaml
OCaml version 4.11.1
# #use "test.ml";;
val f : int -> int =
val g : int * int -> int =
#
So it loaded those definitions from the file and left me in the
interpreter where I can ask it to evaluate expressions. You end your
ocaml session by typing CTRL-D.Then I mentioned that I plan to build up a sort of cheat sheet for OCaml that lists the different language features we have discussed. I will update it for each assignment to include any new features that we are exploring in that homework. The first version is available here.
I pointed out that OCaml cares a lot about the types of various program elements, but it uses type inference to deduce the types when it can. For example, the sqr function below doesn't need the type specification because of the use of the * operator which indicates that n is an int and the return value is an int:
let sqr(n) = n * n
I gave an example where OCaml comes up with an odd type description.
I wrote a function called switch that switches the order of values in
a 2-tuple:
let switch(a, b) = (b, a)
When I asked the interpreter about the type of this function it
said:
# switch;;
- : 'a * 'b -> 'b * 'a =
OCaml is indicating that the first parameter is of type 'a and the
second is of type 'b and that the result reverses the order of these
types. This is OCaml's way of saying that they could be of any type.
We call that a polymorphic type. But what if you wanted to tell OCaml
to use ints? We can do that by specifying a type for each:
let switch((a : int), (b : int)) = (b, a)
I asked people if there was another way of telling OCaml what the type
is. Someone suggested that we could describe the return type of the
function instead of the type of the parameters:
let switch(a, b) : int * int = (b, a)
I mentioned that we could also describe the type of the tuple on the
right-hand side:
let switch(a, b) = ((b, a) : int * int)
Here we needed an extra set of parentheses to make it clear that we
are saying that the type of (b, a) is int * int. So OCaml is very
flexible about infering types as long as the information is included
somewhere. I tend not to include type specifications unless I need
to.Then we discussed the if/else construct, which has the following general form:
let min(x, y) = if x < y then x else y
OCaml indicated that the parameters are of type 'a. This is another
polymorphic type because the less-than operator is defined for most
types in OCaml.Then we talked about using recursion to define functions. I mentioned that the functional languages use recursion often, so if you haven't yet mastered it, this will be your chance to finally figure it out.
The first example we looked at is a factorial function:
let rec factorial(n) =
if n = 0 then 1
else n * factorial(n - 1)
Notice that we had to begin the definition with "let rec" instead of a
simple "let". This is required for recursive functions. We found
that this function went into infinite recursion for a negative number.
For the homework I have asked you to document these kind of
preconditions, as in:
(* pre: n >= 0 *)
let rec factorial(n) =
if n = 0 then 1
else n * factorial(n - 1)
Another option is to call the function invalid_arg when a precondition
is violated:
(* pre: n >= 0 *)
let rec factorial(n) =
if n < 0 then invalid_arg("negative factorial")
else if n = 0 then 1
else n * factorial(n - 1)
Then we discussed how to work with lists. You can construct a list
using the operator :: which is known as the "cons" operator. For
example, we constructed a list by starting with an empty list and
inserting a 7 in front, and then a 5 in front of that, and then a 2 in
front of that, and then a 45 in front of that:
let lst = 45::2::5::7::[]
The cons operator evaluates from right to left, so we ended up with
this list:
[45; 2; 5; 7]
Then we looked at some examples of list recursion. We can pull a list
apart by using the functions List.hd and List.tl. List.hd returns the
"head" of the list (the first value). List.tl returns the "tail" of
the list (the rest of the list). Using these functions, we wrote a
function that takes a list of int values as a parameter and that
returns a new list with each value incremented by one:
let rec inc_all(lst) =
if lst = [] then []
else (List.hd(lst) + 1)::inc_all(List.tl(lst))
And we wrote a function to return the last value in a list, which had
a different base case than the other examples:
let rec last(lst) =
if List.length(lst) = 1 then List.hd(lst)
else last(List.tl(lst))
This version has a precondition that the list is not empty. We can
once again call invalid_arg if the precondition is not satisfied.
(* pre : list is not empty *)
let rec last(lst) =
if lst = [] then invalid_arg("empty list")
else if List.length(lst) = 1 then List.hd(lst)
else last(List.tl(lst))
For a final example, I asked people to consider the problem of
converting a list of names. We assume the names appear as a list of
tuples with last name followed by first name, as in:
let test = [("Clinton", "Hillary"); ("Obama", "Barak"); ("Biden", "Joe")]
The idea is to convert it into a list of simple strings where each string has
the first name followed by a space followed by the last name:
["Hillary Clinton"; "Barack Obama"; "Joe Biden"]
We started a recursive definition:
let rec convert(lst) =
if lst = [] then []
else ...
At this point we were left with the problem of taking the head of the list and
converting it from one form to another. It's a little too much complexity for
us to handle it all at once. This is a great place to introduce a helper
function. If we forget about the list for a minute, we can write a function to
convert the string tuple into a simple string:
let combine(last, first) = first ^ " " ^ last
Given this, it's fairly easy to complete the function:
let rec convert(lst) =
if lst = [] then []
else combine(List.hd(lst))::convert(List.tl(lst))
This technique of introducing a helper function to break down the
complexity of the problem into subproblems is a very important
technique in OCaml programming. You'll want to use this technique for
some of the homework questions.