Iterative Type Inference with Attribute Grammars

作者：Middelkoop Arie^*; Dijkstra Atze; Swierstra S Doaitse

来源：ACM Sigplan Notices, 2011, 46(2): 43-52.

DOI：10.1145/1942788.1868302

• Algorithms
• Languages

Type inference is the process of constructing a typing derivation while gradually discovering type information. During this process, inference algorithms typically make subtle decisions based on the derivation constructed so far.
Because a typing derivation is a decorated tree we aim to use attribute grammars as the main implementation tool. Unfortunately, we can neither express iteration, nor express decisions based on intermediate derivations in such grammars.
We present the language RULER-FRONT, a conservative extension to ordered attribute grammars, that deals with the aforementioned problems. We show why this extension is suitable for the description of constraint-based inference algorithms.

• 出版日期2011-2