Modular extensions for modular (Logic) languages

We address the problem of developing mechanisms for easily implementing modular extensions to modular (logic) languages. By(language) extensions we refer to different groups of syntactic definitions and translation rules that extend a language. Our use of the concept of modularity in this context is twofold. We would like these extensions to be modular, in the sense above, i.e., we should be able to develop different extensions mostly separately. At the same time, the sources and targets for the extensions are modular languages, i.e., such extensions may take as input sepárate pieces of code and also produce sepárate pieces of code. Dealing with this double requirement involves interesting challenges to ensure that modularity is not broken: first, combinations of extensions (as if they were a single extensión) must be given a precise meaning. Also, the sepárate translation of múltiple sources (as if they were a single source) must be feasible. We present a detailed description of a code expansion-based framework that proposes novel solutions for these problems. We argüe that the approach, while implemented for Ciao, can be adapted for other Prolog-based systems and languages.

Abstract multiple specialization and its application to program parallelization.

Program specialization optimizes programs for known valúes of the input. It is often the case that the set of possible input valúes is unknown, or this set is infinite. However, a form of specialization can still be performed in such cases by means of abstract interpretation, specialization then being with respect to abstract valúes (substitutions), rather than concrete ones. We study the múltiple specialization of logic programs based on abstract interpretation. This involves in principie, and based on information from global analysis, generating several versions of a program predicate for different uses of such predicate, optimizing these versions, and, finally, producing a new, "multiply specialized" program. While múltiple specialization has received theoretical attention, little previous evidence exists on its practicality. In this paper we report on the incorporation of múltiple specialization in a parallelizing compiler and quantify its effects. A novel approach to the design and implementation of the specialization system is proposed. The resulting implementation techniques result in identical specializations to those of the best previously proposed techniques but require little or no modification of some existing abstract interpreters. Our results show that, using the proposed techniques, the resulting "abstract múltiple specialization" is indeed a relevant technique in practice. In particular, in the parallelizing compiler application, a good number of run-time tests are eliminated and invariants extracted automatically from loops, resulting generally in lower overheads and in several cases in increased speedups.

A static heap analysis for shape and connectivity: Unified memory analysis: The base framework

Modeling the evolution of the state of program memory during program execution is critical to many parallehzation techniques. Current memory analysis techniques either provide very accurate information but run prohibitively slowly or produce very conservative results. An approach based on abstract interpretation is presented for analyzing programs at compile time, which can accurately determine many important program properties such as aliasing, logical data structures and shape. These properties are known to be critical for transforming a single threaded program into a versión that can be run on múltiple execution units in parallel. The analysis is shown to be of polynomial complexity in the size of the memory heap. Experimental results for benchmarks in the Jolden suite are given. These results show that in practice the analysis method is efflcient and is capable of accurately determining shape information in programs that créate and manipúlate complex data structures.

Removing superfluous versions in polyvariant specialization of prolog programs.

Polyvariant specialization allows generating múltiple versions of a procedure, which can then be separately optimized for different uses. Since allowing a high degree of polyvariance often results in more optimized code, polyvariant specializers, such as most partial evaluators, can genérate a large number of versions. This can produce unnecessarily large residual programs. Also, large programs can be slower due to cache miss effects. A possible solution to this problem is to introduce a minimization step which identifies sets of equivalent versions, and replace all occurrences of such versions by a single one. In this work we present a unifying view of the problem of superfluous polyvariance. It includes both partial deduction and abstract múltiple specialization. As regards partial deduction, we extend existing approaches in several ways. First, previous work has dealt with puré logic programs and a very limited class of builtins. Herein we propose an extensión to traditional characteristic trees which can be used in the presence of calis to external predicates. This includes all builtins, librarles, other user modules, etc. Second, we propose the possibility of collapsing versions which are not strictly equivalent. This allows trading time for space and can be useful in the context of embedded and pervasive systems. This is done by residualizing certain computations for external predicates which would otherwise be performed at specialization time. Third, we provide an experimental evaluation of the potential gains achievable using minimization which leads to interesting conclusions.

Abstract specialization and its application to program parallelization

Program specialization optimizes programs for known valúes of the input. It is often the case that the set of possible input valúes is unknown, or this set is infinite. However, a form of specialization can still be performed in such cases by means of abstract interpretation, specialization then being with respect to abstract valúes (substitutions), rather than concrete ones. This paper reports on the application of abstract múltiple specialization to automatic program parallelization in the &-Prolog compiler. Abstract executability, the main concept underlying abstract specialization, is formalized, the design of the specialization system presented, and a non-trivial example of specialization in automatic parallelization is given.

Implementation of multiple specialization in logic programs

We study the múltiple specialization of logic programs based on abstract interpretation. This involves in general generating several versions of a program predícate for different uses of such predícate, making use of information obtained from global analysis performed by an abstract interpreter, and finally producing a new, "multiply specialized" program. While the topic of múltiple specialization of logic programs has received considerable theoretical attention, it has never been actually incorporated in a compiler and its effects quantified. We perform such a study in the context of a parallelizing compiler and show that it is indeed a relevant technique in practice. Also, we propose an implementation technique which has the same power as the strongest of the previously proposed techniques but requires little or no modification of an existing abstract interpreter.

Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited

This report addresses speculative parallelism (the assignment of spare processing resources to tasks which are not known to be strictly required for the successful completion of a computation) at the user and application level. At this level, the execution of a program is seen as a (dynamic) tree —a graph, in general. A solution for a problem is a traversal of this graph from the initial state to a node known to be the answer. Speculative parallelism then represents the assignment of resources to múltiple branches of this graph even if they are not positively known to be on the path to a solution. In highly non-deterministic programs the branching factor can be very high and a naive assignment will very soon use up all the resources. This report presents work assignment strategies other than the usual depth-first and breadth-first. Instead, best-first strategies are used. Since their definition is application-dependent, the application language contains primitives that allow the user (or application programmer) to a) indícate when intelligent OR-parallelism should be used; b) provide the functions that define "best," and c) indícate when to use them. An abstract architecture enables those primitives to perform the search in a "speculative" way, using several processors, synchronizing them, killing the siblings of the path leading to the answer, etc. The user is freed from worrying about these interactions. Several search strategies are proposed and their implementation issues are addressed. "Armageddon," a global pruning method, is introduced, together with both a software and a hardware implementation for it. The concepts exposed are applicable to áreas of Artificial Intelligence such as extensive expert systems, planning, game playing, and in general to large search problems. The proposed strategies, although showing promise, have not been evaluated by simulation or experimentation.

Abstract Interpretation-based verification/certification in the ciaoPP system

CiaoPP is the abstract interpretation-based preprocessor of the Ciao multi-paradigm (Constraint) Logic Programming system. It uses modular, incremental abstract interpretation as a fundamental tool to obtain information about programs. In CiaoPP, the semantic approximations thus produced have been applied to perform high- and low-level optimizations during program compilation, including transformations such as múltiple abstract specialization, parallelization, partial evaluation, resource usage control, and program verification. More recently, novel and promising applications of such semantic approximations are being applied in the more general context of program development such as program verification. In this work, we describe our extensión of the system to incorpórate Abstraction-Carrying Code (ACC), a novel approach to mobile code safety. ACC follows the standard strategy of associating safety certificates to programs, originally proposed in Proof Carrying- Code. A distinguishing feature of ACC is that we use an abstraction (or abstract model) of the program computed by standard static analyzers as a certifícate. The validity of the abstraction on the consumer side is checked in a single-pass by a very efficient and specialized abstractinterpreter. We have implemented and benchmarked ACC within CiaoPP. The experimental results show that the checking phase is indeed faster than the proof generation phase, and that the sizes of certificates are reasonable. Moreover, the preprocessor is based on compile-time (and run-time) tools for the certification of CLP programs with resource consumption assurances.

Program development using abstract interpretation (and the ciao system preprocessor)

The technique of Abstract Interpretation has allowed the development of very sophisticated global program analyses which are at the same time provably correct and practical. We present in a tutorial fashion a novel program development framework which uses abstract interpretation as a fundamental tool. The framework uses modular, incremental abstract interpretation to obtain information about the program. This information is used to validate programs, to detect bugs with respect to partial specifications written using assertions (in the program itself and/or in system librarles), to genérate and simplify run-time tests, and to perform high-level program transformations such as múltiple abstract specialization, parallelization, and resource usage control, all in a provably correct way. In the case of validation and debugging, the assertions can refer to a variety of program points such as procedure entry, procedure exit, points within procedures, or global computations. The system can reason with much richer information than, for example, traditional types. This includes data structure shape (including pointer sharing), bounds on data structure sizes, and other operational variable instantiation properties, as well as procedure-level properties such as determinacy, termination, non-failure, and bounds on resource consumption (time or space cost). CiaoPP, the preprocessor of the Ciao multi-paradigm programming system, which implements the described functionality, will be used to illustrate the fundamental ideas.

Program analysis, debugging and optimization using the ciao system preprocessor

We present a tutorial overview of Ciaopp, the Ciao system preprocessor. Ciao is a public-domain, next-generation logic programming system, which subsumes ISO-Prolog and is specifically designed to a) be highly extensible via librarles and b) support modular program analysis, debugging, and optimization. The latter tasks are performed in an integrated fashion by Ciaopp. Ciaopp uses modular, incremental abstract interpretation to infer properties of program predicates and literals, including types, variable instantiation properties (including modes), non-failure, determinacy, bounds on computational cost, bounds on sizes of terms in the program, etc. Using such analysis information, Ciaopp can find errors at compile-time in programs and/or perform partial verification. Ciaopp checks how programs cali system librarles and also any assertions present in the program or in other modules used by the program. These assertions are also used to genérate documentation automatically. Ciaopp also uses analysis information to perform program transformations and optimizations such as múltiple abstract specialization, parallelization (including granularity control), and optimization of run-time tests for properties which cannot be checked completely at compile-time. We illustrate "hands-on" the use of Ciaopp in all these tasks. By design, Ciaopp is a generic tool, which can be easily tailored to perform these and other tasks for different LP and CLP dialects.

Estimating the computational cost of logic programs

Information about the computational cost of programs is potentially useful for a variety of purposes, including selecting among different algorithms, guiding program transformations, in granularity control and mapping decisions in parallelizing compilers, and query optimization in deductive databases. Cost analysis of logic programs is complicated by nondeterminism: on the one hand, procedures can return múltiple Solutions, making it necessary to estímate the number of solutions in order to give nontrivial upper bound cost estimates; on the other hand, the possibility of failure has to be taken into account while estimating lower bounds. Here we discuss techniques to address these problems to some extent.

An integration of partial evaluation in a generic abstract interpretation framework

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.

Valtra Versy y Direct

Los nuevos modelos Valtra, en sus versiones Versu y Direct, se han refinado las características tradicionales ofrecidas por Valtra añadiéndose otras muchas. De su “diseño tradicional” se destaca la facilidad de manejo en posición invertida utilizando el sistema de conducción reversible Twin-Trac. De lo "nuevo" se destacan sus nuevas transmisiones: transmisión variable continua (CVT), y transmisión múltiple escalonada con cambio bajo carga (Powershift).

El recinto ferial de la Casa de Campo de Madrid (1950-75)

El tema objeto de investigación “El recinto ferial de la Casa de Campo de Madrid (1950-75)” se trata desde una perspectiva que alterna la visión general y la visión pormenorizada. Profundizamos en la comprensión de las relaciones del recinto con el resto de la ciudad, desde la originalidad y singularidad de su trazado,la descripción y el análisis con distinto grado de detalle de sus arquitecturas, a partir, de la investigación documental, bibliográfica y la restitución gráfica realizada. Procuramos situar los pabellones en el contexto de las arquitecturas del periodo estudiado, indicando, en el caso del recinto original y los pabellones proyectados por el arquitecto Francisco Cabrero, posibles referencias a la tradición vernácula y clásica, los invariantes de la arquitectura española, sus maestros, la visión contemporánea de la arquitectura moderna e interpretación personal, recogida en sus cuatro libros de arquitectura. Otro campo de estudio, el resto de los pabellones construidos en virtud de las necesidades de los organismos que concurrían a la feria, constituyeron, dependiendo de sus distintos autores, un conjunto heterogéneo y diverso de planteamientos estilísticos, concepciones funcionales, espaciales y de calidad arquitectónica. De la comparación se extraen las oportunas reflexiones. La feria supone una alteración de las preexistencias del lugar, influyendo decisivamente en la configuración y evolución del ámbito urbano, condicionándolo, también hoy en día. Examinaremos la repercusión del trazado, la topografía, la vegetación y las construcciones. El carácter actual de cuña dotacional en el entorno del río Manzanares y la repercusión en la estructura del recinto de su división en dos piezas de arquitecturas tan distintas, como la parte antigua y la parte nueva. Partiremos de una restitución gráfica y cronológica, con distinto grado de detalle, del conjunto y los pabellones seleccionados. Otras reflexiones se centraran en el papel del comisario y los arquitectos directores. Desde los condicionantes del encargo inicial, la ampliación del recinto y la gestión de la evolución de la feria en base a los requerimientos agrícolas,folklóricos, comerciales, industriales y turísticos. Una arquitectura que nace de capacidad de improvisar, la flexibilidad, la habilidad y el provecho de cada situación particular. La concreción en unos 40 pabellones y stands (una tercera parte de los que se construyeron), supone una elección en base a criterios de calidad y oportunidad. Son hitos o ejemplos de las distintas corrientes que clasificamos en populares y modernos, casi, como una conclusión preestablecida. El trabajo se orienta hacia las edificaciones modernas ya sea por su logro en la asimilación del ideal, su grado de experimentación e innovación técnica o su interés en la configuración de sus espacios expositivos. Se conservan más y mejor los pabellones populares, lo que nos obliga a la puesta en valor de los modernos, sin menospreciar el interés de los populares, que deberán estudiarse con mayor detalle en trabajos posteriores, a partir, del abundante material recopilado. El objetivo fundamental del trabajo ha sido conocer en profundidad la arquitectura de los pabellones representativos de cada periodo, intentando comprender y restituir el proceso proyectual desde una visión múltiple que comprenda las disciplinas que confluyen en el proyecto arquitectónico. La tesis ofrece la restitución escrita y dibujada del recinto y sus arquitecturas, además,de la interpretación y valoración del autor. La visión contemporánea de Alejandro de la Sota con su crítica arquitectónica de la primera feria, los invariantes expuestos por Fernando Chueca o las sesiones de crítica celebradas en la Revista Nacional, indican el camino que siguieron los autores de los pabellones de la feria y permiten profundizar en el diagnóstico de las ideas del momento, también, a partir de algunas entrevistas realizadas. Se estudian además las relaciones entre el estrecho círculo de autores, las nuevas tendencias y la influencia otros artistas plásticos. Finalmente, la documentación y análisis del material audiovisual, los noticieros, revistas y boletines de la Feria del Campo, permiten extraer conclusiones sobre la originalidad del trazado del recinto y los pabellones, su utilización, así como, el funcionamiento y aceptación social de la feria, desde la perspectiva de la apertura y evolución política y cultural de la transición hacia la democracia. La abundante documentación administrativa localizada admite concluir sobre la veracidad de las circunstancias que influyeron en la concepción y desarrollo del recinto y sus edificios, contrastando el testimonio de sus protagonistas a partir de la recreación propuesta.

La evolución del paisaje fluvial en la confluencia de los ríos Tajo y Jarama

La tesis doctoral que se presenta realiza un análisis de la evolución del paisaje fluvial de las riberas de los ríos Tajo y Jarama en el entorno de Aranjuez desde una perspectiva múltiple. Contempla y conjuga aspectos naturales, tales como los hidrológicos, geomorfológicos y ecológicos; también culturales, como la regulación hidrológica y la gestión del agua, las intervenciones en cauce y márgenes, la evolución de la propiedad y los cambios de usos del suelo, fundamentalmente. Este análisis ha permitido identificar el sistema de factores, dinámico y complejo, que ha creado este paisaje, así como las interrelaciones, conexiones, condicionantes y dependencias de los descriptores paisajísticos considerados. Por ejemplo, se han estudiado las relaciones cruzadas observadas entre dinámica fluvial-propiedad de la tierra-estado de conservación, cuestiones que hasta la fecha no habían sido tratadas, evaluadas o cuantificadas en otros trabajos dedicados a esta zona. La investigación se ha organizado en tres fases fundamentales que han dado lugar a los capítulos centrales del documento (capítulos 2, 3 y 4). En primer lugar, se ha realizado una caracterización de los factores, naturales y culturales, que organizan el paisaje de este territorio eminentemente fluvial (geomorfología, factores climáticos e hidrológicos, vegetación, propiedad de la tierra y elementos culturales de significación paisajística). A continuación, se ha realizado el estudio de la evolución del paisaje fluvial mediante el análisis de diversos elementos, previamente identificados y caracterizados. Para ello se han procesado imágenes aéreas correspondientes a cinco series temporales así como varios planos antiguos, obteniendo una amplia base de datos que se ha analizado estadísticamente. Finalmente, se han contrastado los resultados parciales obtenidos en los capítulos anteriores, lo que ha permitido identificar relaciones causales entre los factores que organizan el paisaje y la evolución de los elementos que lo constituyen. También, interconexiones entre factores o entre elementos. Este método de trabajo ha resultado muy útil para la comprensión del funcionamiento y evolución de un sistema complejo, como el paisaje de la vega de Aranjuez, un territorio con profundas y antiguas intervenciones culturales donde lo natural, en cualquier caso, siempre subyace. Es posible que la principal aportación de este trabajo, también su diferencia más destacada respecto a otros estudios de paisaje, haya sido mostrar una visión completa y exhaustiva de todos los factores que han intervenido en la conformación y evolución del paisaje fluvial, destacando las relaciones que se establecen entre ellos. Esta manera de proceder puede tener una interesante faceta aplicada, de tal manera que resulta un instrumento muy útil para el diseño de planes de gestión de este territorio fluvial. No en vano, una parte sustancial de la vega del Tajo-Jarama en Aranjuez es un Lugar de Importancia Comunitaria (LIC) y su posterior e ineludible declaración como Zona de Especial Conservación (ZEC) de la Red Natura 2000, de acuerdo con lo establecido en la Directiva 92/43/CE, exige la elaboración de un Plan de Gestión que, en gran medida, podría nutrirse de lo presentado, analizado e interpretado en este trabajo. En este sentido, conviene señalar la conciencia ya asumida de considerar, por su carácter integrador de la realidad territorial, el paisaje como elemento clave para la gestión adecuada de la naturaleza y el territorio. Por otra parte, se considera que los resultados de esta Tesis Doctoral permitirían plantear medidas para la puesta en valor de un paisaje sobresaliente, cuyos límites sobrepasan con creces los que en la actualidad conforman el Paisaje Cultural declarado por la UNESCO. En suma, el análisis de este espacio fluvial realizado con la profundidad y amplitud que permite el método de trabajo seguido puede utilizarse para el diseño de estrategias que dirijan la evolución de este territorio en una línea que garantice su conservación global en términos paisajísticos, patrimoniales y ecológicos, permitiendo además, de este modo, su uso equilibrado como recurso económico, cultural o educativo. This doctoral thesis shows an analysis of fluvial landscape evolution from multiple perspectives on the banks of Tagus and Jarama rivers, around Aranjuez. The thesis contemplates and combines natural features, such as hydrological, geomorphological and ecological features, as well as cultural features, like hydrological regulation and water management, interventions in channels and margins, changes in ownership and land use changes, mainly. This analysis has allowed to identify the factors system, dynamic and complex, that this landscape has created, as well as the interrelationships, connections, constraints and dependencies among considered landscape descriptors. For example, we have studied the relationships observed among fluvial dynamics- land ownership -conservation status, issues not addressed, assessed or quantified up to now in other works about this area. The research is organized into three major phases that led to the paper's central chapters (Chapters 2, 3 and 4). First, there has been a characterization of the factors, both natural and cultural, that organize the landscape of this predominantly fluvial area (geomorphology, climate and hydrological factors, vegetation, land and cultural elements of landscape significance). Then, it was made to study of fluvial landscape evolution by analyzing various elements previously identified and characterized. Aerial images were processed for five series and several old maps, obtaining an extensive database, that has been analyzed statistically. Finally, we have contrasted the partial results obtained in the previous chapters, making it possible to identify causal relationships between the factors that organize the landscape and the evolution of the elements that constitute it. This working method has been very useful for understanding the operation and evolution of a complex system, as the landscape of the Vega de Aranjuez, a territory with deep and ancient cultural interventions where anyway, nature feature always lies. It is possible that the main contribution of this work, also its most prominent difference compared with other studies of landscape, has been to show a complete and exhaustive view of all factors involved in the formation and evolution of the fluvial landscape, highlighting the relationships established among them. This approach could have an interesting applied facet, so that is a very useful tool for designing management plans on this river territory. Not surprisingly, a substantial part of the valley of the Tagus-Jarama in Aranjuez is a Site of Community Importance (SCI) and their subsequent and inevitable declaration as Special Area of Conservation (SAC) of the Natura 2000 network, in accordance with the provisions Directive 92/43/EC, requires the development of a management plan that largely could draw on what was presented, analyzed and interpreted in this paper. In this regard, it should be noted conscience and assumed to consider, on the inclusiveness of territorial reality, the landscape as a key element for the proper management of nature and territory. On the other hand, it is considered that the results of this thesis allow to propose measures for enhancement of outstanding scenery, which go well beyond the boundaries that currently the Cultural Landscape declared by UNESCO. In sum, the analysis of this river area made with the depth and breadth that enables working method can be used to design strategies that address the evolution of this territory in a line that guarantees global conservation landscape terms, heritage and ecological, also, allowing its use as a balancing economic, cultural or educational resource.