Problème — Un mini-langage et son interprète

1. L'interprète est une boucle qui lit les instructions une à une. Le programme interprété n'est, pour lui, qu'une liste : une donnée.

def executer(programme, variables):
    etat = dict(variables)
    i = 0
    while 0 <= i < len(programme):
        instruction = programme[i]
        operation = instruction[0]
        if operation == "AFFECTER":
            etat[instruction[1]] = instruction[2]
        elif operation == "AJOUTER":
            etat[instruction[1]] += etat[instruction[2]]
        elif operation == "DECREMENTER":
            etat[instruction[1]] -= 1
        elif operation == "SAUTER_SI_NUL":
            if etat[instruction[1]] == 0:
                i = instruction[2]
                continue
        elif operation == "SAUTER":
            i = instruction[1]
            continue
        elif operation == "STOP":
            return etat
        i += 1
    return etat

2. On ajoute n à un accumulateur puis on décrémente n, jusqu'à ce que n soit nul.

SOMME = [("AFFECTER", "s", 0),
         ("SAUTER_SI_NUL", "n", 5),
         ("AJOUTER", "s", "n"),
         ("DECREMENTER", "n"),
         ("SAUTER", 1),
         ("STOP",)]

print(executer(SOMME, {"n": 5}))          # {'n': 0, 's': 15}
print(executer(SOMME, {"n": 100})["s"])   # 5050
print(len(SOMME))                         # 6
print(SOMME[2])                           # ('AJOUTER', 's', 'n')

Les deux dernières lignes soulignent l'essentiel : SOMME est une liste que l'on peut mesurer, indexer, afficher — le programme est une donnée.

3. Un programme Python qui écrit un programme du mini-langage :

def programme_multiplier(k):
    programme = [("AFFECTER", "r", 0)]
    for _ in range(k):
        programme.append(("AJOUTER", "r", "x"))
    programme.append(("STOP",))
    return programme

print(programme_multiplier(3))
# [('AFFECTER', 'r', 0), ('AJOUTER', 'r', 'x'),
#  ('AJOUTER', 'r', 'x'), ('AJOUTER', 'r', 'x'), ('STOP',)]

print(executer(programme_multiplier(3), {"x": 7})["r"])    # 21
print(executer(programme_multiplier(12), {"x": 12})["r"])  # 144

C'est, en miniature, ce que fait un compilateur : produire un programme dans un langage à partir d'une description écrite dans un autre.

4. Ce langage possède un saut inconditionnel, donc des boucles : le programme [("SAUTER", 0)] ne s'arrête jamais. On montre qu'il est Turing-complet, et par conséquent le problème de l'arrêt y est indécidable exactement comme en Python. La démonstration du cours ne mentionne d'ailleurs aucune particularité de Python : elle n'utilise que la possibilité d'écrire un test, une boucle et un appel — ce que ce langage de six instructions permet déjà. Voilà, très concrètement, ce que signifie « la calculabilité ne dépend pas du langage ».