Усвідомлене програмування у вправі «Зерна» на Bash

Увага, спойлер: у цій статті є спойлери до вправи «Зерна» загалом і зокрема до вправи «Зерна» на треку Bash. Якщо ми ще не виконали її самостійно й не хочемо бачити готові рішення, повернімося до статті, коли завершимо вправу!

Ось наш перший день у новій компанії. Усі папери заповнено, з командою ми познайомилися, і нарешті настав час сісти й почати читати код, над яким нам доведеться працювати. Ми починаємо читати різні функції, класи й модулі, і, читаючи, ловимо себе на тому, що починаємо мружитися на екран від нерозуміння. Ми читаємо далі, і з наших уст зривається одне слово, ледве вимовлене, майже видихнуте: «Щоооооооо...»¹ Чим далі ми читаємо, тим частіше це трапляється, ми дедалі більше дивуємося і навіть трохи злимося.

Що відбувається в цьому коді?

Щоразу, коли над якимось кодом працює більше ніж одна людина, обсяг турботи й навмисності, потрібних, щоб усе залишалося керованим, різко зростає. Це вже не просто концепція, що живе в нашій голові, і код, який має цю концепцію втілити. Тепер концепція має жити всередині коду, де всі, хто працює разом, можуть її бачити й за потреби змінювати.

Те, як ми реалізуємо щось, мало що значить для кінцевого користувача, але має багато сказати кожному інженеру, який будь-коли торкнеться нашого дизайну. Часто є багато способів досягти однакової функціональності, і може здатися, що будь-якого з варіантів буде достатньо, щоб виконати роботу. Проте я переконаний: кожне наше рішення має мати причину (навіть якщо це дрібне рішення з дрібною причиною), і ця причина має передавати мету або вимогу.

Ідея про те, що деталі реалізації мають допомагати читачам коду розпізнавати хід думок, цілі та пріоритети, називається дизайнерським задумом. Те, як ми називаємо змінні, які параметри приймає наша функція і як усе абстраговано, - це все місця, де можна виразити дизайнерський задум: добре або погано.

Я твердо переконаний, що дизайнерський задум - одна з найважливіших речей, які варто враховувати, працюючи над інженерним проєктом. Саме це відрізняє програмну інженерію від програмування.

Програмна інженерія - це те, що відбувається з програмуванням, коли до нього додаються час та інші програмісти.

Russ Cox

Дизайнерський задум не знає меж дисциплін

Я працюю інженером-механіком і проєктую прес-форми для лиття під тиском, переважно для медичних виробів. Усі мої проєкти, щойно завершені, одразу вирушають за двері, до механообробного цеху, де з них починають виготовляти всі деталі й складати їх докупи. Оскільки вони не знають усього, що промайнуло в моїй голові, поки я створював кожен проєкт, мені доводиться шукати спосіб показати свій задум через сам проєкт.

Часто якісь ділянки конструкції стають особливо критичними. Або замовник сказав, що тут потрібні особливо вузькі допуски, або ж спосіб, у який прес-форма збирається докупи, вимагає надзвичайної точності з якоїсь причини. Тож, щоб допомогти верстатникам виготовити деталі так, щоб точність на важливих місцях була в пріоритеті, я залишаю ділянки, які спеціально зроблені квадратними або які легко затиснути в лещата певним чином. Так найпростіший для них шлях дає найкращий результат для мене.

Є також місця, де розміри не такі критичні. Наприклад, якщо я роблю в проєкті отвір лише для вентиляції, я зроблю його зручного поширеного розміру, скажімо 6 мм.

Коли вони обробляють цей отвір і беруться виміряти, що вийшло, якщо вони бачать число на кшталт 5,99 мм, то подумають: «Гаразд, імовірно, тут мало бути 6 мм, тож я досить близько», і їм навіть не доведеться перевіряти розміри на CAD чи на кресленні зі специфікацією. А якби я зробив його чимось незвичним, наприклад 5,87 мм, вони подивилися б на нього й мали б таку першу реакцію:

1. Ой, трясця, невже я зробив отвір замалим? Тут мало бути 6 мм?
2. (Вони йдуть перевіряти CAD і бачать, що їхній отвір у нормі й це просто незвичний розмір.)
3. Хмм. Напевно, цей отвір має незвичний розмір не просто так. Можливо, він справді важливий, або замовник попросив тут особливий отвір. Треба буде піти поговорити з Раяном і зʼясувати, що ж такого важливого в цьому отворі.
4. (БАБАХ! Вони делікатно ставлять шмат алюмінію на мій стіл.)
5. (Вони зʼясовують, що в цьому отворі немає нічого важливого, я просто вибрав дивний розмір, і вся ця додаткова робота й хвилювання були марними.)
6. Ох уже цей Раян, ну й тип. (бурчання, лайка, бурчання)

Усе це відбувається тому, що кожне рішення в моєму проєкті щось повідомляє іншим людям, які на нього дивляться й працюють із ним, хочу я того чи ні. Вони мушені бачити в ньому сенс, бо це єдина інформація, на яку вони можуть спертися! Тож набагато краще, якщо я можу витратити час і вкласти у свій проєкт осмислену, навмисну інформацію.

Зерна: вступ

Тепер поговорімо про те, як дизайнерський задум можна передати в коді, на прикладі однієї з вправ Exercism. Нещодавно я працював зі студентом над його рішенням вправи Зерна на треку Bash. Зерна - це вправа, присвячена задачі про зернини на шахівниці. Коротко: на першу клітинку шахівниці кладуть одну зернину пшениці. На наступну клітинку - дві зернини. На наступну - чотири. І так далі, кожна клітинка має вдвічі більше зернин, ніж попередня. Студентів просять знайти спосіб обчислити значення на кожній окремій клітинці, а також загальну кількість зернин на дошці.

Цей конкретний студент придумав досить дотепний спосіб обчислити суму.

bc <<< 'ibase=16;FFFFFFFFFFFFFFFF'

bc - це калькулятор командного рядка. Йому можна передавати арифметичні вирази, і він їх обчислить, навіть для дуже великих цілих чисел і чисел з плаваючою комою. У Bash є й інші способи робити обчислення без bc, але задля простоти ми розглянемо, як задум можна передати (або не передати), працюючи з bc.

Це рішення працює, бо вся вправа обертається навколо степенів двійки. А де є степені двійки, там є двійкова система, а де є двійкова система, там є шістнадцяткова²!

Рішення дотепне, але що код нам каже? Що тут важлива шістнадцяткова система? Що задача принципово обертається навколо 16? Після перечитування умови стає цілком ясно, що ні те, ні інше не відповідає дійсності. Ми зі студентом накидали кілька ідей, як чіткіше передати задум. Ось що ми придумали:

Перший варіант: двійкова система

Оскільки в нас багато чого подвоюється (а отже, багато степенів 2), подивімося, що відбувається в двійковій системі, і чи це нам допоможе.

На першій клітинці 1 зернина. У двійковій системі це також буде 0b1 (де 0b просто означає «це двійкове число», а власне число - 1).

На другій клітинці 2 зернини. У двійковій системі - 0b10. Поки що всього 3 (або 0b11).

На третій клітинці 4 зернини (0b100). Поки що всього: 7 (0b111).

На четвертій клітинці 8 зернин (0b1000). Поки що всього: 15 (0b1111).

Чи бачимо ми закономірність?

Кожна клітинка відповідає ще одному двійковому розряду, а якщо додати їх усі разом, вийде просто купа одиниць.

У рішенні студента ми могли б замінити літери F на 64 одиниці (по одній на кожну клітинку)!

bc <<< "ibase=2;1111111111111111111111111111111111111111111111111111111111111111"

Це навмисніше, бо точніше відповідає тому, що дає нам задача. Але ми не розмовляємо мовою роботів. Довга, по суті незліченна послідовність одиниць - мабуть, не покращення.

Другий варіант: обчислення грубою силою

Гаразд, тож, можливо, варто зовсім відмовитися від недесяткових систем числення. Чому б не зробити код таким, як ми підсумовували б кількість зернин на шахівниці вручну, рахуючи зернини на кожній клітинці?

total=0
current_grains=1
for square in {1..64}; do
  total=$( bc <<< "$total + $current_grains" )
  current_grains=$( bc <<< "$current_grains * 2" )
done
echo "$total"

Це набагато читабельніше й зрозуміліше. Код ясно показує, що кількість клітинок на шахівниці є рушійним чинником, як і ефект подвоєння для кожної клітинки. Я вважаю, що це краще за початкове рішення.

Однак.

Воно повільне. Цикл, додавання й повторні звернення до зовнішньої команди? Усе це разом дає доволі повільний час виконання. Чи це аж така велика проблема? Ні. Якщо ми пишемо скрипт на Bash, то, ймовірно, уже вирішили, що обмежень за швидкістю в нас немає. Але чи могло б бути краще? Так.

Третій варіант: пряме обчислення

Тож як нам додати все це без ітерацій?

Розгляньмо меншу версію тієї самої задачі: шахівницю з 5 клітинок³.

Ці пʼять клітинок мали б таку кількість зернин:

---------------------
| 1 | 2 | 4 | 8 |16 |
---------------------

А загальна сума тут буде: 1 + 2 + 4 + 8 + 16 = 31. Хм. 31 поки що ні про що очевидне мені не говорить. Візьмімо трохи більше.

Гаразд, а як щодо шахівниці з 6 клітинок? Цього разу я покажу поточну суму під кожною клітинкою, щоб легше було додавати.

-------------------------
| 1 | 2 | 4 | 8 |16 |32 |
|   | 3 | 7 |15 |31 |63 |
-------------------------

А сума: 1 + 2 + 4 + 8 + 16 + 32 = 63. Хм... Я вже починаю вбачати проблиск закономірності, але зробімо ще один приклад, щоб переконатися.

7 клітинок:

-----------------------------
| 1 | 2 | 4 | 8 |16 |32 |64 |
|   | 3 | 7 |15 |31 |63 |127|
-----------------------------

1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. Чи бачимо це? Чи щось насторожує в значеннях 31, 63, 127?

Вони майже степені двійки. Насправді вони на одиницю менші за наступний степінь двійки.

Ще один приклад, щоб закріпити. Уявімо шахівницю з 12 клітинок. Це одиниця, подвоєна 11 разів (що в математичних колах означає 2^11): 2048. Подвоїмо ще раз, і отримаємо 4096 (2^12). Тож... якщо ми правильно вловили закономірність, поточна сума буде на одиницю меншою за 4096, тобто 4095. І якщо ми її порахуємо, то отримаємо саме це: 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048 = 4095.

Інакше кажучи, щоб знайти суму для всіх n клітинок, потрібно піднятися на один степінь двійки вище й відняти 1 від результату.

Кількість зернин на клітинці 64 дорівнює 2^63 (з нульовим індексом, памʼятаємо?). Тож-о-о-о, якщо ми хочемо обчислити загальну кількість зернин на всіх клітинках до клітинки 64 включно, нам треба обчислити 2^64 і відняти 1.

Бум!

У Bash це матиме такий вигляд:

bc <<< "2^64 - 1"

Це стає зрозумілим, коли перевіримо, що відбувається в двійковій системі. Якою в двійковій системі була сума всіх 64 клітинок?

0b1111...  # 64 ones

Яка кількість зернин на теоретичній 65-й клітинці?

0b10000... # 1 and 64 zeros

Як перейти від одиниці та 64 нулів до 64 одиниць? Відняти 1.

А яку додаткову користь це нам дає? Що ж, тепер у нас є гарний, читабельний вираз для суми. Він не виконує ітерацій, тож продуктивність хороша. І він містить число 64, тобто кількість клітинок на шахівниці, а це гарний приклад добре позначеного дизайнерського задуму. Якщо з якоїсь причини за 1000 років світ перейде на стандартну шахівницю 7x7, той майбутній інженер (імовірно, з Bash 6.1) перевірить скрипт, побачить, до чого ми прагнули, і змінить 64 на 49. Усе добре!

Залишаймося навмисними, друзі

Коли ми розробляємо реалізацію, легко розкидатися речами й чіплятися за перше рішення, яке працює. Це нормально, поки ми досліджуємо задачу, але щойно ми повністю зрозуміємо критичні складники (а на добре відшліфування варто витратити час), подбаймо, щоб кожен алгоритм, кожна назва змінної і навіть пробіли малювали картину задачі, критичних вимог і того, як усі частини складаються докупи.