Implementation example of simple LISP processing system (Python version)

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". ).

Overview of processing system

The execution example is as follows. In Python2, replace ʻinput ()withraw_input ()`.

>>> s_rep("(car (cdr '(10 20 30)))")
>>> s_rep(input())
((lambda (x y) (car (cdr x))) '(abc def ghi))
>>> s_rep("((lambda (f x y l) (f x (f y l))) + '10 '20 '0)")
>>> 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)")
>>> 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.

[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](

Implementation example

List processing

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)

S-expression input / output

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
        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
        return "(" + s_strcons(s) + ")"

Super circulation evaluator

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 "" and use the original environment ʻenv. Implemented separately from application. The fixed point combinator is a closure version of the Y combinator [Z combinator]( 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))))
        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))
        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_reads_eval s_string.

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


Supplementary information about the article

Change log

2020-09-07: First edition released

Recommended Posts

Implementation example of simple LISP processing system (Python version)
Status of each Python processing system in 2020
Simple implementation example of one kind of data augmentation
Various processing of Python
Python: Deep learning in natural language processing: Implementation of answer sentence selection system
Version upgrade of python Anaconda
Simple FPS measurement of python
Check OpenSSL version of python 2.6
Python implementation of particle filters
Post processing of python (NG)
Implementation of quicksort in Python
A simple Python implementation of the k-nearest neighbor method (k-NN)
Offline real-time how to write Python implementation example of E14
[With simple explanation] Scratch implementation of deep Boltzmann machine with Python ②
[With simple explanation] Scratch implementation of deep Boltzmann machine with Python ①
[Python] Tuple version of prefecture pull-down
Python implementation of self-organizing particle filters
Implementation of a simple particle filter
pyenv-change the python version of virtualenv
Offline real-time how to write Python implementation example of E15 problem
Ideone> Python version: 3.5 (as of August 29, 2017)
Implementation of life game in Python
Explanation and implementation of simple perceptron
Change the Python version of Homebrew
Master linear search! ~ Python implementation version ~
Implementation of desktop notifications using Python
Basic grammar of Python3 system (dictionary)
Python implementation of non-recursive Segment Tree
Implementation of Light CNN (Python Keras)
Implementation of original sorting in Python
Implementation of Dijkstra's algorithm with python
Basics of binarized image processing with Python
(Java, JavaScript, Python) Comparison of string processing
About the virtual environment of python version 3.7
Implementation of dialogue system using Chainer [seq2seq]
Grayscale by matrix-Reinventor of Python image processing-
Example of 3D skeleton analysis by Python
[Python] Try pydash of the Python version of lodash
Basic grammar of Python3 system (character string)
Drawing with Matrix-Reinventor of Python Image Processing-
The story of blackjack A processing (python)
Memo of troubles about coexistence of Python 2/3 system
Pandas: A very simple example of DataFrame.rolling ()
Practical example of Hexagonal Architecture in Python
Basic grammar of Python3 system (included notation)
Non-recursive implementation of extended Euclidean algorithm (Python)
Python implementation of continuous hidden Markov model
Example of efficient data processing with PANDAS
Matrix Convolution Filtering-Reinventor of Python Image Processing-
A simple example of how to use ArgumentParser
Try the python version of emacs-org parser orgparse
Example of taking Python> function> * args as arguments
Why the Python implementation of ISUCON 5 used Bottle
A memorandum of calling Python from Common Lisp
View the result of geometry processing in Python
Use OpenSeesPy regardless of OS or Python version
A note about the python version of python virtualenv
Image processing? The story of starting Python for
Try the free version of Progate [Python I]
Automating simple tasks with Python Table of contents
Implementation of TRIE tree with Python and LOUDS