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". ).
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.
quote (` ``) est utilisé lors de l'utilisation de valeursquote, ʻif et lambda` peuvent être utilisés comme syntaxe.cons`` car`` cdr ʻeq? `` Pair? `(Créer une cellule contre en interne)+ -* / `(calculé en considérant les nombres cités comme des nombres)# t (true) # f (false) fix (combinateur de points d'immobilité)[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).
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)
À 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) + ")"
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_eval → s_string.
def s_rep(s): return s_string(s_eval(s_read(s), s_init_env))
fix comme équipement standard, il est secrètement appelé Fix Lisp. N'est-ce pas bon.2020-09-07: Première édition publiée
Recommended Posts