乐趣区

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

在上文咱们定义了 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。

退出移动版