[Caml-list] generic programming

[Caml-list] generic programming

[Oleg]

Hi

Is generic programming possible with O'Caml? Suppose I want to find the 
Pearson correlation between two sets of real numbers represented as sets, 
arrays, big_arrays, maps, stacks, queues or lists. Is it possible to have one 
piece of code that handles all of these containers, a generic function of 
some sort? (Iteration is all that is necessary in the Pearson correlation 
example)

Thanks
Oleg

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Re: generic programming

[Ketanu]

Oleg <oleg_inconnu@myrealbox.com> writes:

> Hi
>
> Is generic programming possible with O'Caml? Suppose I want to find the
> Pearson correlation between two sets of real numbers represented as sets,
> arrays, big_arrays, maps, stacks, queues or lists. Is it possible to have
> one piece of code that handles all of these containers, a generic function
> of some sort? (Iteration is all that is necessary in the Pearson
> correlation example)

Sure it is possible ! You should embed all these containers into either
objects or modules whith homogenous interface suitable for your algorithm,
and then code thge appropriate functor or object which will provide the
algorithm itself.

You may also build streams on the top of your structures and implement
algorithm for strams (if this is suitable with the kind of iteration you
need).

You may also write a function pearson_correlation with the four arguments
set1 set2 iter1 iter2, with types

set1:'a
set2:'b
iter1:'a -> int -> float
iter2:'b -> int -> float

where the iter1,2 functions must provide iteration over the containers
set1,2 (thus, the types for iter1,2 mas need to be adapted to your
iteration). 

Hope it helps !
-- 
Ketanu <katanu@wanadoo.fr> - RSA PGP Key ID: 0x20D90C12

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generic programming

[Johan Baltié]

> Hi
> 
> Is generic programming possible with O'Caml? Suppose I want to find 
> the Pearson correlation between two sets of real numbers represented 
> as sets, arrays, big_arrays, maps, stacks, queues or lists. Is it 
> possible to have one piece of code that handles all of these 
> containers, a generic function of some sort? (Iteration is all that is 
> necessary in the Pearson correlation example)

Aren't you looking for functors ??
(http://caml.inria.fr/ocaml/htmlman/manual004.html part 2.3)

Or did I miss something ?


Ciao

Jo
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generic programming

[Jun P.FURUSE]

Hello,

> Is generic programming possible with O'Caml? Suppose I want to find the 
> Pearson correlation between two sets of real numbers represented as sets, 
> arrays, big_arrays, maps, stacks, queues or lists. Is it possible to have one 
> piece of code that handles all of these containers, a generic function of 
> some sort? (Iteration is all that is necessary in the Pearson correlation 
> example)

You may be interested in an experimental implementation of generic
values on O'Caml, found at

    http://pauillac.inria.fr/~furuse/generics/

Regards,
--
Jun
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Chris Hecker]

> > Is generic programming possible with O'Caml?
>Sure it is possible !

Is it, in the sense that Stepanov and those guys mean it?  John Max Skaller 
and I were talking about this a long time ago, and I thought he posted this 
to the list but it turns out it was in email to me, but here goes anyway:

"Sure. I have a 'problem' example: try to implement STL iterators
in Caml. I don't have the expertise in Caml: I think this requires
'higher order functors'. Several people have attempted this, no one
has succeeded that I know of."

Perhaps he's reading and can explain some of the problems.

Caml polymorphism&functors and C++ templates seem to have different 
properties, and I wonder what you can and can't write in each.

Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Oleg]

On Wednesday 03 July 2002 01:29 pm, Chris Hecker wrote:

> Perhaps he's reading and can explain some of the problems.
>
> Caml polymorphism&functors and C++ templates seem to have different
> properties, and I wonder what you can and can't write in each.

I'm also concerned about compilation times. When writing C++ code, having to 
keep template definitions in header files in their entirety is frequently my 
reason not to write templated code.

Thanks
Oleg
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Alessandro Baretta]

Oleg wrote:
> On Wednesday 03 July 2002 01:29 pm, Chris Hecker wrote:
> 
> 
>>Perhaps he's reading and can explain some of the problems.
>>
>>Caml polymorphism&functors and C++ templates seem to have different
>>properties, and I wonder what you can and can't write in each.
> 
> 
> I'm also concerned about compilation times. When writing C++ code, having to 
> keep template definitions in header files in their entirety is frequently my 
> reason not to write templated code.

Templates are "nasty" citizens of the C++ world. I've had 
*so* many problems tracking down bugs in code using STL 
templates. Basically, the "write once, compile many" 
strategy of C++ yields situations where the semantics of the 
algorithms coded in a template depends upon the type 
parameter you pass to the template itself. Abominable.

Stick to Caml: "Write Once, Compile Once, Link Many".

Alex



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Peter Wood]

On Wed, Jul 03, 2002 at 10:29:09AM -0700, Chris Hecker wrote:
> 
> >> Is generic programming possible with O'Caml?
> >Sure it is possible !
> 
> Is it, in the sense that Stepanov and those guys mean it?  John Max Skaller 
> and I were talking about this a long time ago, and I thought he posted this 
> to the list but it turns out it was in email to me, but here goes anyway:
> 
> "Sure. I have a 'problem' example: try to implement STL iterators
> in Caml. I don't have the expertise in Caml: I think this requires
> 'higher order functors'. Several people have attempted this, no one
> has succeeded that I know of."
> 
> Perhaps he's reading and can explain some of the problems.
> 
> Caml polymorphism&functors and C++ templates seem to have different 
> properties, and I wonder what you can and can't write in each.
> 
> Chris

Hi,

Here's an interesting (though old) article by Henry Baker, "Iterators:
Signs of Weakness in Object-Oriented Languages".

http://linux.rice.edu/~rahul/hbaker/Iterator.html

Regards,
Peter
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[james woodyatt]

On Wednesday, July 3, 2002, at 02:55 PM, Peter Wood wrote:
>
> Here's an interesting (though old) article by Henry Baker, "Iterators:
> Signs of Weakness in Object-Oriented Languages".
>
> http://linux.rice.edu/~rahul/hbaker/Iterator.html

Funny you should bring that up now.  I've been working on basically the 
same problem in recent days.

The approach I've been taking seems to me to be similar to what Baker 
describes in that paper.  I have a functional red-black binary tree 
functor that defines a pair of functions for creating generic functional 
streams of the objects in a tree (one in increasing order and the other 
in decreasing order).

I've written functions that map red-black trees (and other specialized 
collections) into objects of a functional stream class.  I've also 
written a library of functions that perform some generic algorithms on 
the contents of generic functional streams (and pairs of streams), e.g. 
fold, compare, etc.

It's true that the stream of elements in my red-black tree 
implementation requires a stack of previously visited parent nodes, but 
that's an artifact of my implementation of the red-black tree 
algorithm.  (If I had used the traditional mutable red-black tree 
algorithm, I could have avoided the stack in the stream object.)  So... 
I've also written "more efficient" variants that use the program stack 
when there's only one tree in the loop, though-- I've not yet measured 
the improvement.

I think the whole thing makes "rather tasteful use of objects and class 
types" to borrow a phrase from Dr. Leroy.  Let me poke at it some more, 
then I'll document it and throw it up for review.  You'll be able to 
judge for yourself.

Meanwhile, I'd say "generic programming" is quite "well-enabled" by 
Ocaml.  Whether you want to do it in the style of Stepanov's STL is a 
whole other question...  Personally, I'd rather be flensed alive by a 
gang of Welsh football hooligans armed with potato peelers than write 
another line of C++ using the STL.  (Okay, that's unnecessarily 
inflammatory.)


--
j h woodyatt <jhw@wetware.com>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Chris Hecker wrote:

>
>
> Is it, in the sense that Stepanov and those guys mean it?  John Max 
> Skaller and I were talking about this a long time ago, and I thought 
> he posted this to the list but it turns out it was in email to me, but 
> here goes anyway:
>
> "Sure. I have a 'problem' example: try to implement STL iterators
> in Caml. I don't have the expertise in Caml: I think this requires
> 'higher order functors'. Several people have attempted this, no one
> has succeeded that I know of."
>
> Perhaps he's reading and can explain some of the problems.
>
> Caml polymorphism&functors and C++ templates seem to have different 
> properties, and I wonder what you can and can't write in each. 


>
> > Is generic programming possible with O'Caml?
> Sure it is possible !

C++ templates use TWO kinds of 'polymorphism' together:

    1) parametric polymorphism
    2) overloading (ad hoc polymorphism)

for example:

    template<class T> int g(T t) { return f(t); }

Notice that 'f' is chosen at instantiation time, based on
the type T of t. You cannot do this in Ocaml, where you
must write instead:

    let g t f = f t in ...

that is, you have to pass the 'dependent function' f explicitly.
This includes methods. The only functions in Ocaml that can act
on a value which has the type of a parameter (but which
do not need to be explicit arguments) are parametrically
polymorphic ones, for example:

    let pair x = (x,x) in ..
    let f x = pair x (* don't need to pass 'pair', its polymorphic *)

now, C++ iterators *depend* on ad hoc polymophism.
For example the algorithm:

    template <class iterator1, class iterator2>
    iterator2 copy(iterator1 src, iterator1 end, iterator2 dst) {
        while(src != end) *dst++ = *src++;
        return dst;
    }

has 'ad hoc' operations on the types iterator1 and iterator2:
namely comparison, dereference, and increment,
and, there are also two implicit types

    iterator1::value_type
    iterator2::value_type

which either must be the same, or there is
a conversion between them .. which is yet another
function not passed explicitly to the template.

As you can see, C++ relies on the *syntactic form*
of the template body, to express the genericity,
and overloading at instantiation time. In general,
this is not 'well principled' although it works well
in practice (but also leads to disasters when it fails
without a compilation error). technically, instantiation
must be functorial, in the sense of both category theory
an Ocaml functors (since these are the same idea ..),
that is, instantiation should 'preserve structure'.

But there is no assurance the C++ instantiation mechanism is functorial.

To make 'copy' work in Ocaml, you can either pass ALL the arguments
explicitly -- and there are a lot of them here .. or you can package them
up in a module with a specifiic interface and use a functor.

Ocaml functors (and polymorphic functions) guarratee functorial 
instantiation
on the algebraic (free) types. If a module has constraints represented as
comments, these are not necessarily preserved by instantiation .. so both
systems have limitations.

Only two data structures in Ocaml readily admit iterators: lists and arrays.
Other data structures like hastables, sets, maps, etc, have control
inverted iterators, which are much weaker (that is, you have to provide
a callback which is given each value in turn -- this is very much less 
useful
than the C++ construction dual to it in which the values are fetched in turn
by an user algorithm...you have to 'control invert' the algorithm to use
it with Ocaml XXX.iter functions, which is non-trivial and greatly
obscures the code. [But I think it can always be done using a mechnical
procedure, related to continuatiuon passing .. my Felix compiler does in
precisely this, but only for a simgle message source at present]

The real problem for STL style iterators is this: in C++,
the very point of iterators is that container independent
algorithms can be written. There is no easy way to do this in Ocaml,
at least not without using classes.

There is a technical way to express the limitation: in Ocaml,
functions are value polymorphic. But higher order functions cannot
be functorially polymorphic, that is, that cannot vary over
different data functors (data structures like lists and arrays
are known as data functors). Hence, we have

    List..map
    Array.map
    Hashtble.map

etc, instead of just 'map' .

Functorial polymorphism can be implemented for a wide class
of functors in an extension of ML: there is work being done
by Barry Jay at UTS on this. See

    http://www-staff.it.uts.edu.au/~cbj/Publications/functorial_ml.ps.gz

Perhaps some of the type theorists reading the above text can give
a better and more proper explanation. But basically: C++ allows
polymorphism over data functors, but that polymorphism is NOT
parametric like it should be. Ocaml insists of everything being
'correct', which excludes features which 'sort of work sometimes' :-)

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Alessandro Baretta wrote:

> Templates are "nasty" citizens of the C++ world. I've had *so* many 
> problems tracking down bugs in code using STL templates. Basically, 
> the "write once, compile many" strategy of C++ yields situations where 
> the semantics of the algorithms coded in a template depends upon the 
> type parameter you pass to the template itself. Abominable.

Well, it isn't that bad, but this:

    "the semantics of the algorithms coded in a template depends upon 
the type parameter you pass to the template"

is entirely correct: instantiation is not functorial (it doesn't 
necessarily preserve the structure
of the algorithm represented in the template .. alternatively, you can 
be 'nastier' and just
say that a template algorithm doesn' *have* any semantics).

FYI: as a member of the C++ committee I have fought long and hard to
limit the damage by trying to insist that the type parameters of a template
can only be bound to object types, and not 'const' or 'reference'  types.
If you allow such bindings, the semantics are wildly indeterminate.
For example:

    template<class T> T f(T t) { return t; }

    f<int&>(x) // returns reference to x

is utterly unlike

    f<int>(x) // returns copy of x

and one wonders what

    template<class T> T &( T &t) { return t; }

means when instantiated like:

    f<int&>  // what type is int && ??

Before you can have parametric polymorphism,
you need a coherent type system .. :-)

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Francois Pottier]

On Wed, Jul 03, 2002 at 10:29:09AM -0700, Chris Hecker wrote:
>
> "Sure. I have a 'problem' example: try to implement STL iterators
> in Caml. I don't have the expertise in Caml: I think this requires
> 'higher order functors'. Several people have attempted this, no one
> has succeeded that I know of."

My memories of STL are vague, but if an iterator is what I think it
is, then implementing one in O'Caml is pretty straightforward. An
iterator is a function that returns a function which maintains a
piece of internal state. There is certainly no need for functors
here!

Here is one for lists:

(* [iterator s] returns a stateful iterator over the list [s]. That is,
   if $s = \{ x_1, x_2, \ldots, x_n \}$, then [iterator s] is a function
   which, when invoked for the $k^{\text{th}}$ time, returns [Some ]$x_k$,
   if $k\leq n$, and [None] otherwise. *)

(* val iterator : 'a list -> (unit -> 'a option) *)

  let iterator list =

    let remainder = ref list in

    let rec next () =
      match !remainder with
      | [] ->
	  None
      | elem :: rest ->
	  remainder := rest;
	  Some elem in

    next

And (more interesting) here is one for trees:

(* [iterator s] returns a stateful iterator over the tree [s]. That is, if
   $s = \{ x_1, x_2, \ldots, x_n \}$, where $x_1 < x_2 < \ldots < x_n$, then
   [iterator s] is a function which, when invoked for the $k^{\text{th}}$
   time, returns [Some ]$x_k$, if $k\leq n$, and [None] otherwise. Such a
   function can be useful when one wishes to iterate over a tree's elements,
   without being restricted by the call stack's discipline.

   Because the call stack is not used to store information about which part
   of the tree remains to be walked, an explicit (heap-allocated) structure
   has to be used. It is defined below. Note that it is essentially a list
   of (element, right-tree) pairs, which corresponds to the information
   which would be stored in the call stack, if it were used.

   It would be possible to implement a straightforward iterator by first
   turning the tree into a list, then walking the list. Our implementation
   is more economical, because it only allocates a structure of size $O(\log
   n)$ (the call stack) at a given time, and because only one walk is
   necessary, thus reaping a small constant time factor. *)

(* val iterator : 'a list -> (unit -> 'a option) *)

  type 'a tree =
    | Empty
    | Node of 'a tree * 'a * 'a tree * int

  type 'a remainder =
    | Nothing
    | ElemThenRightThenParent of 'a * 'a tree * 'a remainder

  let iterator s =

    (* When asked to create an iterator for s, we allocate a piece of state,
       which shall allow the iterator to remember which part of the tree
       remains to be walked. It consists of a tree and a remainder, which are
       to be walked in order. At first, the whole tree [s] has to be walked,
       and there is no remainder.

       Note that [next] does not work in worst-case constant time, since it
       may have to travel arbitrarily far down the current sub-tree's left
       spine. However, it does work in amortized constant time; in other
       words, iterating over a complete tree still takes worst-case linear
       time. *)

    let tree = ref s
    and remainder = ref Nothing in

    let rec next () =
      match !tree, !remainder with
      | Empty, Nothing ->
	  None
      | Empty, ElemThenRightThenParent (elem, right, parent) ->
	  tree := right;
	  remainder := parent;
	  Some elem
      | Node(l, v, r, _), parent ->
	  tree := l;
	  remainder := ElemThenRightThenParent(v, r, parent);
	  next () in

    next

I hope this helps,

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Francois Pottier]

On Fri, Jul 05, 2002 at 01:18:17AM +1000, John Max Skaller wrote:
> 
> Only two data structures in Ocaml readily admit iterators: lists and arrays.
> Other data structures like hastables, sets, maps, etc, have control
> inverted iterators, which are much weaker (that is, you have to provide
> a callback which is given each value in turn

This is true, and I might add that they are *intended* to be weaker.
Programming with an explicit `iter' or `fold' is much more structured
than using an iterator; it is more compact and makes your intent more
apparent. (This idiom is perhaps difficult to read for non-functional
programmers, but the same is true of many features in many languages.)

I find that the use of iterators is very seldom necessary. One typical
instance is when you need to simultaneously iterate over two trees
which have the same fringe, but not necessarily the same shape. Then,
you may use `iter' to iterate over one tree, but need an iterator to
traverse the other. I think this kind of situation arises rather seldom.

Lastly, I should insist (as shown in my previous posting) that this is
not a language issue; it's a library issue. O'Caml's standard library
offers stack-based iterators, but no stateful iterators. This design
choice is meant to encourage a functional programming style and I support
it.

> The real problem for STL style iterators is this: in C++,
> the very point of iterators is that container independent
> algorithms can be written. There is no easy way to do this in Ocaml,
> at least not without using classes.

This is wrong... why classes? (read on)

> are known as data functors). Hence, we have
> 
>     List..map
>     Array.map
>     Hashtble.map
> 
> etc, instead of just 'map' .

Certainly, but you can parameterize your code over `map' (that is, write
as a higher-order function or as a functor) and then apply it to a version
of `map' for the particular data structure at hand.

> Functorial polymorphism can be implemented for a wide class
> of functors in an extension of ML: there is work being done
> by Barry Jay at UTS on this.

As far as I understand, this work is about automatically *generating* code
for `map' from the definition of a data type, which is another issue. O'Caml
as it stands already allows you to write `container independent' code.

> Perhaps some of the type theorists reading the above text can give
> a better and more proper explanation. But basically: C++ allows
> polymorphism over data functors, but that polymorphism is NOT
> parametric like it should be.

Entirely true. I call that textual polymorphism :)

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Xavier Leroy]

> On Fri, Jul 05, 2002 at 01:18:17AM +1000, John Max Skaller wrote:
> > 
> > Only two data structures in Ocaml readily admit iterators: lists and arrays.
> > Other data structures like hastables, sets, maps, etc, have control
> > inverted iterators, which are much weaker (that is, you have to provide
> > a callback which is given each value in turn

I guessed this is what John had in mind :-)

Actually, if you're desperate, you can derive a C++-style iterator
from a higher-order functional iterator (of the kind provided by the
OCaml standard library) by "inverting the control", using threads or
call/cc.  See example below.

Of course, I'm not advocating that anyone should use this trick in actual
programs.  Like François, I find functional iterators so much cleaner
and better structured.  Moreover, the extra "power" of imperative iterators
isn't obvious to me.  For instance, one could argue that imperative
iterators allow iterating in parallel over several data structures.
This is true, but how useful is iterating over two hashtables in
parallel, knowing that you will *not* scan matching keys at the same time?

- Xavier Leroy

exception End_of_iteration

let hashtbl_enumerator (h, chan) =
  Hashtbl.iter
    (fun key data -> Event.sync (Event.send chan (Some(key, data))))
    h;
  Event.sync (Event.send chan None)

class ['a,'b] hashtbl_iterator (h : ('a, 'b) Hashtbl.t) =
    object
      val chan = Event.new_channel ()
      initializer (ignore (Thread.create hashtbl_enumerator (h, chan)))
      method next_element =
        match Event.sync (Event.receive chan) with
          None -> raise End_of_iteration
        | Some e -> e
    end

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Chris Hecker]

>Like François, I find functional iterators so much cleaner
>and better structured.  Moreover, the extra "power" of imperative iterators
>isn't obvious to me.

I think this is a very important point, but I totally disagree with your 
conclusion.  Giving up explicit control over the flow of your program is a 
serious problem in my opinion, and callback solutions force you to do 
that.  Iterating over two things at once is an obvious example of where it 
breaks down, but it happens in a lot of places.  Real closures make it less 
painful to deal with this than in languages without closures, because you 
can have the map/iter code right there acting locally, but closures still 
don't really eliminate the problem that you aren't in control of when that 
code gets called anymore.

As another example, this idiom/pattern actually shows up a lot in GUI APIs 
for things like events.  I think it's pretty clear at this point that 
callback based event handling code leads to more lines of less readable and 
harder to understand code than having the client code be able to pull 
things off a queue when it's ready for the events.  I'm sure some disagree 
with this statement.

Both of these are examples of "push versus pull" interfaces, and pull just 
seems to work better.  Having data pushed at you means you often end up 
buffering it on your end to manage your flow control anyway unless you're 
just doing some trivial processing.

Furthermore, it seems like it's a common trap to fall into saying the 
familiar "you don't want to do that" (like your comment about hashtables) 
when there's a fair amount of evidence that it's reasonable thing to want 
to do (and I think better in a lot of ways).  It seems like it's something 
a good language should support well.

I'm not saying that callback/push interfaces are always bad, just that 
there are strengths and weaknesses to both.  To reference the XML thread, 
there's a reason there are both DOM and SAX interfaces.  I wish Ocaml 
supported imperative/pull coding styles better, which is why I'm interested 
in this thread.

It's late...hopefully this mail made some sense.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] generic programming

[Anton Moscal]

Hello, Johan!
You wrote to "Anton Moscal" <msk@post.tepkom.ru>; "Johan Baltié"
<johan.baltie@wanadoo.fr> on Wed, 3 Jul 2002 10:27:53 +0100:

>> standard collections.

 JB> Yes, but this wrappers are no harsh job to do I think.

It's more complex and delicate job to create logical and otrhogonal design
for such signatures. Stepanov does good job of the same kind for C++.

Anton
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Xavier Leroy]

> [Lots of interesting points about "push" vs. "pull" APIs omitted]

All you said is very reasonable, but I think you're generalizing the
discussion (especially with the GUI examples) beyond what I had in
mind, i.e. iteration over in-memory data structures.  In particular:

> Giving up explicit control over the flow of your program is a 
> serious problem in my opinion

When the task at hand is sufficiently abstract, e.g. "visit every
element of this set once", or "transform this list by applying this
function to each element", explicit control over the flow is something
that I'll gladly omit.  (Just like I'm happy not to have explicit
control over memory deallocation.)

In other terms, are you really saying that you prefer writing

        for (Enumeration e = l.elements(); e.hasMoreElements(); )
                frobnicate((SomeClass) e.nextElement());

over writing

        List.iter frobnicate l

> It seems like it's something a good language should support well.
> [...]
> I wish Ocaml supported imperative/pull coding styles better, which
> is why I'm interested in this thread.

The language provides full imperative power, and it's easy to write
imperative iterators over concrete data structure (like François
showed).  So, what more would you like?

True, abstract types provided by the standard library do not provide
imperative iterators (heavens forbid :-); but there are about three of
them (Set, Map, and Hashtbl), so I don't think this would really stop
you, should you embark in writing STL-style or java.util-style code in
OCaml...

> Furthermore, it seems like it's a common trap to fall into saying the 
> familiar "you don't want to do that" (like your comment about hashtables) 

My comment is more along the need of "I don't see when you'd ever need
to do that, but please enlighten me".  Say you have two hashtables;
please show me a situation where iterating in parallel over the two
hashtables (using two imperative iterators) would be more convenient
than what you can write with OCaml's current hashtable interface (only
functional iterators).

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Chris Hecker]

>All you said is very reasonable, but I think you're generalizing the
>discussion (especially with the GUI examples) beyond what I had in
>mind, i.e. iteration over in-memory data structures.

Right, I just think they're the same issue, just at different levels of 
detail (and impact on code).  I definitely think "map" et al. are useful, 
and I didn't mean to imply otherwise.  I mean, I am trying to learn a 
functional language after all, so clearly I dig it.  :)

My main point was not about iterators specifically, it was about the flow 
control issue that got brought up when someone said "you don't need 
iterators because you have callbacks".  I was saying that the existence of 
a callback interface isn't always a good substitute for an imperative one.

 > The language provides full imperative power, and it's easy to write
>imperative iterators over concrete data structure (like François
>showed).  So, what more would you like?

I need to look at Francois' solution, so I'm not sure yet.  I'm actually 
not running into a problem right now with this anyway, so it's academic for 
me at this point, it was just something I've been wondering about since I 
started learning caml and was mentally comparing it to C++'s templates.  I 
haven't thought about the issues thoroughly, but maybe John Max Skaller can 
comment on whether Francois' iterators are "good enough" for what he was 
trying to write.

>My comment is more along the need of "I don't see when you'd ever need
>to do that, but please enlighten me".

The hashtable example wasn't mine, so I don't know about that.  There's 
also a canonical two-different-shaped-trees example, I think, but I don't 
know much about that either.  I run into this all over the place writing 
games, however.  The GUI thing was one example of a related thing that's 
higher level, but to constrain it to datastructure iteration, often times 
you'll want to do part of an iteration, and then save the state, and the do 
the next part.  So, you'll iterate over some of your AIs this frame, and 
some next frame, to manage your CPU utilization and amortize over multiple 
frames.  I don't know how you'd do that with a "functional iter" (isn't 
that a contradiction? :), although I'm sure someone will come up with 
something insane using continuations and whatnot to prove me wrong.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Chris Hecker wrote:

>
> Both of these are examples of "push versus pull" interfaces, and pull 
> just seems to work better.  Having data pushed at you means you often 
> end up buffering it on your end to manage your flow control anyway 
> unless you're just doing some trivial processing. 

This was once explained to me really well, I can't hope to give as good 
an explanation as I was given,
but I'll try: the reason 'pull' is better is that the natural place to 
put your state data is
'on the stack' and the most important case of this data is the program 
counter.

Put another way, your location in the code is the best way to encode the 
configuration
of your state data, which has something to do with the naturalness of 
block structured
programming: when you are 'here' in the code, 'these' variables are visible
and contain the state.

> I'm not saying that callback/push interfaces are always bad, 

What Francois Pottier said is correct, IMHO: callbacks are best in 
simple cases,
in particular, when there is NO state, using them clearly makes the 
simple structure
of your code evident in the syntax.

Callbacks are *also* probably best when the problem is extremely
complex.

But 'pull' interfaces shine when there is a natural heirarchical
decomposition which can be readily represented by putting
all your state data on the machine stack, and encoding
the 'variant tag' of the union of all stack states in the
natural place -- the program counter.

So: when you don't need state data, the stack doesn't help,
you might as well use a callback. And when the problem
is really complex, you might as well put all your data
into an object, and drive the system as a state machine:
this is better than mixing up the explicit and implicit
state in an arbitrary way (some on the stack, some
in a state object ..) In between, there is a large class
of tree structured problems that admit a clean solution using
subroutines and local variables.

Classic example: recursive descent parser.

Classic counter example: Earley parser (needs frames threaded
in two distinct ways, to allow one to go back and try again
after success as well as failure).

heh. It is interesting that Ocaml experts are arguing
for functional iterators -- which in fact amount
to 'goto' programming, whilst the 'pull' interface
is the essence of functional decomposition :-)
The power and utility of the machine stack is hard
to deny -- it is important enough that hardward provides it :-)

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Xavier Leroy wrote:

>
>The language provides full imperative power, and it's easy to write
>imperative iterators over concrete data structure (like François
>showed).  So, what more would you like?
>
Imperative iterators over all the library data structures :-)

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Chris Hecker wrote:

>
> I need to look at Francois' solution, so I'm not sure yet. 

It's semantically equivalent to input iterators, though the syntax is 
different,
and it misses the ability to iterate over a range with a specified endpoint.
More general iterators need a more sophisticated interface, but the 
technique
can be generalised to returning a tuple of closures [deref, increment, 
compare,
etc, rather than just 'next'] (effectively, a set of
methods on the object which is the state encapsulated in the function:
the usual functional tricky to get object orientation for free :-)

> I'm actually not running into a problem right now with this anyway, so 
> it's academic for me at this point, it was just something I've been 
> wondering about since I started learning caml and was mentally 
> comparing it to C++'s templates.  I haven't thought about the issues 
> thoroughly, but maybe John Max Skaller can comment on whether 
> Francois' iterators are "good enough" for what he was trying to write. 

heh! It's academic for me too.
I was just curious if I could build a version of STL for Ocaml.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Dave Berry]

At 10:33 05/07/2002, Francois Pottier wrote:
>My memories of STL are vague, but if an iterator is what I think it
>is, then implementing one in O'Caml is pretty straightforward. An
>iterator is a function that returns a function which maintains a
>piece of internal state. 

But can you compile it down to a single increment instruction on a pointer
(for an iterator over an array)?

Also, can you compare two iterators for equality?

Dave.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Alessandro Baretta]

John Max Skaller wrote:
> 
> [ Information about Felix ]

I have read about Felix on this list several times. I will 
look into it when I get a chance.

> Well, Ocaml has some problems too.
> I sometime want to give up on it too.
> For example: there is no dynamic loading, which is very serious.
> I really must have that.

Dynamic loading? Hmmm... What about the Dynlink library? Is 
that not what you are talking about?

> And then, there is no intermodule recursion. That is less serious,
> but it is a pain: almost all of the lookup code in Felix is forced into
> a single module, and it is a very large module. I get lost in it.
> [Lookup in Felix is MUCH more complex than Ocaml, due to overloading]

The module system in O'Caml is overall very powerful, but it 
has some weak spots. I think some significant improvements 
could be introduced with relatively little effort. O'CamlP4 
is probably the key element in my idea of "revised module 
system".

> Heh. But I have been writing Ocaml almost exclusively for 3-4 years now.
> I might be on the C++ committee .. but I don't write C++ anymore :-)

Give two or three more years and I'll be at your present 
level. I'm trying to use only O'Caml for application 
software and SQL for batch data processing tasks.

> Be fair though: C++ is better than plain C.
> It's not all that bad, considering the C compatibility constraint.
> What I learned during the process is that C is a very very bad
> language, doing almost everything wrong; this becomes evident
> when you try to extend it (i.e. to build C++) in a a source comatible
> way.

I do not consider myself an expert in either language. What 
I can tell you is that I once had to write a Delaunay 
triangulation algorithm: I tried C++ but reverted to C soon 
enough, when I got lost in the calling sequences of 
constructors and destructors--complexity was a major 
concern, so I switched to C because of its entirely obvious 
code execution path. For many other applications, where 
complexity is not the primary concern, where hierarchical 
polymorphism can be exploited--without the need for 
templates--C++ can certainly win over C.

> Felix doesn't try. It generates C++, and makes it easy to bind to C++,
> but it is a new language, with its own type system and syntax.
> 
>    http://felix.sf.net
> 
> C++ has an excuse for being a bad language.
> 
> Java does not. So if you're going to be annoyed at a language,
> pick Java: C++ advanced industrial programming significantly.
> Java has set it back at least a decade.

Listen, my experience with Java is limited, but has been 
frustrating enough. Let me repeat my previous comment: Long 
live the Caml!

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Alessandro Baretta wrote:

> Dynamic loading? Hmmm... What about the Dynlink library? Is that not 
> what you are talking about? 

Yes, but it is bytecode. I want native code dynamic loading.
I never use bytecode.

Example: I want to build an extensible lexer. I can produce the Ocaml code
I want, but I can't compile it into a shared library which I can dlopen
and get the lex function out of.  So I have to generate C, including
the action functions :-(

I had the same problem with Vyper. I had to compile the whole
standard Python library (binary support parts) into the interpreter.
Very non-modular. By nature, all Python C modules have a
uniform interface, it would have been nice to be able to mimick
the Python technology and build the C support components
as dynamically loadable Ocaml.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Alessandro Baretta]

John Max Skaller wrote:
> Alessandro Baretta wrote:
> 
>> Dynamic loading? Hmmm... What about the Dynlink library? Is that not 
>> what you are talking about? 
> 
> 
> Yes, but it is bytecode. I want native code dynamic loading.
> I never use bytecode.

Ah, that's it! I'm not familiar with native compilation 
because I feel more at ease with the extra features provided 
by the bytecode interpreter. But you are right, the native 
compilation lacks some features. I wonder if the the team 
intends to add them in some time or other.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Francois Pottier]

On Sat, Jul 06, 2002 at 12:05:30AM +0100, Dave Berry wrote:
>
> >An iterator is a function that returns a function which maintains a
> >piece of internal state. 
> 
> But can you compile it down to a single increment instruction on a pointer
> (for an iterator over an array)?

*In principle*, a compiler could perform closure analysis and determine
that the code pointer for the function `next' is known, so the closure
for `next' could be represented (in the case of an array iterator) as
a block containing a pointer to the array and a pointer to a reference
cell containing the current index. The code for the function could be
inlined and would consist in fetching both pieces of information, reading
the array and updating the reference cell.

*In principle*, a compiler could perform escape analysis and allocate the
reference cell on the stack, so accessing and updating it would be cheaper.

*In principle*, a compiler could perform must-alias analysis and find out
that the address of the array is already available elsewhere, thus obviating
the need to create a closure entirely.

Some ML compilers perform some of these optimizations. O'Caml performs none,
as far as I know; they are tricky to implement, especially in combination.
I'd be curious to see how C++ achieves this.

> Also, can you compare two iterators for equality?

What is the semantics of such a comparison?

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[John Max Skaller]

Francois Pottier wrote:

>On Sat, Jul 06, 2002 at 12:05:30AM +0100, Dave Berry wrote:
>
>>>An iterator is a function that returns a function which maintains a
>>>piece of internal state. 
>>>
>>But can you compile it down to a single increment instruction on a pointer
>>(for an iterator over an array)?
>>

>
>Some ML compilers perform some of these optimizations. O'Caml performs none,
>as far as I know; they are tricky to implement, especially in combination.
>I'd be curious to see how C++ achieves this.
>
Simple: templates use 'textual substitution'. An array iterator IS a 
pointer.
So there is no analysis to do. They're also good at optimising classes
with a single data member (int, pointer, etc).

The one that C++ compilers find hard is to see that the instantiations:

    copy<int*,int*,int*> ...
    copy<unisgned int*,unsigned int*, unsigned int*>

can share the same implementation: programmers usually suppress code bloat
on template instantiation using wrapping tricks, knowing that compilers
aren't yet very smart at it.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Streams

[Diego Olivier Fernandez Pons]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3297 bytes --]

    Bonjour,

Dans le cadre de la librairie de structures de données EDiSon
(Efficient Data Structures, Okasaki 2000) que je suis en train de
porter et d'adapter (pour l'instant 500k, prérelease prévue en
septembre), j'ai réalisé plusieurs types de listes à évaluation
retardée.

La première remarque est que j'ai eu beaucoup de mal à trouver de la
documentation à ce sujet :

- une implémentation très simple dans ML for the working programmer
(Paulson 1991, 1996)

- une implémentation par Pierre Weiss pour le problème des 8 dames sur
l'échiquer dans la librairie d'exemples d'Objective Caml

- l'implémentation de Daniel de Rauglaudre, cette dernière ayant
l'inconvénient de s'appuyer sur des fonctions non documentées de Caml,
mais il faut reconnaître que le code est parfaitement lisible et que
l'on devine à peu près ce qui se passe. C'est de surcroît la seule
implémentation à prendre en compte les fonctions génératrices et la
concaténation

- un article de Wadler (1997) sur l'implémentation de l'évaluation
retardée dans les langages stricts, qui a la particularité d'enfoncer
des portes ouvertes (ne considérant que les deux implémentations
traditionnelles) et de parler d'une implémentation particulièrement
efficace en SML/NJ qui serait en cours de développement, or la version
CVS de SML/NJ (110.41) ne comporte rien de tout cela, sinon le
traditionnel module Lazy

Enfin le rapport de recherche de Didier Remy et Daniel de
Rauglaudre (1992) n'est disponible que sous forme papier.


Voici donc mes questions :

- serait-il possible de documenter un peu le module obj ? Peut-être
est-ce une mauvaise idée, dans la mesure où cela pourrait permettre à
des utilisateurs non avertis d'écrire du code dangereux

j'ai écrit une version de listes à évaluation retardée qui simule le
fonctionnement des streams de Caml (fichier joint streamVI.ml)

type 
  'a stream = { mutable data : 'a streamCell } and
  'a streamCell =
    | Nil
    | Cons of 'a * 'a stream
    | Append of 'a stream * 'a stream
    | Delayed of (unit -> 'a stream)
    | Generator of int * (int -> int) * (int -> 'a)

L'inconvénient est que l'on perd le polymorphisme de la liste vide.
N'y a t-il aucun moyen de s'en sortir en utilisant du Caml
conventionnel ?

ensuite je voudrais abstraire le type int du constreur Generator afin
que l'utilisateur puisse indicer sa fonction génératrice par le type
de son choix :

   | Generator of 'k * (k' -> 'k) * ('k -> 'a)

seulement si je déclare un type ('k, 'a) streamCell alors on ne peut
plus utiliser des listes d'indexes de type différent alors qu'elles
sont "logiquement" compatibles puisque le type 'k ne sert qu'a
construire les nouvelles valeurs de type 'a

comment limiter "l'étendue" du type 'k au seul constructeur
[Generator] ?

- la forme spéciale lazy ressemble très fortement à la fonction lazy_
ci-dessous mis à part qu'elle n'évalue pas ses arguments

(* OCaml 3.04 *)
let lazy_ = function x -> ref (Lazy.Delayed (function () -> x))

Quels seraient les inconvénients (théoriques ? pratiques ?) d'une
forme spéciale [uneval_] qui serait équivalente à function () ->,
autrement dit

   uneval : 'a -> (unit -> 'a)
   uneval_ x <=> function () -> x  

        Diego Olivier

[-- Attachment #2: streams --]
[-- Type: APPLICATION/octet-stream, Size: 8911 bytes --]

Re: [Caml-list] Streams

[Alain Frisch]

Hello Diego,

On Fri, 2 Aug 2002, Diego Olivier Fernandez Pons wrote:

> - serait-il possible de documenter un peu le module obj ? Peut-être
> est-ce une mauvaise idée, dans la mesure où cela pourrait permettre à
> des utilisateurs non avertis d'écrire du code dangereux

Using Obj safely requires to know a little bit about the runtime
representation of objects; and once you have this knowledge (after
reading the section on interfacing with C in the manual, or the OCaml
runtime source files), the module interface should be self-explanatory.

> L'inconvénient est que l'on perd le polymorphisme de la liste vide.
> N'y a t-il aucun moyen de s'en sortir en utilisant du Caml
> conventionnel ?

You have to explain to the typechecker that the Nil stream will
never be patched:

type
  'a stream =
     | Nil
     | Patchable of 'a stream_patchable
and 'a stream_patchable = { mutable data : 'a streamCell }
and
  'a streamCell =
    | Cons of 'a * 'a stream
    | Append of 'a stream * 'a stream
    | Delayed of (unit -> 'a stream)
    | Generator of int * (int -> int) * (int -> 'a)

Of course, this is less efficient (one would like to write
as in other ML dialects,

type
  'a stream =
     | Nil
     | Patchable of { mutable data : 'a streamCell }

[see http://pauillac.inria.fr/~lefessan/src/ for such a patch
to OCaml 2.02]
...
Any plan to introduce this syntax in OCaml ?
)

> ensuite je voudrais abstraire le type int du constreur Generator afin
> que l'utilisateur puisse indicer sa fonction génératrice par le type
> de son choix :
>
>    | Generator of 'k * (k' -> 'k) * ('k -> 'a)
>
> seulement si je déclare un type ('k, 'a) streamCell alors on ne peut
> plus utiliser des listes d'indexes de type différent alors qu'elles
> sont "logiquement" compatibles puisque le type 'k ne sert qu'a
> construire les nouvelles valeurs de type 'a
>
> comment limiter "l'étendue" du type 'k au seul constructeur
> [Generator] ?

Couln't you just abstract the generator outside the stream ?

let gen ini f =
  let state = ref ini in
  (fun () -> state := f !state),
  (fun () -> !state);;

Do you really need to keep the current state visible ?

> - la forme spéciale lazy ressemble très fortement à la fonction lazy_
> ci-dessous mis à part qu'elle n'évalue pas ses arguments
>
> (* OCaml 3.04 *)
> let lazy_ = function x -> ref (Lazy.Delayed (function () -> x))
>
> Quels seraient les inconvénients (théoriques ? pratiques ?) d'une
> forme spéciale [uneval_] qui serait équivalente à function () ->,
> autrement dit
>
>    uneval : 'a -> (unit -> 'a)
>    uneval_ x <=> function () -> x

What do you mean by "forme spéciale" ?  If you just want syntactic
sugar, you can implement it yourself with Camlp4.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Streams

[Diego Olivier Fernandez Pons]

    Alain,

> type
>   'a stream =
>      | Nil
>      | Patchable of 'a stream_patchable
> and 'a stream_patchable = { mutable data : 'a streamCell }
> and
>   'a streamCell =
>     | Cons of 'a * 'a stream
>     | Append of 'a stream * 'a stream
>     | Delayed of (unit -> 'a stream)
>     | Generator of int * (int -> int) * (int -> 'a)

Mes listes à évaluation retardées contrairement à celles de Rauglaudre
supportent (quasi) totalement les fonctions génératrices, en
particulier leur concaténation.

Quand Generator ou Delayed vont envoyer une exception [Empty] ou une
liste vide [Nil] respectivement, il faut que je mémorise la valeur, ce
qui empêche la construction que vous proposez à moins d'utiliser
Append (Nil, Nil) ou un nouveau constructeur NilBis dans StreamCell.

voici ma fonction force

let rec force = function stream ->
 (match stream.data with
   | Delayed f -> let x = f () in stream.data <- x.data
   | Generator (index, succ, gen) ->
      (try
         let next_index = succ index in
           stream.data <- Cons (gen next_index, 
              makeStream (Generator (next_index, succ, gen)))
        with Empty -> stream.data <- Nil)
   etc.
  ) ;
  stream 

En fait nous voudrions mimer le mieux possible le comportement des
listes de base, avec une unique représentation de la liste vide :
# []
- : 'a list = []
# let (_ :: tail) = [1] in tail
- : int list = []

# { data = Nil }
- : '_a stream = { data = Nil }

> Couln't you just abstract the generator outside the stream ?
> 
> let gen ini f =
>   let state = ref ini in
>   (fun () -> state := f !state),
>   (fun () -> !state);;
> 
> Do you really need to keep the current state visible ?

Cette représentation des générateurs a été choisie afin de pouvoir
implémenter (relativement) efficacement les fonctions take et drop.

J'ai gardé l'indexe courant visible car c'était fait ainsi dans
l'implémentation de Rauglaudre, en effet dans les streams de Caml
l'indexe compte simultanément le nombre d'états consommés : 

la fonction drop k applique simplement succ^k sur l'indexe,

la fonction take k remplace succ par la version suivante
  let count = ref k in
  let succ' = function index ->
    if !count = 0 then raise Empty
    else decr count ; succ index

L'idée est essentiellement que décaler d'un indice est plus rapide que
générer une valeur avec evenutellement une fonction triviale si ce
n'est pas le cas 'a * 'a -> 'a * 'a -> 'a

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: generic programming

[Eray Ozkural]

On Wednesday 03 July 2002 23:34, Alessandro Baretta wrote:
>
> Templates are "nasty" citizens of the C++ world. I've had
> *so* many problems tracking down bugs in code using STL
> templates. Basically, the "write once, compile many"
> strategy of C++ yields situations where the semantics of the
> algorithms coded in a template depends upon the type
> parameter you pass to the template itself. Abominable.
>
> Stick to Caml: "Write Once, Compile Once, Link Many".

Compared to Ocaml module system, C++ generics is a weakling. The use of 
template classes or functions is prohibitive with respect to compilation 
time, build size and code maintenance. On the other hand, the type system of 
ocaml combined with functors/structures makes generic programming a dream 
come true. I cannot think of a code in C++ that can abstract over a 
particular implementation of, for instance, a Set ADT well enough. Just *try* 
to write your own alternative set implementation for STL. :)

Cheers,

-- 
Eray Ozkural <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners