[Caml-list] do-while loops have always been in OCaml

[Caml-list] do-while loops have always been in OCaml

[Oleg]

Whereas OCaml has `for' and `while' loops, C and Java-like languages
also have `do-while'; the Pascal family has the closely-related
`repeat-until' loops. There are cases (reminded below) where do-while
comes in quite naturally, and with performance advantages. For quite a
while I've been wishing for do-while~-- as is, without any
performance-degrading emulation or extra booleans.  Until I suddenly
realized that do-while has always been in OCaml. Most likely this is
well-known to many~-- but probably not to everyone. This message is
meant to be a reminder and a reference, of how do-while, *with the
expected performance*, is represented in OCaml. 


As a bit of motivation, the real need for (performant) do-while came
in the development of the recent version of strymonas: the stream
library with the utmost performance. Beside OCaml, strymonas also
generates C code, which has do-while natively. I wanted an interface
that supports do-while and produces the best code for both
languages. The method in this article has been used in strymonas and
indeed gave the desired performance -- matching, or surpassing in some
cases, hand-written stream-processing code.

The most common use case for do-while is executing some bit of
(imperative, IO) code that turns out needing re-execution. The typical
example is menu-selection. Here is how it looks in C:

int c;
do {
  puts("\nPlease enter");
  puts("1. choice A");
  puts("2. choice B");
  puts("q. exit");
  switch (c = getchar()) {
  case '1': puts("\n*** doing A"); break;
  case '2': puts("\n*** doing B"); break;
  }
} while (!(c=='q' || c == EOF));

The menu has to be displayed first. It is re-displayed if an invalid
choice is entered, and also to request another choice.

In strymonas, a typical case for do-while is zipping of complex
(nested, filtered, etc.) streams. At some point we execute the
generator of one stream, which is to produce an item and let the
further code deal with it. If the generator for some reason has not
produced an item (e.g., because of the filtering) and has not set the
termination trigger, it needs to be re-executed before we turn to the
other stream.


As well known, the lack of do-while loop does not limit
expressiveness: After all, according to the Structured Programming
theorem, every control flow may be converted to the one using
sequential composition, branching and while-iteration~-- provided one
may introduce an arbitrary amount of auxiliary (often boolean) state.
For our running example, the menu-selection C code can be written in
OCaml as follows:

let again = ref true in
while !again do
  print_endline "\nPlease enter";
  print_endline "1. choice A";
  print_endline "2. choice B";
  print_endline "q. exit";
  match input_char stdin with
  | exception End_of_file -> again := false
  | '1'   -> print_endline "\n*** doing A"
  | '2'   -> print_endline "\n*** doing B"
  | 'q'   -> again := false
  |  _    -> ()
done

We have to introduce an extra boolean, and test for it, even before
the first iteration where we know its value for sure. If we look at the
generated code, we see two branches: one at the beginning, after the
test for `again', and one, unconditionally, at the end, to be beginning
of the loop. It seems insignificant~-- but not when it is repeated
literally hundreds of millions of times in inner loops. The lack of
do-while indeed hinders the performance, as I have confirmed in
strymonas benchmarks.

It turns out, however, that OCaml does have do-while. The
menu-selection can be written to perfectly match the control flow of
the original C code, also avoiding auxiliary booleans. In fact, we
can avoid introducing any mutable state:

while 
  print_endline "\nPlease enter";
  print_endline "1. choice A";
  print_endline "2. choice B";
  print_endline "q. exit";
  match input_char stdin with
  | exception End_of_file -> false
  | '1'   -> print_endline "\n*** doing A"; true
  | '2'   -> print_endline "\n*** doing B"; true
  | 'q'   -> false
  |  _    -> true
do () done

That is the trick. To write it schematically, the do-while of C
     do stm while(test)
is perfectly represented in OCaml as
     while stm; test do () done

The compiled code (assembly) is exactly as desired, with no extra
branches.