overhead of GC in caml runtime?

overhead of GC in caml runtime?

[Norman Ramsey]

Can anyone tell me approximately what fraction of time is
spent in garbage collection, or even better, combined allocation and
collection, in typical caml programs?  Or how to get caml to report
this information for a particular program of mine?

thanks,


Norman

Re: overhead of GC in caml runtime?

[Xavier Leroy]

> Can anyone tell me approximately what fraction of time is
> spent in garbage collection, or even better, combined allocation and
> collection, in typical caml programs?

It depends how allocation-intensive your program is.  For instance, the
Knuth-Bendix benchmark (which allocates quite a lot of short-lived
data) spends about 20% of its time in GC and allocation in the major
heap, when compiled with ocamlopt on a Pentium.

The percentage is lower for bytecode programs, because the collector
still runs at the same speed while the mutator runs more slowly
because of the interpretation overhead.

Most allocations in the minor heap are expanded in-line, so they can't
be measured.

Hope this helps,

- Xavier Leroy

Imperative programming in Caml

[Walid Taha]

[Apologies in advance for purists that this project might offend.]

Dear all,

Below is one of my first attempts at imperative programming in ML: a
program that reads a list of numbers and squares them, using a "mutable
list".  The presence of a "while" construct and easy of terminal IO in
Caml should help an imperative programmer feel at home.  But I am
concerned (and a bit surprised, actually) that the use of "let" bindings
and the presence of normal variables in addition to "mutable" variables
might make it more difficult to explain this program to a beginer that is
*not* interested in the functional aspects.  If any one has suggestions
for making this program more "imperative", I would appreciate it.

Many thanks in advance,

Walid.

---

let squareMany () =
 print_string "\nPlease enter zero (0) to stop.\n\n"; 
 let finished = ref false 
 and 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";;

Re: Imperative programming in Caml

[Markus Mottl]

On Thu, 03 Aug 2000, Walid Taha wrote:
> [Apologies in advance for purists that this project might offend.]

It is not about being "purist" - just about solving problems effectively...

> The presence of a "while" construct and easy of terminal IO in Caml
> should help an imperative programmer feel at home.

I agree that "impurity" can come handy at times (but very seldom!).

> But I am concerned (and a bit surprised, actually) that the use of "let"
> bindings and the presence of normal variables in addition to "mutable"
> variables might make it more difficult to explain this program to a
> beginer that is *not* interested in the functional aspects.

It is a pity that he is not interested in the functional aspects (why?)!
If I wanted to confuse a beginner with a piece of code, I'd take one that
is relatively long, does not use many abstractions and ... is imperative.

Yours (excuse my criticism, I hope you understand the positive intention)
comes quite close to working as a repellent for beginners. - Even I have
troubles understanding what problem the code tries to solve!

> If any one has suggestions for making this program more "imperative", I
> would appreciate it.

If you absolutely need to make it imperative, please introduce some
additional functions (procedures) with intuitiv names so that the meaning
is clear.

In any case, the reason for using functional programming is not to annoy
beginners: in fact, since functional programming is on a somewhat higher
level compared to imperative programming, it is easier to reason about
"what" to solve rather than "how", which is what a beginner should be
concerned about. If he (she?) is already "biased" towards imperative
programming, I'd rather ask for hints on how to explain the merits of
functional style to motivate the beginner to try it.

Just compare the functional version with the imperative one (see below): I
can impossibly imagine that anybody would rather feel attracted by the much
more difficult imperative solution. I hope you'll succeed in "seducing"
your beginner to the elegance of functional style!

Regards,
Markus Mottl

---------------------------------------------------------------------------
  let rec read_ints () =
    print_string "Enter a number: ";
    let number = read_int () in
    if number <> 0 then number :: read_ints ()
    else []

  let squareMany () =
    print_string "\nPlease enter zero (0) to stop.\n\n";
    let lst = read_ints () in
    print_string "Here are the squares of the numbers you entered: ";
    List.iter (fun n -> print_int (n*n); print_char ' ') lst;
    print_string "\n\nGood bye!\n\n"
---------------------------------------------------------------------------

> let squareMany () =
>  print_string "\nPlease enter zero (0) to stop.\n\n"; 
>  let finished = ref false 
>  and 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";;

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: Imperative programming in Caml

[Walid Taha]

Dear Markus,

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

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

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

Best regards,

Walid.

On Fri, 4 Aug 2000, Markus Mottl wrote:

> On Thu, 03 Aug 2000, Walid Taha wrote:
> > [Apologies in advance for purists that this project might offend.]
> 
> It is not about being "purist" - just about solving problems effectively...
> 
> > The presence of a "while" construct and easy of terminal IO in Caml
> > should help an imperative programmer feel at home.
> 
> I agree that "impurity" can come handy at times (but very seldom!).
> 
> > But I am concerned (and a bit surprised, actually) that the use of "let"
> > bindings and the presence of normal variables in addition to "mutable"
> > variables might make it more difficult to explain this program to a
> > beginer that is *not* interested in the functional aspects.
> 
> It is a pity that he is not interested in the functional aspects (why?)!
> If I wanted to confuse a beginner with a piece of code, I'd take one that
> is relatively long, does not use many abstractions and ... is imperative.
> 
> Yours (excuse my criticism, I hope you understand the positive intention)
> comes quite close to working as a repellent for beginners. - Even I have
> troubles understanding what problem the code tries to solve!
> 
> > If any one has suggestions for making this program more "imperative", I
> > would appreciate it.
> 
> If you absolutely need to make it imperative, please introduce some
> additional functions (procedures) with intuitiv names so that the meaning
> is clear.
> 
> In any case, the reason for using functional programming is not to annoy
> beginners: in fact, since functional programming is on a somewhat higher
> level compared to imperative programming, it is easier to reason about
> "what" to solve rather than "how", which is what a beginner should be
> concerned about. If he (she?) is already "biased" towards imperative
> programming, I'd rather ask for hints on how to explain the merits of
> functional style to motivate the beginner to try it.
> 
> Just compare the functional version with the imperative one (see below): I
> can impossibly imagine that anybody would rather feel attracted by the much
> more difficult imperative solution. I hope you'll succeed in "seducing"
> your beginner to the elegance of functional style!
> 
> Regards,
> Markus Mottl
> 
> ---------------------------------------------------------------------------
>   let rec read_ints () =
>     print_string "Enter a number: ";
>     let number = read_int () in
>     if number <> 0 then number :: read_ints ()
>     else []
> 
>   let squareMany () =
>     print_string "\nPlease enter zero (0) to stop.\n\n";
>     let lst = read_ints () in
>     print_string "Here are the squares of the numbers you entered: ";
>     List.iter (fun n -> print_int (n*n); print_char ' ') lst;
>     print_string "\n\nGood bye!\n\n"
> ---------------------------------------------------------------------------
> 
> > let squareMany () =
> >  print_string "\nPlease enter zero (0) to stop.\n\n"; 
> >  let finished = ref false 
> >  and 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";;
> 
> -- 
> Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
> 

Re: Imperative programming in Caml

[John Prevost]

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

Re: Imperative programming in Caml

[Walid Taha]

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.

Re: Imperative programming in Caml

[John Prevost]

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

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

        {...}

    >> imperative call;
    >> let x = blah in
    >> imperative call
    >> 
    >> is much less disconcerting.

    wt> Not quite sure what you mean here.

If you write:

imperative call;
let x = blah in
  imperative call

then you get a little distracted by the indentation.  It's true that
the expression after a let ... in is part of that let, but since let
contains a single expression, keeping everything at the same
indentation level makes things a little more clear.  (That is, makes
it clear that you're doing one thing after another, whether it's the
imperative call or the binding call.)

    wt> Some of the choice was intentional.  In particular, "option"
    wt> types are very appropriate here, and were the first thing that
    wt> came to my mind when I was thinking about writing these little
    wt> examples.  But "option" types do, however, require introducing
    wt> the concept of parameteric polymorphism.  For my initial
    wt> postulate to be answer possitively, avoiding introducing
    wt> 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.

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

Mmm.  I don't think you're going to have much success at showing that
O'Caml is a reasonable language without using at least some
polymorphism.  Perhaps this restatement of my previous code would
help, though:

type optional_int =
       | No_Int
       | Some_Int of int

module MutableIntList = struct
  type mcons = { mutable fore : optional_mcons;
                 mutable v    : int;
                 mutable back : optional_mcons }
   and optional_mcons =
         | No_Mcons
         | Some_MCons of mcons
  type mlist = { mutable head : optional_mcons;
                 mutable tail : optional_mcons }
...
end

type optional_bool =
       | No_Bool
       | Some_Bool of bool

type mutable_bool = { mutable v : bool }

...

This does everything that the previous code did, but with no
parametric polymorphism.  If polymorphism is difficult to explain, you
might show the example in this form, then point out how the same sort
of datastructure is used over and over again with no change but a
different name and different types inside.  Then you could introduce
option and ref types as a generalized solution.

John.

Re: Imperative programming in Caml

[Walid Taha]

Hi John,

> If you write:
> 
> imperative call;
> let x = blah in
>   imperative call
> 
> then you get a little distracted by the indentation.  

Got it!

> Mmm.  I don't think you're going to have much success at showing that
> O'Caml is a reasonable language without using at least some
> polymorphism.  Perhaps this restatement of my previous code would
> help, though:
> 
> type optional_int =
>        | No_Int
>        | Some_Int of int

I feel you were "righter" the first time.  An "option" type is somehow
semanticaly implict in having "null/nill" in every pointer.  So, I think
it is reasonable to interpreter "'a pointer" as "'a option ref".  This
also suggests a naturally way to translate imperative programs to
functional programs systematically.

Thanks again for the great feedback.

Walid.

Re: Imperative programming in Caml

[Pierre Weis]

Hi Walid

> > If you write:
> > 
> > imperative call;
> > let x = blah in
> >   imperative call
> > 
> > then you get a little distracted by the indentation.  
> 
> Got it!
> 
> > Mmm.  I don't think you're going to have much success at showing that
> > O'Caml is a reasonable language without using at least some
> > polymorphism.  Perhaps this restatement of my previous code would
> > help, though:
> > 
> > type optional_int =
> >        | No_Int
> >        | Some_Int of int
> 
> I feel you were "righter" the first time.  An "option" type is somehow
> semanticaly implict in having "null/nill" in every pointer.  So, I think
> it is reasonable to interpreter "'a pointer" as "'a option ref".  This
> also suggests a naturally way to translate imperative programs to
> functional programs systematically.
> 
> Thanks again for the great feedback.
> 
> Walid.

Your problem seems to have something to do with elementary programming
in Caml; you may have a look at the documentation, in particular the
FAQ where basic indentation hints are given in the programming guide
lines (http://pauillac.inria.fr/caml/FAQ/pgl-eng.html), and questions
about imperative programming in Caml including the existence of
imperative pointers and their encoding in Caml are discussed in
details (http://pauillac.inria.fr/caml/FAQ/pointers-eng.html).

Note: if you really do not want to use any kind of polymorphism, I'm
afraid you will have a bad time to write and explain imperative
programming examples in Caml, since you cannot use references ('a
ref), nor arrays ('a array), nor options ('a option), nor lists ('a
list); if you also consistently banish polymorphism from your function
type schemes, what could you do without the basic predicates such that
(=) (that has type 'a -> 'a -> bool), or even any comparison
predicates (<, <=, <>, ...)  that are also polymorphic ?

Hope this helps,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: Imperative programming in Caml

[Walid Taha]

Dear Pierre,

Thank you for you comments.

> Your problem seems to have something to do with elementary programming
> in Caml; you may have a look at the documentation, in particular the
> FAQ where basic indentation hints are given in the programming guide
> lines (http://pauillac.inria.fr/caml/FAQ/pgl-eng.html), and questions
> about imperative programming in Caml including the existence of
> imperative pointers and their encoding in Caml are discussed in
> details (http://pauillac.inria.fr/caml/FAQ/pointers-eng.html).

I took a quick look, and both seem to be very good pointers.  I like the
systematic translation suggested.

> Note: if you really do not want to use any kind of polymorphism, I'm
> afraid you will have a bad time to write and explain imperative
> programming examples in Caml, since you cannot use references ('a
> ref), nor arrays ('a array), nor options ('a option), nor lists ('a
> list); if you also consistently banish polymorphism from your function
> type schemes, what could you do without the basic predicates such that
> (=) (that has type 'a -> 'a -> bool), or even any comparison
> predicates (<, <=, <>, ...)  that are also polymorphic ?

This is a good point.  I had overlooked the fact that "ref" itself is a
polymorphic type constructor.

Best regards,

Walid.

RE: Imperative programming in Caml

[Don Syme]

I don't know how it fits with the grammar, but something like
  mutable finished = false 
  mutable list = Empty
  mutable here = list 

might make things a bit clearer.  You could have implicit dereferencing for
everything declared with "mutable" and something like C's "&finished" if you
wanted to pass the reference.

Just a thought,
Don



-----Original Message-----
From: Walid Taha [mailto:taha@cs.chalmers.se]
Sent: 03 August 2000 20:20
To: caml-list@inria.fr
Subject: Imperative programming in Caml



[Apologies in advance for purists that this project might offend.]

Dear all,

Below is one of my first attempts at imperative programming in ML: a
program that reads a list of numbers and squares them, using a "mutable
list".  The presence of a "while" construct and easy of terminal IO in
Caml should help an imperative programmer feel at home.  But I am
concerned (and a bit surprised, actually) that the use of "let" bindings
and the presence of normal variables in addition to "mutable" variables
might make it more difficult to explain this program to a beginer that is
*not* interested in the functional aspects.  If any one has suggestions
for making this program more "imperative", I would appreciate it.

Many thanks in advance,

Walid.

---

let squareMany () =
 print_string "\nPlease enter zero (0) to stop.\n\n"; 
 let finished = ref false 
 and 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";;

RE: Imperative programming in Caml

[Walid Taha]

Hi Don,

Something along these lines did cross my mind.  In particular, it seems 
one might be able to lift this idea to the level of datatype 
declarations, so that a declaration like:

mutable type list = Cell of int * list;;

and that would be translated to

type list0 = Empty | Cell of int * list  (* Empty is "nil/null" *)
and  list  = list0 ref;;

Then, one can try to systematically introduce implicit dereferencing.  I
am a bit worried, though, that because ":=" is a first class citizen
(function) in Caml, doing things differently on the lhs and rhs might not
enforcable (meaning where to introduce implicit dereferencing).

Has anyone considered this before?

Walid.

On Fri, 4 Aug 2000, Don Syme wrote:

> 
> I don't know how it fits with the grammar, but something like
>   mutable finished = false 
>   mutable list = Empty
>   mutable here = list 
> 
> might make things a bit clearer.  You could have implicit dereferencing for
> everything declared with "mutable" and something like C's "&finished" if you
> wanted to pass the reference.
> 
> Just a thought,
> Don
> 
> 
> 
> -----Original Message-----
> From: Walid Taha [mailto:taha@cs.chalmers.se]
> Sent: 03 August 2000 20:20
> To: caml-list@inria.fr
> Subject: Imperative programming in Caml
> 
> 
> 
> [Apologies in advance for purists that this project might offend.]
> 
> Dear all,
> 
> Below is one of my first attempts at imperative programming in ML: a
> program that reads a list of numbers and squares them, using a "mutable
> list".  The presence of a "while" construct and easy of terminal IO in
> Caml should help an imperative programmer feel at home.  But I am
> concerned (and a bit surprised, actually) that the use of "let" bindings
> and the presence of normal variables in addition to "mutable" variables
> might make it more difficult to explain this program to a beginer that is
> *not* interested in the functional aspects.  If any one has suggestions
> for making this program more "imperative", I would appreciate it.
> 
> Many thanks in advance,
> 
> Walid.
> 
> ---
> 
> let squareMany () =
>  print_string "\nPlease enter zero (0) to stop.\n\n"; 
>  let finished = ref false 
>  and 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";;
>