Re: Imperative programming in Caml

[John Prevost <jmp@arsdigita.com>]

>>>>> "wt" == Walid Taha <taha@cs.chalmers.se> writes:

    wt> Thanks for the nice rewrite, but it ain't purely functional
    wt> still! :)

    wt> Your point is well-taken.  I *am* a functional programmer,
    wt> though I haven't posted to this list before.  I am interested
    wt> in seeing how easy it is to explain imperative concepts in
    wt> Caml.  A bit to my surprise, it is turning out to be more
    wt> subtle than I thought.  In some cases, interesting remedies
    wt> might exits.  Your rewrite of the example is quite interesting
    wt> and I have noted it, but it still uses IO, which is
    wt> imperative.

    wt> I'll summarize the discussions at some point and send them to
    wt> the list.

Well, I think part of the point here is that ocaml does not pretend to
be a purely functional language.  It does, however, lend itself more
to a functional style of programming than an imperative one.  This is
much the same as Lisp or Scheme--there are many imperative constructs,
and in fact, you're likely to use them.  But when you do, it can feel
clunky.

Now, O'Caml has very nice support for working with non-mutable
datatypes.  It has some good support for dealing with mutable
datatypes, too.  What it does not have is a good library of mutable
datastructures.  Is this bad?  I don't think so.  I usually don't need
them.

In any case, a big part of why your program seems to clunky is that
your datatypes are poorly expressed.  Just like in other lesser
languages, it's useful to do some thinking ahead in O'Caml when you
build a complex datatype with pointers (references).  This is why it's
much easier and cleaner to use non-mutable datastructures so often.
You can more easily just define the datastructure without worrying
about the bookkeeping.

In any case, if you were using C, you would want to define some
functions that work on linked lists.  Likewise here.  Here's an
implementation in which I've defined a doubly linked list type and
some operations on it.  (Not all the operations you'd want, but enough
to do what you were trying to do in the spirit of your choice of
implementation.)

(* Module containing a mutable list (doubly-linked list) implementation *)

module Mlist = struct

(* each mcons (node) has a backward pointer, a value, and a foreward pointer *)
  type 'a mcons = { mutable back : 'a mcons option;
		    mutable v : 'a;
		    mutable fore : 'a mcons option }

(* a mlist (whole list object) contains pointers to the first and last
   items in the list *)
  type 'a mlist = { mutable head : 'a mcons option;
		    mutable tail : 'a mcons option }

(* create a new empty list with no nodes.  an empty list is something that
   has identity, so that we can insert into it later. *)
  let create () = { head = None; tail = None }

(* append an item onto a list *)
  let append list v =
    match list.tail with
      | None ->          (* can only happen with no items in the list *)
	  let new_node = { fore = None; v = v; back = None } in
	  begin
	    list.head <- Some new_node;
	    list.tail <- Some new_node
	  end
      |	Some old_node -> (* become the tail of the list *)
	  let new_node = { fore = None; v = v; back = list.tail } in
	  begin
	    old_node.fore <- Some new_node;
	    list.tail <- Some new_node
	  end
end

(* Separate out the "reading" and "writing" parts for clarity *)

let read_values () =
  let list = Mlist.create () in
  let finished = ref false in
  begin
    print_string "Please enter zero (0) to stop.\n\n";
    while not !finished do
      print_string "Enter a number: ";
      let number = read_int () in
      if number = 0
        then finished := true
        else Mlist.append list number
    done;
    list
  end

let show_values list =
  let node = ref list.Mlist.head in
  begin
    print_string "Here are the squares of the numbers you entered: ";
    while !node <> None do
      let Some { Mlist.v = number; Mlist.fore = next } = !node in
      print_int (number * number);
      print_string " ";
      node := next
    done;
    print_string "\n\nGood bye!\n\n"
  end

(* Do the parts together *)

let _ = show_values (read_values ())



Okay.  Some notes.  First--if this were a real project, I'd've hidden
more implementation details of the dllist.  It's not, though.  If more
had been hidden, the implementation invariants would actually be
protected, and I believe that the code using Mlist stuff would be more
clear.

Second thing to note.  In your code, you used an indentation style
that, quite frankly, strikes me as very odd.

My rule is generally to use begin/end around any block of imperative
calls, to always use let ... in let ... in unless and is necessary,
and not to indent after the in of a let in.  Oh.  And I always indent
two spaces.  If I just do these things, your code becomes:

let squareMany () =
  begin
    print_string "\nPlease enter zero (0) to stop.\n\n"; 
    let finished = ref false in
    let list = ref Empty in 
    let here = ref list in
    while not !finished do
      print_string "Enter a number : ";
      let number = read_int () in
      if number <> 0 then
        begin
          let new = ref Empty in
          !here := Cell (number, new);
          here := new;
        end
      else
        begin
          finished:=true;
        end 
      done;
    print_string "Here are the squares of the numbers you entered: ";
    while !list <> Empty do
      let Cell (number, rest) = !list in
      print_int (number * number);
      list := !rest;
      print_string " ";
    done;
    print_string "\n\nGood bye!\n\n";
  end

In this style, the difference between:

imperative call;
imperative call;
imperative call;

and

imperative call;
let x = blah in
imperative call

is much less disconcerting.

In short, I believe that your choice of datastructures leaves too much
hanging out, and that your choice of coding style has also gotten in
the way.

The thing that distressed me most was trying to figure out what your
ref ref was doing.  I understand it now.


So--O'Caml makes it easier to write clear concise small functional
code.  It also allows you to write imperative code, and when you do,
you must do just as much work as in any other imperative language to
make clear how your algorithm works.

Would you have written the above in C without writing some
datastructures and support functions?  I think not (even though you
could do it just with int**s and the like).  So you should not in
O'Caml either.

John.