Dynamic typing is a program analysis targeted at removing runtime tagging and untagging operations from programs written in dynamically typed languages. This paper compares dynamic typing with a subtyping system based...
详细信息
ISBN:
(纸本)9780897917193
Dynamic typing is a program analysis targeted at removing runtime tagging and untagging operations from programs written in dynamically typed languages. This paper compares dynamic typing with a subtyping system based on set constraints. The purpose is both to make precise the relationship between two superficially unrelated type systems and to illustrate how the advantages of dynamic typing and subtype inference can be combined. The central result is a theorem showing that a typing discipline at least as powerful as dynamic typing can be expressed using set constraints.
In this paper, we propose an integration of an extension of Bailin's object-oriented requirements specification (OOS) with a formal notation (Z), called OOSZ. The OOS is used to guide the derivation of Z specifica...
详细信息
In this paper, we propose an integration of an extension of Bailin's object-oriented requirements specification (OOS) with a formal notation (Z), called OOSZ. The OOS is used to guide the derivation of Z specifications. In OOSZ, a function process is converted into an operation schema. An entity process is manifested through a state schema, an instance creation operation schema and an abstract operation schema. Correctness conjectures are generated for verifying the consistency of intralevel and interlevel specifications. These are illustrated using the problem domain of Auto Banking Systems. The bringing together of diagrammatical and text elements of OOS specifications in Z notations offers three major benefits. First, the relationship between ERD and EDFD is tightly coupled compared with Yourdon's SA approach. Second, OOS specifications can be seen both as a structuring mechanism that helps in deriving Z specifications, and as a preliminary that assists in ascertaining the clients requirements. Third, Z specifications make it easier to identify omissions or errors.
Grammar-based programs analyses are static analysis techniques that have traditionally been seen as quite different from abstract-interpretation-based analyses, due to their apparent non-iterative nature. There are de...
详细信息
ISBN:
(纸本)9780897917193
Grammar-based programs analyses are static analysis techniques that have traditionally been seen as quite different from abstract-interpretation-based analyses, due to their apparent non-iterative nature. There are decidable kinds of analysis that cannot be computed using abstract interpretation (even with widening and narrowing). An example of this is the set-based analysis considered in this work. It is shown that grammar and set-constraint-based program analyses are similar abstract interpretations with iterative fixpoint computation using either a widening or a finitary grammar/set-constraints transformer or even a finite domain for each particular program.
A new method for polymorphic type interference for the dynamically typed language Scheme is described. The method which infers both types and explicit run-time type operations (coercions) for a given program can be us...
详细信息
A new method for polymorphic type interference for the dynamically typed language Scheme is described. The method which infers both types and explicit run-time type operations (coercions) for a given program can be used to statically debug Scheme programs and to give a high-level translation to ML, in essence providing an 'embedding' of Scheme into ML. Finally, an introduction to the type theoretic framework of polymorphic dynamic typing is given, the phases of the type interference process are described, and some examples of the resulting Scheme-to-ML translator are presented.
Program fusion is the process whereby separate pieces of code are fused into a single piece, typically transforming a multi-pass algorithm into a single pass. Recent work has made it clear that the process is especial...
详细信息
Program fusion is the process whereby separate pieces of code are fused into a single piece, typically transforming a multi-pass algorithm into a single pass. Recent work has made it clear that the process is especially successful if the loops or recursions are expressed using catamorphisms (***) and constructor-abstraction (e.g. build). In this paper we show how to transform recursive programs into this form automatically, thus enabling the fusion transformation to be applied more easily than before.
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.
Numeric types can be given polymorphic dimension parameters, in order to avoid dimension errors and unit errors. The most general dimensions can be inferred automatically. It has been observed that polymorphic recursi...
详细信息
ISBN:
(纸本)9780897917193
Numeric types can be given polymorphic dimension parameters, in order to avoid dimension errors and unit errors. The most general dimensions can be inferred automatically. It has been observed that polymorphic recursion is more important for the dimensions that for the proper types. We show that, under polymorphic recursion, type inference amounts to syntactic semi-unification of proper types, followed by equational semi-unification of dimensions. Syntactic semi-unification is unfortunately undecidable, although there are procedures that work well in practice, and proper types given by the programmer can be checked. However, the dimensions form a vector space (provided that their exponents are rational numbers). We give a polynomial-time algorithm that decides if a semi-unification problem in a vector space can be solved and, if so, returns a most general semi-unifier.
A new approach to formation and organization of the anticipatory data sampling (A-process) in fast local processor memory is analyzed in development of mechanisms directed to achievement of the limitary processors cap...
详细信息
A new approach to formation and organization of the anticipatory data sampling (A-process) in fast local processor memory is analyzed in development of mechanisms directed to achievement of the limitary processors capacity. The approach is based on the principle of A-process conveyerization ″from above″, analysis results of programs on the standard languages of high-level as well as the principle of A-process ″intellectualization″. The A-processes formed on the base of A-analysis provide essential reduction (tenths of percents) of data processing time in the central processor.
Several mistakes in Transparency Lemma and Soundness Theorem proved by Bijlsma (1989) were pointed out by proposing some counter examples. Furthermore, the authors reproved the above results using intuitive methods wh...
详细信息
Several mistakes in Transparency Lemma and Soundness Theorem proved by Bijlsma (1989) were pointed out by proposing some counter examples. Furthermore, the authors reproved the above results using intuitive methods which are easier to be understood.
This paper presents the main concepts of the mathematical theory PEI for parallel programming and emphasizes its derivation power. The mathematical basis of this theory leads to a nice implementation in CENTAUR of an ...
详细信息
This paper presents the main concepts of the mathematical theory PEI for parallel programming and emphasizes its derivation power. The mathematical basis of this theory leads to a nice implementation in CENTAUR of an environment whose purpose is to transform parallel programs. It is illustrated by two similar examples: the convolution sum and the Dirichlet product. The second one uses non-affine dependencies that can be easily taken into account using PEI.
暂无评论