Cheney no MTA: um compilador no qual a pilha também serve como um heap

 

Ele alguma vez voltou? Não, ele nunca voltou,

E seu destino ainda não foi aprendido,

Ele pode cavalgar para sempre pelas ruas de Boston,

Ele é o homem que nunca voltou.



“Charlie no MTA”, 1949

1. Encerramentos

Um dos recursos úteis das linguagens de programação modernas são as funções aninhadas:

def bubble(arr, comp):

    def swap(i, j):
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp

    flag = True
    while flag:
        flag = False
        for i in range(len(arr) - 1):
            if comp(arr[i], arr[i+1]) > 0:
                swap(i, i+1)
                flag = True

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Essa possibilidade em si não é nova: já existia em Algol (1958) e é familiar a muitos de Pascal (1970). Compilar funções aninhadas é fácil: por exemplo, o quadro de pilha da função interna pode armazenar um ponteiro para o quadro de pilha da função externa para que a função interna possa acessar os parâmetros e variáveis ​​locais da função externa. Alguém pode se lembrar que as instruções enter



e leave



, que apareceram em 80186 (1982), implementam exatamente esse tipo de suporte para funções aninhadas (embora eu nunca tenha visto nenhum compilador que fizesse isso).



As dificuldades começam se o idioma permite que você transfira uma função interna para fora de uma externa:

def by_field(name):

    def comp(x, y):
        return x[name] – y[name]

    return comp

bubble(my_records, by_field("year"))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Como a função interna pode acessar os parâmetros e variáveis ​​locais da externa depois que o retorno da função externa destruiu seu quadro de pilha? De alguma forma, a função interna precisa "pegar" as variáveis ​​usadas junto com ela; uma função junto com variáveis ​​capturadas externamente é chamada de "fechamento". Pascal não suporta mais isso; mas, por exemplo, em C # 7 (2017), para isso, um objeto é criado no heap, contendo todos aqueles parâmetros e variáveis ​​locais aos quais a função interna se refere; e as chamadas dele e da função externa vão não para os valores na pilha, mas para os campos do objeto na pilha. É possível fazer sem essa complicação e continuar trabalhando com a pilha - para evitar endereçamento indireto desnecessário e preservar a localidade das chamadas, e não sobrecarregar o cache de dados com saltos no heap?

2. Aprovação de Continuação

Ao compilar linguagens de programação funcionais, onde capturar variáveis ​​locais por uma função de retorno é uma técnica muito comum, o primeiro passo é traduzir todo o programa em um “estilo de passagem de continuação” (CPS). os retornos das funções são substituídos por um retorno de chamada explícito passado para cada função como um argumento adicional. Por exemplo, nesta função simples que calcula o produto de todos os números primos de 1 a n



inclusive:

def prodprimes(n):
    if n == 1:
        return 1
    elif isprime(n):
        return n * prodprimes(n-1)
    else:
        return prodprimes(n-1)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- prodprimes



endereços de retorno diferentes são transferidos implicitamente para duas chamadas . Se esses endereços forem designados como j



e h



, e o endereço de retorno for passado como um argumento explícito c



, toda a transferência de controle pode ser explicitada:

def prodprimes(n, c):
    if n == 1:
        c(1)
    else:
        def k(b):
            if b:
                def j(p):
                    c(n * p)
                prodprimes(n-1, j)
            else:
                def h(q):
                    c(q)
                prodprimes(n-1, h)
        isprime(n, k)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

No CPS, não há diferença entre chamar uma função e retornar um valor de uma função - ambos são abstraídos como "passar um valor para um endereço especificado". Esta técnica foi usada na maioria dos compiladores Scheme desde o primeiro (1975); um livro inteiro "Compiling with Continuations" (1992) é dedicado a ele, de onde o exemplo acima é retirado. Mais recentemente, um estilo de programação semelhante se tornou popular com o nome de “promessas”.



A razão pela qual o CPS foi usado internamente por compiladores como uma representação intermediária antes do SSA(inventado em 1988) tornou-se mais popular - simplicidade: esta não é outra linguagem com suas próprias regras, mas uma sublinguagem do PL original com a restrição de que uma função ou chamada de continuação é permitida apenas como a última função ou operador de continuação. É fácil traduzir o código PL em CPS com um conjunto de transformações formais e é fácil aplicar transformações simplificadas ao código CPS - por exemplo, descubra que a continuação é h



trivial e substitua o uso h



por c



. Uma característica importante do CPS para nós é que os fechamentos são usados ​​no mesmo escopo em que foram declarados e, portanto, podem acessar variáveis ​​capturadas de fora da mesma maneira que em 80186 - por meio de ponteiros para frames de pilha externos:

def by_field(name, c):

    def comp(x, y, c):
        c(x[name] – y[name])

    c(comp)

def by_year(comp):
    bubble(my_records, comp, halt)

by_field("year", by_year)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Após a conversão para CPS comp



, ele sabe que é uma função de aninhamento 2 e o valor name



está no quadro de aninhamento 1, portanto, a compilação da chamada para name



não causará dificuldades.



Mas o CPS tem uma desvantagem: uma vez que as continuações nunca são executadas return



então, seus quadros de pilha nunca são destruídos e a pilha transbordará muito rapidamente. Por outro lado, uma continuação pode necessitar de um determinado stack frame, seja se ela própria se referir a ela, seja se receber como parâmetro uma continuação que se refere a esta frame. Além disso, a transição para a próxima continuação deve ser a última ação dentro da continuação, de forma que o endereço e os parâmetros da próxima continuação possam ser considerados o resultado da continuação. (O modelo de "promessas" retorna esse resultado explicitamente.) Os compiladores clássicos de Scheme usavam um despachante como o seguinte loop infinito:

1. Execute a continuação atual e obtenha o endereço e os parâmetros da próxima continuação como resultado;
2. Verifique quais stack frames podem ser acessados ​​pelos próximos parâmetros de continuação e continuação passados ​​a ele;
3. , .

Com essa implementação, a pilha de chamadas do sistema não é usada e as transições entre o despachante e as continuações são implementadas normalmente jmp



. Os quadros de continuação são desacoplados da pilha de chamadas e destruídos em ordem aleatória em vez de LIFO , de forma que sua coleção possa ser considerada uma pilha e também um heap.



Como você pode imaginar, com uma verificação de pilha em cada ramificação entre a continuação, o desempenho do programa deixou muito a desejar. Uma das otimizações possíveis é verificar o tamanho da pilha atual antes de sair da continuação e, se não exceder o limite especificado, vá diretamente para a próxima continuação; caso contrário, transfira o controle para o despachante para que ele colete todo o lixo da pilha. Graduado em Boston O MIT Henry Baker comentou sobre esta abordagem: "em vez de pular em um trampolim o tempo todo, pulamos do Empire State Building - mas com muito menos frequência."

3. No MTA

Em 1948, o Boston Metro (Metropolitan Transit Authority) aumentou as tarifas de 10 centavos para 15 centavos. Em vez de repor todas as moedas, na entrada do metrô, os condutores foram instruídos a cobrar uma sobretaxa de cinco centavos na saída do trem. Zombando dessa abordagem, um candidato a prefeito de Boston encomendou a gravação de uma música sobre um certo Charlie, que não tinha um centavo suficiente para pagar a saída, e estava condenado a andar de metrô indefinidamente. O candidato ganhou fama de comunista, ganhou apenas 1,2% dos votos nas eleições e deixou a política para sempre; Mas a canção sobre o passageiro que nunca retorna à superfície da terra acabou se tornando muito mais popular: até o cartão do metrô de Boston, lançado em 2006, é chamado de CharlieCard em homenagem a esse mesmo passageiro.



A história de Charlie inspirou Henry Baker a escrever um compilador Scheme em 1994 que transforma cada continuação em uma função C para que a execução dessas funções nunca chegue return



: por exemplo,

(define (revappend old new)
  (if (null? old)
      new
      (revappend (cdr old) (cons (car old) new))))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- torna-se em

void revappend(clos_type *cont, cons_type *old, cons_type *new) {
  if (old == NIL) {
    /* Call continuation with new as result. */
    return (cont->fn)(cont->env, new);
  }
  cons_type newer; /* Should check stack here. */
  /* Code for (revappend (cdr old) (cons (car old) new)). */
  newer.tag = cons_tag; newer.car = old->car; newer.cdr = new;
  return revappend(cont, old->cdr, &newer);
}

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

O significado do operador return



após tal conversão é dizer ao compilador C que não há necessidade de salvar os registradores antes de chamar a continuação; na verdade, uma função chamada como operando return



nunca retornará. No local marcado como /* Should check stack here. */



, uma verificação do tamanho da pilha é inserida e, se necessário, o despachante é chamado para a coleta de lixo.



Essa abordagem tem várias vantagens sobre a clássica:

1. Scheme : ; – , .. (varargs); – , .. (VLA). 21 . LLVM, .
2. ABI – , Scheme. «» , CPS, . «» callback- «» , , , «» – , . Scheme, map



fold
   
   
   
   , , .

Por outro lado, C não suporta funções aninhadas, o que significa que todos os ponteiros para variáveis ​​capturadas de fora devem ser explicitamente passados ​​junto com o encerramento. Além disso, ao colocar quadros de continuação na pilha do sistema em vez de um autoescrito, surge uma dificuldade: como implementar a coleta de lixo para a pilha do sistema, que não está ligada ao dispositivo de um compilador C específico em uma arquitetura específica?

4. Coletor de lixo de Cheney

O primeiro e mais simples coletor de lixo foi implementado em 1969 para o LISP: quando uma metade do heap estava cheia, o programa parava e todos os dados "vivos" eram recursivamente (passagem em profundidade) transferidos para a segunda metade do heap. Em 1970, Chris Cheney - também em Cambridge, mas do outro lado do oceano a partir do MIT - percebeu que, ao percorrer os dados ativos em amplitude, o próprio coletor não precisaria de memória adicional durante a construção; desde então, a coleta de lixo com a interrupção do programa e a movimentação de objetos ativos para a segunda metade do heap passou a ser chamada de "algoritmo de Cheney". Sua principal desvantagem é que os dados ativos podem ocupar apenas metade da memória disponível, e a segunda metade é ocupada por um "buffer para cópia".



A eficiência da coleta de lixo pode ser melhorada observando que os dados em um programa típico são divididos em "vida muito curta" e "vida muito longa": se um objeto sobreviveu a uma coleta de lixo, é muito provável que sobreviva na próxima coleção também. Portanto, o heap é dividido em um "berçário" para objetos recém-criados e um "heap adulto" de duas metades. Quando o berçário fica cheio, os dados ativos dele são transferidos para o heap adulto; quando uma metade do heap adulto transborda, os dados ativos dele são transportados para a outra metade. Isso economiza memória (nenhum espaço é reservado para dados de curta duração na segunda metade do heap) e tempo de construção (dados de longa duração não são copiados para frente e para trás com cada coleta de lixo no berçário).



Ao usar “Cheney no MTA”, a pilha atua como um gatil. O despachante chamado no estouro de pilha recebe explicitamente como parâmetros ponteiros para todos os dados ativos: esses são todos os parâmetros e variáveis ​​locais da continuação da chamada, incluindo variáveis ​​capturadas passadas para a continuação como um parâmetro implícito. Ao contrário dos coletores de lixo tradicionais, Cheney no MTA não precisa procurar dados ativos dentro da pilha: o CPS garante que todos os dados abaixo do último quadro de pilha morram se não estiverem disponíveis no último quadro. Isso significa que o coletor de lixo não se preocupa com a estrutura dos frames da pilha, nem com a possível presença de frames "estrangeiros" na pilha, sobras de funções em outras linguagens.







A abordagem “Cheney no MTA” é usada nos compiladores C Scheme “Chicken Scheme” (2000) e “Cyclone Scheme” (2016). No Cyclone, para a ideia de longa data de Baker, eles adicionaram suporte para coleta de lixo paralela, quando apenas um encadeamento é interrompido durante a coleta, cuja pilha está sendo processada e o resto continua funcionando.