Cheney sur le MTA: un compilateur dans lequel la pile sert également de tas

 

Est-il jamais revenu? Non, il n'est jamais revenu,

Et son destin est encore désappris,

Il peut rouler pour toujours dans les rues de Boston,

C'est l'homme qui n'est jamais revenu.



«Charlie sur le MTA», 1949

1. Fermetures

L'une des fonctionnalités pratiques des langages de programmation modernes est les fonctions imbriquées:

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

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Cette possibilité elle-même n'est pas nouvelle: elle était déjà à Algol (1958) et est familière à beaucoup de Pascal (1970). La compilation de fonctions imbriquées est facile: par exemple, le cadre de pile de la fonction interne peut stocker un pointeur vers le cadre de pile de la fonction externe afin que la fonction interne puisse accéder aux paramètres et variables locales de la fonction externe. Quelqu'un peut se rappeler que les instructions enter



et leave



, qui sont apparues dans 80186 (1982), implémentent exactement ce genre de support pour les fonctions imbriquées (bien que je n'ai jamais vu de compilateur qui l'a fait).



Les difficultés commencent si la langue permet de transférer une fonction interne en dehors d'une fonction externe:

def by_field(name):

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

    return comp

bubble(my_records, by_field("year"))

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Comment la fonction interne peut-elle accéder aux paramètres et aux variables locales de la fonction externe après que le retour de la fonction externe a détruit son cadre de pile? D'une manière ou d'une autre, la fonction interne doit "saisir" les variables utilisées avec elle; une fonction associée à des variables capturées de manière externe est appelée une «fermeture». Pascal ne supporte plus cela; mais par exemple, dans C # 7 (2017), pour cela, un objet est créé sur le tas, contenant tous ces paramètres et variables locales auxquels la fonction interne fait référence; et les appels à la fois depuis celui-ci et depuis la fonction externe ne vont pas aux valeurs de la pile, mais aux champs de l'objet sur le tas. Est-il possible de se passer de cette complication et de continuer à travailler avec la pile - pour éviter un adressage indirect inutile et préserver la localité des appels, et ne pas gâcher le cache de données avec des sauts dans le tas?

2. Continuation de la réussite

Lors de la compilation de langages de programmation fonctionnels, où la capture de variables locales par une fonction de retour est une technique très courante, la première étape consiste à traduire l'ensemble du programme en un «style de passage continu» (CPS). les retours de fonctions sont remplacés par un rappel explicite passé à chaque fonction comme argument supplémentaire. Par exemple, dans cette fonction simple qui calcule le produit de tous les nombres premiers de 1 à n



inclus:

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

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- prodprimes



des adresses de retour différentes sont implicitement transférées vers deux appels . Si ces adresses sont désignées par j



et h



et que l'adresse de retour est passée en tant qu'argument explicite c



, alors tout le transfert de contrôle peut être rendu explicite:

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)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dans CPS, il n'y a aucune différence entre l'appel d'une fonction et le renvoi d'une valeur à partir d'une fonction - les deux sont abstraits comme «transmettre une valeur à une adresse spécifiée». Cette technique a été utilisée dans la plupart des compilateurs Scheme depuis le tout premier (1975); un livre entier "Compiling with Continuations" (1992) lui est consacré, d'où l'exemple ci-dessus est pris. Plus récemment, un style de programmation similaire est devenu populaire sous le nom de «promesses».



La raison pour laquelle CPS a été utilisé en interne par les compilateurs comme représentation intermédiaire avant SSA(inventé en 1988) est devenu plus populaire - simplicité: ce n'est pas un autre langage avec ses propres règles, mais un sous-langage du PL original avec la restriction qu'une fonction ou un appel de continuation n'est autorisé que comme dernière fonction ou opérateur de continuation. Il est facile de traduire du code PL en CPS avec un ensemble de transformations formelles, et il est facile d'appliquer des transformations simplificatrices au code CPS - par exemple, découvrez que la suite est h



triviale et remplacez l'utilisation h



par c



. Une caractéristique importante de CPS pour nous est que les fermetures sont utilisées dans la même portée dans laquelle elles ont été déclarées, et peuvent donc accéder aux variables capturées de l'extérieur de la même manière que dans 80186 - via des pointeurs vers des cadres de pile externes:

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)

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Après conversion en CPS comp



, il sait qu'il s'agit lui-même d'une fonction d'imbrication 2, et que la valeur name



se trouve dans l'image d'imbrication 1, donc la compilation de l'appel à name



ne posera pas de difficultés.



Mais CPS a un inconvénient: puisque les continuations ne s'exécutent jamais return



alors leurs cadres de pile ne sont jamais détruits et la pile débordera très rapidement. En revanche, une continuation peut avoir besoin d'une certaine trame de pile, soit si elle y fait elle-même référence, soit si elle reçoit comme paramètre une continuation qui se réfère à cette trame. De plus, la transition vers la suite suivante doit être la dernière action à l'intérieur de la suite, de sorte que l'adresse et les paramètres de la suite suivante puissent être considérés comme le résultat de la suite. (Le modèle "promesses" renvoie ce résultat explicitement.) Les compilateurs Scheme classiques utilisaient un répartiteur comme boucle infinie suivante:

1. Exécutez la continuation en cours et obtenez l'adresse et les paramètres de la suite suivante en conséquence;
2. Vérifiez quels cadres de pile sont accessibles par les paramètres de continuation et de continuation suivants qui lui sont transmis;
3. , .

Avec cette implémentation, la pile d'appels système n'est pas utilisée et les transitions entre le répartiteur et les suites sont implémentées normalement jmp



. Les trames de continuation sont découplées de la pile d'appels et détruites dans un ordre aléatoire au lieu de LIFO , de sorte que leur collection peut être considérée comme une pile aussi bien que comme un tas.



Comme vous pouvez le deviner, avec un contrôle de pile sur chaque branche entre les continuations, les performances du programme laissaient beaucoup à désirer. L'une des optimisations possibles consiste à vérifier la taille actuelle de la pile avant de quitter la continuation, et si elle ne dépasse pas le seuil spécifié, passer directement à la suite suivante; sinon, transférez le contrôle au répartiteur afin qu'il collecte tous les déchets de la pile. Diplômé de Boston MIT Henry Baker a commenté cette approche: "au lieu de rebondir sur un trampoline tout le temps, nous sautons de l'Empire State Building - mais beaucoup moins souvent."

3. Sur MTA

En 1948, le métro de Boston (Metropolitan Transit Authority) a augmenté les tarifs de 10 cents à 15 cents. Au lieu de remplacer tous les dix sous, à l'entrée du métro, les conducteurs ont reçu l'ordre de facturer un supplément de cinq cents à la sortie du train. Se moquant de cette approche, un candidat à la mairie de Boston a ordonné l'enregistrement d'une chanson sur un certain Charlie, qui n'avait pas assez de sou pour payer une sortie, et il était condamné à prendre le métro à l'infini. Le candidat a acquis une réputation de communiste, n'a remporté que 1,2% des voix aux élections et a quitté la politique pour toujours; Mais la chanson sur le passager qui ne revient jamais à la surface de la terre s'est avérée beaucoup plus populaire: même la carte de métro de Boston, introduite en 2006, s'appelle CharlieCard en l'honneur de ce même passager.



L'histoire de Charlie a inspiré Henry Baker à écrire un compilateur Scheme en 1994 qui transforme chaque continuation en une fonction C afin que l'exécution de ces fonctions n'atteigne jamais return



: par exemple,

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

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- se transforme en

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);
}

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

La signification de l'opérateur return



après une telle conversion est d'indiquer au compilateur C qu'il n'est pas nécessaire de sauvegarder les registres avant d'appeler la suite; en fait, une fonction appelée comme opérande return



ne retournera jamais. À l'endroit marqué comme /* Should check stack here. */



, une vérification de la taille de la pile est insérée et, si nécessaire, le répartiteur est appelé pour le garbage collection.



Cette approche présente plusieurs avantages par rapport à la méthode classique:

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



fold
   
   
   
   , , .

D'autre part, C ne prend pas en charge les fonctions imbriquées, ce qui signifie que tous les pointeurs vers des variables capturées de l'extérieur doivent être explicitement passés avec la fermeture. De plus, lorsque vous placez des trames de continuation sur la pile système au lieu d'une auto-écrite, une difficulté survient: comment implémenter le garbage collection pour la pile système, qui n'est pas liée au périphérique d'un compilateur C spécifique sur une architecture spécifique?

4. Le ramasse-miettes de Cheney

Le tout premier ramasse-miettes le plus simple a été implémenté en 1969 pour LISP: quand la moitié du tas était pleine, le programme s'arrêtait, et toutes les données «en direct» étaient récursivement (traversée en profondeur d'abord) transférées vers la seconde moitié du tas. En 1970, Chris Cheney - également à Cambridge, mais de l'autre côté de l'océan depuis le MIT - a remarqué qu'en parcourant les données en direct dans toute la largeur, le collecteur lui-même n'aurait pas besoin de mémoire supplémentaire pendant la construction; depuis lors, le ramassage des ordures avec l'arrêt du programme et le déplacement des objets vivants vers la seconde moitié du tas a été appelé "algorithme de Cheney". Son principal inconvénient est que les données en direct ne peuvent occuper que la moitié de la mémoire disponible, et la seconde moitié est occupée par un «tampon de copie».



L'efficacité du garbage collection peut être améliorée en observant que les données d'un programme typique sont divisées en "très courte durée" et "très longue durée": si un objet a survécu à un garbage collection, il est très susceptible de survivre au suivant collection aussi. Par conséquent, le tas est divisé en une "pépinière" pour les objets nouvellement créés et un "tas adulte" de deux moitiés. Lorsque la pépinière est pleine, les données en temps réel sont transférées vers le tas adulte; lorsqu'une moitié du tas d'adultes déborde, les données en temps réel sont reportées sur l'autre moitié. Cela économise à la fois de la mémoire (aucun espace n'est réservé pour les données de courte durée dans la seconde moitié du tas) et du temps de génération (les données de longue durée ne sont pas copiées dans les deux sens avec chaque garbage collection dans la pépinière).



Lors de l'utilisation de «Cheney sur le MTA», la pile agit comme une chatterie. Le répartiteur appelé sur le débordement de pile reçoit explicitement comme paramètres des pointeurs vers toutes les données en direct: ce sont tous les paramètres et les variables locales de la continuation appelante, y compris les variables capturées passées à la continuation en tant que paramètre implicite. Contrairement aux garbage collors traditionnels, Cheney sur le MTA n'a pas besoin de rechercher des données en direct à l'intérieur de la pile: CPS garantit que toutes les données sous la dernière image de la pile sont mortes si elles ne sont pas disponibles à partir de la dernière image. Cela signifie que le garbage collector ne se soucie pas de la structure des cadres de la pile, ni de la présence possible de cadres "étrangers" dans la pile, laissés par des fonctions dans d'autres langages.







L'approche «Cheney on the MTA» est utilisée dans les compilateurs C Scheme «Chicken Scheme» (2000) et «Cyclone Scheme» (2016). Dans Cyclone, à l'idée de longue date de Baker, ils ont ajouté la prise en charge du garbage collection parallèle, lorsqu'un seul thread est arrêté pendant la collecte, dont la pile est en cours de traitement, et le reste continue à fonctionner.