Mini-project: The underlying determinism of OCaml

Warning

OCaml is a statically typed programming language, and so any OCaml expression has a type and is type-correct.

OCaml is a deterministic programming language in that it has a fixed processing order, and the goal of this mini-project is to become aware of this processing order.

To this end, here is a family of tracing identity functions:

let an_int n =
 (* an_int : int -> int *)
  let () = Printf.printf "processing %s...\n" (show_int n)
  in n;;

let a_bool b =
 (* a_bool : bool -> bool *)
  let () = Printf.printf "processing %s...\n" (show_bool b)
  in b;;

let a_char c =
 (* a_char : char -> char *)
  let () = Printf.printf "processing %s...\n" (show_char c)
  in c;;

let a_string s =
 (* a_string : string -> string *)
  let () = Printf.printf "processing %s...\n" (show_string s)
  in s;;

let a_unit () =
 (* a_unit : unit -> unit *)
  let () = Printf.printf "processing the unit value...\n"
  in ();;

let a_function f =
 (* a_function : ('a -> 'b) -> 'a -> 'b *)
  let () = Printf.printf "processing a function...\n"
  and _ = fun x -> f x
  in f;;

Resources

• The OCaml code for the present mini-project (latest version: 06 Mar 2020, with an updated definition of a_function).

Question 1

In an addition (+ in infix notation), are the operands (i.e., the arguments of +) evaluated from left to right or from right to left?

Answer to Question 1

Let’s try:

# an_int 1 + an_int 10;;
processing 10...
processing 1...
- : int = 11
#

Since the processing order of OCaml is fixed, this example is enough to conclude that the operands of an addition are evaluated from right to left. Not just for addition, but also for the other arithmetic operations:

# an_int 10 - an_int 1;;
processing 1...
processing 10...
- : int = 9
# an_int 5 * an_int 4;;
processing 4...
processing 5...
- : int = 20
# an_int 5 / an_int 0;;
processing 0...
processing 5...
Exception: Division_by_zero.
#

Incidentally, the last interaction illustrates that the operands are evaluated before the operation takes place.

Question 2

In a function application, are the two sub-expressions (namely the one in position of a function, on the left, and the one that is the actual parameter of the function, i.e., the argument, on the right) evaluated from left to right or from right to left?

Subsidiary question: is this order compatible with the answer to Question 1? Why?

Question 3

In a (local or global) let-expression declaring several bindings at once, i.e., with and, are the definienses evaluated from left to right or from right to left?

Food for thought

• When a tuple is constructed, in which order are its components evaluated?

• Given two expressions of type int, e1 and e2, how do the two following expressions compare:

  let x1 = e1 and x2 = e2 in x1 + x2;;
  
  let (x1, x2) = (e1, e2) in x1 + x2;;
  

Question 4

In a Boolean conjunction (&& in infix notation), are the conjuncts (i.e., the arguments of &&, of type bool) evaluated from left to right or from right to left?

To answer this question completely, make sure to consider the 4 possible cases.

Why does this design make sense?

Question 5

This question is a warmup for the following two questions. Implement an OCaml function that given 3 characters, yields a string containing these 3 characters. This implementation should pass the following unit test:

let test_warmup candidate =
  (candidate 'a' 'b' 'c' = "abc");;

Question 6

As described in the section about Mapping a character-to-character function pointwise over a string, in Week 06, the library function String.map takes two arguments: a given function mapping a character to a character, and a given string. It applies the given function to each character of the given string and returns a string where each character is the result of applying the given function to the corresponding character in the given string.

Obviously, String.map is implemented with a for-loop: for each of the characters of the given string, the given function is applied.

1. In which order are the characters accessed in the given string?
2. Using a recursive function that operates over a natural number, implement a left-to-right version of String.map. Your implementation will therefore simulate a for-loop that goes from the smallest index to the largest index in the string.
3. Using a recursive function that operates over a natural number, implement a right-to-left version of String.map. Your implementation will therefore simulate a for-loop that goes from the largest index to the smallest index in the string.

Yale N-U-S,

In the middle of the term

string_map_down

Intro to CS [in] germ

Got a disk, a pad, cranberries in a bag

Ain’t gonna cut OCaml no slack

—pastiche of Six Strings Down

Question 7

As described in the subsequent General interlude, still in Week 06, the library function String.mapi (alias Stringy.mapi) takes two arguments: a given function mapping an integer and character to a character, and a given string. It applies the given function to each character of the given string and its index in this string and returns a string where each character is the result of applying the given function to the corresponding index and the corresponding character in the given string.

Obviously, String.mapi is implemented with a for-loop: for each of the characters of the given string, the given function is applied to the current index of the for-loop and to the character at that index.

1. In which order are the characters accessed in the given string?
2. Using a recursive function that operates over a natural number, implement a left-to-right version of String.mapi. Your implementation will therefore simulate a for-loop that goes from the smallest index to the largest index in the string.
3. Using a recursive function that operates over a natural number, implement a right-to-left version of String.mapi. Your implementation will therefore simulate a for-loop that goes from the largest index to the smallest index in the string.

Pure and impure expressions

A bit of terminology first:

• An OCaml expression is said to be “impure” if evaluating it
  • incurs a side effect (e.g., a trace),
  • raises an error (e.g., due to a failed assertion, to a division by 0, etc.), or
  • diverges.
• If evaluating an OCaml expression incurs no side effect, raises no error, and yields a value, it is said to be “pure”.

So we can sketch a grammar of pure expressions as a sub-grammar of expressions:

n ::= ...a number...

b ::= ...a boolean...

c ::= ...a character...

s ::= ...a string...

x ::= ...a name...

e ::= ...an expression...

v ::= n | b | c | s |
    | fun formal -> e
    | x
    | (v, ..., v)
    | if v then v else v
    | let x = v and ... and x = v in v

The non-terminal e is for OCaml expressions in general, and the non-terminal v is for pure expressions. So, to a reasonable approximation, a pure expression (a value) can be

• a literal (number, Boolean, character, or string),
• a function abstraction,
• a variable (since variables denote values),
• a tuple of values, including the empty tuple,
• a conditional expression whose test, consequent, and alternative are values, and
• a let-expression whose definienses and body are values.

We can also classify as pure operations on ground values that do not raise errors. For example, the addition of two values is a value, but not the division of two values because of its potential for dividing by 0.

This classification is both under-approximative and over-approximative because some pure expressions do not fit this grammar (e.g., applying the identity function to a value is a pure operation) and because an expression that fits this grammar of pure expressions can be big enough to provoke a stack overflow when processed by OCaml.

That said, the following questions assume that we can distinguish between expressions that are pure for sure (written v), and expressions that might be impure (written e).

Question 8

1. For any pure expression v of type int, would it be valid to simplify v * 0 into 0?
2. For any potentially impure expression e of type int, would it be valid to simplify e * 0 into 0?
3. For any pure expression v of type int, would it be valid to simplify v * 1 into v?
4. For any potentially impure expression e of type int, would it be valid to simplify e * 1 into e?

Briefly justify your answers.

Question 9

Let e1 and e2 be potentially impure expressions.

1. Are the two following expressions equivalent (i.e., do they carry out the same computation?):

   let x1 = e1 and x2 = e2 in (x1, x2);;
   
   let x2 = e2 and x1 = e1 in (x1, x2);;
   

2. Are the two following expressions equivalent (i.e., do they carry out the same computation?):

   let x1 = e1 in let x2 = e2 in (x1, x2);;
   
   let x2 = e2 in let x1 = e1 in (x1, x2);;
   

Briefly justify your answers.

Question 10

Let v1 and v2 be pure expressions.

1. Are the two following expressions equivalent (i.e., do they carry out the same computation?):

   let x1 = v1 and x2 = v2 in (x1, x2);;
   
   let x2 = v2 and x1 = v1 in (x1, x2);;
   

2. Are the two following expressions equivalent (i.e., do they carry out the same computation?):

   let x1 = v1 in let x2 = v2 in (x1, x2);;
   
   let x2 = v2 in let x1 = v1 in (x1, x2);;
   

Briefly justify your answers.

Resources

• The OCaml code for the present mini-project (latest version: 06 Mar 2020, with an updated definition of a_function).

Version

Added the pastiche of Six Strings Down [09 Mar 2020]

Added the precision that OCaml is a statically typed programming language and that any OCaml expression has a type and is well typed [06 Mar 2020]

Added some Food for thought, lest anyone gets hungry [04 Mar 2020]

Fixed a typo in the narrative, thanks to Le Tram Anh’s eagle eye [24 Feb 2020]

Created [22 Feb 2020]