Прагматика типизированных промежуточных языков

Question

Одной из тенденций в компиляции является использование типизированных промежуточных языков. Хаскеля ghc с этими core Промежуточный язык, вариант System F-omega, является примером этой архитектуры [ 1 ]. Другой - LLVM, в основе которого лежит типизированный промежуточный язык [ 2 ]. Преимущество этого подхода заключается в том, что ошибки в преобразованиях, составляющих части генератора кода, могут быть обнаружены на ранней стадии. Кроме того, информация о типе может использоваться во время оптимизации и генерации кода.

Для эффективности типизированные IR проверяются по типу, а не по типу. Для быстрой проверки типов каждая переменная и каждое связующее средство содержат типы для простой проверки типов.

Однако многие преобразования в конвейере компилятора могут вводить новые переменные. Например, преобразование нормализации K(.) может преобразовать приложение

M(N)

в выражение, подобное

let x = K(M) in
let y = K(N) in x(y)

Вопрос. Интересно, как компиляторы решают вопрос о присвоении типов вновь введенным переменным. Они повторно проверяют, в примере выше K(M) а также K(N)? Разве это не занимает много времени? И это требует передачи окружающей среды? Используют ли они карты из узлов AST для ввода информации, чтобы избежать повторной проверки типов?

---

1. С. Марлоу, С. Пейтон Джонс, Glasgow Haskell Compiler.

2. LLVM Language Reference Manual.

Answer 1

Они повторно проверяют тип, в приведенном выше примере K(M) и K(N)?

Да, это так. Впрочем, это не так уж и плохо. Средство проверки типов знает, что это приложение к . Он знает, что такое тип, и это должен быть тип функции. Он знает, какой типMесть, и он может проверить, совпадает ли он с типом ввода функции. Таким образом, он знает, что имеет тип вывода . Программа проверки типов также знает, что это приложение кN. Он знает, чтоK(N)имеет тот же тип, что иK(M). И он знает, что это приложение к . Он знает, что имеет тип функции и чтоyимеет тот же тип, что и тип ввода . Так это знает, чтоx(y)имеет тот же тип, что иxтип вывода. Таким образом, он знает, что все выражение имеет тот же тип, что иKтип вывода.

Разве это не отнимает много времени?

Не совсем. Средство проверки типов не обязано проверять выражение целиком, прежде чем оно сможет начать проверку типов. Он может проверять подвыражения по мере их поступления и выполнять некоторое кэширование, чтобы избежать повторной проверки уже проверенных подвыражений.

И требует ли это прохождения окружения? Используют ли они карты из узлов AST для ввода информации, чтобы избежать повторной проверки типов?

Да, это так. И они используют карты из узлов AST для ввода информации, но они не используют их, чтобы избежать повторной проверки типов. Они используют их, чтобы избежать повторной проверки одного и того же типа для одного и того же выражения. (Возможно, это одно и то же, я не совсем уверен.)