Состояние и трассировка: что делает программа на самом деле

Если ты привык вести таблицу трассировки и находишь по ней ошибку, листай до «Теперь сам» в конце.

Как думаешь, что напечатает эта программа

Автор хотел найти второе по величине число в списке:

a = [3, 8, 5, 8]
luchshij = 0
vtoroj = 0
for x in a:
    if x > luchshij:
        vtoroj = luchshij
        luchshij = x
print(vtoroj)

Ответь себе, не запуская: что окажется на экране? Читается программа гладко - новое наибольшее отодвигает старое на второе место. Если твой ответ 5, именно для таких случаев и нужна таблица.

На что это похоже

Запись шахматной партии. По ней можно восстановить позицию на любом ходу, не помня партию: взял начальную расстановку и применил ходы по порядку. Позиция - это состояние, ход - это шаг. Тренер, разбирая проигрыш, не спрашивает «что ты хотел», он ставит позицию двадцатого хода и показывает, где план разошёлся с доской. Трассировка делает с программой то же самое.

Механизм: исполнитель Python и его шаги

Исполнитель в этом курсе - интерпретатор Python: программа, которая берёт твой текст и выполняет его сама, шаг за шагом. Строго говоря, CPython (обычный Python) сначала переводит весь файл в промежуточный байт-код, поэтому синтаксическая ошибка в последней строке (скажем, незакрытая скобка) не даст выполниться и первой; но выполняет этот байт-код сам интерпретатор. Есть и другой способ - компилятор: он переводит программу в другой язык, обычно в команды процессора, и выполняется уже перевод. Чаще всего переводят заранее и целиком, но бывает и по частям прямо во время работы программы. Для рассуждения разницы нет: и там и там шаги идут по порядку, и каждый шаг меняет состояние.

Какие шаги бывают:

Таблица трассировки повторяет эту картину: в колонке «строка» - что выполнилось, в колонках переменных - значения после шага, в колонке «условие» - результат проверки. Пустая клетка значит «не изменилось», а до первого присваивания - «значения ещё нет». Когда шаги внутри круга цикла короткие, строку таблицы отводят целому кругу и пишут значения на его конец.

Правило

Трассировка: одна строка таблицы - один выполненный шаг (или целый круг цикла); в клетки пишется значение ПОСЛЕ шага; условия записываются своим результатом, True или False. Заполнять таблицу надо по тексту программы, а не по замыслу, и останавливаться на первой строке, где значение расходится с ожидаемым.

Разбор: таблица для второго по величине

Ведём таблицу для программы из начала урока. Колонки: текущий x, результат условия x > luchshij, значения luchshij и vtoroj после круга.

Программа напечатает 3. Расхождение в третьей строке: пришло 5, оно меньше наибольшего, но больше второго, и должно было занять второе место. Условие x > luchshij его просто не пропустило - ветки для «меньше первого, но больше второго» в программе нет. Читая код, это легко не заметить: мысль «новое наибольшее отодвигает старое» верна, просто она описывает не все случаи.

Исправленная версия добавляет недостающую ветку, а равное наибольшему пропускает - иначе на списке [3, 8, 5, 8] вторым окажется вторая восьмёрка:

a = [3, 8, 5, 8]
luchshij = 0
vtoroj = 0
for x in a:
    if x > luchshij:
        vtoroj = luchshij
        luchshij = x
    else:
        if x > vtoroj and x < luchshij:
            vtoroj = x
print(vtoroj)

5

Обе версии рассчитаны на положительные числа и хотя бы два разных значения: начальный ноль играет роль «меньше всех», и на списке [-8, -3] исправленная версия напечатает 0. Как записать такое требование к входу, разберёт глава «Задача и модель стоимости».

Разбор: обмен двух значений

Нужно поменять местами значения a и b. Первая попытка выглядит очевидной:

a = 4
b = 9
a = b
b = a
print(a, b)

9 9

Таблица объясняет за две строки. После a = b в состоянии a = 9, b = 9: старая четвёрка стёрта, её больше нет нигде. Следующий шаг b = a копирует девятку в b. Присваивание не «переносит» значение, а перезаписывает клетку, и то, что в ней было, пропадает. Значит, старое значение надо где-то сохранить ДО перезаписи - во временной переменной:

a = 4
b = 9
vremennaya = a
a = b
b = vremennaya
print(a, b)

9 4

В Python есть и запись в одну строку, a, b = b, a, - почему она работает, разберёт следующая глава.

Где ошибаются

Первая ошибка - вести таблицу в голове и пропускать «очевидные» круги. Дефект второго по величине жил ровно в круге, который казался очевидным. Вторая - заполнять клетки тем, что строка должна сделать, а не тем, что она делает: так таблица повторяет замысел и ничего не находит. Третья - открыть отладчик или машинную трассу раньше своей таблицы. Тогда расхождение показывают тебе, а не находишь ты, и в следующий раз без отладчика его снова не найти.

Зачем это в работе

Отладчик в редакторе показывает ровно эту таблицу: строку, на которой стоит выполнение, и значения переменных. print внутри цикла печатает её по строке на круг. Разница только в том, кто заполняет клетки, а умение то же: остановиться на первом расхождении с ожиданием. На собеседовании, где отладчика нет, просят прогнать код на маленьком входе вслух - и это тоже трассировка. На ревью она отвечает на вопрос «а что будет на пустом списке» быстрее, чем спор.

Теперь сам

Заполни таблицу и скажи, что напечатает программа:

s = 0
i = 1
while i < 10:
    s = s + i
    i = i * 2
print(s, i)