A coleta de lixo é necessária para implementar fechamentos seguros?

14

Recentemente, participei de um curso on-line sobre linguagens de programação, no qual, entre outros conceitos, foram apresentados encerramentos. Escrevo dois exemplos inspirados neste curso para dar algum contexto antes de fazer minha pergunta.

O primeiro exemplo é uma função SML que produz uma lista dos números de 1 a x, em que x é o parâmetro da função:

fun countup_from1 (x: int) =
    let
        fun count (from: int) =
            if from = x
            then from :: []
            else from :: count (from + 1)
    in
        count 1
    end

No SML REPL:

val countup_from1 = fn : int -> int list
- countup_from1 5;
val it = [1,2,3,4,5] : int list

A countup_from1função usa o fechamento auxiliar countque captura e usa a variável xde seu contexto.

No segundo exemplo, quando invoco uma função create_multiplier t, recebo de volta uma função (na verdade, um fechamento) que multiplica seu argumento por t:

fun create_multiplier t = fn x => x * t

No SML REPL:

- fun create_multiplier t = fn x => x * t;
val create_multiplier = fn : int -> int -> int
- val m = create_multiplier 10;
val m = fn : int -> int
- m 4;
val it = 40 : int
- m 2;
val it = 20 : int

Portanto, a variável mestá vinculada ao fechamento retornado pela chamada de função e agora posso usá-la à vontade.

Agora, para que o fechamento funcione adequadamente durante toda a sua vida útil, precisamos estender a vida útil da variável capturada t(no exemplo, é um número inteiro, mas pode ser um valor de qualquer tipo). Tanto quanto eu sei, no SML isso é possível pela coleta de lixo: o fechamento mantém uma referência ao valor capturado que é posteriormente descartado pelo coletor de lixo quando o fechamento é destruído.

Minha pergunta: em geral, a coleta de lixo é o único mecanismo possível para garantir que os fechamentos sejam seguros (exigíveis durante toda a vida útil)?

Ou quais são outros mecanismos que poderiam garantir a validade dos fechamentos sem coleta de lixo: copie os valores capturados e armazene-os dentro do fechamento? Restringir o tempo de vida do próprio fechamento para que ele não possa ser chamado depois que suas variáveis ​​capturadas expirarem?

Quais são as abordagens mais populares?

EDITAR

Eu não acho que o exemplo acima possa ser explicado / implementado copiando as variáveis ​​capturadas no fechamento. Em geral, as variáveis ​​capturadas podem ser de qualquer tipo, por exemplo, podem ser vinculadas a uma lista muito grande (imutável). Portanto, na implementação, seria muito ineficiente copiar esses valores.

Por uma questão de exaustividade, aqui está outro exemplo usando referências (e efeitos colaterais):

(* Returns a closure containing a counter that is initialized
   to 0 and is incremented by 1 each time the closure is invoked. *)
fun create_counter () =
    let
        (* Create a reference to an integer: allocate the integer
           and let the variable c point to it. *)
        val c = ref 0
    in
        fn () => (c := !c + 1; !c)
    end

(* Create a closure that contains c and increments the value
   referenced by it it each time it is called. *)
val m = create_counter ();

No SML REPL:

val create_counter = fn : unit -> unit -> int
val m = fn : unit -> int
- m ();
val it = 1 : int
- m ();
val it = 2 : int
- m ();
val it = 3 : int

Portanto, as variáveis ​​também podem ser capturadas por referência e ainda estão ativas após a conclusão da chamada de função que as criou ( create_counter ()).

Giorgio
fonte
2
Quaisquer variáveis ​​fechadas devem ser protegidas da coleta de lixo e quaisquer variáveis ​​que não estejam fechadas devem ser elegíveis para a coleta de lixo. Daqui resulta que qualquer mecanismo que possa rastrear com segurança se uma variável está ou não fechada também pode recuperar com segurança a memória que a variável ocupa.
Robert Harvey
3
@btilly: Recontar é apenas uma das muitas estratégias de implementação diferentes para um coletor de lixo. Realmente não importa como o GC é implementado para os fins desta pergunta.
Jörg W Mittag
3
@ btilly: O que significa coleta de lixo "verdadeira"? A recontagem é apenas outra maneira de implementar o GC. O rastreamento é mais popular, provavelmente devido às dificuldades de coletar ciclos com a recontagem. (Geralmente, você acaba com um GC de rastreamento separado de qualquer maneira, então, por que se preocupar em implementar dois GCs, se puder se dar bem com um?). Mas existem outras maneiras de lidar com ciclos. 1) Apenas os proíba. 2) Apenas ignore-os. (Se você está executando uma implementação para scripts únicos rápidos, por que não?) 3) Tente detectá-los explicitamente. (Acontece que com uma velocidade de refcount lata disponível que acima.)
Jörg W Mittag
1
Depende de por que você deseja encerramentos em primeiro lugar. Se você deseja implementar, digamos, uma semântica de cálculo lambda completa, definitivamente precisa do ponto de GC. Não há outro caminho. Se você deseja algo que se assemelha a fechamentos distantes, mas não segue a semântica exata de tais (como em C ++, Delphi, o que for) - faça o que quiser, use a análise de região, use o gerenciamento de memória totalmente manual.
SK-logic
2
@ Wheeler Mason: Os fechamentos são apenas valores, em geral não é possível prever como eles serão movidos em tempo de execução. Nesse sentido, eles não são nada de especial, o mesmo seria válido para uma sequência, uma lista e assim por diante.
Giorgio

Respostas:

14

A linguagem de programação Rust é interessante nesse aspecto.

Rust é uma linguagem do sistema, com um GC opcional, e foi projetada com fechamentos desde o início.

Como as outras variáveis, os fechamentos de ferrugem têm vários sabores. Os fechamentos de pilha , os mais comuns, são para uso único. Eles vivem na pilha e podem fazer referência a qualquer coisa. Os fechamentos proprietários assumem a propriedade das variáveis ​​capturadas. Eu acho que eles vivem na chamada "pilha de troca", que é uma pilha global. Sua vida útil depende de quem os possui. Os fechamentos gerenciados ficam no heap local da tarefa e são rastreados pelo GC da tarefa. Eu não tenho certeza sobre suas limitações de captura, no entanto.

barjak
fonte
1
Link e referência muito interessantes para a linguagem Rust. Obrigado. +1.
Giorgio
1
Pensei muito antes de aceitar uma resposta, porque acho que a resposta de Mason também é muito informativa. Eu escolhi este porque é informativo e cita uma linguagem menos conhecida, com uma abordagem original dos fechamentos.
Giorgio
Obrigado por isso. Estou muito entusiasmado com essa linguagem jovem e fico feliz em compartilhar meu interesse. Eu não sabia se eram possíveis fechamentos seguros sem a GC, antes de ouvir sobre Rust.
Barjak
9

Infelizmente, começar com um GC faz de você uma vítima da síndrome XY:

  • os fechamentos exigem mais do que as variáveis ​​que eles fecharam ao longo do tempo, desde que o fechamento (por razões de segurança)
  • usando o GC, podemos estender a vida útil dessas variáveis ​​por tempo suficiente
  • Síndrome XY: existem outros mecanismos para prolongar a vida útil?

Observe, no entanto, que a idéia de prolongar a vida útil de uma variável não é necessária para um fechamento; é apenas trazido pelo GC; a declaração de segurança original é que as variáveis ​​fechadas devem permanecer enquanto o fechamento (e mesmo que seja instável, poderíamos dizer que elas deveriam permanecer até depois da última invocação do fechamento).

Existem, essencialmente, duas abordagens que posso ver (e elas podem ser combinadas):

  1. Aumente a vida útil das variáveis ​​fechadas (como um GC faz, por exemplo)
  2. Restringir a vida útil do fechamento

O último é apenas uma abordagem simétrica. Geralmente não é usado, mas se, como o Rust, você possui um sistema de tipo com reconhecimento de região, é certamente possível.

Matthieu M.
fonte
7

A coleta de lixo não é necessária para fechamentos seguros ao capturar variáveis ​​por valor. Um exemplo proeminente é o C ++. C ++ não tem coleta de lixo padrão. Lambdas no C ++ 11 são encerramentos (eles capturam variáveis ​​locais do escopo circundante). Cada variável capturada por um lambda pode ser especificada para ser capturada por valor ou por referência. Se for capturado por referência, você poderá dizer que não é seguro. No entanto, se uma variável é capturada por valor, ela é segura, porque a cópia capturada e a variável original são separadas e têm vida útil independente.

No exemplo SML que você deu, é simples de explicar: as variáveis ​​são capturadas por valor. Não há necessidade de "estender a vida útil" de qualquer variável, pois você pode apenas copiar seu valor no fechamento. Isso é possível porque, no ML, as variáveis ​​não podem ser atribuídas. Portanto, não há diferença entre uma cópia e muitas cópias independentes. Embora o SML tenha coleta de lixo, ele não está relacionado à captura de variáveis ​​por fechamento.

A coleta de lixo também não é necessária para fechamentos seguros ao capturar variáveis ​​por referência (tipo de). Um exemplo é a extensão Apple Blocks para as linguagens C, C ++, Objective-C e Objective-C ++. Não há coleta de lixo padrão em C e C ++. Os blocos capturam variáveis ​​por valor por padrão. No entanto, se uma variável local é declarada com __block, os blocos as capturam aparentemente "por referência" e são seguras - elas podem ser usadas mesmo após o escopo em que o bloco foi definido. O que acontece aqui é que as __blockvariáveis ​​são realmente uma estrutura especial abaixo, e quando os blocos são copiados (os blocos devem ser copiados para usá-los fora do escopo, em primeiro lugar), eles "movem" a estrutura para o__block variável na pilha, e o bloco gerencia sua memória, acredito através da contagem de referência.

user102008
fonte
4
"A coleta de lixo não é necessária para fechamentos.": A questão é se é necessária para que o idioma possa impor fechamentos seguros. Eu sei que posso escrever fechamentos seguros em C ++, mas a linguagem não os impõe. Para fechamentos que prolongam a vida útil das variáveis ​​capturadas, consulte a edição da minha pergunta.
Giorgio
1
Suponho que a questão possa ser reformulada: para fechamentos seguros .
Matthieu M.
1
O título contém o termo "fechamentos seguros", você acha que eu poderia formulá-lo de uma maneira melhor?
Giorgio
1
Você pode corrigir o segundo parágrafo? No SML, os fechamentos prolongam a vida útil dos dados referenciados pelas variáveis ​​capturadas. Além disso, é verdade que você não pode atribuir variáveis ​​(alterar sua ligação), mas possui dados mutáveis ​​(através refde). Então, OK, pode-se discutir se a implementação de fechamentos está relacionada à coleta de lixo ou não, mas as declarações acima devem ser corrigidas.
Giorgio
1
@Giorgio: Que tal agora? Além disso, em que sentido você considera minha declaração de que os fechamentos não precisam prolongar a vida útil de uma variável capturada incorreta? Quando você fala sobre dados mutáveis, está falando sobre tipos de referência ( refs, matrizes, etc.) que apontam para uma estrutura. Mas o valor é a referência em si, não a coisa para a qual aponta. Se você possui var a = ref 1e faz uma cópia var b = ae usa b, isso significa que você ainda está usando a? Você tem acesso à mesma estrutura apontada por a? Sim. Isso é apenas como esses tipos trabalhar em SML e não têm nada a ver com fechamentos
user102008
6

A coleta de lixo não é necessária para implementar fechamentos. Em 2008, a linguagem Delphi, que não é coletada como lixo, adicionou uma implementação de fechamentos. Funciona assim:

O compilador cria um objeto functor sob o capô que implementa uma interface que representa um fechamento. Todas as variáveis ​​locais fechadas são alteradas de locais para o procedimento de fechamento para campos no objeto functor. Isso garante que o estado seja preservado enquanto o functor estiver.

A limitação deste sistema é que qualquer parâmetro passado por referência à função envolvente, bem como o valor resultante da função, não pode ser capturado pelo functor porque eles não são locais cujo escopo é limitado ao da função envolvente.

O functor é referido pela referência de fechamento, usando açúcar sintático para fazer com que pareça ao desenvolvedor como um ponteiro de função em vez de uma Interface. Ele usa o sistema de contagem de referência do Delphi para interfaces para garantir que o objeto functor (e todo o estado que ele possui) permaneça "vivo" o tempo que for necessário, e então será liberado quando o refcount cair para 0.

Mason Wheeler
fonte
1
Ah, então só é possível capturar variáveis ​​locais, não os argumentos! Parece uma troca razoável e inteligente! +1
Giorgio
1
@ Giorgio: Ele pode capturar argumentos, mas não aqueles que são parâmetros var .
Mason Wheeler
2
Você também perde a capacidade de ter dois fechamentos que se comunicam através de um estado privado compartilhado. Você não encontrará isso nos casos de uso básicos, mas limita sua capacidade de fazer coisas complexas. Ainda é um ótimo exemplo do que é possível!
btilly
3
@ btilly: Na verdade, se você colocar dois fechamentos dentro da mesma função, isso é perfeitamente legal. Eles acabam compartilhando o mesmo objeto functor e, se modificarem o mesmo estado um do outro, as mudanças em um serão refletidas no outro.
Mason Wheeler
2
@MasonWheeler: "Não. A coleta de lixo é de natureza não determinística; não há garantia de que um objeto seja coletado, muito menos quando ocorrerá. Mas a contagem de referência é determinística: você tem a garantia do compilador de que o objeto será liberado imediatamente após a contagem cair para 0. ". Se eu tivesse um centavo por cada vez que ouvi esse mito perpetuado. OCaml tem um GC determinístico. O C ++ thread safe shared_ptrnão é determinístico porque os destruidores correm para diminuir para zero.
Jon Harrop 27/01