函数／逻辑语言归约实现技术

ＲＦＵＮＬＯＧ是我们在ＬＮＦ演算基础上自行设计实现的一种函数／逻辑语言，它具有统一的操作语义。本文介绍ＲＦＵＮＬＯＧ语言的总体结构、归约操作语义及其解释实现技术。     

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

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

函数／逻辑程序设计语言RFUNILOG

本文提出了一种兼备函数／逻辑功能的程序设计语言ＲＦＵＮＬＯＧ。它不仅具有统一的语法形式和丰富的语言设施，而且有统一的操作语义，整个语言可以用图归约的概念来解释。     

DDFP语言的归约机实现技术

ＤＤＦＰ语言是一种基于表达式的泛函程序设计语言，这是一种具有归约语义的，引用透明的，能表达无限数据结构，高阶纯粹的函数式语言。它的实现是基于λ演算、ＳＬＩ演算、ＳＫＬ－Ｇ演算、ＬＮＦ演算及图归约技术。本文在［４］的基础上首先引进了ＬＮＦ演算，而后详细介绍了该语言的归约机实现技术，对结果作了讨论。     

Verilog代数语义研究

给出了Verilog的代数语义.这是一个等式公理体系,它将Verilog语义特征通过代数规则简洁而准确地表达出来;并且这个代数语义相对于已经所作的操作语义模型来讲是可靠的,即所有的这些代数规则左右两边的进程在操作语义的观察模型下都是互模拟的.研究了此代数语义的相对完备性,即参照前面的操作语义模型,相对于扩展Verilog语言的一个子集而言,此代数语义是完备的.即所有符合这样语法的程序,如果它们是互模拟等价的,那么它们同样可以在所提出的代数系统中被推导相等.在完备性证明过程中,采用范式方法,即构造一种语法上特殊的程序,任何属于上述子集中的一个程序通过该代数规则都能够被转化为范式程序,而且范式程序在操作语义模型下是互模拟的当且仅当它们是语法相同的.上述结果具有重要的理论意义,因为现有的进程代数理论主要是针对管道通信并行语言而展开的,而对于像Verilog这种以共享变量通信为基础的复杂并行语言研究还是比较少的,对此类复杂的基于共享变量的并行语言的进程代数理论研究提出了一种通用、有效的方法.     

归约算法统一描述

归约算法在并行计算中应用广泛,目前有很多归约算法应用于不同的情形。这些归约算法各不相同, 逻辑拓扑是 造成区别的关键 。为了统一描述归约算法,揭示它们的共性,给出了一个逻辑拓扑的定义及其性质。在此基础上,给出了归约算法的统一描述,以利于对归约算法的理解,从而设计适应不同应用和环境的归约算法。该描述也可视为可集成不同语义的归约算法框架,从而有助于设计具有新语义的归约算法。本质上,该统一描述是一个归约算法形式定义,有助于验证归约算法的正确性。     

DFA模型及其语言的结构化代数规约

本文首先阐述了利用ＤＦＡ模型技术进行状态转换系统描述存在的主要问题,提出了利用代数规约技术解决这些问题的可行性,然后介绍了新一代具有松散语义的代数规约语言ＳＰＥＣＴＲＵＭ及其主要规约操作符的语法和语义,并根据ＤＦＡ模型及其语言的数学定义,给出了它们的结构化代数规约,为基于ＤＦＡ模型的状态转换系统的形式化设计和开发奠定了基础。     

成员系统模型及其归约

本文提出了一种基于有限关联团块观点的成员系统模型，主要针对不确定性情况给出了其归约操作的形式化描述，讨论了它与产生式系统的关系，并根据该模型及其归约过程，成功地设计实现了一种并发成员系统程序计算语言，对研究支持多种ＡＩ问题求解的模型及其语言做了有益的尝试。     

含有某种限制的上下文无关文法之LR分析

本文给出一种扩充LR分析方法以使其能够处理含有嵌套限制的上下文无关文法之办法。在基于LR的分析程序中，通常要借助执行LR方法的上下文以外的语义代码处理这样的限制，由于LR方法本身就含有这样的限制，所以潜在的移动归纳与归约归约的冲突可被解决并能进一步制约认可的语言，推荐的方法很蝗于并入现有的基于LR的分析程序生成系统。     

机器定理证明的反向归约方法

基于代数和递归函数理论，本文定义了代数递归谓词．代数递归谓词是一类广泛的谓词．基于数学归纳法，作者给出了证明代数递归谓词永真性的反向归约方法及相应的算法Ｒｅｄｕｃｔｉｏｎ．由于采用反向归约方式来完成定理证明，从根本上消除了正向组合式定理证明所产生的组合爆炸，因而极大地提高了定理证明的效率．     

Garment中多态类型的Ideal模型

本文从Ideal的基本概念出发,研究了Ideal作为类型的语义模型所具有的性质.在类型的Ideal模型下,讨论了Garment中参数化多态类型和约束多态类型的语义.并在此基础上,证明了Garment中类型规则的语义可靠性.     

M-nets: An algebra of high-level Petri nets, with an application to the semantics of concurrent programming languages

This paper describes a high-level Petri net model called M-nets (for modular multilabelled nets). A distinctive feature of this model is that it allows both: unfolding, as do most other high-level net models; and composition – in particular, synchronisation – in a process algebraic style, turning the set of M-nets into an algebraic domain. It turns out that the composition operations of this domain have various algebraic properties. Moreover, the model is such that composition operations are coherent with unfolding, in the sense that the unfolding of a composite high-level net is the composition of the unfoldings of its components. One of the motivations for M-nets is that they be a vehicle for giving semantics of concurrent programming languages. To illustrate their capability for that, the compositional semantics of – a simple, expressive concurrent programming language – is given. An associated low-level net semantics is described, and the coherence of these high-level and low-level semantics is proved. Received: 20 November 1996 / 13 January 1998     

Partial abstract types

Summary Hierarchical abstract types, where particular sorts, operations, and axioms are designated as primitive, with conditional equational formulas are studied. Introducing notions of different homomorphisms particular models of this class can be distinguished as initial or (weakly) terminal. Sufficient conditions for the existence of such models are given and their relationship to the principle of fully abstract semantics is investigated. By this the concept of algebraic specification is extended to specify the semantics of programming languages in a completely abstract algebraic way as it is demonstrated for two toy languages.This research has been partially sponsored by the Sonderforschungsbereich 49 — Programmiertechnik, München     

Fundamental properties of infinite trees

Infinite trees naturally arise in the formalization and the study of the semantics of programming languages. This paper investigates some of their combinatorial and algebraic properties that are especially relevant to semantics.This paper is concerned in particular with regular and algebraic infinite trees, not with regular or algebraic sets of infinite trees. For this reason most of the properties stated in this work become trivial when restricted either to finite trees or to infinite words.It presents a synthesis of various aspects of infinite trees, investigated by different authors in different contexts and hopes to be a unifying step towards a theory of infinite trees that could take place near the theory of formal languages and the combinatorics of thefree monoid.     

函数式逻辑语言的操作语义

函数式语言和逻辑语言在下列意义上是互补的,基于归约的函数式程序设计语言具有确定和懒惰求解等性质.但同时它又缺少诸如存在量化的变量以及部分数据结构等所希望的性质.相反,基于HORN子句逻辑和消解原理的逻辑程序设计语言允许存在量化的变量和部分数据结构但又缺少确定和懒惰求解的性质.从这个角度出发,把函数和逻辑程序设计语言结合成一种范型是很自然的,这种结合提供了一种比逻辑和函数语言表达能力更强的合一语言.提出了函数式逻辑语言的操作语义,同时表明这种操作语义在实践中是可见的.     

Imperative abstractions for functional actions

We elaborate our relational model of non-strict, imperative computations. The theory is extended to support infinite data structures. To facilitate their use in programs, we extend the programming language by concepts such as procedures, parameters, partial application, algebraic data types, pattern matching and list comprehensions. For each concept, we provide a relational semantics. Abstraction is further improved by programming patterns such as fold, unfold and divide-and-conquer. To support program reasoning, we prove laws such as fold–map fusion, otherwise known from functional programming languages. We give examples to show the use of our concepts in programs.     

Executing continuation semantics: A comparison

Several authors have suggested translating denotational semantics into prototype interpreters written in high-level programming languages to provide evaluation tools for language designers. These implementations have generally been understandable when restricted to direct denotational semantics. This paper considers using two declarative programming languages, Prolog and Standard ML, to implement an interpreter that follows the continuation semantics of a small imperative programming language, called Gull. Each of the two declarative languages presents certain difficulties related to evaluation strategies and expressiveness. The implementations are compared in terms of their ease of use for prototyping, their resemblance to the denotational definitions, and their efficiency.