The question of whether the use of good naming style in programs improves program comprehension has important implications for both programming practice and theories of program comprehension. Two experiments were done...
详细信息
The question of whether the use of good naming style in programs improves program comprehension has important implications for both programming practice and theories of program comprehension. Two experiments were done based on Pennington's (Stimulus structures and mental representations in expert comprehension of computer programs, Cognitive Psychology,19, 295-341, 1987) model of programmer comprehension. According to her model, different levels of knowledge, ranging from operational to functional, are extracted during comprehension in a bottom-up fashion. It was hypothesized that poor naming style would affect comprehension of function, but would not affect the other sorts of knowledge. An expertise effect was found, as well as evidence that knowledge of program function is independent of other sorts of knowledge. However, neither novices nor experts exhibited strong evidence of bottom-up comprehension. The results are discussed in terms of emerging theories of program comprehension which include knowledge representation, comprehension strategies, and the effects of ecological factors such as task demands and the role-expressiveness of the language.
We present the dynamically typed lambda-calculus, an extension of the statically typed lambda-calculus with a special type Dyn and explicit dynamic type coercions corresponding to run-time type tagging and type check-...
详细信息
We present the dynamically typed lambda-calculus, an extension of the statically typed lambda-calculus with a special type Dyn and explicit dynamic type coercions corresponding to run-time type tagging and type check-and-untag operations. Programs in run-time typed languages can be interpreted in the dynamically typed lambda-calculus via a nondeterministic completion process that inserts explicit coercions and type declarations such that a well-typed term results. We characterize when two different completions of the same run-time typed program are coherent with an equational theory that is independent of an underlying lambda-theory. This theory is refined by orienting some equations to define safety and minimality of completions. Intuitively, a safe completion is one that does not produce an error at run-time which another completion would have avoided, and a minimal completion is a safe completion that executes fewest tagging and check-and-untag operations amongst all safe completions. We show that every untyped lambda-term has a safe completion at any type and that it is unique modulo a suitable congruence relation. Furthermore, we present a rewriting system for generating minimal completions. Assuming strong normalization of this rewriting system we show that every lambdaI-term has a minimal completion at any type, which is furthermore unique modulo equality in the dynamically typed lambda-calculus.
In this paper we demonstrate that the basic rules and calculational techniques used in two extensively documented program derivation methods can be expressed, and, indeed, can be generalised within a relational theory...
详细信息
In this paper we demonstrate that the basic rules and calculational techniques used in two extensively documented program derivation methods can be expressed, and, indeed, can be generalised within a relational theory of datatypes. The two methods to which we refer are the so-called ''Bird-Meertens formalism'' for the construction of functional programs and the ''Dijkstra-Feijen calculus'' for the construction of imperative programs.
This paper lifts earlier category-theoretic results on datatypes to the level of an abstract language suitable for categorical programming language implementation. The earlier work built a strongly normalizing categor...
详细信息
This paper lifts earlier category-theoretic results on datatypes to the level of an abstract language suitable for categorical programming language implementation. The earlier work built a strongly normalizing categorical combinator reduction system based entirely on functorial strength which allows the distribution of context to the interior of datatypes. Here we declare inductive (initial) and coinductive (final) datatypes in a Hagino-Wraith style to provide an expressive computing environment. An inductive (resp. coinductive) datatype consists of a strong type-forming functor accompanied by (1) a collection of constructors (resp. destructors) and (2) a fold (resp, unfold) which is parametrized by state transformations to realize the appropriate universal property. The high complexity of programming exclusively in categorical notation (combinators) warrants the development of a friendlier language isomorphic to the distributive categorical setting. In this paper such a term logic, which is also the programming language of the charity programming system, is described, This logic is first-order and is dictated directly by the underlying categorical semantics, It embodies primitive inductive and coinductive principles which reflect the uniqueness properties of the fold and unfold combinators. Several basic program equivalences are demonstrated to illustrate how these inductive and coinductive principles can be used.
It is well-known that termination is not a modular property of term rewriting systems, i.e., it is not preserved under disjoint union. The objective of this paper is to provide a ''uniform framework'' ...
详细信息
It is well-known that termination is not a modular property of term rewriting systems, i.e., it is not preserved under disjoint union. The objective of this paper is to provide a ''uniform framework'' for sufficient coditions which ensure the modularity of termination. We will prove the following result. Whenever the disjoint union of two terminating term rewriting systems is nonterminating, then one of the systems is not C-E-terminating (i.e., it loses its termination property when extended with the rules Cons(x, y)--> x and Cons(x, y)--> y) and the other is collapsing. This result has already been achieved by Gramlich [7] for finitely branching term rewriting systems. A more sophisticated approach is necessary, however, to prove it in full generality. Most of the known sufficient criteria for the preservation of termination [24,.15, 13, 7] follow as corollaries from our result, and new criteria are derived. This paper particularly settles the open question whether simple termination is modular in general. We will moreover shed some light on modular properties of combined systems with shared constructors. For instance, it will be shown that the above result does not carry over to constructor-sharing systems.
Katsuno and Mendelzon have distinguished two abstract frameworks for reasoning about change: theory revision and theory update. theory revision involves a change in knowledge or belief with respect to a static world. ...
详细信息
Katsuno and Mendelzon have distinguished two abstract frameworks for reasoning about change: theory revision and theory update. theory revision involves a change in knowledge or belief with respect to a static world. By contrast, theory update involves a change of knowledge or belief in a changing world. In this paper, we are concerned with theory update. Winslett has shown that theory update should be computed ''one model at a time.'' Accordingly, we focus exclusively on the update of interpretations. We begin with a study of revision programming, introduced by Marek and Truszczynski to formalize interpretation update in a language similar to logic programming. While revision programs provide a useful and natural definition of interpretation update, they are limited to a fairly restricted set of update rules. Accordingly, we introduce the more general notion of rule update-interpretation update by arbitrary sets of inference rules. We show that Winslett's approach to update by means of arbitrary sets of formulas corresponds to a simple subclass of rule update. We also specify a simple embedding of rule update in Reiter's default logic, obtained by augmenting the original update rules with default rules encoding the commonsense law of inertia-the principle that things change only when they are made to. (C) Elsevier Science Inc., 1997
We present three refinement principles supporting the transition from system specifications based on (unbounded) asynchronous communication to system specifications based on (bounded) synchronous communication. We ref...
详细信息
We present three refinement principles supporting the transition from system specifications based on (unbounded) asynchronous communication to system specifications based on (bounded) synchronous communication. We refer to these principles as partial, total and conditional refinement, respectively. We distinguish between two synchronization techniques, namely synchronization by hand-shake and synchronization by real-time constraints. Partial refinement supports synchronization by hand-shake with respect to safety properties. Total refinement supports synchronization by hand-shake with respect to both safety and liveness properties. Finally, conditional refinement supports both synchronization by hand-shake and by real-time constraints. We discuss, relate and show the use of these principles in a number of small examples.
A systematic approach is given for deriving incremental programs from non-incremental programs written in a standard functional programming language. We exploit a number of program analysis and transformation techniqu...
详细信息
A systematic approach is given for deriving incremental programs from non-incremental programs written in a standard functional programming language. We exploit a number of program analysis and transformation techniques and domain-specific knowledge, centered around effective utilization of caching, in order to provide a degree of incrementality not otherwise achievable by a generic incremental evaluator.
We present a new principle for the development of database query languages that the primitive operations should be organized around types. Viewing a relational database as consisting of sets of records, this principle...
详细信息
We present a new principle for the development of database query languages that the primitive operations should be organized around types. Viewing a relational database as consisting of sets of records, this principle dictates that we should investigate separately operations for records and sets. There are two immediate advantages of this approach, which is partly inspired by basic ideas from category theory. First, it provides a language for structures in which record and set types may be freely combined: nested relations or complex objects. Second, the fundamental operations for sets are closely related to those for other ''collection types'' such as bags or lists, and this suggests how database languages may be uniformly extended to these new types. The most general operation on sets, that of structural recursion, is one in which not all programs are well-defined. In looking for limited forms of this operation that always give rise to well-defined operations, we find a number of close connections with existing database languages, notably those developed for complex objects. Moreover, even though the general paradigm of structural recursion is shown to be no more expressive than one of the existing languages for complex objects, it possesses certain properties of uniformity that make it a better candidate for an efficient, practical language. Thus rather than developing query languages by extending, for example, relational calculus, we advocate a very powerful paradigm in which a number of well-known languages are to be found as natural sublanguages.
From a theoretical point of view, lazy evaluation corresponds to the call-by-name evaluation method, which substitutes arguments for parameters before evaluating them and never evaluates under a lambda. From an implem...
详细信息
From a theoretical point of view, lazy evaluation corresponds to the call-by-name evaluation method, which substitutes arguments for parameters before evaluating them and never evaluates under a lambda. From an implementation perspective, lazy evaluation is often equated with the call-by-need method, which is similar to call-by-name except that arguments are shared. When an argument's value is required, it is evaluated and its result is stored and used for any other reference to it. The theoretical version of lazy evaluation, or call-by-name, is easily formalized with the reduction rules of lambda calculus. However, it has proven rather difficult to formalize the rules of lazy evaluation with sharing, or call-by-need, in such a way that it both captures sharing and is useful for reasoning. Many optimizations are based on analyses of program behavior which are dependent on whether arguments are implemented via sharing or not. Thus, it is important to have such a model of lazy evaluation in order to develop correct analyses. In this paper, an operational semantics of PCF is presented which captures the sharing inherent in the call-by-need implementation of lazy evaluation in a form that is suitable for reasoning. The semantics uses explicit substitutions to implement sharing. The link between the theoretical and implementation versions of lazy evaluation is made by showing the correctness of the call-by-need semantics with respect to a standard call-by-name semantics for PCF.
暂无评论