λ演算中的第二不动点定理

作者研究λ演算中第二不动点的性质，首先关于第二不动点的３个例题之间的关系且证明了这们，然后为第二不动点组合子给以一个充分条件且作一系列的第二不动点组子，作者还提出和证明了多元第二不点宣。     

λ演算中的第二不动点定理*

作者研究λ演算中的第二不动点的性质．首先讨论关于第二不动点的3个命题之间的关系且证明了它们．然后为第二不动点组合子给以一个充分条件且作出一系列的第二不动点组合子．作者还提出和证明了多元第二不动点定理．     

X—演算与π—演算的语义比较研究

Through the comparison of syntactic structure,operational semantics and algebraic semantics between χ-calculus and π-calculus, this paper concludes that χ-calculus has more succinct syntactic structure,more explicit operational semantics,more intuitionistic algebraic semantics and more favorable algebraic property. And a translation from π-calculus to χ-calculus is presented.     

泛函程序设计语言实现中的图归约演算

本文叙述了在Ｖｏｎ Ｎｅｕｍａｎｎ机器上实现基于λ演算，ＳＫＩ演算的泛函程序设计语言所采用的图归约演算。ＳＫＩ－Ｇ演算是ＳＫＩ演算的图形表示，是基于图形的形式归约系统，面向机器实现，是实现高阶，引用透明，归约语义，全惰性泛函程序设计语言的主要技术基础。     

多态X—演算

The paper proposes polyadic χ-calculus.The language is stronger than χ-calculus in communication.It can exchange several information once time.In the paper we define the syntax and semantics structure of polyadic χ-calculus,and study the hisimulation relations of it.     

扩充逻辑程序设计的R—演算—知识库维护的操作方法

本文首先介绍了知识库维护过程中诸如知识库序列、新规则、用户反驳以及重构等概念；然后给出了一个扩充逻辑程序设计的框架，在这一框架下，每个逻辑程序等价于一个知识库；进一步定义了一个转换系统，称为扩充逻辑程序设计的Ｒ－演算，对一个给定的知识库和用户反驱，此演算可以导出知识库的最佳修正；同时证明了该演算的可靠性和完备性；另外，对本文的工作与其他相关工作进行了比较；最后，给出了本文的结论。     

广义λ－调解

本文提出了算子模糊逻辑中的广义λ－调解方法，证明了它和广义λ－归结的联合使用，对于λＥ－不可满足广义子句集是完备的．     

对象演算II

章应用Ｇｏｇｕｅｎ等人的结论证明并得到了几个结构化对象演算的基本定理。一方面,这些定理保证了该可由现有对象的描述构造新对象的描述,并且可以把建立在现有对象上的定理作为整个对象描述和验证的引理。另一方面,章还讨论了基于封装性的对象精化。于是得到一个结构化的对象演算系统。     

具有代数算子的λ演算系统的模型构造

本文介绍了一个带有代数算子的λ演算系统,并给出了该系统模型的定义,证明了一个满足该定义的充分条件,最后构造了该系统的一个模型。     

带Mismatch算子的高阶π演算

主要研究带mismatch的高阶进程演算的公理化问题。首先,建立存在mismatch时高阶进程的开弱高阶互模拟理论,证明了等价关系、同余性等重要性质;其次,沿用线性的方法,构建得到带 mismatch 的有限进程上的公理系统;最后,基于对开弱高阶互模拟的刻画,证明了该公理系统的完备性定理。该工作为带 mismatch 的高阶进程上互模拟判定的有效算法的设计与实现,进而为相关的应用建模工作提供了理论借鉴。     

Some Lambda Calculus and Type Theory Formalized

We survey a substantial body of knowledge about lambda calculus and Pure Type Systems, formally developed in a constructive type theory using the LEGO proof system. On lambda calculus, we work up to an abstract, simplified proof of standardization for beta reduction that does not mention redex positions or residuals. Then we outline the meta theory of Pure Type Systems, leading to the strengthening lemma. One novelty is our use of named variables for the formalization. Along the way we point out what we feel has been learned about general issues of formalizing mathematics, emphasizing the search for formal definitions that are convenient for formal proof and convincingly represent the intended informal concepts.     

Linear-Time Self-Interpretation of the Pure Lambda Calculus

We show that linear-time self-interpretation of the pure untyped lambda calculus is possible, in the sense that interpretation has a constant overhead compared to direct execution under various execution models. The present paper shows this result for reduction to weak head normal form under call-by-name, call-by-value and call-by-need.We use a self-interpreter based on previous work on self-interpretation and partial evaluation of the pure untyped lambda calculus.We use operational semantics to define each reduction strategy. For each of these we show a simulation lemma that states that each inference step in the evaluation of a term by the operational semantics is simulated by a sequence of steps in evaluation of the self-interpreter applied to the term (using the same operational semantics).By assigning costs to the inference rules in the operational semantics, we can compare the cost of normal evaluation and self-interpretation. Three different cost-measures are used: number of beta-reductions, cost of a substitution-based implementation (similar to graph reduction) and cost of an environment-based implementation.For call-by-need we use a non-deterministic semantics, which simplifies the proof considerably.     

Lambda Calculus with Explicit Recursion

This paper is concerned with the study ofλ-calculus with explicit recursion, namely of cyclicλ-graphs. The starting point is to treat aλ-graph as a system of recursion equations involvingλ-terms and to manipulate such systems in an unrestricted manner, using equational logic, just as is possible for first-order term rewriting. Surprisingly, now the confluence property breaks down in an essential way. Confluence can be restored by introducing a restraining mechanism on the substitution operation. This leads to a family ofλ-graph calculi, which can be seen as an extension of the family ofλσ-calculi (λ-calculi with explicit substitution). While theλσ-calculi treat the let-construct as a first-class citizen, our calculi support the letrec, a feature that is essential to reason about time and space behavior of functional languages and also about compilation and optimizations of programs     

A Calculus of Lambda Calculus Contexts

The calculus c serves as a general framework for representing contexts. Essential features are control over variable capturing and the freedom to manipulate contexts before or after hole filling, by a mechanism of delayed substitution. The context calculus c is given in the form of an extension of the lambda calculus. Many notions of context can be represented within the framework; a particular variation can be obtained by the choice of a pretyping, which we illustrate by three examples.     

Structures Definable in Polymorphism

Encodings in polymorphism with finite product types are considered.These encodings are given in terms of I-algebras.They have th property that the ground terms are precisely the closed normal terms of the encoded types.The proof of a well-known result is transplanted to the setting and it is shown why weak recursion is admissible.The paper also shows how to carry out the dual encodings using the existential quantifier.     

Strictness analysis in the Imperative Lambda Calculus

Concerns over efficiency and expressiveness of functional languages have motivated the study of languages that allow state and pure functionality to coexist peacefully. However, state-oriented features complicate the static analyses which are essential for efficient compilation of these languages. The problem is an interesting one because it combines traditional strictness analysis with the abstract storage structure analysis familiar from imperative languages. We apply the technique of abstract interpretation to perform strictness analysis in the Imperative Lambda Calculus of Swarup, Reddy, and Ireland. A basic analysis is presented, along with some extensions to handle certain evident weaknesses; proofs for these analyses are discussed in some detail.Partially supported by NASA grant NAG-1-613Partially supported by NSF grant CCR 93-03043     

命令的操作语义在类型系统中的一种表示

类型系统建立在一个小的规则集合基础上，易于实现，可理解性好，且具有计算完全性和足够的表达能力,在类型系统中可以重述推导规则，将其形式化为一些归纳关系，从而直接表示了命令的操作语义,类型理论不仅适合于函数式程序的证明，也是刻画和证明命令式程序的合适的框架。     

Congruence of Bisimulation in a Non-Deterministic Call-By-Need Lambda Calculus

We present a call-by-need λ-calculus λ_ND with an erratic non-deterministic operator pick and a non-recursive let. A definition of a bisimulation is given, which has to be based on a further calculus named λ_≈, since the naïve bisimulation definition is useless. The main result is that bisimulation in λ_≈ is a congruence and coincides with the contextual equivalence. The proof is a non-trivial extension of Howe's method. This might be a step towards defining useful bisimulation relations and proving them to be congruences in calculi that extend the λ_ND-calculus.     

对象式Lambda演算的自作用部分计值

讨论了一个对象式Lambda演算的部分计值器.对象式Lambda演算在Lambda演算的基础上添加了对象机制.部分计值器的构造是采用传统的三步法,首先定义对象式Lambda演算的元解释器;然后提出对象式Lambda演算的约束时间分析方法(binding-timeanalysis),约束时间分析决定哪些计算可以在编译时完成,哪些计算需留在运行时执行;最后定义部分计值器,同时,给出了元解释器和部分计值器的正确性证明.