Lambda retornando: isso é legal?

124

Considere este programa bastante inútil:

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

Basicamente, estamos tentando fazer um lambda que retorne a si próprio.

  • MSVC compila o programa e é executado
  • O gcc compila o programa e segfaults
  • clang rejeita o programa com uma mensagem:

    error: function 'operator()<(lambda at lam.cpp:6:13)>' with deduced return type cannot be used before it is defined

Qual compilador está certo? Existe uma violação de restrição estática, UB ou nenhuma?

Atualize que esta leve modificação é aceita pelo clang:

  auto it = [&](auto& self, auto b) {
          std::cout << (a + b) << std::endl;
          return [&](auto p) { return self(self,p); };
  };
  it(it,4)(6)(42)(77)(999);

Atualização 2 : Entendo como escrever um functor que retorne a si próprio, ou como usar o combinador Y, para conseguir isso. Esta é mais uma questão de advogado de linguagem.

Atualização 3 : a questão não é se é legal para um lambda retornar em geral, mas sobre a legalidade dessa maneira específica de fazer isso.

Pergunta relacionada: C ++ lambda retornando a si próprio .

n. 'pronomes' m.
fonte
2
clang parece mais decente neste momento, eu me pergunto se esse construto pode até checar, mais provavelmente ele acaba em uma árvore infinita.
bipll 5/09/18
2
Seu perguntando se é legal que diz que esta é uma questão da língua-advogado, mas várias das respostas realmente não tomar essa abordagem ... é importante para obter as tags direita
Shafik Yaghmour
2
@ ShafikYaghmour Obrigado, adicionou uma tag
n. 'pronomes' m.
1
@ArneVogel sim, o atualizado usa o auto& selfque elimina o problema de referência pendente.
n. 'pronomes' m.
1
@TheGreatDuck, as lambdas C ++ não são realmente expressões teóricas lambda. O C ++ possui tipos recursivos internos que o cálculo lambda de digitação simples original não pode expressar, portanto, pode ter coisas isomórficas para a: a-> a e outras construções impossíveis.
n. 'pronomes' m.

Respostas:

68

O programa está mal formado (clang está correto) por [dcl.spec.auto] / 9 :

Se o nome de uma entidade com um tipo de espaço reservado não reduzido aparecer em uma expressão, o programa está incorreto. Depois que uma instrução de retorno não descartada é vista em uma função, no entanto, o tipo de retorno deduzido dessa instrução pode ser usado no restante da função, inclusive em outras instruções de retorno.

Basicamente, a dedução do tipo de retorno do lambda interno depende de si mesma (a entidade que está sendo nomeada aqui é o operador de chamada) - portanto, você deve fornecer explicitamente um tipo de retorno. Nesse caso em particular, isso é impossível, porque você precisa do tipo de lambda interno, mas não pode nomeá-lo. Mas há outros casos em que tentar forçar lambdas recursivas como essa pode funcionar.

Mesmo sem isso, você tem uma referência pendente .


Deixe-me elaborar um pouco mais, depois de discutir com alguém muito mais inteligente (ou seja, TC) Há uma diferença importante entre o código original (um pouco reduzido) e a nova versão proposta (da mesma forma reduzida):

auto f1 = [&](auto& self) {
  return [&](auto) { return self(self); } /* #1 */ ; /* #2 */
};
f1(f1)(0);

auto f2 = [&](auto& self, auto) {
  return [&](auto p) { return self(self,p); };
};
f2(f2, 0);

E é para isso que a expressão interior self(self)não é dependente f1, mas self(self, p)é dependente f2. Quando expressões não são dependentes, elas podem ser usadas ... avidamente ( [temp.res] / 8 , por exemplo, como static_assert(false)é um erro grave , independentemente de o modelo em que se encontrar ser instanciado ou não).

Pois f1, um compilador (como, digamos, clang) pode tentar instanciar isso ansiosamente. Você conhece o tipo deduzido do lambda externo quando chega ao ;ponto #2acima (é o tipo do lambda interno), mas estamos tentando usá-lo mais cedo do que isso (pense nisso como no ponto #1) - estamos tentando para usá-lo enquanto ainda estamos analisando o lambda interno, antes de sabermos qual é o tipo. Isso afeta o dcl.spec.auto/9.

No entanto, f2não podemos tentar instanciar ansiosamente, porque é dependente. Só podemos instanciar no ponto de uso, momento em que sabemos tudo.


Para realmente fazer algo assim, você precisa de um combinador-y . A implementação do artigo:

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

E o que você quer é:

auto it = y_combinator([&](auto self, auto b){
    std::cout << (a + b) << std::endl;
    return self;
});
Barry
fonte
Como você especificaria o tipo de retorno explicitamente? Eu não consigo entender.
precisa saber é o seguinte
@ Rakete1111 Qual deles? No original, você não pode.
Barry
Ah ok. Eu não sou um nativo, mas "então você tem que fornecer explicitamente um tipo de retorno" parece implicar que há uma maneira, é por isso que eu estava pedindo :)
Rakete1111
4
O @PedroA stackoverflow.com/users/2756719/tc é um colaborador do C ++. Ele também não é um IA ou tem recursos suficientes para convencer um humano que também conhece C ++ a participar da recente mini-reunião do LWG em Chicago.
Casey
3
@Casey Ou talvez o ser humano está apenas repetindo o que a AI disse a ele ... nunca se sabe;)
TC
34

Edit : Parece haver alguma controvérsia sobre se essa construção é estritamente válida de acordo com a especificação C ++. A opinião predominante parece ser que não é válida. Veja as outras respostas para uma discussão mais aprofundada. O restante desta resposta se aplica se a construção for válida; o código aprimorado abaixo funciona com o MSVC ++ e o gcc, e o OP publicou mais códigos modificados que também funcionam com o clang.

Esse é um comportamento indefinido, porque o lambda interno captura o parâmetro selfpor referência, mas selffica fora do escopo após a returnlinha 7. Assim, quando o lambda retornado é executado posteriormente, ele acessa uma referência a uma variável que saiu do escopo.

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self); // <-- using reference to 'self'
      };
  };
  it(it)(4)(6)(42)(77)(999); // <-- 'self' is now out of scope
}

A execução do programa valgrindilustra isso:

==5485== Memcheck, a memory error detector
==5485== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5485== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5485== Command: ./test
==5485== 
9
==5485== Use of uninitialised value of size 8
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485== 
==5485== Invalid read of size 4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  Address 0x4fefffdc4 is not stack'd, malloc'd or (recently) free'd
==5485== 
==5485== 
==5485== Process terminating with default action of signal 11 (SIGSEGV)
==5485==  Access not within mapped region at address 0x4FEFFFDC4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  If you believe this happened as a result of a stack
==5485==  overflow in your program's main thread (unlikely but
==5485==  possible), you can try to increase the size of the
==5485==  main thread stack using the --main-stacksize= flag.
==5485==  The main thread stack size used in this run was 8388608.

Em vez disso, você pode alterar o lambda externo para se auto-referenciar em vez de em valor, evitando várias cópias desnecessárias e resolvendo o problema:

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto& self) { // <-- self is now a reference
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

Isso funciona:

==5492== Memcheck, a memory error detector
==5492== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5492== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5492== Command: ./test
==5492== 
9
11
47
82
1004
TypeIA
fonte
Eu não estou familiarizado com lambdas genéricas, mas você não poderia fazer selfuma referência?
François Andrieux
@ FrançoisAndrieux Sim, se você fizer selfuma referência, este problema vai embora , mas Clang ainda o rejeita por outra razão
Justin
@ FrançoisAndrieux De fato, e eu adicionei isso à resposta, obrigado!
TypeIA
O problema com essa abordagem é que ela não elimina possíveis erros do compilador. Talvez deva funcionar, mas a implementação está quebrada.
Shafik Yaghmour
Obrigado, eu olhei para isso por horas e não vi que selfé capturado por referência!
n. 'pronomes' m.
21

TL; DR;

clang está correto.

Parece que a seção do padrão que torna este mal formado é [dcl.spec.auto] p9 :

Se o nome de uma entidade com um tipo de espaço reservado não reduzido aparecer em uma expressão, o programa está incorreto. Depois que uma instrução de retorno não descartada é vista em uma função, no entanto, o tipo de retorno deduzido dessa instrução pode ser usado no restante da função, inclusive em outras instruções de retorno. [Exemplo:

auto n = n; // error, n’s initializer refers to n
auto f();
void g() { &f; } // error, f’s return type is unknown

auto sum(int i) {
  if (i == 1)
    return i; // sum’s return type is int
  else
    return sum(i-1)+i; // OK, sum’s return type has been deduced
}

Exemplo final]

Trabalho original através

Se examinarmos a proposta A Proposta para adicionar o Y Combinator à biblioteca padrão, ela fornece uma solução funcional:

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

e diz explicitamente que seu exemplo não é possível:

C ++ 11/14 lambdas não incentivam a recursão: não há como referenciar o objeto lambda do corpo da função lambda.

e faz referência a uma discussão na qual Richard Smith alude ao erro que o clang está causando :

Eu acho que isso seria melhor como um recurso de linguagem de primeira classe. Eu fiquei sem tempo para a reunião pré-Kona, mas pretendia escrever um artigo para permitir que um lambda desse um nome (com escopo definido para seu próprio corpo):

auto x = []fib(int a) { return a > 1 ? fib(a - 1) + fib(a - 2) : a; };

Aqui, 'fib' é o equivalente ao lambda's * this (com algumas regras especiais irritantes para permitir que isso funcione, apesar do tipo de fechamento do lambda estar incompleto).

Barry me indicou a proposta de acompanhamento Lambdas recursivas, que explica por que isso não é possível e contorna a dcl.spec.auto#9restrição e também mostra métodos para conseguir isso hoje sem ela:

Lambdas são uma ferramenta útil para refatoração de código local. No entanto, às vezes queremos usar o lambda de dentro dela, para permitir recursão direta ou para permitir que o fechamento seja registrado como uma continuação. Isso é surpreendentemente difícil de se obter bem no C ++ atual.

Exemplo:

  void read(Socket sock, OutputBuffer buff) {
  sock.readsome([&] (Data data) {
  buff.append(data);
  sock.readsome(/*current lambda*/);
}).get();

}

Uma tentativa natural de referenciar um lambda de si mesmo é armazená-lo em uma variável e capturar essa variável por referência:

 auto on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

No entanto, isso não é possível devido a uma circularidade semântica : o tipo da variável automática não é deduzido até depois que a expressão lambda é processada, o que significa que a expressão lambda não pode fazer referência à variável.

Outra abordagem natural é usar uma função std :::

 std::function on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

Essa abordagem é compilada, mas geralmente introduz uma penalidade de abstração: a função std :: pode incorrer em uma alocação de memória e a invocação do lambda normalmente exige uma chamada indireta.

Para uma solução sem custos indiretos, geralmente não existe uma abordagem melhor do que definir explicitamente um tipo de classe local.

Shafik Yaghmour
fonte
@ Cheersandhth.-Alf acabei encontrando a citação padrão depois de ler o jornal por isso não é relevante uma vez que a citação padrão torna claro porque nem abordagem funciona
Shafik Yaghmour
"" Se o nome de uma entidade com um tipo de espaço reservado não reduzido aparecer em uma expressão, o programa está incorreto "Eu não vejo uma ocorrência disso no programa. Embora selfisso não pareça uma entidade.
n. 'pronomes' m
@nm, além de possíveis trechos de redação, os exemplos parecem fazer sentido com a redação e acredito que os exemplos demonstram a questão claramente. Acho que não poderia adicionar mais atualmente para ajudar.
Shafik Yaghmour
13

Parece que o clang está certo. Considere um exemplo simplificado:

auto it = [](auto& self) {
    return [&self]() {
      return self(self);
    };
};
it(it);

Vamos passar por isso como um compilador (um pouco):

  • O tipo de ité Lambda1com um operador de chamada de modelo.
  • it(it); aciona a instanciação do operador de chamada
  • O tipo de retorno do operador de chamada de modelo é auto , portanto, devemos deduzi-lo.
  • Estamos retornando um lambda capturando o primeiro parâmetro do tipo Lambda1 .
  • Esse lambda também possui um operador de chamada que retorna o tipo de chamada self(self)
  • Aviso: self(self)é exatamente o que começamos!

Como tal, o tipo não pode ser deduzido.

Rakete1111
fonte
O tipo de retorno de Lambda1::operator()é simplesmente Lambda2. Então, nessa expressão lambda interna , também é conhecido o tipo de retorno de self(self), uma chamada de . Possivelmente, as regras formais impedem essa dedução trivial, mas a lógica apresentada aqui não. A lógica aqui equivale apenas a uma afirmação. Se as regras formais atrapalham, isso é uma falha nas regras formais. Lambda1::operator()Lambda2
Saúde e hth. #
@ Cheersandhth.-Alf Concordo que o tipo de retorno é Lambda2, mas você sabe que não pode ter um operador de chamada não reduzido apenas porque, porque é isso que você está propondo: Atraso na dedução do tipo de retorno do operador de chamada do Lambda2. Mas você não pode alterar as regras para isso, pois é bastante fundamental.
precisa saber é o seguinte
9

Bem, seu código não funciona. Mas isso faz:

template<class F>
struct ycombinator {
  F f;
  template<class...Args>
  auto operator()(Args&&...args){
    return f(f, std::forward<Args>(args)...);
  }
};
template<class F>
ycombinator(F) -> ycombinator<F>;

Código do teste:

ycombinator bob = {[x=0](auto&& self)mutable{
  std::cout << ++x << "\n";
  ycombinator ret = {self};
  return ret;
}};

bob()()(); // prints 1 2 3

Seu código é UB e mal formado, não é necessário diagnóstico. O que é engraçado; mas ambos podem ser corrigidos independentemente.

Primeiro, o UB:

auto it = [&](auto self) { // outer
  return [&](auto b) { // inner
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};
it(it)(4)(5)(6);

esse é UB, porque o selfvalor externo é capturado por valor, as capturas internas selfpor referência e o retorno é retornado após a outerexecução. Então segfaulting é definitivamente bom.

O conserto:

[&](auto self) {
  return [self,&a](auto b) {
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};

O código permanece incorreto. Para ver isso, podemos expandir as lambdas:

struct __outer_lambda__ {
  template<class T>
  auto operator()(T self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      T self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};
__outer_lambda__ it{a};
it(it);

isso instancia __outer_lambda__::operator()<__outer_lambda__>:

  template<>
  auto __outer_lambda__::operator()(__outer_lambda__ self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};

Então, a seguir, temos que determinar o tipo de retorno de __outer_lambda__::operator().

Passamos por isso linha por linha. Primeiro criamos__inner_lambda__ tipo:

    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };

Agora, olhe lá - seu tipo de retorno é self(self) , ou __outer_lambda__(__outer_lambda__ const&). Mas estamos tentando deduzir o tipo de retorno de __outer_lambda__::operator()(__outer_lambda__).

Você não tem permissão para fazer isso.

Embora, de fato, o tipo de retorno de __outer_lambda__::operator()(__outer_lambda__) não seja realmente dependente do tipo de retorno __inner_lambda__::operator()(int), o C ++ não se importa ao deduzir os tipos de retorno; simplesmente verifica o código linha por linha.

E self(self) é usado antes de deduzi-lo. Programa mal formado.

Podemos corrigir isso ocultando self(self)até mais tarde:

template<class A, class B>
struct second_type_helper { using result=B; };

template<class A, class B>
using second_type = typename second_type_helper<A,B>::result;

int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [self,&a](auto b) {
        std::cout << (a + b) << std::endl;
        return self(second_type<decltype(b), decltype(self)&>(self) );
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

e agora o código está correto e compila. Mas acho que isso é um pouco de hack; basta usar o ycombinator.

Yakk - Adam Nevraumont
fonte
Possivelmente (IDK), essa descrição está correta para as regras formais sobre lambdas. Mas, em termos da reescrita do modelo, o tipo de retorno do modelo lambda interno operator()não pode, em geral, ser deduzido até que seja instanciado (sendo chamado com algum argumento de algum tipo). E assim, uma reescrita manual de máquina para código baseado em modelo funciona muito bem.
Saúde e hth. - Alf
@cheers seu código é diferente; inner é uma classe de modelo no seu código, mas não está no meu ou no código OP. E isso importa, pois os métodos da classe de modelo são instanciados até serem chamados.
Yakk - Adam Nevraumont 5/09/19
Uma classe definida dentro de uma função de modelo é equivalente a uma classe de modelo fora dessa função. É necessário defini-lo fora da função para o código de demonstração quando ele tiver uma função de membro modelada, porque as regras C ++ não permitem um modelo de membro em uma classe local definida pelo usuário. Essa restrição formal não é válida para o que o compilador gera por si próprio.
Saúde e hth. - Alf
7

É fácil reescrever o código em termos das classes que um compilador geraria, ou melhor, deveria gerar para as expressões lambda.

Quando isso é feito, fica claro que o principal problema é apenas a referência pendente e que um compilador que não aceita o código é um tanto desafiado no departamento lambda.

A reescrita mostra que não há dependências circulares.

#include <iostream>

struct Outer
{
    int& a;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner( a, self );    //! Original code has dangling ref here.
    }

    struct Inner
    {
        int& a;
        Outer& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Outer& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

Uma versão totalmente de modelo para refletir a maneira como o lambda interno no código original captura um item de tipo de modelo:

#include <iostream>

struct Outer
{
    int& a;

    template< class > class Inner;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner<Arg>( a, self );    //! Original code has dangling ref here.
    }

    template< class Self >
    struct Inner
    {
        int& a;
        Self& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Self& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

Eu acho que é esse modelo no mecanismo interno, que as regras formais são projetadas para proibir. Se eles proibirem a construção original.

Felicidades e hth. - Alf
fonte
Veja, o problema é que template< class > class Inner;o modelo operator()é ... instanciado? Bem, palavra errada. Escrito? ... durante Outer::operator()<Outer>antes da dedução do tipo de retorno do operador externo. E Inner<Outer>::operator()tem um chamado para Outer::operator()<Outer>si. E isso não é permitido. Agora, a maioria dos compiladores não perceber o self(self)porque esperar para deduzir o tipo de retorno Outer::Inner<Outer>::operator()<int>para quando inté passado. Sensible. Mas sente falta do mal formado do código.
Yakk - Adam Nevraumont 5/09
Bem, acho que eles devem esperar para deduzir o tipo de retorno do modelo de função até que esse modelo de função Innner<T>::operator()<U>seja instanciado. Afinal, o tipo de retorno pode depender do Uaqui. Não, mas em geral.
Saúde e hth. #
certo; mas qualquer expressão cujo tipo é determinado por uma dedução incompleta do tipo de retorno permanece ilegal. Apenas alguns compiladores são preguiçosos e não verificam até mais tarde, momento em que tudo funciona.
Yakk - Adam Nevraumont 5/09