共计 10072 个字符，预计需要花费 26 分钟才能阅读完成。
在上一篇咱们曾经领有了一个简略 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
正文完
