Global type inference in the Stalin Schema compiler

Question

I am looking at the Stalin Scheme compiler. He is big and complex. In addition, if I understood correctly, the author planned to write a series of articles detailing implementation aspects, but failed to do so.

The Stalin aspect that interests me is a global type conclusion: deducing the types of things based on their use in other places of the program. Does Stalin really do this? If so, how, and where in its code base? Does it use a variant / extension of the Hindley-Milner algorithm?

Answer 1

From README :

Stalin does global static type analysis using a soft type system that supports recursive connection types. Stalin can define a narrow or even monomorphic type for each expression of the source code in an arbitrary program scheme without type declarations. This allows Stalin to reduce or often eliminate verification and scheduling of runtime. Stalin also makes a low level choice for each expression. This allows the use of basic machine message data representations for unboxed for all monomorphic types, resulting in extremely high-performance numeric code.

From 1997 talk from Siskind :

Stalin performs type inference using complex analysis (SBA aka 0CFA). This analysis is complemented by support for a multivariate cleavage procedure. SBA results are used to reduce verification and dispatch time. SBA results are also used to select a low level representation for each expression. These are two benefits. First, type tags can be omitted for monotypes, allowing the use of basic machine representations for primitive data. Secondly, boxing can be eliminated by reducing the costs of indirection, distribution and reclamation associated with boxing. Eliminating a box requires that the organization at run time allow variables, parameters, structure slots, and vector slots of different widths depending on the type of data they hold. In addition, custom structures can only be unpacked if these structures are unchanged. SBA expands to define data widths and variability at compile time.

The actual type inference algorithm is apparently mainly implemented in the source file source/stalin3b.sc .

SBA / 0CFA seems to be a completely separate algorithm for Hindley-Milner. However, Hindley-Milner can also be used to implement soft printing. A.

Here's a better description of the 0CFA Algorithm .

Relevant articles are Olin Shivers' doctoral dissertation of 1991. An Analysis of Higher-Order Languages ​​or Taming of Lambda and Flagan & Felleisen 1995 Document "Analysis Set" for the complete scheme and its use in Soft-Typing.