关于java:用java写lisp-解释器-5-自定义-if-存在的问题

34次阅读

共计 2640 个字符，预计需要花费 7 分钟才能阅读完成。

在上文咱们定义了 if 函数还存在一个问题, 那就是当参数是 atom 或简略的不波及递归的函数时一切正常，如果波及到递归函数就出问题了，这里有一个经典的例子

(define fact (lambda ( n)
  (if (= n 1)
      1
      (* n (fact (- n 1))))))

(fact 5)

而后会呈现 StackOverflowError 的异样，让咱们剖析一下为什么会出现异常呢？
首先咱们先看一下咱们自定义的 if 函数
if

 (define if (lambda (p then_v else_v)
     ((or (and p car) cdr) (cons then_v else_v))))

起因在于 if 函数的 p、then_v、else_v 的这三个入参对应的表达式，作为入参时会在办法被调用时解开（执行取得后果 (getAtom)），那为什么 atom 或不波及递归的函数失常呢？
起因在于 getAtom 这个办法: 在 o 也就是入参是表达式或变量时会执行 eval，而入参是 atom 或 function 则间接返回 o

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(toSubCons(o, exp), env);
    } else {return o;}
}

当执行 fact 函数时，咱们会发现 fact 中 if 函数入参 else_v 对应的表达式 (* n (fact (- n 1))) 会被 getAtom（此时 o 是 else_v 对应的表达式），而 fact 再次被触发 else_v 对应表达式再次被 getAtom（此时 o 还是 else_v 对应的表达式），于是陷入了循环中从而呈现了 StackOverflowError 的异样。

从方才的剖析咱们晓得了 else_v 对应的表达式在 getAtom 办法中执行 eval 导致的问题呈现，那么只有不触发 getAtom eval 即可，这里对应的是 else_v 不被执行，恰好咱们的 lambda 能够做到这点（懒加载提早执行）, 让咱们革新一下 fact 函数

(define fact (lambda ( n)
  (if (= n 1)
      1
     (lambda () (* n (fact (- n 1)))))))

而后执行（fact 5）失去了 120 的后果，一切正常了，（还是通过一个中间层即可解决的问题）然而这样写也太麻烦了吧，咱们能够写一个函数简化 (lambda () ()) 这步操作，于是咱们有了 lazyfun 这个函数

(define lazy-fun (lambda (exp) (lambda () (exp))))

而后咱们给它起个别名持有表达式援用的函数

(define quote lazy-fun)

咱们 fact 函数变成了这样

(define fact (lambda ( n)
  (if (= n 1)
      1
     (quote (* n (fact (- n 1)))))))

执行（fact 5）后又呈现了 StackOverflowError, 奇怪了难道

(define a (lambda () 
    (* n (fact (- n 1)))))
(define quote (lambda (exp) (lambda () (exp))))
(define b (quote (* n (fact (- n 1)))))

a b 不等价吗？从数学上来看是等价的，但从咱们程序上来看他们并不是一样的表达式构造，
首先让咱们看一下 a，在看 a 之前先放上咱们解释器解释 lambda 关键字的源码

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, cdr.parent()+"参数不统一");
        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);
    };
}

接着看 a，a 在下面源码中 cdr 对应的是 (() (* n (fact (- n 1)))）,x 对应的是一个空数组；

而 b 在定义时会先解释 quote，quote cdr 对应的局部是 ((exp) (lambda () (exp))), x 对应的是须要 eval 解释的 (* n (fact (- n 1))) 的一个元素的数组；

问题便是出在了 quote 的 x 这里他和 “ 问题是怎么产生的呢？” 起因是一样的表达式 (* n (fact (- n 1))) 在被解释时陷入了 fact 的循环中了于是呈现了 StackOverflowError。

个别问题到这里就告一段落，但 (lambda () (exp)) 写还是太啰嗦了能不能简略些像 (quote exp) 这样呢？答案是有的

咱们只须要自定义一个内置函数即可

quote

 private static Function<ApplyArgs, Object> quote(Cons cdr, Env env) {return (applyArgs) -> applyArgs.getEval().apply(cdr.carCons(), env);
}

还有一个小问题懒加载提早执行是怎么做到的呢？

答案便是高阶函数，问题高阶函数是怎么做到的呢？

答案是 apply(v, cdr, env)

当 apply 执行时内置的 lambda 函数返回了一个函数 (叫 r 吧)，r 函数做为后果被返回了, 并没有再次被 apply，这个时候因为 r 还是函数不会被 getAtom 解开，直到 r 作为变量或表达式时被 apply(v, cdr, env) 到才会执行，从而将 r 解开，
r 解开的过程 applyArgs.getEval().apply(body, env0) 这行代码会被执行到于是又进入了下一个循环中，直到程序执行完。

又是一个中间层即可解决的问题，如同也能了解函数编程遍及度没有面向对象遍及度高的起因了，太多的递归中产生了过多的心智累赘,apply 和 eval 是一对相互调用的好兄弟，但要记得有退出条件哦，不要陷入有限相互调用的中去从而产生 StackOverflowError。

正文完