[Caml-list] Bigarray map & set/get (long)

[Caml-list] Bigarray map & set/get (long)

[Christophe TROESTLER]

Hi everybody,

I am in the process of writing some numerical code (nonlinear ODE/PDE
solvers with C^1 finite elements).  I would like to share some remarks
and ask some questions about the Bigarray module.  As an example of
the operations I need, I chose the matrix assignment

OUT <- A + B .* C

where .* denotes elementwise multiplication.  Direct implementation in
CAML is

let mac out a b c =
  for i = 1 to Array2.dim1 a do
    for j = 1 to Array2.dim2 a do
      out.{i,j} <- a.{i,j} +. b.{i,j} *. c.{i,j}
    done
  done;
  out

Typical matrices are of dimension 1000x1000 and above and computations
like the previous one may need to be repeated several thousand of
times.  Now, I also wrote such computation in C (I mean C called from
CAML).  On my machine (Athlon 1GHz, 512Mb) for a matrix of size
1300x1300, the C version run in 0.16 sec while the above CAML code
takes 2.14 secs; that is, about 13 times more.  Now, if I specify the
full type of the arrays I want (here

type mat =
  (float, Bigarray.float64_elt, Bigarray.fortran_layout) Bigarray.Array2.t

) then the code runs much faster: 0.87 sec (still more than 5 times
the C version unfortunately).  That sould be mentioned in
http://caml.inria.fr/ocaml/speed.html IMHO -- and maybe this page
could be better advertised?.

I tried two other things.  First I wrote a callback version, that is a
"map" function written in C that calls the CAML function passed as
argument.  Its interface looks like:

val map3 :
  out:mat -> (float -> float -> float -> float) -> mat -> mat -> mat -> mat

which allows to write the previous function [mac out a b c] as

map3 ~out (fun a b c -> a +. b *. c) a b c

Now, this does not work so bad (considering it is very naively
written): 0.35 sec (about twice as much as C).  I also wrote in C safe
and unsafe (and specialized to mat) versions and set/get but the the
result is not what is expected: 1.16 sec (about 7 times slower than C)
with little difference between safe/unsafe.

So (eventually :-) here a my questions:

* The Lacaml modules does contain some "matlab like" operations on
  vectors (and, in the future, on 2D arrays).  That will make easy to
  write fast code for this example.  However, one thing that will
  always be necessary is to make CAML functions act on arrays.
  Therefore why not add some carefully designed "map" and "fold"
  functions to the Bigarray module.  Such functions would need making
  bound checks and checks for the type of the array only once, before
  the loop.  To be useful they would need to have optional arguments
  like ~from (index of the start) ~inc (increment, default [|1;
  1;... |]) ~to (max index).  ~out can also be made optional if one
  wants to match more closely the map/fold of Array but it is
  necessary to be able to specify it -- and it may be one of the input
  arrays.

  In the same vein, what can be done to write a faster map-like
  function?

* Are bound checks responsible for the difference between the "fully
  typed" version [mac (out:mat) (a:mat) (b:mat) (c:mat)] and C??  How
  to write specialized (fully typed) versions of set/get (possibly
  unsafe) that will run as fast as C?  What is the difference with the
  set/get for Arrays that allows them to run as fast as C (for a float
  array of the size 1690000 = 1300 * 1300).

Have a good weekend,
Christophe


P.S.  Is it possible to write a "let module A = B" (i.e., module
renaming) in camlp4?  That is very useful when one wants to be able to
switch between different modules with the same interface but do not
want to open them (for name conflicts reasons for example).
-------------------
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] Bigarray map & set/get (long)

[Daniel de Rauglaudre]

Hi,

On Fri, Jul 19, 2002 at 03:59:40PM +0200, Christophe TROESTLER wrote:

> P.S.  Is it possible to write a "let module A = B" (i.e., module
> renaming) in camlp4?  That is very useful when one wants to be able to
> switch between different modules with the same interface but do not
> want to open them (for name conflicts reasons for example).

It may be possible to attack this question by syntax in some cases,
but it is mainly semantics: in particular, what happens if a module
named "A" is defined further? We have to take care of "scopes", which
is semantics.

What do you mean by "switch between different modules with the same
interface"? Can you give a specific example?

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
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] Bigarray map & set/get (long)

[Oleg]

On Friday 19 July 2002 09:59 am, Christophe TROESTLER wrote:
> let mac out a b c =
>   for i = 1 to Array2.dim1 a do
>     for j = 1 to Array2.dim2 a do
>       out.{i,j} <- a.{i,j} +. b.{i,j} *. c.{i,j}
>     done
>   done;
>   out

Chris, 

If you are using fortran layout (column-major) why are you incrementing rows 
in the inner-most loop? (AFAICR this can make a big difference with GCC, 
perhaps O'Caml too). Also, each loop seems to contain a call to function 
Array2.dim2. Can't this number be cached? Thirdly, does bigarray access check 
bounds? Can this be turned off? And finally, you might try to experiment with 
0-based indexing [1], it may turn out to be faster.

HTH
Let me/us know how this turns out,
Oleg

[1] I absolutely abhor 0-based indexing in most modern languages
-------------------
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] Bigarray map & set/get (long)

[Xavier Leroy]

> Now, if I specify the
> full type of the arrays I want (here
> 
> type mat =
>   (float, Bigarray.float64_elt, Bigarray.fortran_layout) Bigarray.Array2.t
> 
> ) then the code runs much faster: 0.87 sec (still more than 5 times
> the C version unfortunately).  That sould be mentioned in
> http://caml.inria.fr/ocaml/speed.html IMHO -- and maybe this page
> could be better advertised?.

It should be mentioned, but really this is the same phenomenon as for
regular arrays: efficient array access code cannot be generated unless
the full type of the (big-) array is statically known.

> * The Lacaml modules does contain some "matlab like" operations on
>   vectors (and, in the future, on 2D arrays).  That will make easy to
>   write fast code for this example.  However, one thing that will
>   always be necessary is to make CAML functions act on arrays.

In the applications for which Bigarray was initially intended, the
Caml code that manipulates directly the bigarrays isn't
time-critical: the time-critical computations are done by external
libraries such as BLAS, Lapack, etc.  Your matrix multiplication code
is a good example: if you care about its performances, then you need
to make it a lot more sophisticated so that it will be cache-friendly
(e.g. blocking); better use an existing, well-tuned C or Fortran
implementation than try to do your own in Caml.

Put it another way, bigarrays are oriented towards efficient
communications with external libraries, not towards writing efficient
numerical code in Caml; for the latter purpose, regular arrays are
actually more efficient.

> * Are bound checks responsible for the difference between the "fully
>   typed" version [mac (out:mat) (a:mat) (b:mat) (c:mat)] and C??

Partially responsible, but another source of overhead is the
address computations when accessing a big array: these involve linear
formulas of the form X * dim1(a) + Y, which are not optimized inside
loops, while most C and Fortran compilers do extensive optimizations
for this kind of computations (hoisting of loop-invariant code,
transformation of multiplications into iterated additions, etc).

> P.S.  Is it possible to write a "let module A = B" (i.e., module
> renaming) in camlp4?

That's a standard feature of the OCaml module language; it's written
"module A = B".  What a surprise :-)

- 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] Bigarray map & set/get

[Christophe TROESTLER]

On Mon, 22 Jul 2002, Xavier Leroy <xavier.leroy@inria.fr> wrote:
> 
> > [...] one thing that will always be necessary is to make CAML
> > functions act on arrays.
> 
> [...] the time-critical computations are done by external libraries
> such as BLAS, Lapack, etc.  [...]

Ok, that's reasonable for arithmetic operations or standard routines
like linear equation solving --- and that's what I am moving towards.
Now, the code uses all along some arbitrary functions f: float ->
float, g : float -> float -> float,... that allow to run the program
for a large class of equations.  Of course, sooner or later I need to
perform some operations on the bigarrays that involve these functions,
the simplest form of which is

     map : 
       ?out:('a, 'b, 'c) Bigarray.Array1.t ->
       ('a -> 'd) -> ('a, 'b, 'c) Array1.t -> ('d, 'b, 'c) Array1.t

(the same as in Array except one can specify the output matrix).  My
questions are:

* Wouldn't these kind of functions be great to have in the standard
  Bigarray module?  (They would also make it closer to the Array one,
  hence easing the transition when needed.)

* If I want to implement them myself, are there any hints to reach
  maximal efficiency?  (Especially w.r.t. callbacks.)

Regards,
ChriS

P.S. Since my code is experimental, efficiency it not the primary
concern.  It just doesn't have to be too slow... (we still need to
make a great deal of runs to have an insight...)
-------------------
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] Bigarray map & set/get

[Christophe TROESTLER]

Thanks for your suggestions.  Here are the results.

On Sat, 20 Jul 2002, Oleg <oleg_inconnu@myrealbox.com> wrote:
> 
> If you are using fortran layout (column-major) why are you
> incrementing rows in the inner-most loop? (AFAICR this can make a
> big difference with GCC, perhaps O'Caml too).

Ooops!  You are correct this make the times more reasonable (about 2
to 3 times C).

> Also, each loop seems to contain a call to function Array2.dim2.
> Can't this number be cached?

Well, that in fact has the opposite effect of increasing very slightly
the running time.

> Thirdly, does bigarray access check bounds? Can this be turned off?

It does.  And I don't think it can be turned off.

> And finally, you might try to experiment with 0-based indexing [1],
> it may turn out to be faster.

Very same running times.

Cheers,
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] Bigarray map & set/get (long)

[Fernando Alegre]

On Mon, Jul 22, 2002 at 11:31:36AM +0200, Xavier Leroy wrote:

> Put it another way, bigarrays are oriented towards efficient
> communications with external libraries, not towards writing efficient
> numerical code in Caml; for the latter purpose, regular arrays are

However, the current implementation of bigarrays does not cooperate
with libraries that need to manage the memory allocation in special ways.
Some efficient libraries need special malloc and free that align the data
for faster cache use. But current bigarrays are unsafe in that kind of
setting. We had modify the source code of bigarrays (alloc and update_proxy)
so that proxies are also updated for externally allocated bigarrays, and
created custom bigarray_alloc and bigarray_finalize.


> 
> > * Are bound checks responsible for the difference between the "fully
> >   typed" version [mac (out:mat) (a:mat) (b:mat) (c:mat)] and C??
> 
> Partially responsible, but another source of overhead is the
> address computations when accessing a big array: these involve linear
> formulas of the form X * dim1(a) + Y, which are not optimized inside
> loops, while most C and Fortran compilers do extensive optimizations
> for this kind of computations (hoisting of loop-invariant code,
> transformation of multiplications into iterated additions, etc).

I have done somewhat extensive tests, and my results indicate that bound
checks are in fact the main source of slowdown. Address computation seemed
negligible in comparison. It was also surprising that setting a value was
much faster than retrieving it. Any ideas why this is so?

Thanks,

       Fernando
       
-------------------
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] Bigarray map & set/get (long)

[Chris Hecker]

>In the applications for which Bigarray was initially intended, the
>Caml code that manipulates directly the bigarrays isn't
>time-critical: the time-critical computations are done by external
>libraries such as BLAS, Lapack, etc.  Your matrix multiplication code
>is a good example: if you care about its performances, then you need
>to make it a lot more sophisticated so that it will be cache-friendly
>(e.g. blocking); better use an existing, well-tuned C or Fortran
>implementation than try to do your own in Caml.

The problem with this is that sometimes you don't want the discontinuity 
and inconvenience of calling to C.  Obviously, it'd be nice if we could do 
everything in ocaml from a simplicity and consistency standpoint, assuming 
it's not an infinite amount of work to get there.

There is an important middle ground between "not caring about speed" and 
"needing the highest end BLAS performance", and since CPUs are making bad 
code fast faster than they're making good code fast, the middle ground is 
moving higher up the importance ladder, and getting easier to attain.

When I looked at it a few months ago, there actually only seem to be a few 
things that are needed to make bigarrays as efficient as C float * arrays 
for most operations.  I don't have my list handy, but when I get around to 
optimizing my game I hope to implement some of these into the 
compiler.  Off the top of my head, I think bounds checking made a 
measurable difference, as did the indirection in the way the bigarray 
header structures are stored on the heap (even when they're going through 
the optimized path in the compiler), and it would be easier to write a 
lapack-style modularized matrix library if there was the concept of taking 
a "pointer" into a 1D bigarray that was lower level than the currently 
exising slice and subarray stuff (so that you can pass a pointer to a 
submatrix + a stride around).

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] Bigarray map & set/get (long)

[Xavier Leroy]

> The problem with this is that sometimes you don't want the discontinuity 
> and inconvenience of calling to C.  Obviously, it'd be nice if we could do 
> everything in ocaml from a simplicity and consistency standpoint, assuming 
> it's not an infinite amount of work to get there.
> 
> There is an important middle ground between "not caring about speed" and 
> "needing the highest end BLAS performance", and since CPUs are making bad 
> code fast faster than they're making good code fast, the middle ground is 
> moving higher up the importance ladder, and getting easier to attain.

Agreed, but in this case (as I mentioned in my earlier post) you'd get
better performance by just using regular float arrays rather than bigarrays.(*)
Thus, I recommend using bigarrays only when interfacing with C or
Fortran numerical code.

- Xavier Leroy

(*) This isn't quite right: on some platforms (PowerPC, Sparc, Mips),
a 1D bigarray can actually be slightly more efficient than a float
array, because of memory alignment properties.  But this isn't true on
the Pentium.
-------------------
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] Bigarray map & set/get (long)

[Chris Hecker]

>Agreed, but in this case (as I mentioned in my earlier post) you'd get
>better performance by just using regular float arrays rather than 
>bigarrays.(*)
>Thus, I recommend using bigarrays only when interfacing with C or
>Fortran numerical code.

Sure, but what a pain if you want to do both (say, do some math on an array 
of floats in caml and then pass them to a graphics api as vertices).  Or, 
you start with an algorithm in caml and then slowly need to move parts of 
it to C/asm.  It would clearly be better if there was a single uniform way 
to do things that was "optimal" (or close) for both situations.  It seems 
that the bigarray stuff is not far off from this, as I said.  There seems 
to be some nice low hanging fruit that could make a big difference in the 
native compiler with bigarrays.

Anyway, I'll look into it again and do some experiments at some point and 
see what I come up with.  I'd much rather have the caml team working on 
harder more higher level stuff that I'd have no prayer of being able to 
do[*], anyway.

Chris

[*] My current list of needed/wanted language features:

1. operator overloading/generics for making math less ugly and painful
2. module recursion
3. views for pattern matching abstract data types

I added views to my want-list relatively recently (6 months ago?) as I 
started trying to do more interesting stuff.  I can't believe the conflict 
between wanting to pattern match like you're supposed to in ml and wanting 
to abstract data types like you're supposed to in ml doesn't get more 
attention in the functional programming community.  It seems like a glaring 
problem, but maybe I'm missing something.


-------------------
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] Bigarray map & set/get (long)

[Michael Vanier]

> Date: Thu, 25 Jul 2002 11:11:08 -0700
> From: Chris Hecker <checker@d6.com>
> 
> [*] My current list of needed/wanted language features:
> 
> 1. operator overloading/generics for making math less ugly and painful
> 2. module recursion
> 3. views for pattern matching abstract data types
> 
> I added views to my want-list relatively recently (6 months ago?) as I 
> started trying to do more interesting stuff.  I can't believe the conflict 
> between wanting to pattern match like you're supposed to in ml and wanting 
> to abstract data types like you're supposed to in ml doesn't get more 
> attention in the functional programming community.  It seems like a glaring 
> problem, but maybe I'm missing something.
> 

Could you give an example?  I'm a bit fuzzy on what you mean by this.

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

wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Chris Hecker]

>Could you give an example?  I'm a bit fuzzy on what you mean by this.

By which?  Views?

http://www.google.com/search?q=views+pattern+matching+abstract+data+types

Chris


At 22:44 7/25/02 -0700, Michael Vanier wrote:

> > Date: Thu, 25 Jul 2002 11:11:08 -0700
> > From: Chris Hecker <checker@d6.com>
> >
> > [*] My current list of needed/wanted language features:
> >
> > 1. operator overloading/generics for making math less ugly and painful
> > 2. module recursion
> > 3. views for pattern matching abstract data types
> >
> > I added views to my want-list relatively recently (6 months ago?) as I
> > started trying to do more interesting stuff.  I can't believe the conflict
> > between wanting to pattern match like you're supposed to in ml and wanting
> > to abstract data types like you're supposed to in ml doesn't get more
> > attention in the functional programming community.  It seems like a 
> glaring
> > problem, but maybe I'm missing something.
> >
>
>Could you give an example?  I'm a bit fuzzy on what you mean by this.
>
>Mike
>-------------------
>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

-------------------
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: wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Michael Vanier]

Yes, I meant about views.  Thanks.  Here's a good reference:

http://citeseer.nj.nec.com/5295.html

Mike

> Date: Fri, 26 Jul 2002 15:33:06 -0700
> From: Chris Hecker <checker@d6.com>
> 
> >Could you give an example?  I'm a bit fuzzy on what you mean by this.
> 
> By which?  Views?
> 
> http://www.google.com/search?q=views+pattern+matching+abstract+data+types
> 
> Chris
> 
> 
> At 22:44 7/25/02 -0700, Michael Vanier wrote:
> 
> > > Date: Thu, 25 Jul 2002 11:11:08 -0700
> > > From: Chris Hecker <checker@d6.com>
> > >
> > > [*] My current list of needed/wanted language features:
> > >
> > > 1. operator overloading/generics for making math less ugly and painful
> > > 2. module recursion
> > > 3. views for pattern matching abstract data types
> > >
> > > I added views to my want-list relatively recently (6 months ago?) as I
> > > started trying to do more interesting stuff.  I can't believe the conflict
> > > between wanting to pattern match like you're supposed to in ml and wanting
> > > to abstract data types like you're supposed to in ml doesn't get more
> > > attention in the functional programming community.  It seems like a 
> > glaring
> > > problem, but maybe I'm missing something.
> > >
> >
> >Could you give an example?  I'm a bit fuzzy on what you mean by this.
> >
> >Mike
> >-------------------
> >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
> 
> 
-------------------
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: wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Chris Hecker]

>Yes, I meant about views.  Thanks.  Here's a good reference:
>http://citeseer.nj.nec.com/5295.html

The Okasaki paper is readable, too.

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: wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Michael Vanier]

> Date: Fri, 26 Jul 2002 15:44:30 -0700
> From: Chris Hecker <checker@d6.com>
> 
> 
> >Yes, I meant about views.  Thanks.  Here's a good reference:
> >http://citeseer.nj.nec.com/5295.html
> 
> The Okasaki paper is readable, too.
> 
> Chris
> 
> 

I can't find a link to any papers by Okasaki on this subject.

Mike
-------------------
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: wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Chris Hecker]

>I can't find a link to any papers by Okasaki on this subject.

http://citeseer.nj.nec.com/okasaki98view.html

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: wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Dimitri Ara]

Chris Hecker <checker@d6.com> a écrit :

> >I can't find a link to any papers by Okasaki on this subject.
> 
> http://citeseer.nj.nec.com/okasaki98view.html

One way to achieve okasaki goal is to provide in the module interface
a lazy concrete_type_of_abstract_type.

Thus, we could write Okasaki's example (page 15) this way:

module type SEQUENCE =
  sig
    type 'a t
    val empty : 'a t
    val cons : 'a -> 'a t -> 'a t
    val append : 'a t -> 'a t -> 'a t
    val lazy_list_of_sequence : 'a t -> 'a Stream.t
  end
      
module Sequence : SEQUENCE =
  struct
    type 'a t = Empty | Cons of 'a * 'a t | Append of 'a t * 'a t
	
    let empty = Empty
    let cons hd tl = Cons hd tl
    let append l1 l2 = Append l1 l2
	
    let rec lazy_list_of_sequence = function
      | Empty -> [< >]
      | Cons a b -> [< 'a ; lazy_list_of_sequence b >]
      | Append a b -> [< lazy_list_of_sequence a; lazy_list_of_sequence b >]
  end
    
open Sequence

let length l =
  let rec length_aux = parser
    | [< 'hd ; tl >] -> 
	1 + length_aux tl
    | [< >] -> 0 in
  length_aux (lazy_list_of_sequence l)
    
let l = append (cons 1 (cons 2 (cons 3 empty))) (cons 4 empty) in
  Printf.printf "%d\n" (length l)

It's syntactically heavy (on an easy example...), it's not
intellectually satisfying, it wastes memory, etc. but it
works :-)

Maybe some camlp4 syntactic sugar could do the trick.

-- 
  Selon les logs, il y a des pertes de porteuses, mais surtout des
  requêtes de déconnexion qui viennent de votre machine.
  Il faut se rappeler que windows 95 est un systeme bio-dégradable.
  -+- Support technique HOL in: Guide du Cabaliste Usenet - CQFD ! -+-
-------------------
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: wanted features (was: Re: [Caml-list] Bigarray map & set/get (long))

[Dimitri Ara]

Chris Hecker <checker@d6.com> a écrit :

> >I can't find a link to any papers by Okasaki on this subject.
> 
> http://citeseer.nj.nec.com/okasaki98view.html

One way to achieve okasaki goal is to provide a lazy
concrete_type_of_abstract_type in the module interface.

Thus, we could write Okasaki's example (page 15) this way:

module type SEQUENCE =
  sig
    type 'a t
    val empty : 'a t
    val cons : 'a -> 'a t -> 'a t
    val append : 'a t -> 'a t -> 'a t
    val lazy_list_of_sequence : 'a t -> 'a Stream.t
  end
      
module Sequence : SEQUENCE =
  struct
    type 'a t = Empty | Cons of 'a * 'a t | Append of 'a t * 'a t
	
    let empty = Empty
    let cons hd tl = Cons hd tl
    let append l1 l2 = Append l1 l2
	
    let rec lazy_list_of_sequence = function
      | Empty -> [< >]
      | Cons a b -> [< 'a ; lazy_list_of_sequence b >]
      | Append a b -> [< lazy_list_of_sequence a; lazy_list_of_sequence b >]
  end
    
open Sequence

let length l =
  let rec length_aux = parser
    | [< 'hd ; tl >] -> 
	1 + length_aux tl
    | [< >] -> 0 in
  length_aux (lazy_list_of_sequence l)
    
let l = append (cons 1 (cons 2 (cons 3 empty))) (cons 4 empty) in
  Printf.printf "%d\n" (length l)

It's syntactically heavy (on an easy example...), it's not as
intellectually satisfying as views are, etc. but it works :-)

Maybe some camlp4 syntactic sugar could do the trick.

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