Pervasives.compare output type

Pervasives.compare output type

[Alex Baretta]

Pervasives.compare currently returns an int. Intuitively it would be 
more appropriate for it to return a union type such as the following.

type comparison_result = Less | Equals | Greater

What are the reasons behind the present design choice?

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Pervasives.compare output type

[Richard Jones]

On Thu, Mar 24, 2005 at 07:47:23PM +0100, Alex Baretta wrote:
> Pervasives.compare currently returns an int. Intuitively it would be 
> more appropriate for it to return a union type such as the following.
> 
> type comparison_result = Less | Equals | Greater
> 
> What are the reasons behind the present design choice?

Wouldn't it be for speed?  You could define Pervasives.compare over
integers just as a subtraction.  For strings, you can write a loop
which looks character-by-character over the strings, subtracting one
character from another, and if the result is non-zero, return that
result directly (else keep iterating).

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] Pervasives.compare output type

[Marcin 'Qrczak' Kowalczyk]

Richard Jones <rich@annexia.org> writes:

>> type comparison_result = Less | Equals | Greater
>> 
>> What are the reasons behind the present design choice?
>
> Wouldn't it be for speed?  You could define Pervasives.compare over
> integers just as a subtraction.

You can't, because of overflow.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: Pervasives.compare output type

[Bardur Arantsson]

Marcin 'Qrczak' Kowalczyk wrote:
> Richard Jones <rich@annexia.org> writes:
> 
> 
>>>type comparison_result = Less | Equals | Greater
>>>
>>>What are the reasons behind the present design choice?
>>
>>Wouldn't it be for speed?  You could define Pervasives.compare over
>>integers just as a subtraction.
> 
> 
> You can't, because of overflow.
> 

Actually, since integers in OCaml are limited to (n-1) bits where n=32
or n=64 depending on architecture, overflow shouldn't be a problem. (The
comments in byterun/compare.c also seem to agree with that.)

Even so, it would be very slow to the polymorphic compare to compare
integers, so if one cares about efficiency, direct subtraction is
preferable.

-- 
Bardur Arantsson
<bardur@imada.sdu.dk>
<bardur@scientician.net>

"Mr. T to pity fool."
                                          http://www.theonion.com

Re: [Caml-list] Re: Pervasives.compare output type

[Jason Hickey]

Bardur Arantsson wrote:
> Actually, since integers in OCaml are limited to (n-1) bits where n=32
> or n=64 depending on architecture, overflow shouldn't be a problem. (The
> comments in byterun/compare.c also seem to agree with that.)
> 
> Even so, it would be very slow to the polymorphic compare to compare
> integers, so if one cares about efficiency, direct subtraction is
> preferable.
> 

This discussion just came up on the MetaPRL list.  Here is an excerpt.

---

By the way, I tried using subtraction for a comparison, and it failed 
miserably:(

...

It is easy to explain--transitivity breaks.  For example, using 
subtraction, the following two relations hold: (min_int < 0) and (0 < 
1); however (min_int > 1).  Oops...

Aleksey Nogin wrote some micro-benchmarks.  These are 
back-of-the-envelope, so don't take them as definitive.
> I wrote the following test:
> 
> ------------
> 
> open Printf
> open Unix
> 
> let f1  x       y = Pervasives.compare x y
> let f2 (x: int) y = Pervasives.compare x y
> let f3  x       y = if x=y then Pervasives.compare "s1" "s2" else if x < y then -1 else 1
> let f4 (x: int) y = if x=y then Pervasives.compare "s1" "s2" else if x < y then -1 else 1
> let f5  x       y = let i = Pervasives.compare x y in if i = 0 then Pervasives.compare "s1" "s2" else i
> let f6 (x: int) y = let i = Pervasives.compare x y in if i = 0 then Pervasives.compare "s1" "s2" else i
> let f7  x       y = match Pervasives.compare x y with 0 -> Pervasives.compare "s1" "s2" | i -> i
> let f8 (x: int) y = match Pervasives.compare x y with 0 -> Pervasives.compare "s1" "s2" | i -> i
> 
> let time name f =
>    let t1=Unix.times () in
>       for i = 10 to 30000000 do ignore(f i 20) done;
>       let t2=Unix.times () in
>          eprintf "Function %s: user time: %f; system time: %f\n%!" name (t2.tms_utime -. t1.tms_utime) (t2.tms_stime -. t1.tms_s
> time)
> 
> let time_all () =
>    time "f1" f1;
>    time "f2" f2;
>    time "f3" f3;
>    time "f4" f4;
>    time "f5" f5;
>    time "f6" f6;
>    time "f7" f7;
>    time "f8" f8
> 
> let () =
>    time_all ();
>    time_all ();
>    time_all ()
> 
> -----------------
> 
> and here are rhe approximate running times:
> 
> Function f1: user time: 1.060000; system time: 0.000000
> Function f2: user time: 0.520000; system time: 0.000000
> Function f3: user time: 2.970000; system time: 0.000000
> Function f4: user time: 0.340000; system time: 0.000000
> Function f5: user time: 1.110000; system time: 0.000000
> Function f6: user time: 0.570000; system time: 0.000000
> Function f7: user time: 1.110000; system time: 0.000000
> Function f8: user time: 0.550000; system time: 0.000000
> 
> -- 
> Aleksey Nogin 

Jason

-- 
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257

Re: [Caml-list] Re: Pervasives.compare output type

[brogoff]

http://caml.inria.fr/pub/ml-archives/caml-list/2001/04/df5452c7bbfbd8342c2bc830b7e2bd4d.en.html


-- 
-- Brian

Re: [Caml-list] Re: Pervasives.compare output type

[Alex Baretta]

Jason Hickey wrote:

>>
>> let f1  x       y = Pervasives.compare x y
>> let f2 (x: int) y = Pervasives.compare x y
>> let f3  x       y = if x=y then Pervasives.compare "s1" "s2" else if x 
>> < y then -1 else 1
>> let f4 (x: int) y = if x=y then Pervasives.compare "s1" "s2" else if x 
>> < y then -1 else 1
>> let f5  x       y = let i = Pervasives.compare x y in if i = 0 then 
>> Pervasives.compare "s1" "s2" else i
>> let f6 (x: int) y = let i = Pervasives.compare x y in if i = 0 then 
>> Pervasives.compare "s1" "s2" else i
>> let f7  x       y = match Pervasives.compare x y with 0 -> 
>> Pervasives.compare "s1" "s2" | i -> i
>> let f8 (x: int) y = match Pervasives.compare x y with 0 -> 
>> Pervasives.compare "s1" "s2" | i -> i
>>
>> let time name f =
>>   

I am unsure as to how to interpret these benchmarks...

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Re: Pervasives.compare output type

[Aleksey Nogin]

On 25.03.2005 01:42, Alex Baretta wrote:

>>> let f1  x       y = Pervasives.compare x y
>>> let f2 (x: int) y = Pervasives.compare x y
>>> let f3  x       y = if x=y then Pervasives.compare "s1" "s2" else if 
>>> x < y then -1 else 1
>>> let f4 (x: int) y = if x=y then Pervasives.compare "s1" "s2" else if 
>>> x < y then -1 else 1
>>> let f5  x       y = let i = Pervasives.compare x y in if i = 0 then 
>>> Pervasives.compare "s1" "s2" else i
>>> let f6 (x: int) y = let i = Pervasives.compare x y in if i = 0 then 
>>> Pervasives.compare "s1" "s2" else i
>>> let f7  x       y = match Pervasives.compare x y with 0 -> 
>>> Pervasives.compare "s1" "s2" | i -> i
>>> let f8 (x: int) y = match Pervasives.compare x y with 0 -> 
>>> Pervasives.compare "s1" "s2" | i -> i
>>>
>>> let time name f =
>>>   
> 
> 
> I am unsure as to how to interpret these benchmarks...

Yes, these were taken a bit out of context. Basically, the question we 
were discussing was:
> What's the fastest way to compare int*string pairs (or, in general - int*'a), where ints are likely to be distinct whenever the second elements are distinct (basically, the int is a hash)?


The answer is that the "f4" above is the fastest one:

let compair_pair ((i1:int), a1) (i2, a2) =
    if i1 = i2 then
       Pervasives.compare a1 a2
    else if i1 < i2 then
       -1
    else
       1

-- 
Aleksey Nogin

Home Page: http://nogin.org/
E-Mail: nogin@cs.caltech.edu (office), aleksey@nogin.org (personal)
Office: Moore 04, tel: (626) 395-2200

Re: [Caml-list] Re: Pervasives.compare output type

[Marcin 'Qrczak' Kowalczyk]

Bardur Arantsson <spam@scientician.net> writes:

>>>Wouldn't it be for speed?  You could define Pervasives.compare over
>>>integers just as a subtraction.
>> 
>> You can't, because of overflow.
>
> Actually, since integers in OCaml are limited to (n-1) bits where n=32
> or n=64 depending on architecture, overflow shouldn't be a problem.

compare must eventually return an OCaml int. It can use subtraction
only in its internal recursion, but when presenting the result to
OCaml code it can't just pass the result of subtraction.

It can use subtraction internally no matter whether the OCaml
interface uses intergers whose sign only matters, or an enumeration.

And thus there seems to be no performance advantage in using ints
instead of the enumeration.

In practice it returns -1,0,1 anyway:
# compare 10 20;;
- : int = -1

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: Pervasives.compare output type

[Bardur Arantsson]

Marcin 'Qrczak' Kowalczyk wrote:
> Bardur Arantsson <spam@scientician.net> writes:
> 
> 
>>>>Wouldn't it be for speed?  You could define Pervasives.compare over
>>>>integers just as a subtraction.
>>>
>>>You can't, because of overflow.
>>
>>Actually, since integers in OCaml are limited to (n-1) bits where n=32
>>or n=64 depending on architecture, overflow shouldn't be a problem.
> 
> 
> compare must eventually return an OCaml int. It can use subtraction
> only in its internal recursion, but when presenting the result to
> OCaml code it can't just pass the result of subtraction.
> 
> It can use subtraction internally no matter whether the OCaml
> interface uses intergers whose sign only matters, or an enumeration.
> 
> And thus there seems to be no performance advantage in using ints
> instead of the enumeration.
> 
> In practice it returns -1,0,1 anyway:
> # compare 10 20;;
> - : int = -1
> 

Indeed, I mistook compare_val for caml_compare.

Still if you can make sufficient guarantees about the ranges of the
integers being compared, you *can* use '-' which *should* be faster than
branching according to conventional wisdom.

The more 'relaxed' requirement that comparison functions can return
anything<0, 0 or anything>0 just means that any higher-order functions
which take comparison functions as arguments *might* run slightly
faster... whether this is true in practise is another matter entirely.

Cheers,

-- 
Bardur Arantsson
<bardur@imada.sdu.dk>
<bardur@scientician.net>

It's not often you see something that's both romantic *and*
thrifty.
                                               Dawn, 'The Office'

Re: [Caml-list] Re: Pervasives.compare output type

[Alex Baretta]

Marcin 'Qrczak' Kowalczyk wrote:
> Bardur Arantsson <spam@scientician.net> writes:
> And thus there seems to be no performance advantage in using ints
> instead of the enumeration.
> 
> In practice it returns -1,0,1 anyway:
> # compare 10 20;;
> - : int = -1
> 

This is the point I was trying to make.

Alex

-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Pervasives.compare output type

[Oliver Bandel]

On Thu, Mar 24, 2005 at 07:47:23PM +0100, Alex Baretta wrote:
> Pervasives.compare currently returns an int. Intuitively it would be 
> more appropriate for it to return a union type such as the following.
> 
> type comparison_result = Less | Equals | Greater
> 
> What are the reasons behind the present design choice?

Maybe it was a historical reason?

Didn't comparison functions (in C and many other languages too)
throw out an integer value?!

Having -1 for smaller (less(er?)) and +1 for bigger (greater)
and 0 for equal makes sense at least for integers.

let sgn a = match a with
    _ when a > 0 -> 1
  | _ when a < 0 -> -1
  | _ -> 0


let compare int_1 int_2 = sgn(int_1 - int_2)

As compare normally is a computation that is used to compare
integers, but can be more generalized to comparing strings
and so on, and maybe because comparing (integers) is derived
from the area of mathematics, this historic offset may be
the reason for that return value.
E.g. comparing strings can be (seems to be) implemented as
comparing the integer-values of the characters (index)
in the ASCII charset.
So, again: that's mathematics of comparing integers.


So all in all, there may be these reasons here:

- derived from mathematics on integers (and easy implementation to
   use the sub of two integers for getting the result, which one
   is greater than the other one, then using the sign of that subtraction)

- resulting value is like in other programming languages an integer value


Nevertheless it could be done with an output type like you gave above.

But you can wrap it, if you want:

type comparison_result = Less | Equals | Greater
let compare_symbres a b = match (compare a b) with
    |  1 -> Greater
    | -1 -> Less
    |  _ -> Equals

Ciao,
   Oliver

Re: [Caml-list] Pervasives.compare output type

[Xavier Leroy]

> Pervasives.compare currently returns an int. Intuitively it would be 
> more appropriate for it to return a union type such as the following.
> type comparison_result = Less | Equals | Greater
> What are the reasons behind the present design choice?

It's a historical error.  If I were to do it again, I'd use a sum type
such as your "comparison_result".  The current solution allows to use
(-) (integer subtraction) as the comparison predicate for *small*
integer arguments, but this doesn't work as a general integer
comparison because of subtraction wrapping around for large arguments.
So, there are really no benefits to encode the result of a 3-way
comparison as an "int".

- Xavier Leroy

Re: [Caml-list] Pervasives.compare output type

[Alex Baretta]

Xavier Leroy wrote:
> It's a historical error.  If I were to do it again, I'd use a sum type
> such as your "comparison_result".  The current solution allows to use
> (-) (integer subtraction) as the comparison predicate for *small*
> integer arguments, but this doesn't work as a general integer
> comparison because of subtraction wrapping around for large arguments.
> So, there are really no benefits to encode the result of a 3-way
> comparison as an "int".
> 
> - Xavier Leroy

Whether fixing such historical errors engenders more benefits than 
trouble is a very interesting philosophical question.

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Pervasives.compare output type

[Jacques Carette]

Alex Baretta <alex@barettadeit.com> wrote:
> Xavier Leroy wrote:
> > It's a historical error.  [...]
> 
> Whether fixing such historical errors engenders more benefits than trouble is a very interesting philosophical 
> question.

There are some conclusions on the topic of 'historical errors' that seem to hold:

- a software system is 'mature' if 'historical errors' cannot be fixed because of the overwhelming weight of backwards 
compatibility [ie progress is definitely hampered by inertia].
- this inertia is not nearly as bad as a lot of people fear (people go upgrade their OSes, compilers, etc even though 
this is sometimes a fair bit of work).  K&R C code bases did get migrated to ANSI C.

It all depends on whether the installed base is viewed as more/less important as the future integrity of the software 
system as a whole.  When I was in industry, I was in a position where I made the choice that future integrity was more 
important [and I did annoy the user base but improved the basic system a lot], and my successors made the opposite 
choice [which means that mostly do 'new' features and can't fix some well-known bugs that users have learned to work 
around].  
  
Jacques

Re: [Caml-list] Pervasives.compare output type

[Alex Baretta]

Jacques Carette wrote:
> Alex Baretta <alex@barettadeit.com> wrote:
> 
>> Xavier Leroy wrote:
>> > It's a historical error.  [...]
>>
>> Whether fixing such historical errors engenders more benefits than 
>> trouble is a very interesting philosophical question.

> It all depends on whether the installed base is viewed as more/less 
> important as the future integrity of the software system as a whole.  
> When I was in industry, I was in a position where I made the choice that 
> future integrity was more important...

On purely theoretical grounds, I agree with you that working around 
"historical errors" is generally worse than updating the existing code 
base. I wonder if Xavier agrees. I also wonder if there are "border 
constraints" beyond his personal taste on this matter.

Alex

-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Pervasives.compare output type

[brogoff]

On Wed, 30 Mar 2005, Jacques Carette wrote:

> Alex Baretta <alex@barettadeit.com> wrote:
> > Xavier Leroy wrote:
> > > It's a historical error.  [...]
> >
> > Whether fixing such historical errors engenders more benefits than trouble is a very interesting philosophical
> > question.
>
[...snip...]
> It all depends on whether the installed base is viewed as more/less important
> as the future integrity of the software system as a whole.  When I was in
> industry, I was in a position where I made the choice that future integrity
> was more important [and I did annoy the user base but improved the basic
> system a lot], and my successors made the opposite choice [which means that
> mostly do 'new' features and can't fix some well-known bugs that users have
> learned to work around].

Speaking as an industrial user, I don't see it as such an either/or. I'd
prefer that enhancements (thisisn't a bug) which require rewriting code
be done as few times as possible, so that each release doesn't require
rewriting code. So, let's say for example that the implementors decide to
change this, and to fix evaluation order to be left to right, I'd prefer
that it were done in one release, rather than two separate ones.

I think even industrial users should realize that OCaml is a research langauge,
and while we're grateful that it is generally quite stable from relase to
release, that research goals take some precedence. Maybe one day the
implementors will decide to "radically" change things, as in the move from
Caml Light to Caml Special Light/OCaml.

-- Brian

Re: [Caml-list] Pervasives.compare output type

[Jacques Carette]

brogoff <brogoff@speakeasy.net> wrote:
> Speaking as an industrial user, I don't see it as such an either/or. I'd
> prefer that enhancements (thisisn't a bug) which require rewriting code
> be done as few times as possible, so that each release doesn't require
> rewriting code. So, let's say for example that the implementors decide to
> change this, and to fix evaluation order to be left to right, I'd prefer
> that it were done in one release, rather than two separate ones.

If I were still in a position to decide such things, that is indeed what I would do:  assuming yearly releases, then 
every third release would be a 'big' one where large changes would be introduced together, and with a couple of 
releases in between that were as backwards compatible as possible.

> I think even industrial users should realize that OCaml is a research langauge,
> and while we're grateful that it is generally quite stable from relase to
> release, that research goals take some precedence. Maybe one day the
> implementors will decide to "radically" change things, as in the move from
> Caml Light to Caml Special Light/OCaml.

My experience (~15 years with the one piece of software, with access to its full history) with software that is now 25 
years old is that 'major' changes should be planned every 3 years, and 'radical' changes every 6-7 years.  That should 
be sufficient to keep the softare healthy and progressing.  I have seen the effect of periods of 6-9 years of relative 
sclerosis (ie basically only new features), and the result was a lot of bloat with questionable new features and much 
less progress on the 'core'.

Of course, the core of OCaml is much more solid than what I was working on.  It is based on very solid theory, which 
also helps a lot.

But theory is also advancing rapidly.  Haskell 6.4's inclusion of GADTs in the core language is exerting a powerful 
pull on me.  On another front, System E looks like a promising 'replacement' for System F based polymorphism - that 
might be a 'radical' change ;-).  But right now metaocaml is keeping me programming in ocaml...

Jacques

Re: [Caml-list] Pervasives.compare output type

[brogoff]

On Wed, 30 Mar 2005, Jacques Carette wrote:
> But theory is also advancing rapidly.  Haskell 6.4's inclusion of GADTs in
> the core language is exerting a powerful pull on me.

I know exactly what you mean :-).

I'm sure you're aware that people at INRIA are working on GADT's as well.
I have to say, the idea is intriguing, I first read about them from Ralf Hinze's
"Fun With Phantom Types"  where he suggests using them to do away with type
classes in Haskell. One problem with all of these "sexy types" is that as you
cram all of this into a language, it gets very complex if you don't throw
something else out. What should get thrown out of OCaml if GADTs get in? :-/


> On another front, System E looks like a promising 'replacement' for System F
> based polymorphism - that might be a 'radical' change ;-).  But right now metaocaml is keeping me
> programming in ocaml...

When it's integrated into the mainstream release, including the
native code compiler (only bytecode last time I looked) I'll look again.

-- Brian

Re: [Caml-list] Pervasives.compare output type

[Jon Harrop]

On Wednesday 30 March 2005 19:49, brogoff wrote:
> On Wed, 30 Mar 2005, Jacques Carette wrote:
> > But theory is also advancing rapidly.  Haskell 6.4's inclusion of GADTs
> > in the core language is exerting a powerful pull on me.
>
> I'm sure you're aware that people at INRIA are working on GADT's as well.
> I have to say, the idea is intriguing...

Would someone be so kind as to enlighten me (and probably a few other people!) 
as to what these intruiging GADT things are and what they're good for? :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Pervasives.compare output type

[Jacques Carette]

Jon Harrop <jon@ffconsultancy.com> wrote:
> Would someone be so kind as to enlighten me (and probably a few other people!) 
> as to what these intruiging GADT things are and what they're good for? :-)

They are a (conservative) extension to Algebraic Data Types (and G=Guarded or Generalized, depending on the author). 
 The basic idea is that instead of giving names to the various constructors in a Sum type, you give explicit functions 
which become the constructors.  Furthermore, you then make type inference context-dependent: the type of each 
constructor is inferred independently, and can have different 'guards'.  

Or at least that's my quick-and-dirty impression, which definitely contains technical inaccuracies, but is roughly 
right.  To get a good introduction, why not turn to 
http://pauillac.inria.fr/~fpottier/slides/slides-msr-11-2004.pdf
for a pleasant and informative read.  The slides give references as well as example applications.

For more information:
http://research.microsoft.com/Users/simonpj/papers/gadt/gadt.ps.gz
http://citeseer.ist.psu.edu/669510.html (and several more at http://cristal.inria.fr/~simonet/publis/)
http://www.cs.bu.edu/~hwxi/academic/drafts/ATS.pdf   [tougher read...]

For interesting but serious discussions:
http://lambda-the-ultimate.org/node/view/552
http://lambda-the-ultimate.org/node/view/116
http://lambda-the-ultimate.org/node/view/290

The most convincing example I have seen is that an eval function for a statically-typed language
let rec eval e = 
   match e with 
     | Lit n -> n
     | Plus(a,b) -> (eval a) + (eval b)
     | True -> true
     | False -> false
     | And(a,b) -> (eval a) && (eval b)
     | If(t,c,a) -> if eval t then eval c else eval a
     | IfZero e' -> (eval e') = 0
is currently rejected in ML languages, but with GADTs the above can be accepted, as it can't "go wrong".

Jacques

Re: [Caml-list] Pervasives.compare output type

[Christopher Dutchyn]

On Wed, 30 Mar 2005, Jacques Carette wrote:

> The most convincing example I have seen is that an eval function for a 
> statically-typed language
> let rec eval e =   match e with     | Lit n -> n
>    | Plus(a,b) -> (eval a) + (eval b)
>    | True -> true
>    | False -> false
>    | And(a,b) -> (eval a) && (eval b)
>    | If(t,c,a) -> if eval t then eval c else eval a
>    | IfZero e' -> (eval e') = 0
> is currently rejected in ML languages, but with GADTs the above can be 
> accepted, as it can't "go wrong".

I've played a little with GADTs in GHC 6.4.  What strikes me as most 
valuable about this example (besides its conciseness) it that it leverages 
the type-inferencer/checker in the metalanguage (Haskell) into a 
type-inferencer/checker for the object language.  I'm trying to make it do 
subtyping by passing lists of types (simulated by pairs).

  --
Christopher Dutchyn
UBC Computer Science


>
> Jacques
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Pervasives.compare output type

[brogoff]

Jon (and others),
   In addition to the sources Jacques provided, let me point you to

   http://www.informatik.uni-bonn.de/~ralf/publications/With.pdf

for a very readable description that doesn't rely on heavy type theory to get
the idea across.

I wonder, if you really want to use this approach for genericity on, say
numeric types, if you need something like Haskell's newtype (and a guarantee
that the constructor get optimized away) to make it useful?

-- Brian

On Wed, 30 Mar 2005, Jacques Carette wrote:

> Jon Harrop <jon@ffconsultancy.com> wrote:
> > Would someone be so kind as to enlighten me (and probably a few other people!)
> > as to what these intruiging GADT things are and what they're good for? :-)
>
> They are a (conservative) extension to Algebraic Data Types (and G=Guarded or Generalized, depending on the author).
>  The basic idea is that instead of giving names to the various constructors in a Sum type, you give explicit functions
> which become the constructors.  Furthermore, you then make type inference context-dependent: the type of each
> constructor is inferred independently, and can have different 'guards'.
>
> Or at least that's my quick-and-dirty impression, which definitely contains technical inaccuracies, but is roughly
> right.  To get a good introduction, why not turn to
> http://pauillac.inria.fr/~fpottier/slides/slides-msr-11-2004.pdf
> for a pleasant and informative read.  The slides give references as well as example applications.
>
> For more information:
> http://research.microsoft.com/Users/simonpj/papers/gadt/gadt.ps.gz
> http://citeseer.ist.psu.edu/669510.html (and several more at http://cristal.inria.fr/~simonet/publis/)
> http://www.cs.bu.edu/~hwxi/academic/drafts/ATS.pdf   [tougher read...]
>
> For interesting but serious discussions:
> http://lambda-the-ultimate.org/node/view/552
> http://lambda-the-ultimate.org/node/view/116
> http://lambda-the-ultimate.org/node/view/290
>
> The most convincing example I have seen is that an eval function for a statically-typed language
> let rec eval e =
>    match e with
>      | Lit n -> n
>      | Plus(a,b) -> (eval a) + (eval b)
>      | True -> true
>      | False -> false
>      | And(a,b) -> (eval a) && (eval b)
>      | If(t,c,a) -> if eval t then eval c else eval a
>      | IfZero e' -> (eval e') = 0
> is currently rejected in ML languages, but with GADTs the above can be accepted, as it can't "go wrong".
>
> Jacques
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

GADT?? (Re: [Caml-list] Pervasives.compare output type)

[Oliver Bandel]

On Wed, Mar 30, 2005 at 10:49:42AM -0800, brogoff wrote:
> On Wed, 30 Mar 2005, Jacques Carette wrote:
> > But theory is also advancing rapidly.  Haskell 6.4's inclusion of GADTs in
> > the core language is exerting a powerful pull on me.
> 
> I know exactly what you mean :-).
> 
> I'm sure you're aware that people at INRIA are working on GADT's as well.
> I have to say, the idea is intriguing, I first read about them from Ralf Hinze's
> "Fun With Phantom Types"  where he suggests using them to do away with type
> classes in Haskell. One problem with all of these "sexy types" is that as you
> cram all of this into a language, it gets very complex if you don't throw
> something else out. What should get thrown out of OCaml if GADTs get in? :-/
[...]


What is/what are GADT?!

Ciao,
   Oliver

Re: [Caml-list] Pervasives.compare output type

[Oliver Bandel]

On Wed, Mar 30, 2005 at 04:45:27PM +0200, Alex Baretta wrote:
> Xavier Leroy wrote:
> >It's a historical error.  If I were to do it again, I'd use a sum type
> >such as your "comparison_result".  The current solution allows to use
> >(-) (integer subtraction) as the comparison predicate for *small*
> >integer arguments, but this doesn't work as a general integer
> >comparison because of subtraction wrapping around for large arguments.
> >So, there are really no benefits to encode the result of a 3-way
> >comparison as an "int".
> >
> >- Xavier Leroy
> 
> Whether fixing such historical errors engenders more benefits than 
> trouble is a very interesting philosophical question.


Well, there are implementations of modules with and without
named parameters, why not providing different implementations
for compare?

Or maybe additionnally to "compare" provide a function
"comparison" or "comp" or something like that?

Is it sooooooo necessary to have only this one "compare"
function? Is it too much overhead in the interface to
add a function that uses sum-types?


Maybe commenting "compare" with an attribute like "do not use
in future developments" or so?!

Ciao,
    Oliver