Exemple d'implémentation d'un système de traitement LISP simple (version Python)

Cet article est un résumé d'exemples d'implémentation d'un système de traitement LISP simple qui utilise un extrait / modification de la version Python de mon article suivant.

Une implémentation simple de l'évaluateur méta-circulaire, qui est le corps principal du système de traitement LISP, est Exemple d'implémentation primaire (Paul) Exemple de description de Graham's Common Lisp: "McCarthy's Original Lisp") et SICP 4.1 (/sicp/full-text/sicp/book/node76.html) est publié depuis longtemps, c'est donc très simple. Au contraire, l'implémentation de traitement d'entrée / sortie et de liste de type S qui effectue une analyse de phrase / syntaxe nécessite plus de temps et d'efforts pour chaque langage de développement, et je l'ai résumé pour ceux qui sont au seuil.

Puisque les deux articles ci-dessus implémentent le langage C, Ruby et JavaScript en plus de Python, nous pouvons créer le même article pour ces versions linguistiques (par conséquent, le titre est "Version Python". ).

Vue d'ensemble du système de traitement

L'exemple d'exécution est le suivant. En Python2, remplacez ʻinput () par raw_input () `.

>>> s_rep("(car (cdr '(10 20 30)))")
'20'
>>> s_rep(input())
((lambda (x y) (car (cdr x))) '(abc def ghi))
'def'
>>> s_rep("((lambda (f x y l) (f x (f y l))) + '10 '20 '0)")
'30'
>>> s_rep("((lambda (f x y l) (f x (f y l))) cons '10 '20 '())")
'(10 20)'
>>> s_rep("((fix (lambda (fact) (lambda (n) (if (eq? n '0) '1 (* n (fact (- n '1))))))) '10)")
'3628800'
>>> fassoc = "(lambda (assoc) (lambda (k) (lambda (v) (if (eq? v '()) #f (if (eq? k (car (car v))) (car v) ((assoc k) (cdr v)))))))"
>>> s_rep("(((fix" + fassoc + ") 'Orange) '((Apple . 110) (Orange . 210) (Lemmon . 180)))")
'(Orange . 210)'

Le contenu de la mise en œuvre est le suivant.

[LispKit] plutôt que Pure LISP car il existe un correctif qui vous permet de définir des procédures récursives au lieu d'avoir la possibilité de définir des noms. Il peut être proche de Lisp](https://en.wikipedia.org/wiki/Lispkit_Lisp).

Exemple d'implémentation

Traitement des listes

Extrait de Article précédent.

def cons(x, y): return (x, y)
def car(s): return s[0]
def cdr(s): return s[1]
def eq(s1, s2): return s1 == s2
def atom(s): return isinstance(s, str) or eq(s, None) or isinstance(s, bool)

Entrée / sortie de type S

À partir de Article précédent, changez la partie d'analyse de phrase en () et `` identification ( s_lex), et changez la partie de génération d'arbre de syntaxe abstraite. Changé pour générer un arbre de syntaxe par contre cellule avec fonction de traitement de liste tout en prenant en charge la paire de points et le symbole de guillemet (s_syn), et défini la fonction d'entrée d'expression Ss_read` qui les résume.

def s_lex(s):
    for p in "()'": s = s.replace(p, " " + p + " ")
    return s.split()

def s_syn(s):
    def quote(x):
        if len(s) != 0 and s[-1] == "'":
            del s[-1]
            return cons("quote", cons(x, None))
        else: return x
    t = s[-1]
    del s[-1]
    if t == ")":
        r = None
        while s[-1] != "(":
            if s[-1] == ".":
                del s[-1]
                r = cons(s_syn(s), car(r))
            else: r = cons(s_syn(s), r)
        del s[-1]
        return quote(r)
    else: return quote(t)

def s_read(s): return s_syn(s_lex(s))

La section de sortie de type S s_string est nouvellement créée. En interne, une liste vide qui est "Aucun" est définie sur output(), et une valeur booléenne est définie sur output # t`` # f.

def s_strcons(s):
    sa_r = s_string(car(s))
    sd = cdr(s)
    if eq(sd, None):
        return sa_r
    elif atom(sd):
        return sa_r + " . " + sd
    else:
        return sa_r + " " + s_strcons(sd)

def s_string(s):
    if   eq(s, None):  return "()"
    elif eq(s, True):  return "#t"
    elif eq(s, False): return "#f"
    elif atom(s):
        return s
    else:
        return "(" + s_strcons(s) + ")"

Évaluateur de super diffusion

Créez la fonction s_eval en vous référant à SICP 4.1. Pour l'application des fonctions intégrées et des opérateurs pseudo-numériques, reportez-vous à "lis.py" de Peter Norvig et utilisez l'environnement d'origine ʻenv. Mis en œuvre séparément de l'application. Le combinateur de points d'immobilité est une version fermée du combinateur Y [combinateur Z](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF # Z% E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF) est prédéfini dans l'environnement ʻenv.

s_builtins = {
    "cons":   lambda x, y:   cons(x, y),
    "car":    lambda s:      car(s),
    "cdr":    lambda s:      cdr(s),
    "eq?":    lambda s1, s2: eq(s1, s2),
    "pair?":  lambda s:      not atom(s),
    "+":      lambda s1, s2: str(int(int(s1) + int(s2))),
    "-":      lambda s1, s2: str(int(int(s1) - int(s2))),
    "*":      lambda s1, s2: str(int(int(s1) * int(s2))),
    "/":      lambda s1, s2: str(int(int(s1) / int(s2)))
}

def lookup_variable_value(var, env):
    def loop(env):
        def scan(vars, vals):
            if eq(vars, None): return loop(cdr(env))
            elif eq(var, car(vars)): return car(vals)
            else: return scan(cdr(vars), cdr(vals))
        frame = car(env)
        fvar = car(frame)
        fval = cdr(frame)
        return scan(fvar, fval)
    return loop(env)

def s_eval(e, env):
    def sargs(a, env):
        if eq(a, None): return None
        else: return cons(s_eval(car(a), env), sargs(cdr(a), env))
    if atom(e):
        if e in s_builtins: return e
        else: return lookup_variable_value(e, env)
    elif eq(car(e), "quote"):
        return car(cdr(e))
    elif eq(car(e), "if"):
        pred = car(cdr(e))
        texp = car(cdr(cdr(e)))
        fexp = cdr(cdr(cdr(e)))
        if eq(s_eval(pred, env), True): return s_eval(texp, env)
        else: return False if eq(fexp, None) else s_eval(car(fexp), env)
    elif eq(car(e), "lambda"):
        lvars = car(cdr(e))
        lbody = car(cdr(cdr(e)))
        return cons("lambda", cons(lvars, cons(lbody, cons(env, None))))
    else:
        f = s_eval(car(e), env)
        args = sargs(cdr(e), env)
        return s_apply(f, args)

def s_apply(f, args):
    def pargs(al):
        if eq(al, None): return []
        else: return [car(al)] + pargs(cdr(al))
    if atom(f): return s_builtins[f](*pargs(args))
    else:
        lvars = car(cdr(f))
        lbody = car(cdr(cdr(f)))
        lenvs = car(cdr(cdr(cdr(f))))
        env = cons(cons(lvars, args), lenvs)
        return s_eval(lbody, env)

fixproc = s_eval(s_read( \
    "(lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))" \
), None)

s_init_env = cons(cons( \
    cons("fix",   cons("#t", cons("#f",  None))), \
    cons(fixproc, cons(True, cons(False, None)))  \
), None)

REP (no Loop) Définissez s_rep qui est une collection de s_read s_evals_string.

def s_rep(s): return s_string(s_eval(s_read(s), s_init_env))

Remarques

Informations complémentaires sur l'article

Journal des modifications

2020-09-07: Première édition publiée

Recommended Posts

Exemple d'implémentation d'un système de traitement LISP simple (version Python)
Statut de chaque système de traitement Python en 2020
Exemple d'implémentation simple d'un type d'augmentation de données
Divers traitements de Python
Python: Apprentissage en profondeur dans le traitement du langage naturel: Implémentation d'un système de sélection de phrases de réponses
Mise à niveau de python Anaconda
Mesure FPS simple de python
Vérifiez la version OpenSSL de python 2.6
Implémentation Python du filtre à particules
Post-traitement de python (NG)
Implémentation du tri rapide en Python
Une implémentation Python simple de la méthode k-voisinage (k-NN)
Comment écrire un exemple d'implémentation E14 Python en temps réel hors ligne
[Avec une explication simple] Implémentation Scratch d'une machine Boltsman profonde avec Python ②
[Avec une explication simple] Implémentation Scratch d'une machine Boltzmann profonde avec Python ①
[Python] Version Taple du menu déroulant de la préfecture
Implémentation Python du filtre à particules auto-organisateur
Mise en place d'un filtre à particules simple
pyenv-changer la version python de virtualenv
Comment écrire un exemple d'implémentation Python du problème E15 en temps réel hors ligne
Version Ideone> Python: 3.5 (au 29 août 2017)
Implémentation du jeu de vie en Python
Explication et mise en œuvre du perceptron simple
Maîtrisez la recherche linéaire! ~ Version d'implémentation Python ~
Implémentation des notifications de bureau à l'aide de Python
Grammaire de base du système Python3 (dictionnaire)
Implémentation Python de l'arborescence de segments non récursive
Implémentation de Light CNN (Python Keras)
Implémentation du tri original en Python
Implémentation de la méthode Dyxtra par python
Bases du traitement d'images binarisées par Python
À propos de l'environnement virtuel de Python version 3.7
Implémentation d'un système de dialogue utilisant Chainer [seq2seq]
Échelle de gris par matrice-Reinventor of Python image processing-
Exemple d'analyse de squelette tridimensionnelle par Python
[Python] Essayez pydash de la version Python de lodash
Grammaire de base de la série Python3 (chaîne de caractères)
Dessin avec Matrix-Reinventor of Python Image Processing-
L'histoire du traitement A du blackjack (python)
Note de problèmes sur la coexistence du système Python 2/3
Pandas: un exemple très simple de DataFrame.rolling ()
Exemple pratique d'architecture hexagonale en Python
Grammaire de base du système Python3 (notation incluse)
Implémentation Python du modèle Markov caché continu
Exemple de traitement efficace des données avec PANDAS
Filtrage par convolution par matrice-Reinventor of Python image processing-
Essai du parseur d'emacs-org orgparse pour python
Exemple de prise de Python> function> * args comme argument
Pourquoi l'implémentation Python d'ISUCON 5 a utilisé Bottle
Un mémorandum sur l'appel de Python à partir de Common Lisp
Afficher le résultat du traitement de la géométrie en Python
Utilisez OpenSeesPy quel que soit le système d'exploitation ou la version de Python
Écrire une note sur la version python de python virtualenv
Traitement d'image? L'histoire du démarrage de Python pour
Essayez Progate Free Edition [Python I]
Automatiser des tâches simples avec Python Table des matières
Implémentation de l'arbre TRIE avec Python et LOUDS