5.3Alocação de Armazenamento e Coleta de Lixo

Na seção 5.4, mostraremos como implementar um avaliador de Scheme como uma máquina de registradores. Para simplificar a discussão, assumiremos que nossas máquinas de registradores podem ser equipadas com uma memória estruturada em listas, na qual as operações básicas para manipular dados estruturados em listas são primitivas. Postular a existência de tal memória é uma abstração útil quando se está focando nos mecanismos de controle em um interpretador de Scheme, mas isso não reflete uma visão realista das operações primitivas de dados em computadores contemporâneos. Para obter uma visão mais completa de como um sistema Lisp opera, devemos investigar como a estrutura de listas pode ser representada de uma forma compatível com as memórias convencionais de computadores.

Há duas considerações na implementação da estrutura de listas. A primeira é puramente uma questão de representação: como representar a estrutura de "caixa e ponteiro" dos pares de Lisp, usando apenas as capacidades de armazenamento e endereçamento das memórias típicas de computadores. A segunda questão diz respeito ao gerenciamento da memória à medida que a computação prossegue. A operação de um sistema Lisp depende crucialmente da capacidade de criar continuamente novos objetos de dados. Isso inclui objetos que são explicitamente criados pelos procedimentos Lisp que estão sendo interpretados, bem como estruturas criadas pelo próprio interpretador, como ambientes e listas de argumentos. Embora a criação constante de novos objetos de dados não representasse um problema em um computador com uma quantidade infinita de memória rapidamente endereçável, as memórias de computadores estão disponíveis apenas em tamanhos finitos (infelizmente). Assim, os sistemas Lisp fornecem uma facilidade de alocação automática de armazenamento para suportar a ilusão de uma memória infinita. Quando um objeto de dados não é mais necessário, a memória alocada para ele é automaticamente reciclada e usada para construir novos objetos de dados. Existem várias técnicas para fornecer essa alocação automática de armazenamento. O método que discutiremos nesta seção é chamado de coleta de lixo.

5.3.1Memória como Vetores

Uma memória de computador convencional pode ser pensada como um array de compartimentos, cada um dos quais pode conter uma peça de informação. Cada compartimento tem um nome único, chamado de endereço ou localização. Sistemas de memória típicos fornecem duas operações primitivas: uma que busca os dados armazenados em uma localização especificada e outra que atribui novos dados a uma localização especificada. Endereços de memória podem ser incrementados para suportar o acesso sequencial a algum conjunto de compartimentos. De forma mais geral, muitas operações importantes de dados exigem que os endereços de memória sejam tratados como dados, que podem ser armazenados em localizações de memória e manipulados em registradores de máquina. A representação da estrutura de listas é uma aplicação dessa aritmética de endereços.

Para modelar a memória do computador, usamos um novo tipo de estrutura de dados chamada vetor. Abstratamente, um vetor é um objeto de dados composto cujos elementos individuais podem ser acessados por meio de um índice inteiro em um tempo que é independente do índice.²⁹⁰ Para descrever as operações de memória, usamos dois procedimentos primitivos de Scheme para manipular vetores:

• (vector-ref ⟨vector⟩ ⟨n⟩) retorna o $n^{\text{ésimo}}$ elemento do vetor.
• (vector-set! ⟨vector⟩ ⟨n⟩ ⟨value⟩) define o $n^{\text{ésimo}}$ elemento do vetor para o valor designado.

Por exemplo, se v é um vetor, então (vector-ref v 5) obtém a quinta entrada no vetor v e (vector-set! v 5 7) altera o valor da quinta entrada do vetor v para 7.²⁹¹ Para a memória do computador, esse acesso pode ser implementado por meio do uso de aritmética de endereços para combinar um endereço base que especifica a localização inicial de um vetor na memória com um índice que especifica o deslocamento de um elemento particular do vetor.

Representando dados Lisp

Podemos usar vetores para implementar as estruturas básicas de pares necessárias para uma memória estruturada em listas. Vamos imaginar que a memória do computador é dividida em dois vetores: the-cars e the-cdrs. Representaremos a estrutura de listas da seguinte forma: Um ponteiro para um par é um índice nos dois vetores. O car do par é a entrada em the-cars com o índice designado, e o cdr do par é a entrada em the-cdrs com o índice designado. Também precisamos de uma representação para objetos que não são pares (como números e símbolos) e uma maneira de distinguir um tipo de dado de outro. Existem muitos métodos para realizar isso, mas todos se resumem ao uso de ponteiros tipados, ou seja, estender a noção de "ponteiro" para incluir informações sobre o tipo de dado.²⁹² O tipo de dado permite que o sistema distinga um ponteiro para um par (que consiste no tipo de dado "par" e um índice nos vetores de memória) de ponteiros para outros tipos de dados (que consistem em algum outro tipo de dado e o que quer que esteja sendo usado para representar dados desse tipo). Dois objetos de dados são considerados iguais (eq?) se seus ponteiros forem idênticos.²⁹³ Figura 5.14 ilustra o uso desse método para representar a lista ((1 2) 3 4), cujo diagrama de caixa e ponteiro também é mostrado. Usamos prefixos de letras para denotar as informações de tipo de dado. Assim, um ponteiro para o par com índice 5 é denotado por p5, a lista vazia é denotada pelo ponteiro e0, e um ponteiro para o número 4 é denotado por n4. No diagrama de caixa e ponteiro, indicamos no canto inferior esquerdo de cada par o índice do vetor que especifica onde o car e o cdr do par estão armazenados. As localizações em branco em the-cars e the-cdrs podem conter partes de outras estruturas de listas (que não são de interesse aqui).

Um ponteiro para um número, como n4, pode consistir em um tipo indicando dados numéricos junto com a representação real do número 4.²⁹⁴ Para lidar com números que são grandes demais para serem representados no espaço fixo alocado para um único ponteiro, poderíamos usar um tipo de dado bignum, para o qual o ponteiro designa uma lista na qual as partes do número são armazenadas.²⁹⁵

Um símbolo pode ser representado como um ponteiro tipado que designa uma sequência dos caracteres que formam a representação impressa do símbolo. Essa sequência é construída pelo leitor de Lisp quando a string de caracteres é inicialmente encontrada na entrada. Como queremos que duas instâncias de um símbolo sejam reconhecidas como o "mesmo" símbolo por eq? e queremos que eq? seja um teste simples para igualdade de ponteiros, devemos garantir que, se o leitor vir a mesma string de caracteres duas vezes, ele usará o mesmo ponteiro (para a mesma sequência de caracteres) para representar ambas as ocorrências. Para realizar isso, o leitor mantém uma tabela, tradicionalmente chamada de obarray, de todos os símbolos que já encontrou. Quando o leitor encontra uma string de caracteres e está prestes a construir um símbolo, ele verifica o obarray para ver se já viu a mesma string de caracteres antes. Se não tiver visto, ele usa os caracteres para construir um novo símbolo (um ponteiro tipado para uma nova sequência de caracteres) e insere esse ponteiro no obarray. Se o leitor já viu a string antes, ele retorna o ponteiro de símbolo armazenado no obarray. Esse processo de substituir strings de caracteres por ponteiros únicos é chamado de internamento de símbolos.

Implementando as operações primitivas de listas

Dado o esquema de representação acima, podemos substituir cada operação "primitiva" de lista de uma máquina de registradores por uma ou mais operações primitivas de vetor. Usaremos dois registradores, the-cars e the-cdrs, para identificar os vetores de memória, e assumiremos que vector-ref e vector-set! estão disponíveis como operações primitivas. Também assumimos que operações numéricas em ponteiros (como incrementar um ponteiro, usar um ponteiro de par para indexar um vetor ou adicionar dois números) usam apenas a parte do índice do ponteiro tipado.

Por exemplo, podemos fazer uma máquina de registradores suportar as instruções

(assign ⟨reg₁⟩ (op car) (reg ⟨reg₂⟩))
(assign ⟨reg₁⟩ (op cdr) (reg ⟨reg₂⟩))

se as implementarmos, respectivamente, como

(assign ⟨reg₁⟩ 
        (op vector-ref)
        (reg the-cars)
        (reg ⟨reg₂⟩))
(assign ⟨reg₁⟩
        (op vector-ref)
        (reg the-cdrs)
        (reg ⟨reg₂⟩))

As instruções

(perform (op set-car!) (reg ⟨reg₁⟩) (reg ⟨reg₂⟩))
(perform (op set-cdr!) (reg ⟨reg₁⟩) (reg ⟨reg₂⟩))

são implementadas como

(perform (op vector-set!)
         (reg the-cars)
         (reg ⟨reg₁⟩)
         (reg ⟨reg₂⟩))
(perform (op vector-set!)
         (reg the-cdrs)
         (reg ⟨reg₁⟩)
         (reg ⟨reg₂⟩))

Cons é realizado alocando um índice não utilizado e armazenando os argumentos para cons em the-cars e the-cdrs naquela posição indexada do vetor. Presumimos que há um registrador especial, free, que sempre contém um ponteiro de par contendo o próximo índice disponível, e que podemos incrementar a parte do índice desse ponteiro para encontrar a próxima localização livre.²⁹⁶ Por exemplo, a instrução

(assign ⟨reg₁⟩
        (op cons)
        (reg ⟨reg₂⟩)
        (reg ⟨reg₃⟩))

é implementada como a seguinte sequência de operações de vetor:²⁹⁷

(perform (op vector-set!)
         (reg the-cars)
         (reg free)
         (reg ⟨reg₂⟩))
(perform (op vector-set!)
         (reg the-cdrs)
         (reg free)
         (reg ⟨reg₃⟩))
(assign ⟨reg₁⟩ (reg free))
(assign free (op +) (reg free) (const 1))

A operação eq?

(op eq?) (reg ⟨reg₁⟩) (reg ⟨reg₂⟩)

simplesmente testa a igualdade de todos os campos nos registradores, e predicados como pair?, null?, symbol?, e number? precisam apenas verificar o campo de tipo.

Implementando pilhas

Embora nossas máquinas de registradores usem pilhas, não precisamos fazer nada especial aqui, pois as pilhas podem ser modeladas em termos de listas. A pilha pode ser uma lista dos valores salvos, apontada por um registrador especial the-stack. Assim, (save ⟨reg⟩) pode ser implementado como

(assign the-stack 
        (op cons)
        (reg ⟨reg⟩)
        (reg the-stack))

Da mesma forma, (restore ⟨reg⟩) pode ser implementado como

(assign ⟨reg⟩ (op car) (reg the-stack))
(assign the-stack (op cdr) (reg the-stack))

e (perform (op initialize-stack)) pode ser implementado como

(assign the-stack (const ()))

Essas operações podem ser expandidas em termos das operações de vetor fornecidas acima. Em arquiteturas de computadores convencionais, no entanto, geralmente é vantajoso alocar a pilha como um vetor separado. Então, empilhar e desempilhar podem ser realizados incrementando ou decrementando um índice nesse vetor.

Exercício 5.20: Desenhe a representação de caixa e ponteiro e a representação de vetor de memória (como na Figura 5.14) da estrutura de lista produzida por

(define x (cons 1 2))
(define y (list x x))

com o ponteiro free inicialmente p1. Qual é o valor final de free? Quais ponteiros representam os valores de x e y?

Exercício 5.21: Implemente máquinas de registradores para os seguintes procedimentos. Assuma que as operações de memória de estrutura de lista estão disponíveis como primitivas de máquina.

1. count-leaves recursivo:

   (define (count-leaves tree)
     (cond ((null? tree) 0)
           ((not (pair? tree)) 1)
           (else 
            (+ (count-leaves (car tree))
               (count-leaves (cdr tree))))))

2. count-leaves recursivo com contador explícito:

   (define (count-leaves tree)
     (define (count-iter tree n)
       (cond ((null? tree) n)
             ((not (pair? tree)) (+ n 1))
             (else 
              (count-iter 
               (cdr tree)
               (count-iter (car tree) 
                           n)))))
     (count-iter tree 0))

Exercício 5.22: Exercício 3.12 de 3.3.1 apresentou um procedimento append que anexa duas listas para formar uma nova lista e um procedimento append! que emenda duas listas. Projete uma máquina de registradores para implementar cada um desses procedimentos. Assuma que as operações de memória de estrutura de lista estão disponíveis como operações primitivas.

5.3.2Mantendo a Ilusão de Memória Infinita

O método de representação delineado em 5.3.1 resolve o problema de implementar a estrutura de listas, desde que tenhamos uma quantidade infinita de memória. Com um computador real, eventualmente ficaremos sem espaço livre para construir novos pares.²⁹⁸ No entanto, a maioria dos pares gerados em uma computação típica são usados apenas para manter resultados intermediários. Após esses resultados serem acessados, os pares não são mais necessários—eles são lixo. Por exemplo, a computação

(accumulate 
 +
 0
 (filter odd? (enumerate-interval 0 n)))

constrói duas listas: a enumeração e o resultado da filtragem da enumeração. Quando a acumulação estiver completa, essas listas não serão mais necessárias, e a memória alocada pode ser recuperada. Se pudermos organizar para coletar todo o lixo periodicamente, e se isso reciclar memória na mesma taxa em que construímos novos pares, teremos preservado a ilusão de que há uma quantidade infinita de memória.

Para reciclar pares, devemos ter uma maneira de determinar quais pares alocados não são mais necessários (no sentido de que seu conteúdo não pode mais influenciar o futuro da computação). O método que examinaremos para realizar isso é conhecido como coleta de lixo. A coleta de lixo é baseada na observação de que, a qualquer momento em uma interpretação de Lisp, os únicos objetos que podem afetar o futuro da computação são aqueles que podem ser alcançados por alguma sucessão de operações car e cdr a partir dos ponteiros que estão atualmente nos registradores da máquina.²⁹⁹ Qualquer célula de memória que não seja acessível dessa forma pode ser reciclada.

Existem muitas maneiras de realizar a coleta de lixo. O método que examinaremos aqui é chamado de stop-and-copy. A ideia básica é dividir a memória em duas metades: "memória de trabalho" e "memória livre". Quando cons constrói pares, ele aloca esses pares na memória de trabalho. Quando a memória de trabalho estiver cheia, realizamos a coleta de lixo localizando todos os pares úteis na memória de trabalho e copiando esses pares para localizações consecutivas na memória livre. (Os pares úteis são localizados rastreando todos os ponteiros car e cdr, começando com os registradores da máquina.) Como não copiamos o lixo, presumivelmente haverá memória livre adicional que podemos usar para alocar novos pares. Além disso, nada na memória de trabalho é necessário, pois todos os pares úteis nela foram copiados. Assim, se trocarmos os papéis da memória de trabalho e da memória livre, podemos continuar o processamento; novos pares serão alocados na nova memória de trabalho (que era a antiga memória livre). Quando essa memória estiver cheia, podemos copiar os pares úteis para a nova memória livre (que era a antiga memória de trabalho).³⁰⁰

Implementação de um coletor de lixo stop-and-copy

Agora usamos nossa linguagem de máquina de registradores para descrever o algoritmo stop-and-copy em mais detalhes. Assumiremos que há um registrador chamado root que contém um ponteiro para uma estrutura que eventualmente aponta para todos os dados acessíveis. Isso pode ser organizado armazenando o conteúdo de todos os registradores da máquina em uma lista pré-alocada apontada por root logo antes de iniciar a coleta de lixo.³⁰¹ Também assumimos que, além da memória de trabalho atual, há memória livre disponível na qual podemos copiar os dados úteis. A memória de trabalho atual consiste em vetores cujos endereços base estão nos registradores chamados the-cars e the-cdrs, e a memória livre está nos registradores chamados new-cars e new-cdrs.

A coleta de lixo é acionada quando esgotamos as células livres na memória de trabalho atual, ou seja, quando uma operação cons tenta incrementar o ponteiro free além do final do vetor de memória. Quando o processo de coleta de lixo estiver completo, o ponteiro root apontará para a nova memória, todos os objetos acessíveis a partir de root terão sido movidos para a nova memória, e o ponteiro free indicará o próximo local na nova memória onde um novo par pode ser alocado. Além disso, os papéis da memória de trabalho e da nova memória terão sido trocados—novos pares serão construídos na nova memória, começando no local indicado por free, e a (anterior) memória de trabalho estará disponível como a nova memória para a próxima coleta de lixo. Figura 5.15 mostra o arranjo da memória logo antes e logo após a coleta de lixo.

O estado do processo de coleta de lixo é controlado mantendo dois ponteiros: free e scan. Esses ponteiros são inicializados para apontar para o início da nova memória. O algoritmo começa realocando o par apontado por root para o início da nova memória. O par é copiado, o ponteiro root é ajustado para apontar para a nova localização, e o ponteiro free é incrementado. Além disso, a localização antiga do par é marcada para mostrar que seu conteúdo foi movido. Essa marcação é feita da seguinte forma: Na posição car, colocamos uma tag especial que sinaliza que este é um objeto já movido. (Tal objeto é tradicionalmente chamado de coração partido.)³⁰² Na posição cdr, colocamos um endereço de encaminhamento que aponta para a localização para a qual o objeto foi movido.

Após realocar o root, o coletor de lixo entra em seu ciclo básico. A cada passo do algoritmo, o ponteiro scan (inicialmente apontando para o root realocado) aponta para um par que foi movido para a nova memória, mas cujos ponteiros car e cdr ainda se referem a objetos na memória antiga. Esses objetos são cada um realocado, e o ponteiro scan é incrementado. Para realocar um objeto (por exemplo, o objeto indicado pelo ponteiro car do par que estamos escaneando), verificamos se o objeto já foi movido (como indicado pela presença de uma tag de coração partido na posição car do objeto). Se o objeto ainda não foi movido, nós o copiamos para o local indicado por free, atualizamos free, configuramos um coração partido na localização antiga do objeto e atualizamos o ponteiro para o objeto (neste exemplo, o ponteiro car do par que estamos escaneando) para apontar para a nova localização. Se o objeto já foi movido, seu endereço de encaminhamento (encontrado na posição cdr do coração partido) é substituído pelo ponteiro no par que está sendo escaneado. Eventualmente, todos os objetos acessíveis terão sido movidos e escaneados, momento em que o ponteiro scan ultrapassará o ponteiro free e o processo terminará.

Podemos especificar o algoritmo stop-and-copy como uma sequência de instruções para uma máquina de registradores. O passo básico de realocar um objeto é realizado por uma sub-rotina chamada relocate-old-result-in-new. Essa sub-rotina obtém seu argumento, um ponteiro para o objeto a ser realocado, de um registrador chamado old. Ela realoca o objeto designado (incrementando free no processo), coloca um ponteiro para o objeto realocado em um registrador chamado new e retorna saltando para o ponto de entrada armazenado no registrador relocate-continue. Para iniciar a coleta de lixo, invocamos essa sub-rotina para realocar o ponteiro root, após inicializar free e scan. Quando a realocação de root for concluída, instalamos o novo ponteiro como o novo root e entramos no loop principal do coletor de lixo.

begin-garbage-collection
  (assign free (const 0))
  (assign scan (const 0))
  (assign old (reg root))
  (assign relocate-continue 
          (label reassign-root))
  (goto (label relocate-old-result-in-new))
reassign-root
  (assign root (reg new))
  (goto (label gc-loop))

No loop principal do coletor de lixo, devemos determinar se há mais objetos a serem escaneados. Fazemos isso testando se o ponteiro scan coincide com o ponteiro free. Se os ponteiros forem iguais, todos os objetos acessíveis terão sido realocados, e saltamos para gc-flip, que limpa as coisas para que possamos continuar a computação interrompida. Se ainda houver pares a serem escaneados, chamamos a sub-rotina de realocação para realocar o car do próximo par (colocando o ponteiro car em old). O registrador relocate-continue é configurado para que a sub-rotina retorne para atualizar o ponteiro car.

gc-loop
  (test (op =) (reg scan) (reg free))
  (branch (label gc-flip))
  (assign old 
          (op vector-ref)
          (reg new-cars)
          (reg scan))
  (assign relocate-continue 
          (label update-car))
  (goto (label relocate-old-result-in-new))

Em update-car, modificamos o ponteiro car do par que está sendo escaneado, então prosseguimos para realocar o cdr do par. Retornamos para update-cdr quando essa realocação for concluída. Após realocar e atualizar o cdr, terminamos de escanear esse par, então continuamos com o loop principal.

update-car
  (perform (op vector-set!)
           (reg new-cars)
           (reg scan)
           (reg new))
  (assign  old 
           (op vector-ref)
           (reg new-cdrs)
           (reg scan))
  (assign  relocate-continue
           (label update-cdr))
  (goto (label relocate-old-result-in-new))
update-cdr
  (perform (op vector-set!)
           (reg new-cdrs)
           (reg scan)
           (reg new))
  (assign  scan (op +) (reg scan) (const 1))
  (goto (label gc-loop))

A sub-rotina relocate-old-result-in-new realoca objetos da seguinte forma: Se o objeto a ser realocado (apontado por old) não for um par, então retornamos o mesmo ponteiro para o objeto inalterado (em new). (Por exemplo, podemos estar escaneando um par cujo car é o número 4. Se representarmos o car por n4, como descrito em 5.3.1, então queremos que o ponteiro car "realocado" ainda seja n4.) Caso contrário, devemos realizar a realocação. Se a posição car do par a ser realocado contiver uma tag de coração partido, então o par já foi movido, então recuperamos o endereço de encaminhamento (da posição cdr do coração partido) e retornamos isso em new. Se o ponteiro em old apontar para um par ainda não movido, então movemos o par para a primeira célula livre na nova memória (apontada por free) e configuramos o coração partido armazenando uma tag de coração partido e um endereço de encaminhamento na localização antiga. Relocate-old-result-in-new usa um registrador oldcr para armazenar o car ou o cdr do objeto apontado por old.³⁰³

relocate-old-result-in-new
  (test (op pointer-to-pair?) (reg old))
  (branch (label pair))
  (assign new (reg old))
  (goto (reg relocate-continue))
pair
  (assign  oldcr 
           (op vector-ref)
           (reg the-cars)
           (reg old))
  (test (op broken-heart?) (reg oldcr))
  (branch  (label already-moved))
  (assign  new (reg free)) ; nova localização para o par
  ;; Atualiza o ponteiro `free`.
  (assign free (op +) (reg free) (const 1))
  ;; Copia o `car` e o `cdr` para a nova memória.
  (perform (op vector-set!)
           (reg new-cars)
           (reg new)
           (reg oldcr))
  (assign  oldcr 
           (op vector-ref)
           (reg the-cdrs)
           (reg old))
  (perform (op vector-set!)
           (reg new-cdrs)
           (reg new)
           (reg oldcr))
  ;; Constrói o coração partido.
  (perform (op vector-set!)
           (reg the-cars)
           (reg old)
           (const broken-heart))
  (perform (op vector-set!)
           (reg the-cdrs)
           (reg old)
           (reg new))
  (goto (reg relocate-continue))
already-moved
  (assign  new
           (op vector-ref)
           (reg the-cdrs)
           (reg old))
  (goto (reg relocate-continue))

No final do processo de coleta de lixo, trocamos os papéis das memórias antiga e nova trocando os ponteiros: trocamos the-cars com new-cars, e the-cdrs com new-cdrs. Estaremos então prontos para realizar outra coleta de lixo na próxima vez que a memória se esgotar.

gc-flip
  (assign temp (reg the-cdrs))
  (assign the-cdrs (reg new-cdrs))
  (assign new-cdrs (reg temp))
  (assign temp (reg the-cars))
  (assign the-cars (reg new-cars))
  (assign new-cars (reg temp))