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

Я хотел бы реализовать батут в 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());
}

}

Ответ 1

Я попробовал следующие возможности реализации: A) С thunks (см. Код CPS ниже) B) Без трюков, предложенных chris (см. Код CPS2 ниже) C) С помощью thunks с переполнением стека заменяется проверкой глубины (см. Код 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);
}

}

Ответ 2

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