## Part 1: Working with OCaml and Unix
The OCaml toplevel `utop` has many features that make interacting with it
easier. We'll start by showing you some of those. Using these tips will save
you hours of debugging time during the semester.
### Tab completion
*Tab completion* is an extremely useful feature of both the command line and
`utop`.
**Exercise:** open `utop`. Type `Ran` and press ``. Delete that and type `Ra`
and press ``. Delete that and type `Arr` and press ``.
The tab key figures out all possible completions for what you've started to
type. If all possible completions share some more characters, then it adds
those characters. You'll notice that the list of all possible completions is
shown just below the command line.
### The command line
**Extended exercise:**
Exit the top level. Change to your home directory (called `~`) using
the `cd` command:
cd ~
List the files in that directory using the `ls` command:
ls
Create a directory called recitations using the `mkdir` command:
mkdir recitations
Change to that directory:
cd re
Create a file called `func.ml` using your editor of choice:
subl func.ml
emacs func.ml
gvim func.ml
**End of extended exercise.**
### The #use directive
`utop` is very convenient for quickly testing an idea, but it quickly becomes
cumbersome to re-type the same sequence of expressions over and over again.
The `#use` directive instructs `utop` to process the contents of a file as if you
had typed them in. You will save yourself countless hours over the course of the semester
if you develop the following habit:
**As soon as you find yourself typing something a second time into `utop`,
put it into a file that you `#use` instead.**
For the rest of this lab, put all your code into `func.ml`, and execute
it as you go by typing
#use "func.ml";;
in the top level.
## Part 2: Defining functions
### Recursive functions
**Exercise:** Define a recursive function `fact : int -> int`, such
that `fact n` is `n!`, where `!` denotes the
[factorial function][fact].
**Exercise:** Define a recursive function `fib : int -> int`, such
that `fib n` is the `n`th number in the *Fibonacci sequence*.
The [Fibonacci sequence][fib] is 0, 1, 1, 2, 3, 5, 8, 13, ...
[fact]: https://en.wikipedia.org/wiki/Factorial
[fib]: https://en.wikipedia.org/wiki/Fibonacci_number
### Polymorphic Functions
Perhaps the simplest function is the identity function `fun x -> x`. What is
its type?
```
utop# fun x -> x;;
- : 'a -> 'a
```
The `'a` is a *type variable*: it stands for an unknown type, just like
a regular variable stands for an unknown value. Type variables always
begin with a single quote. Commonly used type variables include `'a`, `'b`, and `'c`,
which OCaml programmers typically pronounce in Greek: alpha, beta, and gamma.
**Exercise:** what is the type of `f`, defined as follows:
let f x = if x then x else x
Explain why it has this type.
**Exercise:** what is the type of `g`, defined as follows:
let g x y = if y then x else x
Explain why it has this type.
**Exercise:** what is the type of `h`, defined as follows:
let h x y z = if x then y else z
Explain why it has this type.
**Exercise:** what is the type of `i`, defined as follows:
let i x y z = if x then y else y
Explain why it has this type.
### Partial application
Consider the function `add1` defined as follows:
```
let add1 x = x + 1
```
Recall that this can also be written
```
let add1 = fun x -> x + 1
```
**Exercise:** Use the `fun` keyword to define functions `add1`, `add2`, and
`add3` of type `int -> int`. Discover that this is boring.
```
let add2 : int -> int = ...
let add3 : int -> int = ...
let add4 : int -> int = ...
```
**Exercise:** define a function `addn` which takes an integer `n` as input, and
returns a *function* of type `int -> int`.
```
let addn n : int -> int = ...
```
Finish the above exercise before proceeding.

The intent is that `addn` is a function that takes an integer `n` and gives you
a function of type `int -> int`. You might expect that it would have type
`int -> (int -> int)`. However, utop probably gave you the following:
```
addn : int -> int -> int =
```
It turns out that `int -> (int -> int)` and `int -> int -> int` are exactly the
same, Just as `3 - 5 - 2` and `(3 - 5) - 2` are exactly the same values (note also
that `(int -> int) -> int` is different from `int -> int -> int`, just like
`3 - (5 - 2)` is different from `3 - 5 - 2`). "But wait," you say! `int -> int
-> int` is the type of a function that takes two ints and returns an int, which
is different from our function which takes a single int and returns a function.
In fact, the following three functions are **syntactically different** but
**semantically equivalent**. That is, they are different ways of expressing
the same computation:
```
let add x y = x+y
let add x = fun y -> x+y
let add = fun x -> (fun y -> x+y)
```
The function `addn` that you defined is exactly the same as the function `add`.
If you give either of them a single argument, it simply returns a function that
is expecting the second argument. For example:
```
let add10 = add 10
```
**Exercise:** Put the definitions of `add` and `add10` into `func.ml` and find
out what `utop` says the type of it is. Compare the type of `add10` to the
type of `add`. Experiment with applying `add10` to some arguments.
What you just did is called *partial application*: you partially applied
the function `add` to one argument, even though you normally would think
of it as a multi-argument function. This works exactly because `add`
is really a function that takes an argument `x` and returns
a function `(fun y -> x+y)`. Which leads us to a deep truth...
### The truth about functions
Are you ready for the truth? Here goes...
**Every OCaml function takes exactly one argument.**
Why? Consider `add`: although we can write it as
`let add x y = x + y`, we now know that's semantically
equivalent to `let add = fun x -> (fun y -> x+y)`.
And in general,
```
let f x1 x2 ... xn = e
```
is semantically equivalent to
```
let f =
fun x1 ->
(fun x2 ->
(...
(fun xn -> e)...))
```
So even though you think of `f` as a function that takes `n` arguments,
in reality it is a function that takes 1 argument, and returns
a function.
### Implicit parentheses
After the above discussion, you will now understand that
```
t1 -> t2 -> t3 -> t4
```
means the same as
```
t1 -> (t2 -> (t3 -> t4)))
```
That is, function types are right associative:
there are implicit parentheses around function types,
from right to left.
The intuition here is that a function takes a single argument
and returns a new function that expects the remaining arguments.
But what about function application?
**Exercise:** In `add 2 3`, where are the implicit parentheses? Answer
before reading further.
A function application
```
e1 e2 e3 e4
```
means the same as
```
((e1 e2) e3) e4
```
That is, function application is left associative:
there are implicit parentheses around applications, from left to right.
The intuition here is that the left-most expression grabs the next
expression to its right as its single argument.
### Operators
The addition operator `+` has type `int->int->int`.
It is normally written *infix*, e.g., `3+4`.
By putting parentheses around it, we can
make it a *prefix* operator: `(+) 3 4`.
The same technique works for any built-in operator.
(But be careful of multiplication, which must be
written `( * )` as infix, because `(*)` would be
incorrectly parsed as beginning a comment.)
We can even define our own new infix operators, as follows:
let (^^) x y = max x y;;
2 ^^ 3 (* is 3 *)
**Exercise:**
Try this yourself, by defining an infix operator `$$` to compute
the average of two floating-point numbers. For example,
* `1.0 $$ 2.0 = 1.5`
* `0. $$ 0. = 0.`
### Higher-order functions
In OCaml, functions are *higher order*: they can take functions
as inputs and return functions as output. This feature is really
just a consequence of the decision that functions are values;
they can be used anywhere any other kind of value may be used.
You've already written some functions that return functions as results. In
this section we'll consider functions that also take other functions as
arguments.
Consider writing some functions that double and square their arguments:
```
let double x = 2*x
let square x = x*x
```
Now, consider writing functions that quadruple and raise-to-the-4th-power
their arguments:
```
let quad x = double (double x)
let fourth x = square (square x)
```
Do you see how we've repeated the same pattern of code in writing `quad` and `fourth`?
Each calls a function twice. We can factor out that pattern using a higher-order
function:
```
let twice f x = f (f x)
let quad x = twice double x
let fourth x = twice square x
```
Function `twice` takes a function `f` as its first argument, a value `x` as its
second argument, then applies `f` to `x`, and applies `f` again to the result of
`f x`. Function `quad` passes `double` and `x` to `twice`, causing `double` to
be applied twice.
Let's look at the type of `twice`:
```
# twice;;
- : ('a -> 'a) -> 'a -> 'a =
```
Function `twice` therefore takes a first argument that is a function
from `'a` to `'a`, a second argument that is a value of type `'a`,
and returns a value of type `'a`. Note how `twice` can be used on any type `'a`:
```
let quad x = twice double x
let repeat s = s ^ s
let rerepeat s = twice repeat s
```
In `quad`, `'a` is `int`. In `rerepeat`, it is `string`. This kind of
abstraction from the particular type of a value is known as
*parametric polymorphism*.
As another example in parenthesizing types, note that the type of `twice` is
the same as `('a -> 'a) -> ('a -> 'a)`. With the explicit parentheses, it is
clearer that we think of twice as a function that takes one function and returns
another function.
**Exercise:** Generalize `twice` to a function `n_times f n x` that
applies `f` to `x` a total of `n` times. That is,
* `n_times f 0 x` yields `x`
* `n_times f 1 x` yields `f x`
* `n_times f 2 x` yields `f (f x)` (which is the same as `twice f x`)
* `n_times f 3 x` yields `f (f (f x))`
* ...
It turns out there's an even better way to use `twice` to define
functions like `quad` and `fourth`:
```
let quad = twice double
let fourth = twice square
```
**Exercise:** give a function of type `(int -> int) -> int`
**Exercise:** Type that final definition of `quad` and `fourth` into `func.ml`, then
`#use` it to see what `utop` says their types are. Explain how it can be that
`quad` is not syntactically written as a function that takes an argument,
and yet its type shows that it is in fact a function.
**Exercise:** what does `twice twice (add 10)` do?
## Labeled and optional arguments
Usually the type and name of a function give you a pretty good idea of what the
arguments should be. However, for functions with many arguments (especially
arguments of the same type), it can be useful to label them. For example, you
might guess that the function `String.sub` returns a substring of the given string
(and you would be correct). You could type in `String.sub` to find its type:
utop # String.sub;;
- : string -> int -> int -> string
But it's not clear from the type how to use it—you're forced to consult the
documentation.
OCaml supports labeled arguments to functions. You can declare this
kind of function using the following syntax:
utop # let f ~name1:arg1 ~name2:arg2 = arg1 + arg2;;
val f : name1:int -> name2:int -> int =
This function can be called by passing the labeled arguments in either order:
f ~name2:3 ~name1:4;;
Labels for arguments are often the same as the variable names for them. OCaml
provides a shorthand for this case. The following are equivalent:
let f ~name1:name2 ~name2:name2 = name1+name2
let f ~name1 ~name2 = name1 + name2
Use of labeled arguments is a largely matter of taste: they convey extra
information, but they can also add clutter to types. The OCaml standard library
provides labeled versions of some of the functions in the `StdLabels` module:
utop # StdLabels.String.sub;;
- : string -> pos:int -> len:int -> string =
**Exercise:** write a function `divide : numerator:float -> denominator:float
-> float`. Call your function.
It is also possible to make some arguments optional: when called without the
argument, a default value will be provided. To declare such a function, use the
following syntax:
utop # let f ?name:(arg1=8) arg2 = arg1 + arg2;;
val f : ?name:int -> int -> int =
You can then call a function with or without the argument:
utop # f ~name:2 7;;
- : int = 9
utop # f 7;;
- : int = 15
## Part 3: Programming exercises
### Reverse an integer
Write a function `rev_int : int -> int` that takes an
integer `i` and returns an integer whose digits are
the reverse of `i`. The sign should remain unchanged.
If the reversed integer is larger than `max_int`,
the behavior is unspecified: your function can
do whatever you want. For example:
* `rev_int 1234 = 4321`
* `rev_int 4 = 4`
* `rev_int (-1234) = (-4321)`
* `rev_int (-10) = (-1)`
* `rev_int 1073741822 = (* undefined: 2281473701 > max_int *)`
Hints: Use the `/`, `*`, and `mod` operators. Use recursion.
Define helper functions as necessary.
## Reverse an integer in an arbitrary base
Modify your `rev_int` to compute the reverse in an arbitrary base (with default
10). It should have the type
rev_base : ?base:int -> int -> int
Redefine rev_int using rev_base. Your answer should fit into 32 characters:
+---------------------------------+
| let rev_int |
+---------------------------------+
You can use `printf` to print out integers in base 8 (octal) or base 16
(hexadecimal) for testing:
utop# let x = 39;;
utop# Printf.printf "%o\n" x;; (* %o for octal, \n for newline *)
47
utop# Printf.printf "%o\n" (rev_int ~base:8 x);;
74
utop# Printf.printf "%d\n" x;; (* %d for decimal *)
39
utop# Printf.printf "%d\n" (rev_int ~base:10 x);;
93
utop# Printf.printf "%x\n" x;; (* %x for hexadecimal *)
27
utop# Printf.printf "%x\n" (rev_int ~base:16 x);;
72
`Printf.printf` is a very general printing mechanism; we'll discuss it further
next time.