Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5
  1. #1
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 569
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 569
    Points : 2 571
    Points
    2 571

    Par défaut [Idée]Lambda-calcul non typé 100% graphique

    La palette de composants graphiques :



    Il n'y a en tout que trois composants logiques :
    1. La boîte-ronde pour l'abstraction.
    2. La boîte-coin-arrondi pour l'application. Dans le sens horaire : la fonction, le coin-arrondi puis l'argument.
    3. La boîtes-carrée pour les variables. Une boîtes-carrée contient un certain nombre de jetons. Ce nombre n donne la n-ième boîte-ronde rencontrée en suivant le cheminement des flèches. Il désigne l'abstraction par laquelle la variable est liée.


    Quelques exemples classiques :



    Vous trouvez plus lisible qu'une notation textuelle ? Moins lisible ?
    Le principal obstacle concret avant de faire une calculatrice complète c'est l'algo de tree-drawing pour afficher le résultat. Des idées sur ce point ?
    Du même auteur: le cours OCaml, le dernier article publié, le projet, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  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 : 172
    Points
    172

    Par défaut

    Bonjour,

    Un de mes collègues est très graphes et graphiques pour la représentation du lambda-calcul.

    Tu risques de rencontrer un problème lorsque tu auras trop d'applications imbriquées à gauche. Il va sûrement falloir compromettre la proximité des blocs et allonger des flèches, dès lors qu'on attein un niveau supérieur à 3.

    L'approche à la de Bruijn rend les choses assez difficile à lire, étiqueter les nœuds par des noms faciliterait la lecture. On connait les problèmes de ce compromis.

    Je dirais que je trouve ça :
    - moins lisible qu'un texte en nominal ;
    - un poil plus lisible qu'un texte en de Bruijn (tant que la taille reste petite).

    J'ai tendance à penser que, pour le dessin, tu aurais moins de problème avec une représentation "pyramidale", typique du dessin d'arbres. Ici, le recroquevillement qui s'opère pose problème.

  3. #3
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 569
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 569
    Points : 2 571
    Points
    2 571

    Par défaut La lettre Caml

    Il y a un bon algo de tree-drawing pyramidal dans La lettre Caml n°5.
    Et un algo de β-réduction dans La lettre Caml n°6.
    J'ai aussi lu des choses sur la KAM et la G-machine.

    Hé bien disons que je me suis laisser distraire un moment par mes jolis petits graphiques (la peur d'affronter mon code OCaml?).

    Je ferais bien de retourner à mon projet.
    Désolé pour le dérangement.
    Du même auteur: le cours OCaml, le dernier article publié, le projet, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  4. #4
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 569
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 569
    Points : 2 571
    Points
    2 571

    Par défaut Le jeu des tours de hanoï

    Déplacer n+1 anneaux de la tige A vers la tige C :
    Code ocaml :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    let rec zfix f x = f (zfix f) x
    
    let hanoi hn src tmp dst acc n =
      if n = 0 then
        src::dst::acc
      else
        hn tmp src dst (src::dst::(hn src dst tmp acc (pred n))) (pred n)
        
    let hanoi = (zfix hanoi) 'A' 'B' 'C' []

    Une fois λ-encodé :

    Code ocaml :
    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
    let nil  = Abs(Abs(Var 1))
    let trio = Abs(Abs(Abs(Abs(App(App(App(Var 1,Var 4),Var 3),Var 2)))))
    let rod_a = Abs(Var 1)
    let rod_b = Abs(Abs(Var 1))
    let rod_c = Abs(Abs(Var 2))
    let yfix = Abs(App(Abs(App(Var 2,App(Var 1,Var 1))),Abs(App(Var 2,App(Var 1,Var 1)))))
    let zero = Abs(Abs(Var 2))
    let one = Abs(Abs(App(Var 1,zero)))
    let two = Abs(Abs(App(Var 1,one)))
    let three = Abs(Abs(App(Var 1,two)))
    
    let hanoi =
       Abs(Abs(Abs(Abs(Abs(Abs(
          App(
          App(Var 1,App(App(App(trio,Var 5),Var 3),Var 2)), (* if n = 0 then src::dst::acc *)
             Abs(
                App(App(App(App(App(
                   Var 7, (* hn  *)
                   Var 5),(* tmp *)
                   Var 6),(* src *)
                   Var 4),(* dst *)
                   App(
                      App(App(trio,Var 6),Var 4), (* src::dst:: *)
                      App(App(App(App(App(Var 7,Var 6),Var 4),Var 5),Var 3),Var 1) (* hn src dst tmp acc (pred n) *)
                   )
                ),
                Var 1)
             )
          )
       ))))))
    
    let hanoi = (* yfix hanoi 'A' 'B' 'C' [] *)
       Abs(
          App(App(App(App(App(
             App(yfix,hanoi),
             rod_a),     
             rod_b),     
             rod_c),     
             nil),
             Var 1
          )
       )

    Afin de faciliter le calcul du prédécesseur l'entier pris en paramètre (nombre d'anneaux au départ sur la tige A) est en encodage de Scott.

    Solution pour 4 anneaux à déplacer de la tige A vers la tige C :

    Code ocaml :
    beta_reduction (App(hanoi,three));;

    Comme je n'ai pas encore vérifié la conversion en 2D (l'interpréteur 2D est en cours d'écriture) je me suis contenté d'une apparition furtive (Spoiler Afficher dans ma critique du film TRON Legacy). Si je programme aussi bien en 2D qu'en 1D ça devrait donner quelque chose comme ça :

    Du même auteur: le cours OCaml, le dernier article publié, le projet, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  5. #5
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 569
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 569
    Points : 2 571
    Points
    2 571

    Par défaut

    J'ai terminé l'écriture de l'interpréteur en 2D. Quelques tests m'ont confirmé que le programme ci-dessus résout bien le jeu des tours de Hanoï.

    Ça me motive pour la traduction d'un programme plus conséquent, par exemple :
    Code ocaml :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    type function_x =
         | X
         | Int of int
         | Neg of function_x
         | Sin of function_x
         | Cos of function_x
         | Exp of function_x
         | Power of function_x * int
         | Add of function_x * function_x
         | Mul of function_x * function_x
    
    let rec deriv = function
      | X        -> Int 1
      | Int n    -> Int 0
      | Neg(u)   -> Neg(deriv u)
      | Sin(u)   -> Mul(deriv u,Cos(u))
      | Cos(u)   -> Neg(Mul(deriv u,Sin(u)))
      | Exp(u)   -> Mul(deriv u,Exp(u))
      | Power(u,n) -> Mul(Int n,Mul(deriv u,Power(u,n-1)))
      | Add(u,v) -> Add(deriv u,deriv v)
      | Mul(u,v) -> Add(Mul(deriv u,v),Mul(u,deriv v))

    Sur cet exemple les constructeurs (du simple fait de leur nombre) seront considérablement plus abstraits :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    X ≡ x i n s c e p a m ↦ x
    Int ≡ j x i n s c e p a m ↦ i j
    Neg ≡ u x i n s c e p a m ↦ n u
    Sin ≡ u x i n s c e p a m ↦ s u
    Cos ≡ u x i n s c e p a m ↦ c u
    Exp ≡ u x i n s c e p a m ↦ e u
    Power ≡ u j x i n s c e p a m ↦ p u j
    Add ≡ u v x i n s c e p a m ↦ a u v
    Mul ≡ u v x i n s c e p a m ↦ m u v
    Ça devrait me permettre de mieux appréhender la charge que pose la 2D en matière de contrainte de layout.

    À gauche la palette de composants taille 39 × 39. À droite la même palette de composants taille 32 × 32. Pour l'un des nombreux éditeurs de cartes à tuiles (comme Mappy) sous win32 ou GTK2.

    Du même auteur: le cours OCaml, le dernier article publié, le projet, 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
  •