Résumé de mon travail / 4ème étape de la feuille de triche. J'ai lu la page Web suivante et j'ai décidé d'écrire le premier interpréteur de 7 lignes (calcul lambda) en Python et dans d'autres langages de programmation. Par conséquent, pour le moment, seules la description Scheme du langage d'origine et la description Python.
(λ x . x) → ((λ x . x)) ((λ x . x) (λ a . a)) → (λ a . a) (((λ f . f) (λ g . g)) (λ a . a)) → ((λ a . a)) (((λ f . (λ x . (f x))) (λ g . g )) (λ a . a)) → ((λ a . a))
Dans cet article, le symbole lambda utilise "/" (au lieu de "λ").
Pour faciliter le portage du travail (?), La structure est divisée en parties suivantes pour chaque langue. Cependant, afin d'éviter la duplication avec des fonctions existantes, ʻeval est le nom de fonction de ʻeval7 et ʻapply est le nom de fonction de ʻapply7.
Choix de «lecture». Il analyse la phrase et la syntaxe des expressions S (parse).
gosh> (read (open-input-string "(hoge hage (hige (foo bar)) baz)"))
(hoge hage (hige (foo bar)) baz)
ʻAssq` est OK.
gosh> (assq 'a '((a 10) (b 20) (c 30)))
(a 10)
Évaluation faisant partie de la formule. Copiez et collez presque la page Web ci-dessus. Il prend l'expression ʻe et l'environnement ʻenv, si l'expression ʻe est une variable, il récupère la valeur correspondante de l'environnement ʻenv et la renvoie, et si l'expression ʻe est une seule expression lambda, c'est l'environnement ʻenv comme valeur. En dehors de cela, il est considéré comme une liste de la fonction «(car e)» et de la valeur «(cadr e)» donnée à la fonction, et chaque fonction / valeur est auto-évaluée en premier (ordre applicatif). Appelez ʻapply` pour appliquer la fonction.
(define (eval7 e env)
(cond ((symbol? e) (cadr (assq e env)))
((eq? (car e) '/) (cons e env))
(else (apply7 (eval7 (car e) env)
(eval7 (cadr e) env)))))
Partie d'application de fonction. Copiez et collez presque la page Web ci-dessus. Reçoit la fonction f et la valeur x, associe la variable de fonction(cadr (voiture f))à la valeur x, et la combine avec la valeur non appliquée restante(cdr f)comme environnement. , Appelez la partie d'évaluation de l'expression ʻeval avec la fonction corps expression (cddr (car f)) `.
Par mesure de précaution pour l'implémentation, le côté droit de la période d'expression lambda d'entrée est automatiquement la partie cdr de la paire de points dans Scheme, donc par exemple, «f» est »((/ a. (/ C. d))). Le (cd dr (voiture f)) au moment de) devient (\ c. D) au lieu de (. (/ C. d)) `.
(define (apply7 f x)
(eval7 (cddr (car f))
(cons (list (cadr (car f)) x)
(cdr f))))
Utilisez display tel quel.
gosh> (display '((/ a . a)))
((/ a . a))#<undef>
gosh> (display (eval7 (read) '()))
(((/ f . (/ x . (f x))) (/ g . g )) (/ a . a))
((/ a . a))#<undef>
Python（Python 3，Python2）
Ici read_from_tokens () pakuri. La gestion des erreurs a été perdue.
def readlist(x):
xl = x.replace('(', ' ( ').replace(')', ' ) ').split()
def ret(ts):
t = ts.pop(0)
if t == '(':
r = []
while ts[0] != ')': r.append(ret(ts))
ts.pop(0)
return tuple(r)
else:
return t
return ret(xl)
>>> readlist('(hoge hage (hige (foo bar)) baz)')
('hoge', 'hage', ('hige', ('foo', 'bar')), 'baz')
Au début, j'ai pensé à utiliser le type dictionnaire, mais cela semblait gênant au moment de l'évaluation λ, donc je l'ai implémenté en supposant le type taple.
def assoc(k, vl):
if not vl: return False
elif vl[0][0] == k: return vl[0]
else: return assoc(k, vl[1:])
>>> assoc('a', (('a', 10), ('b', 20), ('c', 30)))
('a', 10)
Indice grand succès. Schéma (LISP) (voiture x), (cdr x), (cadr x) est x [0] de Python, x [1:], x [1] Classique (généralement le contraire).
def eval7(e, env):
if isinstance(e, str): return assoc(e, env)[1]
elif e[0] == '/': return (e,) + env
else: return apply7(eval7(e[0], env), eval7(e[1], env))
Le deuxième grand succès en abonnements. La raison de cdddr = [3:] ʻau lieu de cddr=[2:]est de supprimer'.'` (voir l'explication de l'implémentation du schéma).
def apply7(f, x): return eval7(f[0][3:][0], ((f[0][1], x),) + f[1:])
L'inverse de l'entrée. C'est vraiment mon propre travail. Le dernier «[: -1]» est très technique.
def writelist(x):
def ret(xs):
r = ('(')
for t in xs:
if isinstance(t, tuple):
r += ret(t)
else:
r = r + t + ' '
r = r[:-1] + ') '
return r
return ret(x)[:-1]
>>> writelist(('a', 'b', ('c', 'd'), (('e', 'f'), ('g', 'h'))))
'(a b (c d) ((e f) (g h)))'
Pour Python3 (utilisez ʻinput () `).
>>> print(writelist(eval7(readlist(input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))
Pour Python2 (utilisez raw_input ()).
>>> print(writelist(eval7(readlist(raw_input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))
Recommended Posts