乐趣区

关于lisp:用java写lisp-解释器-2-扩展无限可能

在上一篇咱们曾经领有了一个简略 lisp 解释器(JLispInter)它反对:

  • 变量:a
  • 绑定:(define a 5)
  • 四则运算:+ – * /
  • 函数(lambda (x) (exp))
  • 调用(g exp)

过后咱们还留下了一些问题:

如解析器还不反对字符串,高阶函数中四则运算 define 等还不能作为入参,不反对匿名函数,分支判断 等

在这篇文章中咱们先疏忽语法树解析器,专一于解释器,花了 1 个多小时的工夫写了一个更加欠缺的解释器,为了不便解说我会将代码一段一段的放出,这样能够让咱们更聚焦一些,在开始前,画了一个表达式语法元素的形成图,这是形象之后(疏忽了如 Characters,Strings,Vectors , Dotted pairs,lists 等)前面如 Dotted pairs 咱们能够通过函数的模式实现。

其中 var expression 是援用类型也就是能够对其进行化简,var 在此处咱们用 symbols 进行代指;number, characters, boolean 是根底类型或原子类型(atom)不能对其进行化简,其就是最简模式;functional 则是介于两者之前,在作为参数时它是一个箱子,在对其进行 apply(调用)时则是关上的箱子,箱子里关上后能够是 atom,也能够是 functional,如果是后者则是高阶函数,也就是能够再次对其进行 apply(调用)直到关上后为 atom 为止。

在前面咱们会看到:“道生一,毕生二,二生三,三生万物。”

准备阶段 咱们还须要对 Env 进行一些革新, 对解析器进行的革新咱们在这里先疏忽掉, Cons 对应的是前文 ExpNode(此处 Cons 是 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;}
}

道生一

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 最开始的时候只有 exp,和 env 两个参数;前面发现有的函数会须要 args, 而后就又定义了一个懒加载的 lazyArgs;至于 eval 函数则是为了当自定义函数应用时可能有一个门(这个门只对自定义函数凋谢),它的作用是:“为了获取一些货色要去应用某些函数或取值,而这些函数或取值能够不须要本人再去实现一遍,间接应用 eval 便可获取。”

此时 JLispInter2 还没有任何内置的函数,不过咱们还是能够只用 atom 应用 JLispInter2.eval 办法。

输出

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

输入

6
3

尽管还没有任何内置函数,但从输入后果来看这是一个好的开始,接下来让咱们为其减少如四则运算函数,而后再看一下它的成果,让咱们开始吧。

毕生二

咱们先定义一个用来治理内置函数的类,咱们就叫它 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();}
}

而后让咱们对 JLispInter2 施加一些魔法,哈哈哈

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));
    }
}

尽管只减少了一行

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

但当初 JLispInter2 曾经反对四则运算了,让咱们测试一下。

输出

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

输入

45
16

从输入后果来看它合乎咱们的预期,这阐明 var (env), expression, function, apply, atom 这些性能曾经能够失常工作了,接下来让咱们为其减少更多的内置函数,让其能够更弱小一些吧。

二生三

既然是内置函数,那用户自定义额函数要怎么办呢?这很简略,咱们只须要减少一个能够返回函数的高阶函数即可,让咱们开始吧。

首先在 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, "参数不统一");
                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);
        }
    }
}

就这么简略,只须要 15 行代码即可,让咱们来好好的看一下它。

 return (applyArgs) -> {...}

通过下面这行代码咱们返回一个函数,这对应下面咱们刚提到过的高阶函数。

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

通过下面这行代码咱们能够取得入参的值。

 Env env0 = Env.newInstance(env);

通过下面这行代码咱们为以后办法在调用时创立一个新的环境。

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

通过下面这行代码咱们为以后办法入参进行了变量绑定。

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

通过下面这行代码咱们让 eval 函数帮咱们解释以后办法体并失去返回值。

让咱们测试一下解释器是否失常工作。

输出

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

输入

10

让咱们再测试一下是否反对高阶函数

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

输入

30
30

成果还是很不错的,接下来让咱们再减少 let cond set! apply 内置函数。

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){
                    // 去掉括號
                    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);
            }
        }

...
}

接下来让咱们将他们注册进去

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()));
        }
...
}

貌似还少点什么?是的 boolean 逻辑

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;
        }
...
}

这里也要记得注册哦。

FunManager

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

持续咱们的测试
为了不便这里不再分两行

// 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
退出移动版