П'ятничний формат: «не Можна просто так взяти і пояснити непрограммисту...»

Існують концепти, які дуже складно зрозуміти навіть програмістам на початку свого шляху. І деякі з них точно не вдасться легко і швидко пояснити «простим смертним», якщо вони не математики. Зазвичай такі поняття вже не так лякають людей після наведення прикладів з «звичайного» світу.

Ми в 1cloud спробували знайти такі аналогії, так що тепер розмови з неспеціалістами можуть стати трішки цікавіше, і вам з більшою ймовірністю вдасться досягти взаєморозуміння (на цю тему ми написали практичний посібник «Як вивести з себе програміста»).


/ Flickr / Dave Allen / CC

1. Рекурсія
Вже майже стало крилатим вираз: «Щоб зрозуміти рекурсію, треба спочатку зрозуміти рекурсію». Але в кожному жарті, як відомо, є частка правди.

Звернемося до історії: математики використовували принцип індукції для визначення функції задовго до XIX століття, але в 1889 і 1891 Джузеппе Пеано (Giuseppe Пеано) ввів систему з п'яти аксіом для натуральних чисел (1888 першу версію аксіом, сформулював Ріхард Дедекінда (Richard Dedekind), однак створення аксіом закріпилося за Пеано). П'ята аксіома індукції була пізніше названа примітивної рекурсією. Це поняття відіграє важливу роль в підставах математики (докладніше читайте в роботи Роберта В. Соара «Вычислимость і Рекурсія», пункт 2.2).

Сьогодні це складно уявити, але був час, коли використання рекурсії в програмуванні здавалося сомнительным. Так, на початку шістдесятих члени комітету з розробки Algol'у-60 не зійшлися в думці з цього питання. Джон Маккарті вважав рекурсію витонченим способом навчити комп'ютери повторювати виконання одного і того ж коду з певними змінами. Він запропонував зробити можливість рекурсії характерною рисою нової мови, але до якогось консенсусу з цього питання прийти не вдалося. Вчені не впевнені, що вдасться її реалізувати.

Деяким членам комітету, наприклад, Петеру Науру і Адріана ван Вейнгаардену, ідея рекурсії видалася привабливою. Вивчивши проект звіту комітету в кінці 59-го, Эдсгер Дейкстра прийшов до висновку, що практично ніхто не був проти рекурсивних викликів, але це не було відображено в документі. Тоді він подзвонив Науру в Амстердам, попросивши додати лише одне речення, яке залишилося непоміченим при підписанні проекту іншими членами. Так була введена можливість рекурсії.

Рекурсію буває складно зрозуміти і початківцям. Наприклад, Джон Д. Кук, доктор математичних наук і розробник ПЗ, говорить про те, що не треба намагатися детально уявити, як виконується рекурсія. Пол Грем у своїй книзі про Лисп писав, що зазвичай при визначенні рекурсивної функції програміст не представляє послідовність викликів, що є результатом його виклику.

Ще одна проблема полягає в тому, як рекурсію пояснюють в підручниках. Блогер і програміст Густаво Дуарте (Gustavo Duarte) пише, що зазвичай там показується рекурсивна реалізація факторіала, а потім говориться про те, що працює це жахливо повільно і може призвести до збою з-за переповнення стека. Це приблизно, як якщо б вам сказали: «Ви завжди можете висушити волосся, засунувши голову в мікрохвильову піч. Але будьте обережні, такий спосіб може призвести до підвищення внутрішньочерепного тиску і вибуху голови. Або ви можете скористатися рушником».

Стів Макконнелл (Steven MacConnell), американський програміст, у своїй книзі «Досконалий код» розповідає, що звільнив співробітника, що використовує рекурсію. Але далеко не всі згодні з таким жорстким підходом. Так, російський програміст Олексій Мічурін (Білайн, Яндекс.Монетизація) впевнений, що в деяких випадках обійтися без рекурсії не, наприклад, у функціональних мовах типу Haskell або таких засобах, як XSLT-процесори. Так і у випадку з алгоритмом швидкого сортування quicksort, який сам по собі рекурсивний, рекурсія допоможе чіткіше сформулювати його ідею.

Але пояснити суть рекурсії непрограммистам не так вже і складно, тому що сам концепт використовується навіть в мистецтві і називається ефект Дросте. В літературі рекурсію можна знайти ще у Шекспіра: спектакль, який ставить головний герой у п'єсі, описує події самої трагедії «Гамлет». У романі Р. Маркеса «Сто років самотності» життя сім'ї Буэндиа рекурсивно повторюється з покоління в покоління, а коли останній з роду закінчує розшифровувати рукопис чарівника Мелькиадеса (яка і є опис самої книги), все зникає в налетевшем урагані.

У російській літературі рекурсивні структуру творів вводить Достоєвський, що навіть ускладнює сприйняття тексту для читача. Прикладом окремого рекурсивного елемента, традиційного для російських письменників, є рекурсивний сон: наприклад, потрійний сон вірші Лермонтова. (Докладніше про рекурсивних снах у Гоголя і Достоєвського читайте тут: «Сон Чарткова» і «Сон Свидригайлова»).

Тема багаторівневого сну лягла в основу усім відомого фільму «Початок» (тут можна почитати про декілька цікавих фактів, які допоможуть зрозуміти фільм). За сюжетом з кожним зануренням в сон у сні, час все сильніше сповільнюється, поки майже не зупиняється в «лімбо», де можна прожити цілу вічність. Ще один випадок рекурсії — зображення в зображенні. Він часто застосовується в образотворчому мистецтві (найвідоміший приклад — роботи М. Ешера), фотографії та рекламу. Та й випадки використання рекурсії в мові всім відомі: наприклад, пісня Максима Леонідова «Я обернувся подивитися, чи не озирнулася вона, щоб подивитися, чи не обернувся я...».

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

2. Вкладені цикли
Біля витоків вкладених циклів варто Чарльз Беббідж, винахідник першої аналітичної обчислювальної машини. Його дружба з Адою Лавлейс (Ada Lovelace), яка вважається першим комп'ютерним програмістом, зробила дуже великий вплив на становлення Ади як талановитого математика. І саме вона перекладала статті Луїджі Федеріко Менабреа (1842), присвячену винайденої Чарльзом Бэбиджем аналітичній машині. Але вона виконала не тільки переклад на англійську, але і написала свої коментарі, які були в три рази довше самої статті. У роботі, опублікованій в 1843 році в англійському науковому журналі, вона описала код, який можна було б використовувати у пристрої, щоб зіставити букви і символи з числами, і описала теорію циклів.

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

Прикладів вкладених циклів в реальному світі безліч — по суті, будь-повторювана дія — від миття посуду до ходьби – можна назвати вкладеним циклом. Але зупинимося на деяких конкретних аналогіях. Наприклад, лічильник відвідувань на сайті або спідометр в машині працює за таким же принципом. Вони складаються з 7-8 вкладених циклів з лічильником, кожен з яких має значення від 0 до 9. Крайнє праве число змінюється швидше всього: ви бачите, як воно збільшується, коли на сайт заходить новий відвідувач, або коли ви їдете в машині додому. Усі інші числа змінюються з більш повільною швидкістю.

В НЛП теж є термін «вкладені цикли». Сам метод йде корнями роботи відомого американського психотерапевта Мілтона Еріксона (Milton Erickson), спеціалізувався на гіпнозі. Такий прийом використовується для своєрідного введення в транс, щоб навіяти певну ідею. Суть методу — вкладення історії в історію. Потрібно почати розповідати історію, але замість її закінчення — почати ще одну. Цей крок слід повторити 3-5 разів. В середині останньої історії слід ввести ключову ідею або спонукання, а потім завершити всі розказані історії у зворотному порядку, від останньої до першої (приклад такої історії можна подивитися тут в п. 3).

3. Паралелізм
Програмісти-початківці іноді відчувають складності при роботі з паралельними системами. Основна складність з їх застосуванням послідовних мови полягає в тому, щоб визначити, коли і як слід чергувати частини програми, які можуть взаємодіяти один з одним. (Детальніше читайте тут у пункті «What makes Concurrent Software Difficult?»). При роботі на багатоядерних процесорах процедура веде до збільшення часу виконання операції і ускладнюється необхідністю синхронізації.

Витоки паралелізму можна знайти ще в роботи того ж Менабреа про аналітичній машині (див. висновок перед приміткою перекладача). Але більш істотний внесок у розвиток паралельних систем в 60-х роках XX століття вніс Карл Адам Петрі (Carl Adam Petri) представивши нову концепцію паралельних та розподілених систем, застосовну до багатьох типів дискретних систем в різних сферах наукових досліджень (інформатика, юриспруденція, виробництво, транспорт, хімія, епідеміологія, демографія). (Детальніше читайте тут у розділі «About Carl Adam Petri»). Перше наукове дослідження в області паралельних алгоритмів належить Эдсгеру Дейкстри, де він запропонував варіанти вирішення проблеми взаємного виключення.

Поза програмування така система використовувалася, наприклад, у телеграфному повідомленні. При цьому застосовувалося різне ущільнення каналів. У 1869 р. Р. В. Морозів розробив апарат частотного ущільнення ліній зв'язку: передача декількох повідомлень по одній лінії проводилася сигналами струму різної частоти. А в 1872 році Еміль Бодо (Emile Baudot) створив телеграфний апарат багаторазового дії, застосувавши ущільнення каналу з поділом часу, яке дозволило передавати по одній лінії до п'яти повідомлень. Такий спосіб передбачає чергування блоків інформації з різних потоків.

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

Паралельні системи в реальному світі не така вже рідкість, наприклад, злагоджена робота команди, в якій різні люди виконують різні завдання. Ефективна робота команди відмінно показана на прикладі японських робітників, коли 1200 інженерів за кілька годин перенесли наземну станцію метро під землю.


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

Ну і звичайно, можна провести паралель між комп'ютером і мозком. На відміну від людини, наш мозок точно встигає виконувати велику кількість завдань (точнее близько 50) одноразово і цілком досягає успіху в цьому. Але всі ці завдання розподіляються між різними групами нейронів. Марвін Мінський написав книгу «Товариство розуму», в якій розглядає людський розум як сукупність окремих простих процесів, які називаються агентами. Така теорія теж відображає основи системи паралельних обчислень.

4. Оператор присвоювання
Оператор присвоювання може ввести в оману новачка в програмуванні з двох причин: через використання знака рівності і нерозуміння самої суті оператора. Знак рівності не завжди і не у всіх мовах) використовується для позначення оператора присвоювання. Наприклад в APL, щоб відрізняти присвоювання від рівності, присвоювання позначався так: «<-».

Тим не менш, у багатьох сучасних мовах введена можливість використовувати знак «=» для оператора присвоювання, так як завжди можна зрозуміти з контексту, що саме мається на увазі: присвоювання або асоціація (до речі, Ніклаус Вірт считал використання знака «=» в якості оператора присвоювання «поганою ідеєю» – і не лише через труднощі розуміння, але і з-за порушення логіки – з його точки зору введення такого позначення призводить до появи нового логічного концепту – «примусу до рівності»).

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

Додаткове читання:

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.