homebrew : Le langage de programmation le plus simple au monde

homebrew

Aujourd’hui je vous propose d’écrire votre propre langage de programmation… en quelques minutes. Le langage le plus simple au monde. Par contre, même s’il est minimaliste, il possède plus ou moins toutes les structures qu’un grand langage doit avoir.

L’idée n’est pas la mienne – vous allez voir l’impact de Lisp sur ce langage. 🙂

Proposez un nom dans les commentaires.

A novice was trying to fix a broken Lisp machine by turning the power off and on.
Knight, seeing what the student was doing, spoke sternly: “You cannot fix a machine by just power-cycling it with no understanding of what is going wrong.”
Knight turned the machine off and on.
The machine worked.

(Jargon File / AI Koans)

Structure de base

  1. Je vais écrire ce langage en Python, mais vous allez voir qu’il est ultra-portable.
  2. Afin de simplifier le langage, je vais garder le contenu du programme dans un arbre dès le début. Heureusement pour nous, en Python nous pouvons facilement émuler un arbre avec des listes qui contiennent d’autres listes, etc.
  3. Je vais utiliser la notation préfixée, i.e. au lieu d’écrire (1+2), je vais écrire (+ 1 2) ou en Python ["+", 1, 2] (en forme d’une liste).

Commençons par la fin :

  1. Afin d’exécuter le programme, nous allons appeler la fonction « execute » qui va recevoir des programmes en entrée.
  2. Chaque programme peut être (voir le schéma) :
    1. soit une valeur tel que chiffre ou ligne de caractères (j’ai décidé que le chiffre 42 est un programme valide équivalent à return 42),
    2. soit une liste d’opérations, tels que « + » ou « – » qui peut contenir d’autres « sous-programmes » (et donc des chiffres, lignes de caractères).
  3. Le résultat d’exécution :
    1. d’une valeur ça sera cette même valeur (i.e. execute(3) donne 3 en sortie),
    2. d’une liste d’opérations dépend d’opérateurs de ce programme, par exemple :
      1. l’opérateur « + » donne le résultat d’addition des résultats d’exécution de ces deux opérandes (qui peuvent être des sous-programmes)
      2. etc.

Voici mon résultat pour l’instant:

def execute(prog) :
    if(isinstance(prog,int) or isinstance(prog,float) or isinstance(prog,str)) :
        return prog
    if(isinstance(prog,list)) :
        if(prog[0] == "+") :
            return execute(prog[1]) + execute(prog[2])
        if(prog[0] == "-") :
            return execute(prog[1]) - execute(prog[2])
    raise ValueError('Strange program')

Regardez : je peux déjà lancer execute(["+", 1, 2]) et obtenir 3, mais je peux faire des formules plus complexes aussi, comme execute(["+", 1, ["-", 2, 1]]) et c’est grâce à la récursion.

Autrement dit, nous avons déjà obtenu une squelette pour une calculatrice. Il ne reste qu’ajouter des operateurs dont nous avons besoin. Grace à notre syntaxe, nous n’avons pas besoin de réfléchir, dans quel ordre les opérateurs vont s’exécuter – ça sera toujours l’ordre imposé par l’arbre de programme.

Voici comment nous ajoutons d’autres opérateurs (juste avant la ligne « raise ») :

def execute(prog) :
        ...
        if(prog[0] == "*") :
            return execute(prog[1]) * execute(prog[2])
        if(prog[0] == "/") :
            return execute(prog[1]) / execute(prog[2])
        if(prog[0] == "<") :
            return execute(prog[1]) < execute(prog[2])
        if(prog[0] == ">") :
            return execute(prog[1]) > execute(prog[2])
        if(prog[0] == "=") :
            return execute(prog[1]) == execute(prog[2])
    raise ValueError('Strange program')

If

Nous pouvons ajouter un « if » sous une forme suivante : ["if", condition, résultat-si-vrai, résultat-si-faux] :

  • si dans le code d’un programme on détecte une liste et cette liste se commence par « if », c’est l’opérateur « if »,
  • dans ce cas on interprète le deuxième élément de la liste en espèrent qu’il rendra un booléen,
  • si le booléen est « vrai », on interprète la troisième cellule de la liste et rendons son résultat,
  • sinon – on exécute la quatrième cellule de la liste.

Voici l’implémentation (à mettre avant « raise ») :

def execute(prog) :
        ...
        if(prog[0] == "if") :
            if(execute(prog[1])) :
                return execute(prog[2])
            else :
                return execute(prog[3])
    raise ValueError('Strange program')

Encore une fois, grâce à la récursion, chaque partie de « if » est un sous-programme qui peut contenir plusieurs opérateurs, donc je peux exécuter print(execute(["if", ["=", ["+", 1, 2], 3], "yep", "nope"])) et vérifier que 1+2=3 (notre test imprime « yep »).

Variables

Nous avons déjà obtenu un micro-langage, mais c’est difficile de programmer sans variables. Nous allons les ajouter !

Je propose de garder des variables dans un « environnement », i.e. dans un « dictionnaire » où le nom de chaque variable est une clé. De plus, vu que nous avons l’ambition d’obtenir un vrai langage de programmation avec des variables locales, nous allons permettre une séquence d’environnements embarqués (« scopes », i.e. chaque environnement peut avoir un environnement « parent »).

L’environnement actuel sera stocké dans une variable « vars » :

Ici nous avons deux environnements un – « actuel », l’autre – « précédent ». Vous pouvez voir que nous avons bien les variables « a » et « c » locales à notre environnement (donc les valeurs d’environnement-parent ne sont pas accessibles pour nous au moment d’exécution du code). Par contre, si on aura besoin de la variable « b », elle sera lue depuis l’environnement précédent car une telle variable n’existe pas dans l’environnement actuel.

Vous connaissez ce fonctionnement sous le nom « variable shadowing », i.e. depuis l’environnement (scope) actuel nous pouvons voir les variables de l’environnement précédent tant que nous n’avons pas créé des variables avec le même nom dans l’environnement actuel :

J’ajoute donc deux opérateurs :

  • « get » – pour la lecture de contenu des variables,
  • « set » – pour la modification des valeurs des variables.

« Set » fonctionnera que dans le dernier environnement – pas de modification de variables globales !

Exemples : ["get", "a"] ou ["set", "a", ["-", ["get", "b"], 1]] sont équivalents à ...=a et a=b-1 respectivement.

Partout dans le code on ajoute la variable "vars" pour stocker l’état d’environnement actuel (dès maintenant elle doit être passée dans chaque opérateur) :

def execute(prog,vars) :
    if(isinstance(prog,int) or isinstance(prog,float) or isinstance(prog,str)) :
        return prog
    if(isinstance(prog,list)) :
        if(prog[0] == "+") :
            return execute(prog[1],vars) + execute(prog[2],vars)
        ...
        if(prog[0] == "set") :
            vars[prog[1]] = execute(prog[2],vars)
            return True
        if(prog[0] == "get") :
            if(prog[1] in vars) :
                return vars[prog[1]]
            else :
                return execute(["get",prog[1]],vars["__prevvars"])
    raise ValueError('Strange program')

Maintenant nous pouvons envoyer des variables dans notre programme au moment de lancement en utilisant le dictionnaire « vars » : execute(["+",["get","a"],["get","b"]], {"a":1,"b":2}).

Fonctions

Il nous manque des fonctions… et de la récursion.

Ici il faut aller doucement car il y a plusieurs sujets :

  • possibilité d’exécuter plusieurs commandes, par exemple : fais si, puis fais ça… sans laquelle c’est compliqué d’écrire des programmes plus ou moins complexes ;
  • possibilité de définir des fonctions, i.e. def <nom-de-fonction> <paramètres-de-fonction> <contenu-de-fonction>;
  • possibilité d’appeler des fonctions, i.e. <nom-de-fonction> <valeurs-des-paramètres>.

La partie d’exécution séquentielle – c’est simple – juste à la fin d’interprétateur nous pouvons ajouter un boucle qui viendra exécuter une liste en tant qu’une séquence d’opérations et le dernier block exécuté sera le résultat de la chaine :

        for block in prog :
            s = execute(block,vars)
        return s

Exemple : le programme suivant [ ["set","a",1] , ["+",["get","a"],4] ] retourne 5 (deux opérations consécutives, le résultat de la dernière opération est le résultat d’ensemble).

A noter que ce bout de code s’exécutera si et seulement si on ne trouve aucune autre interprétation à la liste donnée (i.e. on ne décide pas que la liste est un opérateur/fonction).

Pour la définition d’une fonction ce n’est pas compliqué non plus – on peut juste garder le code dans une variable, mais on doit aussi garder la liste des noms des paramètres de cette fonction.

Dans l’exemple suivant nous définissons la fonction « max » avec deux paramètres « a » et « b » qui deviendront des variables locales (au moment d’exécution) et pourront être utilisées dans le code de la fonction :

Voici le bout de code qui implémente « def » :

        if(prog[0] == "def") :
            vars[prog[1]] = {"params":prog[2],"body":prog[3]}
            return True

Maintenant nous pouvons penser exécuter des fonctions.

Voici le syntaxe que je voudrais utiliser : ["nom de fonction", valeur 1, valeur 2, etc]. Pour la fonction max on doit pouvoir utiliser l’expression ["max",1,2].

Note. A ce niveau, les fonctions définies par le développeur seront impossibles à distinguer de nos opérateurs de base car le syntaxe est strictement le même !

L’interprétateur qui exécute des fonctions :

  • cherche une fonction par son nom (en utilisant l’opération « get » que nous avons déjà codé) ;
  • initialise l’environnement ;
  • pour chaque paramètre entrant, il exécute le code lié à chaque variable et importe le résultat dans le nouvel environnement ;
  • exécute le contenu de la fonction en utilisant le nouvel environnement.
        if(isinstance(prog[0],str)) :
            progContents = execute(["get",prog[0]],vars)
            newvars = {}
            newvars["__prevvars"] = vars
            for i in range(len(progContents["params"])) :
                newvars[progContents["params"][i]] = execute(prog[i+1],vars)
            return execute(progContents["body"],newvars)

Maintenant nous pouvons définir et exécuter la fonction « max » (regardez – on passe bien les variables « x » et « y » dans les paramètres « a » et « b ») :

execute([["def",
                "max",
                ["a","b"],
                ["if",
                      [">", 
                           ["get","a"], 
                           ["get","b"]
                      ],
                      ["get","a"],
                      ["get","b"]
                ]
         ],
         ["max",["get","x"],["get","y"]]],
         {"x":1,"y":2})

# > 2

Nous pouvons même calculer la factorielle (grâce à la récursion):

print(execute([["def",
                      "fact",
                      ["n"],
                      ["if",
                            ["=",["get","n"],1],
                            1,
                            ["*",
                                 ["get","n"],
                                 ["fact",["-",["get","n"],1]]
                            ]
                      ]
               ],
               ["fact",["get","a"]]],
               {"a":3}))

# > 6

Voici le code complet :

def execute(prog,vars) :
    if(isinstance(prog,int) or isinstance(prog,float) or isinstance(prog,str)) :
        return prog
    if(isinstance(prog,list)) :
        if(prog[0] == "+") :
            return execute(prog[1],vars) + execute(prog[2],vars)
        if(prog[0] == "-") :
            return execute(prog[1],vars) - execute(prog[2],vars)
        if(prog[0] == "*") :
            return execute(prog[1],vars) * execute(prog[2],vars)
        if(prog[0] == "/") :
            return execute(prog[1],vars) / execute(prog[2],vars)
        if(prog[0] == "<") :
            return execute(prog[1],vars) < execute(prog[2],vars)
        if(prog[0] == ">") :
            return execute(prog[1],vars) > execute(prog[2],vars)
        if(prog[0] == "=") :
            return execute(prog[1],vars) == execute(prog[2],vars)
        if(prog[0] == "if") :
            if(execute(prog[1],vars)) :
                return execute(prog[2],vars)
            else :
                return execute(prog[3],vars)
        if(prog[0] == "set") :
            vars[prog[1]] = execute(prog[2],vars)
            return True
        if(prog[0] == "get") :
            if(prog[1] in vars) :
                return vars[prog[1]]
            else :
                return execute(["get",prog[1]],vars["__prevvars"])
        if(prog[0] == "def") :
            vars[prog[1]] = {"params":prog[2],"body":prog[3]}
            return True
        if(isinstance(prog[0],str)) :
            progContents = execute(["get",prog[0]],vars)
            newvars = {}
            newvars["__prevvars"] = vars
            for i in range(len(progContents["params"])) :
                newvars[progContents["params"][i]] = execute(prog[i+1],vars)
            return execute(progContents["body"],newvars)
        for block in prog :
            s = execute(block,vars)
        return s
    raise ValueError('Strange program')

Vous pouvez ajouter des boucles, des contrôles supplémentaires, autres types de données, mais nous avons déjà un interprétateur « assez complet » en moins de 50 lignes de code.

Note. Vous pouvez faire une remarque que nous utilisons le code Python pour créer la liste avec le programme (i.e. nous n’avons pas fait de parser), donc le langage est incomplet… C’est vrai, mais rien ne m’empêche utiliser un parser de JSON / YAML ou XML pour importer le même arbre sans stocker le code directement en Python.

Petit refactoring

Nous avons déjà remarqué qu’il n’y avait pas de différence entre des opérateurs prédéfinis et des fonctions. Dans ce cas, nous pouvons faire un petit refactoring de notre code – nous allons diviser toutes les fonctions en deux groupes :

  • binaires – implémentées en Python (pourront être « lazy » pour pouvoir exécuter « if » correctement et pour optimiser « or » et « and ») ;
  • définies dans le code – implémentées avec notre langage.

Dans ce cas, nous pouvons « sortir » certains opérateurs dans les variables d’environnement (je me suis permis d’ajouter aussi « lazy & » et « lazy | ») :

def execute(prog,vars) :
    if(isinstance(prog,int) or isinstance(prog,float) or isinstance(prog,str)) :
        return prog
    if(isinstance(prog,list)) :
        if(prog[0] == "set") :
            vars[prog[1]] = execute(prog[2],vars)
            return True
        if(prog[0] == "get") :
            if(prog[1] in vars) :
                return vars[prog[1]]
            else :
                return execute(["get",prog[1]],vars["__prevvars"])
        if(prog[0] == "def") :
            vars[prog[1]] = {"type":"defined","params":prog[2],"body":prog[3]}
            return True
        if(isinstance(prog[0],str)) :
            progContents = execute(["get",prog[0]],vars)
            if(progContents["type"] == "defined") :
                newvars = {}
                newvars["__prevvars"] = vars
                for i in range(len(progContents["params"])) :
                    newvars[progContents["params"][i]] = execute(prog[i+1],vars)
                return execute(progContents["body"],newvars)
            else :
                return progContents["body"](prog,vars) #opérateurs binaires
        for block in prog :
            s = execute(block,vars)
        return s
    raise ValueError('Strange program')

baseEnv={
     "if": {"type":"binary","body":lambda x, vars : execute(x[2],vars) if execute(x[1],vars) else execute(x[3],vars)},
     "+" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)+execute(x[2],vars)},
     "-" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)-execute(x[2],vars)},
     "*" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)*execute(x[2],vars)},
     "/" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)/execute(x[2],vars)},
     "<" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)<execute(x[2],vars)},
     ">" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)>execute(x[2],vars)},
     "=" : {"type":"binary","body":lambda x, vars : execute(x[1],vars)==execute(x[2],vars)},
     "&" : {"type":"binary","body":lambda x, vars : False if not(execute(x[1],vars)) else execute(x[2],vars)},
     "|" : {"type":"binary","body":lambda x, vars : True if execute(x[1],vars) else execute(x[2],vars)}
    }

Nos pouvons lancer notre algorithme de calcul de la factorielle de façon suivante (regardez attentivement la dernière ligne où nous faisons référence à baseEnv) :

print(execute([["def",
                      "fact",
                      ["n"],
                      ["if",
                            ["=",["get","n"],1],
                            1,
                            ["*",
                                 ["get","n"],
                                 ["fact",["-",["get","n"],1]]
                            ]
                      ]
               ],
               ["fact",["get","a"]]],
               {"a":3,"__prevvars":baseEnv}))

# > 6

De même, maintenant nous pouvons implémenter la fonction de notre article précédent (ici – version non-optimisée) :

print(execute([["def",
                      "calc",
                      ["m","n"],
                      ["if",
                            ["|",["=",["get","n"],1],["=",["get","m"],1]],
                            1,
                            ["+",
                                 ["calc",["get","m"],["-",["get","n"],1]],
                                 ["calc",["-",["get","m"],1],["get","n"]]
                            ]
                      ]
               ],
               ["calc",["get","M"],["get","N"]]],{"M":6,"N":4,"__prevvars":baseEnv}))

# > 56

L’effet de bord d’un tel refactoring : maintenant nous pouvons « surcharger » les opérateurs de base, i.e. redéfinir « + » ou « if » si nécessaire.

Réflexions

  1. Il est possible d’écrire le cœur d’un langage de programmation en moins de 30 lignes de code (après refactoring et sans compter les opérateurs « standards » de baseEnv).
  2. Le micro-interprétateur obtenu nous permet de voir en clair les décisions à prendre pour construire un langage de programmation plus ou moins utile :
    1. quand créer les « environnements », i.e. ce que veut dire « variable locale »,
    2. comment faire fonctionner le « set » : doit-il mettre à jour une variable globale ou créer une variable locale,
    3. comment traiter le « binding » entre des variables et des paramètres d’une fonction au moment d’exécution,
    4. comment utiliser le « laziness »,
    5. etc…
  3. Ce n’est pas par hasard que LISP utilise la notation préfixée – cela permet d’analyser le code aussi facilement que les données. 🙂

Bonne santé à vous et à votre code.

Post Scriptum. Higher-order functions, lambdas, currying, etc

Si vous voulez pouvoir exécuter quelque chose ressemblant à l’exemple suivant (i.e. utiliser les lambdas, currying, etc), il faudra apporter quelques ajustements.

[
#une fonction de deux paramètres - juste pour exemple
    ["def", 
           "max",
           ["a","b"],
           ["if",[">",["get","a"],["get","b"]],["get","a"],["get","b"]]
    ],
#fonction pour fixer le deuxième paramètre
    ["def",
           "maxN",
           ["n"],
           ["lambda",["m"],["max",["get","m"],["get","n"]]]],
#que nous pouvons utiliser par la suite pour produire une lambda
    ["set","max5",["maxN",5]],
#et notre lambda peut être appliquée comme n'importe quelle autre fonction
    ["max5",7]
]

# > 7

Il faut ajuster le modèle de mémoire afin que des fonctions puissent « se rappeler » les variables locales des fonctions-parents :

Dans notre exemple (ci-dessus) : si la fonction qui s’exécute actuellement veut lire la variable « a », elle verra la valeur 1 (actuelle), si elle veut lire la variable « c », elle verra la valeur « 42 » car elle a été fixée au moment de sa création, alors que la variable « e » viendra de l’environnement d’exécution (« précèdent »). C’est le seul comportement « par défaut » que je juge logique.

Voici l’aperçu des modifications :

  • l’opérateur « get » : maintenant il peut parcourir l’arbre d’environnements dans l’ordre suivant la priorité des parents.
  • ajoute des définitions des lambdas ;
  • ajoute d’exécutions des lambdas ;
  • encore une règle pour les bloques de code pour permettre l’exécution de lambda (si le premier élément d’une liste est une lambda – on l’exécute en passant le reste comme paramètres) ;
  • création d’environnement pour l’exécution d’une fonction est devenu un peu plus complexe.

Note. Dans le code suivant j’utilise des dictionnaires Python pour « stocker » les lambdas et tous les liens (probablement un class ira mieux, mais je ne veux pas augmenter la taille d’interprétateur). Vous pouvez aussi remarquer que « def » est devenu juste un « sucre syntactique » à « set »+ »lambda ».

def execute(prog,vars) :
    #constante
    if(isinstance(prog,int) or isinstance(prog,float) or isinstance(prog,str)) :
        return prog
    
    #liste... donc programme
    if(isinstance(prog,list)) :

        #opérateur "set" - mettre dans l'environnement actuel
        if(prog[0] == "set") :
            vars[prog[1]] = execute(prog[2],vars)
            return True
            
        #opérateur "get" doit tolérer les erreurs à cause de nombreuses branches
        #dans nos environnements
        if(prog[0] == "get") :
            if(prog[1] in vars) :
                return vars[prog[1]]
            else :
                try :
                    return execute(["get",prog[1]],vars["__prevvars"])
                except KeyError :
                    return execute(["get",prog[1]],vars["__prevvars2"])
        
        #définition de lambda
        if(prog[0] == "lambda") :
            return {"type":"defined","params":prog[1],"body":prog[2],"ownvars":vars}

        #définition de fonction (=lambda + set)
        if(prog[0] == "def") :
            vars[prog[1]] = {"type":"defined","params":prog[2],"body":prog[3],"ownvars":vars}
            return True

        #liste qui se commence par nom d'une fonction ou par une lambda
        if(isinstance(prog[0],str) or isinstance(prog[0],dict)) :
            if(isinstance(prog[0],str)) :
                progContents = execute(["get",prog[0]],vars)
            else :
                progContents = prog[0]
            if(progContents["type"] == "defined") :
                ownvars = {}
                if "ownvars" in progContents :
                    ownvars["__prevvars"] = progContents["ownvars"]
                for i in range(len(progContents["params"])) :
                    ownvars[progContents["params"][i]] = execute(prog[i+1],vars)
                return execute({"type":"defined","ownvars":ownvars,"body":progContents["body"]},vars)
            else :
                return progContents["body"](prog,vars)

        #ce n'est pas un opérateur évident
        #c'est juste un block ?
        s = execute(prog[0],vars)
        if(isinstance(s,dict)) :
            #non - c'est un appel à une fonction lambda
            return execute([*[s], *prog[1:]],vars)
        else :
            #si, juste continue...
            for block in prog[1:] :
                s = execute(block,vars)
            return s

    #dictionnaire = lambda
    if(isinstance(prog,dict)) :
        if(prog["type"] == "defined") :
            newvars = {}
            if "ownvars" in prog :
                newvars["__prevvars"] = prog["ownvars"]
                newvars["__prevvars2"] = vars
            else :
                newvars["__prevvars"] = vars
            return execute(prog["body"],newvars)
        else :
            return progContents["body"](prog,vars)
    raise ValueError('Strange program')

baseEnv={
     "if": {"type":"binary","params":[],"body":lambda x, vars : execute(x[2],vars) if execute(x[1],vars) else execute(x[3],vars)},
     "+" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)+execute(x[2],vars)},
     "-" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)-execute(x[2],vars)},
     "*" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)*execute(x[2],vars)},
     "/" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)/execute(x[2],vars)},
     "<" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)<execute(x[2],vars)},
     ">" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)>execute(x[2],vars)},
     "=" : {"type":"binary","params":[],"body":lambda x, vars : execute(x[1],vars)==execute(x[2],vars)},
     "&" : {"type":"binary","params":[],"body":lambda x, vars : False if not(execute(x[1],vars)) else execute(x[2],vars)},
     "|" : {"type":"binary","params":[],"body":lambda x, vars : True if execute(x[1],vars) else execute(x[2],vars)}
    }

Maintenant le code suivant est devenu valide (ici on cherche l’opérateur « * » qu’on applique comme une lambda) :

[
  ["get","*"],
  2,
  2
]

# > 4

et celui-ci aussi :

[
  ["def","mult",[],["get","*"]], #fonction qui "produira" un opérateur de multiplication
  [["mult"],2,2]                 #lancement de la fonction et de son opérateur
]

# > 4

Il nous ne manquent que des structures de données plus complexes comme des listes et des dictionnaires pour qu’on puisse faire du OOP de même genre que JavaScript…