In functional programming, intermediate data structures are often used to 'glue' together small programs. Deforestation is a program transformation to remove these intermediate data structures automatically. W...
详细信息
ISBN:
(纸本)9780897917193
In functional programming, intermediate data structures are often used to 'glue' together small programs. Deforestation is a program transformation to remove these intermediate data structures automatically. We present a simple algorithm for deforestation based on two fusion rules for hylomorphism, an expressive recursion pattern. A generic notation for hylomorphisms is introduced, where natural transformations are explicitly factored out, and it is used to represent programs. Our method successfully eliminates intermediate data structures of any algebraic type from a much larger class of compositional functional programs than previous techniques.
In an attempt to devise a general notion of model for spatial logic, we have been led to consider transition systems with an additional so-called spatial structure on the states, with both the tran- sition and the spa...
详细信息
Many consider the bugs expected to rise at the change of the century to be a normal maintenance issue. In this paper we show, that there are some significant differences. Taking advantage of this differences may help ...
详细信息
Many consider the bugs expected to rise at the change of the century to be a normal maintenance issue. In this paper we show, that there are some significant differences. Taking advantage of this differences may help to lower migration costs. We look at how organizations adapt their maintenance capabilities to the demand. Under normal conditions this strategy helps simultaneously to cope with the occurring bug load and to keep costs down. Century change related bugs, however, occur in large quantity also in programs with very low error rates in the past, bringing organization in a situation they are not prepared to. We deduce, that more mechanical approaches may be more appropriate and cost effective. A list of criteria is deduced to find the best approach in a given situation.
One of the major challenges in denotational semantics is the construction of fully abstract models for sequential programming languages. For the past fifteen years, research on this problem has focused on developing m...
详细信息
ISBN:
(纸本)0897914538
One of the major challenges in denotational semantics is the construction of fully abstract models for sequential programming languages. For the past fifteen years, research on this problem has focused on developing models for PCF, an idealized functional programming language based on the typed lambda calculus. Unlike most practical languages, PCF has no facilities for observing and exploiting the evaluation order of arguments in procedures. Since we believe that such facilities are crucial for understanding the nature of sequential computation, this paper focuses on a sequential extension of PCF (called SPCF) that includes two classes of control operators: error generators and escape handlers. These new control operators enable us to construct a fully abstract model for SPCF that interprets higher types as sets of error-sensitive functions instead of continuous functions. The error-sensitive functions form a Scott domain that is isomorphic to a domain of decision trees. We believe that the same construction will yield fully abstract models for functional languages with different control operators for observing the order of evaluation.
StarLogo is programmable modeling environment designed to help nonexpert users (in particular, precollege students) model and explore decentralized systems, such as ant colonies and market economies. People often have...
详细信息
ISBN:
(纸本)9780897918329
StarLogo is programmable modeling environment designed to help nonexpert users (in particular, precollege students) model and explore decentralized systems, such as ant colonies and market economies. People often have difficulty understanding the workings of such systems. By using StarLogo, people can move beyond the 'centralized mindset' - that is, they begin to understand how patterns can arise through decentralized interactions, not from the dictates of a centralized authority.
Escape analysis is an abstract interpretation technique for statistically optimizing storage management devised by Park & Goldberg [30]. The main application of escape analysis is the optimization of storage manag...
详细信息
ISBN:
(纸本)9780897918534
Escape analysis is an abstract interpretation technique for statistically optimizing storage management devised by Park & Goldberg [30]. The main application of escape analysis is the optimization of storage management and data locality in garbage-collected languages such as ML or JAVA. We improve the previously known exponential complexity bound of Park & Goldberg: we show that first-order escape analysis (EA1) can be solved in almost linear time, and that second-order escape analysis (EA2) is DEXPTIME-hard. We exhibit a fast, equational, path-compression based abstract interpretation algorithm for EA1. We prove that it is sound and complete, and that its time complexity is O(n log2 n). We sketch an extension of the analysis to higher-order functions and imperative operations that is approximate. Finally we briefly present some experimental evidence that escape analysis may be useful in practice.
We propose a syntactic approach to performing fixed point computation on finite domains. Finding fixed points in finite domains for monotonic functions is an essential task when calculating abstract semantics of funct...
详细信息
ISBN:
(纸本)0897914813
We propose a syntactic approach to performing fixed point computation on finite domains. Finding fixed points in finite domains for monotonic functions is an essential task when calculating abstract semantics of functional programs. Previous methods for fixed point finding have been mainly based on semantic approaches which may be very inefficient even for simple programs. We outline the development of a syntactic approach, and show that the syntactic approach is sound and complete with respect to semantics. A few examples are provided to illustrate this syntactic approach.
Object-oriented analysis is the newest component of a proposed object-oriented software life cycle methodology. In this paper, we make comparisons between the standard data flow diagram (DFD) models and the newly intr...
详细信息
ISBN:
(纸本)0897914724
Object-oriented analysis is the newest component of a proposed object-oriented software life cycle methodology. In this paper, we make comparisons between the standard data flow diagram (DFD) models and the newly introduced object models within the context of an existing moderately complex (approx. 65,000 lines) software project. In particular, we compare the complexities of competing models for the project domain using some simple metrics.
This paper studies the problem of simplifying typings and the size-complexity of most general typings in typed programming languages with atomic subtyping. We define a notion of minimal typings relating all typings wh...
详细信息
ISBN:
(纸本)9780897918534
This paper studies the problem of simplifying typings and the size-complexity of most general typings in typed programming languages with atomic subtyping. We define a notion of minimal typings relating all typings which are equivalent with respect to instantiation. The notion of instance is that of Fuh and Mishra [13], which supports many interesting simplifications. We prove that every typable term has a unique minimal typing, which is the logically most succinct among all equivalent typings. We study completeness properties, with respect to our notion of minimality, of well-known simplification techniques. Drawing upon these results, we prove a tight exponential lower bound for the worst case dag-size of constraint sets as well as of types in most general typings. To the best of our knowledge, the best previously proven lower bound was linear.
We design a calculus where objects are created by instantiating classes, as well as mixins. Mixin-instantiated objects are "incomplete objects", that can be completed in object-based fashion. The combination...
详细信息
ISBN:
(纸本)9781581139648
We design a calculus where objects are created by instantiating classes, as well as mixins. Mixin-instantiated objects are "incomplete objects", that can be completed in object-based fashion. The combination of class-based features with object-based ones offers some flexible programming solutions. The fact that all objects are created from fully-typed constructs is a guarantee of controlled (therefore reasonably safe) behavior. Copyright 2005 ACM.
暂无评论