* Re: [Caml-list] Re: generic programming
2002-07-03 17:29 ` Chris Hecker
@ 2002-07-03 20:07 ` Oleg
2002-07-03 20:34 ` Alessandro Baretta
2002-07-03 21:55 ` Peter Wood
` (2 subsequent siblings)
3 siblings, 1 reply; 31+ messages in thread
From: Oleg @ 2002-07-03 20:07 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Re: generic programming
2002-07-03 20:07 ` Oleg
@ 2002-07-03 20:34 ` Alessandro Baretta
2002-07-04 15:33 ` John Max Skaller
2002-10-15 0:10 ` Eray Ozkural
0 siblings, 2 replies; 31+ messages in thread
From: Alessandro Baretta @ 2002-07-03 20:34 UTC (permalink / raw)
To: Oleg, Ocaml
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-03 20:34 ` Alessandro Baretta
@ 2002-07-04 15:33 ` John Max Skaller
[not found] ` <3D249B27.5080807@baretta.com>
2002-10-15 0:10 ` Eray Ozkural
1 sibling, 1 reply; 31+ messages in thread
From: John Max Skaller @ 2002-07-04 15:33 UTC (permalink / raw)
To: Alessandro Baretta; +Cc: Oleg, Ocaml
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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Re: generic programming
2002-07-03 20:34 ` Alessandro Baretta
2002-07-04 15:33 ` John Max Skaller
@ 2002-10-15 0:10 ` Eray Ozkural
1 sibling, 0 replies; 31+ messages in thread
From: Eray Ozkural @ 2002-10-15 0:10 UTC (permalink / raw)
To: Ocaml
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-03 17:29 ` Chris Hecker
2002-07-03 20:07 ` Oleg
@ 2002-07-03 21:55 ` Peter Wood
2002-07-04 2:02 ` james woodyatt
2002-07-04 15:18 ` John Max Skaller
2002-07-05 8:33 ` Francois Pottier
3 siblings, 1 reply; 31+ messages in thread
From: Peter Wood @ 2002-07-03 21:55 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-03 21:55 ` Peter Wood
@ 2002-07-04 2:02 ` james woodyatt
0 siblings, 0 replies; 31+ messages in thread
From: james woodyatt @ 2002-07-04 2:02 UTC (permalink / raw)
To: Peter Wood; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-03 17:29 ` Chris Hecker
2002-07-03 20:07 ` Oleg
2002-07-03 21:55 ` Peter Wood
@ 2002-07-04 15:18 ` John Max Skaller
2002-07-05 8:42 ` Francois Pottier
2002-07-05 8:33 ` Francois Pottier
3 siblings, 1 reply; 31+ messages in thread
From: John Max Skaller @ 2002-07-04 15:18 UTC (permalink / raw)
To: Chris Hecker; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Re: generic programming
2002-07-04 15:18 ` John Max Skaller
@ 2002-07-05 8:42 ` Francois Pottier
2002-07-05 9:25 ` Xavier Leroy
0 siblings, 1 reply; 31+ messages in thread
From: Francois Pottier @ 2002-07-05 8:42 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-05 8:42 ` Francois Pottier
@ 2002-07-05 9:25 ` Xavier Leroy
2002-07-05 9:57 ` Chris Hecker
0 siblings, 1 reply; 31+ messages in thread
From: Xavier Leroy @ 2002-07-05 9:25 UTC (permalink / raw)
To: Francois Pottier; +Cc: caml-list
> 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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Re: generic programming
2002-07-05 9:25 ` Xavier Leroy
@ 2002-07-05 9:57 ` Chris Hecker
2002-07-05 13:54 ` Xavier Leroy
2002-07-05 19:31 ` John Max Skaller
0 siblings, 2 replies; 31+ messages in thread
From: Chris Hecker @ 2002-07-05 9:57 UTC (permalink / raw)
To: Xavier Leroy, Francois Pottier; +Cc: caml-list
>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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-05 9:57 ` Chris Hecker
@ 2002-07-05 13:54 ` Xavier Leroy
2002-07-05 17:59 ` Chris Hecker
2002-07-05 19:33 ` John Max Skaller
2002-07-05 19:31 ` John Max Skaller
1 sibling, 2 replies; 31+ messages in thread
From: Xavier Leroy @ 2002-07-05 13:54 UTC (permalink / raw)
To: Chris Hecker; +Cc: Francois Pottier, caml-list
> [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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Re: generic programming
2002-07-05 13:54 ` Xavier Leroy
@ 2002-07-05 17:59 ` Chris Hecker
2002-07-05 20:31 ` John Max Skaller
2002-07-05 19:33 ` John Max Skaller
1 sibling, 1 reply; 31+ messages in thread
From: Chris Hecker @ 2002-07-05 17:59 UTC (permalink / raw)
To: Xavier Leroy; +Cc: Francois Pottier, caml-list
>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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-05 17:59 ` Chris Hecker
@ 2002-07-05 20:31 ` John Max Skaller
0 siblings, 0 replies; 31+ messages in thread
From: John Max Skaller @ 2002-07-05 20:31 UTC (permalink / raw)
To: Chris Hecker; +Cc: Xavier Leroy, Francois Pottier, caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-05 13:54 ` Xavier Leroy
2002-07-05 17:59 ` Chris Hecker
@ 2002-07-05 19:33 ` John Max Skaller
1 sibling, 0 replies; 31+ messages in thread
From: John Max Skaller @ 2002-07-05 19:33 UTC (permalink / raw)
To: Xavier Leroy; +Cc: Chris Hecker, Francois Pottier, caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-05 9:57 ` Chris Hecker
2002-07-05 13:54 ` Xavier Leroy
@ 2002-07-05 19:31 ` John Max Skaller
1 sibling, 0 replies; 31+ messages in thread
From: John Max Skaller @ 2002-07-05 19:31 UTC (permalink / raw)
To: Chris Hecker; +Cc: Xavier Leroy, Francois Pottier, caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-03 17:29 ` Chris Hecker
` (2 preceding siblings ...)
2002-07-04 15:18 ` John Max Skaller
@ 2002-07-05 8:33 ` Francois Pottier
2002-07-05 23:05 ` Dave Berry
3 siblings, 1 reply; 31+ messages in thread
From: Francois Pottier @ 2002-07-05 8:33 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Re: generic programming
2002-07-05 8:33 ` Francois Pottier
@ 2002-07-05 23:05 ` Dave Berry
2002-07-08 9:54 ` Francois Pottier
2002-08-02 14:49 ` [Caml-list] Streams Diego Olivier Fernandez Pons
0 siblings, 2 replies; 31+ messages in thread
From: Dave Berry @ 2002-07-05 23:05 UTC (permalink / raw)
To: Francois.Pottier, caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-05 23:05 ` Dave Berry
@ 2002-07-08 9:54 ` Francois Pottier
2002-07-08 15:49 ` John Max Skaller
2002-08-02 14:49 ` [Caml-list] Streams Diego Olivier Fernandez Pons
1 sibling, 1 reply; 31+ messages in thread
From: Francois Pottier @ 2002-07-08 9:54 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Re: generic programming
2002-07-08 9:54 ` Francois Pottier
@ 2002-07-08 15:49 ` John Max Skaller
0 siblings, 0 replies; 31+ messages in thread
From: John Max Skaller @ 2002-07-08 15:49 UTC (permalink / raw)
To: Francois.Pottier; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread
* [Caml-list] Streams
2002-07-05 23:05 ` Dave Berry
2002-07-08 9:54 ` Francois Pottier
@ 2002-08-02 14:49 ` Diego Olivier Fernandez Pons
2002-08-02 15:29 ` Alain Frisch
1 sibling, 1 reply; 31+ messages in thread
From: Diego Olivier Fernandez Pons @ 2002-08-02 14:49 UTC (permalink / raw)
To: caml-list
[-- 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 --]
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Streams
2002-08-02 14:49 ` [Caml-list] Streams Diego Olivier Fernandez Pons
@ 2002-08-02 15:29 ` Alain Frisch
2002-08-03 14:19 ` Diego Olivier Fernandez Pons
0 siblings, 1 reply; 31+ messages in thread
From: Alain Frisch @ 2002-08-02 15:29 UTC (permalink / raw)
To: Diego Olivier Fernandez Pons; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Streams
2002-08-02 15:29 ` Alain Frisch
@ 2002-08-03 14:19 ` Diego Olivier Fernandez Pons
0 siblings, 0 replies; 31+ messages in thread
From: Diego Olivier Fernandez Pons @ 2002-08-03 14:19 UTC (permalink / raw)
To: Alain Frisch; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 31+ messages in thread