Write lisp interpreter in java (5 problems with custom if)

As we have defined the if function above, there is still a problem. That is, when the parameter is atom or a simple function that does not involve recursion, everything is normal. If the recursion function is involved, there will be a problem. Here is a classic example

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

Then the StackOverflowError exception will appear. Let's analyze why the exception occurs?
First, let's take a look at our custom if function

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

How did the problem arise?

The reason lies in the p and then of the if function_ v, else_ The expressions corresponding to the three input parameters of V, when used as input parameters, will be untied when the method is called (execute to get the result (getAtom)), so why is atom or functions that do not involve recursion normal?
The reason is that the getAtom method: eval will be executed when the input parameter is an expression or variable, while the input parameter is atom or function, and o will be returned directly

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;

When executing the fact function, we will find that the if function in the fact takes the parameter else_ The expression corresponding to V (* n (fact (- n 1))) will be getAtom (at this time, O is the expression corresponding to else_v), and the fact will be triggered else again_ The expression corresponding to V is again by getAtom (at this time o is also the expression corresponding to else_v), so it falls into a loop, resulting in the exception of StackOverflowError.

How to solve it

From the analysis just now, we know else_ If the expression corresponding to V causes problems by executing eval in the getAtom method, as long as getAtom eval is not triggered, the corresponding expression here is else_v is not executed, which is exactly what our lambda can do (lazy loading and delayed execution). Let's modify the fact function

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

Then we execute (fact 5) and get the result of 120. Everything is normal. (it can still be solved through an intermediate layer). However, it is too troublesome to write this. We can write a function to simplify the operation (lambda () ()), so we have the function lazyfun

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

Then we give it an alias to hold the function referenced by the expression

(define quote lazy-fun)

Our fact function becomes like this

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

After executing (fact 5), StackOverflowError appears again. Is it strange

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

Are a and B not equivalent? Mathematically, they are equivalent, but from our program point of view, they are not the same expression structure,
First, let's take a look at a. before looking at a, put our interpreter to explain the source code of lambda keyword

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()+"Inconsistent parameters");
        Env env0 = Env.newInstance(env);
        int i = 0;
        for (Object argName : args) {
            env0.setEnv(((Symbols) argName), x[i]);
        return applyArgs.getEval().apply(body, env0);

Then look at a. in the above source code, cdr corresponds to (() (* n (fact (- n 1))), and x corresponds to an empty array;

b will explain quote first when defining. The corresponding part of quote cdr is ((EXP) (lambda() (EXP)), and X corresponds to an array of elements (* n (fact (- n 1))) that need to be interpreted by eval;

The problem lies in the x of quote. He and "how did the problem arise?" The reason is that the same expression (* n (fact (- n 1))) falls into the loop of fact when interpreted, so StackOverflowError appears.

The general question will come to an end here, but (lambda () (exp)) is still too verbose. Can it be simpler like (quote exp)? The answer is yes

We only need to customize a built-in function


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

There is also a small problem. How does lazy loading delay execution do?

The answer is higher-order function. How does higher-order function do it?

The answer is apply(v, cdr, env)

When the built-in function CDR or applv is returned, it will not be untied as a result of the function CDR (applv) until it is executed as a function of apply (applr) again,
r unlock the process applyargs getEval(). The line "apply (body, env0)" will be executed until the next loop is executed.


It is another problem that can be solved by the middle layer. It seems that we can understand the reason why the popularity of functional programming is not as high as that of object-oriented programming. Too much recursion produces too much mental burden. apply and eval are good brothers who call each other, but remember to have exit conditions. Don't fall into infinite mutual calls, resulting in StackOverflowError.

Keywords: Java interceptor lisp

Added by StripedTiger on Sat, 12 Feb 2022 04:42:40 +0200