loading...

Write lisp in python

mak12776 profile image Mohammad Amin Khakzadan Updated on ・2 min read

I recently thought about how I can merge lisp programming language and python, and tried to write a lisp syntax like compiler in python. Some thing that can convert the following lisp code:

(repeat 2 (write-ln (+ 10 20)))

to this tree:

word: "repeat"
    int: 2
    word: "write-ln"
        symbol: +
            int: 10
            int: 20

And then write an executor for executing tree.

But I figured out that I don't need to write a lisp syntax parser. Instead I can use python builtins types directly.

for example:

('repeat', ('print', ('add', 10, 20)))

And then the result of my thoughts was that I wrote this simple python builtins types compiler. (pbtc for shorthand)

#!/usr/bin/python3

# filename: main.py

import itertools
import sys

def add(*args):
    result = args[0] if len(args) != 0 else None
    for arg in args[1:]:
        result += arg
    return result

def sub(*args):
    result = args[0] if len(args) != 0 else None
    for arg in args[1:]:
        result -= arg
    return result

def mul(*args):
    result = args[0] if len(args) != 0 else None
    for arg in args[1:]:
        result *= arg
    return result

def div(*args):
    result = args[0] if len(args) != 0 else None
    for arg in args[1:]:
        result /= arg
    return result

def true_div(*args):
    result = args[0] if len(args) != 0 else None
    for arg in args[1:]:
        result //= arg
    return result

def join(sep, args):
    return sep.join(args)

tuple_compilers = {
    'add': add,
    'sub': sub,
    'mul': mul,
    'div': div,
    'tdiv': true_div,
    'print': lambda *args: print(*args),

    'join': join,
    'repeat': itertools.repeat,
}

def compile_tuple(tree, memory, compile):
    if len(tree) == 0:
        raise ValueError('invalid tuple length: {}'.format(len(tree)))
    if not isinstance(tree[0], str):
        raise ValueError('invalid tuple instruction: {}'.format(tree[0]))
    if tree[0] not in tuple_compilers:
        raise ValueError('unknown tuple instruction: {}'.format(tree[0]))
    args = []
    for node in tree[1:]:
        args.append(compile(node, memory))
    return tuple_compilers[tree[0]](*args)

compilers = {
    tuple: compile_tuple,
    (list, dict, str, int, float, bytes): 
        lambda tree, memory, compile: tree,
}

def compile_tree(tree, compilers, memory = None):
    self = lambda tree, memory: compile_tree(tree, compilers, memory)
    for _type, compile in compilers.items():
        if isinstance(tree, _type):
            return compile(tree, memory, self)
    raise TypeError(type(tree).__name__)

with open(sys.argv[1]) as infile:
    globals_dict = {}
    exec('grammar = ' + infile.read())

compile_tree(grammar, compilers)

it's not safe, it's slow, but works.

testing:


# filename: lispy

('print', 
    ('join', ' ', ('repeat', ('join', ' ', ['hi', 'bye']), 10))
    )

$./main.py lispy:

hi bye hi bye hi bye hi bye hi bye hi bye hi bye hi bye hi bye hi bye

It's fun...

Maybe later, I wrote a more complete version of this and publish it somewhere, as open source.

Posted on by:

Discussion

markdown guide
 

Convert the strings into bytes. For example:

ADD = b'a'
MUL = b'b'

Make use of cache (using lru_cache or similar). Use the object sharing mechanism for tuples. The way golang uses slices. Make everything immutable, hashable thus cacheable. And u have a faster runtime.

 

Are you aware of Hy, that is exactly a lisp dialect of Python?