Что не так с циклами for?

в 12:27, , рубрики: haskell, Программирование, циклы for

Возможное появление замыканий в Java стало горячей темой для обсуждений. Готовится предложение по добавлению замыканий в грядущую версию языка, однако же предлагаемый синтаксис вкупе с усложнением языка подвергаются критике со стороны многих Java программистов.

Сегодня Эллиотт Расти Харольд (Elliotte Rusty Harold) опубликовал свои сомнения по поводу возможных изменений. Один из главных заданных им вопросов: “Почему вы ненавидите цикл for”(«Why Hate the for Loop?»)?

Я не знаю, что заставляет людей так страстно мечтать об избавлении от циклов for. Это не первый и даже не второй раз, когда теоретики от мира computer science восстают против них.

Было бы неправильным думать, что один лишь Эллиотт подвергает сомнению необходимость в бедных и несчастных замыканиях. Главным образом, он сетует на то, что так и не увидел после прочтения недавней статьи Брюса Тейта (Bruce Tate) какой-либо ценности в возможном введении замыканий в Java (последний использует для примеров Ruby):

Листинг 1. Простейшее замыкание.

3.times {puts "Inside the times method."}

Результаты:
Inside the times method.
Inside the times method.
Inside the times method.

Здесь times — метод объекта 3, он исполняет код замыкания три раза.

{puts "Inside the times method."}

и есть замыкание. Это анонимная функция, которая, будучи переданной методу times, выводит строку “Inside the times method.” на печать. Данный код является куда более ясным и простым, нежели его альтернатива с применением цикла for:

Листинг 2. Цикл без замыканий.

for i in 1..3
 puts "Inside the times method."
end

Даже я, увидев такое бледное и безжизненное введение в замыкания, с трудом увидел бы их настоящее значение. Первое, что приходит на ум при виде этих примеров: “Да, пожалуй тут есть некий тонкий оттенок”. Остальные примеры из статьи Брюса настолько же тривиальны, неясны и совсем не проливают света на предмет обсуждения.

Я не стану обсуждать претензии Эллиота к коду, написанному на языке Ruby — эта тема не стоит выеденного яйца. Я также обойду стороной как споры о синтаксисе, предложенном для замыканий в Java, так и вопрос о том, вписываются ли они в этот язык на текущей стадии его развития. Я не интересуюсь этим вопросом, и, честно говоря, мне не важно, когда и как эти проблемы будут разрешены, и будут ли они разрешены вообще.

Тем не менее, Эллиотт поднимает действительно важный вопрос: “Почему вы ненавидите цикл for”?

Вот вам распространенный пример:

double sum = 0;
for (int i = 0; i < array.length; i++) {
    sum += array[i];
}

Что он делает? Я занимаюсь программированием на протяжении множества лет, и понимание куска этого кода не займет у меня много времени — это обыкновенное суммирование элементов массива. Однако для того, чтобы прочесть этот пример, я должен последовательно просмотреть около тридцати лексем, распыленных по четырем строкам. Разумеется, при написании этого кода можно было бы воспользоваться синтаксическим сахаром, который сократил бы его объем. Однако суть в том, что есть множество мест, где вы потенциально можете допустить ошибку при написании обычного суммирования.

Желаете доказательств? Пожалуйста, привожу вам следующий же пример из статьи Эллиотта:

String s = "";
for (int i = 0; i < args.length; i++) {
    s += array[i];
}

Замечаете баг? Даже если этот код скомпилируется и пройдет ревизию, могут пройти недели до момента получения первого сообщения об ошибке и еще несколько до выпуска исправления. И это всего-навсего простые циклы for. А теперь представьте, насколько более сложной становится работа в случае с сильно разросшимися, и, быть может, вложенными циклами. (Если вы все еще не беспокоитесь о багах, подумайте об обыкновенных опечатках. А затем подумайте о том, как часто вы пишите подобные циклы.)

Если бы у вас была возможность написать простой цикл for в одну строчку, с меньшим количеством символов, его было бы гораздо легче прочесть. Потому что более краткая форма записи ведет к куда как меньшей вероятности возникновения ошибок в коде, и, когда они все-таки появляются, их (в основном) гораздо проще отловить.

Как в этой ситуации могли бы помочь замыкания? Вот вам первый пример на Haskell:

total = sum array

Ну ладно-ладно, это было не совсем честно. Функция sum не использует замыканий — она определена через свертку (прим. переводчика: английский вариант — fold), которая, в свою очередь, использует замыкания.

total = foldl (+) 0 array

Вот вам второй пример применения замыканий:

s = concat array
s = foldr (++) [] array

Возможно, пример с использованием странно выглядящих функций foldl и foldr для объяснения замыканий не так уж очевиден для программистов, знакомых лишь с циклическими конструкциями. Однако же он подчеркивает главную слабость циклов for — они пытаются объединить в себе три различных операции — фильтрацию, свертывание и преобразование.

Два приведенных выше примера показывают, как можно взять список и свернуть его в один элемент. В мире функционального программирования подобные операции называются свертками. Для своей работы свертка принимает функцию (замыкание), начальное значение (прим. переводчика: далее по тексту — “аккумулятор”) и посещает первый элемент списка. Замыкание применяется к аккумулятору и первому элементу списка, результат кладется в аккумулятор. Затем свертка применяет замыкание к обновленному значению аккумулятора и второму элементу списка. Этот процесс продолжается вплоть до конца списка, когда последнее значение аккумулятора и становится результатом применения свертки.

Вот наглядное объяснение:

s = foldl (+) 0       [1, 2, 3]
 = foldl (+) (0 + 1) [2, 3]
 = foldl (+) 1       [2, 3]
 = foldl (+) (1 + 2) [3]
 = foldl (+) 3       [3]
 = foldl (+) (3 + 3) []
 = foldl (+) 6       []
 = 6

Haskell предоставляет несколько функций-сверток: foldl начинает обработку списка с первого его элемента, и проходит последовательно до последнего элемента; foldr, напротив, начинает с последнего элемента, и движется по направлению к первому элементу. Есть и другие варианты, но эти два являются основными.

Разумеется, свертки являют собой очень примитивные операции, и было бы весьма неразумно выбросить за борт циклы for и заменить их различными fold-образными “заклинаниями”. Вместо этого, более высокоуровневые операции, такие как sum, prod и concat, определены в терминах сверток. Вы, в свою очередь, программируете уже в терминах данных высокоуровневых операций, получая более сжатый код, код, который гораздо проще прочесть, написать и понять.

Однако не каждый цикл представляет собой сворачивание списка в один элемент. Рассмотрим следующий пример:

for (int i = 0; i < array.length; i++) {
    array[i] *= 2;
}

В данном случае мы имеем дело с преобразованием, в функциональных языках это называется map:

new_array = map (*2) array

Функция map посещает каждый элемент списка, применяет к нему [элементу] переданное ей замыкание и создает из возвращаемых замыканием значений новый список. (Некоторые языки вместо создания нового списка замещают старые элементы исходного списка новыми). Такую операцию гораздо проще понять. sort делает нечто похожее, в том смысле, что она принимает список и возвращает новый список (или же модифицирует старый).

Третья разновидность циклов for — фильтрующие циклы. Рассмотрим пример:

int tmp[] = new int [nums.length];
int j = 0;
for (int i = 0; i < nums.length; i++) {
    if ((nums[i] % 2) == 1) {
        tmp[j] = nums[i];
        j++;
    }
}

Очень простой код, смысл которого, тем не менее, почти полностью погребен под излишней сложностью, к которой привело использование цикла for и двух индексов. Если фильтрация является такой же фундаментальной операцией, как fold и map, применение её должно быть настолько же простым, и, вообще говоря, так оно и есть:

odds = filter (i -> (i `mod` 2) == 1) nums
odds = filter odd nums  -- более верно

Вот, собственно говоря, все недостатки цикла for: он объединяет в себе (по меньшей мере) три разновидности операций, и фокусирует внимание на второстепенной детали — прохождение последовательности (индексов) значений. Но на самом деле, свертывание, преобразование и фильтрация — это три различных способа обработки списка и они должны восприниматься по-разному. Использование замыканий в теле цикла позволяет гораздо нагляднее отделить что от как. Я мог бы писать анонимные функции всякий раз, когда мне нужно обработать список, или же использовать функции, написанные до меня (например odd, (+) или sqrt).

Если замыкания не являются эзотерическим инструментом, но глубоко встроены в язык и его стандартную библиотеку, нам не нужно возиться с этими низкоуровневыми операциями (прим. переводчика: здесь имеются в виду map, fold и filter). Вместо этого, мы можем создать высокоуровневые операции, с говорящими названиями, например sum или product.

Кроме того, работа с подобными терминами помогает гораздо легче понимать более сложные операции, такие как преобразование дерева (mapping a tree), фильтрация вектора (filtering a vector) или свертывание списка в хэш (прим. переводчика: не совсем понятно, что имел в виду автор под словами “folding a list into a hash” — сворачивание списка в одно-единственное значение, или функцию получения хэш-таблицы из списка кортежей, имеющуюся в стандартной библиотеке).

В конце концов Эллиотт поразводил руками на тему параллельного исполнения кода на нескольких ядрах, и посетовал на то, что код

3.times {...}

почти наверняка будет параллелиться хуже, чем аналогичный цикл for. Мне кажется, что он упускает из виду одно обстоятельство. Да, есть вычисления, которые должны выполняться последовательно, есть и такие, которые могут выполняться параллельно. Но отделение одних от других является для компилятора сложной задачей, если единственный используемый вами инструмент — цикл for. Если же вы можете разделить последовательные вычисления (то бишь foldl и foldr) и (возможно) параллельные (map и filter), то, тем самым, вы серьезно упрощаете задачу компилятора. Более того, вы даже можете явно запросить последовательную или параллельную версию map, если вы знаете природу обрабатываемых вами данных лучше, чем компилятор.

От переводчика

В тексте частенько проскальзывают упоминания замыканий. Если я правильно понимаю определение замыканий, то нужно сказать, что автор путает анонимные функции и замыкания — в приведенных им примерах отсутствуют функции, работающие с переменными из окружения, не указанными в списке параметров.

Автор: artemgapchenko

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js