Problemas ao implementar fechamentos em configurações não funcionais

18

Nas linguagens de programação, os fechamentos são um recurso popular e frequentemente desejado. A Wikipedia diz (ênfase minha):

Na ciência da computação, um fechamento (...) é uma função juntamente com um ambiente de referência para as variáveis ​​não locais dessa função. Um fechamento permite que uma função acesse variáveis ​​fora de seu escopo lexical imediato.

Portanto, um fechamento é essencialmente um valor de função (anônimo?) Que pode usar variáveis ​​fora de seu próprio escopo. Na minha experiência, isso significa que ele pode acessar variáveis ​​que estão no escopo em seu ponto de definição.

Na prática, o conceito parece divergir, pelo menos fora da programação funcional. Linguagens diferentes implementam semânticas diferentes, até parece haver guerras de opiniões. Muitos programadores parecem não saber o que são fechamentos, visualizando-os como pouco mais que funções anônimas.

Além disso, parece haver grandes obstáculos ao implementar fechamentos. O mais notável é que o Java 7 deveria incluí-los, mas o recurso foi adiado para uma versão futura.

Por que os fechamentos são tão difíceis (de entender e) de realizar? Essa é uma pergunta muito ampla e vaga, portanto, deixe-me focar mais nessas perguntas interconectadas:

  • Existem problemas com a expressão de fechamentos em formalismos semânticos comuns (pequeno passo, grande passo, ...)?
  • Os sistemas de tipos existentes não são adequados para fechamentos e não podem ser estendidos facilmente?
  • É problemático alinhar os fechamentos com uma tradução de procedimento tradicional baseada em pilha?

Observe que a pergunta se refere principalmente a linguagens processuais, orientadas a objetos e de script em geral. Tanto quanto eu sei, linguagens funcionais não têm nenhum problema.

Rafael
fonte
Boa pergunta. Os fechamentos foram implementados no Scala, e Martin Odersky escreveu o compilador Java 1.5, portanto, não está claro por que eles não estão no Java 7. O C # os possui. (Vou tentar escrever uma resposta melhor mais tarde.)
Dave Clarke
4
Linguagens funcionais impuras como Lisp e ML acomodam fechamentos muito bem, portanto não pode haver uma razão semântica intrínseca para que sejam problemáticas.
Gilles 'SO- stop be evil'
Incluí o item porque tenho me esforçado para imaginar como seria uma semântica de pequenas etapas para fechamentos. Pode muito bem ser que os fechamentos em si não sejam um problema, mas é difícil incluí-los em um idioma que não foi projetado para eles.
Raphael
1
Dê uma olhada em pdfs.semanticscholar.org/73a2/… - Os autores de Lua fizeram uma maneira muito inteligente e discutiram problemas gerais de implementação de fechamentos também
Bulat

Respostas:

10

Posso direcioná-lo para a página da wikipedia com problemas do Funarg ? Pelo menos é assim que as pessoas do compilador costumavam fazer referência ao problema de implementação do fechamento.

Portanto, um fechamento é essencialmente um valor de função (anônimo?) Que pode usar variáveis ​​fora de seu próprio escopo. Na minha experiência, isso significa que ele pode acessar variáveis ​​que estão no escopo em seu ponto de definição.

Embora essa definição faça sentido, ela não ajuda a descrever o problema de implementar funções de primeira classe em uma linguagem tradicional baseada em pilha de tempo de execução. Quando se trata de problemas de implementação, as funções de primeira classe podem ser divididas em duas classes:

  • Variáveis ​​locais nas funções nunca são usadas após o retorno da função.
  • Variáveis ​​locais podem ser usadas após o retorno da função.

O primeiro caso (funargs para baixo) não é tão difícil de implementar e pode ser encontrado até nas linguagens processuais mais antigas, como Algol, C e Pascal. C meio que contorna o problema, pois não permite funções aninhadas, mas Algol e Pascal fazem a contabilidade necessária para permitir que as funções internas façam referência às variáveis ​​de pilha da função externa.

O segundo caso (funargs para cima), por outro lado, exige que os registros de ativação sejam salvos fora da pilha, na pilha. Isso significa que é muito fácil vazar recursos de memória, a menos que o tempo de execução do idioma inclua um coletor de lixo. Embora quase tudo seja coletado hoje em dia, exigir um deles ainda é uma decisão significativa do projeto e foi ainda mais há algum tempo.


Quanto ao exemplo específico de Java, se bem me lembro, o principal problema não era realmente implementar fechamentos, mas como apresentá-los à linguagem de uma maneira que não fosse redundante aos recursos existentes (como classes internas anônimas) e que não entraram em conflito com os recursos existentes (como exceções verificadas - um problema que não é trivial para resolver e que a maioria das pessoas não pensa a princípio).

Também posso pensar em outras coisas que tornam as funções de primeira classe menos triviais de implementar, como decidir o que fazer com variáveis ​​"mágicas" como essa , auto ou super e como interagir com os operadores de fluxo de controle existentes, como interrupção e retorno (queremos permitir retornos não locais ou não?). Mas, no final, a popularidade recente das funções de primeira classe parece indicar que as linguagens que não as possuem geralmente o fazem por razões históricas ou devido a alguma decisão de design significativa desde o início.

hugomg
fonte
1
Você conhece algum idioma que distingue os casos ascendentes e descendentes? Nas linguagens .NET, um método genérico que esperava receber uma função somente para baixo poderia receber uma estrutura do tipo genérico junto com um delegado que receberia uma estrutura como uma referência externa (em C #, um " refparâmetro"). Se o chamador encapsular todas as variáveis ​​de interesse na estrutura, o delegado poderá ser totalmente estático, evitando a necessidade de uma alocação de heap. Os compiladores não oferecem nenhuma ajuda agradável de sintaxe para essas construções, mas o Framework poderia apoiá-las.
Supercat
2
@supercat: O Rust possui vários tipos de fechamento que permitem aplicar em tempo de compilação se uma função interna precisar usar o heap. No entanto, isso não significa que uma implementação não possa tentar evitar alocações de heap sem forçar você a se preocupar com todos esses tipos extras. Um compilador pode tentar inferir a vida útil da função ou pode usar verificações de tempo de execução para salvar preguiçosamente variáveis ​​na pilha somente quando estritamente necessário (consulte a seção "escopo lexical" do artigo Evolução da Lua para obter detalhes)
hugomg
5

Podemos ver como os fechamentos são implementados em C #. A escala das transformações que o compilador C # realiza deixa claro que a maneira de implementar fechamentos é bastante trabalhosa. Pode haver maneiras mais fáceis de implementar fechamentos, mas acho que a equipe do compilador C # estaria ciente disso.

Considere o seguinte pseudo-C # (recortei algumas coisas específicas do C #):

int x = 1;
function f = function() { x++; };
for (int i = 1; i < 10; i++) {
    f();
}
print x; // Should print 9

O compilador transforma isso em algo assim:

class FunctionStuff {
   int x;
   void theFunction() {
       x++;
   }
}

FunctionStuff theClosureObject = new FunctionStuff();
theClosureObject.x = 1;
for (int i = 1; i < 10; i++) {
    theClosureObject.theFunction();
}
print theClosureObject.x; // Should print 9

(na realidade, a variável f ainda será criada, onde f é um 'delegado' (= ponteiro de função), mas esse delegado ainda está associado ao objeto theClosureObject - deixei esta parte de fora para esclarecer aqueles que não estão familiarizados com c #)

Essa transformação é bastante maciça e complicada: considere fechamentos dentro de fechamentos e a interação de fechamentos com o restante dos recursos da linguagem C #. Eu posso imaginar que o recurso foi adiado para Java, pois o Java 7 já possui muitos recursos novos.

Alex ten Brink
fonte
Eu posso ver para onde isso está indo; ter vários fechamentos e o escopo principal acessar a mesma variável ficará confuso.
Raphael
Para ser sincero, isso se deve mais ao uso da estrutura de OO existente para implementar fechamentos e a qualquer problema real com eles. Outras linguagens apenas alocam as variáveis ​​em uma estrutura separada, sem método, e permitem que vários fechamentos as compartilhem, se quiserem.
hugomg
@Raphael: como você se sente sobre fechamentos dentro de fechamentos? Espere, deixe-me acrescentar que no.
Alex ten Brink
5

Para responder parte da sua pergunta. O formalismo descrito por Morrisett e Harper cobre a semântica de grandes e pequenos passos de linguagens polimórficas de ordem superior que contêm fechamentos. Existem documentos antes desses que fornecem os tipos de semântica que você está procurando. Veja, por exemplo, a máquina SECD . Adicionar referências mutáveis ​​ou locais mutáveis ​​a essas semânticas é simples. Não vejo problemas técnicos no fornecimento dessa semântica.

Dave Clarke
fonte
Obrigado pela referência! Parece não facilitar a leitura, mas isso provavelmente é esperado em um artigo de semântica.
Raphael
1
@ Rafael: Provavelmente existem mais simples por aí. Vou tentar encontrar algo e voltar para você. De qualquer forma, a Figura 8 possui a semântica que você está procurando.
68660 Dave
Talvez você possa fornecer uma visão geral aproximada. as ideias centrais na sua resposta?
Raphael
2
@Raphael. Talvez eu possa encaminhá-lo para minhas anotações de aula que uso em um curso de linguagens de programação, o que fornece uma rápida introdução. Por favor, olhe para cima apostilas 8 e 9.
Uday Reddy
1
Esse link aparece morto ou atrás da autenticação invisível. ( cs.cmu.edu/afs/cs/user/rwh/public/www/home/papers/gcpoly/tr.pdf ). Eu sou 403 proibido.
Ben Fletcher