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.
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.
The introduction of a 'loop header' block facilitates the hoisting of loop-invariant code from a loop. In a λ-calculus intermediate representation, which has a notion of scope, this transformation is particul...
详细信息
The introduction of a 'loop header' block facilitates the hoisting of loop-invariant code from a loop. In a λ-calculus intermediate representation, which has a notion of scope, this transformation is particularly useful. Loop headers with scope also solve a problem with in-line expansion of recursive functions or loops: if done naively, only the first iteration is inlined. A loop header can encapsulate the loop or recursion for better in-line expansion. This optimization improves performance by about 5% in Standard ML of New Jersey.
In this paper we provide answers to the following problems. 1. Given a data flow graph and a performance constraint, determine a lower-bound on the storage area required for executing the data flow graph while satisfy...
详细信息
ISBN:
(纸本)0818665653
In this paper we provide answers to the following problems. 1. Given a data flow graph and a performance constraint, determine a lower-bound on the storage area required for executing the data flow graph while satisfying the performance constraint. 2. Determine a lower-bound on performance for executing a data flow graph under fixed storage area constraints. The results demonstrate that our approach produces solutions which are very close to the optimal.
The iteration space dependence graph (ISDG) of a loop captures the synchronization requirements of the execution of the loop on parallel machines. Some of the edges in an ISDG may correspond to redundant synchronizati...
详细信息
ISBN:
(纸本)0780318625
The iteration space dependence graph (ISDG) of a loop captures the synchronization requirements of the execution of the loop on parallel machines. Some of the edges in an ISDG may correspond to redundant synchronization statements. In this paper we investigate the removal of such edges in the ISDG of a triply nested loop with constant dependences. We identify a class of triply-nested loops with the property of uniform redundancy. In the case of a general triply-nested loop, we characterize points in the iteration space at which a dependence is redundant.
The development of a unimodular transformation theory and associated algorithms has renewed interest in FORTRAN DO loops that are not perfectly (or tightly) nested. In this paper we summarize a number of techniques th...
详细信息
ISBN:
(纸本)0818666056
The development of a unimodular transformation theory and associated algorithms has renewed interest in FORTRAN DO loops that are not perfectly (or tightly) nested. In this paper we summarize a number of techniques that convert imperfectly nested loops into perfectly nested loops. We examined over 25,000 lines of scientific FORTRAN kernels and benchmarks. Statistics are reported on how often imperfect loops occur and how effective two transformations (scalar forward substitution and loop distribution) are at converting imperfectly nested loops into perfectly nested loops. Further, we describe a compiler that integrates scalar forward substitution, loop distribution, and unimodular transformations while maintaining the basic philosophy of unimodular transformation theory. While our data indicate that imperfectly nested loops still present a problem, the compiler we describe is no more limited by perfectly nested loops than other restructuring compilers available today.
PowerEpsilon is a proof development system based on Martin-Lof's Type theory and the Calculus of Constructions. It contains a logic, a specification language and a programming language, so it is a powerful tool wi...
详细信息
PowerEpsilon is a proof development system based on Martin-Lof's Type theory and the Calculus of Constructions. It contains a logic, a specification language and a programming language, so it is a powerful tool with different uses. However, the constructive type theory is an integrated logic in which the logical and computational parts are associated so well that to extract a program from a proof is not a straightforward task. In this paper, a new approach for extracting program from a proof called type erasing is proposed.
Inlining trials are a general mechanism for making better automatic decisions about whether a routine is profitable to inline. Unlike standard source-level inlining heuristics, an inlining trial captures the effects o...
详细信息
ISBN:
(纸本)0897916433
Inlining trials are a general mechanism for making better automatic decisions about whether a routine is profitable to inline. Unlike standard source-level inlining heuristics, an inlining trial captures the effects of optimizations applied to the body of the inlined routine when calculating the costs and benefits of inlining. The results of inlining trials are stored in a persistent database to be reused when making future inlining decisions at similar call sites. Type group analysis can determine the amount of available static information exploited during compilation, and the results of analyzing the compilation of an inlined routine help decide when a future call site would lead to substantially the same generated code as a given inlining trial. We have implemented inlining trials and type group analysis in an optimizing compiler for SELF, and by making wiser inlining decisions we were able to cut compilation time and compiled code space with virtually no loss of execution speed. We believe that inlining trials and type group analysis could be applied effectively to many high-level languages where procedural or functional abstraction is used heavily.
暂无评论