## 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 `<tab>`. Delete that and type `Ra` and press `<tab>`. Delete that and type `Arr` and press `<tab>`. 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<tab> 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. <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> <br/> 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 = <fun> ``` 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 = <fun> ``` 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&mdash;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 = <fun> 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 = <fun> **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 = <fun> 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.