Version française
Home     About     Download     Resources     Contact us    
Browse thread
overhead of GC in caml runtime?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Walid Taha <taha@c...>
Subject: Re: Imperative programming in Caml

Dear John,

Thank you for your detailed reply and comments.  You make some very good
points.  Let me try to explain some things that were not explicit in my
initial email, and some others that your suggestions have brought to
light:

> Well, I think part of the point here is that ocaml does not pretend to
> be a purely functional language.  

Yes, and that is indeed a good thing in general.

> 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.

My interest is not in having libraries, but rather, in how close to
"street imperative style" one can get writting code in Caml.  Also, I am
not saying imperative programming is better.  Neither am I concerned about
the presence of imperative libraries.  Rather, I am interesting about in
imperative programs (including libraries, I guess) could be written in a
way easy to explain to an imperative programmer.

> 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 ())
> 

This is a great revision, and I particularly like the way that you broke
the task into smaller pieces.  The code is certainly more structured.  
However, you get the biggest payoff in your rewrite from using the
"option" type, and that is something that I was trying to avoid (see
"option types" below).

> 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

Many thanks for the rewrite and the comments on indentation style!

> 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.

Not quite sure what you mean here.

> 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.

Some of the choice was intentional.  In particular, "option" types are
very appropriate here, and were the first thing that came to my mind when
I was thinking about writing these little examples.  But "option" types
do, however, require introducing the concept of parameteric polymorphism.
For my initial postulate to be answer possitively, avoiding introducing
concepts from function programming would be necessary.

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

I found the need for ref ref that strange too, but as you see, for that
"naive" imperative style, it is necessary.

Thanks again for you detail feedback.  Your input is very useful.

Walid.