Summary of my work / 4th stage of cheat sheet. I read the following web page and decided to write the first 7-line interpreter (lambda calculus) in Python and other programming languages. Therefore, for the time being, only the Scheme description of the original language and the Python description.
(λ 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))
In this article, the lambda symbol uses "/" (instead of "λ").
For convenience of porting work (?), The structure is divided into the following parts for each language. However, in order to avoid duplication with existing functions, ʻeval is the function name of ʻeval7 and ʻapply is the function name of ʻapply7.
read choice. It lexically analyzes (parses) S-expressions.
gosh> (read (open-input-string "(hoge hage (hige (foo bar)) baz)"))
(hoge hage (hige (foo bar)) baz)
ʻAssq` is OK.
gosh> (assq 'a '((a 10) (b 20) (c 30)))
(a 10)
Evaluation part of the formula. Almost copy and paste of the above Web page. It takes the expression ʻe and the environment ʻenv, retrieves the corresponding value from the environment ʻenv if the expression ʻe is a variable, and returns it, and if the expression ʻe is a single lambda expression, it takes the environment ʻenv as a value. Other than that, it is regarded as a list of the function (car e) and the value (cadr e) given to the function, and each function / value is self-evaluated first (applicative order). Call ʻapply` to apply the function.
(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)))))
Function application part. Almost copy and paste of the above Web page. Receives the function f and the value x, associates the function variable (cadr (car f)) with the value x, and combines it with the remaining unapplied value(cdr f)as an environment. , Call the expression evaluation part ʻeval together with the function body expression (cddr (car f)) `.
As a precaution for implementation, the right side of the input lambda expression period is automatically the cdr part of the dot pair in Scheme, so for example, f is((/ a. (/ C. d))). The(cd dr (car f)) at the time of) becomes (\ c. D) instead of (. (/ C .d)).
(define (apply7 f x)
(eval7 (cddr (car f))
(cons (list (cadr (car f)) x)
(cdr f))))
Use display as it is.
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）
Here's read_from_tokens () pakuri. Error handling was lost.
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')
At first, I thought about using the dictionary type, but it seemed to be troublesome at the time of λ evaluation, so I implemented it assuming the tuple type.
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)
Subscript great success. Scheme (LISP) (car x), (cdr x), (cadr x) is Python's x [0], x [1:], x [1] Classic (usually the opposite).
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))
The second big success in subscripting. The reason for cdddr =[3:]instead of cddr = [2:] is to remove '.' (See the explanation of Scheme implementation).
def apply7(f, x): return eval7(f[0][3:][0], ((f[0][1], x),) + f[1:])
The reverse of the input. This is truly my own work. The last [: -1] is very technical.
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)))'
For Python3 (use ʻinput ()`).
>>> print(writelist(eval7(readlist(input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))
For Python2 (use raw_input ()).
>>> print(writelist(eval7(readlist(raw_input()), ())))
(((/ f . (/ x . (f x))) (/ a . a )) (/ b . b))
((/ b . b))
Recommended Posts