We develop the Scott model of the programming language PCF in univalent type theory. Moreover, we work constructively and predicatively. To account for the non-termination in PCF, we use the lifting monad (also known as the partial map classifier monad) from topos theory, which has been extended to univalent type theory by Escard\'o and Knapp. Our results show that lifting is a viable approach to partiality in univalent type theory. Moreover, we show that the Scott model can be constructed in a predicative and constructive setting. Other approaches to partiality either require some form of choice or quotient inductive-inductive types. We show that one can do without these extensions.
翻译:我们开发了编程语言PCF的斯科特模式。 此外,我们以非象素类型理论的方式开发了编程语言PCF模式。 此外,我们以建设性和预想性的方式工作。为了说明PCF中未终结的内容,我们使用了从topos理论(也称为部分地图分类器 Monad ) 开始的提法,Escard\'o和Knapp已经将其扩展为非象素类型理论。我们的结果表明,提法是处理非象素类型理论中偏向性的可行方法。此外,我们证明,斯科特模型可以在预想性和建设性的环境中构建。其他偏向性的方法要么需要某种选择形式,要么需要某种有理的引导型类型。我们显示,没有这些扩展,就可以做到这一点。