Acid, le lisp-like de la communauté !

@AlphaZeta Il faut voir qu'un compilateur est un (long) pipeline arbitrairement complexe dont l'analyse lexicale et syntaxique n'est que la toute première étape.

Tant que la syntaxe et la sémantique du langage ne sont pas stables tu es susceptible de changer des choses en profondeur dans le parseur, modifier des noeuds de l'AST, etc. Chaque modification à ce niveau est susceptible de devoir être prise en compte sur la totalité du pipeline.

De ce fait, en prenant le raccourcis d'utiliser Python pour te donner un interpréteur temporaire, tu reduis le pipeline à sa première étape, donc tu peux potentiellement tout changer sans que ça ne prête à conséquence : tout changer, c'est juste modifier le parseur, pas une vingtaine de classes, une demi-douzaine de visitors, une RI, un générateur de code et/ou un interpréteur.

Dans mon ancien boulot, jai bossé sur un compilateur dont le développement avait été ultra-mal planifié au profit du sacro-saint Livrable. Il fallait avoir un interpréteur avant même d'avoir un language design stable. Résultat, tout le code a été changé entièrement au moins 2 ou 3 fois en un an, brique par brique.

Ça m'a dégoûté du projet.

Honnêtement, utiliser l'AST de Python me paraît vraiment plus simple.

Je suis d'accord que c'est plus facile, mais j'aimerais à terme utiliser d'autres technologies, pourquoi pas imaginer un système de bytecode, ou encore une compilation à l'aide de LLVM ? De toute façon on peut implémenter ça sur plusieurs branches, donc on peut utiliser à la fois l'AST de Python et LLVM

J'ai besoin de savoir en quoi elle est incomplète pour compléter ma PR. J'ai cru comprendre qu'il manquait des commentaires. J'ajoute des commentaires constamment (je vais bientôt push avec plein d'ajouts de commentaires dans acid/parser.py)

PLY pour une grammaire LISP-like, c'est un peu overkill. Je pense pas que ça soit nécessaire. Surtout que le parser est déjà implémenté.

J'ai implémenté les commentaires en ligne et en bloc (avec //, /* et */ comme précisé dans les specs de Carnufex), mais je suis pas vraiment satisfait de mon code. C'est là que mon système avec les enums a ses limites. Je veux dire, le code marche, mais il est pas hyper beau je trouve. Si quelqu'un a une solution plus élégante je suis preneur

PS: @the_new_sky: je suis pas pressé que tu merge ma PR, mais peut-être qu'il y a des membres qui souhaiteraient contribuer (ce qui demande que le parser soit implémenté, à moins que quelqu'un ne veuille réécrire un autre parser plus propre).

Si quelqu'un a des questions à poser ou des conseils à me donner à propos de ma PR je veux bien.

Edit: Je me permet de signaler une toute petite erreur dans la description du dépôt GitHub:

Python implemantation of Acid language

Ça serait plutôt "Python implementation of the Acid language"

Aucun problème Alpha Zeta.

J'ai prévu de merger ta Pull Request cette après-midi.

Je vais aussi m'atteler au compilateur en AST Python selon les travaux de Nohar, mais il me manque une spec sur l'AST d'Acid pour aller jusqu'au bout.

PS : Merci pour la petite erreur

Qu'est-ce qui te manque ?

Comment serait représenté l'AST d'Acid dans un document JSON ?

J'avais proposé ça. L'autre option est la représentation en liste imbriquées de Folaefolc. Ma solution est plus verbeuse mais permet de faire un dispatcher très simple grâce à l'attribut type.

Tu veux implémenter la sérialisation/déserialisation en JSON ou tu veux juste faire la traduction en AST Python ? Je peux m'en charger si tu veux (quoique ça serait bien de laisser des trucs à faire aux autres )

Tu vois le dictionnaire dans le post de nohar ? Utilises le module json pour le mettre dans un fichier, et regarde ce que ça donne : voilà le résultat que le parser doit générer. Je suis actuellement en train de mettre le code de nohar dans un module, pour transformer cette représentation en AST python (et y ajouter éventuellement quelques helpers pour charger directement depuis le fichier).

Si vous voulez réutiliser le code que je vous ai montré, c'est plutôt facile :

Si un noeud se construit par MonNoeud(arg="plop", body=[MonAutreNoeud(val="plip")]), l'idée est de représenter cet objet par :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

{
    "type": "MonNoeud",
    "arg": "plop",
    "body": [
        {
             "type": "MonAutreNoeud",
             "val": "plip"
        }
    ]
}

C'est à dire le dictionnaire des kwargs du constructeur auquel tu ajoutes le nom de la classe indexé à la clé "type".

J'ai regardé vite fait pour les conditions et j'ai ce code sur wikipédia

1
2
3
4
5

(defun factorial (n)
  "Calcule la factorielle de l'entier n."
  (if (<= n 1)
      1
    (* n (factorial (- n 1)))))

vu comme le if est implémenté il est simple de le définir comme une simple fonction qui prend un Bool et 2 fonction se qui pourrait faire en Acid

1
2
3
4
5
6

(define if (lambda cond fif felse (
    match cond (
        (True  fif)
        (False felse)
    )
)))

Sinon on peut faire un truc super extensible, mais qui demande un tout petit peu de metaprogramming: on donne à l'attribut type le nom exact du type du nœud, et on implémente une fonction qui retrouve la classe seulement par le nom. Je ne sais pas si c'est une bonne idée, j'ai tendance à abuser des trucs comme ça.

Edit: exemple:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def deserialize(json_data):
    return Program.load(json_data)

class Program:
    ...

    @classmethod
    def load(cls, json_data):
        name_class_mapping = { typ.__name__, typ for typ in Expr.__subclasses__() }
        instrs = []

        for json_instr in json_data['instructions']:
            type_name = json_instr['type']
            typ = name_class_mapping[type_name]
            del json_instr['type']
            instr = typ(**json_instr)
            instrs.append(instr)

        return Program(instrs, json_data.get('path', None))

Edit 2: Question de Python: si je n'utilise pas cls dans une classmethod, je ferai mieux d'utiliser une staticmethod ou y'a pas de différence ?

Edit 3: en fait c'est exactement ce que nohar fait dans ce message, sauf que à la place de prendre les classes du module ast je prends les classes de mon Parser, mais du coup ça sert à rien.

Edit 4: Finalement je pense que représenter l'AST de Acid en JSON c'est mieux que de représenter l'AST de Python en JSON. Du coup on traduirait l'AST Acid en AST Python depuis des méthodes, au lieu de faire directement du singledispatch sur le JSON.

the_new_sky, peux-tu éditer ton message sur l'autre sujet ? En effet, les gens pourraient croire que l'on implémente Acid qu'en Python

D'ailleurs, on a dit qu'on commentait en français ou en anglais, finalement ?

Du coup on traduirait l'AST Acid en AST Python depuis des méthodes, au lieu de faire directement du singledispatch sur le JSON.

Le single dispatch est juste une façon efficace et élégante de traverser un JSON. Tu peux l'utiliser pour des AST Custom : tu as juste à virer le hack sur les paramètres lineno et col_offset dans mon code, et peupler le dictionnaire AST_CLASSES avec tes propres classes au lieu de celles du module standard, et ça marchera out of the box.

Ensuite si tu veux convertir de l'AST Acid vers l'AST Python, plutot que d'utiliser des méthodes, je te conseille de passer par un visitor (cadeau : https://zestedesavoir.com/tutoriels/1226/le-pattern-dispatcher-en-python/ ). L'idée, c'est que les classes d'AST n'aient aucune intelligence : leur vocation est descriptive uniquement. Au lieu d'implémenter N*12 méthodes (pour N classes d'AST et 12 étapes de traitement et d'analyse sémantique), tu n'implémentes et ne maintiens que 12 visitors indépendants.

Crois moi sur parole : manipuler des AST, c'est LE moment où il faut user de toutes les astuces pour écrire le moins de code possible.

Perso j'ai commenté en anglais, autant partir là dessus. Le seul truc en français qu'on fait c'est la documentation pour chaque package, comme ce fichier.

Ok merci pour les conseils.

(PS: J'ai lu ton tutoriel sur le pattern dispatcher, j'ai beaucoup aimé :P)

AlphaZeta, pourquoi tu compliques ?

L'idée est simple :

• on vole honteusement le code de nohar (je vous rassure, je l'ai compris avant de le copier ) ;
• on se débrouille pour que nos parsers génèrent l'AST python sous forme de json (i.e le dictionnaire dans le post de nohar écrit en json) ;
• si on commence à être gêné par cette représentation, on crée un AST plus adapté à Acid, et on crée un visitor qui fait la traduction en AST Python, comme nous l'a conseillé nohar. Mais pour l'instant, et tant que le langage n'est pas stable, on reste sur la première solution.

Maintenant que je l'ai énoncé de la manière la plus claire dont je suis capable, est-ce que tout le monde est d'accord ?

Entendu

J'approuve. Pensez bien à indiquer le pseudo de l'auteur de chaque partie du code. Je vous laisse, je vais merger les pulls request, maintenir le github et le sujet (et le message dans l'autre sujet).

EDIT : merge OK

Désolé j'avais encore une toute petite modif à faire

C'est la première fois que j'utilise vraiment Git et GitHub, je dois réouvrir une pull request ?

Au pire comme j'ai pas grand chose à ajouter, je peux demander à the_new_sky de rajouter les modifs.

J'ai mis à jour à la main, aucun problème.

EDIT : Tout est mis à jour

J'ai commencé mon parser en C++, et je commence par le lexer : j'ai créé un lexer générique qui peut s'utiliser avec un autre langage qu'Acid, mais je n'ai pas encore commencé à rédiger le code propre à Acid. Pour l'instant, je n'ai pas créé de dépôt sur Github, je le ferai dès que j'ai le temps.

En attendant, je poste le code ici si quelqu'un veut l'utiliser. A moi d'utiliser ma magie noire (non, je rigole rien de compliqué là dedans) ! Bref, trève de parlote :

Lexer.hpp :

 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

#include <map>
#include <regex>
#include <functional>

// TODO : WRITE DOC !!!

template<typename TokenTraits>
class Lexer
{
public:
    explicit Lexer(std::istream& is)
    : m_is(is)
    , associations{}
    {   
    }

    Lexer(Lexer const&) = delete;
    Lexer& operator=(Lexer const&) = delete;

    Lexer(Lexer&&) = delete;
    Lexer& operator=(Lexer&&) = delete;

    virtual ~Lexer()
    {
    }

public:
    using Tokens = TokenTraits::Tokens;

    using Token = Tokens;

public:
    Token popToken();

    Token getCurrentToken() const
    {
        return m_currentToken;
    }

public:
    // Todo : find a better name for this.
    std::map<std::regex, Token> associations;

private:
    virtual Token handleSpecialLexem()
    {
    }

private:
    std::istream& m_is;

    Token m_currentToken;
};

Lexer.inl :

 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

// TODO : WRITE DOC !!!

#include "Lexer.hpp"

#include <string>

Lexer::Token Lexer::popToken()
{
    auto popped = getCurrentToken();

    std::string word{};

    if(!(m_is >> word))
    {
        if(is.eof())
        {
            m_currentToken = Tokens::EndOfFile;
        }

        return popped;
    }

    for(auto const& element : associations)
    {
        if(std::regex_match(word, element.first)
        {
            m_currentToken = element.second;

            return popped;
        }
    }

    m_currentToken = handleSpecialLexem();

    return popped;
}

un exemple de TokenTraits :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct TokenTraits
{
    enum class Tokens
    {
        Lambda,
                ...,
        EndOfFile,
        Other,
        Unknown
    }
}

Si vous voulez des explications, n'hésitez pas à demander !

P.S : Avec un peu de chance, peut-être que ce message attirera des amateurs de C++ sur le sujet D'ailleurs, peux-tu ajouter le tag C++ dans le sujet ?

EDIT : nohar a montré de trucs cool en python, il fallait bien que je défende de mon mieux C++

EDIT 2 : J'ai renommé le paramètre template en TokenTraits, car c'est plus une classe de traits qu'une classe de politiques