boot.l

(set 'list (lambda args args))

(set 'setq
     (macro (name value)
            (list 'set (list 'quote name) value)))

(setq defun
      (macro (name args . body)
        (list 'setq name (cons 'lambda (cons args body)))))

(setq defmacro
      (macro (name args . body)
        (list 'setq name (cons 'macro (cons args body)))))

(defun caar (x) (car (car x)))
(defun cadr (x) (car (cdr x)))
(defun cdar (x) (cdr (car x)))
(defun cddr (x) (cdr (cdr x)))

(defun read (prompt) (parse (read-raw prompt)))

(defun repl ()
  (print (format (eval (cons 'progn (read ">>> ")))))
  (repl))

tinylisp.py

import ast
import collections
import enum
import functools
import itertools
import string


class Tag(enum.Enum):
    LEFT = enum.auto()
    RIGHT = enum.auto()
    DOT = enum.auto()
    QUOTE = enum.auto()
    LITERAL = enum.auto()

Token = collections.namedtuple('Token', ['tag', 'value'])
Symbol = collections.namedtuple('Symbol', ['name'])
Cons = collections.namedtuple('Cons', ['car', 'cdr'])

class Peekable:
    def __init__(self, it):
        self._it, = itertools.tee(it, 1)
    def __iter__(self):
        return self._it
    def __next__(self):
        return next(self._it)
    def peek(self, default=None):
        try:
            return next(self._it.__copy__())
        except StopIteration:
            return default
    @classmethod
    def wrap(cls, f):
        def inner(*args, **kwargs):
            return cls(f(*args, **kwargs))
        return inner

@Peekable.wrap
def lex(s):
    gather = ''
    comment = False
    instring = ''
    escape = False
    def tokenize():
        nonlocal gather
        try:
            t = Token(Tag.LITERAL, ast.literal_eval(gather))
        except (SyntaxError, ValueError):
            t = Token(Tag.LITERAL, Symbol(gather))
        gather = ''
        return t
    for c in s:
        if comment:
            if c in '\n':
                comment = False
            continue
        elif c in ';':
            comment = True
        elif instring:
            gather += c
            if not escape and c in instring:
                instring = ''
                yield tokenize()
            if not escape and c == '\\':
                escape = True
            elif escape:
                escape = False
        elif c in '"':
            if gather:
                yield tokenize()
            gather += c
            instring = c
        elif c in string.whitespace:
            if gather:
                yield tokenize()
        elif c in '(.)\'':
            if gather:
                yield tokenize()
            tag = {
                '(': Tag.LEFT,
                ')': Tag.RIGHT,
                '.': Tag.DOT,
                '\'': Tag.QUOTE,
            }[c]
            yield Token(tag, None)
        else:
            gather += c
    if gather:
        yield tokenize()

class ParseError(Exception):
    def __init__(self, msg, tok):
        if tok:
            super().__init__(msg + ': {}'.format(tok.tag.name))
        else:
            super().__init__(msg)
        self.tok = tok

def expect(toks, tag):
    try:
        n = next(toks)
        if not n.tag == tag:
            raise ParseError('unexpected token', n)
    except StopIteration:
        raise ParseError('unexpected EOF', None)

def parse_list(toks):
    result = None
    tok = toks.peek()
    if tok and tok.tag == Tag.RIGHT:
        next(toks)
        return None
    a = parse_one(toks)
    tok = toks.peek()
    if tok and tok.tag == Tag.DOT:
        next(toks)
        b = parse_one(toks)
        expect(toks, Tag.RIGHT)
    else:
        b = parse_list(toks)
    return Cons(a, b)

def parse_one(toks):
    tok = next(toks)
    if tok.tag == Tag.LEFT:
        return parse_list(toks)
    elif tok.tag == Tag.QUOTE:
        return Cons(Symbol('quote'), Cons(parse_one(toks), None))
    elif tok.tag == Tag.LITERAL:
        return tok.value
    else:
        raise ParseError('unexpected token', tok)

def parse(toks):
    try:
        while True:
            yield parse_one(toks)
    except StopIteration:
        return

def list_to_expr(l, r=None):
    l = iter(l)
    try:
        a = next(l)
    except StopIteration:
        return r
    return Cons(a, list_to_expr(l, r))

def expr_to_list(sexp):
    if sexp is None:
        return [], None
    elif isinstance(sexp, Cons):
        l, r = expr_to_list(sexp.cdr)
        return [sexp.car] + l, r
    else:
        return [], sexp

def expr_format(sexp):
    if sexp is None:
        return '()'
    l, r = expr_to_list(sexp)
    if l:
        if r:
            return '(' + ' '.join(expr_format(s) for s in l) + ' . ' + expr_format(r) + ')'
        else:
            return '(' + ' '.join(expr_format(s) for s in l) + ')'
    elif isinstance(sexp, Symbol):
        return sexp.name
    else:
        return repr(r)

class EvaluationError(Exception):
    pass

class Callable:
    def __init__(self, f):
        self.f = f

class Macro(Callable):
    def evaluate(self, env, args):
        l, r = expr_to_list(args)
        if r is not None:
            raise EvaluationError('unexpected cdr in macro args')
        return self.f(env, *l)

class Function(Callable):
    def evaluate(self, env, args):
        l, r = expr_to_list(args)
        l = [expr_eval(env, x) for x in l]
        if r is not None:
            raise EvaluationError('unexpected cdr in function args')
        return self.f(env, *l)

class Lambda(Callable):
    def __init__(self, macro=False):
        self.macro = macro
    def evaluate(self, env, args):
        l, r = expr_to_list(args)
        if r is not None:
            raise EvaluationError('unexpected cdr in lambda def')
        argnames, *body = l
        if isinstance(argnames, Cons):
            argnames, r = expr_to_list(argnames)
        else:
            r = argnames
            argnames = []
        def inner(innerenv, *innerargs):
            if r is not None:
                if not len(innerargs) >= len(argnames):
                    raise EvaluationError('incorrect arguments to lambda')
            else:
                if not len(innerargs) == len(argnames):
                    raise EvaluationError('incorrect arguments to lambda')
            newenv = innerenv.new_child()
            for n, v in zip(argnames, innerargs):
                newenv[n.name] = v
            rest = innerargs[len(argnames):]
            if r is not None:
                newenv[r.name] = list_to_expr(rest)
            ret = exprs_eval(newenv, body)
            if self.macro:
                ret = expr_eval(innerenv, ret)
            return ret
        if self.macro:
            return Macro(inner)
        else:
            return Function(inner)

class Environment(collections.ChainMap):
    def set(self, k, v):
        for m in self.maps:
            if k in m:
                m[k] = v
                break
        else:
            self.maps[0][k] = v
    
environment = Environment({
    'quote': Macro(lambda e, a: a),
    'set': Macro(lambda e, n, v: e.set(expr_eval(e, n).name, expr_eval(e, v))),
    'lambda': Lambda(),
    'macro': Lambda(macro=True),
    'progn': Macro(lambda e, *args: exprs_eval(e, args)),

    'read-raw': Function(lambda e, p: input(p)),
    'parse': Function(lambda e, a: list_to_expr(parse(lex(a)))),
    'eval': Function(lambda e, *args: exprs_eval(e, args)),
    'format': Function(lambda e, a: expr_format(a)),
    'print': Function(lambda e, a: print(a)),

    'car': Function(lambda e, a: a.car),
    'cdr': Function(lambda e, a: a.cdr),
    'cons': Function(lambda e, a, b: Cons(a, b)),

    '+': Function(lambda e, *a: sum(a)),
    '*': Function(lambda e, *p: functools.reduce(lambda a, b: a * b, p, 1)),
    '-': Function(lambda e, a, b: a - b),
    '/': Function(lambda e, a, b: a // b),
})

def exprs_eval(env, sexps):
    if isinstance(sexps, Cons):
        l, r = expr_to_list(sexps)
        if r is not None:
            raise EvaluationError('unexpected cdr in program body')
    else:
        l = sexps
    ret = None
    for expr in l:
        ret = expr_eval(env, expr)
    return ret

def expr_eval(env, sexp):
    if isinstance(sexp, Cons):
        head = expr_eval(env, sexp.car)
        if isinstance(head, Callable):
            return head.evaluate(env, sexp.cdr)
        raise EvaluationError('not callable: {}'.format(expr_format(sexp.car)))
    else:
        if isinstance(sexp, Symbol):
            try:
                return env[sexp.name]
            except KeyError:
                raise EvaluationError('undefined symbol: {!r}'.format(sexp.name))
        return sexp

if __name__ == '__main__':
    import readline

    with open('boot.l') as f:
        boot = f.read()
        for v in parse(lex(boot)):
            expr_eval(environment, v)

    while True:
        try:
            expr_eval(environment, Cons(Symbol('repl'), None))
        except Exception as e:
            print(e)