Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 4 sur 4
  1. #1
    Invité de passage
    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 : 0
    Points
    0

    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 :
    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 :
    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 Valentin Robert
    Étudiant
    Inscrit en
    juin 2004
    Messages
    70
    Détails du profil
    Informations personnelles :
    Nom : Homme Valentin Robert
    Âge : 25
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2004
    Messages : 70
    Points : 168
    Points
    168

    Par défaut

    Code :
    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 :
    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 :
    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 :
    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 :
    | 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 :
    | Abs (x,u) when x = var -> Abs(x,u)
    ?

    ---

    Une seconde chose genante est celle ci :

    Code :
    | 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 :
    (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 :
    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
    Invité de passage
    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 : 0
    Points
    0

    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 :
    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
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 574
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 574
    Points : 2 707
    Points
    2 707

    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: le cours OCaml, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •