This article is a summary of implementation examples of a simple LISP processing system that uses an excerpt / modification of the Python version of my article below.
A simple implementation of the meta-circular evaluator, which is the main body of the LISP processing system, is Primary implementation example (Paul). Graham's Common Lisp description example: "McCarthy's Original Lisp") and SICP 4.1 /sicp/full-text/sicp/book/node76.html) is very easy because it has been published for a long time. Rather, S-expression input / output and list processing implementation that perform lexical / syntactic analysis require more time and effort for each development language, and I have summarized it for those who are at the threshold.
Since the above two articles implement C language, Ruby, and JavaScript in addition to Python, we may create the same article for these language versions (hence, the title is "Python version". ).
The execution example is as follows. In Python2, replace ʻinput ()withraw_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)'
The implementation contents are as follows.
quote (') is used when using values.quote, ʻif and lambda` can be used as syntax.cons`` car cdr ʻeq? pair?` (Create cons cell internally)+ -`` * `` / (Calculates quoted numbers as numbers)# t (true) # f (false) fix (fixed point combinator)[LispKit] rather than Pure LISP because there is a fix that allows you to define recursive procedures instead of having the ability to define names. It may be close to Lisp](https://en.wikipedia.org/wiki/Lispkit_Lisp).
Excerpt from Previous article.
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)
From Previous article, change the lexical analysis part to () and ' identification (s_lex), and change the abstract syntax tree generation part. Changed to generate a syntax tree by cons cell with a list processing function while supporting dot pairs and quote symbols (s_syn), and defined an S-expression input functions_read that summarizes them.
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))
S-expression output section s_string is newly created. Internally, the empty list that is None is set to output(), and the boolean value is set to 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) + ")"
Create a s_eval function by referring to SICP 4.1. For the application of built-in functions and pseudo-numerical operators, refer to Peter Norvig's "lis.py" and use the original environment ʻenv. Implemented separately from application. The fixed point combinator is a closure version of the Y combinator [Z combinator](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) is preset in the environment ʻ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)
Define s_rep which is a collection of s_read → s_eval → s_string.
def s_rep(s): return s_string(s_eval(s_read(s), s_init_env))
fix as standard equipment, it is secretly called Fix Lisp. Is it not good.2020-09-07: First edition released
Recommended Posts