在上一篇咱们曾经领有了一个简略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
@Slf4jpublic 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)输入
63尽管还没有任何内置函数，但从输入后果来看这是一个好的开始，接下来让咱们为其减少如四则运算函数，而后再看一下它的成果，让咱们开始吧。
毕生二
咱们先定义一个用来治理内置函数的类，咱们就叫它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))输入
4516从输入后果来看它合乎咱们的预期，这阐明 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)) +)输入
3030成果还是很不错的，接下来让咱们再减少 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