Week 2 tutorial programming exercises: Thinking like OCaml

Author:Bram Geron
Description:These exercises are to assist in the programming remedial tutorials.
Subsite home page:
 http://bit.ly/focs-aux

You will receive this sheet with the questions; all the answers are on the indicated URL (but collapsed).

You can also find the answer by opening utop or ocaml, and I highly recommend to install utop.

Try it: enter 3 + 4 ;; and verify that the result is 7.

Syntax and precedence

The basic elements of OCaml are:

Variables

These are “names”. Examples:

x, f, g, three, double, twice

OCaml can remember a meaning for variables if you use let (see below).

Constants

Examples of integer constants:

42, -3
Arithmetic

Nothing surprising.

3 + 4
4 * 5

Like in school, you can write complex expressions, such as

3 + 4 * 5

Like in school, this means:

3 + (4 * 5)
Defining variables
let x = 3;;

let three = 1 + 2;;

From now on, OCaml knows that three + three = 3 + 3 = 6.

When you define a variable like this, it stays until you redefine it.

Let..in..

You can also “temporarily” define a variable.

For instance, let’s say that x is not yet defined. Then

let x = 3 in 3

evaluates to 3, and

let x = 3 in x + 3

evaluates to 6.

You should always add the right bracket as far to the right as possible.

Exercise. Add the right brackets here.

(answer goes here)
let x = 3 in (x + 3)

You can temporarily define multiple variables; this is nothing special. Example:

let x = 3 in let y = 4 in x + y

Now let’s add parentheses:

(answer goes here)
let x = 3 in (let y = 4 in (x + y))

You can combine multiple let..in.. in a different way. Parenthesise:

let x = let y = 4 in y in x

Exercise. Add parentheses. There is only one way that you can add parentheses, all other ways are invalid OCaml.

Exercise. Can you see why all other parenthesisations are invalid?

(answer goes here)
let x = (let y = 4 in y) in x

Let-bindings, variables, evaluation

To evaluate let variable = expression1 in expression2:

  1. Try to simplify (evaluate) expression1 as far as you can.
  2. Draw a big box around expression2
  3. In the right-hand corner of it, write variable = simplifiedexpression1.
  4. Erase let variable = ....
  5. Continue working in

To evaluate a variable x:

  1. Find the innermost box that is annotated with x = value
  2. Replace x where you wanted to evaluate it with value.

When you have a number (in general, a value) in the innermost box, then you can erase all the boxes.

Exercise. Evaluate all the expressions from the last section.

Exercises

Calculate by hand the value of the expressions below, or say that it returns an error. Use the method above.

OCaml keywords are printed in bold. Bold does not mean anything, but might make the code easier to read.

  1. Evaluate all expressions in the previous section.

  2. .

    let x = 3 in (let y = 4 in (x + y))
    (answer goes here)

  3. We can use multiple let..in.. in a different way.

    let x = let y = 3 in 2 * y in 2 * x

    First, add the right parentheses.

    Then, compute the result.

    (answer goes here)

    Before we draw any boxes, we simplify let y = 3 in 2 * y. Draw a box with y = 3, fill in y, simplify to 6.

    Then you can draw a box with x = 6. Fill in x, simplify to 12.

  4. Parenthesise, then solve.

    let x = let y = 5 in 3 in let y = 4 in x * y
    (answer goes here)
    • Simplify the x = part. Inside it, replace let y = 5 in with a bubble. Simplifying 3 is finished, so erase the bubble again.
    • We now have let x = 3 in. Draw a bubble for it.
    • We now have let y = 4 in. Draw a bubble for it.
    • Replace x by 3 and y by 4.
    • Simplify 3 * 4 to 12.

    If you try it in utop, you will get a warning that you have an unused variable. This is okay.

    Often, unused variables mean you are doing unnecessary computations. Indeed, we did let y = 5 in but it was useless.

  5. Parenthesise, then solve.

    let x = let y = 5 in 3 in y
    (answer goes here)
    • Simplify the x = part as in the previous exercise. You now have let x = 3 in y.
    • Make a bubble with x = 3 in the corner.
    • y is undefined, so ERROR.

  6. Parenthesise, then solve.

    let x = 2 in let x = x + 1 in x
    (answer goes here)

    Answer: 3.

  7. Parenthesise, then solve.

    let x = 2 in let y = x + 1 in y * let y = y + 1 in y
    (answer goes here)
    let x = 2 in (let y = (x + 1) in y * (let y = y + 1 in y))
    • Draw a bubble with x = 2.
    • Replace x in x + 1 with 2, simplify 2+1 to 3.
    • Draw a bubble with y = 3
    • Replace y in y + 1 with 3, simplify 3+1 to 4.
    • Replace inner y with 4.
    • Erase bubble
    • Replace y with 3.
    • Simplify 3 * 4 = 12

Exercise. If time: make an expression for your neighbour with between 2 and 4 uses of let..in... Solve it yourself, let them solve it, and compare your answers.

Anonymous functions

Anonymous functions (or lambdas) are integral to programming.

They look like this:

fun x -> x + 3

Also very important is function application. For instance,

(fun x -> x + 3) 4

The parentheses always go as far to the right as possible:

fun x -> (x + 3)

for the first example, and for the second example

(fun x -> (x + 3)) 4

Be careful! Space is not just space separating two things, but it has meaning. Space is called application, and you have to simplify when you can.

Application works the same as let..in.. . Draw a bubble with x = 4, and evaluate x + 3. The value of (fun x -> (x + 3)) 4 is 7.

Exercises

  1. Parenthesise and evaluate.

    (fun x -> 2 * x) 3
    (answer goes here)

    Answer: 6.

  2. Parenthesise and evaluate.

    (fun x -> 2 * x) 3 + (fun x -> x + 1) 3

    Note that you will have multiple bubbles here.

    (answer goes here)

    Answer: 10.

  3. Evaluate.

    2 + (fun whatever -> whatever * whatever) 10
    (answer goes here)

    Answer: 102.

Higher-order functions

Putting functions in the environment (“in the bubble”) is nothing special.

Exercises

  1. Parenthesise and evaluate. Add parentheses when you need to.

    let f = (fun x -> x * 2) in f 3
    (answer goes here)

    • Make a bubble, write f = fun x -> x * 2 in the corner of it.

    • Replace f by (fun x -> x * 2) (add parentheses!)

      Now you have (fun x -> x * 2) 3

    • Make a bubble with x = 3

    • Simplify x * 2 to 6.

  2. Parenthesise and evaluate.

    let f = (fun x -> x * 2) in f (f 3)
    (answer goes here)

    Same, but you have to replace f twice, and you get an application twice. The result is 12.

Named functions

Instead of

let f = (fun x -> x * 2) in f 3

we can write

let f x = x * 2 in f 3

which means exactly the same. When you draw the bubble, write

f = fun x -> x * 2

in the bubble.

Exercises

  1. Parenthesise and evaluate. Add parentheses when you need to.

    let f x = x * 2 in f 3
    (answer goes here)

    As before.

    • Make a bubble, write f = fun x -> x * 2 in the corner of it.

    • Replace f by (fun x -> x * 2) (add parentheses!)

      Now you have (fun x -> x * 2) 3

    • Make a bubble with x = 3

    • Simplify x * 2 to 6.

  2. Parenthesise and evaluate.

    let f x = x * 2 in f (f 3)
    (answer goes here)

    Same, but you have to replace f twice, and you get an application twice. The result is 12.

  3. Parenthesise and evaluate.

    let f x = x * 2 in f x
    (answer goes here)
    • Draw the bubble with f = fun x -> x * 2.
    • x is not in a bubble, so we cannot simplify it. Error!

  4. Evaluate.

    let f x = 3 * x in let g x = 3 + x in f (g 4)
    (answer goes here)

    21

    This was from the lecture: http://bit.ly/focs04a

  5. Evaluate.

    let f x = x + x in let g h = h (h 1) in g f
    (answer goes here)

    The exercise is easier when we rename the variables:

    let double x = x + x in
let apply_twice_to_one h = h (h 1) in
apply_twice_to_one double

    The answer is 4:

    • Write a bubble f = fun x -> x + x

    • Write a bubble g = fun h -> h (h 1)

    • Substitute g to get

      (fun h -> h (h 1)) f

      inside the two bubbles

    • Substitute f to get

      (fun h -> h (h 1)) (fun x -> x + x)

      inside the two bubbles

    • Write another bubble h = fun x -> x + x; inside it h (h 1)

    • Fill in h in the inside

    • In the brackets, make a bubble with let x = 1; the bubble contains x + x. Simplifies to 2. Remove the x bubble.

    • You have h 2 left. Make a bubble with x = 2 and x + x inside it. This simplifies to 4.

    • Remove the h bubble, the g bubble, and the f bubble.

    The answer is 4.

    This was from the lecture: http://bit.ly/focs04b

  6. Evaluate.

    let f g = g (g 1) in let h x = x + x in f h
    (answer goes here)

    The answer is the same as the previous exercise. I just renamed the variables and swapped the lets.

    Let’s do it in steps. First, I’ll lay out the code differently.

    let f g = g (g 1) in
let h x = x + x
in f h

    Then I’ll reorder the lets.

    let h x = x + x
let f g = g (g 1) in
in f h

    Then I’ll rename the variables.

    let f x = x + x
let g h = h (h 1) in
in g f

    Now the correspondence should be obvious.

    .

    You cannot always reorder the lets. Can you give an example?