Globale Art Inferenz in der Scheme-Compiler Stalin

Question

Ich bin in den Scheme Compiler Stalin. Es ist groß und komplex. Außerdem, wenn ich richtig verstanden habe, plante der Autor, eine Reihe von Papieren zu schreiben, die Aspekte der Implementierung aufzählten, kam aber nie dazu, das zu tun.

Der Aspekt von Stalin, an dem ich interessiert bin, ist die globale Typinferenz: die Art der Dinge basierend auf ihrer Verwendung an anderen Stellen im Programm abzuleiten. Macht Stalin das wirklich? Wenn ja, wie und wo in seiner Codebasis? Verwendet es eine Variante/Erweiterung eines Hindley-Milner-Algorithmus?

Answer 1

Vom README:

Stalin hat globale statische Typanalyse mit einem weichen Typ-System, das rekursive Vereinigungstypen unterstützt. Stalin kann für jeden Quellcodeausdruck in beliebigen Programmen ohne Typdeklarationen einen schmalen oder sogar monomorphen Typ bestimmen. Dies ermöglicht Stalin zu reduzieren, oder oft zu beseitigen, Laufzeit-Typ-Prüfung und Versand. Stalin auch macht Low-Level-Repräsentation Auswahl pro Ausdruck-Basis. Dies ermöglicht die Verwendung von unverpackten Basismaschinen-Datendarstellungen für alle monomorphe Typen, die zu extrem leistungsfähigem numerischem Code führen.

Aus 1997 talk by Siskind:

Stalin führt Typinferenz mit Set-basierte Analyse (SBA aka 0CFA). Diese Analyse wird erweitert, um die multivariante Prozedur zu unterstützen. Die Ergebnisse von SBA werden verwendet, um den Laufzeittyp zu überprüfen und zu versenden. Die Ergebnisse von SBA werden auch verwendet, um eine Low-Level-Repräsentationsauswahl auf einer Pro-Expressionsbasis zu machen . Dies hat zwei Vorteile. Erstens können Typ-Tags für Monotypien eliminiert werden, , die die Verwendung von Basismaschinenrepräsentationen für primitive Daten erlauben. Zweitens kann das Boxen eliminiert werden, was die Kosten von Indirection, Allokation und Reklamation verringert, die mit Boxen verbunden sind. Das Beseitigen von Boxen erfordert, dass die Laufzeitorganisation Variablen, Parametern, Struktursteckplätzen und Vektorsteckplätzen unterschiedliche Breiten zulässt, je nach Art der Daten, die sie halten. Darüber hinaus können benutzerdefinierte Strukturen nur dann entkoppelt werden, wenn diese Strukturen unveränderlich sind. SBA wird erweitert, um Daten Breiten und Mutabilität zur Kompilierzeit zu bestimmen.

Der tatsächliche Typ Inferenzalgorithmus scheint hauptsächlich in der Quelle Datei source/stalin3b.sc umgesetzt werden.

Es scheint, dass SBA/0CFA ein völlig separater Algorithmus zu Hindley-Milner ist. Hindley-Milner kann jedoch auch zur Implementierung von Soft-Typisierung verwendet werden.

Hier ist ein schöner description of the 0CFA algorithm.

Relevante Papiere sind 1991 Dissertation ctrl-flow Olin Shivers Analyse von höherer Ordnung Sprachen oder Taming Lambda und Flanagan & 1995er Felleisen Papier Set Basierte Analyse für Full Schema und seine Verwendung in Soft- Eingabe.