IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Beta conversion en caml


Sujet :

Caml

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2012
    Messages : 5
    Points : 2
    Points
    2
    Par défaut Beta conversion en caml
    Bonjour à tous,

    Je bloque de nouveau sur quelque chose. Je dois construire un beta-reducteur de lambda expression. Pour ce faire j'ai définit un type expr, définit la fonction freevar et maintenant je bloque sur la substitution, je sens que je m'en approche.

    Voici mon code pour l'instant :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     
    type expr = Var of char
              | Abs of char * expr
              | App of expr * expr;;
     
    let freevar var exp =
            let rec freevarIter var  = function
                     Var  x           -> true
                    |App (u,v)        -> ((freevarIter var u) or (freevarIter var v))
                    |Abs (x,u) when x  = var -> false
                    |Abs (x,u) when x  !=var -> freevarIter var u
     
                    in freevarIter var exp;;
     
    let rec subst var n exp= match exp with
             	Var  x    when x  = var -> n
            |       Var  y    when y != var -> y
            |       App (u,v) -> App((subst var n u),(subst var n v))
            |       Abs (x,u) -> Abs(x,u)
            |       Abs (y,u) when ((y != var) AND (freevar y n)=false) -> Abs(y,subst var n u)
            | 	Abs (y,u) when ((freevar y n) AND (((freevar a u)= false) or (freevar a n)=false))
    			-> subst(var n (Abs(a,subst a y)));;
    Je débute en ocaml et ne comprends pas tout. (c'est bien ça le problème)
    J'ai globalement recopié les définitions de mon cours mais pour la fin je sais pas comment définir que var n et exp sont des expr.

    Si je mets
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    let rec subst var:expr n:expr exp:expr= match exp with
             	Var  x    when x  = var -> n
    ...
    J'ai droit à un syntax error.

    Je me doute que le reste des fonctions n'est pas parfait mais j'aimerais au moins réussir à compiler pour pouvoir faire des tests.

    Merci d'avance pour votre aide!

  2. #2
    Membre actif
    Avatar de Ptival
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2004
    Messages
    70
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2004
    Messages : 70
    Points : 276
    Points
    276
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    type expr =
    | Var of char
    | Abs of char * expr
    | App of expr * expr;;
    Jusqu'ici, tout va bien (tu n'as pas besoin des ";;" si tu ecris un fichier).

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    let freevar var exp =
      let rec freevarIter var  = function
      | Var  x                         -> true
      | App (u,v)                    -> ((freevarIter var u) or (freevarIter var v))
      | Abs (x,u) when x  = var -> false
      | Abs (x,u) when x  !=var -> freevarIter var u
      in freevarIter var exp;;
    Ca me semble raisonnable, voici une facon peut-etre un peu plus idiomatique d'ecrire la meme fonction :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    let rec freevar var = function
      | Var (_)                        -> true
      | App (u,v)                     -> (freevarIter var u) or (freevarIter var v)
      | Abs (x, _) when x = var  -> false
      | Abs (_, u) (* x != var *) -> freevarIter var u
    ---

    Passons au sujet epineux :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    let rec subst var n exp= match exp with
    | Var  x      when x  = var -> n (* au passage, tu evites ici un piege classique de debutant, bravo *)
    | Var  y      when y != var -> y
    | App (u,v)                     -> App((subst var n u),(subst var n v))
    | Abs (x,u)                     -> Abs(x,u)
    | Abs (y,u) when ((y != var) AND (freevar y n)=false) -> Abs(y,subst var n u)
    | Abs (y,u) when ((freevar y n) AND (((freevar a u)= false) or (freevar a n)=false))
    			-> subst(var n (Abs(a,subst a y)));;
    Un premier probleme apparait immediatement : les deux derniers motifs sont "hors de portee".

    Cette ligne semble bizarre :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    | Abs (x,u)                     -> Abs(x,u)
    Puisque cette ligne capture tous les motifs Abs, les deux lignes qui suivent ne sont jamais atteintes. Ne voulais-tu pas ecrire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    | Abs (x,u) when x = var -> Abs(x,u)
    ?

    ---

    Une seconde chose genante est celle ci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    | Abs (y,u) when ((y != var) AND (freevar y n)=false) -> Abs(y,subst var n u)
    Si y n'est pas libre dans n, pourquoi continuer la substitution ? (Apres tout, ton algorithme de substitution mimique sensiblement l'algorithme freevar).

    Au passage egalement, je ne connais pas la priorite respective de "=" et de "AND" (and ?), aussi, je mettrais des parentheses dans cette situation :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    (y != var) AND (freevar y n = false)
    Je pense que c'est la priorite normale, mais bon, je te previens quand meme.

    Et si tu changes le premier test, pas besoin de re-tester que y n'est pas var...

    ---

    Le dernier cas, c'est juste n'importe quoi :
    - ta condition est bien plus compliquee que necessaire ;
    - tu parles d'un "a" qui n'est mentionne nulle part ;
    - ton appel recursif est incorrect (tu essaies meme d'utiliser var comme une fonction...).

    A revoir.

    ---

    Pour ta derniere remarque, la syntaxe correct est :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    let rec subst (var:expr) (n:expr) (exp:expr) = match exp with
             	Var  x    when x  = var -> n
    ...
    Au passage encore, var devrait est un char, pas une expr. Mais ceci ne resoudra pas les autres problemes de ta fonction subst.

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2012
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2012
    Messages : 5
    Points : 2
    Points
    2
    Par défaut
    Merci beaucoup pour toutes ces explications! C'est beaucoup plus clair dans mon esprit!

    J'ai réussi à faire à peu près ce que je voulais, me manque que le problème de capture à gérer. Mais je vois pas trop comment pour l'instant.

    Je mets mon code, il a l'air de fonctionner sur les expressions que j'ai testé mais je me doute que sa fonctionne pas dans tous les cas.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    (* Définir le type expression du lambda calcul : exp *)
     
    type expr = Var of char
              | Abs of char * expr
              | App of expr * expr
     
    (* Définir FreeVar *)
     
    let freevar var exp =
            let rec freevarIter var  = function
                     Var  x  -> true
                    |App (u,v) -> (freevarIter var u) || (freevarIter var v)
                    |Abs (x,u) when x  = var -> false
                    |Abs (x,u) when x  !=var -> freevarIter var u
     
                    in freevarIter var exp;;
     
    let x = Var 'x';;
    let t = Var 't';;
    let y = Var 'y';;
    let z = Var 'z';;
    let v = Var 'v';;
     
    (* expressions du jeu d'essais *)
    let exp0 = App(Abs('x',App(x,t)),v);;
    let exp1 = App(Abs('x',App(Abs('y',App(y,x)),z)),v);;
    let exp2 = Abs('x',App(x,x));;
    let exp3 = App(Abs('x',t),App(exp2,exp2));;
     
    (* definir substitution valide , manque la gestion du problème de capture*)
     
    let rec subst (var:char) (n:expr) (exp:expr) = match exp with
             	Var  x    when x  = var -> n
            |       Var  y    -> exp
            |       App (u,v) -> App((subst var n u),(subst var n v))
            |       Abs (x,u) when x = var -> Abs(x,u)
            |       Abs (y,u) -> Abs(y,subst var n u)
     
     
    (* definir red_name, renvoie FN si existe avec un appel par nom *)
    let rec red_name exp=match exp with
    	Var x -> exp
    	| Abs(y,u) -> Abs(y,red_name u)
    	| App(Abs(z,v),w) -> red_name (subst z w v)
    	| App(a,b) -> App(red_name a,red_name b);;
     
    (* definir red_value , renvoie FN si existe avec un appel par valeur*)
    let rec red_value exp=match exp with
    	Var x -> exp
    	| Abs(y,u) -> Abs(y,red_value u)
    	| App(Abs(z,v),w) -> red_value (subst z (red_value w) v)
    	| App(a,b) -> App(red_value a,red_value b);;

    Je ne me sers plus de Freevar pour l'instant, mais je crois qu'elle ne fonctionne pas correctement. Je regarderais plus en détail plus tard. En attendant si vous avez des remarques sur mon code je suis preneur! En tout cas merci

  4. #4
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    Tu dois résoudre le problème de la capture des noms de variable ?
    Et tu n'as pas le droit de passer par les indices de De Bruijn

    Moi j'appelle ça de la maltraitance enseignant/étudiant.
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

Discussions similaires

  1. algo et caml
    Par rabi dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 08/11/2002, 23h44
  2. [MSXML] Comment empécher la conversion des entités ?
    Par nima dans le forum XSL/XSLT/XPATH
    Réponses: 3
    Dernier message: 08/11/2002, 15h14
  3. Algorithme de conversion de RTF vers HTML
    Par youtch dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 10/09/2002, 13h35
  4. [Conversions] Millisecondes...
    Par agh dans le forum Langage
    Réponses: 2
    Dernier message: 06/08/2002, 12h25
  5. Réponses: 2
    Dernier message: 05/06/2002, 13h29

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo