
arXiv: 1904.09810
AbstractWe 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ó 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.
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Type theory, Topoi, univalent mathematics, Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.), Scott model, Semantics in the theory of computing, Mathematics - Logic, Categories of fibrations, relations to \(K\)-theory, relations to type theory, PCF, Logic in Computer Science (cs.LO), Categorical semantics of formal languages, lifting monad, Continuous lattices and posets, applications, type theory, partial map classifier, FOS: Mathematics, Functional programming and lambda calculus, Logic (math.LO)
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Type theory, Topoi, univalent mathematics, Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.), Scott model, Semantics in the theory of computing, Mathematics - Logic, Categories of fibrations, relations to \(K\)-theory, relations to type theory, PCF, Logic in Computer Science (cs.LO), Categorical semantics of formal languages, lifting monad, Continuous lattices and posets, applications, type theory, partial map classifier, FOS: Mathematics, Functional programming and lambda calculus, Logic (math.LO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
