LANG·I Язык Глава 5 из 65
Свои слова
Мастерская инструментов. В 1949 году в Кембридже научились писать подпрограммы — куски программы, которые можно звать снова и снова, — и собирать их в библиотеку. Мы соберём свой ящик инструментов: простые числа, наибольший общий делитель, римские цифры, проверка номера карты. А заодно сыграем в чёрный ящик.
Язык
Опирается на: 04 · Снова и снова
Что вы унесёте из главы
- давать куску программы имя и звать его с разными параметрами
- отличать return от print и понимать, где живут переменные функции
- разбивать задачу на функции сверху вниз и проверять номер карты алгоритмом Луна
Прошлая глава кончилась стеной. В задаче про простые числа проверка одного числа заняла семь строк и намертво вросла в цикл. Захотите найти простые-близнецы — пары вроде 11 и 13, где оба числа простые, — и проверять придётся два числа, а значит, писать эти семь строк дважды. Понадобится простота ещё где-нибудь — трижды. А потом в одной из копий найдётся ошибка, и чинить её придётся во всех. Нужен способ написать кусок работы один раз, дать ему имя и звать по имени. В ту же стену упёрлись программисты первых компьютеров и нашли выход в первые же месяцы работы машин.
Кембридж, 1949: библиотека на перфоленте
Сегодня подпрограммы называют функциями, и конец им никто вручную не дописывает, это делает язык. А идея всё та же, что у Уилера. Эта глава устроена как мастерская: вы соберёте ящик инструментов, которые ещё не раз вернутся в курсе, и с каждым новым инструментом будет открываться новая деталь того, как устроены функции.
Инструмент первый: квадрат
Начнём с инструмента, результат которого видно глазами. В прошлой главе черепаха рисовала квадрат циклом из двух команд. Чтобы нарисовать три квадрата разного размера, этот цикл пришлось бы написать трижды. Вместо этого научим Python новому слову:
Строка def draw_square(size): — заголовок. Слово def (от define, «определить») говорит: сейчас будет новое слово. Дальше имя, в скобках — параметр size, двоеточие, а под ним с отступом — тело. Определение само ничего не рисует: оно только записывает рецепт под именем draw_square. Работа начинается при вызове. Строка draw_square(40) значит: «выполни тело, положив в size число 40». Значение, которое передают при вызове, называют аргументом. Тело одно, а вызовов с разными аргументами три, вот и квадратов три.
Такой именованный кусок программы, который можно вызывать с разными аргументами, называется функцией. Многие функции Python знает с рождения — print, input, len, — а свои можно добавлять сколько угодно, и язык прирастает словами под вашу задачу.
Параметров бывает несколько. Многоугольник требует двух чисел: сколько сторон и какой они длины. Поворот на каждом углу, как мы выяснили в прошлой главе, равен $360 / n$ градусов:
Аргументы раздаются параметрам по порядку: первый — в sides, второй — в size. Шесть многоугольников из одного угла, от треугольника до восьмиугольника, а описание многоугольника — одно.
Проследим, как Python ходит по программе с функцией. Нажмите «Шаги» и следите за стрелкой. После шестой строки она прыгнет в функцию, на её заголовок в первой строке, пройдёт тело и вернётся на седьмую. В колонке «Кадры» появится второй кадр, рабочее место вызова, где лежит его параметр name. Это всё тот же прыжок Уилера, только адрес возврата Python запоминает сам.
Определение стоит выше вызовов, и не случайно: Python читает программу сверху вниз, и к строке greet("Ада") он уже должен знать, что такое greet. Поменяйте их местами — получите знакомый NameError.
Инструмент второй: сумма цифр
Квадрат рисует, и это его единственная работа. Но чаще от инструмента ждут ответа: посчитай и скажи результат. Возьмём сумму цифр из задачи прошлой главы и сделаем из неё функцию:
Последняя строка тела, return total, заканчивает работу функции и отдаёт значение туда, откуда её позвали. После этого сам вызов digit_sum(1843) в программе как бы превращается в число 16: его можно напечатать, сложить с чем-нибудь, сравнить или отдать другой функции. В последней строке программы так и сделано: сумма цифр числа $2^{1000}$ равна 1366, а сумма цифр 1366 — 16. То, что функция отдаёт через return, называют её возвращаемым значением.
Раз функция отдаёт число, из неё можно строить новые инструменты. Будем складывать цифры, пока не останется одна, — получится цифровой корень:
У положительного числа цифровой корень совпадает с остатком от деления на 9 (если остаток ноль, корень равен девяти). На этом построена старинная проверка вычислений «по девяткам»: у правильного произведения цифровой корень равен цифровому корню произведения корней сомножителей. Нам же сейчас интереснее другое: digital_root уместился в четыре строки, потому что черновую работу за него делает готовый инструмент.
Здесь начинающие путаются чаще всего. Вот та же функция, только вместо return в конце стоит print:
Число 16 на экране есть — его напечатала функция. Но в result лежит None, особое значение «ничего»: функция, которая не дошла до return, возвращает именно его. А с «ничего» нельзя складывать, отсюда TypeError. Запомните разницу: print показывает значение человеку и тут же о нём забывает, return отдаёт значение программе, чтобы та работала с ним дальше.
Функция def twice(x): return 2 * x. Что напечатает print(twice(twice(3)) + twice(1))?
Изнутри наружу: twice(3) — это 6, twice(6) — 12, twice(1) — 2, и $12 + 2 = 14$. Каждый вызов превращается в своё возвращаемое значение, и выражение считается дальше как обычное.
Игра: чёрный ящик
О функции с return снаружи можно судить только по ответам. Дали вход, получили выход, а что внутри, не видно, да и знать не обязательно. Ниже десять ящиков с функциями внутри. Бросайте в ящик числа, смотрите, что выходит, и когда поймёте закон — нажмите «Я понял». Ящик задаст три вопроса: предскажите его ответы, и он откроется, показав свой код.
Так же смотрят на функции математики — в «Царице наук» с этого начинается глава о функциях. И так же работают программисты: вы пользуетесь print и len, ни разу не заглянув внутрь. На договоре «дай мне это — получишь то» держатся большие программы: их собирают из частей, не помня устройства каждой. Свою функцию лучше снабдить таким договором прямо в коде, и до этого мы скоро дойдём.
У каждого вызова свой верстак
Внутри digit_sum есть переменные n и total. А что, если переменные с такими же именами есть и в основной программе? Функция крутит n до нуля — не сломает ли она чужое n?
Снаружи n осталось 1843, а total — тысячей. При каждом вызове Python заводит для функции новое рабочее место — его называют кадром, — и все переменные, которые функция создаёт, включая параметры, живут там. Это локальные переменные: у каждого вызова они свои и исчезают, когда вызов закончился. Часть программы, где имя что-то значит, называют областью видимости этого имени. Нажмите «Шаги»: во время вызова в колонке «Кадры» их два, глобальный и digit_sum(), и в каждом своё n.
Когда функции вызывают друг друга, кадры складываются стопкой: позвали функцию — сверху лёг новый кадр, она вернула ответ — кадр сняли, и работа продолжается в кадре под ним. Эту стопку называют стеком вызовов. Вот три функции, которые зовут друг друга: периметр прямоугольного треугольника по двум катетам вызывает гипотенузу, а та дважды — квадрат.
Два вызова perimeter — две «горы» одинаковой формы: каждая вырастает до четырёх кадров, когда работает square, и опускается обратно. В каждой горе square вызывается дважды, и это два разных кадра, каждый со своим x.
Здесь видно, чего не умел прыжок Уилера. Адрес возврата подпрограмма EDSAC хранила в своей последней ячейке — в одном экземпляре. Если бы подпрограмма позвала саму себя, второй вызов затёр бы адрес возврата первого, и первый уже не нашёл бы дороги назад. У Python для каждого вызова свой кадр, а в нём своё место возврата, поэтому функция может позвать саму себя, та — снова себя, и так сотни раз вглубь. Что из этого получается и где этому предел, расскажет глава 9.
Настройки по умолчанию
Хорошему инструменту не нужно каждый раз сообщать очевидное. Пусть многоугольник по умолчанию рисуется со стороной 60 и чёрным цветом, а когда надо — другими. Для этого в заголовке параметру дают значение по умолчанию:
Первый вызов передаёт только число сторон, остальное берётся по умолчанию. Во втором указан и размер. В третьем размер пропущен, а цвет назван по имени: color="red". Такие аргументы называют именованными, и порядок для них неважен: в четвёртом вызове размер назван раньше числа сторон.
Вы пользовались этим ещё в прошлой главе, когда писали print("#", end=""). У print тоже есть параметры со значениями по умолчанию, и Python охотно их покажет:
Заголовок print(*args, sep=' ', end='\n', file=None, flush=False) читается так: сколько угодно значений, между ними по умолчанию пробел, в конце по умолчанию перевод строки '\n'. Когда вы писали end="", вы меняли одну настройку, не трогая остальных.
Этикетка на инструменте
Откуда help узнал, что делает print? Из этикетки, которую прикрепили к функции её авторы. Своей функции этикетку можно дать так же: строкой в тройных кавычках сразу под заголовком. Это строка документации, по-английски docstring:
В этикетке пишут договор, а не устройство: что функция принимает, что возвращает и, если надо, пример. Хороший пример заодно служит проверкой — в главе 11 мы научимся запускать такие примеры автоматически. Вторая половина этикетки — имя. Имена функций, которые что-то делают, обычно начинают с глагола: draw_square, greet. Функции, которые считают величину, называют по величине: digit_sum, hypotenuse. А функции-вопросы с ответом «да» или «нет» — с is_: is_prime, is_lucky.
Бусы из функций
Мы уже нанизывали функции одну на другую: digit_sum(digit_sum(2 ** 1000)), twice(twice(3)). Ответ одной функции становится входом другой. Это композиция, и с ней из нескольких простых инструментов получаются новые без единой новой строки внутри. Попробуйте на бусах: каждая бусина — маленькая функция, число бежит по нитке слева направо.
Уже первая задачка показывает, что порядок бусин не безразличен: «квадрат, потом плюс один» делает из тройки 10, а «плюс один, потом квадрат» — 16. Запись тоже стоит запомнить. Нитка читается слева направо, а в Python та же цепочка пишется изнутри наружу: в inc(square(3)) первой выполняется самая внутренняя функция, square. Математики пишут композицию так же, $f(g(x))$, и так же её читают.
Сверху вниз: счастливый билет
Функции нужны не только чтобы не повторяться. С их помощью большую задачу можно решать, не утонув в деталях. Вот задача. На старых трамвайных и автобусных билетах печатали шестизначный номер, от 000000 до 999999. Билет считался счастливым, если сумма первых трёх цифр равна сумме последних трёх, — как 123 321. Сколько всего счастливых билетов?
Решим её сверху вниз. Сначала напишем решение так, будто нужный инструмент уже есть, — функцию is_lucky, которая отвечает, счастлив ли билет. Пока у нас вместо неё заглушка, которая всегда отвечает «нет»:
Программа работает, хоть и врёт: печатает ноль. Подчёркивания в 1_000_000 Python пропускает, они только для глаз. Зато верхний уровень готов, и он прост, как сама задача: перебрать билеты и сосчитать счастливые. Спустимся на уровень ниже и допишем is_lucky. Первые три цифры номера — это ticket // 1000, последние три — ticket % 1000, а складывать цифры у нас уже есть чем:
Счастливых билетов 55 252 — примерно один на восемнадцать. Функция is_lucky возвращает результат сравнения, то есть сразу True или False, без всякого if, и ни одна функция здесь не длиннее шести строк. Такой способ решать задачи называют декомпозицией сверху вниз: сначала главная мысль, записанная через ещё не написанные функции, потом каждая из них по отдельности, и так до самых простых. Так пишут и большие программы, от игр до операционных систем.
Чистые инструменты
Если вы добрались до десятого ящика в игре, вы встретили странную функцию: на один и тот же вход она отвечала по-разному. Внутри у неё глобальный счётчик вызовов, и каждый вызов его меняет. Сравните её с digit_sum: та отвечает только на основании аргумента и ничего не меняет вокруг — ни переменных снаружи, ни экрана. Такие функции называют чистыми.
Не всякая полезная функция чистая: вся польза draw_square в том, что она рисует, а greet — что печатает. Но где можно, лучше писать чистые. Такую функцию легко проверить: дал вход, сравнил выход с ожидаемым, и неважно, вызывали ли её до этого, — так сервер курса и проверяет ваши задачи. Её можно переставлять и нанизывать, как бусину, не боясь сюрпризов вроде десятого ящика.
Инструмент на каждый день: номер карты
Возьмите любую банковскую карту. Цифры её номера не случайны: последняя — контрольная цифра, её подбирают так, чтобы весь номер прошёл одну простую проверку. Если при наборе ошиблись в одной цифре, проверка это заметит, и сайт магазина скажет «неверный номер карты», даже не связываясь с банком.
Правило Луна такое. Идём по номеру справа налево и каждую вторую цифру — вторую, четвёртую, шестую с конца — удваиваем; если после удвоения получилось больше девяти, вычитаем девять. Складываем всё вместе. Номер верен, если сумма делится на 10. Попробуйте на номере ниже: нажатие на цифру меняет её на следующую, а кнопки устраивают типичные ошибки набора.
Опыт под рисунком перебирает все ошибки в одной цифре и ловит каждую. Так будет с любым номером, и это можно доказать.
Если в номере, прошедшем проверку Луна, заменить одну цифру другой, номер проверку не пройдёт.
Посмотрим, что каждая цифра $d$ даёт в сумму. Если цифра не удваивается, она даёт саму себя, и разные цифры дают разное. Если удваивается — цифры 0, 1, 2, …, 9 дают соответственно 0, 2, 4, 6, 8, 1, 3, 5, 7, 9: снова все десять результатов разные, каждый от 0 до 9. Значит, когда одна цифра меняется на другую, её вклад меняется на число от 1 до 9 по модулю (в ту или другую сторону), а остальные слагаемые остаются прежними. Сумма меняется на число, не кратное 10, и раз прежняя сумма делилась на 10, новая делиться перестаёт.
С перестановкой соседних цифр почти так же: проверка ловит её всегда, кроме одного случая — пары 0 и 9. Ноль, удвоенный или нет, даёт ноль, а девятка даёт девять в обоих случаях (18 − 9 = 9), поэтому от перестановки 09 ↔ 90 сумма не меняется. Правило Луна можно посчитать в уме, и при этом оно ловит самые частые ошибки набора. От всех ошибок сразу одна контрольная цифра не защитит.
Задачи: ваш ящик инструментов
Четыре инструмента, каждый — функция. Тесты вызывают вашу функцию с разными аргументами и сравнивают с ожидаемым то, что она вернула, — именно вернула, а не напечатала. Печатать внутри функций не нужно.
Напишите функцию is_prime(n), которая возвращает True, если целое число $n$ простое, и False в остальных случаях — в том числе для 0, 1 и отрицательных чисел. Тесты проверят и числа около триллиона, так что перебирать делители до самого $n$ не получится: на всё даётся пара секунд.
Проверку из задачи «Все простые до n» можно взять почти без изменений. Только вместо флажка теперь есть return: нашёлся делитель — сразу return False, функция на этом закончится.
Делители достаточно перебирать, пока d * d <= n: для числа около $10^{12}$ это миллион проверок вместо триллиона. И не забудьте про числа меньше двух.
Флажок is_prime из прошлой главы исчез: досрочный return делает то же самое короче. А близнецы, с которых началась глава, теперь ищутся одним условием. Бывают ли простые-близнецы сколь угодно большими, до сих пор никто не знает; об этом в «Царице наук».
Напишите функцию gcd(a, b), которая возвращает наибольший общий делитель неотрицательных целых чисел $a$ и $b$. Например, gcd(12, 18) == 6, gcd(17, 5) == 1, gcd(0, 5) == 5, а gcd(0, 0) по договорённости равен 0. Готовым math.gcd пользоваться нельзя. Числа будут длиной до сотни цифр.
Алгоритм Евклида: общий делитель чисел $a$ и $b$ делит и остаток a % b, поэтому gcd(a, b) == gcd(b, a % b). Когда второе число стало нулём, ответ — первое. Подробно — в «Царице наук».
В цикле while b != 0 пару нужно заменить одной строкой: a, b = b, a % b. Вычитать меньшее из большего тоже можно, но на числах вроде $10^{18}$ и 7 это займёт сотни лет.
Три строки, которым больше двух тысяч лет: алгоритм описан в «Началах» Евклида. Остатки убывают очень быстро — числа хотя бы вдвое уменьшаются за каждые два шага, — поэтому даже для стозначных чисел нужно не больше нескольких сотен итераций. Этот инструмент понадобится в главе 60, когда мы будем строить ключи шифра RSA.
Напишите функцию to_roman(n), которая возвращает число от 1 до 3999 римскими цифрами — строкой: to_roman(4) == "IV", to_roman(1994) == "MCMXCIV", to_roman(2026) == "MMXXVI". Напомним цифры: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000, а 4, 9, 40, 90, 400 и 900 пишутся вычитанием: IV, IX, XL, XC, CD, CM.
Разложите задачу сверху вниз. Римская запись числа — это запись тысяч, потом сотен, потом десятков, потом единиц, склеенные подряд: 1994 = M + CM + XC + IV.
Сотни, десятки и единицы пишутся по одному правилу, только разными буквами: для единиц I, V, X, для десятков X, L, C, для сотен C, D, M. Напишите помощницу roman_digit(d, one, five, ten), которая записывает одну десятичную цифру $d$ этими тремя буквами, и вызовите её три раза.
Строку можно умножить на число: "I" * 3 == "III", а "I" * 0 — пустая строка. Цифры 4 и 9 — особые случаи: one + five и one + ten.
Одна функция знает, как писать одну цифру, другая — как разложить число на цифры. Ни одна не длиннее девяти строк, и обе можно проверить по отдельности. Без помощницы одно и то же правило пришлось бы писать трижды, с разными буквами, и мы снова упёрлись бы в стену из начала главы. Скобки вокруг длинного выражения в return нужны, чтобы перенести его на несколько строк.
Напишите функцию luhn(number), которая получает номер строкой — цифры, возможно, разделённые пробелами, — и возвращает True, если номер проходит проверку Луна, и False иначе. Например, luhn("2026 1001 0405 1234") — True, а luhn("2026 1001 0405 1235") — False.
Сначала уберите пробелы: пройдите строку циклом for и соберите только цифры в новую строку. Её можно превратить в число через int — ведущие нули на сумму Луна не влияют.
Цифры числа справа налево вы уже умеете перебирать: n % 10 и n // 10. Заведите счётчик позиции: удваивается цифра, если позиция нечётная (самая правая — позиция 0).
Удвоенное больше девяти — вычтите девять. В конце верните total % 10 == 0 — это уже True или False.
Снова декомпозиция: очистка номера — отдельная маленькая функция. Настоящий номер карты в ячейку лучше не вписывать: код выполняется на сервере курса, и номер уйдёт туда вместе с программой. Для опытов хватит выдуманных номеров, как в условии. А в главе 16 сумма Луна послужит хеш-функцией.
Куда дальше
Ящик собран. Вот что в нём лежит и где оно пригодится:
| Инструмент | Что делает | Где вернётся |
|---|---|---|
digit_sum | сумма цифр | в бусах и счастливых билетах этой главы |
is_prime | простое ли число | глава 60: ключи RSA строят из больших простых |
gcd | наибольший общий делитель | глава 60: RSA |
to_roman | римская запись | пример декомпозиции |
luhn | проверка номера карты | глава 16: хеш-таблицы |
Все наши инструменты работают с одним числом или одной строкой за раз. luhn проверит номер карты, а если номеров тысяча? is_prime ответит про одно число, но куда сложить все найденные простые, чтобы потом с ними работать? Заводить тысячу переменных number1, number2… глупо, да и сколько их понадобится, заранее не знаешь. Нужно одно имя для многих значений. Оно появится в главе 6 и сразу пойдёт в дело: вам достанется журнал землетрясений с трекера сайта, тысячи записей, а к нему вопросы дежурного сейсмолога.