In the last article, we already have a simple lisp interpreter (JLispInter), which supports:

• Variable: a
• Binding: (define a 5)
• Four operations: + - */
• Function (lambda (x) (exp))
• Call (g exp)

At that time, we also left some questions:

For example, the parser does not support strings, the four operations define in high-order functions cannot be used as input parameters, and anonymous functions and branch judgment are not supported

In this article, we first ignore the syntax tree parser and focus on the interpreter. We spent more than an hour writing a more perfect interpreter. In order to facilitate the explanation, I will release the code paragraph by paragraph, so that we can focus more. Before we start, we draw a composition diagram of expression syntax elements, This is after abstraction (Characters, Strings, vectors, Dotted pairs, lists, etc.) and then Dotted pairs. We can implement it in the form of functions.

var expression is a reference type, that is, it can be simplified. Here, we use symbols to refer to var; Number, characters and Boolean are basic types or atom types, which cannot be simplified. They are the simplest form; Functional is between the two. When it is used as a parameter, it is a box. When it is applied (called), it is an open box. After being opened, it can be atom or functional. If it is the latter, it is a high-order function, that is, it can be applied (called) again until it is atom.

In the back, we will see: "Tao gives birth to one, gives birth to two, two gives birth to three, and three gives birth to all things."

In the preparatory stage, we also need to make some modifications to Env. We ignore the modifications to the parser here. Cons corresponds to the previous ExpNode (where cons is the parent class of ExpNode)

Env

public class Env {

    private final Map<String, Object> env = new HashMap<>();
    private Env parent;

    public static Env newInstance(Env parent) {
        Env env1 = new Env();
        env1.parent = parent;
        return env1;
    }

    public void setEnv(Symbols symbols, Object val) {
       setEnv(symbols.getName(),val);
    }

    public void setEnv(String key, Object val) {
        env.put(key, val);
    }

    public Optional<Object> env(Symbols symbols) {
        String symbolsName = symbols.getName();
        return Optional.ofNullable(env.containsKey(symbolsName) ? env.get(symbolsName) : (parent != null ? parent.env(symbols).orElse(null) : null));
    }

    public boolean contains(Symbols symbols){
        return env.containsKey(symbols.getName());
    }

    public Env parent(){
        return parent;
    }
}

Dao begets One

JLispInter2

@Slf4j
public class JLispInter2 {


    private static final Predicate<Object> IS_EXP = o -> o instanceof Cons;

    private static final Predicate<Object> IS_SYMBOLS = o -> o instanceof Symbols;

    private static final Predicate<Object> IS_FUN = o -> o instanceof Function;

    private static final Predicate<Object> IS_ATOM = o -> o instanceof Number || o instanceof String || o instanceof Boolean;

    private static final BiPredicate<Cons, Object> CAN_APPLY = (exp, v) -> IS_FUN.test(v) && exp.isExp();

    public static Object eval(String exp) {
        Env root = Env.newInstance(null);
        return eval(Parse.parseTree(exp), Env.newInstance(root));
    }

    private static Object eval(Cons exp, Env env) {
        Object car = exp.car();
        Cons cdr = exp.cdr();
        if (IS_EXP.test(car)) {
            Object v = eval(exp.carCons(), env);
            if (CAN_APPLY.test(exp, v)) {
                return apply(v, cdr, env);
            }
            return cdr.isEmpty() ? v : eval(cdr, env);
        } else if (IS_SYMBOLS.test(car)) {
            Object v = env.env(exp.carSymbols()).orElseThrow(() -> new IllegalArgumentException(exp.parent() + ": " + exp.carSymbols() + " not define"));
            if (CAN_APPLY.test(exp, v)) {
                return apply(v, cdr, env);
            }
            return cdr.isEmpty() ? v : eval(cdr, env);
        } else if (IS_ATOM.test(car)) {
            return cdr.isEmpty() ? car : eval(cdr, env);
        } else {
            return cdr.isEmpty() ? car : eval(cdr, env);
        }
    }

    private static Object apply(Object v, Cons cdr, Env env) {
        return ((Function<ApplyArgs, Object>) v).apply(ApplyArgs.of(cdr, env, () -> cdr.data().stream().map(o -> getAtom(o, cdr, env)).toArray(), JLispInter2::eval));
    }

    private static Object getAtom(Object o, Cons exp, Env env) {
        if (IS_EXP.test(o)) {
            return eval((Cons) o, env);
        } else if (IS_SYMBOLS.test(o)) {
            return eval(toCons(o, exp), env);
        } else {
            return o;
        }
    }

    private static Cons toCons(Object obj, Cons parent) {
        return ExpNode.one(parent, obj);
    }

    @Value(staticConstructor = "of")
    public static class ApplyArgs {
        Cons exp;
        Env env;
        Supplier<Object[]> lazyArgs;
        BiFunction<Cons, Env, Object> eval;
    }
}

ApplyArgs initially had only exp and env parameters; Later, it is found that some functions need args, and then a lazy loaded lazyArgs is defined; As for the eval function, there is a door (this door is only open to the user-defined function) when the user-defined function is used. Its function is: "in order to obtain some things, you need to use some functions or values, and these functions or values can be obtained directly by using Eval without implementing them again."

At this time, jlispintern2 does not have any built-in functions, but we can still use jlispintern2 only with atom Eval method.

input

(1 2 3 4 5 6)
(1 2 3)

output

6
3

Although there are no built-in functions yet, from the output results, this is a good start. Next, let's add four operation functions, and then take a look at its effect. Let's start.

One begets Two

Let's first define a class to manage built-in functions. Let's call it FunManager

FunManager

 static  class FunManager{
        private static final Map<String, Function<ApplyArgs, Object>> FUNCTIONAL = new ConcurrentHashMap<>();

        static {
            reg("+", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce(Integer::sum).orElse(null));
            reg("-", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce((a, b) -> a - b).orElse(null));
            reg("*", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce((a, b) -> a * b).orElse(null));
            reg("/", applyArgs -> toIntStream(applyArgs.getLazyArgs()).reduce((a, b) -> a / b).orElse(null));
        }

        private static void reg(String optKey, Function<ApplyArgs, Object> opt) {
            FUNCTIONAL.put(optKey, opt);
        }

        private static Stream<Integer> toIntStream(Supplier<Object[]> supplierObjs) {
            return Stream.of(supplierObjs.get()).map(Object::toString).map(Integer::valueOf).collect(Collectors.toList()).stream();
        }
}

Then let's apply some magic to JLispInter2, hahaha

JLispInter2

public class JLispInter2 {
    public static Object eval(String exp) {
        Env root = Env.newInstance(null);
        FunManager.FUNCTIONAL.forEach(root::setEnv);
        return eval(Parse.parseTree(exp), Env.newInstance(root));
    }
}

Although only one line has been added

 FunManager.FUNCTIONAL.forEach(root::setEnv);

But now jlispintern2 supports four operations. Let's test it.

input

(+ 1 2 3 4 (+ 5 6) (+ 7 8 (+ 9 0)))
(+ 1 2 3 4 (- 9 3))

output

45
16

From the output results, it meets our expectations, which shows that the functions of VaR (Env), expression, function, apply and atom can work normally. Next, let's add more built-in functions to make them more powerful.

Two begets Three

Since it is a built-in function, what should the user-defined amount function do? This is very simple. We just need to add a higher-order function that can return the function. Let's start.

First, add a higher-order function in FunManager

FunManager

static  class FunManager{
     static {
        ...
        reg("lambda", applyArgs -> lambda(applyArgs.getExp(), applyArgs.getEnv()));
        ...
    }

    private static Function<ApplyArgs, Object> lambda(Cons cdr, Env env) {
            return (applyArgs) -> {
                Object[] x = applyArgs.getLazyArgs().get();
                Cons args = cdr.carCons();
                Cons body = cdr.cdr();
                validateTrue(args.data().size() == x.length, "Inconsistent parameters");
                Env env0 = Env.newInstance(env);
                int i = 0;
                for (Object argName : args) {
                    env0.setEnv(((Symbols) argName), x[i]);
                    i++;
                }
                return applyArgs.getEval().apply(body, env0);
            };
    }
    private static void validateTrue(boolean flag, String err) {
        if (!flag) {
            throw new IllegalArgumentException(err);
        }
    }
}

It's that simple. It only needs 15 lines of code. Let's take a good look at it.

 return (applyArgs) -> {...}

Through the above line of code, we return a function, which corresponds to the higher-order function we just mentioned above.

 Object[] x = applyArgs.getLazyArgs().get();

Through the above line of code, we can get the value of the input parameter.

 Env env0 = Env.newInstance(env);

Through the above line of code, we create a new environment for the current method when calling.

 env0.setEnv(((Symbols) argName), x[i]);

Through the above line of code, we bound variables for the input parameters of the current method.

return applyArgs.getEval().apply(body, env0);

Through the above line of code, we let the eval function help us interpret the current method body and get the return value.

Let's test whether the interpreter works properly.

input

((lambda (x) (+ 5 x)) 5)

output

10

Let's test again whether we support higher-order functions

((lambda (x) (+ 5 x)) ((lambda (y) (* y y)) 5))
(((lambda (x) (lambda (o) (o 5 x))) ((lambda (y) (* y y)) 5)) +)

output

30
30

The effect is still very good. Next, let cond set! apply built-in function.

FunManager.let

static  class FunManager{
...
         private static Object let(Cons cdr, Env env, BiFunction<Cons, Env, Object> eval) {
            Object car0 = cdr.car();
            validateTrue(car0 instanceof Cons && cdr.data().size() == 2, "please check" + car0);
            Env env0 = Env.newInstance(env);
            Cons car = cdr.carCons();
            Cons body = cdr.cdr().carCons();
            for (Object con : car) {
                validateTrue(IS_EXP.test(con), "please check" + con);
                Cons item = (Cons) con;
                Symbols var = item.carSymbols();
                validateTrue(!env0.contains(var), "Do not repeat the let " + var);
                env0.setEnv(var, eval.apply(item.cdr(), env));
            }
            return eval.apply(body, env0);
        }
...
}

FunManager.cond

static  class FunManager{
...
        private static Object cond(Cons cdr, Env env, BiFunction<Cons, Env, Object> eval){
            Cons car = cdr.carCons();
            Cons predicateExp = car.carCons();
            Cons body = car.cdr();
            if(isaBoolean(eval.apply(predicateExp, env))){
                return eval.apply(body, env);
            }else{
                Cons elseCdr = cdr.cdr();
                if(elseCdr.data().size()==1){
                    // Remove the brackets
                    while (IS_EXP.test(elseCdr.car())&&elseCdr.data().size()==1){
                        elseCdr = elseCdr.carCons();
                    }
                    validateTrue(IS_SYMBOLS.test(elseCdr.car())&&elseCdr.carSymbols().getName().equals("else"),"cond last item not else key");
                    return  eval.apply(elseCdr.cdr(), env);
                }
                return cond(elseCdr, env, eval);
            }
        }
...
}

FunManager.set!

static  class FunManager{
...
        private static Object set(Cons cdr,Env env, BiFunction<Cons, Env, Object> eval) {
            Symbols var = cdr.carSymbols();
            Object val = eval.apply(cdr.cdr(),env);
            validateTrue(env.env(var).isPresent(), " not definition set! error " + var);
            Env envParent = env;
            while (!envParent.contains(var)) {
                envParent = envParent.parent();
            }
            envParent.setEnv(var, val);
            return null;
        }
...
}

FunManager.apply0

static  class FunManager{
...
        private static Object apply0(Cons cdr, Env env) {
            Object f = cdr.car();
            f = getAtom(f, cdr, env);
            if (IS_FUN.test(f)) {
                return apply(f, cdr.cdr(), env);
            } else {
                throw new IllegalArgumentException("apply " + cdr);
            }
        }

...
}

Next, let's register them

FunManager

static  class FunManager{
...
       static {
            ...
            reg("let", applyArgs -> let(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
            reg("set!", applyArgs -> set(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
            reg("apply", applyArgs -> apply0(applyArgs.getExp(), applyArgs.getEnv()));
            reg("cond", applyArgs -> cond(applyArgs.getExp(), applyArgs.getEnv(), applyArgs.getEval()));
        }
...
}

What seems to be missing? Yes, boolean logic

FunManager.regBooleanFun

static  class FunManager{
...
        private static void regBooleanFun() {
            reg("and", applyArgs -> {
                Object[] ts = applyArgs.getLazyArgs().get();
                return Stream.of(ts).allMatch(FunManager::isaBoolean) ? ts[ts.length - 1] : false;
            });
            reg("or", applyArgs -> Stream.of(applyArgs.getLazyArgs().get()).filter(FunManager::isaBoolean).findFirst().orElse(false));
            reg("not", applyArgs -> {
                Object[] ts = applyArgs.getLazyArgs().get();
                validateTrue(ts.length == 1, applyArgs.getExp() + "not args only one");
                return !isaBoolean(ts[0]);
            });
            reg("<", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x < (Integer) y : x.toString().length() < y.toString().length()));
            reg("<=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x <= (Integer) y : x.toString().length() <= y.toString().length()));
            reg("=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), Object::equals));
            reg("!=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> !x.equals(y)));
            reg(">", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x > (Integer) y : x.toString().length() > y.toString().length()));
            reg(">=", applyArgs -> predicate(applyArgs.getExp(), applyArgs.getLazyArgs(), (x, y) -> (x instanceof Integer && y instanceof Integer) ? (Integer) x >= (Integer) y : x.toString().length() >= y.toString().length()));
        }

        private static Object predicate(Cons exp, Supplier<Object[]> lazyArgs, BiPredicate<Object, Object> predicates) {
            Object[] objs = lazyArgs.get();
            validateTrue(objs.length > 1, exp + " args qty > 1 ");
            Object o = objs[0];
            for (int i = 1; i < objs.length; i++) {
                Object o1 = objs[i];
                boolean b = predicates.test(o, o1);
                if (!b) {
                    return b;
                }
                o = o1;
            }
            return true;
        }
...
}

Also remember to register here.

FunManager

static  class FunManager{
...
       static {
            ...
             regBooleanFun();
        }
...
}

Continue our test
For convenience, there are no more two lines here

// let test
<= (let ((a 5) (b 5) (g (lambda (x y) (+ x y)))) (g a b))
=> 10
// cond test
<= ((lambda (x) (cond ((< 5 x) 1) ((> 5 x) -1) (else 0) )) 6)
=> 1
// let and cond test 
<= (let ((a 5) (g (lambda (x) (cond ((< 5 x) 1) ((> 5 x) -1) (else 0) )))) (g a))
=> 0
// set! test 
<= (let ((a 5) (b 6)) ((set! a 6) (+ a b)))
=> 12
// apply test
<= (let ((a 5) (g (lambda (x) (cond ((< 5 x) 1) ((> 5 x) -1) (else 0) )))) (apply g a))
=> 0