论文标题
通过评估打字的lambda演算对标准化的语义分析
Semantic Analysis of Normalisation by Evaluation for Typed Lambda Calculus
论文作者
论文摘要
本文通过评估从分类和代数观点评估打字的Lambda演算的标准化。本文的第一部分通过Kripke逻辑关系分析了Jung和Tiuryn的lambda可确定性结果，并显示了如何适应它以统一确定性和归一化，从而产生了扩展的归一化结果。在本文的第二部分中，通过考虑强度的kripke关系（以artin胶的形式）进一步完善了分析，并证明可以为术语归一化，从而在分类胶水的背景下通过评估来归一化。技术开发包括对语法的代数处理和类型lambda conculus的语义，该语法允许在简单键入的Metatheory中给出标准化函数的定义。合成了相关功能编程语言中的逐评性程序。
This paper studies normalisation by evaluation for typed lambda calculus from a categorical and algebraic viewpoint. The first part of the paper analyses the lambda definability result of Jung and Tiuryn via Kripke logical relations and shows how it can be adapted to unify definability and normalisation, yielding an extensional normalisation result. In the second part of the paper the analysis is refined further by considering intensional Kripke relations (in the form of Artin glueing) and shown to provide a function for normalising terms, casting normalisation by evaluation in the context of categorical glueing. The technical development includes an algebraic treatment of the syntax and semantics of the typed lambda calculus that allows the definition of the normalisation function to be given within a simply typed metatheory. A normalisation-by-evaluation program in a dependently-typed functional programming language is synthesised.
