Обработка StackOverflow в Java для батута

Question

Я хотел бы реализовать батут в Java, возвращая thunk каждый раз, когда я нажимаю StackOverflowError. Существуют ли какие-либо гарантии в отношении 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

Я попробовал следующие возможности реализации: А) С громом (см. Код CPS ниже) Б) Без гирлянды, как предложено Крисом (см. Код CPS2 ниже) C) С thunks с переполнением стека, замененным проверкой глубины (см. Код CPS3 ниже)

В каждом случае я проверял, является ли 100 000 000 четным числом. Эта проверка продолжалась А) около 2 секунд Б) около 17 секунд В) около 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);
}

}

Answer 2

Это интересный способ подняться в стек.Кажется, что это работает, но, вероятно, медленнее, чем обычный способ реализации этого метода, который заключается в создании исключения, которое перехватывается $BIGNUM, укладывает в стек стек вызовов.