## 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 nth 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.