Re: Can someone explain?

Re: Can someone explain?

[Juergen Pfitzenmaier]

Lyn A Headley wrote:
> An ocaml "port" of STL would kick ass.  especially, think how well
> iterators would combine with closures!  The C++ notion of "function
> objects" and "adaptors" looks clumsy in comparison (e.g. you cannot
> create a localized class object)

Hmm, don't know if it would be the same nice thing as in C++. A year ago
I added a GC to the STL containers so there's some experience of what
can happen if you try this in ocaml.
Some algorithms using the STL are built around the fact that certain iterators
and the value they refer to don't change if you treat the container ``nicely''.
To keep these algos working was quite some pain.
Haven't really thought about what happens if the GC is a real member of the
language and not just an add-on. May be things are easier then but I wouldn't
bet on it.
ciao pfitzen

Re: Can someone explain?

[skaller]

Lyn A Headley wrote:

> Here's an idea: just hijack the Python implementation and provide an
> ocaml interface.  This has the advantages that (1) it has been
> hand-tuned for efficiency for years and (2) that it will export a
> similar interface to the ocaml code as has existed for the C code for
> years, thus allowing a smoother transition to ocaml for python
> extension writers.

	I thought of that, and I was tempted!	
However, I decided against it for several reasons.

	First, while it leverages the Python code, it creates 
a headache for memory management, since Python does it's own,
which doesn't sit well with ocaml garbage collector.

	Second, it means any extensions I wish to write
will have to be written in C. This defeats the advantages
of using ocaml. For example, I have already added a Rational
type using the num module: I did it in only a few hours,
and added long integers at the same time: the num long integers
are already faster than the python ones.

	Third, it becomes sensitive to the C implementation
of Python which changes with versions, and depends on 
the whims of developers who may have different goals than I do.

> Come to think of it, why not do that for /all/ the builtin types?
> These will also be useful for use by code generated by viperc.

	So will the ocaml based run time, if the compiler back end
generates ocaml :-)

	There are two versions of Python: CPython (C) and JPython (Java).
Both suffer from portability problems, due to the base language,
compared with ocaml (IMHO). Both suffer from inferior technology,
compared with ocaml (IMHO).

	My plan is to suport _pure_ python, not C based extensions:
just the same as JPython cannot use C based extensions. 
I suspect that the C -> ocaml -> python wrapper chain for 
extensions representing external interfaces (operating system
services and access to C libraries) is probably easier
than the C -> CPython extension -> Python.

	However, a lot of C modules in python are only
for efficiency, and it is better to rewrite these in Python
and use the compiler, or, in ocaml if really necessary.

> Darn it, now you've got
> me all psyched about ocaml again.  Too bad I already committed to
> Eiffel for my latest project.

	Oh well :-)

> An ocaml "port" of STL would kick ass.  

	The code I showed is part of a set of modules I'm developing
that (attempt to) provide ocaml representations of the same ideas.
However, this has a lower priority than the python compiler.

>especially, think how well
> iterators would combine with closures!  The C++ notion of "function
> objects" and "adaptors" looks clumsy in comparison (e.g. you cannot
> create a localized class object)

	Yes. In fact, I have a contract to write a book on STL,
but I gave up precisely because of this. I tried to tell the
committee, but they just didn't understand. STL isn't that useful in
C++, because the core language fails to support
nested functions, when it could. Furthermore,
the committee broke the way unions work, so that they
cannot be used to implement variants easily.

	I prefer to work with a language whose developers
actually know some mathematics.

>     skaller> A class is used here to represent the whole list. It is
>     skaller> an object simply because that is the intended use: as a
>     skaller> mutable object with various mutators. In retrospect, this
>     skaller> is probably a mistake.
> 
> why?

	Because, the functional operations, such as concatenation,
require access to the private data, and cannot get it. There are
no friends in ocaml: the correct solution is to abandon the class
and use an algebraic data structure, and restrict the interface 
of the module so it becomes abstract.

	There is another reason: class methods cannot be polymorphic,
wheres plain functions of modules can be (independently of instantiation
of type parameters of the module).

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

Re: Can someone explain?

[skaller]

Gerd Stolpmann wrote:
> 
> On Tue, 05 Oct 1999, John Skaller wrote:
> >       The other thing I would beg for is to fix the parser
> >and lexer to be re-entrant [purely functional]. At present, state
> >information
> >must be kept in global store :-(
> >

> I have recently posted a solution for this problem

> The solution requires a complicated Makefile

I have seen your solution, but I'd prefer not to rely on
this kind of thing in code which may be distributed: it's fragile,
depending on implementation dependent knowledge about the form
of the files ocamlyacc generates.

However, it seems like a good proof of principle, and I'm 
sure we're agreeing a _standard_ solution in the next
version of ocaml would be ideal.

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

Re: Can someone explain?

[Lyn A Headley]

>>>>> "skaller" == skaller  <skaller@maxtal.com.au> writes:

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

    skaller> 	Thanks, but you have not answered the real question
    skaller> here: WHY are the values present in the interface when
    skaller> they are not accessible via the interface?

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

    skaller> 	Again, I knew that, the real question is WHY this
    skaller> information is in the _interface_??


[I know]


    skaller> 	I will change the representation to match Python,
    skaller> using an array (or perhaps a doubly linked list of
    skaller> arrays), and report back.

Here's an idea: just hijack the Python implementation and provide an
ocaml interface.  This has the advantages that (1) it has been
hand-tuned for efficiency for years and (2) that it will export a
similar interface to the ocaml code as has existed for the C code for
years, thus allowing a smoother transition to ocaml for python
extension writers.

Come to think of it, why not do that for /all/ the builtin types?
These will also be useful for use by code generated by viperc.


    skaller> 	You would need the WHOLE interpreter :-) I will make
    skaller> that available in the near future, asking for help to
    skaller> speed up the implementation.

yum. <smacks his chops noisily>

    skaller> 	I think it would be VERY useful to have an ocaml
    skaller> written Python interpreter/compiler as fast as, or faster
    skaller> than, CPython.  There are a lot of Python users out there
    skaller> who could be introduced to ocaml this way, and gain
    skaller> immediate benefits from a faster implementation
    skaller> (particularly the compiler).

Me too!  This could be a big thing for ocaml.  Darn it, now you've got
me all psyched about ocaml again.  Too bad I already committed to
Eiffel for my latest project.

[snip]

    skaller> A doubly linked list has a node containing two pointers,

[snip]
    >> > and 't iterator = > Empty > | Node of 't d_node

    skaller> 	This is the type of a pointer to a node. In ocaml,

An ocaml "port" of STL would kick ass.  especially, think how well
iterators would combine with closures!  The C++ notion of "function
objects" and "adaptors" looks clumsy in comparison (e.g. you cannot
create a localized class object)


    skaller> A class is used here to represent the whole list. It is
    skaller> an object simply because that is the intended use: as a
    skaller> mutable object with various mutators. In retrospect, this
    skaller> is probably a mistake.

why?


-Lyn

Re: Can someone explain?

[Gerd Stolpmann]

On Tue, 05 Oct 1999, John Skaller wrote:

>	The other thing I would beg for is to fix the parser
>and lexer to be re-entrant [purely functional]. At present, state
>information
>must be kept in global store :-(
>
>	It would also be useful if the parser could support nested
>parser calls as the lexer can: this is possible with the lexer,
>because the lexbuf is always in a state to read the next lexeme,
>however it is not possible with the parser because it may have read
>a token ahead of the production being reduced.

I have recently posted a solution for this problem by turning the
generated parser into a class; side-effects still exist but are
limited to the object representing the parser. You can simply create
several instances of the same parser, and nested parser calls are possible
if the sub-parser resides in a different object than the calling parser.

The solution requires a complicated Makefile, and I again suggest to
support an object-oriented parser generator in one of the next caml
releases. You find a description of the idea here:
	http://pauillac.inria.fr/caml/caml-list/1575.html

A working application is my XML parser, look at the files markup_yacc.mly and
Makefile.code in
	http://people.darmstadt.netsurf.de/Gerd.Stolpmann/ocaml/markup-0.2.tar.gz
As any real application, this parser is much more complicated than necessary to
demonstrate the principle...

Gerd

--
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 100             
64293 Darmstadt     EMail:   Gerd.Stolpmann@darmstadt.netsurf.de (privat)
Germany                     
----------------------------------------------------------------------------

Re: Can someone explain?

[Jerome Vouillon]

On Tue, Oct 05, 1999 at 08:57:20AM +1000, skaller wrote:
> Pierre Weis wrote:
> > 
> > > 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.
> 
> 	Thanks, but you have not answered the real question here:
> WHY are the values present in the interface when they are not accessible
> via the interface?
>  
> > > 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.
> 
> 	Again, I knew that, the real question is WHY this information
> is in the _interface_??

This information is in the interface because a class declaration can
also be used for inheritance, and a subclass can access the instance
variables of its parent and provide an implementation for the
virtual methods.

-- Jérôme

Re: Can someone explain?

[skaller]

Pierre Weis wrote:
> 
> > 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.

	Thanks, but you have not answered the real question here:
WHY are the values present in the interface when they are not accessible
via the interface?
 
> > 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.

	Again, I knew that, the real question is WHY this information
is in the _interface_??

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

	Sigh. I have just examined the Python implementation and 
the reason is that Python uses arrays for lists. This makes
insertion, deletion, and concatenation O(n), but it uses
fast machine primatives (memcpy) and does only one allocation.
My doubly linked list is the same order for appending,
but it laboriously copies each node one by one, and has to do an
allocation
for each one, and has to search for the i'th location as well.
So it is much slower than the Python equivalent.

	I will change the representation to match Python, using an
array (or perhaps a doubly linked list of arrays), and report back.

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

	You would need the WHOLE interpreter :-)
I will make that available in the near future, asking for help
to speed up the implementation.

	I think it would be VERY useful to have an ocaml written
Python interpreter/compiler as fast as, or faster than, CPython.
There are a lot of Python users out there who could be introduced
to ocaml this way, and gain immediate benefits from a faster
implementation (particularly the compiler).

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

	Excellent! This would be an ideal situation.

	The other thing I would beg for is to fix the parser
and lexer to be re-entrant [purely functional]. At present, state
information
must be kept in global store :-(

	It would also be useful if the parser could support nested
parser calls as the lexer can: this is possible with the lexer,
because the lexbuf is always in a state to read the next lexeme,
however it is not possible with the parser because it may have read
a token ahead of the production being reduced.

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

Sorry for brevity. STL is the C++ Standard Template Library,
it contains efficient codes for manipulating data structures
with generic algorithms, using iterators (i.e. pointer like things).

> > module DoublyLinkedList : BiDirectional =
> >   struct (* doubly linked list type *)
> >     type 't d_node =
> >       {
> >         mutable nxt: 't iterator;
> >         mutable prv: 't iterator;
> >         mutable data: 't
> >       }

A doubly linked list has a node containing two pointers,

	nxt -- a pointer to the next node object
	prv -- a pointer to the previous node object
	data -- the data

	
> >     and 't iterator =
> >       Empty
> >       | Node of 't d_node

	This is the type of a pointer to a node. In ocaml,
references are used for pointers, so the type of a pointer is
just that of a node, except that the pointer can advance
'off the end of the list' and so can refer to no node,
and thus the two cases 'Empty' for off the end, and Node
for pointing to an actual 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

	next gets a pointer to the next node, given a pointer to some
node x. deref gets the data, given an iterator. in C++:

	x = ++x // next
	*x      // deref

is the notation used, however the implementation is

	x->nxt
	x->data

> >     class ['t] dlist =
> >       object(self)
> >         val mutable first': 't iterator = Empty

A class is used here to represent the whole list. It is an object
simply because that is the intended use: as a mutable object
with various mutators. In retrospect, this is probably a mistake.

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

Re: Can someone explain?

[Pierre Weis]

> 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

Can someone explain?

[skaller]

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?

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

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.

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

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