[Caml-list] const equivalent for mutable types?

[Caml-list] const equivalent for mutable types?

[Christopher A. Gorski]

In my code I find that I'm passing a lot of mutable values to functions. 
  Some functions merely read the values.  Others modify the values.  Is 
there a method in OCaml for reproducing behavior similar in spirit to 
the const declaration in C?

Here is a specific case of the general problem:

let t=ref 0
let change r = incr r
let nochange r = Printf.printf "test:%d\n" !r

The problem is that in complex programs I often get confused over what 
functions are modifying values and what functions are not.  I feel like 
I should be able to do something like

let result = change (const r)

and have the compiler give me a type error.

Is there a way to do this in OCaml?  Should I change my programming 
style?  Am I asking a naive question that's already been answered many 
times over in a different form?

-- 
Chris Gorski - http://cgorski.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] const equivalent for mutable types?

[Jean-Marie Gaillourdert]

Hi,

Am Samstag, 31. Juli 2004 10:56 schrieb Christopher A. Gorski:
> In my code I find that I'm passing a lot of mutable values to functions.
>   Some functions merely read the values.  Others modify the values.  Is
> there a method in OCaml for reproducing behavior similar in spirit to
> the const declaration in C?

In a purely functional language every parameter is "const". Although OCaml is 
not pure this behaviour is still the default. 

> Here is a specific case of the general problem:
>
> let t=ref 0
> let change r = incr r
> let nochange r = Printf.printf "test:%d\n" !r
>
> The problem is that in complex programs I often get confused over what
> functions are modifying values and what functions are not.  I feel like
> I should be able to do something like
>
> let result = change (const r)
>
> and have the compiler give me a type error.
>
> Is there a way to do this in OCaml?  Should I change my programming
> style?  Am I asking a naive question that's already been answered many
> times over in a different form?

There is a very simple way to do so: Just don't pass the references around.

let t=ref 0
let change r = incr r
let nochange r = Printf.printf "test:%d\n" r

You can now distinguish "const" parameters from "non-const" parameters.

change t
nochange !t 


Regards,
 Jean-Marie Gaillourdet

-------------------
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] const equivalent for mutable types?

[Jean-Marie Gaillourdert]

Hi,
> Am Samstag, 31. Juli 2004 10:56 schrieb Christopher A. Gorski:
> > The problem is that in complex programs I often get confused over what
> > functions are modifying values and what functions are not.  I feel like
> > I should be able to do something like
> >
> > let result = change (const r)
> >
> > and have the compiler give me a type error.

let  const = (!)

will do the trick.

Regards,
  Jean-Marie Gaillourdet

-------------------
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] const equivalent for mutable types?

[Markus Mottl]

On Sat, 31 Jul 2004, Christopher A. Gorski wrote:
> In my code I find that I'm passing a lot of mutable values to functions. 
>  Some functions merely read the values.  Others modify the values.  Is 
> there a method in OCaml for reproducing behavior similar in spirit to 
> the const declaration in C?

No, you'd need an abstract module for this to hide the concrete
representation.  This is actually good SE-practice.

You can do this very conveniently using so-called phantom types.  For the
special case of references, here is an example that implements ones,
which can be made constant:

---------------------------------------------------------------------------
module type REF = sig
  type ('a, 'rw) t

  val ref : 'a -> ('a, [ `R | `W ]) t
  val (!) : ('a, [> `R ]) t -> 'a
  val (:=) : ('a, [> `W ]) t -> 'a -> unit

  val incr : (int, [> `W ]) t -> unit
  val decr : (int, [> `W ]) t -> unit

  external const : ('a, [> `R ]) t -> ('a, [ `R ]) t = "%identity"
  external normal_ref : ('a, [ `R | `W ]) t -> 'a ref = "%identity"
end

module Ref : REF = struct
  type ('a, 'rw) t = 'a ref

  let ref = ref
  let (!) = (!)
  let (:=) = (:=)

  let incr = incr
  let decr = decr

  external const : ('a, [> `R ]) t -> ('a, [ `R ]) t = "%identity"
  external normal_ref : ('a, [ `R | `W ]) t -> 'a ref = "%identity"
end
---------------------------------------------------------------------------

The phantom variable is 'rw.  When creating references, it can be any
of `R (for reading) and `T (for writing).  Some functions only require
the reference to be readable (like (!)), others only need to write to
them (e.g. (:=)).  References are made constant by simply applying the
(internal) identity function to them, which is actually a no-op.  But we
only leave the `R-flag in the type.  A "normal" reference can be made
from the upper ones only if they support both reading and writing.

> let result = change (const r)
> 
> and have the compiler give me a type error.

Now we try this out with your example:

---------------------------------------------------------------------------
open Ref

let () =
  let t = ref 0 in
  let change r = incr r in
  let nochange r = Printf.printf "test:%d\n" !r in
  change (const t)
---------------------------------------------------------------------------

And we get:

  This expression has type (int, [ `R ]) Ref.t but is here used with type
    (int, [> `W ]) Ref.t

"nochange" will work without a type error as expected.

Regards,
Markus

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
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] const equivalent for mutable types?

[Markus Mottl]

On Sat, 31 Jul 2004, Jean-Marie Gaillourdert wrote:
> There is a very simple way to do so: Just don't pass the references
> around.

For references this is certainly usually the preferred case, but for
mutable records this would be plain awkward.  You don't always want to
copy all data in a structure to an otherwise equivalent constant record.

Even in the case of references you might have a SE-problem: what do
you do if you suddenly discover that it is necessary to overwrite a
reference in a large function which only used the plain value before?
This might require tons of changes.  If you want to deliberately leave
this option open, just pass the reference with an additional "read-only"
type constraint.

Regards,
Markus

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
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] const equivalent for mutable types?

[Jon Harrop]

On Saturday 31 July 2004 11:34, Markus Mottl wrote:
> ...
>   val incr : (int, [> `W ]) t -> unit
>   val decr : (int, [> `W ]) t -> unit

Should these both be [`R|`W]?

> The phantom variable is 'rw.  When creating references, it can be any
> of `R (for reading) and `T (for writing).

Do you mean `W for writing?

That's very interesting. So a phantom type is a type which you stick in to 
dupe the type system into doing something for you? Is there a good reference 
on those? I seem to remember a thread about their utility in porting the STL 
to ocaml but that was before I had ever used OCaml...

And this const-alternative is useful when dealing with large records which 
have mostly constant but some mutable entries because handling such records 
invokes a lot of copying? But, say, arrays are passed by reference so this 
wouldn't provide much of a performance advantage, is that right? 
Incidentally, does anyone have a functional array implementation (which 
doesn't suck ;-)?

Cheers,
Jon.

-------------------
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] const equivalent for mutable types?

[Brian Hurt]

On Sat, 31 Jul 2004, Christopher A. Gorski wrote:

> In my code I find that I'm passing a lot of mutable values to functions. 
>   Some functions merely read the values.  Others modify the values.  Is 
> there a method in OCaml for reproducing behavior similar in spirit to 
> the const declaration in C?

Yeah.  Don't pass in a reference, pass in what the reference points at.

If you're passing a lot of mutable arguments around, I'd start rethinking 
your design.  Mutable arguments should be few and far between.

Two functional design patterns you might not be aware of, that should help 
eliminate a lot of mutable arguments:

1) Use tuples to return multiple values.  One of the most common 
reasons in C/C++/Java programming to using mutable arguments is to return 
multiple values from a function.  Say you have a function that takes an 
integer and a string, and returns a boolean and a float.  In C/C++, you 
might have a header something like:
    bool foo(int arg1, char * arg2, double * res2_p);
res2_p is the pointer to the location to store the second result, the 
float.  In Ocaml, the function should have the type:
    val foo: int -> string -> bool * float
The advantage of doing this is in Ocaml is that the caller can drop the 
return values into whatever variables they want, like:
    let succeeded, fval = foo(3, "bar") in
    ...

It also makes what is an input to the function and what is an output of 
the function clear.

2) Return the updated data structure.  Another common reason to use 
mutable arguments is to pass in a data structure that the routine then 
modifies.  Instead of having the data structure be modified, have the 
routine return the replacement data structure.  Say you have a StringMap 
module, defined like:
module StringMap = Map.Make(String);;

You want to write a routine that adds the key "foo" and the value 3 to an 
int StringMap.t- thus modifying the data structure.  The function should 
have the type:
val add_foo: int StringMap.t -> int StringMap.t

And might be implemented like:
let add_foo smap = StringMap.add "foo" 3 smap;;

The big advantage here is that the caller gets to decide which version of 
versions of the data structure they continue to use- the old, unmodified 
version, or the new, modified version, or both.


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
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] const equivalent for mutable types?

[Brian Hurt]

On Sat, 31 Jul 2004, Markus Mottl wrote:

> On Sat, 31 Jul 2004, Jean-Marie Gaillourdert wrote:
> > There is a very simple way to do so: Just don't pass the references
> > around.
> 
> For references this is certainly usually the preferred case, but for
> mutable records this would be plain awkward.  You don't always want to
> copy all data in a structure to an otherwise equivalent constant record.
> 
> Even in the case of references you might have a SE-problem: what do
> you do if you suddenly discover that it is necessary to overwrite a
> reference in a large function which only used the plain value before?
> This might require tons of changes.  If you want to deliberately leave
> this option open, just pass the reference with an additional "read-only"
> type constraint.
> 

This way lies hell.

The problem is that if the called function *can* modify the argument, 
there is an extra, uncheckable, dependency between the caller and called 
functions.  The depedency can work in both ways- with the caller depending 
on the called function changing the argument in some known way, or with 
the caller depending upon the called function not changing the argument.  
If you violate these constraints, you can easily wind up with a bug.

Another thing to note: const in C/C++ isn't.  I can always type cast 
around the const and modify the memory anyways.  Even ignoring wild 
pointers.

Worrying about how long it takes to allocate a new structure is being
pennywise and pound foolish- and committing premature optimization.  
Especially considering you're most likely copying from L1 cache back to L1
cache, which is real cheap.  Copying a small (3-8 element) structure from
L1 cache to a different place in L1 cache is 10-20 clock cycles.  A single
cache miss that goes to main memory is 100-350 clock cycles.  Which means
I can copy that structure 5-35 times in the time it takes me to just load 
it the first time.

Take a gander at:
http://citeseer.ist.psu.edu/goncalves95cache.html

First, get your program working.  Then measure it, and see if it's fast 
enough.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
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] const equivalent for mutable types?

[Markus Mottl]

On Sat, 31 Jul 2004, Brian Hurt wrote:
> The problem is that if the called function *can* modify the argument, 
> there is an extra, uncheckable, dependency between the caller and called 
> functions.  The depedency can work in both ways- with the caller depending 
> on the called function changing the argument in some known way, or with 
> the caller depending upon the called function not changing the argument.  
> If you violate these constraints, you can easily wind up with a bug.

Sure.  That's also why I think that using non-mutable datastructures
should always be preferred.

> Another thing to note: const in C/C++ isn't.  I can always type cast
> around the const and modify the memory anyways.  Even ignoring wild
> pointers.

Well, you can also always use Obj.magic in OCaml (newbies beware:
DON'T!)... ;-)

> Worrying about how long it takes to allocate a new structure is being
> pennywise and pound foolish- and committing premature optimization.  

I wasn't referring to optimization, this is a different topic.
But there may also be semantic issues.  E.g. you may not want to lose
the possibility of using physical identity (==) on structures.

Regards,
Markus

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

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

[Caml-list] Phantom types

[Markus Mottl]

On Sat, 31 Jul 2004, Jon Harrop wrote:
> On Saturday 31 July 2004 11:34, Markus Mottl wrote:
> > ...
> >   val incr : (int, [> `W ]) t -> unit
> >   val decr : (int, [> `W ]) t -> unit
> 
> Should these both be [`R|`W]?

Well, in this case it doesn't really matter.  The upper version would
also accept only writable references in addition to readable ones.
But they must be at least writable.  Even other attributes would be
accepted as long as `W is one of them.

> > The phantom variable is 'rw.  When creating references, it can be any
> > of `R (for reading) and `T (for writing).
> 
> Do you mean `W for writing?

Sorry, yeah.

> That's very interesting. So a phantom type is a type which you stick in
> to dupe the type system into doing something for you? Is there a good
> reference on those? I seem to remember a thread about their utility
> in porting the STL to ocaml but that was before I had ever used OCaml...

Indeed, phantom types are extremely neat.  Sometimes I think that every
type, including basic ones, should actually have a polymorphic parameter,
which can later be used for constraining it.

E.g.:

---------------------------------------------------------------------------
module type PHANTOM_INT = sig
  type 'p t

  val add : 'p t -> 'p t -> 'p t

  val add_even_even : [> `Even ] t -> [> `Even ] t -> [> `Even ] t
  val add_even_odd : [> `Even ] t -> [> `Odd ] t -> [> `Odd ] t
  val add_odd_even : [> `Odd ] t -> [> `Even ] t -> [> `Odd ] t
  val add_odd_odd : [> `Odd ] t -> [> `Odd ] t -> [> `Even ] t
  val make_even : 'a t -> [ `Even ] t
  val make_odd : 'a t -> [ `Odd ] t
end

module PhantomInt : PHANTOM_INT = struct
  type 'p t = int

  let add = (+)
  let add_even_even = add
  let add_even_odd = add
  let add_odd_even = add
  let add_odd_odd = add
  let make_even n = if n mod 2 = 0 then n else failwith "not even"
  let make_odd n = if n mod 2 <> 0 then n else failwith "not odd"
end

module type PHANTOM_LIST = sig
  type ('a, 'p) t

  val rev : ('a, 'p) t -> ('a, 'p) t

  val rev_sorted_up : ('a, [> `SortedUp ]) t -> ('a, [> `SortedDown ]) t
  val rev_sorted_down : ('a, [> `SortedDown ]) t -> ('a, [> `SortedUp ]) t
end

module PhantomList : PHANTOM_LIST = struct
  type ('a, 'p) t = 'a list

  let rev = List.rev
  let rev_sorted_up = rev
  let rev_sorted_down = rev
end
---------------------------------------------------------------------------

You get the idea.  Phantom types not only allow you to capture
constraints, which are proved by the compiler, they are also perfectly
cheap computationally, because you don't have to check things at runtime
all the time.

E.g. after having successfully applied "make_even" to an integer, the
compiler guarantees that it won't be misused, i.e. other functions only
need to require this constraint in their type signature, and need not
check it at runtime anymore.

I wonder in how far generics could make these type checking tricks even
more powerful!

> And this const-alternative is useful when dealing with large records which 
> have mostly constant but some mutable entries because handling such records 
> invokes a lot of copying? But, say, arrays are passed by reference so this 
> wouldn't provide much of a performance advantage, is that right? 

> Incidentally, does anyone have a functional array implementation (which 
> doesn't suck ;-)?

If you mean O(1) with constants as low as imperative arrays: no ;-)

Regards,
Markus

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
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] const equivalent for mutable types?

[skaller]

On Sat, 2004-07-31 at 23:44, Jon Harrop wrote:

> Incidentally, does anyone have a functional array implementation (which 
> doesn't suck ;-)?

Map?

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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] const equivalent for mutable types?

[skaller]

On Sun, 2004-08-01 at 00:31, Brian Hurt wrote:

> 
> This way lies hell.

Balance is the key.

I have in fact just converted a functional algorithm
to an imperative one. Its the Felix inliner (which
inlines functions).

What happens is I replace a function call with
the body of the function being called with the
argument replacing the parameter.

The purely functional algorithm was 
inefficient: it has to inline recursively,
and in doing so, it inlines the same function
calls multiple times, because there are multiple
calls. It is faster to 'cache' any inlining done
into a function so when *it* is called the inlined
version can be inlined.

The easiest way to do this caching is simply replace
the function into which inlining is done with the
inlined version :)


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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

[Caml-list] Functional arrays

[Jon Harrop]

On Saturday 31 July 2004 17:35, skaller wrote:
> On Sat, 2004-07-31 at 23:44, Jon Harrop wrote:
> > Incidentally, does anyone have a functional array implementation (which
> > doesn't suck ;-)?
>
> Map?

Well, by "array" I mean a container with O(1) random access where "n" is the 
number of elements already in the container. ;-)

Also, I'd like it to "enforce" its size. With a map you could have an element 
missing. Although you may be able to write a balanced binary tree which used 
its depth information to enforce each element being filled. That might be 
interesting...

Anyway, I'm considering implementing arrays which look functional but which 
use built-in arrays and keep track of "derived" arrays (e.g. subarrays) using 
mutables under the bonnet and lazily re-jig them. I think this could make 
things substantially faster (better asymptotic complexity) in my context but 
I'm entirely unsure of how bad the constant prefactor would be hit.

Cheers,
Jon.

-------------------
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] const equivalent for mutable types?

[Chris Gorski]

Markus Mottl wrote:

> No, you'd need an abstract module for this to hide the concrete
> representation.  This is actually good SE-practice.
> 
> You can do this very conveniently using so-called phantom types.  For the
> special case of references, here is an example that implements ones,
> which can be made constant:

Everyone's responses were helpful, and this is exactly what I was 
looking for.  Thank you.

-- 
Chris Gorski - http://www.cgorski.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] Functional arrays

[skaller]

On Sun, 2004-08-01 at 03:23, Jon Harrop wrote:
> On Saturday 31 July 2004 17:35, skaller wrote:
> > On Sat, 2004-07-31 at 23:44, Jon Harrop wrote:
> > > Incidentally, does anyone have a functional array implementation (which
> > > doesn't suck ;-)?
> >
> > Map?
> 
> Well, by "array" I mean a container with O(1) random access where "n" is the 
> number of elements already in the container. ;-)

> Anyway, I'm considering implementing arrays which look functional but which 
> use built-in arrays and keep track of "derived" arrays (e.g. subarrays)

Ugg :)

How about a tree of buckets?

This limits copying on modification to one bucket.

When it gets big, you increase the bucket size so
the tree part doesn't grow too much, so you could
amortize the performance between O(1) and O(log n).

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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] Functional arrays

[brogoff]

On Sat, 1 Aug 2004, skaller wrote:
> On Sun, 2004-08-01 at 03:23, Jon Harrop wrote:
> > On Saturday 31 July 2004 17:35, skaller wrote:
> > > On Sat, 2004-07-31 at 23:44, Jon Harrop wrote:
> > > > Incidentally, does anyone have a functional array implementation (which
> > > > doesn't suck ;-)?
> > >
> > > Map?
> >
> > Well, by "array" I mean a container with O(1) random access where "n" is the
> > number of elements already in the container. ;-)
>
> > Anyway, I'm considering implementing arrays which look functional but which
> > use built-in arrays and keep track of "derived" arrays (e.g. subarrays)

One problem with even the simple minded solution of a type of array
without set is that it isn't a covariant container, like a list, and you can't
make it one, even though that should be allowed. That may not bug you, but it
was an annoyance for me when I discovered this. Jacques Garrigue said it was
probably too much work to fix that. Any functional array you build on top of
arrays gets bit by this.

-- Brian

-------------------
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] Functional arrays

[Diego Olivier Fernandez Pons]

    Bonjour,


> > > Incidentally, does anyone have a functional array implementation

As far as I know there are 3 main techniques to implement functional
arrays :

- version arrays
- maps with indexed access
- random acces lists


A version array is a classical array (O(1) acces) where persistance is
handled by 'indirection' and 'cache' : a pointer based mechanism
allows you to restore the complete history of the array by writing
back when needed this information in the main array.

classical examples :

- an array of stamped lists (confer to the ML version of Martin
Erwing's functional graph library)

- an array of trees (confer to the work of Melissa O'Neill where the
underlying trees are splay trees - she has written a Master Thesis, a
JFP paper and part of her doctoral dissetation on the subject)



The other two techniques handle persistency by copying and sharing (as
usual in functional programming).

- The map family is just a classical tree-like data structure
optimized for fast index location (the n-th element). Usually, the
balanced scheme used is Stephen Adam's weight-balanced trees because
memoizing in every node the size of the subtree allows a fast index
computation (see Baire, /set folder)

- The random acces list family is based on the isomorphism of binary
numbers and a list of increasing 2^k sized trees. There are many well
known data structures that can be seen as a particular case of this
scheme including binomial heaps (Vuillemin) and their amortized
variants (Okasaki-Brodal), and functional arrays (Okasaki)

You will find functional arrays code in
- Edison (Okasaki's Haskell data structure library)
- Markus Mottl port of Okasaki's book
- Baire

> Well, by "array" I mean a container with O(1) random access where
> "n" is the number of elements already in the container.

- version array O(1) access to the current array / up to O(n) for
previous versions
- maps O(log n) access to all arrays
- ral O(log n) access to all arrays


        Diego Olivier

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

Re: [Caml-list] Functional arrays

[Daniel Ortmann]

Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr> writes:

> - Markus Mottl port of Okasaki's book

Would you post a link to this work?  (I believe I had a copy and lost it.)

-- 
Daniel Ortmann, LSI Logic, 3425 40th Av NW, Suite 200, Rochester MN 55901
work: Daniel.Ortmann@lsil.com / 507.535.3861 / 63861 int / 8012.3861 gdds
home: dortmann@charter.net 507.288.7732, 2414 30Av NW #D, Rochester MN 55901
gpg/pgp public key: http://wwwkeys.us.pgp.net
jabber: daniel_ortmann@jabber.org / dortmann@jabber.co.lsil.com

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

Re: [Caml-list] Functional arrays

[Diego Olivier Fernandez Pons]

    Bonjour,

> > - Markus Mottl port of Okasaki's book
>
> Would you post a link to this work?  (I believe I had a copy and lost it.)
>

Google for Markus Mottl

then software -> caml -> purefun (chapter 9) and dscontrib


        Diego Olivier

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

Re: [Caml-list] Functional arrays

[Diego Olivier Fernandez Pons]

    Bonjour,

> > - Markus Mottl port of Okasaki's book
>
> Would you post a link to this work?  (I believe I had a copy and lost it.)

And here is the electronic version of Okasaki's thesis

http://www.cs.cmu.edu/afs/cs.cmu.edu/project/fox/mosaic/papers/cokasaki-thesis.ps


        Diego Olivier

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

Re: [Caml-list] Phantom types

[Jon Harrop]

On Saturday 31 July 2004 17:31, Markus Mottl wrote:
> module type PHANTOM_INT = sig
>   type 'p t
> ...

Right, I've had a bit more of a chance to play with phantom types now, and I'm 
quite confused. :-)

As far as I can tell, there were a few errors in Markus' original (I may well 
be wrong, of course), so here is my altered version:

module PhantomInt : sig
  type 'p t
	
  val add : 'p t -> 'p t -> 'p t
      
  val add_even_even : [ `Even ] t -> [ `Even ] t -> [ `Even ] t
  val add_even_odd : [ `Even ] t -> [ `Odd ] t -> [ `Odd ] t
  val add_odd_even : [ `Odd ] t -> [ `Even ] t -> [ `Odd ] t
  val add_odd_odd : [ `Odd ] t -> [ `Odd ] t -> [ `Even ] t
  val neg : 'a t -> 'a t
  val make_even : int -> [ `Even ] t
  val make_odd : int -> [ `Odd ] t
end = struct
  type 'p t = int
	
  let add = (+)
  let add_even_even = add
  let add_even_odd = add
  let add_odd_even = add
  let add_odd_odd = add
  let neg n = -n
  let make_even n = if n mod 2 = 0 then n else failwith "not even"
  let make_odd n = if n mod 2 <> 0 then n else failwith "not odd"
end;;

So I've changed the types to be [ `Even ] instead of [> `Even ] and the "make" 
functions to be "int -> ...". This appear to work as desired:

# let i = PhantomInt.make_even 2;;
val i : [ `Even ] PhantomInt.t = <abstr>
# let j = PhantomInt.make_odd 3;;
val j : [ `Odd ] PhantomInt.t = <abstr>
# PhantomInt.add_even_odd i j;;
- : [ `Odd ] PhantomInt.t = <abstr>
# PhantomInt.add_even_even i j;;
This expression has type [ `Odd ] PhantomInt.t but is here used with type
  [ `Even ] PhantomInt.t
These two variant types have no intersection

Now, there are some subtle peculiarities of these which I don't understand. 
Firstly, the type checking of the phantom types only seems to work if the 
type is made abstract in the module signature. I can't think why this should 
make a difference though. For example, changing "type 'p t" to "type 'p t = 
int" in "PhantomInt : sig" then allows:

# PhantomInt.add_even_even i j;;
- : [ `Even ] PhantomInt.t = 5

which is clearly undesirable.

Secondly, specifying the types as Markus did (e.g. [> `Even]), which I think 
should have been correct, leads to some kind of monomorphic type:

# PhantomInt.add_even_odd i j;;
- : _[> `Odd ] PhantomInt.t = <abstr>

Note the "_" preceding the "[> `Odd]". I'm not sure what the implications of 
this are.

Can someone explain these to me, please?

Cheers,
Jon.

PS: I'm using 3.08.0, in case that makes a difference.

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

[Caml-list] Why does ocaml use custom buffering?

[Daan Leijen]

I was wondering why the OCaml runtime implements its
own buffering on channel operations (in "byterun/io.c")
instead of using the standard "FILE*" operations in C?

Is there a particular reason (like performance), or is
it just an historic artifact?

All the best,
  Daan.

-------------------
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] Phantom types

[Jon Harrop]

On Monday 23 August 2004 10:49, Jon Harrop wrote:
> Secondly, specifying the types as Markus did (e.g. [> `Even])...

I should add, using:

  val add_even_even : [> `Even ] t -> [> `Even ] t -> [> `Even ] t
  val add_even_odd : [> `Even ] t -> [> `Odd ] t -> [> `Odd ] t

allows:

# PhantomInt.add_even_odd i j;;
val k : _[> `Odd ] PhantomInt.t = <abstr>

which can then be misused:

# PhantomInt.add_even_even i k;;
- : [ `Even ] PhantomInt.t = <abstr>

I think this is because [> `Even] means any superset of [ `Even ] whereas [< 
`Even], which was probably intended, means any subset of [ `Even ]. Indeed, 
the latter appears to work.

Cheers,
Jon.

-------------------
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] Phantom types

[brogoff]

On Mon, 23 Aug 2004, Jon Harrop wrote:

> On Saturday 31 July 2004 17:31, Markus Mottl wrote:
> > module type PHANTOM_INT = sig
> >   type 'p t
> > ...
>
> Right, I've had a bit more of a chance to play with phantom types now, and I'm
> quite confused. :-)
>
> As far as I can tell, there were a few errors in Markus' original (I may well
> be wrong, of course), so here is my altered version:

[...snip...]

Yes, those look like errors, and your fixes look good.

> So I've changed the types to be [ `Even ] instead of [> `Even ] and the "make"
> functions to be "int -> ...". This appear to work as desired:

that's what you want in this example.

> Now, there are some subtle peculiarities of these which I don't understand.
> Firstly, the type checking of the phantom types only seems to work if the
> type is made abstract in the module signature. I can't think why this should
> make a difference though. For example, changing "type 'p t" to "type 'p t =
> int" in "PhantomInt : sig" then allows:
>
> # PhantomInt.add_even_even i j;;
> - : [ `Even ] PhantomInt.t = 5
>
> which is clearly undesirable.

This looks like a bug in the OCaml type checker. It also occurs if you replace
the polymorphic variants with type even = Even and odd = Odd. It remains if
you replace the phantom type int by int64 or even int array, but goes away when
you replace the phantom type by  type 'p t = { data = int } or
type 'p t = Int int. So the built in types appear to be being treated
differently.

> Secondly, specifying the types as Markus did (e.g. [> `Even]), which I think
> should have been correct, leads to some kind of monomorphic type:
>
> # PhantomInt.add_even_odd i j;;
> - : _[> `Odd ] PhantomInt.t = <abstr>

A [> or [< means there's an implicit type variable.

-- Brian

-------------------
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] Phantom types

[Jacques GARRIGUE]

From: Jon Harrop <jon@jdh30.plus.com>

> I should add, using:
> 
>   val add_even_even : [> `Even ] t -> [> `Even ] t -> [> `Even ] t
>   val add_even_odd : [> `Even ] t -> [> `Odd ] t -> [> `Odd ] t
> 
> allows:
> 
> # PhantomInt.add_even_odd i j;;
> val k : _[> `Odd ] PhantomInt.t = <abstr>

This part is OK.

> which can then be misused:
> 
> # PhantomInt.add_even_even i k;;
> - : [ `Even ] PhantomInt.t = <abstr>

But this one is wrong.

> I think this is because [> `Even] means any superset of [ `Even ] whereas [< 
> `Even], which was probably intended, means any subset of [ `Even ]. Indeed, 
> the latter appears to work.

Indeed, one must be careful about variance.
So the right signature would be:
   type +'a t
   type any = [`Even|`Odd]
   val add_even_even : [ `Even ] t -> [ `Even ] t -> [> `Even ] t
   val add_even_odd : [ `Even ] t -> [ `Odd ] t -> [> `Odd ] t
   val add_unknown_unknown : any t -> any t -> any t
(Note the + indicating covariance)

Then you have
# let k = PhantomInt.add_even_odd i j;;
val k : [> `Odd ] PhantomInt.t = <abstr>
(polymorphic result!)
# PhantomInt.add_even_even i k;;
** type error
# PhantomInt.add_unknown_unknown i k;;
- : any t = <abstr>

Jacques Garrigue

-------------------
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] Phantom types

[Goswin von Brederlow]

Thomas Braibant <thomas.braibant@gmail.com> writes:

> Hi list,
>
> Following on the thread "Subtyping structurally-equivalent records, or
> something like it?", I made some experimentations with phantom types.
> Unfortunately, I turns out that I do not understand the results I got.
>
> Could someone on the list explain why the first piece of code is well
> typed, while the second one is not ?
>
>
> type p1
> type p2
>
> type 'a t = float
> let x : p1 t = 0.0
> let id : p2 t -> p2 t = fun x -> x
> let _ = id x (* type checks with type p2 t*)

This is actualy a problem, at least for me. Because that is a type error
you usualy want to specifically catch through the use of phantom types.
But ocaml knows that 'a t = float and all floats are compatible. So it
accepts all 'a t as the same.

To make the phantom type checking work for you you need to move the
definition of your phantom type into a submodule and make the type
abstract through its signature. Any functions converting from one 'a t
to 'b t also need to be in there. To avoid having to use the submodule
name all the time you can use something like

module M : sig type 'a t = private float val make : float -> 'a t end = struct
  type 'a t = float
  let make f = f
end
include M

# let x : p1 t = make 0.0;;
val x : p1 t = 0.
# let id : p2 t -> p2 t = fun x -> x;;
val id : p2 t -> p2 t = <fun>
# let _ = id x;;
Error: This expression has type p1 t = p1 M.t
       but an expression was expected of type p2 t = p2 M.t

The "private" tells the type system that nobody (outside the module) is
to create a value of that type. Only inside the module, where the type
isn't private can you create one.

> type 'a t = {l: float}
> let x : p1 t = {l = 0.0}
> let id : p2 t -> p2 t = fun x -> x
> let _ = id x (* ill typed *)

Why it works correctly here is explained nicely in the other mailss in
this thread.

> Any thoughts ?
>
> thomas

MfG
        Goswin