Лямбда функции c рекурсия

Добавил пользователь Евгений Кузнецов
Обновлено: 19.09.2024

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

Рассмотрим для начала обычный вариант вычисления факториала, а также уточним, что такое рекурсивная функция.

Рекурсивная функция

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

Вот пример такой бесконечной рекурсивной функции, программа с которой завершается аварийно из-за переполнения стека вызовов.

1. Рекурсивная функция
2. Факториал
3. Применение рекурсивной лямбда функции
1. 1. С применением std::function
2. 2. Без применения std::function
Чтобы такого не происходило, нужно добавить условие выхода из рекурсивной функции, например, достижение счётчика рекурсивных вызовов значения 100.

Теперь рекурсивная функция будет завершаться корректно, благодаря счётчику стек вызовов не будет переполняться и программа завершиться без ошибок.

Факториал

А теперь определимся с тем, что такое факториал.
- 4! = 1 · 2 · 3 · 4 = 24
- 5! = 1 · 2 · 3 · 4 · 5 = 120
Теперь напишем функцию для вычисления факториала

В данном случае функция написана так, чтобы вычисление факториала выполнялось с наибольшего числа и заканчивалось нулём. Тогда будет выполняться корректный выход из рекурсии и функция будет возвращать значение факториала.

В результате код программы для вычисления факториала будет выглядеть так

А теперь применим для вычисления факториала рекурсивную лямбда функцию.

В современных стандартах C++ есть два варианта записи рекурсивных функций:

С применением std::function

В данном случае для применения рекурсии лямбда функция должна знать о своей собственной структуре, чтобы быть способной захватить саму себя по ссылке, но лямбда функция - это анонимное объявление объекта, которое каким-то образом нужно сделать явным. В этом нам поможет std::function, который поможет определить сигнатуру лямбда функции.

Но это не значит, что вовсе нельзя обойтись без явного использования std::function для рекурсивных функций. В стандарте C++14 появилась возможность определять аргументы лямбда функций как auto, за счёт чего лямбда функцию можно передавать в качестве аргумента самой себе по ссылке. Получится та же самая рекурсивная лямбда функция, но с использованием исключительно средств языка программирования C++.

К вопросу о целесообразности применения рекурсивных лямбда функций.

Не имеет смысла объявлять функцию или метод в классе, если эта функция используется в одном единственном месте кода. Это как минимум будет усложнять интерфейс класса, если на каждый чих будем писать новые методы. Гораздо лучше объявить лямбду внутри другого метода, где она должна выполняться. Это касается всех лямбда функций, как обычных, так и рекурсивных.

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

Рекомендуем хостинг TIMEWEB

Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Пожалуйста, посмотрите мою небольшую статью в блоге, где я покажу вам несколько интересных примеров лямбд. Знаете ли вы, как написать рекурсивную лямбду? Хранить их в контейнере? Или вызывать во время компиляции?

Смотрите в статье.

1. Рекурсивная лямбда с помощью std::function

Написать рекурсивную функцию относительно просто: внутри определения функции вы можете вызвать ту же функцию по ее имени. А как насчет лямбд?

Это, к сожалению, не компилируется.

Один из способов - использовать std::function :

На этот раз нам нужно захватить factorial , а затем мы можем ссылаться на него внутри тела лямбды.

Начиная с C++14 мы также можем использовать общие лямбды и написать следующий код:

На этот раз он еще сложнее (но не требует интенсивного использования std::function ). Здесь внутренняя лямбда используется для основного вычисления, а затем она передается как общий аргумент.

Но мне интересно: вы когда-нибудь использовали рекурсивные лямбды? Или лучше полагаться на рекурсивные функции (которые кажутся гораздо более удобными в использовании и написании).

2. constexpr Lambdas

Но это еще не все с рекурсией. :)

Начиная с C++17 мы можем писать лямбды, у которых оператор вызова определен как constexpr. Можно использовать это свойство и расширить рекурсивный пример до:

А в C++20 вы даже можете применять consteval для маркировки лямбд, которые могут быть вычислены только во время компиляции.

3. Хранение лямбд в контейнере

Возможно, это не совсем правильно. но теоретически мы можем хранить лямбды в контейнере.

Хотя у типов замыканий конструкторы по умолчанию удалены (если только это не stateless lambda в C++20), можно сделать небольшой хак и хранить все лямбды как объекты std::function . Например:

4. Общие лямбды и их вывод

C++14 привнес важное дополнение в лямбды: общие лямбда-аргументы. Приведем один пример, который показывает, в чем его польза:

Но начиная с C++14, мы можем воспользоваться автоматическим выводом типов для их возвращения и просто написать:

Приведенный выше код намного проще и экономичнее, поскольку нам не нужно использовать std::function .

Резюме

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

Используете ли вы лямбды в подобных контекстах? А может быть, у вас есть еще более сложные примеры? Поделитесь своим опытом в комментариях под статьей.

На Хабре недавно проскочила ещё одна статья про вычисления на шаблонах C++ от HurrTheDurr. В комментариях к ней лично я увидел вызов:

> С каждым новым релизом количество способов нетривиально вывихнуть себе мозг при помощи С++ продолжает увеличиваться)
> > Особенно, если не менять подход к реализации игрового поля и продолжать пытаться все вычисления выполнять не над константами, а над типами.

А так ли сложно будет написать универсальный вычислитель на типах, более удобный для программирования, чем клеточный автомат? Как оказалось, несложно; я в 30 раз больше времени потратил на эту статью, чем на написание и отладку собственно кода вычислителя.

Чуть раньше AveNat опубликовала введение в лямбда-исчисление в двух частях, так что вдохновение пришло мгновенно. Хотелось, чтобы можно было (образно) писать так:
А на выходе получать такое:
Статья получилась несколько великоватой, так как мне хотелось рассказать обо всех интересных штуках, которые здесь используются. И ещё она требует базового набора знаний о лямбда-исчислении. Приведённых выше обзоров, среднего знания C++ (с шаблонами), и здравого смысла должно быть достаточно для понимания содержимого.

Под катом находится очередное прокомментированное конструктивное доказательство Тьюринг-полноты шаблонов C++ в виде compile-time интерпретатора бестипового лямбда-исчисления (плюс печеньки в виде макросов и рекурсии).

(Так как компиляторы C++03 требуют < асимметричных < угловых < скобок < в < шаблонах >> > > > , а меня в большинстве случаев коробит от их внешнего вида, то для компиляции необходима или поддержка C++11, или sed ':l;s/>>/> >/g;tl' . За исключением части про макросы, в коде не используются никакие другие возможности C++11.)

Синтаксис

Имена переменных можно составлять из нескольких символов: 'foo' . Однако апологеты лямбда-исчисления считают это роскошью. Во-вторых, значение подобных символьных литералов оставляется на усмотрение компилятора (2.14.3/1 ), что в редких случаях может привести к коллизии имён.

Теперь мы можем записывать с помощью шаблонов любые лямбда-термы!

Что дальше?

Не будем изобретать велосипед для записи самих термов, а используем традиционные списки:
Зафиксируем синтаксис лямбда-исчисления:
Далее определим функцию eval , которая будет интерпретировать термы, различая их по синтаксису:
Отлично. Но как реализовать eval-ref ? Откуда интерпретатор узнает значение переменной? Для этого существует такое понятие как окружение (environment). В окружениях сохраняются связи между переменными и их значениями. Поэтому eval на самом деле выглядит так — с дополнительным аргументом:
Теперь вычисление ссылки на переменную определяется просто — это поиск значения переменной в окружении:
Значением абстракции должна быть анонимная функция одного аргумента. Эту функцию вызовет аппликация, когда придёт время. Смысл абстракции состоит в том, чтобы вычислить своё тело exp в окружении, где переменная абстракции var имеет значение переданного аргумента arg . О создании такого окружения позаботится функция bind .Значения остальных переменных могут варьироваться, но конкретно в лямбда-исчислении принято, чтобы они оставались такими же, как и в месте определения абстракции (то есть брались из окружения env ). Из-за свойства сохранения исходного окружения подобные функции называются замыканиями.

Наконец, аппликация — применение значения абстракции fun к значению аргумента arg .Здесь сначала вычисляется абстракция и её аргумент, а потом уже происходит вызов. Соответственно, eval выполняет редукцию лямбда-термов в аппликативном порядке (с вызовом по значению).

Осталось только определить пару функций для работы с окружениями. lookup для поиска значения переменной в окружении и bind для создания новых окружений:
Супер! У нас есть интерпретатор лямбда-исчисления, написанный в чистом функциональном стиле. (Весь исходник.) И он даже работает:

Но что за скобки? И при чём здесь C++?

Глядя на исходный код интерпретатора на Scheme, можно относительно легко догадаться, как писать интерпретатор лямбда-термов на шаблонах C++. Напомню, что сами термы записываются следующими шаблонами:

Шаблонные функции (не те)

Функция-интерпретатор называется Eval . Так как в шаблонах нет функций, то нам придётся обойтись одними шаблонами:

Eval и Apply

Теперь с помощью частичной специализации шаблонов мы можем декларативно описать поведение Eval . Например, вычисление ссылки на переменную — это поиск значения переменной в окружении с помощью функции Lookup (она возвращает значение через result ):
Результат вычисления абстракции — это замыкание, представляемое шаблонным типом Closure . Замыкание сохраняет в себе (анонимную) функцию и окружение определения этой функции:
Результат вычисления аппликации — это применение вычисленного замыкания к вычисленному аргументу (выполняемое функцией Apply ):
Таким образом, Eval определена только для Ref , Lam , App (и окружений вторым аргументом). Вызовы Eval с другими аргументами просто не скомпилируются.

Идём дальше. Замыкания — это просто структуры данных интерпретатора, хранящие два значения (функцию и окружение её определения). Реализуются, естественно, ещё одним шаблоном:
Вся суть лямбда-исчисления сконцентрирована в определении функции Apply . Замыкания вычисляются в окружении своего определения, которое Bind расширяет привязкой аргумента вычисляемой функции к его фактическому значению:(Заметьте, что Apply в принципе можно определить вообще для чего угодно, не только для применения абстракций.)

Lookup и Bind

Осталось разобраться с окружениями. Для начала, неплохо было бы иметь пустое окружение:
Далее, необходимо реализовать механизм расширения окружений с помощью Bind . Этот тип данных определяет новое окружение, в котором переменная Var связана со значением Val , а значения остальных переменных определяются окружением Env :Получили своеобразный связный список на шаблонах.

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

Конец

Вот так в 50 строках мы полностью определили синтаксис и семантику лямбда-исчисления с помощью шаблонов C++, что доказывает Тьюринг-полноту механизма раскрытия шаблонов C++ (при условии неограниченного объёма доступной памяти).

Определение машины Тьюринга (англ.) можно втиснуть в примерно такой же объём строк, но оно всё равно будет более многословным из-за более сложной конструкции. Определение мю-рекурсивных функций (англ.) будет наверняка короче, но ненамного. Интересно было бы ещё посмотреть на реализацию алгоритмов Маркова, но её я не нашёл, оценить размеры исходного кода сложно, а писать самому лень.

Окей, попробуем провести простейшее вычисление, используя полученные возможности (полный код):

Такой способ исполнения программ в общем-то тоже неплох, но хотелось бы поудобнее.

Расширение множества термов

Во-первых, замыкания шаблонного интерпретатора — это его внутренние структуры данных. Им соответствуют только типы C++, но не значения. С ними необходимо работать внутри самого интерпретатора и никогда не выносить за пределы механизма шаблонов. (Поэтому они специально оставлены неопределёнными типами.)

Во-вторых, очевидно, что в случае представления аргументов в виде чисел Чёрча, результат их сложения тоже будет числом Чёрча — функцией двух аргументов, которая N раз применяет первый аргумент ко второму. (Потому-то мы и получили на выходе именно замыкание, как говорит выдача gcc.) Но что нам делать с этой функцией? Ведь в качестве аргументов мы ей можем передавать лишь такие же функции!

Действительно, сейчас наш интерпретатор понимает только чистое лямбда-исчисление, в котором есть лишь абстракции, аппликации и переменные (которые ссылаются на абстракции или аппликации). Синтаксис позволяет составлять лямбда-термы исключительно из этих трёх компонентов. Любое нарушение этого правила приводит к ошибке компиляции.

Чтобы получить возможность расшифровки результатов вычислений, необходимо использовать прикладное лямбда-исчисление — в нём множество термов расширено элементами некоторого предметного множества. В нашем случае это будет множество типов данных C++.

Введём для них соответствующий терм:Он обозначает инъекцию типа T во множество термов лямбда-исчисления.

После расширения синтаксиса необходимо уточнить семантику языка — определить с помощью Eval значение новой синтаксической конструкции. Ну… так как T — это произвольное значение, то Eval о нём известно лишь то, что такое значение существует. Единственный смысл, который можно придать функции в подобных условиях — это тождество:
Теперь мы можем передавать в качестве аргументов числа (представленные типами):Осталось придумать, как передать функцию, и мы сможем превращать числа Чёрча в нормальные числа int . Ведь если N раз применить функцию инкремента к нулю, то в итоге получится натуральное число N.

Представим, что каким-то образом мы смогли это сделать, передав в интерпретатор типы Succ (successor) и Zero . Проследим, что происходит при вызове такой функции:Бинго! Для определения поведения Succ необходимо специализировать Apply для неё! (Подобные преобразования называются дельта-правилами.)

Например, вот так определяется функция инкремента:Возвращаемое значение Apply должно быть типом, объявленным как result . Поэтому результатом инкремента является тип данных, структурно идентичный описанному выше Zero . Это позволяет представить натуральные числа нешаблонными типами данных, сохраняя возможность получить обычный int с соответствующим значением.

Теперь наконец можно вывести результат сложения! (Полный код.)

Глобальное окружение и свободные переменные

Ещё стоит обратить внимание на свободные переменные Unchurch . Они входят в окружение безо всяких Inj вокруг. Это тоже потому, что в памяти интерпретатора эти значения представляются именно таким образом. Inj необходима только для записи их в тексте программ (в лямбда-термах).

Макросы

Никого ещё не достало, что для записи функций нескольких аргументов их необходимо вручную каррировать? И все эти постоянные Ref ?

А между прочим, даже в лямбда-исчислении приняты удобные сокращения:

До После

Давайте реализуем такие же.

Две фазы

До этого момента в жизни наших программ было только одно важное событие — определение их значения с помощью Eval . Теперь к нему прибавится ещё раскрытие макросов с помощью Expand . Всё, что подаётся на вход Eval , сначала необходимо пропустить через Expand . Введём новую удобную функцию Compute , которая объединяет эти действия:
Expand принимает только один аргумент. Будем считать, что это чёрный ящик: на входе программа с макросами, на выходе — без них. В нашем простом случае не нужны какие-либо макроокружения.

Реализация макросов

Теперь макросы, очевидно, необходимо реализовать внутри Expand . Нам нужны некие Lam_ и App_ , которые раскрываются следующим образом:

До После

Lam_ Lam. >>

App_ App<. App, C>, . Z>

App_ App_, . >

В C++11 появились шаблоны произвольной арности, что порядком облегчает задачу. Обладателям компиляторов C++03 остаётся только страдать и писать тысячу и одну специализацию: Lam_2 для двух аргументов, Lam_3 для трёх, App_4 для четырёх, и т. д. Ну, или извращаться ещё сильнее и повторить всё, что показано ниже, с помощью родного препроцессора C++.

А ещё шаблоны C++11 не позволяют смешивать в пачке аргументы-числа и аргументы-типы, поэтому у App_ будет два соответствующих варианта. Печалька.

Реализации App_s (для символов) и App_i (для типов) более объёмные, поэтому объяснения и код спрятаны под спойлер.

Для начала необходимо унифицировать аргументы аппликации. Они могут быть или пачкой имён переменных, или пачкой лямбда-термов. Имена надо превратить в термы. Если бы шаблоны C++11 позволяли написать map для пачек, то было бы проще, а так мы построим ещё один связный список. (А может, map реально написать? Anyone?)

Первый элемент списка RefList надо применить ко второму. Затем к этому результату последовательно применяются остальные элементы. Останавливаемся, когда элементы закончатся (дойдём до Nil ).
Заметили её? Да, это хвостовая рекурсия.

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

Остальное

И последнее, но важное дополнение. Экспандер должен правильно обрабатывать встроенные конструкции языка, раскрывая макросы там, где они могут встретиться:
Кто заметил в работе Expand параллели с Eval и Apply , тот молодец.
(Полный код с поддержкой макросов.)

Рекурсия

Сказав про полноту по Тьюрингу полученного вычислителя, мы как-то обошли стороной один момент, удовлетворившись простой арифметикой. Ведь Тьюринг-полная система позволяет выразить циклы! Рассмотрим циклические вычисления на примере (барабанная дробь) факториала.

В лямбда-исчислении нельзя выразить рекурсию напрямую, так как у абстракций отсутствуют имена. Для записи рекурсии в привычном виде потребуется магический оператор Rec , который подобен обычной абстракции Lam , но создаёт абстракции с дополнительным аргументом — ссылкой на саму определяемую абстракцию.

Однако, хитрые математики нашли способ обойти это ограничение: так называемый Y-комбинатор позволяет выражать рекурсивные функции как решения функциональных уравнений о неподвижных точках. Что это такое и как расшифровывается предыдущее предложение, можете прочитать в другом месте, а сейчас важно, что Y-комбинатор записывается вот так:
Чтобы выразить с его помощью рекурсивную функцию, вычисляющую факториал, сначала нужно определить необходимые для неё математические и логические операторы: умножение, вычитание, сравнение. Также не помешают и более удобный способ записи чисел Чёрча. Все определения можно посмотреть здесь (последние четыре раздела), они являются стандартными определениями подобных функций в лямбда-исчислении. (Если вы осилили чтение до этого момента, то проблем с пониманием их реализации возникнуть не должно.)

Окей, попробуем применить всё это вместе, вычислив (Y F 1) — факториал единички:

Не компилируется. И лог ошибок на 64 килобайта. Почему?

Всё дело в порядке вычислений. Обычный Y-комбинатор записывается из расчёта на нормальный порядок вычислений. В нём кусочек f (x x) сначала вызовет подстановку (x x) в тело f , и только потом, если это понадобится, значение (x x) будет вычислено (тоже с ленивой подстановкой).

В случае аппликативного порядка (вызова по значению) это выражение вычисляется сразу же, что очевидно приводит к бесконечному циклу (если посмотреть, чему должен быть равен аргумент x). Например, интерпретатор лямбда-исчисления на Scheme, показанный ранее, зацикливается.

Если расшифровать лог, выплёвываемый gcc, то там так и написано, что:не определяет типа result , то есть этот вызов не имеет смысла. Компилятор увидел и разорвал бесконечный цикл подстановки шаблонов, который по стандарту является неопределённым (14.7.1/15 ).

Шаблоны C++ тоже проводят вычисления в аппликативном порядке, потому что вызовом функции typename Eval::value является инстанциирование шаблона. Инстанциирование Eval очевидно требует инстанциирования Exp и Env .

В языках с аппликативным порядком вычислений следует применять Z-комбинатор — модификацию Y-комбинатора, в которой выражение (x x) завёрнуто в абстракцию, что предотвращает его преждевременное вычисление:
Теперь ошибок компиляции не видно, равно как и её конца. Очевидно, в этот раз мы перехитрили компилятор и заставили его что-то бесконечно рекурсивно раскрывать. Разумно предположить, что этим чем-то может быть только рекурсивный вызов факториала.

Стоп! А когда компилятор вообще должен прекратить подставлять факториал сам в себя? В смысле, когда мы хотим, чтобы он прекратил так делать? По идее, за это отвечает оператор If : когда аргумент факториала равен нулю, то нужно вернуть единицу, а не пытаться делать рекурсивный вызов. А как определяется If ?

Как абстракция. Вроде бы всё хорошо, стандартное определение для булевых констант Чёрча… Вот только рассчитано оно тоже на нормальный порядок редукции! При аппликативном порядке If вычисляет обе ветки сразу вместе с условием, и только после этого делает выбор.

Проблему можно решить способом, аналогичным Z-комбинатору: завернуть отложенные вычисления в абстракцию. Однако, в случае If условие заворачивать как раз не надо. Поэтому, к сожалению, If не может быть удобной функцией в аппликативных языках. Однако, его можно сделать макросом!
Строго говоря, переменная 'u' не должна совпадать ни с одной свободной переменной Then или Else . Такой возможности (гигиены) наша макросистема не предоставляет. И вообще, имён переменных у нас весьма ограниченное количество. Поэтому зарезервируем идентификатор 0 в качестве ни с чем не совпадающего идентификатора:
Вот теперь наконец-то факториал заработает. (Полный код.)

К сожалению, дождаться вычисления факториала семи мне не удалось, не говоря уже о том, что на 32-битных системах компилятор попросту умирает от переполнения стека. Но всё равно.

Заключение

Лямбда-выражения являются одним из наиболее мощных дополнений в C++11 и продолжают развиваться с каждым новым стандартом языка. В этой статье мы пройдемся по их истории и посмотрим на эволюцию этой важной части современного C++.

Вторая часть доступна по ссылке:
Lambdas: From C++11 to C++20, Part 2

Вступление

Я решил взять код у Томаса (с его разрешения!), описать его и создать отдельную статью.

Мы начнем с изучения C++03 и с необходимости в компактных локальных функциональных выражениях. Затем мы перейдем к C++11 и C++14. Во второй части серии мы увидим изменения в C++17 и даже взглянем на то, что произойдет в C++ 20.

С самого начала STL std::algorithms , такие как std::sort , могли принимать любой вызываемый объект и вызывать его для элементов контейнера. Однако в C++03 это предполагало только указатели на функции и функторы.

Но проблема заключалась в том, что вы должны были написать отдельную функцию или функтор в другой области видимости, а не в области видимости вызова алгоритма.

В качестве потенциального решения вы могли бы подумать о написании локального класса функторов — поскольку C++ всегда поддерживает этот синтаксис. Но это не работает…

Посмотрите на этот код:

Попробуйте скомпилировать его с -std=c++98 , и вы увидите следующую ошибку в GCC:

Если мы посмотрим на N3337 — окончательный вариант C++11, то увидим отдельный раздел для лямбд: [expr.prim.lambda].

Далее к C++11

Вот базовый пример кода, который также показывает соответствующий объект локального функтора:

Вы также можете проверить CppInsights, который показывает, как компилятор расширяет код:

Посмотрите на этот пример:

В этом примере компилятор преобразует:

Во что-то похожее на это (упрощенная форма):

Некоторые определения, прежде чем мы начнем:

Вычисление лямбда-выражения приводит к временному prvalue. Этот временный объект называется объектом-замыканием (closure object).

Тип лямбда-выражения (который также является типом объекта-замыкания) является уникальным безымянным non-union типом класса, который называется типом замыкания (closure type).

Несколько примеров лямбда-выражений:

Поскольку компилятор генерирует уникальное имя для каждой лямбды, узнать его заранее не представляется возможным.

Более того [expr.prim.lambda]:
Тип замыкания, связанный с лямбда-выражением, имеет удаленный ([dcl.fct.def.delete]) конструктор по умолчанию и удаленный оператор присваивания.

Поэтому вы не можете написать:

Это приведет к следующей ошибке в GCC:

Оператор вызова

По умолчанию это встроенный константный метод. Вы можете изменить его, указав mutable после объявления параметров:

Захватив переменную, вы создаете член-копию этой переменной в типе замыкания. Затем внутри тела лямбды вы можете получить к нему доступ.
- [&] — захват по ссылке, все переменные в автоматическом хранилище объявлены в области охвата
- [=] — захват по значению, значение копируется
- [x, & y] — явно захватывает x по значению, а y по ссылке
Вы можете поиграться с полным примером здесь: @Wandbox

Хотя указание [=] или [&] может быть удобно — поскольку оно захватывает все переменные в автоматическом хранилище, более очевидно захватывать переменные явно. Таким образом, компилятор может предупредить вас о нежелательных эффектах (см., например, примечания о глобальных и статических переменных)

И важная цитата:

По умолчанию operator() типа замыкания является константным, и вы не можете изменять захваченные переменные внутри тела лямбда-выражения.
Если вы хотите изменить это поведение, вам нужно добавить ключевое слово mutable после списка параметров:

В приведенном выше примере мы можем изменить значения x и y… но это только копии x и y из прилагаемой области видимости.

Захват глобальных переменных

Если у вас есть глобальное значение, а затем вы используете [=] в лямбде, вы можете подумать, что глобальное значение также захвачено по значению… но это не так.

Поиграть с кодом можно здесь: @Wandbox

Захватываются только переменные в автоматическом хранилище. GCC может даже выдать следующее предупреждение:

Это предупреждение появится только в том случае, если вы явно захватите глобальную переменную, поэтому, если вы используете [=] , компилятор вам не поможет.
Компилятор Clang более полезен, так как генерирует ошибку:

Захват статических переменных

Захват статических переменных аналогичен захвату глобальных:

Поиграть с кодом можно здесь: @Wandbox

И снова, предупреждение появится, только если вы явно захватите статическую переменную, поэтому, если вы используете [=] , компилятор вам не поможет.

Захват члена класса

Знаете ли вы, что произойдет после выполнения следующего кода:

Код объявляет объект Baz, а затем вызывает foo() . Обратите внимание, что foo() возвращает лямбду (хранящуюся в std::function ), которая захватывает член класса.

Поскольку мы используем временные объекты, мы не можем быть уверены, что произойдет, при вызове f1 и f2. Это проблема висячих ссылок, которая порождает неопределенное поведение.

Опять же, если вы укажете захват явно ([s]):

Компилятор предотвратит вашу ошибку:

Move-able-only объекты

Если у вас есть объект, который может быть только перемещен (например, unique_ptr), то вы не можете поместить его в лямбду в качестве захваченной переменной. Захват по значению не работает, поэтому вы можете захватывать только по ссылке… однако это не передаст его вам во владение, и, вероятно, это не то, что вы хотели.

Сохранение констант

Если вы захватываете константную переменную, то константность сохраняется:

Возвращаемый тип

В C++11 вы можете пропустить trailing возвращаемый тип лямбды, и тогда компилятор выведет его за вас.

Первоначально вывод возвращаемого типа значения был ограничен лямбдами, содержащими один оператор return, но это ограничение было быстро снято, поскольку не было проблем с реализацией более удобной версии.

Таким образом, начиная с C++11, компилятор может вывести тип возвращаемого значения, если все операторы return могут быть преобразованы в один и тот же тип.

Если все операторы return возвращают выражение и типы возвращаемых выражений после преобразования lvalue-to-rvalue (7.1 [conv.lval]), array-to-pointer (7.2 [conv.array]) и function-to-pointer (7.3 [conv.func]) такое же, как у общего типа;

Поиграться с кодом можно здесь: @Wandbox

В вышеприведенной лямбде есть два оператора return , но все они указывают на double , поэтому компилятор может вывести тип.

IIFE — Немедленно вызываемые выражения (Immediately Invoked Function Expression)

В наших примерах я определял лямбду, а затем вызвал ее, используя объект замыкания… но ее также можно вызывать немедленно:

Такое выражение может быть полезно при сложной инициализации константных объектов.

Преобразование в указатель на функцию

Тип замыкания для лямбда-выражения без захвата имеет открытую невиртуальную неявную функцию преобразования константы в указатель на функцию, имеющую тот же параметр и возвращаемые типы, что и оператор вызова функции типа замыкания. Значение, возвращаемое этой функцией преобразования, должно быть адресом функции, которая при вызове имеет тот же эффект, что и вызов оператора функции типа сходного с типом замыкания.

Другими словами, вы можете преобразовывать лямбды без захватов в указатель на функцию.

Поиграться с кодом можно здесь: @Wandbox

Улучшения в C++14

C++14 добавил два значительных улучшения в лямбда-выражения:
- Захваты с инициализатором
- Общие лямбды
Возвращаемый тип

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

Возвращаемый тип лямбды — auto, который заменяется trailing возвращаемым типом, если он предоставляется и/или выводится из операторов возврата, как описано в [dcl.spec.auto].

Захваты с инициализатором

Короче говоря, мы можем создать новую переменную-член типа замыкания и затем использовать ее внутри лямбда-выражения.

Это может решить несколько проблем, например, с типами, доступными только для перемещения.

Перемещение

Теперь мы можем переместить объект в член типа замыкания:

Оптимизация

Другая идея состоит в том, чтобы использовать его как потенциальную технику оптимизации. Вместо того, чтобы вычислять какое-то значение каждый раз, когда мы вызываем лямбду, мы можем вычислить его один раз в инициализаторе:

Захват переменной-члена

Инициализатор также можно использовать для захвата переменной-члена. Затем мы можем получить копию переменной-члена и не беспокоиться о висячих ссылках.

Поиграться с кодом можно здесь: @Wandbox

В foo() мы захватываем переменную-член, копируя ее в тип замыкания. Кроме того, мы используем auto для вывода всего метода (ранее, в C++11 мы могли использовать std::function ).

Обобщенные лямбда-выражения

Еще одно существенное улучшение — это обобщенная лямбда.
Начиная с C++14 можно написать:

Это эквивалентно использованию объявления шаблона в операторе вызова типа замыкания:

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

В этой статье мы начали с первых дней лямбда-выражений в C++03 и C++11 и перешли к улучшенной версии в C++14.

Вы увидели, как создавать лямбду, какова основная структура этого выражения, что такое список захвата и многое другое.

В следующей части статьи мы перейдем к C++17 и познакомимся с будущими фичами C++20.

Вторая часть доступна здесь:

Мой любимый инструмент в C++ - это лямбда функции, хотя как-то мне говорили, что они кажутся страшными. На самом деле они прелестны. Они значительно упрощают написание программ и позволяют делать довольно интересные решения.

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

Возможные варианты синтаксиса лямбда функций

Первый вариант является полным, но не запрещается использовать сокращённые вариации записи функций.
- capture - список внешних захватываемых объектов, они могут захватываться как по ссылке, так и копированием.
- params - список параметров, передаваемых в лямбда функции, данная часть будет аналогична записи аргументов для обычных функций.
- mutable - использование mutable позволяет модифицировать копии объектов, которые были захвачены копированием. В обычном варианте они не будут модифицироваться.
- exception - обеспечивает спецификацию исключения, то есть лямбда функции также как и обычные функции могут выкидывать исключения.
- attribute - обеспечивает спецификацию атрибута, таких атрибутов в спецификации C++ определено всего два ([[noreturn]], [[carries_dependency]])
- params - список параметров, передаваемых в лямбда функцию
- ret - возвращаемое значение лямбда функции
Что касается возвращаемого значение, то оно может автоматически выводиться из типа объекта, который возвращается оператором return. Если же в лямбда-функции отсутствует оператор return, то возвращаемое значение будет void.

Лямбда функция создаёт безымянный временный объект уникального безымянного non-union, non-aggregate типа, известного как тип замыкания. Благодаря введению оператора auto в современном стандарте C++ можно объявить объект лямбда функции довольно легко, без прописывания объявления функтора ( std::function ) со всеми апраметрами и возвращаемыми значениями, что делает код более простым и читаемым (для опытного программиста, конечно. Безусловно нужно учитывать то, что новичок быстрее заподозрит неладное, если в объявлении лямбды будет фигурировать std::function, но это уже вопрос практики).

Вот пример объявления простой лямбда функции, которая будет возвращать тип void , поскольку отсутствует хотя бы один оператор return .

Соответственно программный код не скомпилируется, если в лямда-функции будет присутствовать два и более оператора return, которые будут возвращать объекты разных типов, не связанных между собой иерархией наследования и не способные быть приведены к типу базового класса. И даже, если эти объекты имеют базовый класс, необходимо будет прописать тип возвращаемого значения, им как раз будет указатель на объект базового класса (в общем случае).

Вот пример кода, который не скомпилируется.

Нужно указать тип возвращаемого значения

Также ошибка компиляции будет в том случае, если не указать тип возвращаемого значения и при этом вы создаёте в куче объект внутри лямбда функции, но в некоторых случаях можете вернуть указатель на nullptr. То есть ниже следующий код не скомпилируется.

Опять нужно указать тип возвращаемого значения

Дело в том, что nullptr - это универсальный тип данных, который в каком-то смысле не является типом данных, поскольку его нельзя установить в качестве типа переменной. Но он может быть присвоен в качестве значения указателю на объект. Чтобы неявное преобразование в данном случае происходило правильно, нужно также указать тип возвращаемого значения.

Также в выше приведённом примере показано, как вызвать лямда функцию и передать в неё параметры. Заметили? В данном примере используется параметр int type , в зависимости от которого мы возвращаем указатель на созданный объект или nullptr .

Также в лямбда функциях присутствует понятие захвата переменных. Это означает, что лямбда функция может использовать не только переменные, которые передаются ей в качестве параметров, но и какие-либо объекты, которые были объявлены вне лямда-функции.

Список символов может быть передан следующим образом:
- где a захвачена по значению, а b захвачена по ссылке.
- захватывает указатель по значению.
- захват всех символов по ссылке
- захват всех символов по значению
- ничего не захватывает
Про захват переменных поговорим в следующих статьях.

Но отмечу один интересный момент, лямда-функцию можно вызвать сразу же там, где вы её и объявили, если добавить после тела лямда функции круглые скобки и передать все необходимые параметры, если они имеются.

Например такой код тоже скомпилируется

Так что подумайте, скомпилируется ли следующий программный код?

Рекомендуем хостинг TIMEWEB

Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Читайте также: