[Caml-list] égalité physique (==) avec Pervasives.(+)

[Caml-list] égalité physique (==) avec Pervasives.(+)

[Diego Olivier Fernandez Pons]

    Bonjour,

Je suis en train de préparer le système de description de contraintes
pour les algorithmes de descente sur les polyhèdres (i.e. simplexe et
variantes locales) que l'on utilise dans les approximations de
problèmes NP-difficiles

J'essaie d'encapsuler le type ['a] dans un type ['a expr]

type 'a expr =
  | Constante of 'a
  | Variable of int
  | Operateur of 'a expr * 'a expr * ('a -> 'a -> 'a)
  | Application of 'a expr * ('a -> 'a)

let inj = function x -> Constante x

let inj1 f = function expression ->
  match expression with
   | Constante v -> Constante f v
   | Variable _ | Operateur _ | Application _ ->
      Application (expression, f)

let inj2 f = fun x y ->
  match (x, y) with
    | (Constante s, Constante t) -> Constante (f s t)
    | _ -> Operateur (x, y, f)

val inj  : 'a -> 'a expr
val inj1 : ('a -> 'a) -> ('a expr -> 'a expr)
val inj2 : ('a -> 'a -> 'a) -> ('a expr -> 'a expr -> 'a expr)
val eval : 'a env -> 'a expr -> 'a

Maintenant je veux traverser la syntaxe abstaite et optimiser le
traitement des opérateurs les plus simples (*, +, /, ...) et pour les
reconnaître j'utilise l'égalité physique (==)

Seulement, les opérateurs Pervasive.qqch ne semblent pas se comporter
comme les fonctions définies par l'utilisateur :

let f = function x -> x + 1
let a = (1, f)
let (_, g) = a

f == g
- : bool = true

let a = (1, (+))
let (_, g) = a

(+) == g
- : bool = false

let a = (1, Pervasives.(+))
let (_, g) = a

Pervasives.(+) == g
- : bool = false


Pourquoi ce comportement ? Comment contourner le problème ?

        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] égalité physique (==) avec Pervasives.(+)

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 1213 bytes --]

Peut-être que Pervasives.(+), correspondant à une instruction du processeur (ou 
presque) et donc pas à une fonction habituelle, le compilo reconstruit-il une 
nouvelle fonction (ou cloture) à chaque fois que l'on utilise (+) de façon 
partielle.

Il me semble un peu bizarre d'utiliser l'égalité physique sur des fonctions !
cela suppose que l'on connait le mécanisme utilisé par le compilateur pour 
créer de nouvelles clôtuers ou utiliser les anciennes, ce qui n'est pas très bon:
- impossible de prouver les programmes,
- aucune garanties qu'ils tourneront sur les versions futures du langage !

Même l'orsqu'il s'agit d'une optimisation, il est important d'être sur qu'elle 
remplit son usage ! (même si le programm marche quel que soit le résultat de ==)

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: Type: application/pgp-signature, Size: 252 bytes --]

Re: [Caml-list] égalité physique (==) avec Pervasives.(+)

[Florian Hars]

> Il me semble un peu bizarre d'utiliser l'égalité physique sur des 
> fonctions !

Well, physical equality of closures is the only meaningful type of equality for 
functions (unless you manage to discover a polynomial algorithm to solve the 
halting problem).

Yours, Florian.

-------------------
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] égalité physique (==) avec Pervasives.(+)

[Diego Olivier Fernandez Pons]

    Bonjour,

On Tue, 7 Jan 2003, Christophe Raffalli wrote

> Même l'orsqu'il s'agit d'une optimisation, il est important d'être
> sur qu'elle remplit son usage ! (même si le programme marche quel
> que soit le résultat de ==)

C'est une remarque fort juste au demeurant !

Un des problèmes des solveurs de contraintes est la nécessité de
manipulation de fonctions sous deux formes :

- une forme explicite pour la propagation de contraintes

let f = fun x y -> x + y < 10 && 0 < x + y

si vous avez des bornes sur y, vous pouvez en déduire des bornes sur
x, mais pour ce faire il faut pouvoir 'traverser' f

- une forme 'compilée' pour l'énumération exhaustive

si vous avez épuisé toutes l'information dont vous disposiez, il ne
reste pas d'autre solution que d'essayer tous les couples (x, y) avec
un mécanisme de retour en arrière.

La librairie FaCiLe a choisi une forme explicite pour la propagation
(sous forme de syntaxe abstraite que l'on construit lors de la
déclarations de contraintes) et une fonction d'évaluation (donc assez
lente) pour la recherche.

Si je suppose résolue la question de la compilation à la volée
de fonctions (par exemple Dynamic Caml), on peut essayer un compromis
par une double représentation des fonctions

f = (f_abstraite, f_compilée)

Seulement, pour permuter de représentation selon les besoins, je ne
vois pas d'autre solution que :
- hacher la représentation courante (par exemple f_compilée)
- aller chercher la valeur dans une table (clé, g_abstraite,
g_compilée)
- vérifier l'égalité physique g_compilée == f_compilée
- en déduire que g_abstraite est bien une représentation abstraite de
la fonction voulue.

(ou bien une solution plus ou moins équivalente)

Je suis tout à fait d'accord sur le fait que l'égalité physique n'est
pas la panacée, mais je n'ai pas vraiment d'autre solution à proposer.

Et il y a bien sûr toujours le problème des applications partielles,
et je n'ai aucun moyen de prouver la correction du code, et je n'ai
aucune garantie sur la stabilité du code dans les futures versions, et
je ne sais même pas si cette optimisation remplit son usage...

Cela dit, mon courrier précédent n'était qu'une tentative de
résolution partielle du problème.

        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