1000 resultados para Program Transformations
Resumo:
The relationship between abstract interpretation and partial deduction has received considerable attention and (partial) integrations have been proposed starting from both the partial deduction and abstract interpretation perspectives. In this work we present what we argüe is the first fully described generic algorithm for efñcient and precise integration of abstract interpretation and partial deduction. Taking as starting point state-of-the-art algorithms for context-sensitive, polyvariant abstract interpretation and (abstract) partial deduction, we present an algorithm which combines the best of both worlds. Key ingredients include the accurate success propagation inherent to abstract interpretation and the powerful program transformations achievable by partial deduction. In our algorithm, the calis which appear in the analysis graph are not analyzed w.r.t. the original definition of the procedure but w.r.t. specialized definitions of these procedures. Such specialized definitions are obtained by applying both unfolding and abstract executability. Our framework is parametric w.r.t. different control strategies and abstract domains. Different combinations of such parameters correspond to existing algorithms for program analysis and specialization. Simultaneously, our approach opens the door to the efñcient computation of strictly more precise results than those achievable by each of the individual techniques. The algorithm is now one of the key components of the CiaoPP analysis and specialization system.
Resumo:
Information generated by abstract interpreters has long been used to perform program specialization. Additionally, if the abstract interpreter generates a multivariant analysis, it is also possible to perform múltiple specialization. Information about valúes of variables is propagated by simulating program execution and performing fixpoint computations for recursive calis. In contrast, traditional partial evaluators (mainly) use unfolding for both propagating valúes of variables and transforming the program. It is known that abstract interpretation is a better technique for propagating success valúes than unfolding. However, the program transformations induced by unfolding may lead to important optimizations which are not directly achievable in the existing frameworks for múltiple specialization based on abstract interpretation. The aim of this work is to devise a specialization framework which integrates the better information propagation of abstract interpretation with the powerful program transformations performed by partial evaluation, and which can be implemented via small modifications to existing generic abstract interpreters. With this aim, we will relate top-down abstract interpretation with traditional concepts in partial evaluation and sketch how the sophisticated techniques developed for controlling partial evaluation can be adapted to the proposed specialization framework. We conclude that there can be both practical and conceptual advantages in the proposed integration of partial evaluation and abstract interpretation.
Resumo:
Dynamic scheduling increases the expressive power of logic programming languages, but also introduces some overhead. In this paper we present two classes of program transformations designed to reduce this additional overhead, while preserving the operational semantics of the original programs, modulo ordering of literals woken at the same time. The first class of transformations simplifies the delay conditions while the second class moves delayed literals later in the rule body. Application of the program transformations can be automated using information provided by compile-time analysis. We provide experimental results obtained from an implementation of the proposed techniques using the CIAO prototype compiler. Our results show that the techniques can lead to substantial performance improvement.
Resumo:
Esta tesis estudia la reducción plena (‘full reduction’ en inglés) en distintos cálculos lambda. 1 En esencia, la reducción plena consiste en evaluar los cuerpos de las funciones en los lenguajes de programación funcional con ligaduras. Se toma el cálculo lambda clásico (i.e., puro y sin tipos) como el sistema formal que modela el paradigma de programación funcional. La reducción plena es una técnica fundamental cuando se considera a los programas como datos, por ejemplo para la optimización de programas mediante evaluación parcial, o cuando algún atributo del programa se representa a su vez por un programa, como el tipo en los demostradores automáticos de teoremas actuales. Muchas semánticas operacionales que realizan reducción plena tienen naturaleza híbrida. Se introduce formalmente la noción de naturaleza híbrida, que constituye el hilo conductor de todo el trabajo. En el cálculo lambda la naturaleza híbrida se manifiesta como una ‘distinción de fase’ en el tratamiento de las abstracciones, ya sean consideradas desde fuera o desde dentro de si mismas. Esta distinción de fase conlleva una estructura en capas en la que una semántica híbrida depende de una o más semánticas subsidiarias. Desde el punto de vista de los lenguajes de programación, la tesis muestra como derivar, mediante técnicas de transformación de programas, implementaciones de semánticas operacionales que reducen plenamente a partir de sus especificaciones. Las técnicas de transformación de programas consisten en transformaciones sintácticas que preservan la equivalencia semántica de los programas. Se ajustan las técnicas de transformación de programas existentes para trabajar con implementaciones de semánticas híbridas. Además, se muestra el impacto que tiene la reducción plena en las implementaciones que utilizan entornos. Los entornos son un ingrediente fundamental en las implementaciones realistas de una máquina abstracta. Desde el punto de vista de los sistemas formales, la tesis desvela una teoría novedosa para el cálculo lambda con paso por valor (‘call-by-value lambda calculus’ en inglés) que es consistente con la reducción plena. Dicha teoría induce una noción de equivalencia observacional que distingue más puntos que las teorías existentes para dicho cálculo. Esta contribución ayuda a establecer una ‘teoría estándar’ en el cálculo lambda con paso por valor que es análoga a la ‘teoría estándar’ del cálculo lambda clásico propugnada por Barendregt. Se presentan resultados de teoría de la demostración, y se sugiere como abordar el estudio de teoría de modelos. ABSTRACT This thesis studies full reduction in lambda calculi. In a nutshell, full reduction consists in evaluating the body of the functions in a functional programming language with binders. The classical (i.e., pure untyped) lambda calculus is set as the formal system that models the functional paradigm. Full reduction is a prominent technique when programs are treated as data objects, for instance when performing optimisations by partial evaluation, or when some attribute of the program is represented by a program itself, like the type in modern proof assistants. A notable feature of many full-reducing operational semantics is its hybrid nature, which is introduced and which constitutes the guiding theme of the thesis. In the lambda calculus, the hybrid nature amounts to a ‘phase distinction’ in the treatment of abstractions when considered either from outside or from inside themselves. This distinction entails a layered structure in which a hybrid semantics depends on one or more subsidiary semantics. From a programming languages standpoint, the thesis shows how to derive implementations of full-reducing operational semantics from their specifications, by using program transformations techniques. The program transformation techniques are syntactical transformations which preserve the semantic equivalence of programs. The existing program transformation techniques are adjusted to work with implementations of hybrid semantics. The thesis also shows how full reduction impacts the implementations that use the environment technique. The environment technique is a key ingredient of real-world implementations of abstract machines which helps to circumvent the issue with binders. From a formal systems standpoint, the thesis discloses a novel consistent theory for the call-by-value variant of the lambda calculus which accounts for full reduction. This novel theory entails a notion of observational equivalence which distinguishes more points than other existing theories for the call-by-value lambda calculus. This contribution helps to establish a ‘standard theory’ in that calculus which constitutes the analogous of the ‘standard theory’ advocated by Barendregt in the classical lambda calculus. Some prooftheoretical results are presented, and insights on the model-theoretical study are given.
Resumo:
The paper presents a short review of some systems for program transformations performed on the basis of the internal intermediate representations of these programs. Many systems try to support several languages of representation of the source texts of programs and solve the task of their translation into the internal representation. This task is still a challenge as it is effort-consuming. To reduce the effort, different systems of translator construction, ready compilers with ready grammars of outside designers are used. Though this approach saves the effort, it has its drawbacks and constraints. The paper presents the general idea of using the mapping approach to solve the task within the framework of program transformations and overcome the disadvantages of the existing systems. The paper demonstrates a fragment of the ontology model of high-level languages mappings onto the single representation and gives the example of how the description of (a fragment) a particular mapping is represented in accordance with the ontology model.
Resumo:
Starting with an evaluator for a language, an abstract machine for the same language can be mechanically derived using successive program transformations. This has relevance to studying both the space and time properties of programs because these can be estimated by counting transitions of the abstract machine and measuring the size of the additional data structures needed, such as environments and stacks. In this article we use this process to derive a function that accurately counts the number of steps required to evaluate expressions in a simple language.
Resumo:
Thesis--University of Illinois.
Resumo:
Program compilation can be formally defined as a sequence of equivalence-preserving transformations, or refinements, from high-level language programs to assembler code, Recent models also incorporate timing properties, but the resulting formalisms are intimidatingly complex. Here we take advantage of a new, simple model of real-time refinement, based on predicate transformer semantics, to present a straightforward compilation formalism that incorporates real-time constraints. (C) 2002 Elsevier Science B.V. All rights reserved.
Resumo:
Résumé Métropolisation, morphologie urbaine et développement durable. Transformations urbaines et régulation de l'étalement : le cas de l'agglomération lausannoise. Cette thèse s'inscrit clans la perspective d'une analyse stratégique visant à un définir et à expliciter les liens entre connaissance, expertise et décision politique. L'hypothèse fondamentale qui oriente l'ensemble de ce travail est la suivante : le régime d'urbanisation qui s'est imposé au cours des trente dernières années correspond à une transformation du principe morphogénétique de développement spatial des agglomérations qui tend à alourdir leurs bilans écologiques et à péjorer la qualité du cadre de vie des citadins. Ces enjeux environnementaux liés aux changements urbains et singulièrement ceux de la forme urbaine constituent un thème de plus en plus important dans la recherche de solutions d'aménagement urbain dans une perspective de développement durable. Dans ce contexte, l'aménagement urbain devient un mode d'action et une composante de tout premier ordre des politiques publiques visant un développement durable à l'échelle locale et globale. Ces modalités de développement spatial des agglomérations émergent indiscutablement au coeur de la problématique environnementale. Or si le concept de développement durable nous livre une nouvelle de de lecture des territoires et de ses transformations, en prônant le modèle de la ville compacte et son corollaire la densification, la traduction à donner à ce principe stratégique reste controversée, notamment sous l'angle de l'aménagement du territoire et des stratégies de développement urbain permettant une mise en oeuvre adéquate des solutions proposées. Nous avons ainsi tenté dans ce travail de répondre à un certain nombre de questions : quelle validité accorder au modèle de la ville compacte ? La densification est-elle une réponse adéquate ? Si oui, sous quelles modalités ? Quelles sont, en termes de stratégies d'aménagement, les alternatives durables au modèle de la ville étalée ? Faut-il vraiment densifier ou simplement maîtriser la dispersion ? Notre objectif principal étant in fine de déterminer les orientations et contenus urbanistiques de politiques publiques visant à réguler l'étalement urbain, de valider la faisabilité de ces principes et à définir les conditions de leur mise en place dans le cas d'une agglomération. Pour cela, et après avoir choisi l'agglomération lausannoise comme terrain d'expérimentation, trois approches complémentaires se sont révélées indispensables dans ce travail 1. une approche théorique visant à définir un cadre conceptuel interdisciplinaire d'analyse du phénomène urbain dans ses rapports à la problématique du développement durable liant régime d'urbanisation - forme urbaine - développement durable ; 2. une approche méthodologique proposant des outils d'analyse simples et efficaces de description des nouvelles morphologies urbaines pour une meilleure gestion de l'environnement urbain et de la pratique de l'aménagement urbain ; 3. une approche pragmatique visant à approfondir la réflexion sur la ville étalée en passant d'une approche descriptive des conséquences du nouveau régime d'urbanisation à une approche opérationnelle, visant à identifier les lignes d'actions possibles dans une perspective de développement durable. Cette démarche d'analyse nous a conduits à trois résultats majeurs, nous permettant de définir une stratégie de lutte contre l'étalement. Premièrement, si la densification est acceptée comme un objectif stratégique de l'aménagement urbain, le modèle de la ville dense ne peut être appliqué saris la prise en considération d'autres objectifs d'aménagement. Il ne suffit pas de densifier pour réduire l'empreinte écologique de la ville et améliorer la qualité de vie des citadins. La recherche d'une forme urbaine plus durable est tributaire d'une multiplicité de facteurs et d'effets de synergie et la maîtrise des effets négatifs de l'étalement urbain passe par la mise en oeuvre de politiques urbaines intégrées et concertées, comme par exemple prôner la densification qualifiée comme résultante d'un processus finalisé, intégrer et valoriser les transports collectifs et encore plus la métrique pédestre avec l'aménagement urbain, intégrer systématiquement la diversité à travers les dimensions physique et sociale du territoire. Deuxièmement, l'avenir de ces territoires étalés n'est pas figé. Notre enquête de terrain a montré une évolution des modes d'habitat liée aux modes de vie, à l'organisation du travail, à la mobilité, qui font que l'on peut penser à un retour d'une partie de la population dans les villes centres (fin de la toute puissance du modèle de la maison individuelle). Ainsi, le diagnostic et la recherche de solutions d'aménagement efficaces et viables ne peuvent être dissociés des demandes des habitants et des comportements des acteurs de la production du cadre bâti. Dans cette perspective, tout programme d'urbanisme doit nécessairement s'appuyer sur la connaissance des aspirations de la population. Troisièmement, la réussite de la mise en oeuvre d'une politique globale de maîtrise des effets négatifs de l'étalement urbain est fortement conditionnée par l'adaptation de l'offre immobilière à la demande de nouveaux modèles d'habitat répondant à la fois à la nécessité d'une maîtrise des coûts de l'urbanisation (économiques, sociaux, environnementaux), ainsi qu'aux aspirations émergentes des ménages. Ces résultats nous ont permis de définir les orientations d'une stratégie de lutte contre l'étalement, dont nous avons testé la faisabilité ainsi que les conditions de mise en oeuvre sur le territoire de l'agglomération lausannoise. Abstract This dissertation participates in the perspective of a strategic analysis aiming at specifying the links between knowledge, expertise and political decision, The fundamental hypothesis directing this study assumes that the urban dynamics that has characterized the past thirty years signifies a trans-formation of the morphogenetic principle of agglomerations' spatial development that results in a worsening of their ecological balance and of city dwellers' quality of life. The environmental implications linked to urban changes and particularly to changes in urban form constitute an ever greater share of research into sustainable urban planning solutions. In this context, urban planning becomes a mode of action and an essential component of public policies aiming at local and global sustainable development. These patterns of spatial development indisputably emerge at the heart of environmental issues. If the concept of sustainable development provides us with new understanding into territories and their transformations, by arguing in favor of densification, its concretization remains at issue, especially in terms of urban planning and of urban development strategies allowing the appropriate implementations of the solutions offered. Thus, this study tries to answer a certain number of questions: what validity should be granted to the model of the dense city? Is densification an adequate answer? If so, under what terms? What are the sustainable alternatives to urban sprawl in terms of planning strategies? Should densification really be pursued or should we simply try to master urban sprawl? Our main objective being in fine to determine the directions and urban con-tents of public policies aiming at regulating urban sprawl, to validate the feasibility of these principles and to define the conditions of their implementation in the case of one agglomeration. Once the Lausanne agglomeration had been chosen as experimentation field, three complementary approaches proved to be essential to this study: 1. a theoretical approach aiming at definying an interdisciplinary conceptual framework of the ur-ban phenomenon in its relation to sustainable development linking urban dynamics - urban form - sustainable development ; 2. a methodological approach proposing simple and effective tools for analyzing and describing new urban morphologies for a better management of the urban environment and of urban planning practices 3. a pragmatic approach aiming at deepening reflection on urban sprawl by switching from a descriptive approach of the consequences of the new urban dynamics to an operational approach, aiming at identifying possible avenues of action respecting the principles of sustainable development. This analysis approach provided us with three major results, allowing us to define a strategy to cur-tail urban sprawl. First, if densification is accepted as a strategic objective of urban planning, the model of the dense city can not be applied without taking into consideration other urban planning objectives. Densification does not suffice to reduce the ecological impact of the city and improve the quality of life of its dwellers. The search for a more sustainable urban form depends on a multitude of factors and effects of synergy. Reducing the negative effects of urban sprawl requires the implementation of integrated and concerted urban policies, like for example encouraging densification qualified as resulting from a finalized process, integrating and developing collective forms of transportation and even more so the pedestrian metric with urban planning, integrating diversity on a systematic basis through the physical and social dimensions of the territory. Second, the future of such sprawling territories is not fixed. Our research on the ground revea-led an evolution in the modes of habitat related to ways of life, work organization and mobility that suggest the possibility of the return of a part of the population to the center of cities (end of the rule of the model of the individual home). Thus, the diagnosis and the search for effective and sustainable solutions can not be conceived of independently of the needs of the inhabitants and of the behavior of the actors behind the production of the built territory. In this perspective, any urban program must necessarily be based upon the knowledge of the population's wishes. Third, the successful implementation of a global policy of control of urban sprawl's negative effects is highly influenced by the adaptation of property offer to the demand of new habitat models satisfying both the necessity of urbanization cost controls (economical, social, environ-mental) and people's emerging aspirations. These results allowed us to define a strategy to cur-tail urban sprawl. Its feasibility and conditions of implementation were tested on the territory of the Lausanne agglomeration.
Resumo:
Lithobiostratigraphic data indicate that the double reflectors on the seismic profile through Ocean Drilling Program (ODP) Site 1148 represent two unconformities that coincide, respectively, with the lower/upper Oligocene boundary at ~488 mcd, and Oligocene-Miocene boundary at 460 mcd. Two other unconformities, at ~478 and 472 mcd, respectively, were also identified within the upper Oligocene section. Together they erased a sediment record of about 3 Ma from this locality in a period of very active seafloor spreading. The existence of 32.8 Ma marine sediment at the terminated depth (850 mcd) indicates that the initial breakup of the South China Sea (SCS) was probably during 34-33 Ma, close to the Eocene-Oligocene boundary. High sedimentation rates of 60-115 m/my from the much expanded, N350 m lower Oligocene section resulted from rifting and rapid subsidence between 33 and 29 Ma. The mid-Oligocene unconformity at ~28.5 Ma, which also occurred in many parts of the Indo-West Pacific region, was probably related to a significant uplift of the Himalayan-Tibetan Plateau to the west and the initial collision between Indonesia and Australia in the south. A narrowed Indonesian seaway may have accounted for the late Oligocene warming and chalk deposition in the northern South China Sea including the Site 1148 locality. The unconformities and slumps near the Oligocene-Miocene boundary indicate a very unstable tectonic regime, probably corresponding to changes in the rotation of different land blocks and the seafloor spreading ridge from nearly E-W to NE-SW, as recognized earlier at magnetic Anomaly 7. This 25 Ma event also saw the first New Guinea terrane docking at the northern Australian craton. The low sedimentation rate of ~15 m/my in the early to middle Miocene may correspond to another period of rapid seafloor spreading and rapid widespread subsidence that effectively caused sediment source areas to retreat with a rapidly rising sea level. The isostatic nature of these late Oligocene unconformities and slumps with several major collision-uplift events indicate that the rapid changes in the early evolutionary history of the South China Sea were mainly responding to regional tectonic reconfiguration including the uplift-driven southeast extrusion of the Indochina subcontinent.
Resumo:
Knowing the size of the terms to which program variables are bound at run-time in logic programs is required in a class of applications related to program optimization such as, for example, recursion elimination and granularity analysis. Such size is difficult to even approximate at compile time and is thus generally computed at run-time by using (possibly predefined) predicates which traverse the terms involved. We propose a technique based on program transformation which has the potential of performing this computation much more efficiently. The technique is based on finding program procedures which are called before those in which knowledge regarding term sizes is needed and which traverse the terms whose size is to be determined, and transforming such procedures so that they compute term sizes "on the fly". We present a systematic way of determining whether a given program can be transformed in order to compute a given term size at a given program point without additional term traversal. Also, if several such transformations are possible our approach allows finding minimal transformations under certain criteria. We also discuss the advantages and present some applications of our technique.
Resumo:
Knowing the size of the terms to which program variables are bound at run-time in logic programs is required in a class of applications related to program optimization such as, for example, granularity analysis and selection among different algorithms or control rules whose performance may be dependent on such size. Such size is difficult to even approximate at compile time and is thus generally computed at run-time by using (possibly predefined) predicates which traverse the terms involved. We propose a technique based on program transformation which has the potential of performing this computation much more efficiently. The technique is based on finding program procedures which are called before those in which knowledge regarding term sizes is needed and which traverse the terms whose size is to be determined, and transforming such procedures so that they compute term sizes "on the fly". We present a systematic way of determining whether a given program can be transformed in order to compute a given term size at a given program point without additional term traversal. Also, if several such transformations are possible our approach allows finding minimal transformations under certain criteria. We also discuss the advantages and applications of our technique and present some performance results.
Resumo:
Knowing the size of the terms to which program variables are bound at run-time in logic programs is required in a class of applications related to program optimization such as, for example, recursion elimination and granularity analysis. Such size is difficult to even approximate at compile time and is thus generally computed at run-time by using (possibly predefined) predicates which traverse the terms involved. We propose a technique based on program transformation which has the potential of performing this computation much more efficiently. The technique is based on finding program procedures which are called before those in which knowledge regarding term sizes is needed and which traverse the terms whose size is to be determined, and transforming such procedures so that they compute term sizes "on the fly". We present a systematic way of determining whether a given program can be transformed in order to compute a given term size at a given program point without additional term traversal. Also, if several such transformations are possible our approach allows finding minimal transformations under certain criteria. We also discuss the advantages and present some applications of our technique.
Resumo:
"May 1977."
Resumo:
The article describes the structure of an ontology model for Optimization of a sequential program. The components of an intellectual modeling system for program optimization are described. The functions of the intellectual modeling system are defined.