Question

Question

[dsingh01]

[-- Attachment #1.1: Type: text/plain, Size: 327 bytes --]

Bonjour;
pour recevoir une aide pour la réalisation d'un projet de caml,j'ai 
envoyé un mail à cette adresse ocaml_beginners@yahoogroups.com 
<mailto:ocaml_beginners@yahoogroups.com>
mais je n'ai pas eu de réponse .
Pouvez-vous faire en sorte que je recoive une réponse ou alors 
pouvez-vous m'aidez pour le projet que voici:


[-- Attachment #1.2: Type: text/html, Size: 640 bytes --]

[-- Attachment #2: enonce.txt --]
[-- Type: text/plain, Size: 14829 bytes --]

Projet de programmation fonctionnelle:
GENERATION D'OBJETS COMBINATOIRES DÉCRIT PAR UNE GRAMMAIRE
Le but de ce projet est de compter et d'engendrer l'ensemble des objets combinatoire décrit par une grammaire. Il est ainsi possible d'engendrer une grande variété d'objets comme des arbres ou des mots. 


1 Exemples
1.1 Les arbres binaires complets
Un arbre binaire complet est soit une feuille, soit un noeud sur lequel on a greffé deux arbres binaires complets. Cette définition se traduit dans le type ocaml:
type tree = Leaf | Node of tree*tree;;

Ainsi, on peut décrire l'ensemble des arbres binaires par les définitions récursives suivantes:
 - l'ensemble "Trees" des arbres est la réunion (que l'on notera en ocaml par le constructeur Union) de deux ensembles : l'ensemble "Nodes" des noeuds et l'ensemble "Leaf" des feuilles;
 -l'ensemble "Nodes" des noeuds est obtenu à partir de l'ensemble des paires d'arbres, c'est-à-dire le produit cartésien (noté par le constructeur Prod) de l'ensemble des arbres avec lui même;
 -il n'y a qu'un seul arbres possible constitué d'une feuille. C'est le singleton (constructeur Singleton) Leaf

Une telle définition est appelée grammaire. On écrira en ocaml la grammaire des arbres de la manière suivante:
let consNode fg fd = Node (fg,fd);; (* fonction qui construit un arbre à
                                       partir des deux sous-arbres *)
let gramTrees = valuGrammar ["Tree", Union ("Leaf", "Node");
                             "Leaf", Singleton Leaf;
                             "Node", Prod("Tree", "Tree", consNode)];;

Le but de ce projet est d'implanter un algorithme permettant de compter et d'engendrer automatiquement la liste des objets décrit par une grammaire de ce type: par exemple il y a 5 arbres binaires complets à quatre feuilles:
Ce que l'on peut obtenir par le programme
# count gramTrees "Tree" 4;;
- : int = 5

La liste des objets décrits par la grammaire peut ensuite être obtenue comme suit.
# derivation gramTrees "Tree" 4;;
- : tree objects list =
[Pair (Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf), Atom Leaf);
 Pair (Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf)), Atom Leaf);
 Pair (Pair (Atom Leaf, Atom Leaf), Pair (Atom Leaf, Atom Leaf));
 Pair (Atom Leaf, Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf));
 Pair (Atom Leaf, Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf)))]

Une telle expression qui décrit la suite des opérations dans la grammaire est appelé une dérivation de la grammaire. À chaque dérivation correspond un arbre. Voici la liste des arbres correspondants aux dérivations précédentes:

# generation gramTrees "Tree" 4;;
- : tree list =
[Node (Node (Node (Leaf, Leaf), Leaf), Leaf);
 Node (Node (Leaf, Node (Leaf, Leaf)), Leaf);
 Node (Node (Leaf, Leaf), Node (Leaf, Leaf));
 Node (Leaf, Node (Node (Leaf, Leaf), Leaf));
 Node (Leaf, Node (Leaf, Node (Leaf, Leaf)))]

1.2 Les mots de Fibonacci
On appelle mot de Fibonacci tout mot sur l'alphabet A et B qui ne contient pas deux B a la suite. Un tel mot w est décrit par la grammaire suivante:
 -soit w est vide;
 -soit w est de la forme Au où u est un mot de Fibonacci;
 -soit w est le mot B;
 -soit w est de la forme BAu où u est un mot de Fibonacci;
Ceci ce traduit en ocaml par la grammaire:
let gramFibo = valuGrammar ["Fib",    Union ("Vide",  "Cas1");
                            "Cas1",   Union ("CasAu", "Cas2");
                            "Cas2",   Union ("AtomB", "CasBAu");
                            "Vide",   Epsilon "";
                            "CasAu",  Prod  ("AtomA", "Fib", (^));
                            "AtomA",  Singleton "A";
                            "AtomB",  Singleton "B";
                            "CasBAu", Prod  ("AtomB", "CasAu", (^))
                           ];;

Notons la fonction (^) qui concatène deux chaîne de caractères. Voici la liste des mots de Fibonacci de longueur 3: AAA, AAB, ABA, BAA, BAB.  Ce qui se vérifie par
# count gramFibo "Fib" 3;;
- : int = 5
# generation gramFibo "Fib" 3;;
- : string list = ["AAA"; "AAB"; "ABA"; "BAA"; "BAB"]

Voici comment ils sont dérivés par la grammaire:
# derivation gramFibo "Fib" 3;;
- : string objects list =
[Pair (Atom "A", Pair (Atom "A", Pair (Atom "A", Eps "")));
 Pair (Atom "A", Pair (Atom "A", Atom "B"));
 Pair (Atom "A", Pair (Atom "B", Pair (Atom "A", Eps "")));
 Pair (Atom "B", Pair (Atom "A", Pair (Atom "A", Eps "")));
 Pair (Atom "B", Pair (Atom "A", Atom "B"))]

On peut de la même manière obtenir les 21 mots de Fibonacci de longueur 6:
# generation gramFibo "Fib" 6;;
- : string list =
["AAAAAA"; "AAAAAB"; "AAAABA"; "AAABAA"; "AAABAB"; "AABAAA"; "AABAAB";
 "AABABA"; "ABAAAA"; "ABAAAB"; "ABAABA"; "ABABAA"; "ABABAB"; "BAAAAA";
 "BAAAAB"; "BAAABA"; "BAABAA"; "BAABAB"; "BABAAA"; "BABAAB"; "BABABA"]

2 Définitions formelles
Soit 'a un type caml. Une grammaire décrit récursivement un sous-ensemble de l'ensemble des objets de type 'a. Elle est constitué d'un ensemble de règles ayant chacune un nom (chaîne de caractères). Le nom d'une règle est appelé symbole non-terminal ou plus simplement non-terminal de la grammaire.

Une règle de grammaire R décrit un ensemble qui est
 1 soit un singleton dont le seul élément est un objet atomique de type 'a et qui sera de poids 1 (par exemple la feuille d'un arbre).
 2 soit un ensemble dont le seul élément est un objet vide de type 'a et qui sera de poids 0 (par exemple la chaîne vide).
 3 soit l'union de deux ensembles décrit par deux non-terminaux N_1 et N_2;
 4 soit le produit cartésien de deux ensembles décrit par deux non-terminaux N_1 et N_2; L'ensemble est alors constitué des paires d'éléments (e1, e2) appartenant à N_1 x N_2. Dans ce cas, il faut de plus donner à ocaml une fonction qui construit l'objet ocaml correspondant à la paire (e1, e2). 

La taille ou poids d'un objet est le nombre d'atomes qu'il contient. Le poids d'un élément correspondant à une paire (e1, e2) est donc la somme des poids de e1 et de e2.
À chaque non-terminal on associe la taille du plus petit objet qui en dérive.
Cette taille est appelé valuation du non-terminal.

2.1 Structures de données
Une grammaire sera stockées sous la forme de listes d'associations. On définit
donc le type liste d'association par:
type ('clef, 'valeur) assoc = ('clef * 'valeur) list;;
Une grammaire est une table qui associe à chaque non-terminal une règle de
grammaire:
type 'a rule = | Singleton of 'a
               | Epsilon   of 'a
               | Union     of string * string
               | Prod      of string * string * ('a->'a->'a);;
type 'a simpleGrammar = (string, 'a rule) assoc;;
Voici le type décrivant les objets dérivés correspondant aux règles:
type 'a objects = | Atom of 'a
                  | Eps  of 'a
                  | Pair of ('a objects) * ('a objects);;
où
 1 Atom x est le seul objet dérivé de la règle Singleton x;
 2 Eps e est le seul objet dérivé de la règle Epsilon e;
 3 si e1 est un objet dérivé du non-terminal nt1 et e2 est un objet dérivé du non-terminal nt2 alors Pair (e1,e2) est un objet par la règle (nt1,nt2,_).

De plus, une fois calculée, on a besoin de stocker la valuation à l'intérieur
de la grammaire. Une telle grammaire est dite valuée. On utilisera les types
ocaml suivants:
type valuation  = (string, int)  assoc;;
type 'a valuatedGrammar = (string, 'a rule*int) assoc;;

2.2 Pour s'entraîner
 1 Donner la grammaire ocaml de tous les mots sur l'alphabet A, B.
 2 Donner la grammaire ocaml des mots de Dyck, c'est-à-dire les mots sur l'alphabet (,) et qui sont correctement parenthésés.
 3 Écrire une fonction qui vérifie qu'une grammaire est correcte, c'est-à-dire que chaque non-terminal apparaissant dans une règle est bien défini par la grammaire.

3 Algorithmes
On écrira le programme en quatres temps:
 1 Calcul de la valuation d'une grammaire (ce qui permet de vérifier la grammaire);
 2 Calcul du nombre d'objets de poids donné;
 3 Calcul des dérivations des objets d'un poids donné;
 4 Calcul des objets d'un poids donné;
Le calcul de la valuation est nécessaire aux étapes suivantes qui sont
indépendantes. Je les ai néanmoins classé par ordre croissant de difficulté.

3.1 Calcul de la valuation
La valuation du non-terminal nt est la taille du plus petit objet qui en dérive. La valuation d'une grammaire est l'ensemble des valuations des terminaux. Elle vérifie les quatres règles suivantes:
 1 la valuation d'un Singleton est 1;
 2 la valuation d'un Epsilon est 0;
 3 la valuation de l'union Union des non-terminaux N_1 et N_2 est le minimum des valuations de N_1 et de N_2;
 4 la valuation du produit Prod des non-terminaux N1 et N2 est la somme des valuations de N_1 et de N_2;

Pour la calculer, on procède comme suit. On part de la valuation V_0 (incorrecte) qui associe à chaque non-terminal la valeur infini. En appliquant une fois non récursivement (pour éviter les boucles infinies) les règles précédentes à partir de V_0, on calcule une nouvelle valuation V_1.
On calcule ensuite de même une valuation V_2 a partir de V_1. On recommence tant que la valuation V_n est différente de V_n-1. La valuation cherchée V = V_n est obtenue quand V_n=V_n-1.
  Note: Si V(N) := V_n(N) = infini pour un certain non terminal N, alors aucun objet ne dérive de ce non-terminal. On considère alors que la grammaire est incorrecte.

3.1 À faire:
En ocaml on définira donc le type et l'exception suivante
type intInf = Infinity | Int of int;;
exception InfiniteValuation of string;;
 4 Écrire les fonctions plusIntInf et minIntInf pour calculer la somme et le plus petit de deux entiers ou infinis.
val plusIntInf : intInf -> intInf -> intInf
val minIntInf : intInf -> intInf -> intInf
 5 Écrire une fonction nextValuation qui calcule la valuation V_i à partir de la grammaire et de V_i-1:
val nextValuation : 'a simpleGrammar ->
                       (string * intInf) list -> (string * intInf) list
 6 Écrire la fonction makeValuation qui calcule la valuation d'une grammaire et en déduire une fonction valuGrammar qui calcule la grammaire valuée associée à une grammaire simple et qui renvoie une exception InfiniteValuation nt si un terminal nt a une valuation infinie.
val makeValuation : 'a simpleGrammar -> (string * intInf) list
val valuGrammar : 'a simpleGrammar -> 'a valuatedGrammar
Toutes les fonctions suivantes travaillerons sur la grammaire valuée.

3.2 Comptage du nombre d'objets
Le comptage du nombre d'objets de poids i se fait en appliquant récursivement les règles suivantes:
Soit N un non-terminal. On note C_N(i) le nombre d'objet de poids i.
 1 si N est un Singleton alors C_N(1) = 1 et C_N(i) = 0 si i est différent de 1;
 2 si N est un Epsilon alors alors C_N(0) = 1 et C_N(i) = 0 si i est différent de 0;
 3 si N est l'union Union des non-terminaux N_1 et N_2 alors C_N(i) = C_{N_1}(i) + C_{N_2}(i),;
 4 si N est le produit Prod des non-terminaux N_1 et N_2:
   C_N(i) = sum_{k+l=i} C_{N_1}(k) + C_{N_2}(l),;
 Pour aller plus vite et éviter des boucles infinies, on ne considérera dans la somme précédente que les cas où k >= V(N_1) et l >= V(N_2), où V(N) désigne la valuation du non-terminal N. En effet, par définition
  C_N(i) = 0 si V(N) > i. 

3.2.1 A faire
 7 Écrire la fonction count qui compte le nombre d'objets d'une grammaire dérivant d'un non-terminal et d'un poids donné:
val count : 'a valuatedGrammar -> string -> int -> int

3.3 Calcul de la liste des dérivations et des objets
L'algorithme est exactement le même dans les deux cas, seul diffère le type du
résultat. On applique récursivement les définitions des constructeurs Singleton, Epsilon, Union et Prod pour retourner la liste des objets de taille i. En particulier, si N  est le produit Prod des non-terminaux N_1 et N_2, la liste des objets dérivant de N et de poids i est la concaténation des listes de tous les produits cartésiens d'élément dérivant de N_1 et de taille k et d'élément dérivant de N_2 et de taille l, pour tous les couples k,l tels que
k+l=i, k >= V(N_1) et l >= V(N_2) (comme précédemment V(M) désigne la valuation du non-terminal M).

Par exemple, pour obtenir les arbres de taille 3, on procède de la manière suivante
Calcul de Tree = Union (Leaf, Node) avec i=3.
 -Application de Leaf = Singleton Leaf avec i=3, on retourne la liste vide [];
 -Application de Node = Prod(Tree, Tree) avec i=3. La valuation de Tree est 1. Il y a donc deux possibilités 3=1+2 ou 3=2+1.
  
  1 -Application de Tree = Union (Leaf, Node)} avec i=2.
    -Leaf est vide avec i=2 on retourne la liste vide.
    -Application de Node = Prod(Tree, Tree) avec i=2. La valuation de Tree est 1. Une seule décomposition est possible 1+1... On appelle donc deux fois Tree avec i=1... (Je n'écrit pas les appels récursifs)...qui retourne la liste [Atom Leaf]. On retourne donc la liste :[Pair (Atom Leaf, Atom Leaf)]
   -Application de Tree = Union (Leaf, Node) avec i=1.On retourne la liste : [Atom Leaf]
Le produit cartésien des deux listes précédentes est la liste formée du seul élément [Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf)]
   
  2 -Application de Tree = Union (Leaf, Node) avec i=1.On retourne la liste 
[Atom Leaf]
    -Application de Tree = Union (Leaf, Node) avec i=2.On retourne donc la liste
[Pair (Atom Leaf, Atom Leaf)]
  Le produit cartésien des deux listes précédentes est la liste formée du seul élément [Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf))]
  
On retourne donc la liste des deux dérivations:
[Pair (Pair (Atom Leaf, Atom Leaf), Atom Leaf);
 Pair (Atom Leaf, Pair (Atom Leaf, Atom Leaf))]

Pour i=6, il faut essayer les décompositions 6=5+1, 6=4+2, 6=3+3, 6=2+4 et 6=1+5. Étudions le cas 3+3. Par appel récursif on trouve deux arbres de poids 3:
 [Node (Node (Leaf, Leaf), Leaf); Node (Leaf, Node (Leaf, Leaf))]

Le produit cartésien est donc formé de 4 éléments qui correspondent aux 4 arbres suivants:
 Node (Node (Leaf, Node (Leaf, Leaf)), Node (Node (Leaf, Leaf), Leaf));
 Node (Node (Node (Leaf, Leaf), Leaf), Node (Node (Leaf, Leaf), Leaf));
 Node (Node (Leaf, Node (Leaf, Leaf)), Node (Leaf, Node (Leaf, Leaf)));
 Node (Node (Node (Leaf, Leaf), Leaf), Node (Leaf, Node (Leaf, Leaf)));

3.3.1 À faire:
 8  Écrire une fonction
val cartProd : 'a objects list -> 'a objects list -> 'a objects list qui calcule le produit cartésien de deux listes d'objets.
 9 Écrire la fonction
val derivation : 'a valuatedGrammar -> string -> int -> 'a objects list qui calcule la liste des objets dérivant d'un non-terminal d'une grammaire et d'un poids donné.
 10 Écrire la fonction
val cartProdCons : ('a -> 'a -> 'a) -> 'a list -> 'a list -> 'a list qui construit en utilisant une fonction de construction (par exemple consNode ou (^) la liste des objets correspondants aux dérivation d'un non-terminal d'une grammaire et d'un poids donné.
 11 En déduire la fonction 
val generation : 'a valuatedGrammar -> string -> int -> 'a list qui répond au problème posé. 

Re: [Caml-list] Question

[Remi Vanicat]

Le 23/05/05, dsingh01"@etudiant.univ-mlv.fr  dsingh01<"> a écrit :
>  Bonjour;
>  pour recevoir une aide pour la réalisation d'un projet de caml,j'ai envoyé
> un mail à cette adresse ocaml_beginners@yahoogroups.com
>  mais je n'ai pas eu de réponse .

ocaml_begginers est une liste qu'on ne peut acceder que s'y on est abboner. Voir
http://groups.yahoo.com/group/ocaml_beginners

>  Pouvez-vous faire en sorte que je recoive une réponse ou alors pouvez-vous
> m'aidez pour le projet que voici:
>  

Le projet que l'on vous propose m'a l'aire détailler. N'esperez pas
qu'on le résolve pour vous, essayez un peu de le faire tout seul. Et
si vos avez des questions plus spécifique, posez les, mais pas avant
d'avoir relut votre cours et réfléchis un peu.

In english: a student ask us to do its homework, I reaply that it
should do it by himself.

Re: [Caml-list] Question

[Jacques Carette]

Je ne peux pas aider directement, mais il est quand meme bon de noter que le packetage 'combstruct' pour le logiciel 
Maple, fait tout ceci et meme beaucoup plus.  Il peut etre de l'utiliser comme point de comparaison.  Puisque ce 
logicial (combstruct) est issu du projet ALGO a l'INRIA, il devrait etre possible d'obtenir de l'aide de ca cote 
aussi.

Jacques

" dsingh01" <" dsingh01"@etudiant.univ-mlv.fr> wrote:
> Bonjour;
> pour recevoir une aide pour la réalisation d'un projet de caml,j'ai envoyé un mail à cette adresse 
> ocaml_beginners@yahoogroups.com <mailto:ocaml_beginners@yahoogroups.com>
> mais je n'ai pas eu de réponse .
> Pouvez-vous faire en sorte que je recoive une réponse ou alors pouvez-vous m'aidez pour le projet que voici:
> 

Re: [Caml-list] question

[Damien Bobillot]

[-- Attachment #1.1: Type: text/plain, Size: 551 bytes --]


Le 8 juin 05 à 12:06, dsingh01 a écrit :

> j'ai envoye un mail a
> ocaml_beginners@yahoogroups.com
> pour qu'on m'aide a debugger des fonctions et je voudrais savoir  
> quand j'aurais une reponse.
> merci de me repondre

Le temps que quelqu'un le fasse : les mailings listes ne sont pas des  
hotlines, les réponses ne viennent que lorsque quelqu'un décide d'en  
faire une.

Par ailleurs, n'étant pas abonné à ocaml_beginners@yahoogroups.com  
comme de nombreuses personnes ici, je ne pourrais pas t'aider

-- 
Damien Bobillot


[-- Attachment #1.2: Type: text/html, Size: 1361 bytes --]

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2375 bytes --]

Re: [Caml-list] Question

[Luc Maranget]

> On Thu, 2003-12-11 at 20:52, Luc Maranget wrote:
> 
> > To conclude adopting the Felix way in Ocaml is by no mean a trivial
> > change and benefits are unclear, how many programs do realy use this
> > feature ?
> 
> Well, none in Ocaml because it isn't present :-)
> I have occasionally wanted this, but there is always
> a workaround.
> 
> Basically, I think it would be useful in the following
> situation:
> 
> 	match x with
> 	| A
> 	| (B (j,k) when j=k) -> e1
> 	| B (j,k) -> e2
Hum, I think that you assume this is correct 
provided j and k are not present in e1.

However, this code does not follow the current rules of
bindings in or-pattern: j and k are bound only in the right argument of
the or pattern.

Since using j and k in ``when j=k'' seems legitimate, this means that
the rules of bindings patterns also need to be changed...


> 
> 	match x with
> 	| A i
> 	| B (i,k) when i = k -> ... i ..
> 
Same binding problem, even more clear.
the scoping rules for variable bound in patterns become more complicated.



-- 
Luc Maranget

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

[skaller]

On Thu, 2003-12-11 at 20:52, Luc Maranget wrote:

> To conclude adopting the Felix way in Ocaml is by no mean a trivial
> change and benefits are unclear, how many programs do realy use this
> feature ?

Well, none in Ocaml because it isn't present :-)
I have occasionally wanted this, but there is always
a workaround.

Basically, I think it would be useful in the following
situation:

	match x with
	| A
	| (B (j,k) when j=k) ->
	| B (j,k) ->

Without a nested when clause, you could code

	let handler () = ... in
	match x with
	| A -> handler ()
	| B (j,k) when j = k -> handler ()
	| B (j,k) -> ...

delocalising the handler. (I have matches several pages long,
so this is annoying).

Also useful would be:

	match x with
	| A i
	| B (i,k) when i = k -> ... i ..

though I can't see a way to generalise that. 

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

[Luc Maranget]

> > The when construct introduces a guard to a pattern matching
> > clause. This means that a when construct is global to the entire
> > pattern of the clause it appears in; it means in particular that no
> > when construct can be nested into a pattern and the question of its
> > distributivity wrt any other construct is pointless.
> > 
> > >  Is there a good reason for this?
> > 
> > Yes: simplicity, complexity invariants preservation for runtime
> > pattern analysis decisions even in the presence of when clauses,
> > easier understanding of the compiler warnings, simplicity and
> > well-definedness semantics (in particular the desired invariance wrt
> > the order of evaluation).
> 
> Whoa! Can you say that slower? Felix allows nested when clauses
> in patterns (however it doesn't allow alternatives yet). 
> The current implementation is unoptimised, 
> I just evaluate the match of each pattern in turn until one matches.
> 
> One small difference .. the argument of a when clause is
> an expression .. and felix expressions are purely functional
> so there is no issue of order of evaluation changing anything.
> 
> So, what have I lost?

In some sense order of evaluation may not be an issue
(at worst it can be left unspecified!).
That said.

  When clauses inside patterns would for sure much complicate optimized
compilation and maybe diagnostics. So basically you loose optimised
compilation and simple diagnostics.


  Moreover at the moment the AST types for patterns and expression are
not mutually recursive. Expressions depend on patterns but not the other way
round.

As far as I know, The compiler take advantage of this in many places,
with code that more or less looks as follows

let rec treat_pat = blabala
;;

let rec treat_expr = blabla ... treat_pat ...
;;


Making patterns and expressions mutually dependant, would perhaps,
break some untold assumption, hidden invariant etc.

To conclude adopting the Felix way in Ocaml is by no mean a trivial
change and benefits are unclear, how many programs do realy use this
feature ?


Cheers,
-- 
Luc Maranget

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

[skaller]

On Wed, 2003-12-10 at 21:27, Pierre Weis wrote:
> [...]
> >  I was expecting "when" to be right distributive over "|". I find
> > OCaml's behaviour not very intuitive in such a situation.
> [...]
> 
> The when construct introduces a guard to a pattern matching
> clause. This means that a when construct is global to the entire
> pattern of the clause it appears in; it means in particular that no
> when construct can be nested into a pattern and the question of its
> distributivity wrt any other construct is pointless.
> 
> >  Is there a good reason for this?
> 
> Yes: simplicity, complexity invariants preservation for runtime
> pattern analysis decisions even in the presence of when clauses,
> easier understanding of the compiler warnings, simplicity and
> well-definedness semantics (in particular the desired invariance wrt
> the order of evaluation).

Whoa! Can you say that slower? Felix allows nested when clauses
in patterns (however it doesn't allow alternatives yet). 
The current implementation is unoptimised, 
I just evaluate the match of each pattern in turn until one matches.

One small difference .. the argument of a when clause is
an expression .. and felix expressions are purely functional
so there is no issue of order of evaluation changing anything.

So, what have I lost?


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

[Pierre Weis]

[...]
>  I was expecting "when" to be right distributive over "|". I find
> OCaml's behaviour not very intuitive in such a situation.
[...]

The when construct introduces a guard to a pattern matching
clause. This means that a when construct is global to the entire
pattern of the clause it appears in; it means in particular that no
when construct can be nested into a pattern and the question of its
distributivity wrt any other construct is pointless.

>  Is there a good reason for this?

Yes: simplicity, complexity invariants preservation for runtime
pattern analysis decisions even in the presence of when clauses,
easier understanding of the compiler warnings, simplicity and
well-definedness semantics (in particular the desired invariance wrt
the order of evaluation).

>  Cheers,
> 
>  Sébastien.

Best regards,

Pierre Weis

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


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

[Damien Doligez]

On Monday, December 1, 2003, at 04:41 PM, sebastien FURIC wrote:

> # let test t t' = match t, t' with
>   | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
> -> "OK"
>   | _ -> "KO";;
> Characters 73-79:
> Warning: this pattern is unused.
>   | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
> -> "OK"
>                                           ^^^^^^
[...]

>  I was expecting "when" to be right distributive over "|".

That notion doesn't make sense because "when" is not a pattern operator.
If you "distribute" when over |, you get this:

  # let test t t' = match t, t' with
    | ((Toto _ | Titi _), Toto x when x = 0
       | Toto x, (Toto _ | Titi _) when x = 0)
      -> "OK"
    | _ -> "KO";;

which is nonsense, from O'Caml's point of view.

-- Damien

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

[sebastien FURIC]

Remi Vanicat a écrit :
> 
> "sebastien FURIC" <sebastien.furic@tni-valiosys.com> writes:
> 
> >  Hi,
> >
> >  What do you think of the following code?
> >
> > # type toto = Toto of int | Titi of string;;
> > type toto = Toto of int | Titi of string
> > # let test t t' = match t, t' with
> >   | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
> > -> "OK"
> >   | _ -> "KO";;
> > Characters 73-79:
> > Warning: this pattern is unused.
> >   | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
> > -> "OK"
> >                                           ^^^^^^
> 
> I can't answer to your question, but with your example, one can do a:
> 
> # let test t t' = match t, t' with
>   | ((Toto _ | Titi _), Toto 0
>   | Toto 0, (Toto _ | Titi _)) when x = 0 -> "OK"
>   | _ -> "KO";;
> 
> of course, this is not generalizable to any test.

 I could have even write:

# let test t t' = match t, t' with
  | _, Toto 0 | Toto 0, _ -> "OK"
  | _ -> "KO";;

 The point is that my example is extracted from a "serious" project
where I wrote something like:

| ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when f(x) = 0
-> ...

 and where type toto has more than 2 constructors.

 Cheers,

 Sébastien.

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

[Remi Vanicat]

"sebastien FURIC" <sebastien.furic@tni-valiosys.com> writes:

>  Hi,
>
>  What do you think of the following code?
>
> # type toto = Toto of int | Titi of string;;
> type toto = Toto of int | Titi of string
> # let test t t' = match t, t' with
>   | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
> -> "OK"
>   | _ -> "KO";;
> Characters 73-79:
> Warning: this pattern is unused.
>   | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
> -> "OK"
>                                           ^^^^^^

I can't answer to your question, but with your example, one can do a: 

# let test t t' = match t, t' with
  | ((Toto _ | Titi _), Toto 0
  | Toto 0, (Toto _ | Titi _)) when x = 0 -> "OK"
  | _ -> "KO";;

of course, this is not generalizable to any test.

-- 
Rémi Vanicat

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

[sebastien FURIC]

 Hi,

 What do you think of the following code?

# type toto = Toto of int | Titi of string;;
type toto = Toto of int | Titi of string
# let test t t' = match t, t' with
  | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
-> "OK"
  | _ -> "KO";;
Characters 73-79:
Warning: this pattern is unused.
  | ((Toto _ | Titi _), Toto x | Toto x, (Toto _ | Titi _)) when x = 0
-> "OK"
                                          ^^^^^^
val test : toto -> toto -> string = <fun>
# test (Toto 0) (Toto 1);;
- : string = "KO"

 I was expecting "when" to be right distributive over "|". I find
OCaml's behaviour not very intuitive in such a situation. The correct
code is:

# let test t t' = match t, t' with
  | (Toto _ | Titi _), Toto x when x = 0 -> "OK"
  | Toto x, (Toto _ | Titi _) when x = 0 -> "OK"
  | _ -> "KO";;
val test : toto -> toto -> string = <fun>
# test (Toto 0) (Toto 1);;
- : string = "OK"

 Is there a good reason for this?

 Cheers,

 Sébastien.

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