[Caml-list] OCaml Speed for Block Convolutions

[Caml-list] OCaml Speed for Block Convolutions

[David McClain]

....well, I hate to say this... but I did recode the innermost loop in C and
it now runs more than 5 times faster... Straight recoding into C bought 4x,
and using better math brought that up to 5x.

I think the big thing here is that the OCaml code was producing huge amounts
of garbage, despite preallocated buffers with which all the processing was
reading and writing data. The ancillary closures and tuple args were just
eating my shirt...

- DM


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

[Caml-list] OCaml Speed for Block Convolutions

[William Chesters]

David McClain writes:
 > ....well, I hate to say this... but I did recode the innermost loop in C and
 > it now runs more than 5 times faster... Straight recoding into C bought 4x,
 > and using better math brought that up to 5x.
 > 
 > I think the big thing here is that the OCaml code was producing huge amounts
 > of garbage, despite preallocated buffers with which all the processing was
 > reading and writing data. The ancillary closures and tuple args were just
 > eating my shirt...

I can easily imagine that, with two caveats: tuples passed directly to
functions do seem to get elided, while on the other hand apparently
atomic float accumulators can cause more garbage than you might think.
E.g.

        let a = ref 0. in
        for i = 0 to n-1 do
          a := !a +. Array.unsafe_get xs i
        done

makes garbage---`a' isn't unboxed---while

        type floatref = { mutable it: float }

        let a = { it = 0. } in
        for i = 0 to n-1 do
          a := !a +. Array.unsafe_get xs i
        done

doesn't.  The effect on the visible quality of the assembler for the
inner loop is dramatic, and so is the speed improvement ... basically
using polymorphic data structures is a bad idea.  I wonder if this is
a limitation you have run up against?

Some years ago I made a library using camlp4 for supporting tensor
notation, e.g.

        tens x[I] = a[I J] b[J]

using both automatically generated C and vanilla caml.  When I
recently noticed the above point about not using polymorphic
references, I found there was rather little difference in performane
between the C and ocaml versions.
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Chris Hecker]

>        let a = ref 0. in
>makes garbage---`a' isn't unboxed---while
>       type floatref = { mutable it: float }
>doesn't.

Does this bother anybody else besides me?  Since ref is kind of built-in, is there any way to special case its use on unboxed types and optimize it without making us rewrite lots of code?  There's plenty of other special cased stuff in the compiler, so hey, it's a party!  :)

The other place I get bitten by ref being kind of built-in, kind of not, is in pattern matching:

match a_ref with 
{ contents = 0.0 } -> yuck

Yes, I can match !a, but that's not always convenient (for example, I want a function to take a ref, but name its value:

let f ((x,y) as xy) z = fine
let f ({contents = (x,y)} as xyr) z = a mess

Maybe I'm still too imperative and use ref too much, but I run into this all the time.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[David McClain]

> I can easily imagine that, with two caveats: tuples passed directly to
> functions do seem to get elided, while on the other hand apparently
> atomic float accumulators can cause more garbage than you might think.

Actually, wherever I produce new data, I usually allocate an entirely new
array to hold the results. Then I use unsafe accesses like the following for
summing two arrays:

let dst = Array.unsafe_create nel in
for ix = 0 to pred nel do
    Array.unsafe_set dst ix ((Array.unsafe_get src1 ix) +. (Array.unsafe_get
src2 ix))
done;

I think the constant creation of new arrays to hold intermediate results
(i.e., immutable data) is costing too much. Many of the intermediate values
could be overwritten in place and save a lot of time.

... of course... don't ask how long it took to write all this stuff in the
inner loops of the convolution in C, nor how long it took to debug that
stuff.... And immutable data definitely helps to get the code correct. OCaml
still rules!

- DM

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Tom _]

> E.g.
> 
>         let a = ref 0. in
>         for i = 0 to n-1 do
>           a := !a +. Array.unsafe_get xs i
>         done

Incidentally, rather than trying to come up
with other workaround for imperative variables,
maybe it would be better to just make the
straightforward functional implementation fast:

  let loop i total =
    if i=n then total else
    loop (i+1) (total + Array.unsafe_get xs i)
  in loop 0 0.0

In fact, in a compiler that already has TRO
and type inference, shouldn't this be entirely
equivalent to an imperative loop?

Another approach would be to adopt a "functional"
loop syntax as found in languages like SISAL.  

Tom.


__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail - only $35 
a year!  http://personal.mail.yahoo.com/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Markus Mottl]

On Mon, 04 Jun 2001, David McClain wrote:
> let dst = Array.unsafe_create nel in

Are there any intentions to add "unsafe_create" for float arrays to the
standard library? It would be nice to have a function that allocates such
arrays without initializing them - they are not scanned by the GC, anyway.

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Chris Hecker]

>maybe it would be better to just make the
>straightforward functional implementation fast:
>  let loop i total =
>    if i=n then total else
>    loop (i+1) (total + Array.unsafe_get xs i)
>  in loop 0 0.0

I was planning on asking about this after I timed it relative to a nonrecursive loop.  I noticed a while back that Markus' code for the Language Shootout (for example, http://www.bagley.org/~doug/shootout/bench/matrix/) does tail recursion rather than looping, so I was curious about whether it was superior.

However, this doesn't solve all the problems where this crops up:

let a = ref 0 in
Hashtbl.iter (fun k d -> a := !a + d) my_hash

or 

let hash_to_list h =
        let l = ref [] in
        Hashtbl.iter (fun k d -> l := d :: !l) h

or whatever.  Sometimes these can be handled by fold type functions, but not always (Hashtbl has no fold, for example).

Sometimes you need an imperative variable around, and it'd be nice if it was optimal in the easy cases.  Since function calls are so cheap these days on branch predicting CPUs, these functional map/iter/fold type things can still be high performance.

I haven't done any performance timings yet on these types of operations, though, so a huge grain of salt is attached to this email.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Brian Rogoff]

On Mon, 4 Jun 2001, Tom _ wrote:
> > E.g.
> > 
> >         let a = ref 0. in
> >         for i = 0 to n-1 do
> >           a := !a +. Array.unsafe_get xs i
> >         done
> 
> Incidentally, rather than trying to come up
> with other workaround for imperative variables,
> maybe it would be better to just make the
> straightforward functional implementation fast:
> 
>   let loop i total =
>     if i=n then total else
>     loop (i+1) (total + Array.unsafe_get xs i)
>   in loop 0 0.0
> 
> In fact, in a compiler that already has TRO
> and type inference, shouldn't this be entirely
> equivalent to an imperative loop?

Yes, but I think the general problem that William Chesters alludes to (the
overhead of polymorphic variables) is an interesting one to solve
regardless. Coming back to the subject of this thread, in an ideal world, 
there wouldn't be a need to distinguish between Bigarray and Array, you'd 
just use polymorphic arrays and the compiler would be smart enough to 
always get unboxed and tag free element representations. Supposedly Stalin 
comes close (I've only played with it on *very* small programs) so maybe 
one day we'll get something similar. And maybe David McClain wouldn't have
to write his inner loops in C or Fortran. What a wonderful world that
would be...

> Another approach would be to adopt a "functional"
> loop syntax as found in languages like SISAL.  

Or SAC. But OCaml arrays (and strings) aren't functional, and the only
Clean and efficient way I know to deal with that is uniqueness type
information. Functional arrays (trees or version arrays) are not efficient
enough to replace imperative arrays when you have single threaded usage; 
definitely not the right data structure for signal processing or numerical 
linear algebra. OTOH (changing the subject) it might be nice to have
built in version arrays and functional strings for other reasons.

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Chris Hecker]

>I think the constant creation of new arrays to hold intermediate results
>(i.e., immutable data) is costing too much. Many of the intermediate values
>could be overwritten in place and save a lot of time.
>... of course... don't ask how long it took to write all this stuff in the
>inner loops of the convolution in C, nor how long it took to debug that
>stuff.... And immutable data definitely helps to get the code correct. OCaml
>still rules!

I think I'm missing something.  The ocaml loops allocate memory for temps, but the C loops reuse storage?  Did you do a version for ocaml that's got the same level of optimizations as the C version (not allocating, etc.)?

If the code's not to big, could you post it?

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Tom _]

>         let a = ref 0. in
>         for i = 0 to n-1 do
>           a := !a +. Array.unsafe_get xs i
>         done

I think it's natural for this to cause storage
allocation.  After all, "ref 0." is an object that
can be passed around.  The compiler may be able
to infer that it can allocate it on the stack, but
that may be hard in general.

Why not have a construct that expresses what
the programmer really wants:

  let mutable a = 0. in
  for i = 0 to n-1 do
    a <- a +. Array.unsafe_get xs i
  done

Tom

PS: sorry if you have seen this posting before; I
think I keep hitting the wrong button in my mailer
and end up not responding to the list


__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail - only $35 
a year!  http://personal.mail.yahoo.com/
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Stefan Monnier]

>>>>> "Brian" == Brian Rogoff <bpr@best.com> writes:
> regardless. Coming back to the subject of this thread, in an ideal world, 
> there wouldn't be a need to distinguish between Bigarray and Array, you'd 
> just use polymorphic arrays and the compiler would be smart enough to 
> always get unboxed and tag free element representations. Supposedly Stalin 

That's also what SML/NJ tries to do.  But short of doing whole program
analysis and/or profiling feedback, it's difficult to generate as good
code as in the Bigarray case.


	Stefan
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Hugo Herbelin]

> >         let a = ref 0. in
> >         for i = 0 to n-1 do
> >           a := !a +. Array.unsafe_get xs i
> >         done
> ...
> Why not have a construct that expresses what
> the programmer really wants:
> 
>   let mutable a = 0. in
>   for i = 0 to n-1 do
>     a <- a +. Array.unsafe_get xs i
>   done
> 
> Tom

I was precisely asking myself the same question, initially motivated
by explaining the imperative constructs of ML to programmers coming
from the imperative side. I mean how to explain that you find in ML a
regular for-loop, a regular while-loop but you need to use pointers to
translate assignments as in the code at top above which really only
corresponds to the following C code:

int i;
double *a = (double *) malloc(sizeof(double)); *a = 0;
for (i=0;i<=n-1;i++) *a = *a + xs[i];


Assume more generally that you can modify any local variable as in the
(standard) following example:

let fact (mutable n) =
  let mutable r = 1 in
  while n > 0 do
     r <- r * n;
     n <- n - 1
  done;
  r

At first, this is in contradiction with the substitution property of
purely functional languages, like "let x = 1 in ... x ..." should
behave the same as "... 1 ...", but it then should be enough to
explain that a while-loop binds over all the variables modified in its
body, as the functional interpretation of the while-loop shows it

let fact n =
  let r = 1 in
  let rec loop (r,n as effects) =
     if n > 0 then
       let r = r * n in
       let n = n - 1 in
       loop (r,n)
     else effects in
  let (r,n) = loop (r,n) in
  r

and the substitution property is preserved.

The compilation model of ocaml is already able to handle this (at
least the bytecode, in fact to realize the incrementation of the
for-loops counter) and the typing would just be monomorphic as for 
any mutable. May there be any problem I don't see? Is there a risk
to allow more imperative-style algorithms? Could it really lead to
a sensible benefit in efficiency for some typical algorithms?

At least, it seems there is some limitations with higher-order
functions.

> let a = ref 0 in
> Hashtbl.iter (fun k d -> a := !a + d) my_hash

Following the same principe as before, an alternative would be

let a = mutable 0 in
Hashtbl.iter (fun k d -> a <- a + d) my_hash

explaining that the substitution property is preserved by the fact
that a function too binds over the variables it modifies, even if in
this case, the functional translation needs to add an extra arg to
iter.

But since only "immediate" variables of a function are not copied (all
the variables declared by and since the closer surrounding "fun"), the
last option will not work: when building the closure, a new copy of
the value of a is put in the closure environment and further updatings
will not affect the initial cell.

                                                  Hugo
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Charles Martin]

>> >           a := !a +. Array.unsafe_get xs i
>>     a <- a +. Array.unsafe_get xs i

At the risk of being off topic, I am wondering why most every code scrap that appears on this list uses [Array|String].unsafe_[get|set], rather than the "safe" versions.  Are off-by-one errors and the like so rare?  Doesn't adding "-unsafe" as a compiler option to your final build have the same effect?  If not, that would be worth knowing.


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[David McClain]

> I think I'm missing something.  The ocaml loops allocate memory for temps,
but the C loops reuse storage?  Did you do a version for ocaml that's got
the same level of optimizations as the C version (not allocating, etc.)?

I didn't write an OCaml program to solve this specific problem. Instead, I
made use of my NML (numeric modeling language) built on top of OCaml. Hence,
being a general purpose language, it had to make very conservative choices
to protect the user. Whenever new data are generated, they are placed into
freshly allocated arrays.

Had I written code to specifically address this one problem it would
probably have performed better. I was quite impressed with the performance I
was getting from my NML which used this very general purpose OCaml kernel. I
almost stopped at that point. But nagging questions, eager users, and a
growing list of block convolution jobs convinced me to see what I could do
in C, while still living primarily in the NML world.

I didn't see any need to rewrite all the file I/O handling, the
unwind-protect mechanisms, etc, etc, all in C when I have perfectly good
versions of this stuff in NML thanks to OCaml. So I simply targeted the
innermost loop where I knew much of the overhead was in fresh array creation
at every intermediate step. I am doing block convolutions on GByte sized
datasets, which is far more than NML was ever intended to support well. NML
is a modeling and prototyping language.

But adding C code is as easy as adding C code to any OCaml program and
recompiling the augmented NML system. Hence targeting only the inner loops
was very simple (in principle). In practice, even after nearly 30 years of
heavy C/C++ experience I still cannot write even relatively simple programs
without planting bugs in them. To OCaml's credit, I can easily write OCaml
code that executes properly the first time out. No debugging. I wish that
were the case for C as well.

So to end this long winded explanation, had I written OCaml code
specifically for the purpose of block convolutions I would have expected a
performance around 70% of that demonstrated by C, not the factor of 4 that I
had with NML. I could have written to use mutable arrays in that case,
reaping much of the same advantages that I got when I rewrote the inner
loops in C.

- DM

----- Original Message -----
From: "Chris Hecker" <checker@d6.com>
To: "David McClain" <dmcclain1@mindspring.com>; <caml-list@inria.fr>
Sent: Tuesday, June 05, 2001 12:22 AM
Subject: Re: [Caml-list] OCaml Speed for Block Convolutions


>
> >I think the constant creation of new arrays to hold intermediate results
> >(i.e., immutable data) is costing too much. Many of the intermediate
values
> >could be overwritten in place and save a lot of time.
> >... of course... don't ask how long it took to write all this stuff in
the
> >inner loops of the convolution in C, nor how long it took to debug that
> >stuff.... And immutable data definitely helps to get the code correct.
OCaml
> >still rules!
>
> I think I'm missing something.  The ocaml loops allocate memory for temps,
but the C loops reuse storage?  Did you do a version for ocaml that's got
the same level of optimizations as the C version (not allocating, etc.)?
>
> If the code's not to big, could you post it?
>
> Chris
>
>

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[William Chesters]

Charles Martin writes:
 > 
 > >> >           a := !a +. Array.unsafe_get xs i
 > >>     a <- a +. Array.unsafe_get xs i
 > 
 > At the risk of being off topic, I am wondering why most every code
 > scrap that appears on this list uses
 > [Array|String].unsafe_[get|set], rather than the "safe" versions.
 > Are off-by-one errors and the like so rare?  Doesn't adding
 > "-unsafe" as a compiler option to your final build have the same
 > effect?  If not, that would be worth knowing.

it's just that when one posts performance-related snippets, it saves
everyone's time if it's immediately clear that bounds checks are not
an issue
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[William Chesters]

Hugo Herbelin writes:
 > Assume more generally that you can modify any local variable as in the
 > (standard) following example:
 > 
 > let fact (mutable n) =
 >   let mutable r = 1 in
 >   while n > 0 do
 >      r <- r * n;
 >      n <- n - 1
 >   done;
 >   r

This doesn't actually make life much easier for the compiler.  On
32-bit machines [see other thread!], `r' must be a reference (in the
C++ sense) to a heap object---64-bit float, plus header.  In general
it is not safe to overwrite the float value in the heap, if it's
possible that other variables have been assigned to it (unless floats
are assigned by value not by reference, but in that case you get heap
allocation at the time of assignment ...).  The analysis necessary for
determining that no such aliasing references can exist, and indeed
that the value can simply be kept in a float register/on the FPU
stack, is already there in the compiler and applies perfectly well to
mutable references.

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Patrick M Doane]

On Wed, 6 Jun 2001, William Chesters wrote:

> Hugo Herbelin writes:
>  > Assume more generally that you can modify any local variable as in the
>  > (standard) following example:
>  > 
>  > let fact (mutable n) =
>  >   let mutable r = 1 in
>  >   while n > 0 do
>  >      r <- r * n;
>  >      n <- n - 1
>  >   done;
>  >   r
> 
> This doesn't actually make life much easier for the compiler.

Even if there's no benefit to the compiler, I think there is a benefit to
the programmer. I would much rather write imperative code with that
syntax.

Patrick

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[William Chesters]

Markus Mottl writes:
 > On Mon, 04 Jun 2001, David McClain wrote:
 > > let dst = Array.unsafe_create nel in
 > 
 > Are there any intentions to add "unsafe_create" for float arrays to the
 > standard library? It would be nice to have a function that allocates such
 > arrays without initializing them - they are not scanned by the GC, anyway.

My feeling has always been that the overhead of initialising a float
array, per element, is considerably less than the cost of one floating
point operation; so if you ever intend to actually use the array for
anything, the inefficiency is negligible.

On the other hand if we have unsafe_set than unsafe_create is hardly a
huge additional bloat, more a kind of natural counterpart.

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Chris Hecker]

>My feeling has always been that the overhead of initialising a float
>array, per element, is considerably less than the cost of one floating
>point operation; so if you ever intend to actually use the array for
>anything, the inefficiency is negligible.

This is not true on modern processors, if I understand what you're saying.  Touching memory that's not in the cache is orders of magnitude slower than flops.  Even the best case, with the memory in the cache, touching memory is the same speed or slower than doing a flop on most CPUs.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Hugo Herbelin]

William Chesters wrote:
> Hugo Herbelin writes:
>  > Assume more generally that you can modify any local variable as in the
>  > (standard) following example:
>  > 
>  > let fact (mutable n) =
>  >   let mutable r = 1 in
>  >   while n > 0 do
>  >      r <- r * n;
>  >      n <- n - 1
>  >   done;
>  >   r
> 
> This doesn't actually make life much easier for the compiler.  On
> 32-bit machines [see other thread!], `r' must be a reference (in the
> C++ sense) to a heap object---64-bit float, plus header.  In general
> it is not safe to overwrite the float value in the heap, if it's
> possible that other variables have been assigned to it. (unless floats
> are assigned by value not by reference, but in that case you get heap
> allocation at the time of assignment ...).  

  To be boxed or not is not a property of the language but of the
implementation. This means that the semantics for such a "x <- e"
for boxed values (may be floats) can only be the same as for unboxed
values, that is "assignment by value".

  This means that "x <- e", compared to "x.contents <- e", wouldn't
avoid the heap allocation inherent to the boxing of floats, but would
just avoid the initial allocation of an extra ref block and the
subsequent indirections to set/get the value (assuming the cell is not
already cached in a register what perhaps the compiler is able to do).

                                                  Hugo


-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[William Chesters]

Chris Hecker writes:
 > 
 > >My feeling has always been that the overhead of initialising a float
 > >array, per element, is considerably less than the cost of one floating
 > >point operation; so if you ever intend to actually use the array for
 > >anything, the inefficiency is negligible.
 > 
 > This is not true on modern processors, if I understand what you're saying.  Touching memory that's not in the cache is orders of magnitude slower than flops.  Even the best case, with the memory in the cache, touching memory is the same speed or slower than doing a flop on most CPUs.

Er, yes, you are right of course and "I didn't mean to say that" ;)
but rather: whatever you subsequently do to the float array, be it
arithmetic or churning it through the cache, is likely to be
more expensive per element than initialisation.

Sorry,
William

[head befuddled by day spent trying to trick C++ compiler into coding up
float array ops right, or that's my excuse!]
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Tom _]

--- William Chesters <williamc@paneris.org> wrote:
> Hugo Herbelin writes:
>  > Assume more generally that you can modify any
> local variable as in the
>  > (standard) following example:
>  > 
>  > let fact (mutable n) =
>  >   let mutable r = 1 in
>  >   while n > 0 do
>  >      r <- r * n;
>  >      n <- n - 1
>  >   done;
>  >   r
> 
> This doesn't actually make life much easier for the
> compiler.  On 32-bit machines [see other thread!], 
> `r' must be a reference (in the 
> C++ sense) to a heap object---64-bit float, plus
> header.

I don't see why. The compiler has full type 
information.  All it may have to do is box up
a return value.

In any case, whether or not the compiler in the
current implementation can or cannot do good type
inference and may or may not be forced to box
a floating point number, the two constructs mean
something different to the programmer, and they
behave differently.  In particular "mutable x"
can never be passed around as a reference, while
"x = ref ..." can.  If not anything else, that
prevents the programmer from inadvertently inhibiting
a compiler optimization by passing around a reference.

Besides, the syntax is probably quite a bit more 
natural to imperative programmers anyway.

Tom.


__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail - only $35 
a year!  http://personal.mail.yahoo.com/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Jacques Garrigue]

About the introduction of a let mutable construct,
Tom _ <tom7ca@yahoo.com> wrote

> In any case, whether or not the compiler in the
> current implementation can or cannot do good type
> inference and may or may not be forced to box
> a floating point number, the two constructs mean
> something different to the programmer, and they
> behave differently.  In particular "mutable x"
> can never be passed around as a reference, while
> "x = ref ..." can.  If not anything else, that
> prevents the programmer from inadvertently inhibiting
> a compiler optimization by passing around a reference.

Not exactly, the compiler may still need to build a reference.

    let mutable x = 0 in
    List.iter (fun y -> x <- x+y) l;
    x

Since x has to be modified in a function called by iter, it must be
wrapped into an actual reference cell.

As the compiler already does a good job at unboxing only locally used
references, let mutable would only be some syntactic sugar (with
exactly the same typing as a reference).

> Besides, the syntax is probably quite a bit more 
> natural to imperative programmers anyway.

This is actually the only argument for let mutable.
I would also like such a construct, but I don't know whether its worth
it. The real question is whether let mutable should be allowed at
toplevel, with problems for both answers.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Currying in Ocaml

[Mark Wotton]

Is it possible to curry on arbitrary parameters in Ocaml, or is it
strictly left to right? I have a function "print_all depth tree" and
sometimes I'd like to curry on depth, other times on tree. I see that if i
write a little wrapper like "rev_curry_print_all tree depth = print_all
depth tree" I could curry using that instead, but this function is called
inside a deep recursive loop and I'm worried that I'll get an unnecessary
function call overhead. Is there a better way of doing this?

regards,
Mark


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Currying in Ocaml

[Chris Hecker]

Let's start up the commuting labels discussion again!!!

Ahem.

I think you have to eta-expand:

(fun t d -> print_all d t)

I don't think there's a flip f x y = f y x in the pervasives library (why not, by the way, INRIA folks?), but it seems to be a common idiom, like fst and snd.

As for overhead, "Assume Nothing," as they say.  Try eta-expanding and let us know if you see a performance problem.

Chris

At 10:20 AM 6/8/01 +1000, Mark Wotton wrote:
>Is it possible to curry on arbitrary parameters in Ocaml, or is it
>strictly left to right? I have a function "print_all depth tree" and
>sometimes I'd like to curry on depth, other times on tree. I see that if i
>write a little wrapper like "rev_curry_print_all tree depth = print_all
>depth tree" I could curry using that instead, but this function is called
>inside a deep recursive loop and I'm worried that I'll get an unnecessary
>function call overhead. Is there a better way of doing this?
>
>regards,
>Mark
>
>
>-------------------
>Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
>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/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Ohad Rodeh]

I don't mean to barge into an open door here, but
the discussion here is about escape analysis. This certainly
does not require the new "mutable" syntax. My personal opinion
is that Caml has enough syntax as it is (try using/modifying the
OCaml mly files as an exercise ...). 

In any case, escape analysis a clever optimization allowing some heap
allocated objects to be allocated on the run-time stack.
The MLkit takes escape analysis into the extrem, using regions. Java
compilers also use escape analysis to reduce heap allocation. 

Since we are already on the "with list" thread, I'd like to add my 
own wish. I'm going to teach the "Purely Functional Data Structures" book
(Chris Okasaki) as a course next semester. To do the real nifty stuff, you
need to have polymorphic recursion supported by the compiler. Can this be
added to the next release? 

	Ohad.

On Fri, 8 Jun 2001, Jacques Garrigue wrote:

> About the introduction of a let mutable construct,
> Tom _ <tom7ca@yahoo.com> wrote
> 
> > In any case, whether or not the compiler in the
> > current implementation can or cannot do good type
> > inference and may or may not be forced to box
> > a floating point number, the two constructs mean
> > something different to the programmer, and they
> > behave differently.In particular "mutable x"
> > can never be passed around as a reference, while
> > "x = ref ..." can.If not anything else, that
> > prevents the programmer from inadvertently inhibiting
> > a compiler optimization by passing around a reference.
> 
> Not exactly, the compiler may still need to build a reference.
> 
>   let mutable x = 0 in
>   List.iter (fun y -> x <- x+y) l;
>   x
> 
> Since x has tobe modified in a function called by iter, it must be
> wrapped into an actual reference cell.
> 
> As the compiler already does a good job at unboxing only locally used
> references, let mutable would only be some syntactic sugar (with
> exactly the same typing as a reference).
> 
> > Besides, the syntax is probably quite a bit more
> > natural to imperative programmers anyway.
> 
> This is actually the only argument for let mutable.
> I would also like such a construct, but I don't know whether its worth
> it. Thereal question is whether let mutable should be allowed at
> toplevel, with problems for both answers.
> 
> Cheers,
> 
> Jacques Garrigue
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugsFAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.frArchives: http://caml.inria.fr
> 

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Currying in Ocaml

[Anton Moscal]

 8 Июнь 2001 04:20, Mark Wotton написал:
> Is it possible to curry on arbitrary parameters in Ocaml, or is it
> strictly left to right? I have a function "print_all depth tree" and
> sometimes I'd like to curry on depth, other times on tree. I see that if i
> write a little wrapper like "rev_curry_print_all tree depth = print_all
> depth tree" I could curry using that instead, but this function is called
> inside a deep recursive loop and I'm worried that I'll get an unnecessary
> function call overhead. Is there a better way of doing this?

You can achieve this effect by using labels in "commutiong labels mode" 
(compiler swtich -labels)

let test ~a ~b = Printf.printf "a=%d b=%d\n" a b

let testb = test ~a:1
let testa = test ~b:1

let _ = 
  testb ~b:10;
  testa ~a:10


Regards, Anton
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Brian Rogoff]

> Since we are already on the "with list" thread, I'd like to add my 
> own wish. I'm going to teach the "Purely Functional Data Structures" book
> (Chris Okasaki) as a course next semester. To do the real nifty stuff, you
> need to have polymorphic recursion supported by the compiler. Can this be
> added to the next release? 

This has been discussed many times here, and Pierre Weis has given a 
few good summaries of past work which you can access from the archives. 
In particular, the forward declaration he proposed also fixed the 
module spanning recursive function definition issue, and so kills 
at least two birds with one stone. Here's the ref 

http://caml.inria.fr/archives/199902/msg00020.html

Supporting polymorphic recursion is really high on my wish list too even
though I'm not in school or teaching. In essence, I want more
recursion: polymorphic recursion, module spanning recursive types, etc. I
personally hadn't bumped into the case where module spanning recursive
function definitions were a pain, but I found Fergus Henderson's argument
from the Mercury compiler sources pretty convincing so I want that too. 

Anyways, that's the problem with that damned Okasaki book; once you read
it you start wanting all of these fancy features. I guess ignorance
really is bliss. :-)

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> About the introduction of a let mutable construct,
> Tom _ <tom7ca@yahoo.com> wrote
> 
> > In any case, whether or not the compiler in the
> > current implementation can or cannot do good type
> > inference and may or may not be forced to box
> > a floating point number, the two constructs mean
> > something different to the programmer, and they
> > behave differently.  In particular "mutable x"
> > can never be passed around as a reference, while
> > "x = ref ..." can.  If not anything else, that
> > prevents the programmer from inadvertently inhibiting
> > a compiler optimization by passing around a reference.
> 
> Not exactly, the compiler may still need to build a reference.
> 
>     let mutable x = 0 in
>     List.iter (fun y -> x <- x+y) l;
>     x
> 
> Since x has to be modified in a function called by iter, it must be
> wrapped into an actual reference cell.
> 
> As the compiler already does a good job at unboxing only locally used
> references, let mutable would only be some syntactic sugar (with
> exactly the same typing as a reference).
> 
> > Besides, the syntax is probably quite a bit more 
> > natural to imperative programmers anyway.
> 
> This is actually the only argument for let mutable.
> I would also like such a construct, but I don't know whether its worth
> it. The real question is whether let mutable should be allowed at
> toplevel, with problems for both answers.
> 
> Cheers,
> 
> Jacques Garrigue
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

The introduction of a ``let mutable'', more concisely noted with the
var keyword, is not new: it has been discussed in the Caml groups 3 or
4 years ago. We chose to abandon it for sake of semantics simplicity
of the language. This construction would have introduced the notion of
Lvalue in Caml, thus introducing some additional semantics complexity,
and a new notion to explain to beginners. Furthermore, the efficiency
gain was not clear, since Xavier had succeeded at optimizing reference
allocations for all typical uses of references that are relevant to
the proposed (less powerful) ``let mutable'' bound variables.

Let me explain the semantics arguments (semantics is more important
that many of us think, although all of us are syntax lovers and syntax
alternate features advocates) for pure references and against the
introduction of ``let mutable'' bound variables.

Dynamic semantics (or evaluation mechanism)
-------------------------------------------

You may not have noticed that Caml mutable values (references or
arrays) have a first class citizen status, being treated as regular
values with respect to data structures manipulation and function calls
and returns. For example, the assignment operators are regular
functions with no magic (such as special annotations of arguments at
definition time, or special operation at call sites). Hence you can
define your own assigment functions using regular Caml programming:

let ( += ) r v = r := !r + v;;
val ( += ) : int ref -> int -> unit = <fun>

Now, if you write x += 2 you apply the (infix) operator += to the two
expressions x and 2. This is just regular Caml computation, hence you
can write arbitrary programs instead of x and 2. For instance, f y +=
g 0 means that function call f y returns a reference whose contents is
incremented by (the value of) g 0.

Note that the mechanism is also that simple for the ! operator: ! has
no special evaluation rule, it is applied to the value of its argument
(which must be a reference) and returns it contents. Hence you may
write !(f y), provided that f y returns a reference.

In the same vein you can redefine the usual := operator (for instance
to count the number of assigments in your program):

let assignment_count = ref 0;;

let ( := ) r v =
  incr assignment_count;
  r := v;;
val ( := ) : 'a ref -> 'a -> unit = <fun>

If you prefer the C way, you can even use:

let ( = ) r v = r := v;;
val ( = ) : 'a ref -> 'a -> unit = <fun>

Now you loose = as a short hand for the polymorphic comparison, but as
desired, r = 1 will gladly assign 1 to r ...

Another interesting point: there is no scope limitation or odity for
references; references obey the usual scope and life time rules.

Static semantics (or typechecking mechanism)
--------------------------------------------

On this (hard) side, nothing to gain with the new construct: the
restriction on typechecking of polymorphic refs should be maintained
for vars, or we must revert to the original complicated (and probably
not proved sound) rule of original ML (see below).

Historical (and personal) note:
-------------------------------

The proposed construct is not new: it has been introduced in original
ML (from LCF) by Robin Milner in 1978. Mutable variables were
introduced by letref (reminiscent of the letrec keyword that
introduced recursive definitions at that time). You would declare a
(so-called) reference identifier by the definition

letref x = 0;;

and assign it using:

x := x + 1;;

(Note that on the left of := you needed a left value, hence an
identifier previously defined via letref.)

During the year 1984, the ML team discovered that allocating a cell
for letref identifiers will enhance the power of ``letref''
definitions since references could be treated as first class citizen
values. My first compilation programming exercise was to implement the
new feature into the V6.1 version of the ML compiler during falls 1984
(or may be at beginning of 1985 ?). We simultaneously maintained both
constructs in the language; we also used the same := operator to
assign references (desambiguated via a compiler annotation of letref
bound identifiers), and an explicit deref function to get the contents
of the new references. After the introduction of the shorter !
dereferencing operator, everybody in the ML community (read community
as ``the people logged on our vax or on the Cambridge University's
vax''!) agreed that the old letref construct was subsumed by the new
references stuff. Thus, I suppressed the old letref construct from the
language. The special typing rule for letref was reinforced for the
new references (but getting rid of the strange lambda-bound
restriction of the letref construct) in a trivial way: at the end of
typechecking all references defined in the program should have
monomorphic types. As you may know this was the beginning of a long
and difficult quest of the right typing restriction for safe
manipulation of polymorphic mutable values in ML-like
languages. Although the currently used value restriction rule was
discovered by Greg Morrisset in 1995, the Caml team actively
participated to this quest with a POPL article by Xavier Leroy and I
in 1991, and culminated with Xavier's PHD thesis in 1992.

Conclusion:
-----------

On the language design side, we worked hard to bypass the limitations
of letrefs in order to design first class citizens references, and to
get rid of left values in the language. On the compiler construction
side, Xavier worked hard to optimise spurious allocations of
references that can be treated as vars. I think we now have the power
and conceptual simplicity of references along with the runtime
efficiency of letrefs, I don't see the point to introduce a new
arguably useless construct.

Best regards,

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Stefan Monnier]

>>>>> "Pierre" == Pierre Weis <Pierre.Weis@inria.fr> writes:
> languages. Although the currently used value restriction rule was
> discovered by Greg Morrisset in 1995, the Caml team actively

I though it was Andrew K. Wright "Simple Imperative Polymorphism" in
Lisp and Symbolic Computation, Déc 95 (the corresponding tech-report
dates back to 93).  Does anybody remember ?


	Stefan
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> >>>>> "Pierre" == Pierre Weis <Pierre.Weis@inria.fr> writes:
> > languages. Although the currently used value restriction rule was
> > discovered by Greg Morrisset in 1995, the Caml team actively
> 
> I though it was Andrew K. Wright "Simple Imperative Polymorphism" in
> Lisp and Symbolic Computation, Déc 95 (the corresponding tech-report
> dates back to 93).  Does anybody remember ?
> 
> 
> 	Stefan
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Oups: the value restriction was indeed studied by Andrew Wright and
first published as a tech report in 1993, then published in 1995 in
Lisp and Symbolic Computation. Sorry for the mistake.

Here are the references to the relevant publications:

A.K. Wright. Polymorphism for imperative languages without imperative
types. Technical report TR93-200, Rice University, 1993.

@article{ wright95simple,
    author = "Andrew K. Wright",
    title = "Simple Imperative Polymorphism",
    journal = "Lisp and Symbolic Computation",
    volume = "8",
    number = "4",
    pages = "343--355",
    year = "1995",
    url = "citeseer.nj.nec.com/wright95simple.html"
}

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Michel Quercia]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="US-ASCII", Size: 1469 bytes --]

Le Vendredi  8 Juin 2001 19:30,  Pierre Weis a écrit :

> The introduction of a ``let mutable'', more concisely noted with the
> var keyword, is not new: it has been discussed in the Caml groups 3 or
> 4 years ago. We chose to abandon it for sake of semantics simplicity
> of the language.

For beginners (f.e. students) things look a bit complicated :

(* summing up all elements of an integer array *)
let adda a =
  let res = ref 0 in
  let i = ref 0 in
  while !i < Array.length(a) do res := !res+a.(!i); i := !i+1 done;
  !res
;;

A lot of boring exclam, but that's the price to pay for having 
mutable values, and that's logical. Okay ...

(* same, but with a for loop *)
let add_1 a =
  let res = ref 0 in
  for i=0 to Array.length(a)-1 do res := !res + a.(i) done;
  !res
;;

No exclam and no ref for i ?  And its value is changing though ? Where is 
gone the logic ?

> This construction would have introduced the notion of
> Lvalue in Caml, thus introducing some additional semantics complexity,
> and a new notion to explain to beginners.

Lvalues already exist in Ocaml (and have to be explained to beginners), for 
example : "a.(i) <- a.(i)+1".

Regards,
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://pauillac.inria.fr/~quercia
mailto:michel.quercia@prepas.org
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] should "a.(i)" be a reference? (was "let mutable")

[Judicaël Courant]

Hi,

On Fri, 8 Jun 2001 21:30:29 +0200
Michel Quercia <michel.quercia@prepas.org> wrote:

> (* same, but with a for loop *)
> let add_1 a =
>   let res = ref 0 in
>   for i=0 to Array.length(a)-1 do res := !res + a.(i) done;
>   !res
> ;;
> 
> No exclam and no ref for i ?  And its value is changing though ? Where
is 
> gone the logic ?

It does not change more than in "List.iter (fun i -> res := !res + a(i))
l". The "for" loop is just a new kind of binder. With the suitable
for_loop function (let rec for_loop b e f = if b <= e then begin f b;
for_loop (b+1) e f end), you could write this as:

for_loop 0 (Array.length(a)-1) (fun i -> res := !res + a.(i))

On the contrary, a mutable "i" would mean you could change the way the
iterations are done inside your loop, which is not really nice IMHO:

for i:= 0 to Array.length(a)-1 do
 res := !res+a.(!i);
 if once_again() then i := !i - 1
done

is really bad programming style; if you want to do this, use a while loop
instead.

> 
> > This construction would have introduced the notion of
> > Lvalue in Caml, thus introducing some additional semantics complexity,
> > and a new notion to explain to beginners.
> 
> Lvalues already exist in Ocaml (and have to be explained to beginners),
for 
> example : "a.(i) <- a.(i)+1".
> 

You are right, but maybe this suggest that a.(i) should be typed as a
reference?

Or, in order to preserve compatibility, the reference could be noted
"a.&(i)"; "a.(i)" would be just syntactic sugar for
"!a.&(i)" and "a.(i) <- y" would be syntactic sugar for "a.&(i) := y".
The same could be done for mutable record fields. This would not only tidy
the semantics, but it would also enrich the language: the programmer could
then use references to mutable record fields or to array cells as function
arguments (would anybody be interested by such a feature?).

Best regards,

Judicaël Courant.
-- 
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/
(+33) (0)1 69 15 64 85
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> Le Vendredi  8 Juin 2001 19:30,  Pierre Weis a écrit :
> 
> > The introduction of a ``let mutable'', more concisely noted with the
> > var keyword, is not new: it has been discussed in the Caml groups 3 or
> > 4 years ago. We chose to abandon it for sake of semantics simplicity
> > of the language.
> 
> For beginners (f.e. students) things look a bit complicated :
> 
> (* summing up all elements of an integer array *)
> let adda a =
>   let res = ref 0 in
>   let i = ref 0 in
>   while !i < Array.length(a) do res := !res+a.(!i); i := !i+1 done;
>   !res
> ;;
> 
> A lot of boring exclam, but that's the price to pay for having 
> mutable values, and that's logical. Okay ...
> 
> (* same, but with a for loop *)
> let add_1 a =
>   let res = ref 0 in
>   for i=0 to Array.length(a)-1 do res := !res + a.(i) done;
>   !res
> ;;
> 
> No exclam and no ref for i ?  And its value is changing though ? Where is 
> gone the logic ?

The for loop is a short hand for a call to a local recursive function:
no reference and no problem here, unless you consider that you cannot
change the arguments of a recursive call to a function.

(For readers not familiar with the subject, let's recall that

for i = e1 to e2 do e3 done

 is equivalent to

let rec _loop i _lim = if i <= _lim then begin e3; _loop (i + 1) _lim end in
_loop e1 e2

(where _loop and _lim stand for new fresh identifiers, not free in e1, e2,
or e3)
)

> > This construction would have introduced the notion of
> > Lvalue in Caml, thus introducing some additional semantics complexity,
> > and a new notion to explain to beginners.
> 
> Lvalues already exist in Ocaml (and have to be explained to beginners), for 
> example : "a.(i) <- a.(i)+1".

I'm afraid this is wrong.

The syntactic construction e1.(e2) <- e3 is a short hand for a
function call: Array.set e1 e2 e3. Once more there is no Lvalue here,
just a regular function call (hence you can write arbitrary complex
expressions in place of e1, provided it returns an array value).

I'm a bit surprised that you feel it necessary to explain the notion
of Lvalue to beginners when there is no such notion in the language !

Best regards.

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Jacques Garrigue]

From: Pierre Weis <Pierre.Weis@inria.fr>

> > > This construction would have introduced the notion of
> > > Lvalue in Caml, thus introducing some additional semantics complexity,
> > > and a new notion to explain to beginners.
> > 
> > Lvalues already exist in Ocaml (and have to be explained to
> > beginners), for example : "a.(i) <- a.(i)+1".
> 
> I'm afraid this is wrong.
> 
> The syntactic construction e1.(e2) <- e3 is a short hand for a
> function call: Array.set e1 e2 e3. Once more there is no Lvalue here,
> just a regular function call (hence you can write arbitrary complex
> expressions in place of e1, provided it returns an array value).
> 
> I'm a bit surprised that you feel it necessary to explain the notion
> of Lvalue to beginners when there is no such notion in the language !

You can of course explain the semantics this way, but most people
apparently consider that there are lvalues in ocaml, just that they
are very restricted. It is certainly much simpler to explain than
lvalues in C!

Also, there is one unique case currently which can only be explained
by the distinction lvalue/rvalue: instance variables in objects.

  class counter = object
    val mutable x = 0
    method get = x
    method bump = x <- x + 1
  end

How can you explain the method bump without the notion of lvalue?

Perfectly coherent answers would be, let's remove mutable instance
variables, or force the notation self.x to access variables.
Another answer is that people so fond of objects have already heared
of lvalues anyway.

the problem is not only with lvalues either. With for loops, you have
a case of rvalue, where something which is not syntactically a
function have a changing variable, which is accessed directly. The
fact you cannot change it yourself is not relevant.

Best regards,

     Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> From: Pierre Weis <Pierre.Weis@inria.fr>
> 
> > > > This construction would have introduced the notion of
> > > > Lvalue in Caml, thus introducing some additional semantics complexity,
> > > > and a new notion to explain to beginners.
> > > 
> > > Lvalues already exist in Ocaml (and have to be explained to
> > > beginners), for example : "a.(i) <- a.(i)+1".
> > 
> > I'm afraid this is wrong.
> > 
> > The syntactic construction e1.(e2) <- e3 is a short hand for a
> > function call: Array.set e1 e2 e3. Once more there is no Lvalue here,
> > just a regular function call (hence you can write arbitrary complex
> > expressions in place of e1, provided it returns an array value).
> > 
> > I'm a bit surprised that you feel it necessary to explain the notion
> > of Lvalue to beginners when there is no such notion in the language !
> 
> You can of course explain the semantics this way, but most people
> apparently consider that there are lvalues in ocaml, just that they
> are very restricted. It is certainly much simpler to explain than
> lvalues in C!

Most people consider Caml as a toy language, since it is not a
mainstream language. As a computer science researcher fond of riguour,
I certainly will not organize a vote to find out if ``most people
apparently consider'' something, to decide that this something is
true.

A more interesting contribution would be to give evidences that
references and arrays and other imperative features are indeed built
with lvalues in Caml.

> Also, there is one unique case currently which can only be explained
> by the distinction lvalue/rvalue: instance variables in objects.
> 
>   class counter = object
>     val mutable x = 0
>     method get = x
>     method bump = x <- x + 1
>   end
> 
> How can you explain the method bump without the notion of lvalue?

I can't and I just consider the introduction of lvalues to model
states in objects as a flaw in the design of this feature (and I
certainly never have promoted it). Reintroduction of lvalues just for
this questionable facility is an error.

> Perfectly coherent answers would be, let's remove mutable instance
> variables, or force the notation self.x to access variables.

Yes. That's what we should have done, since we love perfectly coherent
answers for Caml.

> Another answer is that people so fond of objects have already heared
> of lvalues anyway.

So what ?

I cannot consider such a vague argument as a satisfactory answer to an
important language design decision, since this ``answer'' is not a
language design consideration. If we were using this kind of general
public oriented reasons as guidelines to develop the semantics of the
language, you could imagine I could state that ``people so fond of
objects have already heared of bus error anyway'', which is also true
I'm afraid, to justify the introduction of a feature that would cause
some bus errors from time to time!

> the problem is not only with lvalues either. With for loops, you have
> a case of rvalue, where something which is not syntactically a
> function have a changing variable, which is accessed directly. The
> fact you cannot change it yourself is not relevant.

What do you mean here ? A for loop being just a shorthand for the
definition of a function, I don't see the problem...

Best regards,

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Jacques Garrigue]

Bonjour Pierre,

> > You can of course explain the semantics this way, but most people
> > apparently consider that there are lvalues in ocaml, just that they
> > are very restricted. It is certainly much simpler to explain than
> > lvalues in C!
> 
> Most people consider Caml as a toy language, since it is not a
> mainstream language. As a computer science researcher fond of riguour,
> I certainly will not organize a vote to find out if ``most people
> apparently consider'' something, to decide that this something is
> true.

I didn't ask for one. I'm basically agreeing with you that once we
have a good property, we shall stick to it.
My remark was just that it was not a completely unreasonable way to
explain the behaviour of assignment, and that thanks to good
properties, this was kept simple.

> A more interesting contribution would be to give evidences that
> references and arrays and other imperative features are indeed built
> with lvalues in Caml.

Indeed the type checker has an individual case for each of the
assignment constructs, so the parallel with lvalues is only on
surface. (More precisely, only records are handled by the type
checker, other ones are just syntactic sugar.)

> > Also, there is one unique case currently which can only be explained
> > by the distinction lvalue/rvalue: instance variables in objects.
> 
> > Perfectly coherent answers would be, let's remove mutable instance
> > variables, or force the notation self.x to access variables.
> 
> Yes. That's what we should have done, since we love perfectly coherent
> answers for Caml.

Indeed.

> > Another answer is that people so fond of objects have already heared
> > of lvalues anyway.
> 
> So what ?

I was just wondering why it is the way it is, nothing more.
I suppose we're not going to change it anyway, considering the
quantity of code involved. The best would be not to have it in the
first place.

> > the problem is not only with lvalues either. With for loops, you have
> > a case of rvalue, where something which is not syntactically a
> > function have a changing variable, which is accessed directly. The
> > fact you cannot change it yourself is not relevant.
> 
> What do you mean here ? A for loop being just a shorthand for the
> definition of a function, I don't see the problem...

If we take your previous argument of evidences in the compiler, the
loop variable is indeed compiled as a lvalue. There is no function
involved, and the for loop goes down to the backend.
But I agree that you can handle this as syntactic sugar, and provide a
semantics without rvalues for it.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Georges Brun-Cottan]

Bonjour Jacques,

>  > > the problem is not only with lvalues either. With for loops, you have
>  > > a case of rvalue, where something which is not syntactically a
>  > > function have a changing variable, which is accessed directly. The
>  > > fact you cannot change it yourself is not relevant.

I think it is relevant: it is not uncommon in C to mistakenly
transform a simple finite loop in an infinite one through side-effect
to the loop control variable... The 'for' loop makes the point very
clear that you are protected against this case.

[...]  and later on 

> If we take your previous argument of evidences in the compiler, the
> loop variable is indeed compiled as a lvalue. There is no function
> involved, and the for loop goes down to the backend.

But it can not be assigned explicitely by the programmer, right?

-- Georges
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[John Max Skaller]

Pierre Weis wrote:

> A more interesting contribution would be to give evidences that
> references and arrays and other imperative features are indeed built
> with lvalues in Caml.

	To do that, one must understand what an lvalue is.
In C, it is an expression term obeying certain syntactic
constraints.  That is, it is not a matter of semantics,
or typing: an lvalue is a particular piece of syntax.

	To say that another way, some constraints on the
language _syntax_ are not imposed by the grammar, but by 
additional rules such as 'the argument of the unary & operator
must be an lvalue'.

	This is NOT the case in C++, where the typing
is related to lvalueness. Note that in BOTH cases,
lvalueness is related to addressability, NOT necessarily
mutability. In C++, non-lvalues are definitely mutable!

	[The rules in C++ are a shambles]

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Michael Sperber [Mr. Preprocessor]]

Here's a shameless plug for a paper which also examines some related
issues and briefly talks about mutable let as well:

@InProceedings{SperberThiemann1998,
  author = 	 {Michael Sperber and Peter Thiemann},
  title = 	 {{ML} and the Address Operator},
  booktitle = 	 {1998 {ACM-SIGPLAN} Workshop on {ML}},
  crossref =	 {ML1998},
  pages =	 {4--13},
  year =	 1998
}

@Proceedings{ML1998,
      title =        "1998 {ACM-SIGPLAN} Workshop on {ML}",
      booktitle =    "1998 {ACM-SIGPLAN} Workshop on {ML}",
      year =         "1998",
      month =     sep,
      address = "Baltimore, Maryland"
}

I'll be glad to send PostScript to anyone who asks.

-- 
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Dave Berry]

I once advocated a "const" datatype for SML.  The const constructor
would create unique immutable values that could be compared for pointer
equality, satisfying Don's first use of refs.  (It's possible I included
these in the Edinburgh SML Library -- I don't recall after all these
years).  But this idea never caught on.

A similar idea is to define:
  type 'a pointer = 'a option ref
  fun null (ref NONE) = true | null _ = false
  fun ::= (p, v) = p := SOME v

Dave.


-----Original Message-----
From: Don Syme [mailto:dsyme@microsoft.com]
Sent: 15 June 2001 04:20

[ To expand on why "mutable" fields are, IMHO, so much better...  In
Standard ML "refs" get used in data structures for four main purposes: 
  - to get values that can be compared by pointer equality; 
  - to ensure sharing of an allocation cell; 
  - to allow "regular" mutation; 
  - to cope with initializing recursive data structures using "ref
option".  

Because of these multiple uses I honestly used to get "ref" type
constructors nested two or three deep (when designing some
pointer-chasing graph structures)!!  

I was never able to get this code right until I switched to Caml,
precisely because my structures became simpler.  In Caml the combination
of inbuilt pointer equality and "mutable" made things sufficiently
simple, and the ability to allocate at least some recursively linked
objects without using "ref option" also helped.  
]

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Don Syme]

Hi Pierre,

> On the language design side, we worked hard to bypass the limitations
> of letrefs in order to design first class citizens references, and to
> get rid of left values in the language. On the compiler construction
> side, Xavier worked hard to optimise spurious allocations of
> references that can be treated as vars. I think we now have the power
> and conceptual simplicity of references along with the runtime
> efficiency of letrefs, I don't see the point to introduce a new
> arguably useless construct.

I agree with most of what you say, but only in the sense that I would
agree that "mutable" is not really needed for record fields either, and
that programmers could be forced to live with Standard ML's "ref" just
to keep the language slightly simpler.  

But then why is "mutable" on record fields better for the working
imperative programmer?  Firstly because it's just closer to C.  But I
think it might also be the case that using "mutable" is just lighter on
the programmer's mind than using "ref".  My feeling is that the same
holds true for let-bound variables.  

[ To expand on why "mutable" fields are, IMHO, so much better...  In
Standard ML "refs" get used in data structures for four main purposes: 
  - to get values that can be compared by pointer equality; 
  - to ensure sharing of an allocation cell; 
  - to allow "regular" mutation; 
  - to cope with initializing recursive data structures using "ref
option".  

Because of these multiple uses I honestly used to get "ref" type
constructors nested two or three deep (when designing some
pointer-chasing graph structures)!!  

I was never able to get this code right until I switched to Caml,
precisely because my structures became simpler.  In Caml the combination
of inbuilt pointer equality and "mutable" made things sufficiently
simple, and the ability to allocate at least some recursively linked
objects without using "ref option" also helped.  
]

Mutable let-bound variables aren't as important as mutable fields, but I
don't see any great harm in having them.  OCaml is almost a truly great
imperative programming language, and I reckon if you added these then
you'd be a bit closer to this goal.  But at the moment C programs still
look like a bit of a mess when translated over to OCaml: too many "refs"
and "!"s...  These are fine if you're writing the stuff, but look pretty
crazy when you show the code to a C programmer (for starters ! gets
confused with C's "not"...)

(As an aside I will mention that I would like to see some remaining
problems solved: specifying enforced sharing by some other means than
using refs; and being able to "tie the knot" on recursive structures
that extend beyond a finite number of simultaneously allocated
cons-cells, without using "ref option". I guess both of these are pretty
hard to solve.  More realistically, I also don't see any harm at all in
having an extended "for" loop construct much as I proposed a year or so
ago.)

Don

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Dave Berry]

Let me refute my own suggestion.  If people do want the ability to
specify stack allocation, they will want it for immutable values as well
as mutable values.  So it should be a separate, orthogonal construct.


-----Original Message-----
From: Dave Berry 
Sent: 08 June 2001 10:00
To: Jacques Garrigue; tom7ca@yahoo.com
Cc: williamc@paneris.org; caml-list@inria.fr
Subject: RE: [Caml-list] let mutable (was OCaml Speed for Block
Convolutions)


One possible reason for adding "let mutable" would be to specify that
escapes (such as the one Jacques gave) are explicitly disallowed.  In
other words, programmers could use "let mutable" to enforce the
requirement that the data is stack-allocated.  The compiler would report
an error if it is not possible to stack-allocate, instead of silently
defaulting to heap allocation.  Programmers might want to do this to
guarantee efficiency, or to guarantee that the memory is deallocated and
does not become a potential memory leak.

It might even be possible to attach finalisers to the data, which would
be guaranteed to be called when the function exits, analogous to C++
destructors.  However, this would complicate exception handling and
possibly tail-recursion optimisations.


-----Original Message-----
From: Jacques Garrigue [mailto:garrigue@kurims.kyoto-u.ac.jp]
Sent: 08 June 2001 00:50
To: tom7ca@yahoo.com
Cc: williamc@paneris.org; caml-list@inria.fr
Subject: [Caml-list] let mutable (was OCaml Speed for Block
Convolutions)


About the introduction of a let mutable construct,
Tom _ <tom7ca@yahoo.com> wrote

> In any case, whether or not the compiler in the
> current implementation can or cannot do good type
> inference and may or may not be forced to box
> a floating point number, the two constructs mean
> something different to the programmer, and they
> behave differently.  In particular "mutable x"
> can never be passed around as a reference, while
> "x = ref ..." can.  If not anything else, that
> prevents the programmer from inadvertently inhibiting
> a compiler optimization by passing around a reference.

Not exactly, the compiler may still need to build a reference.

    let mutable x = 0 in
    List.iter (fun y -> x <- x+y) l;
    x

Since x has to be modified in a function called by iter, it must be
wrapped into an actual reference cell.

As the compiler already does a good job at unboxing only locally used
references, let mutable would only be some syntactic sugar (with
exactly the same typing as a reference).

> Besides, the syntax is probably quite a bit more 
> natural to imperative programmers anyway.

This is actually the only argument for let mutable.
I would also like such a construct, but I don't know whether its worth
it. The real question is whether let mutable should be allowed at
toplevel, with problems for both answers.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
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/
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/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Dave Berry]

One possible reason for adding "let mutable" would be to specify that
escapes (such as the one Jacques gave) are explicitly disallowed.  In
other words, programmers could use "let mutable" to enforce the
requirement that the data is stack-allocated.  The compiler would report
an error if it is not possible to stack-allocate, instead of silently
defaulting to heap allocation.  Programmers might want to do this to
guarantee efficiency, or to guarantee that the memory is deallocated and
does not become a potential memory leak.

It might even be possible to attach finalisers to the data, which would
be guaranteed to be called when the function exits, analogous to C++
destructors.  However, this would complicate exception handling and
possibly tail-recursion optimisations.


-----Original Message-----
From: Jacques Garrigue [mailto:garrigue@kurims.kyoto-u.ac.jp]
Sent: 08 June 2001 00:50
To: tom7ca@yahoo.com
Cc: williamc@paneris.org; caml-list@inria.fr
Subject: [Caml-list] let mutable (was OCaml Speed for Block
Convolutions)


About the introduction of a let mutable construct,
Tom _ <tom7ca@yahoo.com> wrote

> In any case, whether or not the compiler in the
> current implementation can or cannot do good type
> inference and may or may not be forced to box
> a floating point number, the two constructs mean
> something different to the programmer, and they
> behave differently.  In particular "mutable x"
> can never be passed around as a reference, while
> "x = ref ..." can.  If not anything else, that
> prevents the programmer from inadvertently inhibiting
> a compiler optimization by passing around a reference.

Not exactly, the compiler may still need to build a reference.

    let mutable x = 0 in
    List.iter (fun y -> x <- x+y) l;
    x

Since x has to be modified in a function called by iter, it must be
wrapped into an actual reference cell.

As the compiler already does a good job at unboxing only locally used
references, let mutable would only be some syntactic sugar (with
exactly the same typing as a reference).

> Besides, the syntax is probably quite a bit more 
> natural to imperative programmers anyway.

This is actually the only argument for let mutable.
I would also like such a construct, but I don't know whether its worth
it. The real question is whether let mutable should be allowed at
toplevel, with problems for both answers.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
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/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr