[Caml-list] look operator

[Caml-list] look operator

[Winfried Dreckmann]

Dear everyone,

I can't resist to ask for people's opinion on a certain compromise between
imperative and functional programming which a found in the "numerix" library
of Michel Quercia. Of course, if you read this, Michel, I would be
particularly grateful for your own opinion.

It's about abstracting the ! operator by introducing a function

val look : tref -> t

which coerces a mutable object into a non-mutable one. Using this function
is dangerous because, with this function, the non-mutable type t is not
strictly non-mutable anymore. As the manual says, the result of "look r" is
volatile, it is only guaranteed to be valid until the next in-place
operation involving r. In my own experience, mistakes occur faster than
expected. But this is a great and elegant trick. Using "look", every single
function with arguments of type t, say

val add_in : tref -> t -> t -> unit,

replaces two or more functions which would otherwise be necessary, in this
case

val add_in1 : tref -> t -> t -> unit
val add_in2 : tref -> tref -> t -> unit
val add_in3 : tref -> tref -> tref -> unit

at least. This would certainly blow up the library to impractical
dimensions. Of course, overloading would help, and "look" might become
obsolete in this way.
However, I think the problem is not mainly about overloading, but about
reintroducing imperative features in an abstract and controlled way. I
could, for instance, also imagine an abstract assign operator

val set : tref -> t -> unit

where the contents of t is not copied but assigned to tref, and thus made
mutable, which could be useful in certain restricted ways.

My question to the caml list: Would you accept such constructions as decent
Caml programming, if applied carefully and only in cases where it allows
what is otherwise impossible (e. g. integrating mutable and non-mutable
objects as it is done in "numerix"). Or is it all just a silent
reintroduction of C pointers, and principally a bad thing?

Regards,
Winfried Dreckmann

-------------------
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] look operator

[Pixel]

Winfried Dreckmann <wd@lidingo.mail.telia.com> writes:

[...]

> It's about abstracting the ! operator by introducing a function
> 
> val look : tref -> t
> 
> which coerces a mutable object into a non-mutable one. Using this function
> is dangerous because, with this function, the non-mutable type t is not
> strictly non-mutable anymore. As the manual says, the result of "look r" is
> volatile, it is only guaranteed to be valid until the next in-place
> operation involving r. In my own experience, mistakes occur faster than
> expected. But this is a great and elegant trick.

=> "look" is only used for efficiency? couldn't the compiler achieve
the same result without using an unsafe construct?

> Using "look", every single
> function with arguments of type t, say
> 
> val add_in : tref -> t -> t -> unit,
> 
> replaces two or more functions which would otherwise be necessary, in this
> case
> 
> val add_in1 : tref -> t -> t -> unit
> val add_in2 : tref -> tref -> t -> unit
> val add_in3 : tref -> tref -> tref -> unit

are you saying that i would be nice to have this? As far as i have
looked at numerix, it doesn't have this.

> 
> at least. This would certainly blow up the library to impractical
> dimensions. Of course, overloading would help, and "look" might become
> obsolete in this way.
> However, I think the problem is not mainly about overloading,

agreed, row subtyping can already achieve this:

----------------------------------------
let add_in_wrapped r a b = r := !r + a + b

let deref = function
  | `Ref a -> !a
  | `Const a -> a

let add_in (`Ref a) b c = add_in_wrapped a (deref b) (deref c)

let x = `Ref (ref 1)
let y = `Ref (ref 2)
let c = `Const 3
;;
add_in x y c ; x
----------------------------------------

> but about
> reintroducing imperative features in an abstract and controlled way. I
> could, for instance, also imagine an abstract assign operator
> 
> val set : tref -> t -> unit
> 
> where the contents of t is not copied but assigned to tref, and thus made
> mutable, which could be useful in certain restricted ways.
> 
> My question to the caml list: Would you accept such constructions as decent
> Caml programming, if applied carefully and only in cases where it allows
> what is otherwise impossible (e. g. integrating mutable and non-mutable
> objects as it is done in "numerix"). Or is it all just a silent
> reintroduction of C pointers, and principally a bad thing?

I don't think this will never be in OCaml!
(but i may be prooved wrong :)

I've not found many information about this. AFAIK C++ is the only
language having constness subtyping (http://merd.net/inoutness.html)

The few links i've found: http://merd.net/inoutness.html#references
I someone knows better, please tell, i'm interested :)

-------------------
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] look operator

[Michel Quercia]

Le Thu, 06 Jun 2002 12:01:02 +0200
Winfried Dreckmann <wd@lidingo.mail.telia.com> écrivit :

> Dear everyone,
> 
> I can't resist to ask for people's opinion on a certain compromise between
> imperative and functional programming which a found in the "numerix" library
> of Michel Quercia. Of course, if you read this, Michel, I would be
> particularly grateful for your own opinion.

OK, here are some motivations for introducing trefs into Numerix and the strange-behaved look operation.

If one writes :

 r := add !r x

where "r" is an ordinary Ocaml reference to some big integer and "x" is another big integer, then the addition of r.contents and x will be performed, some fresh memory will be allocated for holding
the result, and the memory holding the previous content of "r" will be returned back to the memory pool (actually there is no memory return, the GC finds by itself which blocs of memory can be
recycled). Very often, the size of the result is equal to the size of the former content of "r", therefore one ends up with asking the Ocaml memory manager for a memory block and returning a few
microseconds later some other bloc of the same size. This is inefficient, and it is dramatically inefficient inside of inner loops. One can speed up things by using the memory already allocated to
r.contents for storing the result if this memory bloc is large enough, and if the former content was only reachable through "r". Doing this way, Ocaml memory manager is not bothered at all, and I
observed a global speedup factor of 2 when implementing this "recycle now" policy in the program I was developping at that time (Hamming numbers chase).

> As the manual says, the result of "look r" is
> volatile, it is only guaranteed to be valid until the next in-place
> operation involving r.

I think that I'll try and rewrite this sentence better for next Numerix release. One should read : "the result is always a valid big integer, but the value of this integer is granted to be constant
only until the next in-place operation involving r. With the current implementation, after the instruction :

let l = look r in xxx_in r <expression>

the identifier "l" is bound either to the former value held by "r" or to the new one. The "look" operation should be restricted to local use only, and the "copy_out" operation should be used whenever
it can not be proved that r will never be modified again."


> In my own experience, mistakes occur faster than
> expected.

Right, and should such an operation become standard, then the compiler should check that the tref "r" becomes unreachable after the last "look" (this may be easier to say than to implement).

> But this is a great and elegant trick.

Thanks,

> Using "look", every single
> function with arguments of type t, say
> 
> val add_in : tref -> t -> t -> unit,
> 
> replaces two or more functions which would otherwise be necessary, in this
> case
> 
> val add_in1 : tref -> t -> t -> unit
> val add_in2 : tref -> tref -> t -> unit
> val add_in3 : tref -> tref -> tref -> unit
> 
> at least. This would certainly blow up the library to impractical
> dimensions.

On my side it would not be a big burden, just a matter of adding some preprocessing step, but it is definitely unmanageable on the user side.

> Of course, overloading would help, and "look" might become
> obsolete in this way.

I think overloading is absolutely necessary when dealing with numerical data. Writing some mathematical code invloving short integers, big integers, vectors and matrices for instance is a nightmare
with the current Ocaml syntax. When such an overloading mechanism will be available, the "look" operation will disappear at the next Numerix release (but not the "trefs").


> I could, for instance, also imagine an abstract assign operator
> 
> val set : tref -> t -> unit
> 
> where the contents of t is not copied but assigned to tref, and thus made
> mutable, which could be useful in certain restricted ways.

This is too dangerous :

let e1 = ... and e2 = ... in
set r (if ... then e1 else e2);
xxx_in r ...;

(* try and guess what will be e1 and e2 now *)

Regards,
-- 
Michel Quercia
57 rue abbé Grégoire, 38000 Grenoble
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org
-------------------
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] look operator

[Winfried Dreckmann]

on 06.06.2002 12:58 Uhr, Pixel at pixel@mandrakesoft.com wrote:

> => "look" is only used for efficiency? couldn't the compiler achieve
> the same result without using an unsafe construct?

Yes, only for efficiency, see Michel Quercia's reply. As you point out,
there are other ways to do the same thing which are safe but cost too much.

>> Using "look", every single
>> function with arguments of type t, say
>> 
>> val add_in : tref -> t -> t -> unit,
>> 
>> replaces two or more functions which would otherwise be necessary, in this
>> case
>> 
>> val add_in1 : tref -> t -> t -> unit
>> val add_in2 : tref -> tref -> t -> unit
>> val add_in3 : tref -> tref -> tref -> unit
> 
> are you saying that i would be nice to have this? As far as i have
> looked at numerix, it doesn't have this.

No, I'm saying that "add_in" together with "look" has the same functionality
as the three functions below. I find this quite elegant, if there were no
safety issues with "look".

>> My question to the caml list: Would you accept such constructions as decent
>> Caml programming, if applied carefully and only in cases where it allows
>> what is otherwise impossible (e. g. integrating mutable and non-mutable
>> objects as it is done in "numerix"). Or is it all just a silent
>> reintroduction of C pointers, and principally a bad thing?
> 
> I don't think this will never be in OCaml!
> (but i may be prooved wrong :)

Right so! But with the C interface you can program such constructions
anyway. I wouldn't see a problem at all if all unsafety is hidden from the
user. However, in the case of "look" in the "numerix" library a certain
amount of unsafety is left to the user. This is unsatisfactory. Michel
Quercia describes some ideas to solve this problem in his letter.

Thanks for the link.

Winfried Dreckmann



-------------------
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] look operator

[Winfried Dreckmann]

on 06.06.2002 17:08 Uhr, Michel Quercia at michel.quercia@prepas.org wrote:

> The "look" operation should be restricted to local use only, and the
> "copy_out" operation should be used whenever
> it can not be proved that r will never be modified again."

Thanks for your long explanations. I understand that you are concerned with
the safety problem.

> Right, and should such an operation become standard, then the compiler should
> check that the tref "r" becomes unreachable after the last "look" (this may be
> easier to say than to implement).

I think it's an interesting idea which one should keep in mind.

> I think overloading is absolutely necessary when dealing with numerical data.
> ...
> When such an overloading mechanism will be available, the "look" operation
> will disappear at the next Numerix release (but not the "trefs").

That would be the best solution. Not the "trefs" of course. Having t's and
tref's together is the best part.

>> I could, for instance, also imagine an abstract assign operator
>> 
>> val set : tref -> t -> unit
>> 
>> where the contents of t is not copied but assigned to tref, and thus made
>> mutable, which could be useful in certain restricted ways.
> 
> This is too dangerous :
>
> let e1 = ... and e2 = ... in
> set r (if ... then e1 else e2);
> xxx_in r ...;
>
> (* try and guess what will be e1 and e2 now *)

Definitely. Actually I was thinking about implementing matrices with mutable
entries where for efficiency reasons the implementation type of entries
would be t, and of course implementation details would be hidden by the
interface. To do this with Numerix one would at least need a function

val set : tref -> t matrix -> int -> int -> unit

to make matrix entries accessible to in-place operations (with an subsequent
update to make sure the entries get really changed). So I thought there is
more to "look" than "look", and that assignment operators are also worth
considering. But this is stretching it very far. In fact, the above way of
implementing matrices with mutable entries looks like a kind of unboxing,
and this may be best seen, according to Xavier Leroy, as an optimization.

Regards,
Winfried Dreckmann

-------------------
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] look operator

[Michel Quercia]

Le Fri, 07 Jun 2002 11:13:24 +0200
Winfried Dreckmann <wd@lidingo.mail.telia.com> écrivit :

> Definitely. Actually I was thinking about implementing matrices with
> mutable entries where for efficiency reasons the implementation type of
> entries would be t, and of course implementation details would be hidden
> by the interface. To do this with Numerix one would at least need a
> function
> 
> val set : tref -> t matrix -> int -> int -> unit
> 
> to make matrix entries accessible to in-place operations (with an
> subsequent update to make sure the entries get really changed).

Well, I can easily add such a function, but there remains a few problems
to solve first.

1. Is it okay to have some matrix entry change of value at any time
because we are reusing the tref for some other computation ? Some
machinery could be used to prevent this, for instance clearing the tref
once its value has been "transfered" through a "set" operation.

2. We would need a lot of different "set" functions, one for vectors, one
for matrices, one for each (record type, mutable field) pair that may
happen to be usefull...

3. We can restrict the spread of mutable data to vectors and provide a new
datatype : tvector with its collection of associated functions : vlook,
vadd_in, vmul_in, ...

My preference goes to 3.

Regards,
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org
-------------------
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] look operator

[Winfried Dreckmann]

on 07.06.2002 15:52 Uhr, Michel Quercia at michel.quercia@prepas.org wrote:

> Well, I can easily add such a function, but there remains a few problems
> to solve first.
> 
> 1. Is it okay to have some matrix entry change of value at any time
> because we are reusing the tref for some other computation ? Some
> machinery could be used to prevent this, for instance clearing the tref
> once its value has been "transfered" through a "set" operation.

> 2. We would need a lot of different "set" functions, one for vectors, one
> for matrices, one for each (record type, mutable field) pair that may
> happen to be usefull...
> 
> 3. We can restrict the spread of mutable data to vectors and provide a new
> datatype : tvector with its collection of associated functions : vlook,
> vadd_in, vmul_in, ...
> 
> My preference goes to 3.

I thought of something like 1, but you are right, 3 would be the most
practical way.

> Regards,

Winfried Dreckmann



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