Sequencing in OCaml

Given an expression e1 of type unit and an expression e2 of type t, the compound expression, which has type t:

let () = e1
in e2

is syntactically sugared into the sequence expression, which also has type t:

e1; e2

Evaluating either expression requires first evaluating e1. If this evaluation completes, it yields a value of type unit. Evaluating either expression then reduces to evaluating e2.

<type> ::= ...
<expression> ::= ... | <expression> ; <expression>
SEQG |- e1 : unitG |- e2 : t
G |- e1; e2 : t

In words: in any type environment G, the expression e1; e2 has type t whenever in that environment, the expression e1 has type unit and the expression e2 has type t.

For example, the following two expressions have the type int:

let () = Printf.printf "Hello world!\n" in 33    (* <-- implicit sequencing *)

Printf.printf "Hello world!\n"; 33               (* <-- explicit sequencing *)

Evaluating either of them

  1. prints out Hello world! and issues a new line, and
  2. yields the integer 33.

To wit:

# let () = Printf.printf "Hello world!\n" in 33;;    (* <-- implicit sequencing *)
Hello world!
- : int = 33
# Printf.printf "Hello world!\n"; 33;;               (* <-- explicit sequencing *)
Hello world!
- : int = 33
#

The printf-expression is evaluated for its effect, since its result is not significant.

These two expressions mean the same (e.g., they are compiled to the same object code). The short hand ; for sequencing is more convenient in practice.

For a last example, here is again the example of the previous lecture note about references:

let r = ref 1               (* <-- creation of a reference *)
in let x = !r               (* <-- dereference *)
   in let () = r := 10 in   (* <-- mutation of the reference and implicit sequencing *)
      let y = !r            (* <-- dereference *)
      in x + y;;

This example can be equivalently written using the short-hand notation for sequencing:

let r = ref 1       (* <-- creation of a reference *)
in let x = !r       (* <-- dereference *)
   in r := 10;      (* <-- mutation of the reference and explicit sequencing *)
      let y = !r    (* <-- dereference *)
      in x + y;;

Likewise, functions that emit traces can be written using the short-hand notation for sequencing Printf.printf ...; blah instead of the long-hand notation let () = Printf.printf ... in blah.

Sequencing in retrospect

So every time we want to restrict a function to only operate on non-negative number and write:

let fac n_given =
  let () = assert (n_given >= 0) in    (* <-- implicit sequencing *)
  let rec visit n =
    if n = 0
    then 1
    else n * visit (pred n)
  in visit n_given;;

we can write:

let fac n_given =
  assert (n_given >= 0);    (* <-- explicit sequencing *)
  let rec visit n =
    if n = 0
    then 1
    else n * visit (pred n)
  in visit n_given;;

Ditto for tracing functions. Rather than writing:

let traced_fac n =
  let rec visit n i =
    let () = Printf.printf "%svisit %s ->\n" (indent i) (show_int n) in    (* <-- implicit sequencing *)
    let result = (if n = 0
                  then 1
                  else n * (visit (pred n) (succ i)))
    in let () = Printf.printf "%svisit %s <- %s\n" (indent i) (show_int n) (show_int result) in    (* <-- implicit sequencing *)
       result
  in visit n 0;;

we can write:

let traced_fac' n =
  let rec visit n i =
    Printf.printf "%svisit %s ->\n" (indent i) (show_int n);    (* <-- explicit sequencing *)
    let result = (if n = 0
                  then 1
                  else n * (visit (pred n) (succ i)))
    in Printf.printf "%svisit %s <- %s\n" (indent i) (show_int n) (show_int result);    (* <-- explicit sequencing *)
       result
  in visit n 0;;

And ditto for The imperative simulation of String.mapi in terms of String.map. Rather than writing:

let string_mapi f s =
  let i = ref ~-1
  in String.map (fun c ->
                  let () = i := succ !i in    (* <-- implicit sequencing *)
                  f !i c)
                s

we can write:

let string_mapi f s =
  let i = ref ~-1
  in String.map (fun c ->
                  i := succ !i;    (* <-- explicit sequencing *)
                  f !i c)
                s

On the associativity of sequencing

Is sequencing associative?

For any expressions e1, e2, and e3,

  • evaluating e1; (e2; e3) proceeds as evaluating let () = e1 in (let () = e2 in e3), i.e., let () = e1 in let () = e2 in e3, which requires first evaluating e1; if this evaluation completes, it yields the unit value and evaluating e1; (e2; e3) reduces to evaluating (e2; e3), i.e., e2; e3;

    evaluating e2; e3, i.e., let () = e2 in e3 requires first evaluating e2; if this evaluation completes, it yields the unit value and evaluating e2; e3 reduces to evaluating e3;

  • evaluating (e1; e2); e3 proceeds as evaluating let () = let () = e1 in e2 in e3, which requires first evaluating e1; e2, i.e., let () = e1 in e2;

    evaluating e1; e2 requires first evaluating e1; if this evaluation completes, it yields the unit value and evaluating e1; e2 reduces to evaluating e2;

    if evaluating e2 completes, it yields the unit value and evaluating (e1; e2); e3 reduces to evaluating e3.

To sum up, in both cases,

  1. e1 is evaluated; if this evaluation completes,
  2. e2 is evaluated; if this evaluation completes,
  3. e3 is evaluated,

in that order. So if computational effects take place (from tracing to raising an error to diverging), they do in the same order. If the two first evaluations complete, they give rise to the unit value, and evaluating either expression reduces to evaluating e3.

Therefore yes, the expressions e1; (e2; e3) and (e1; e2); e3 are observationally equivalent: sequencing is associative in OCaml, which is why compilers can flatten sequences of instructions.

So for example:

# Printf.printf "hello"; (Printf.printf " "; (Printf.printf "world\n"; 33));;
hello world
- : int = 33
# ((Printf.printf "hello"; Printf.printf " "); Printf.printf "world\n"); 33;;
hello world
- : int = 33
#

In practice, just like for addition and multiplication, the parentheses are redundant and so they are omitted:

# Printf.printf "hello"; Printf.printf " "; Printf.printf "world\n"; 33;;
hello world
- : int = 33
#

Exercise 02

Is sequencing commutative?

Solution for Exercise 02

Alfrothul: No it isn’t in general.

Anton: Well, right. If something happens, and then something else, most of the time the result is not the same as vice versa.

Pablito: But if I turn left, and then right, or right, and then left, I do get to the same place in a taxicab geometry.

Anton: True enough, but we are talking sequencing in programming, where side effects can take place.

Alfrothul: For example, incrementing a variable by 1 and then multiplying it by 2 doesn’t give the same result as multiplying it by 2 and then incrementing it by 1.

Pablito: But that’s because the functions fun x -> 2 * (x + 1) and fun x -> (2 * x) + 1 are not equivalent.

Anton: Right. But the issue here is imperative. Look:

# let x = ref 1 and y = ref 10 in x := !x + !y; y := !x + !y; (!x, !y);;
- : int * int = (11, 21)
# let x = ref 1 and y = ref 10 in y := !x + !y; x := !x + !y; (!x, !y);;
- : int * int = (12, 11)
#

Pablito: Ah, your point is that the two expressions x := !x + !y; y := !x + !y and y := !x + !y; x := !x + !y are not observationally equivalent.

Anton: Precisely, since each occurrence of !x + !y accesses both references in reading, and each assignment accesses one of these references in writing.

Alfrothul: Sequentializing computations in the presence of side effects is not easy at all.

Pablito: You said that sequencing is not commutative in general?

Alfrothul: Well, yes, that was the point of the example just above.

Pablito: Are there examples where sequencing is commutative?

Alfrothul: Actually yes, when the effects (read or write) are independent of each other. Look:

# let x = ref 1 and y = ref 10 in x := !x + 1; y := !y + 1; (!x, !y);;
- : int * int = (2, 11)
# let x = ref 1 and y = ref 10 in y := !y + 1; x := !x + 1; (!x, !y);;
- : int * int = (2, 11)
#

Anton: The commands x := !x + 1 and y := !y + 1 are independent.

Alfrothul: They could be executed in parallel.

More syntactic sugar: begin and end

The keywords begin and end can be used instead of parentheses to delimit a sequence of OCaml commands, i.e., of expressions of type unit -> unit:

# begin Printf.printf "hello "; Printf.printf "world\n" end;;
hello world
- : unit = ()
#

They make it more patent that what lies in between is a sequence of commands.

Sequencing, iteratively: for-loops

With sequence and side effects, we now stand in imperative-programming land, and so instead of simulating, e.g., for-loops, we can use OCaml’s syntactic sugar for them:

<expression> ::= ... | for <name> = <expression> to <expression> do <expression> done | for <name> = <expression> downto <expression> do <expression> done

The corresponding typing rule reads as follows:

FORUPG |- e1 : intG |- e2 : int(x : int), G |- e0 : unit
G |- for x = e1 to e2 do e0 done : unit
FORDOWNG |- e1 : intG |- e2 : int(x : int), G |- e0 : unit
G |- for x = e1 downto e2 do e0 done : unit

In words,

  • in any type environment G, the expressions for x = e1 to e2 do e0 done and for x = e1 downto e2 do e0 done have type unit whenever (1) in that environment, the expression e1 and the expression e2 have type int and (2) the expression e0 has type unit in an extension of that environment where the name x has type int.

Furthermore,

  • to evaluate for x = e1 to e2 do e0 done,

    • we first evaluate e1 (which gives the integer n1, assuming that this evaluation completes);
    • we then evaluate e2 (which gives the integer n2, assuming that this evaluation completes);

    if n1 > n2, the result of evaluating for x = e1 to e2 do e0 done is the unit value;

    otherwise, e0 is evaluated n2 - n1 + 1 times, each of them yielding the unit value, assuming that each evaluation completes:

    • the first time, e0 is evaluated in an environment where x denotes n1;
    • the second time, e0 is evaluated in an environment where x denotes n1+1;
    • the third time, e0 is evaluated in an environment where x denotes n1+2;
    • ...
    • and the last time, e0 is evaluated in an environment where x denotes n2;

    the result of evaluating for x = e1 downto e2 do e0 done is then the unit value.

  • to evaluate for x = e1 downto e2 do e0 done,

    • we first evaluate e1 (which gives the integer n1, assuming that this evaluation completes);
    • we then evaluate e2 (which gives the integer n2, assuming that this evaluation completes);

    if n1 < n2, the result of evaluating for x = e1 downto e2 do e0 done is the unit value;

    otherwise, e0 is evaluated n1 - n2 + 1 times, each of them yielding the unit value, assuming that each evaluation completes:

    • the first time, e0 is evaluated in an environment where x denotes n1;
    • the second time, e0 is evaluated in an environment where x denotes n1-1;
    • the third time, e0 is evaluated in an environment where x denotes n1-2;
    • etc.
    • and the last time, e0 is evaluated in an environment where x denotes n2;

    the result of evaluating for x = e1 downto e2 do e0 done is then the unit value.

Vocabulary:

  • a for-loop is also referred to as a for-expression;
  • x and e0 are often referred to as the index and the body of for x = e1 to e2 do e0 done as well as of for x = e1 downto e2 do e0 done, respectively.

Here are four telling examples, where the index of the loop is not used in its body (which is akin to primitive iteration):

# for i = 1 to 3 do Printf.printf "testing\n" done;;
testing
testing
testing
- : unit = ()
# for i = 3 to 1 do Printf.printf "testing\n" done;;
- : unit = ()
# for i = 3 downto 1 do Printf.printf "testing\n" done;;
testing
testing
testing
- : unit = ()
# for i = 1 downto 3 do Printf.printf "testing\n" done;;
- : unit = ()
#
Pablito (reflectively): Wow. Exercise 01 in Week 05 really was salient.

In this interaction,

  1. Printf.printf "testing\n" is evaluated for each of the increasing integers between 1 and 3, inclusively, i.e., three times, and the result is the unit value;
  2. Printf.printf "testing\n" is evaluated for each of the increasing integers between 3 and 1, inclusively, i.e., zero times since there isn’t any increasing integer between 3 and 1, and the result is the unit value;
  3. Printf.printf "testing\n" is evaluated for each of the decreasing integers between 3 and 1, inclusively, i.e., three times, and the result is the unit value;
  4. Printf.printf "testing\n" is evaluated for each of the decreasing integers between 1 and 3, inclusively, i.e., zero times since there isn’t any decreasing integer between 1 and 3, and the result is the unit value.

Here are four more telling examples, where the index of the loop is used in its body (which is akin to primitive recursion):

# for i = 1 to 3 do Printf.printf "testing %d\n" i done;;
testing 1
testing 2
testing 3
- : unit = ()
# for i = 3 to 1 do Printf.printf "testing %d\n" i done;;
- : unit = ()
# for i = 3 downto 1 do Printf.printf "testing %d\n" i done;;
testing 3
testing 2
testing 1
- : unit = ()
# for i = 1 downto 3 do Printf.printf "testing %d\n" i done;;
- : unit = ()
#

In this interaction,

  1. Printf.printf "testing %d\n" 1, and then Printf.printf "testing %d\n" 2, and then Printf.printf "testing %d\n" 3 are evaluated, and the result is the unit value;
  2. the body of the for-loop is not evaluated since there isn’t any increasing integer between 3 and 1, and the result is the unit value;
  3. Printf.printf "testing %d\n" 3, and then Printf.printf "testing %d\n" 2, and then Printf.printf "testing %d\n" 1 are evaluated, and the result is the unit value;
  4. the body of the for-loop is not evaluated since there isn’t any decreasing integer between 1 and 3, and the result is the unit value.

To implement for-loops in OCaml, we Church-encode the index, i.e., we make it an argument of a function whose body is the body of the for-loop:

let up_for i j f =
  if i > j
  then ()
  else let rec loop n =
         if n = j
         then f n
         else begin
                f n;
                loop (succ n)
              end
       in loop i;;

let down_for i j f =
  if i < j
  then ()
  else let rec loop n =
         if n = j
         then f n
         else begin
                f n;
                loop (pred n)
              end
       in loop i;;

To wit, let us revisit the first batch of examples, where the index of the for-loop is not used in the body of the loop:

# up_for 1 3 (fun i -> Printf.printf "testing\n");;
testing
testing
testing
- : unit = ()
# up_for 3 1 (fun i -> Printf.printf "testing\n");;
- : unit = ()
# down_for 3 1 (fun i -> Printf.printf "testing\n");;
testing
testing
testing
- : unit = ()
# down_for 1 3 (fun i -> Printf.printf "testing\n");;
- : unit = ()
#

In this interaction,

  1. fun i -> Printf.printf "testing\n" is successively applied to 1, 2, and 3;
  2. fun i -> Printf.printf "testing\n" is not applied at all;
  3. fun i -> Printf.printf "testing\n" is successively applied to 3, 2, and 1;
  4. fun i -> Printf.printf "testing\n" is not applied at all.

And likewise, let us revisit the second batch of examples, where the index of the for-loop is used in the body of the loop:

# up_for 1 3 (fun i -> Printf.printf "testing %d\n" i);;
testing 1
testing 2
testing 3
- : unit = ()
# up_for 3 1 (fun i -> Printf.printf "testing %d\n" i);;
- : unit = ()
# down_for 3 1 (fun i -> Printf.printf "testing %d\n" i);;
testing 3
testing 2
testing 1
- : unit = ()
# down_for 1 3 (fun i -> Printf.printf "testing %d\n" i);;
- : unit = ()
#

The implementation of up_for and down_for are properly tail-recursive in that the last iteration is implemented with a tail call. Let us illustrate this point first with up_for and then with down_for:

# let rec test () = for i = 1 to 1 do test () done in test ();;
Stack overflow during evaluation (looping recursion?).
# let rec test () = up_for 1 1 (fun i -> test ()) in test ();;

Exercise 03

We are given:

let char_print c =
  Printf.printf "%c" c;;
  1. Using a for-loop, implement a function of type string -> unit that, given a string, prints its characters using char_print:

    # string_print "abc";;
    abc
    - : unit = ()
    #
    
  2. Using a for-loop, implement a function of type string -> unit that, given a string, prints its characters in reverse order:

    # string_print_reverse "abc";;
    cba
    - : unit = ()
    #
    

Exercise 04

We are still given:

let char_print c =
  Printf.printf "%c" c;;
  1. Implement a function of type string -> unit that prints the successive prefixes of a string on successive lines, starting with the empty prefix and ending with the given string:

    # string_print_prefixes_up "abc";;
    
    a
    ab
    abc
    - : unit = ()
    #
    

    The successive prefixes should be left-aligned.

  2. Implement a function of type string -> unit that prints the prefixes of a string on successive lines, starting with the given string and ending with the empty prefix:

    # string_print_prefixes_down "abc";;
    abc
    ab
    a
    
    - : unit = ()
    #
    

    The prefixes should be left-aligned.

  3. Implement a function of type string -> unit that prints the successive suffixes of a string on successive lines, starting with the given string and ending with the empty suffix:

    # string_print_suffixes_up "abc";;
    abc
     bc
      c
    
    - : unit = ()
    #
    

    The successive suffixes should be right-aligned.

  4. Implement a function of type string -> unit that prints the suffixes of a string on successive lines, starting with the empty suffix and ending with the given string:

    # string_print_suffixes_down "abc";;
    
      c
     bc
    abc
    - : unit = ()
    #
    

    The suffixes should be right-aligned.

Exercise 05

Implement an OCaml function that maps a given string to the corresponding list of characters:

let test_chars_of_string candidate =
  let b0 = (candidate ""     = [])
  and b1 = (candidate "0"    = ['0'])
  and b2 = (candidate "01"   = ['0'; '1'])
  and b3 = (candidate "012"  = ['0'; '1'; '2'])
  and b4 = (candidate "abcd" = ['a'; 'b'; 'c'; 'd'])
  in b0 && b1 && b2 && b3 && b4;;

Functional solution for Exercise 05

The following implementation traverses the string from right to left, starting from the empty list and accumulating one character onto another to construct the resulting list:

let fun_chars_of_strings s =
  let rec loop n a =
    if n = 0
    then a
    else let n' = pred n
         in loop n' (s.[n'] :: a)
  in loop (String.length s) [];;

This implementation is a fit for nat_parafold_left:

let nat_parafold_left zero_case succ_case n =
  let () = assert (n >= 0) in
  let rec loop i a =
    if i = 0
    then a
    else let i' = pred i
         in loop i' (succ_case i a)
  in loop n zero_case;;

let fun_chars_of_strings_alt s =
  nat_parafold_left
    []
    (fun i a ->
      s.[i] :: a)
    (String.length s);;

Imperative solution for Exercise 05

In the functional solution just above, loop has type int -> char list -> char list: it “threads” the accumulator in that given one, it returns a new one. (Technically, applying loop to an integer yields an endofunction: a function whose domain is also its co-domain. Here this function is an accumulator transformer.) Imagine that we want loop to have type int -> unit and do the same job. The accumulator would then need to become implicit:

  • it would be read when loop is being applied instead of being passed as an argument, and
  • it would then be overwritten when loop is applied instead of being returned as a result.

The accumulator would then be referred to in the lexical environment of loop, and this reference would be mutable. Concretely:

let imp_chars_of_strings s =
  let a = ref []
  in let rec loop n =
       if n = 0
        then ()
        else let n' = pred n
             in begin
                  a := s.[n'] :: !a;
                  loop n'
                end
  in begin
       loop (String.length s);
       !a
     end;;

This solution can be made “for-ready”, by making loop iterate from the last index of the given string down to its first and stop when the index becomes out of bounds:

let massaged_imp_chars_of_strings s =
  let a = ref []
  in begin
       let rec loop n =
         if n < 0
         then ()
         else begin
                a := s.[n] :: !a;
                loop (pred n)
              end
       in loop (String.length s - 1);
       !a
     end;;

This massaged version can be syntactically sugared with a for-loop, as in the following alternative solution.

Imperative solution for Exercise 05, with a for-loop

The following implementation traverses the string from right to left, accumulating one character onto another to construct the resulting list. To this end, a for-loop with decreasing indices is used. Its body side-effects a reference that holds the list under construction:

let for_chars_of_strings s =
  let a = ref []
  in begin
      for n = String.length s - 1 downto 0 do
        a := s.[n] :: !a
      done;
      !a
    end;;

Exercise 06

Re-implement up_for using nat_parafold_right and then using nat_parafold_left. The following unit tests should be satisfied:

# up_for_pararight 1 3 (fun i -> Printf.printf "%d\n" i);;
1
2
3
- : unit = ()
# up_for_pararight 3 1 (fun i -> Printf.printf "%d\n" i);;
- : unit = ()
# up_for_paraleft 1 3 (fun i -> Printf.printf "%d\n" i);;
1
2
3
- : unit = ()
# up_for_paraleft 3 1 (fun i -> Printf.printf "%d\n" i);;
- : unit = ()
#

Subsidiary questions:

  1. Is up_for_pararight iterative? In other words, does evaluating, e.g., up_for_pararight 1 1000000 (fun i -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  2. Is up_for_paraleft iterative? In other words, does evaluating, e.g., up_for_paraleft 1 1000000 (fun i -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  3. What about the proper tail recursion mentioned just before Exercise 05? Are your implementations of up_for_pararight and of up_for_paraleft properly tail recursive?

Exercise 07

Re-implement down_for using nat_parafold_right and then using nat_parafold_left. The following unit tests should be satisfied:

# down_for_pararight 3 1 (fun i -> Printf.printf "%d\n" i);;
3
2
1
- : unit = ()
# down_for_pararight 1 3 (fun i -> Printf.printf "%d\n" i);;
- : unit = ()
# down_for_paraleft 3 1 (fun i -> Printf.printf "%d\n" i);;
3
2
1
- : unit = ()
# down_for_paraleft 1 3 (fun i -> Printf.printf "%d\n" i);;
- : unit = ()
#

Subsidiary questions:

  1. Is down_for_pararight iterative? In other words, does evaluating, e.g., down_for_pararight 1 1000000 (fun i -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  2. Is down_for_paraleft iterative? In other words, does evaluating, e.g., down_for_paraleft 1 1000000 (fun i -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  3. What about the proper tail recursion mentioned just before Exercise 05? Are your implementations of down_for_pararight and of down_for_paraleft properly tail recursive?

Exercise 08

In the particular case where the body of the for-loop does not use the index of the loop, re-implement up_for using nat_fold_right and then using nat_fold_left. The following unit tests should be satisfied:

# up_for_right 1 3 (fun () -> Printf.printf "hello\n");;
hello
hello
hello
- : unit = ()
# up_for_right 3 1 (fun () -> Printf.printf "hello\n");;
- : unit = ()
# up_for_left 1 3 (fun () -> Printf.printf "hello\n");;
hello
hello
hello
- : unit = ()
# up_for_left 3 1 (fun () -> Printf.printf "hello\n");;
- : unit = ()
#

Subsidiary questions:

  1. Is up_for_right iterative? In other words, does evaluating, e.g., up_for_right 1 1000000 (fun () -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  2. Is up_for_left iterative? In other words, does evaluating, e.g., up_for_left 1 1000000 (fun () -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  3. What about the proper tail recursion mentioned just before Exercise 05? Are your implementations of up_for_right and of up_for_left properly tail recursive?

Exercise 09

In the particular case where the body of the for-loop does not use the index of the loop, re-implement down_for using nat_fold_right and then nat_fold_left. The following unit tests should be satisfied:

# down_for_right 3 1 (fun () -> Printf.printf "hello\n");;
3
2
1
- : unit = ()
# down_for_right 1 3 (fun () -> Printf.printf "hello\n");;
- : unit = ()
# down_for_left 3 1 (fun () -> Printf.printf "hello\n");;
3
2
1
- : unit = ()
# down_for_left 1 3 (fun () -> Printf.printf "hello\n");;
- : unit = ()
#

Subsidiary questions:

  1. Is down_for_right iterative? In other words, does evaluating, e.g., down_for_right 1 1000000 (fun i -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  2. Is down_for_left iterative? In other words, does evaluating, e.g., down_for_left 1 1000000 (fun i -> ()) yield the unit value, or does it make OCaml’s stack overflow? Why is that?
  3. What about the proper tail recursion mentioned just before Exercise 05? Are your implementations of down_for_right and of down_for_left properly tail recursive?

Exercise 10

In the light of Exercise 06, Exercise 07, Exercise 08, and Exercise 09, what can be concluded about the relation between for-loops that use their index, for-loops that do not use their index, primitive iteration (i.e., nat-fold functions), and primitive recursion (i.e., nat-parafold functions)?

Exercise 11

It is generally a good idea to repeat tests over random input. To this end, implement a repeat loop as an OCaml function of type int -> (unit -> unit) -> unit that is such that:

  • repeat (-1) t and () are observationally equivalent;
  • repeat 0 t and () are observationally equivalent;
  • repeat 1 t and t () are observationally equivalent;
  • repeat 2 t and begin t (); t () end are observationally equivalent;
  • repeat 3 t and begin t (); t (); t () end are observationally equivalent;
  • etc.

Be imaginative: provide implementations that use for-loops and others that are (tail-)recursive. Also, the more pilfering in the up_for and down_for menagerie, the better.

As per what is mentioned just before Exercise 03, are your implementations properly tail recursive?

Sequencing, iteratively: while-loops

As stated above, with sequence and side effects, we now stand in imperative-programming land, and so instead of simulating, e.g., while-loops, we can use OCaml’s syntactic sugar for them:

<expression> ::= ... | while <expression> do <expression> done

The corresponding typing rule reads as follows:

WHILEG |- e1 : boolG |- e0 : unit
G |- while e1 do e0 done : unit

In words,

  • In any type environment G, the expression while e1 do e0 done have type unit whenever (1) the expression e1 has type bool in that environment and (2) the expression e0 has type unit in that environment.

Furthermore,

  • to evaluate while e1 do e0 done, we first evaluate e1:
    • if e1 evaluates to false, the result of evaluating while e1 do e0 done is the unit value;
    • if e1 evaluating to true, e0 is evaluated;
      • if this evaluation completes, we then evaluate e1 and iterate.

Vocabulary:

  • a while-loop is also referred to as a while-expression;
  • in while e1 do e0 done, e1 is referred to as the test and e0 as the body of the while-loop, respectively.

We are now in position to express in OCaml the imperative implementation of the imperative Factorial program in Week 02. To quote:

For a more computational example, imagine a program that works over two memory locations. The first one (call it x) is initialized with 5, and the second (call it a) with 1. The program repeatedly checks whether the content of x is 0, and stops if it is so, with a containing the result. Otherwise, the program multiplies the content of x by the content of a and stores the result at location a, it decrements the content of x, and it iterates.

To code:

let imp_fac n =
  let x = ref n and a = ref 1
  in begin
       while !x <> 0 do
         a := !x * !a;
         x := pred !x
       done;
       !a
     end;;

To wit:

# test_fac imp_fac;;
- : bool = true
#
Pablito: To quote, to code, and to wit.
Halcyon: This is so cool!

A job interview

Dines Bjørner: Could you write a looping OCaml expression that does not terminate?

Loki: Certainly:

# while true do () done;;

Dines Bjørner: Thanks.

Loki: No problem:

  C-c C-cInterrupted.
#

Dines Bjørner: And could you write an OCaml expression that loops three times in a row?

Loki: Of course:

# while true do () done; while true do () done; while true do () done;;

Mimer: Prof. Bjørner! Thanks for looping by!

Dines Bjørner (modestly): Just the once, just the once.

The happy drunkard: Would you like some beer?

Exercise 12

Implement a mean OCaml function of type (unit -> bool) -> (unit -> unit) -> unit that simulates a while-loop so that imp_fac can be expressed as follows:

let imp_fac_alt n =
  let x = ref n and a = ref 1
  in begin
       meanwhile
         (fun () ->
            !x <> 0)
         (fun () ->
            begin
              a := !x * !a;
              x := pred !x
            end);
       !a
      end;;

Can you make your implementation of meanwhile properly tail-recursive, as per what is mentioned just before Exercise 05?

Exercise 13

Using a while-loop, implement a predicate that, given a string, tests whether this string is a palindrome.

Exercise 14

Implement an OCaml predicate deciding whether all the characters in a given string are distinct. This predicate should satisfy the following unit tests:

let test_string_all_distinct_characters candidate =
  let b0 = (candidate "" = true)
  and b1 = (candidate "a" = true)
  and b2 = (candidate "bc" = true)
  and b3 = (candidate "dd" = false)
  and b4 = (candidate "xyz" = true)
  and b5 = (candidate "Yale-NUS" = true)
  and b6 = (candidate "Yale-NUS College" = false)
  in b0 && b1 && b2

Exercise 15

Implement an OCaml function of type string -> int that, given a string of 9 characters containing distinct digits in any order, returns the integer represented by the missing digit. So for example, applying this function to "123456789" or to "987654321" should yield 0.

For simplicity, and beyond checking that the given string contains 9 characters, there is no need to test whether it is conformant, i.e., that it contains distinct digits.

Partial solution for Exercise 15

Pablito: Hey, that’s Exercise 19 in Week 06.

Bong-sun: Right. I think the point here is to implement a function that maps a string of digits to the sum of the integers represented by these digits using a local reference and a for-loop.

Pablito: How about we use an option type in the result to distinguish between conformant and non-conformant input strings?

Bong-sun: Good idea. <clickety clickety click>:

let test_missing_digit candidate =
  let b0 = (candidate "123456789" = Some 0)
  and b1 = (candidate "023456789" = Some 1)
  and b2 = (candidate "013456789" = Some 2)
  and b3 = (candidate "012456789" = Some 3)
  and b4 = (candidate "012356789" = Some 4)
  and b5 = (candidate "012346789" = Some 5)
  and b6 = (candidate "012345789" = Some 6)
  and b7 = (candidate "012345689" = Some 7)
  and b8 = (candidate "012345679" = Some 8)
  and b9 = (candidate "012345678" = Some 9)
  in b0 && b1 && b2 && b3 && b4 && b5 && b6 && b7 && b8 && b9;;

Pablito: Lemme see:

let missing_digit s =
  if String.length s <> 9
  then None
  else let n = string_sum_of_digits s
       in if 36 <= n && n <= 45
          then Some (45 - n)
          else None;;

Irene: Cool solution, guys!

Bong-sun: Thanks.

Halcyon: The point is that the sum of the 10 first natural numbers, 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9, is (9 * 10)/2 = 45.

Everybody claps their hands, including Mimer, but let’s not go there.

Halcyon: Er... Thanks. I guess?

Dana: This solution is completely tested.

Bong-sun: Right. The unit-test function enumerates all the possible strings, modulo the order of their characters.

Dana: But is it sound?

Bong-sun: Well, if it is given a string that does not contain 9 characters, it returns None, and if it is given a string that does not only contain digits, it raises an error.

Dana: Indeed. But what if the string contains 9 digits, but these digits are not all distinct? What happens then?

Bong-sun: Let’s see. Oh. One of the lower digits could be repeated, and then one of the upper digits could also be repeated, to compensate. For example:

# missing_digit "003345678";;
- : int option = Some 9
# missing_digit "002445678";;
- : int option = Some 9
# missing_digit "002355678";;
- : int option = Some 9
# missing_digit "002346678";;
- : int option = Some 9
# missing_digit "002345778";;
- : int option = Some 9
# missing_digit "002345688";;
- : int option = Some 9
#

Dana: Right. Or 0 could occur more than twice:

# missing_digit "000645678";;
- : int option = Some 9
# missing_digit "000009999";;
- : int option = Some 9
# missing_digit "000019999";;
- : int option = Some 8
# missing_digit "000029999";;
- : int option = Some 7
# missing_digit "000039999";;
- : int option = Some 6
# missing_digit "000099999";;
- : int option = Some 0
#

Mimer (coughing in his hand, though again let’s not go there): *Hashing*

Dana: Yes. There are lots of collisions here.

Bong-sun: Right. But only for non-conformant input strings. For conformant strings, testing is complete modulo the order of their characters, and therefore the implementation is correct.

Edsger W. Dijkstra: Yup.

Mimer: Prof. Dijkstra! Thanks for sticking around!

Resources

Version

Added the partial solution for Exercise 15 [12 Mar 2023]

Added the job interview [21 Jan 2023]

Created [03 Nov 2022]