...

пятница, 11 ноября 2016 г.

Пятничный формат: «Нельзя просто так взять и объяснить непрограммисту…»

Существуют концепты, которые очень сложно понять даже программистам в начале своего пути. И некоторые из них точно не удастся легко и быстро объяснить «простым смертным», если они не математики. Обычно такие понятия уже не так пугают людей после приведения примеров из «обычного» мира.

Мы в 1cloud попытались найти такие аналогии, так что теперь разговоры с неспециалистами могут стать чуточку интереснее, и вам с большей вероятностью удастся достичь взаимопонимания (на эту тему мы написали практическое пособие «Как вывести из себя программиста»).


/ Flickr / Dave Allen / CC

1. Рекурсия


Уже почти крылатым стало выражение: «Чтобы понять рекурсию, надо сначала понять рекурсию». Но в каждой шутке, как известно, есть доля правды.

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

Сегодня это сложно представить, но было время, когда использование рекурсии в программировании казалось сомнительным. Так, на заре шестидесятых члены комитета по разработке Алгола-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)

    Let's block ads! (Why?)

    Комментариев нет:

    Отправить комментарий