Re: Can someone explain?

From: Pierre Weis (Pierre.Weis@inria.fr)
Date: Mon Oct 04 1999 - 10:23:49 MET DST


From: Pierre Weis <Pierre.Weis@inria.fr>
Message-Id: <199910040823.KAA21438@pauillac.inria.fr>
Subject: Re: Can someone explain?
To: skaller@maxtal.com.au (skaller)
Date: Mon, 4 Oct 1999 10:23:49 +0200 (MET DST)
In-Reply-To: <37F10F65.47A4212C@maxtal.com.au> from "skaller" at Sep 29, 99 04:56:37 am

> Is there a way to access a value of a class instance?
> If so, what is the syntax? If not, what is the purpose
> of allowing 'val' bindings in class declarations in module
> signatures?

The only way to access a value of a class instance is via method
invocation: you have to define a method that returns the value.

> Similarly, what is the purpose of allowing 'virtual'
> methods in class types and class declarations in
> module signatures?

Virtual methods are methods that are declared but not implemented:
sub-classes must define them.

> I have a doubly linked list class, and concatenating
> two lists takes 100 times longer in ocaml using my
> code than pythons list concatenation function,
> which is written in C.

Wao! I would like to be able to run your benchmark, since I will be
glad to try to use the Python's way of handling lists to speed up the
Caml list package by a factor of 100! We worked hard on this point,
and Caml lists (and more generally similar data structure
manipulations) are supposed to be among the fastest known
implementations available. So, could you please send a complete
reproducible benchmark ?

> My code isn't optimal (given the particular data structure
> I've chosen) because the concat function cannot
> get at values of the class. Excerpt given below.
> Any advice appreciated. (A high speed mutable list
> in the standard library would be even better :-)

As you suggested, we may add extra list manipulation modules in the
standard library, such as mutable lists or doubly linked
lists. Mutable lists are easy to implement and there is no doubt that
many Caml programmers have already written such kind of packages and
can contribute.

About your own program, I cannot comment on efficiency, since I do not
catch the general idea of the design: I am a bit surprised by the
melting of object oriented features and regular algebraic data type
manipulation to implement lists. Could you please explain a bit the
logic of your code (in particular the only comment
(* STL style mutators *) is a kind of puzzle for me) ?

Best regards,

Pierre Weis

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

> module DoublyLinkedList : BiDirectional =
> struct (* doubly linked list type *)
> type 't d_node =
> {
> mutable nxt: 't iterator;
> mutable prv: 't iterator;
> mutable data: 't
> }
>
> and 't iterator =
> Empty
> | Node of 't d_node
>
> let next x = match x with Empty -> Empty | Node n -> n.nxt
> let deref x = match x with Empty -> None | Node n -> Some n.data
>
> class ['t] dlist =
> object(self)
> val mutable first': 't iterator = Empty
> val mutable last': 't iterator = Empty
> val mutable size: int = 0
>
> method private init node =
> last' <- node;
> first' <- node;
> size <- 1
>
> method length = size
>
> (* STL style mutators *)
> method push_back (data':'t): unit =
> match last' with
> | Empty -> self#init (Node {nxt=Empty; prv=Empty; data=data'})
> | Node fin ->
> let tmp = Node {nxt=Empty; prv=last'; data=data'} in
> fin.nxt <- tmp;
> last' <- tmp;
> size <- size + 1
>
> method first = first'
> end
>
> let concat (x:'a dlist) (y:'a dlist) :'a dlist =
> let z = new dlist in
> let i = ref x#first in
> while deref !i <> None do
> match deref !i with
> | Some v -> z#push_back v; i := next !i
> | None -> assert false
> done;
> let j = ref y#first in
> while deref !j <> None do
> match deref !j with
> | Some v -> z#push_back v; j := next !j
> | None -> assert false
> done;
> z
> end
>
> --
> John Skaller, mailto:skaller@maxtal.com.au
> 1/10 Toxteth Rd Glebe NSW 2037 Australia
> homepage: http://www.maxtal.com.au/~skaller
> downloads: http://www.triode.net.au/~skaller



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:25 MET