Re: entiers et reels

Re: entiers et reels

[quercia]

En attendant la reponse de l'INRIA, voici une petite recreation
sur une addition polymorphe de mon cru : Le principe est par un
bidouillage en C de tester le type des arguments d'une somme puis
d'effectuer l'operation adequate.

While waiting for an answer from INRIA, here's a recreation on
a ploymorphic addition : With some C hacking, one can test the
type of the arguments of a sum and call the appropriate routine.

--------------------- Fichier addition.c ------------------------------------

#include "misc.h"
#include "mlvalues.h"
#include "alloc.h"

value addition(value a, value b)
{
#define cas(x) (Is_long(x) ? 0 : (Tag_val(x) == Double_tag ? 1 : 2))

  switch (cas(a) + 3*cas(b)) {
  case 0 : return(a+b-1);
  case 1 : return(copy_double( Double_val(a) + (double) (b >> 1) ));
  case 3 : return(copy_double( (double) (a >> 1) + Double_val(b) ));
  case 4 : return(copy_double( Double_val(a) + Double_val(b) ));
  default: invalid_argument("+");
  }
}

----------------------- Fichier addition.mli ---------------------------------

value prefix + : 'a -> 'b -> 'c = 2 "addition";;

----------------------- Fichier addition.ml ---------------------------------

(* rien *) (* empty file *)

----------------------- Commandes de compilation ----------------------------

#!/bin/sh

camlc -custom -c addition.mli addition.c addition.ml
camlmktop -custom -o camladdition addition.o addition.zo

--------------------- Essai au terminal -------------------------------------
---------------------------- Demo -------------------------------------------

bash$ camllight camladdition
>       Caml Light version 0.7

##open "addition";;
#(* Sommes homogenes *)
 print_int(1 + 2);; print_float(1.2 + 3.4);;
3- : unit = ()
#4.6- : unit = ()
#(* Sommes heterogenes *)
 print_float(1 + 2.3);; print_float(1.2 + 3);;
3.3- : unit = ()
#4.2- : unit = ()
#(* Somme invalide *)
 print_float(1 + true);;
Uncaught exception: Invalid_argument "+"
#(* Pb : Caml n'est plus capable de typer le resultat d'une somme *)
 2 + 3;;
- : '_a = <poly>
#(* mais on peut l'aider *)
 (2 + 3 : int);; (4.5 + 6.7 : float);;
- : int = 5
#- : float = 11.2
#(* peut-on mentir ? *)
 (2 + 3 : float);; (4.5 + 6.7 : int);;
Segmentation fault
bash$ camllight camladdition
>       Caml Light version 0.7

##open "addition";;
#(* plus subtil *)
 let liste = [1 + 2; 3.14 + 4.57];;
liste : '_a list = [<poly>; <poly>]
#print_int(hd liste);;
3- : unit = ()
#print_float(hd(tl liste));;
Toplevel input:
>print_float(hd(tl liste));;
>            ^^^^^^^^^^^^
This expression has type int,
but is used with type float.
#let liste = [1 + 2; 3.14 + 4.57];;
liste : '_a list = [<poly>; <poly>]
#print_float(hd(tl liste));;
7.71- : unit = ()
#print_int(hd liste);;
Toplevel input:
>print_int(hd liste);;
>          ^^^^^^^^
This expression has type float,
but is used with type int.
#(* un essai idiot *)
 let f x = x+1;;
f : 'a -> 'b = <fun>
#(f 1 :int);;
- : int = 2
#f 1 2;;
Segmentation fault
bash$
-----------------------------------------------------------------------------
Michel Quercia
Lycee Carnot
16 bd Thiers
21000 Dijon
France

Re: entiers et reels

[Xavier Leroy]

> Maybe I'm too dense or I have been exposed to too much Fortran, but I
> don't fully understand:
> Standard ML has [overloaded arithmetic operators]
> (at least in the New Jersey incarnation), so why
> can't Caml?

Caml could very well have it. Indeed, the old Caml V3.1 implementation
has support for overloaded operators that far exceeds what NJML provides.

> As long as all operands are of the same type, the
> semantics should be obvious.

The semantics are obvious once types are assigned to all
subexpressions of the program. But that's where the problem lies in
a language with type inference. Consider:

        let f x y = x + y

Assuming + works on ints and floats, f has two possible types, namely
int -> int -> int and float -> float -> float. These are the only two
types. In particular, their least upper bound 'a -> 'a -> 'a is not
a valid type for f (unless + is implemented with run-time type tests,
as in Michel Quercia's post, but this defeats the whole purpose of
static typing -- just go back to Scheme, then).

So, the type inferencer fails on the definition above ("cannot resolve
overloading"), and the programmer must add a type constraint:

        let f (x:float) y = x + y

Frankly, if I must explain the compiler what I mean, I'd rather not
have + overloaded and write +. for float addition:

        let f x y = x +. y

Of course, in larger examples, there's more context that helps in
resolving overloading, e.g.

        let f x = x + y * 3.14

But the general problem remains: in the presence of overloaded
operators, ML's type system no longer possesses the principal typing
property, hence type inference can fail on well-typed but ambiguous
programs.

Lots of effort have been invested in trying to resolve that problem,
in particular the development of type classes as implemented in Haskell.
But it really opens a whole new can of worms, both on the semantic
side and on the implementation side.

If you're interested, here are some references:

        Wadler and Blott, "How to make ad-hoc polymorphism less ad-hoc",
        POPL 89.

        Hudak et al, "Report on the programming language Haskell",
        SIGPLAN Notices 27(5), 1992.

        Dubois, Rouaix, and Weis, "Extensional polymorphism", POPL 95.

        Harper and Morriset, "Compiling polymorphism using intensional
        type analysis, POPL 95.

As you can see, the problem of overloaded operators is far from
solved. Until the dust settles, I'd rather keep Caml Light simple and
implement no overloading at all.

- Xavier Leroy

Re: entiers et reels

[Thorsten Ohl]

>>>>> "Pierre" == Pierre Weis <Pierre.Weis@inria.fr> writes:

Pierre> En revanche il n'y a pas de sens raisonable a` une addition
Pierre> polymorphe, et c'est pourquoi nous avons une collection
Pierre> d'additions monomorphes.

 [ No, I'm not going to embarrass myself by trying to respond in
   French ... :-) ]

Maybe I'm too dense or I have been exposed to too much Fortran, but I
don't fully understand:

Standard ML has it (at least in the New Jersey incarnation), so why
can't Caml?  As long as all operands are of the same type, the
semantics should be obvious.

I agreee that promotion will open a can of worms (standard example:
(1/2)*2.0 would most likely evaluate to 0.0, which is even more likely
_not_ what the programmer intended).  But wouldn't it be possible to
assign types to subexpressions based on the context in such a way that
no information can be lost?

I asking out of curiosity, but from the user's perspective I want to
add that polymorphic arithmetic is just soooo convenient.  It can be
abused, but it can also make programs much more readable, if used with
discretion.  In particular if types have a natural inclusion (like
natural, integer, rational, real and complex numbers).  Also for
vector spaces: it is usually not ambigious whether a scalar or an
inner product is intended.

Greetings,
-Thorsten

/// Thorsten Ohl, TH Darmstadt, Schlossgartenstr. 9, D-64289 Darmstadt, Germany
//// http://crunch.ikp.physik.th-darmstadt.de/~ohl //// voice: +49-6151-16-3116
///// email: Thorsten.Ohl@Physik.TH-Darmstadt.de /// secretary: 2072, fax: 2421

Re: entiers et reels

[Pierre Weis]

> pourquoi les relations < > <= etc.. sont-elles polymorphes et les operations
> + * etc.. ne le sont-elles pas?
> 
> Hubert Fauque

En fait les comparaisons sont des primitives polymorphes en Caml Light
0.7. Ces primitives travaillent uniforme'ment sur tous les types de
donne'es, en effectuant une descente re'cursive dans la structure des
donne'e pour les comparer. C'est tre`s pratique car les fonctions qui
utilisent des comparaisons peuvent e^tre polymorphes. Ce comportement
est raisonnable pour la plupart des valeurs Caml, comme les entiers ou
les chai^nes de caracte`res ou me^me pour les types de donne'es
``alge'briques'' qu'on de'finit en Caml. Les proble`mes peuvent
apparai^tre dans le cas de donne'es cycliques (la comparaison peut
boucler), ou les donne'es de types non alge'briques (par exemple les
nombres rationnels du module camlnum). De la me^me fac,on les
fonctions ne font pas partie d'un type de'fini comme une alge`bre
libre: la comparison de fonctions est donc proble'matique. C'est
pourquoi les comparaisons ont un comportement bizarre avec les
fonctions: on accepte (statiquement) de comparer les fonctions mais on
de'clenche une erreur dynamiquement.

En revanche il n'y a pas de sens raisonable a` une addition
polymorphe, et c'est pourquoi nous avons une collection d'additions
monomorphes.

> in english:
> I don't understand why caml accepts 5<6 and 5. < 6. but not 2+3 and 2.+3.

The reason is that comparisons (lesser or greater or equal) are
polymorphic in the Caml Light system 0.7. These primitives behave
uniformely on every data, using a recursive descent into the structure
of the data to compare them. This is very convenient since polymorphic
functions that use comparisons can be polymorphic. Indeed this
behaviour is reasonable for most Caml values, such as integers
character strings or even ``algebraic'' data types (sum or product
types defined by the user). Problems may appear in case of cyclic data
(the comparison may loop), or non algebraic data (such as rational
numbers when using the camlnum package). Since arrow types are not
algebraic, the polymorphic comparison becomes problematic when faced
to functions, for which there is no hope to implement
comparisons. That's why the comparisons have a strange behaviour for
function: they (statically) accept to compare functional values, but
raise a failure at runtime.

On the other hand we cannot find a reasonable meaning for a
polymorphic addition, that's why we only have monomorphic versions.

Pierre Weis

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

entiers et reels

[Fauque UPS]

*** english summary follows ***

une question sur caml-light:

pourquoi les relations < > <= etc.. sont-elles polymorphes et les operations
+ * etc.. ne le sont-elles pas?
caml accepte 5 > 6 et 5.0 > 6 mais refuse 3. + 2.; je comprend l'eventuelle
necessite de separer les types entier et reel mais pourquoi pas aussi pour
< >..


Hubert Fauque

in english:
I don't understand why caml accepts 5<6 and 5. < 6. but not 2+3 and 2.+3.