Ponteiros de função, fechamentos e lambda

Acabo de aprender sobre indicadores de função e, enquanto lia o capítulo K&R sobre o assunto, a primeira coisa que me atingiu foi: "Ei, isso é meio que um encerramento." Eu sabia que essa suposição estava fundamentalmente errada de alguma forma e, após uma pesquisa online, não encontrei realmente nenhuma análise dessa comparação.

Então, por que os ponteiros de função no estilo C são fundamentalmente diferentes de fechamentos ou lambdas? Até onde eu posso dizer, isso tem a ver com o fato de que o ponteiro de função ainda aponta para uma função definida (nomeada) em oposição à prática de definir anonimamente a função.

Por que passar uma função para uma função é vista como mais poderosa no segundo caso, onde não tem nome, do que no primeiro, onde é apenas uma função normal do dia a dia que está sendo passada?

Por favor, diga-me como e por que estou errado em comparar os dois tão de perto.

Obrigado.

Um lambda (ou fechamento ) encapsula o ponteiro de função e as variáveis. É por isso que, em C #, você pode fazer:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

Eu usei um delegado anônimo lá como um encerramento (sua sintaxe é um pouco mais clara e mais próxima de C do que o equivalente lambda), que capturou lessThan (uma variável de pilha) no encerramento. Quando o fechamento é avaliado, lessThan (cujo stack frame pode ter sido destruído) continuará a ser referenciado. Se eu mudar menos do que, mudo a comparação:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

Em C, isso seria ilegal:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

embora eu pudesse definir um ponteiro de função que leva 2 argumentos:

int lessThan = 100;
BOOL (*lessThanTest)(int, int);

lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false

BOOL LessThan(int i, int lessThan) {
   return i < lessThan;
}

Mas, agora tenho que passar os 2 argumentos quando avalio. Se eu desejasse passar este ponteiro de função para outra função onde lessThan não estivesse no escopo, eu teria que mantê-lo ativo manualmente, passando-o para cada função na cadeia, ou promovendo-o para global.

Embora a maioria das linguagens convencionais que suportam encerramentos usem funções anônimas, não há requisitos para isso. Você pode ter encerramentos sem funções anônimas e funções anônimas sem encerramentos.

Resumo: um fechamento é uma combinação de ponteiro de função + variáveis ​​capturadas.

Como alguém que escreveu compiladores para linguagens com e sem encerramentos "reais", discordo respeitosamente de algumas das respostas acima. Um fechamento Lisp, Scheme, ML ou Haskell não cria uma nova função dinamicamente . Em vez disso, ele reutiliza uma função existente, mas o faz com novas variáveis ​​livres . A coleção de variáveis ​​livres é freqüentemente chamada de ambiente , pelo menos pelos teóricos da linguagem de programação.

Um encerramento é apenas um agregado que contém uma função e um ambiente. No compilador Standard ML de New Jersey, representamos um como um registro; um campo continha um ponteiro para o código e os outros campos continham os valores das variáveis ​​livres. O compilador criou um novo encerramento (não função) dinamicamente , alocando um novo registro contendo um ponteiro para o mesmo código, mas com valores diferentes para as variáveis ​​livres.

Você pode simular tudo isso em C, mas é um pé no saco. Duas técnicas são populares:

1. Passe um ponteiro para a função (o código) e um ponteiro separado para as variáveis ​​livres, de modo que o fechamento seja dividido em duas variáveis ​​C.

2. Passe um ponteiro para uma estrutura, onde a estrutura contém os valores das variáveis ​​livres e também um ponteiro para o código.

A técnica # 1 é ideal quando você está tentando simular algum tipo de polimorfismo em C e não quer revelar o tipo de ambiente --- você usa um ponteiro void * para representar o ambiente. Por exemplo, veja o artigo de Dave Hanson interfaces e implementações C de . A técnica # 2, que mais se assemelha ao que acontece em compiladores de código nativo para linguagens funcionais, também se assemelha a outra técnica familiar ... objetos C ++ com funções-membro virtuais. As implementações são quase idênticas.

Essa observação levou a uma piada de Henry Baker:

As pessoas no mundo Algol / Fortran reclamaram durante anos que não entendiam o que os fechamentos de funções de uso possíveis teriam na programação eficiente do futuro. Então a revolução da `programação orientada a objetos 'aconteceu, e agora todos programam usando encerramentos de função, exceto que ainda se recusam a chamá-los assim.

Em C, você não pode definir a função embutida, portanto, você não pode realmente criar um encerramento. Tudo o que você está fazendo é passar uma referência a algum método pré-definido. Em linguagens que suportam métodos / fechamentos anônimos, a definição dos métodos é muito mais flexível.

Em termos mais simples, os ponteiros de função não têm escopo associado a eles (a menos que você conte o escopo global), enquanto os encerramentos incluem o escopo do método que os está definindo. Com lambdas, você pode escrever um método que escreve um método. Os fechamentos permitem vincular "alguns argumentos a uma função e obter uma função de menor aridade como resultado". (retirado do comentário de Thomas). Você não pode fazer isso em C.

EDIT: Adicionando um exemplo (vou usar uma sintaxe em estilo Actionscript, porque é isso que estou pensando agora):

Digamos que você tenha algum método que tenha outro método como argumento, mas não forneça uma maneira de passar nenhum parâmetro para aquele método quando for chamado. Como, digamos, algum método que causa um atraso antes de executar o método que você passou (exemplo estúpido, mas quero mantê-lo simples).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Agora, digamos que você queira que o usuário runLater () atrase algum processamento de um objeto:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

A função que você está passando para process () não é mais uma função definida estática. É gerado dinamicamente e pode incluir referências a variáveis ​​que estavam no escopo quando o método foi definido. Assim, ele pode acessar 'o' e 'objectProcessor', mesmo que não estejam no escopo global.

Espero que tenha feito sentido.

Fechamento = lógica + ambiente.

Por exemplo, considere este método C # 3:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

A expressão lambda não apenas encapsula a lógica ("compare o nome"), mas também o ambiente, incluindo o parâmetro (isto é, a variável local) "nome".

Para saber mais sobre isso, dê uma olhada em meu artigo sobre encerramentos, que o conduz por C # 1, 2 e 3, mostrando como os encerramentos tornam as coisas mais fáceis.

Em C, ponteiros de função podem ser passados ​​como argumentos para funções e retornados como valores de funções, mas as funções existem apenas no nível superior: você não pode aninhar definições de função umas dentro das outras. Pense sobre o que seria necessário para C oferecer suporte a funções aninhadas que podem acessar as variáveis ​​da função externa, enquanto ainda é capaz de enviar ponteiros de função para cima e para baixo na pilha de chamadas. (Para seguir esta explicação, você deve saber os fundamentos de como as chamadas de função são implementadas em C e na maioria das linguagens semelhantes: navegue pela entrada da pilha de chamadas na Wikipedia.)

Que tipo de objeto é um ponteiro para uma função aninhada? Não pode ser apenas o endereço do código, porque se você chamá-lo, como ele acessa as variáveis ​​da função externa? (Lembre-se de que, por causa da recursão, pode haver várias chamadas diferentes da função externa ativas ao mesmo tempo.) Isso é chamado de problema de funarg e há dois subproblemas: o problema de funargs para baixo e o problema de funargs para cima.

O problema dos funargs descendentes, isto é, enviar um ponteiro de função "para baixo na pilha" como um argumento para uma função que você chama, na verdade não é incompatível com C, e o GCC suporta funções aninhadas como funargs descendentes. No GCC, quando você cria um ponteiro para uma função aninhada, você realmente obtém um ponteiro para um trampolim , um pedaço de código construído dinamicamente que configura o ponteiro de link estático e chama a função real, que usa o ponteiro de link estático para acessar as variáveis ​​da função externa.

O problema do funargs ascendente é mais difícil. O GCC não impede que você permita que um ponteiro de trampolim exista depois que a função externa não estiver mais ativa (não tem registro na pilha de chamadas) e, em seguida, o ponteiro de link estático pode apontar para lixo. Os registros de ativação não podem mais ser alocados em uma pilha. A solução usual é alocá-los no heap e deixar um objeto de função que representa uma função aninhada apenas apontar para o registro de ativação da função externa. Esse objeto é chamado de fechamento . Então, a linguagem normalmente terá que oferecer suporte à coleta de lixo para que os registros possam ser liberados assim que não houver mais ponteiros apontando para eles.

Lambdas ( funções anônimas ) são realmente um problema separado, mas normalmente uma linguagem que permite que você defina funções anônimas instantaneamente também permite que você as retorne como valores de função, então eles acabam sendo encerramentos.

Um lambda é uma função anônima definida dinamicamente . Você simplesmente não pode fazer isso em C ... quanto a fechamentos (ou a convenção dos dois), o exemplo típico de ceceio seria algo como:

(defun get-counter (n-start +-number)
     "Returns a function that returns a number incremented
      by +-number every time it is called"
    (lambda () (setf n-start (+ +-number n-start))))

Em termos de C, você poderia dizer que o ambiente léxico (a pilha) de get-counterestá sendo capturado pela função anônima e modificado internamente como mostra o exemplo a seguir:

[1]> (defun get-counter (n-start +-number)
         "Returns a function that returns a number incremented
          by +-number every time it is called"
        (lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]> 

Os fechamentos implicam que alguma variável do ponto de definição da função seja vinculada à lógica da função, como ser capaz de declarar um mini-objeto em tempo real.

Um problema importante com C e fechamentos é que as variáveis ​​alocadas na pilha serão destruídas ao deixar o escopo atual, independentemente de um fechamento estar apontando para elas. Isso levaria ao tipo de bugs que as pessoas obtêm quando retornam descuidadamente ponteiros para variáveis ​​locais. Os fechamentos implicam basicamente que todas as variáveis ​​relevantes são itens contados por ref ou coletados em um heap.

Não me sinto confortável em equacionar lambda com encerramento porque não tenho certeza de que lambdas em todas as linguagens são encerramentos, às vezes acho que lambdas foram apenas funções anônimas definidas localmente sem a vinculação de variáveis ​​(Python pré 2.1?).

No GCC, é possível simular funções lambda usando a seguinte macro:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Exemplo da fonte :

qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
     lambda (int, (const void *a, const void *b),
             {
               dump ();
               printf ("Comparison %d: %d and %d\n",
                       ++ comparison, *(const int *) a, *(const int *) b);
               return *(const int *) a - *(const int *) b;
             }));

Usar essa técnica, é claro, remove a possibilidade de seu aplicativo trabalhar com outros compiladores e é aparentemente um comportamento "indefinido", então YMMV.

O encerramento captura as variáveis ​​livres em um ambiente . O ambiente ainda existirá, mesmo que o código circundante possa não estar mais ativo.

Um exemplo em Common Lisp, onde MAKE-ADDERretorna um novo encerramento.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Usando a função acima:

CL-USER 55 > (let ((adder1 (make-adder 0 10))
                   (adder2 (make-adder 17 20)))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder1))
               (print (funcall adder1))
               (describe adder1)
               (describe adder2)
               (values))

10 
20 
30 
40 
37 
57 
77 
50 
60 
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(77 20)

Observe que a DESCRIBEfunção mostra que os objetos de função para ambos os encerramentos são os mesmos, mas o ambiente é diferente.

Common Lisp faz com que tanto closures quanto objetos de função pura (aqueles sem um ambiente) sejam funções e pode-se chamar ambos da mesma maneira, aqui usando FUNCALL.

A principal diferença surge da falta de escopo lexical em C.

Um ponteiro de função é apenas isso, um ponteiro para um bloco de código. Qualquer variável não pilha que ele faz referência é global, estática ou semelhante.

Um fechamento, OTOH, tem seu próprio estado na forma de 'variáveis ​​externas' ou 'upvalues'. eles podem ser tão privados ou compartilhados quanto você quiser, usando o escopo léxico. Você pode criar muitos encerramentos com o mesmo código de função, mas diferentes instâncias de variáveis.

Alguns fechamentos podem compartilhar algumas variáveis ​​e, portanto, podem ser a interface de um objeto (no sentido OOP). para fazer isso em C, você precisa associar uma estrutura a uma tabela de ponteiros de função (é isso que C ++ faz, com uma classe vtable).

em resumo, um fechamento é um ponteiro de função MAIS algum estado. é uma construção de nível superior

A maioria das respostas indica que os encerramentos requerem ponteiros de função, possivelmente para funções anônimas, mas como Mark escreveu, os encerramentos podem existir com funções nomeadas. Aqui está um exemplo em Perl:

{
    my $count;
    sub increment { return $count++ }
}

O fechamento é o ambiente que define a $countvariável. Está disponível apenas para a incrementsub - rotina e persiste entre as chamadas.

Em C, um ponteiro de função é um ponteiro que invocará uma função quando você desreferenciá-la, um encerramento é um valor que contém a lógica de uma função e o ambiente (variáveis ​​e os valores aos quais estão vinculados) e um lambda geralmente se refere a um valor que é na verdade uma função sem nome. Em C, uma função não é um valor de primeira classe, então não pode ser passado, então você deve passar um ponteiro para ele, no entanto, em linguagens funcionais (como Scheme) você pode passar funções da mesma maneira que passa qualquer outro valor