Acid, le lisp-like de la communauté !

Je pense que je vais m'attaquer à la compilation plus bas niveau après avoir fini le typage. Je ne pense pas implémenter d'algorithme d'inférence de type pour l'instant, la dernière fois que j'ai essayé ça s'est mal passé

PS: J'ai presque un système de typage simple mais il s'appuie trop sur les types de Python. Je suis un peu obligé parce que l'AST Acid est traduit en AST Python pour être exécuté. C'est pourquoi je pense que je vais essayer d'implémenter un compilateur vers du bas niveau avant d'avancer mon typage. En soi je pourrais continuer avec l'AST Python mais ça risque d'être un peu brouillon si je commence à implémenter des types paramétrés et des types de données algébriques (je vais avoir recours à beaucoup de metaprogramming pour le coup)…

Je ne pense pas implémenter d'algorithme d'inférence de type pour l'instant, la dernière fois que j'ai essayé ça s'est mal passé

Alors c'est probablement une bonne chose de ne pas faire de typage du tout pour l'instant : les langages fonctionnels se prêtent assez mal à des systèmes de types minimalistes comme en C. Quand on a un langage expressif, soit on ne type pas (comme les Lisp typiques), soit on doit avoir un système de types expressif lui-même.

J'ai presque un système de typage simple mais il s'appuie trop sur les types de Python. Je suis un peu obligé parce que l'AST Acid est traduit en AST Python pour être exécuté.

L'intérêt d'un système de types, c'est qu'il prouve statiquement que ton programme ne comporte pas d'erreur. Donc si ton programme type, tu n'as pas besoin en plus de l'adapter au pseudo-typage de python : il suffit de mettre des Object partout pour que ça passe. C'est une pratique assez courante quand on compile vers un langage qui a lui-même un système de types différent de la source (par exemple, l'extraction de Coq vers OCaml met des Obj.magic (* 'a -> 'b *) partout.)

Ca se voit moins dans les schémas d e compilation qu'on a l'habitude de voir de loin, parce qu'on compile vers un langage non typé (comme l'assembleur) ou qu'on compile vers un langage dont le système de types est conçu pour que ça se passe bien (par exemple, les instructions d'une machine virtuelle - je n'ai pas d'exemple certain sous la main, mais je pense que le bytecode java est un peu typé).

D'accord donc il faut que j'écrive un typechecker statique qui vérifie la cohérence des types de mon AST Acid. Du coup il va falloir coder un inférenceur de type non ?

En fait la dernière fois j'avais galéré à cause des variables de types libres.

De toute façon je vais essayer d'implémenter le truc en Python, ça sera probablement plus facile qu'en Haskell.

AlphaZeta: Juste si la dernière fois ça a foutu ton code en l'air développe le sur une branche séparé.

Tu peux vouloir préciser le type de chaque variable directement dans la syntaxe et donc éviter l'inférenceur. Mais autrement oui, il te faudra le créer. Et non, que tu codes en Python ou en Haskell, tu ne faciliteras pas plus la vie d'un côté ou de l'autre, tu coderas juste différemment.

Salut,

Je suis un peu bloqué pour l'implémentation du pattern matching. Je ne sais pas comment traduire une expression match en AST Python. J'ai essayé en faisant des try partout en écrivant un AST Python à la main mais ça fait 50 lignes et c'est sale

Quelqu'un pourrait m'aider ?

@Lalla: Ouais pas faux.

Edit: Je sais déjà que mes patterns seront des objets avec une méthode match qui retourne un environnement. Par exemple, Uncons(Var('x'), Var('xs')).match([1, 2, 3, 4]) retournera quelque chose comme ça: {'x': 1, 'xs': [2, 3, 4]} (ou bien lèvera une MatchError). Ceci est l'équivalent en Acid de ceci:

1
2
3
4

(match (Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))) (
   ((Cons x xs) ...)   // la valeur si le motif correspond
   ...                 // peut-être d'autres patterns
))

Une suite de if/elif ?

@Kje: Non parce que le motif peut aussi déclarer des valeurs (regarde mon message d'avant, j'ai édité). Donc il faut aussi que j'ai la possibilité de déclarer des variable à l'exécution. Tout à l'heure j'ai fait ça avec exec mais c'est immonde.

En gros mon idée c'était ça:

1
2
3
4

(match x (
    (pat1 val1)
    (pat2 val2)
))

… se traduit en Python par:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

try:
    __m = pat1.match(x)
except MatchError:
    try:
        __m = pat2.match(x)
    except MatchError:
        raise
    else:
        for __k, __v in __m.items():
            __k = __v   # ici on met un exec parce que c'est pas possible autrement (à ma 
connaissance)
            # exec('{} = {}'.format(__k, __v))
        return val1
else:
    return val2

Ouais d'accord mais ça revient à peu près à mon code. Ça résout pas le problème du exec. Surtout que je dois écrire tout l'AST à la main, donc ça fait environ 80 lignes ton truc.

Edit: Ah non je pense que je peux me débrouiller avec ast.parse si je veux échapper à l'écriture de l'AST à la main. Par contre j'ai toujours le problème du exec

Edit 2: D'ailleurs ton code peut être simplifié:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

for pattern, val in patterns:
    try:
        _m = pattern.match(x)
    except MatchError:
       continue  # ou pass, ici ça change rien
    else:
        for _k, _v in _m.items():
            exec("%s = %s" % (_k, _v))  # globals() et locals() sont par défaut
        return val

raise MatchError(x)

Edit: Et merde… En fait je peux pas utiliser ast.parse parce que en fait c'est pas return val mais je dois insérer l'AST de val dans le else, pas le retourner.

Jésus Marie Joseph qu'ai-je fait ?

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

value = compiler.translate(match.value)

node = python_ast.ExceptHandler(
    type=python_ast.Name(id='MatchError', ctx=python_ast.Load()),
    name=None,
    body=[
        python_ast.Raise(exc=None, cause=None)
    ]
)

for assoc in reversed(match.assocs):
    node = python_ast.Try(
        body=[
            python_ast.Assign(
                targets=[
                    python_ast.Name(id='__m', ctx=python_ast.Store())
                ],
                value=python_ast.Call(
                    func=python_ast.Attribute(
                        value=compiler.translate(assoc.pattern),
                        attr='match',
                        ctx=python_ast.Load()
                    ),
                    args=[value],
                    keywords=[]
                )
            )
        ],
        handlers=[node],
        orelse=[
            python_ast.For(
                target=python_ast.Tuple(
                    elts=[
                        python_ast.Name(id='__k', ctx=python_ast.Store()),
                        python_ast.Name(id='__v', ctx=python_ast.Store())
                    ],
                    ctx=python_ast.Store()
                ),
                iter=python_ast.Call(
                    func=python_ast.Attribute(
                        value=python_ast.Name(id='__m', ctx=python_ast.Load())
                        attr='items',
                        ctx=python_ast.Load()
                    ),
                    args=[],
                    keywords=[]
                ),
                body=[
                    python_ast.Expr(
                        expr=python_ast.Call(
                            func=python_ast.Name(id='exec', ctx=python_ast.Load())
                            args=[
                                python_ast.Call(
                                    func=python_ast.Attribute(
                                        value=python_ast.Str(string="{} = {}"),
                                        attr='format',
                                        ctx=python_ast.Load()
                                    ),
                                    args=[
                                        python_ast.Name(id='__k', ctx=python_ast.Store()),
                                        python_ast.Name(id='__v', ctx=python_ast.Store()),
                                    ],
                                    keywords=[]
                                )
                            ],
                            keywords=[]
                        )
                    )
                ]
            ),
            python_ast.Return(value=compiler.translate(last.value))
        ],
        finalbody=[]
    )

En plus ça marche même pas parce que là j'ai une instruction, pas une expression

*pan*

Edit: OK j'ai trouvé un moyen pour transformer mon instruction en expression.

De la doc sur le pattern matching. D'ailleurs, le bouquin en lui-même vaut sans doute la peine d'être lu: The Implementation of functional programming languages.
Une autre approche serait d'implémenter match directement dans le langage cible, à l'aide de macros. Mais ça suppose d'avoir des macros.

J'avais mollement lu ce bouquin pour savoir me renseigner sur la G-Machine. Cependant, avec notre méthode de compilation actuelle, à savoir compiler vers un AST Python, je pense que c'est plus adapté d'implémenter ça directement en Python. Pas forcément par des macros parce que ça existe pas dans la version officielle de Python, mais en bidouillant avec l'environnement par défaut d'Acid. C'est ce que j'ai commencé à faire.

Edit: Par contre quand on aura un système de compilation vers du plus bas niveau, pourquoi pas

Luc Maranget a écrit quelques papiers sur la compilation du pattern matching. Optimizing pattern matching (je te laisse chercher) notamment décrit à peu près l'implémentation actuelle dans le compilateur OCaml. Il a aussi un papier plus récent (2008 contre 2001) qui fait ça avec des arbres de décision.

Salut,

Suite à un petit souci, je n'ai pas accès aux dernières modifications de myrma/PyAcid:typing. Du coup je pense faire un REPL et changer un peu le système d'erreur pour que ça soit un peu plus explicite.

AZ.

Edit: Sinon j'aurais aimé faire un truc stylé avec des couleurs pour les erreurs comme Python colore en rouge le traceback dans les terminaux xterm. Le souci c'est que je ne sais pas quelle librairie utiliser. J'ai entendu parler de colorama mais j'ai envie d'utiliser le moins de dépendance possible.

Je sais que ça pour le coup c'est un détail insignifiant, mais comme je peux pas avancer ma branche typing j'ai rien d'autre à faire

Edit: Sinon j'aurais aimé faire un truc stylé avec des couleurs pour les erreurs comme Python colore en rouge le traceback dans les terminaux xterm. Le souci c'est que je ne sais pas quelle librairie utiliser. J'ai entendu parler de colorama mais j'ai envie d'utiliser le moins de dépendance possible.

Pour l'avoir essayé, colorama est très bien, il fonctionne aussi sous Windows (et peut-être macOS).

Comment peut-on résoudre ce problème ?

Si tu tiens vraiment à rester portable tout en affichant des couleurs, colorama est la seule solution. Pour un compilateur c'est quand même une dépendance largement acceptable (et puis c'est pas très lourd comme package).

PS : MacOS utilisant bash comme shell par défaut, il n'y a aucune raison que ça ne fonctionne pas.

Je vais gérer ça de mon côté, j'avais qu'à bien utiliser git et GitHub.

Je vais push les derniers commits qui implémentent le REPL et je règlerai ce souci avant de soumettre la PR dès que je pourrais.

Sinon OK pour colorama, je fais ça bientôt.

Je passe en coup de vent pour dire que non : la spec dit bien que toutes les lambdas doivent avoir une contrainte de type (un bloc hastype), justement pour qu’il n’y ait aucune ambiguïté, et qu’on n’ait pas besoin d’inférence de types.

Salut,

Je me demandais comment fonctionne le système de contributeurs sur GitHub. Par exemple sur PyAcid je ne suis pas marqué comme contributeur (il y a que the_new_sky).