java - 在 Java 中为 Trampoline 处理 StackOverflow

Question

我想通过在遇到 StackOverflowError 时返回一个 thunk 来在 java 中实现一个蹦床。关于 StackOverflowError 是否有任何保证，例如，如果我在 StackOverflowError 之后做的唯一事情是在堆上创建对象并从函数返回，我会没事的吗？

如果上面的内容听起来含糊不清，我已经添加了一些代码，以尾递归方式在连续传递样式中计算偶数/奇数，每当堆栈溢出时返回延迟的 thunk。代码在我的机器上运行，但 Java 是否保证它始终运行？

public class CPS {
public static class Thunk {
    final Object r;
    final Continuation c;
    final boolean isDelayed;
    public Object force() {
        Thunk t = this;
        while (t.isDelayed)
            t = t.compute();
        return t.r;
    }
    public Thunk compute() {
        return this;
    }
    public Thunk(Object answer) {
        isDelayed = false;
        r = answer;
        c = null;
    }
    public Thunk(Object intermediate, Continuation cont) {
        r = intermediate;
        c = cont;
        isDelayed = true;
    }
}

public static class Continuation {
    public Thunk apply(Object result) {
        return new Thunk(result);
    }
}

public static Thunk even(final int n, final Continuation c) {
    try {
        if (n == 0) return c.apply(true);
        else return odd(n-1, c);
    } catch (StackOverflowError x) {
        return new Thunk(n, c) {
            public Thunk compute() {
                return even(((Integer)n).intValue(), c);
            }
        };
    }
}

public static Thunk odd(final int n, final Continuation c) {
    try {
        if (n == 0) return c.apply(false);
        else return even(n-1, c);
    } catch (StackOverflowError x) {
        return new Thunk(n, c) {
            public Thunk compute() {
                return odd(((Integer)n).intValue(), c);
            }
        };
    }
}

public static void main(String args[]) {
    System.out.println(even(100001, new Continuation()).force());
}

}

Answer 1

我尝试了以下实现可能性:A) 有 thunks(见下面的代码 CPS)B) 没有 chris 建议的 thunks(见下面的代码 CPS2)C) 用深度检查替换堆栈溢出的 thunk(参见下面的代码 CPS3)

在每种情况下，我都会检查 100,000,000 是否为偶数。这个检查持续了A) 大约 2 秒B) 大约 17 秒C) 大约 0.2 秒

因此，从一长串函数返回比抛出展开该链的异常更快。此外，与其等待堆栈溢出，不如只记录递归深度并在深度 1000 处展开要快得多。

CPS 代码:

public class CPS {

public static class Thunk {
    final Object r;
    final boolean isDelayed;
    public Object force() {
        Thunk t = this;
        while (t.isDelayed)
            t = t.compute();
        return t.r;
    }
    public Thunk compute() {
        return this;
    }
    public Thunk(Object answer) {
        isDelayed = false;
        r = answer;
    }
    public Thunk() {
        isDelayed = true;
        r = null;
    }
}

public static class Continuation {
    public Thunk apply(Object result) {
        return new Thunk(result);
    }
}

public static Thunk even(final int n, final Continuation c) {
    try {
        if (n == 0) return c.apply(true);
        else return odd(n-1, c);
    } catch (StackOverflowError x) {
        return new Thunk() {
            public Thunk compute() {
                return even(n, c);
            }
        };
    }
}

public static Thunk odd(final int n, final Continuation c) {
    try {
        if (n == 0) return c.apply(false);
        else return even(n-1, c);
    } catch (StackOverflowError x) {
        return new Thunk() {
            public Thunk compute() {
                return odd(n, c);
            }
        };
    }
}


public static void main(String args[]) {
    long time1 = System.currentTimeMillis();
    Object b =  even(100000000, new Continuation()).force();
    long time2 = System.currentTimeMillis();
    System.out.println("time = "+(time2-time1)+", result = "+b);
}

}

CPS2 代码:

public class CPS2 {

public abstract static class Unwind extends RuntimeException {
    public abstract Object compute();
    public Object force() {
        Unwind w = this;
        do {
            try {
                return w.compute();
            } catch (Unwind unwind) {
                w = unwind;
            }
        } while (true);
    }
}

public static class Continuation {
    public Object apply(Object result) {
        return result;
    }
}

public static Object even(final int n, final Continuation c) {
    try {
        if (n == 0) return c.apply(true);
        else return odd(n-1, c);
    } catch (StackOverflowError x) {
        throw new Unwind()  {
            public Object compute() {
                return even(n, c);
            }
        };
    }
}

public static Object odd(final int n, final Continuation c) {
    try {
        if (n == 0) return c.apply(false);
        else return even(n-1, c);
    } catch (StackOverflowError x) {
        return new Unwind() {
            public Object compute() {
                return odd(n, c);
            }
        };
    }
}


public static void main(String args[]) {
    long time1 = System.currentTimeMillis();
    Unwind w = new Unwind() {
        public Object compute() {
            return even(100000000, new Continuation());
        }
    };
    Object b = w.force();
    long time2 = System.currentTimeMillis();
    System.out.println("time = "+(time2-time1)+", result = "+b);
}

}

CPS3 代码:

public class CPS3 {

public static class Thunk {
    final Object r;
    final boolean isDelayed;
    public Object force() {
        Thunk t = this;
        while (t.isDelayed)
            t = t.compute();
        return t.r;
    }
    public Thunk compute() {
        return this;
    }
    public Thunk(Object answer) {
        isDelayed = false;
        r = answer;
    }
    public Thunk() {
        isDelayed = true;
        r = null;
    }
}

public static class Continuation {
    public Thunk apply(Object result) {
        return new Thunk(result);
    }
}

public static Thunk even(final int n, final Continuation c, final int depth) {
    if (depth >= 1000) {
        return new Thunk() {
            public Thunk compute() {
                return even(n, c, 0);
            }
        };
    }
    if (n == 0) return c.apply(true);
    else return odd(n-1, c, depth+1);
}

public static Thunk odd(final int n, final Continuation c, final int depth) {
    if (depth >= 1000) {
        return new Thunk() {
            public Thunk compute() {
                return odd(n, c, 0);
            }
        };
    }
    if (n == 0) return c.apply(false);
    else return even(n-1, c, depth+1);
}


public static void main(String args[]) {
    long time1 = System.currentTimeMillis();
    Object b =  even(100000000, new Continuation(), 0).force();
    long time2 = System.currentTimeMillis();
    System.out.println("time = "+(time2-time1)+", result = "+b);
}

}