Scala. Профессиональное программирование 2022. Одерски Мартин, Спун Лекс, Веннерс Билл, Соммерс ФрэнкО41 Scala. Профессиональное программирование. 5е изд спб. Питер, 2022. 608 с. ил. Серия Библиотека программиста
 Скачать 6.24 Mb.
|
|
184 Глава 8 • Функции и замыкания Затем вы можете определить метод, который примет Increaser : def increaseOne(increaser: Increaser): Int = increaser.increase(1) Чтобы вызвать ваш новый метод, необходимо передать анонимный экзем пляр типажа Increaser , например: increaseOne( new Increaser: def increase(i: Int): Int = i + 7 ) Однако, начиная с версии 2.12 и выше, в Scala можно просто использовать функциональный литерал, потому что Increaser относится к типу SAM: increaseOne(i => i + 7) // Scala 8 .10 . Хвостовая рекурсия В разделе 7.2 упоминалось, что для преобразования цикла while , который обновляет значение var переменных в код более функционального стиля, ис пользующий только val переменные, обычно нужно прибегнуть к рекурсии. Рассмотрим пример рекурсивной функции, которая вычисляет приблизи тельное значение, повторяя уточнение приблизительного расчета, пока не будет получен приемлемый результат: def approximate(guess: Double): Double = if isGoodEnough(guess) then guess else approximate(improve(guess)) С соответствующими реализациями isGoodEnough и improve подобные функ ции часто используются при решении задач поиска. Если нужно, чтобы функция approximate выполнялась быстрее, может возникнуть желание написать ее с циклом while : def approximateLoop(initialGuess: Double): Double = var guess = initialGuess while !isGoodEnough(guess) do guess = improve(guess) guess Какая из двух версий approximate более предпочтительна? Если требуется лаконичность и нужно избавиться от использования var переменных, то вы играет первый, функциональный вариант. Но, может быть, более эффектив 8 .10 . Хвостовая рекурсия 185 ным окажется императивный подход? На самом деле, если измерить время выполнения, окажется, что они практически одинаковы! Этот результат может показаться неожиданным, поскольку рекурсивный вызов выглядит намного более затратным, чем простой переход из конца цикла в его начало. Но в показанном ранее вычислении приблизительного значения компилятор Scala может применить очень важную оптимизацию. Обратите внимание на то, что в вычислении тела функции approximate рекурсивный вызов стоит в самом конце. Функции наподобие approximate , которые в качестве последнего действия вызывают сами себя, называются функциями с хвостовой рекурсией. Компилятор Scala обнаруживает хвосто вую рекурсию и заменяет ее переходом к началу функции после обновления параметров функции новыми значениями. Из этого можно сделать вывод, что избегать использования рекурсивных алгоритмов для решения ваших задач не стоит. Зачастую рекурсивное реше ние выглядит более элегантно и лаконично, чем решение на основе цикла. Если в решении задействована хвостовая рекурсия, то расплачиваться за него издержками производительности во время выполнения программы не придется. Трассировка функций с хвостовой рекурсией Для каждого вызова функции с хвостовой рекурсией новый фрейм стека создаваться не будет, все вызовы станут выполняться с использованием одного и того же фрейма. Это обстоятельство может вызвать удивление у программиста, который исследует трассировку стека программы, давшей сбой. Например, данная функция вызывает себя несколько раз и генерирует исключение: def boom(x: Int): Int = if x == 0 then throw new Exception("boom!") else boom(x - 1) + 1 Эта функция не относится к функциям с хвостовой рекурсией, поскольку после рекурсивного вызова выполняет операцию инкремента. При ее запуске будет получен вполне ожидаемый результат: scala> boom(3) java.lang.Exception: boom! at .boom( at .boom( at .boom( 186 Глава 8 • Функции и замыкания at .boom( at . Если теперь внести изменения в boom так, чтобы в ней появилась хвостовая рекурсия: def bang(x: Int): Int = if x == 0 then throw new Exception("bang!") else bang(x - 1) то получится следующий результат: scala> bang(5) java.lang.Exception: bang! at .bang( at . На сей раз вы видите только фрейм стека для bang . Можно подумать, bang дает сбой перед своим собственным вызовом, но это не так. Оптимизация хвостового вызова Код, скомпилированный для approximate , по сути, такой же, как и код, скомпилированный для approximateLoop . Обе функции компилиру ются в одни и те же 13 инструкций байткода Java. Если просмотреть байткоды, сгенерированные компилятором Scala для метода с хвосто вой рекурсией approximate , то можно увидеть, что, хотя и isGoodEnough , и improve вызываются в теле метода, approximate там не вызывается. При оптимизации компилятор Scala убирает рекурсивный вызов: public double approximate(double); Code: 0: aload_0 1: astore_3 2: aload_0 3: dload_1 4: invokevirtual #24; //метод isGoodEnough:(D)Z 7: ifeq 12 10: dload_1 11: dreturn 12: aload_0 13: dload_1 14: invokevirtual #27; //метод improve:(D)D 17: dstore_1 18: goto 2 8 .10 . Хвостовая рекурсия 187 Обычно вы добавляете аннотацию scala.annotation.tailrec к методу, ко торый должен быть хвостовой рекурсией, например, когда вы ожидаете, что рекурсия может зайти очень далеко. Чтобы убедиться, что компилятор Scala выполняет оптимизацию хвостовой рекурсии, вы можете добавить @tailrec перед определением метода. В случае невозможности оптимизации компи лятор выдаст ошибку и объяснение, почему она возникла. Ограничения хвостовой рекурсии Использование хвостовой рекурсии в Scala строго ограничено, поскольку набор инструкций виртуальной машины Java (JVM) существенно затруд няет реализацию более сложных форм хвостовых рекурсий. Оптимизация в Scala касается только непосредственных рекурсивных вызовов той же са мой функции, из которой выполняется вызов. Если рекурсия косвенная, как в следующем примере, где применяются две взаимно рекурсивные функции, то ее оптимизация невозможна: def isEven(x: Int): Boolean = if x == 0 then true else isOdd(x — 1) def isOdd(x: Int): Boolean = if x == 0 then false else isEven(x — 1) Получить оптимизацию хвостового вызова невозможно и в том случае, если завершающий вызов делается в отношении функционального значения. Рас смотрим, к примеру, такой рекурсивный код: val funValue = nestedFun def nestedFun(x: Int): Unit = if x != 0 then println(x) funValue(x — 1) Переменная funValue ссылается на функциональное значение, которое, по сути, заключает в себе вызов функции nestedFun . В момент применения функционального значения к аргументу все изменяется и nestedFun при меняется к тому же самому аргументу, возвращая результат. Поэтому вы можете понадеяться на то, что компилятор Scala выполнит оптимизацию хвостового вызова, но в данном случае этого не произойдет. Оптимизация хвостовых вызовов ограничивается ситуациями, когда метод или вложенная функция вызывают сами себя непосредственно в качестве своей последней операции, не обращаясь к функциональному значению или через какогото другого посредника. (Если вы еще не усвоили, что такое хвостовая рекурсия, то перечитайте раздел 8.10.) 188 Глава 8 • Функции и замыкания Резюме В данной главе мы представили довольно подробный обзор использования функций в Scala. Кроме методов, этот язык предоставляет локальные функ ции, функциональные литералы и функциональные значения. В дополнение к обычным вызовам функций в Scala используются частично примененные функции и функции с повторяющимися параметрами. При благоприятной возможности вызовы функций реализуются в виде оптимизированных хвостовых вызовов, благодаря чему многие привлекательные рекурсивные функции выполняются практически так же быстро, как и оптимизированные вручную версии, использующие циклы while . В следующей главе на основе этих положений мы покажем, как имеющаяся в Scala расширенная поддерж ка функций помогает абстрагировать процессы управления. 9 Управляющие абстракции В главе 7 мы отметили, что встроенных управляющих абстракций в Scala не так уж много, поскольку этот язык позволяет вам создавать собственные управляющие абстракции. В предыдущей главе мы рассмотрели функцио нальные значения. В этой покажем способы применения функциональных значений в целях создания новых управляющих абстракций. Попутно рас смотрим карринг и передачу параметров по имени. 9 .1 . Сокращение повторяемости кода Каждую функцию можно разделить на общую часть, одинаковую для всех вызовов функции, и особую часть, которая может варьироваться от одного вызова функции к другому. Общая часть находится в теле функции, а особая должна предоставляться через аргументы. Когда в качестве аргумента ис пользуется функциональное значение, особая часть алгоритма сама по себе является еще одним алгоритмом! При каждом вызове такой функции ей можно передавать в качестве аргумента другое функциональное значение, и вызванная функция в этом случае будет вызывать переданное функцио нальное значение. Такие функции высшего порядка, то есть функции, которые получают функции в качестве параметров, обеспечивают вам дополнитель ные возможности по сокращению и упрощению кода. Одним из преимуществ функций высшего порядка является то, что они пре доставляют вам возможность создавать управляющие абстракции, которые позволяют избавиться от повторяющихся фрагментов кода. Предположим, вы создаете браузер файлов и должны разработать API, разрешающий поль зователям искать файлы, соответствующие какомулибо критерию. Сначала 190 Глава 9 • Управляющие абстракции вы добавляете средство поиска тех файлов, чьи имена заканчиваются кон кретной строкой. Это даст пользователям возможность найти, к примеру, все файлы с расширением .scala . Такой API можно создать путем определения публичного метода filesEnding внутри следующего объектаодиночки: object FileMatcher: private def filesHere = (new java.io.File(".")).listFiles def filesEnding(query: String) = for file <- filesHere if file.getName.endsWith(query) yield file Метод filesEnding получает список всех файлов, находящихся в текущем каталоге, применяя приватный вспомогательный метод filesHere , затем фильтрует этот список по признаку, завершается ли имя файла тем содер жимым, которое указано в пользовательском запросе. Поскольку filesHere является приватным методом, то метод filesEnding — единственный до ступный метод, определенный в FileMatcher , то есть в API, который вы предлагаете своим пользователям. Пока все идет неплохо — повторяющегося кода нет. Но чуть позже вы хотите разрешить пользователям искать по любой части имени файла. Такой поиск пригодится, когда пользователи не смогут вспомнить, как именно они на звали файл, phb-important.doc , joyful-phb-report.doc , may2020salesdoc.phb или совершенно иначе, и единственное, в чем они уверены, — что гдето в имени фигурирует phb . Вы возвращаетесь к работе и к FileMatcher API добавляете соответствующую функцию: def filesContaining(query: String) = for file <- filesHere if file.getName.contains(query) yield file Данная функция работает точно так же, как и filesEnding . Она ищет теку щие файлы с помощью filesHere , проверяет имя и возвращает файл, если его имя соответствует критерию поиска. Единственное отличие — функция использует метод contains вместо метода endsWith . Проходит несколько месяцев, и программа набирает популярность. Со временем вы уступае те просьбам некоторых активных пользователей, желающих вести поиск с помощью регулярных выражений. У этих нерадивых пользователей об разовались огромные каталоги с тысячами файлов, и им хочется получить возможность искать все pdf файлы, в названии которых имеется сочетание oopsla . Чтобы позволить им сделать это, вы создаете следующую функцию: def filesRegex(query: String) = for file <- filesHere if file.getName.matches(query) yield file 9 .1 . Сокращение повторяемости кода 191 Опытные программисты могут обратить внимание на все допущенные повто рения и удивиться тому, что они не были сведены в общую вспомогательную функцию. Но если подходить к решению этой задачи в лоб, то ничего не получится. Можно было бы придумать следующее: def filesMatching(query: String, method) = for file <- filesHere if file.getName.method(query) yield file В некоторых динамичных языках такой подход сработал бы, но в Scala не разрешается вставлять подобный код во время выполнения. Что же делать? Ответ дают функциональные значения. Передавать имя метода в качестве значения нельзя, но точно такой же эффект можно получить, если передать функциональное значение, вызывающее для вас этот метод. В этом случае к методу, единственной задачей которого будет проверка соответствия имени файла запросу, добавляется параметр matcher : def filesMatching(query: String, matcher: (String, String) => Boolean) = for file <- filesHere if matcher(file.getName, query) yield file В данной версии метода условие if теперь использует параметр matcher для проверки соответствия имени файла запросу. Что именно проверяется, зависит от того, что указано в качестве matcher . А теперь посмотрите на тип самого этого параметра. Это функция, вследствие чего в типе имеется обозна чение => . Функция получает два строковых аргумента, имя файла и запрос, и возвращает булево значение, следовательно, типом этой функции является (String, String) => Boolean Располагая новым вспомогательным методом по имени filesMatching , мож но упростить три поисковых метода, заставив их вызывать вспомогательный метод, передавая в него соответствующую функцию: def filesEnding(query: String) = filesMatching(query, _.endsWith(_)) def filesContaining(query: String) = filesMatching(query, _.contains(_)) def filesRegex(query: String) = filesMatching(query, _.matches(_)) Функциональные литералы, показанные в данном примере, задействуют синтаксис заместителя, рассмотренный в предыдущей главе, который может 192 Глава 9 • Управляющие абстракции быть вам еще не совсем привычен. Поэтому поясним, как применяются за местители: функциональный литерал _.endsWith(_) , используемый в методе filesEnding , означает то же самое, что и следующий код: (fileName: String, query: String) => fileName.endsWith(query) Поскольку filesMatching получает функцию, требующую два String аргу мента, то типы аргументов указывать не нужно — можно просто воспользо ваться кодом (filename, query) => filename.endsWith(query) . А так как в теле функции каждый из параметров используется только раз (то есть первый параметр, filename , применяется в теле первым, второй параметр, query , — вторым), можно прибегнуть к синтаксису заместителей — _.endsWith(_) Первый знак подчеркивания станет заместителем для первого параметра — имени файла, а второй — заместителем для второго параметра — строки запроса. Этот код уже упрощен, но может стать еще короче. Обратите внимание: ар гумент query передается filesMatching , но данная функция ничего с ним не делает, за исключением того, что передает его обратно переданной функции matcher . Такая передача тудасюда необязательна, поскольку вызывающий код с самого начала знает о query ! Это позволяет удалить параметр query как из filesMatching , так и из matcher , упростив код до состояния, показанного в листинге 9.1. Листинг 9.1. Использование замыканий для сокращения повторяемости кода object FileMatcher: private def filesHere = (new java.io.File(".")).listFiles private def filesMatching(matcher: String => Boolean) = for file <- filesHere if matcher(file.getName) yield file def filesEnding(query: String) = filesMatching(_.endsWith(query)) def filesContaining(query: String) = filesMatching(_.contains(query)) def filesRegex(query: String) = filesMatching(_.matches(query)) В этом примере показан способ, позволяющий функциям первого класса помочь вам избавиться от дублирующегося кода, что без них сделать было бы очень трудно. В Java, к примеру, можно создать интерфейс, который со держит метод, получающий одно String значение и возвращающий значение 9 .2 . Упрощение клиентского кода 193 типа Boolean , а затем создать и передать функции filesMatching экземпля ры анонимного внутреннего класса, реализующие этот интерфейс. Такой подход позволит избавиться от дублирующегося кода, чего, собственно, вы и добивались, но в то же время приведет к добавлению чуть ли не большего количества нового кода. Стало быть, цена вопроса сведет на нет все преиму щества и лучше будет, вероятно, смириться с повторяемостью кода. Кроме того, данный пример показывает, как замыкания способны помочь сократить повторяемость кода. Функциональные литералы, использованные в предыдущем примере, такие как _.endsWith(_) и _.contains(_) , во время выполнения программы становятся экземплярами функциональных значе ний, которые не являются замыканиями, поскольку не захватывают никаких свободных переменных. К примеру, обе переменные, использованные в вы ражении _.endsWith(_) , представлены в виде знаков подчеркивания, следо вательно, берутся из аргументов функции. Таким образом, в _.endsWith(_) задействуются не свободные, а две связанные переменные. В отличие от этого, в функциональном литерале _.endsWith(query) , использованном в са мом последнем примере, содержатся одна связанная переменная, а именно аргумент, представленный знаком подчеркивания, и одна свободная перемен ная по имени query . Возможность убрать параметр query из filesMatching в этом примере, тем самым еще больше упростив код, появилась у вас только потому, что в Scala поддерживаются замыкания. 9 .2 . Упрощение клиентского кода В предыдущем примере было показано, что применение функций высшего порядка способствует сокращению повторяемости кода по мере реализации API. Еще один важный способ использовать функции высшего порядка — поместить их в сам API с целью повысить лаконичность клиентского кода. Хорошим примером могут послужить методы организации циклов специ ального назначения, принадлежащие имеющимся в Scala типам коллекций 1 Многие из них перечислены в табл. 3.1, но сейчас, чтобы понять, почему эти методы настолько полезны, внимательно рассмотрите только один пример. Рассмотрим exists — метод, определяющий факт наличия переданного значения в коллекции. Разумеется, искать элемент можно, инициализировав var переменную значением false и выполнив перебор элементов коллекции, 1 Эти специализированные методы циклической обработки определены в трейте Iterable , который является расширением классов List , Set и Map . Более подробно данный вопрос рассматривается в главе 15. |