Crazy python

[amarao]

Функция выглядит как вычислимая примитивно-рекурсивная, но на самом деле невычислимая общерекурсивная!

Доказательство

def foo(i):
    if i < 0 or i > 10:
        return i
    try:
        print(f"{i} - 1")
        return foo(i-1)
    finally:
        print(f"{i} + 1")
        return foo(i+1)

print(foo(5))

На самом деле эта функция - чистое UB в питоне. После долгих лет рассказа о том, что в питоне нет UB.

Вот более интересный генератор последовательностей на той же базе.

def foo(i):
    if i < 0 or i > 10:
        return i
    print(i, end='', sep='')
    try:
        return foo(i-1)
    finally:
        return foo(i+1)

print(foo(5))

Чем не генератор случайных чисел?

Comments

[juan_gandhi]

What's ub?

[amarao]

undefined behavior. Вещь, которая преследует низкоуровневые языки типа С, С++, Rust (Swift и т.д.).

[yurikhan]

Чё это UB? Language Reference § 8.4 The try statement:

The return value of a function is determined by the last return statement executed. Since the finally clause always executes, a return statement executed in the finally clause will always be the last one executed[.]

Банальная нетерминированная взаимная рекурсия между foo(1) и foo(0), с коротким заходом в foo(-1) на каждом круге.

[amarao]

Но при этом, если я его поменяю на

def foo(i):
    if i < 1 or i > 8:
        return i
    print(i, end='', sep='')
    foo(i-1)
    return foo(i+1)

То последовательность полностью меняется, превращаясь в 54321212121212121212121212121212121212121212121212...

Более того, если сделать вот так:

def foo(i):
    if i < 1 or i > 8:
        return i
    print(i, end='', sep='')
    try:
        foo(i-1)
    finally:
        return foo(i+1)

То она меняется опять! Хотя, формально, codeflow никак не поменян.

[yurikhan]

Ну кек бы условие «базы рекурсии» поменялось — было < 0, стало < 1. Теперь такая же нетерминированная рекурсия между foo(2) и foo(1) с заходом в foo(0) (которого не видно, потому что он возвращает 0 без print’а).

[amarao]

Нет, дело не в лимитах. try/finally прячет except Exception: pass. Что, в свою очередь, означает, что вывод зависит от глубины стека на котором случился exception, что определяет последовательность -1 и +1.

Т.е. у нас действительно нет детерминизма, он он происходит из-за разной глубины стека (внешнего side cause). Хотя всё равно выглядит странно.

[amarao]

Я, кажется, начал понимать. Дело в эксепшенах с рекурсией.

Они съедаются и продолжается выполнение. Вероятнее всего в этот момент всякие нюансы с глубиной стека начинают определять random seed.

[yurikhan]

Так, а вот продолжать рекурсию при получении KeyboardInterrupt — это подстава.

[amarao]

Ну вот так вот неявный except работает.

Если хочешь убить - Ctrl-Z; kill %%.

[yurikhan]

Это для тех, у кого нет соседней вкладки с htop’ом :P