Parallel execution of Prolog programs: a survey

Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.

Incremental analysis of constraint logic programs

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program which has already been analyzed. In these cases, it appears inecient to perform the analysis of the program again from scratch, as needs to be done with current systems. We describe how the xed-point algorithms used in current generic analysis engines for (constraint) logic programming languages can be extended to support incremental analysis. The possible changes to a program are classied into three types: addition, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be recomputed and for performing the actual recomputation. The potential benets and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in the PLAI generic abstract interpretation framework. The results show signicant benets when using the proposed incremental analysis algorithms.

Improving abstract interpretations by combining domains

This article considers static analysis based on abstract interpretation of logic programs over combined domains. It is known that analyses over combined domains provide more information potentially than obtained by the independent analyses. However, the construction of a combined analysis often requires redefining the basic operations for the combined domain. A practical approach to maintain precision in combined analyses of logic programs which reuses the individual analyses and does not redefine the basic operations is illustrated. The advantages of the approach are that proofs of correctness for the new domains are not required and implementations can be reused. The approach is demonstrated by showing that a combined sharing analysis — constructed from "old" proposals — compares well with other "new" proposals suggested in recent literature both from the point of view of efficiency and accuracy.

Global analysis of constraint logic programs

This article presents and illustrates a practical approach to the dataow analysis of constraint logic programming languages using abstract interpretation. It is rst argued that from the framework point of view it suces to propose relatively simple extensions of traditional analysis methods which have already been proved useful and practical and for exist. This is shown by proposing a simple extension of Bruynooghes traditional framework which allows it to analyze constraint logic programs. Then and using this generalized framework two abstract domains and their required abstract functions are presented the rst abstract domain approximates deniteness information and the second one freeness. Finally an approach for cobining those domains is proposed The two domains and their combination have been implemented and used in the analysis of CLP and Prolog III applications. Results from this implementation showing its performance and accuracy are also presented

Las presentaciones de trabajo en lengua inglesa: una propuesta de curso on-line.

Desde la explosión de crecimiento de internet que comenzó en los años 90, se han ido creando y poniendo a disposición de los usuarios diversas herramientas para compartir información y servicios de diversas formas, desde el nacimiento del primer navegador hasta nuestros días, donde hay infinidad de lenguajes aplicables al ámbito web. En esta fase de crecimiento, en primer lugar, de cara a usuarios individuales, saldrían herramientas que permitirían a cada cual hacer su web personal, con sus contenidos expuestos. Más adelante se fue generando el fenómeno “comunidad”, con, por ejemplo, foros, o webs en las que había múltiples usuarios que disfrutaban de contenidos o servicios que la web ofreciese. Este crecimiento del mundo web en lo comunitario ha avanzado en muchas ramas,entre ellas, por supuesto, la educacional, surgiendo plataformas como la que es base del proyecto que a continuación se presenta, y herramienta básica y prácticamente ya imprescindible en la enseñanza universitaria: Moodle. Moodle es una herramienta diseñada para compatir recursos y diseñar actividades para el usuario potencial, complementando su aprendizaje en aula, o incluso siendo una vía autónoma de aprendizaje en sí misma. Se ha realizado un estudio sobre el estado de saludo de los contenidos que se exponen en Moodle, y se ha encontrado que una gran mayoría de los cursos que se pueden visitar tienen un gran número de carencias. Por un lado, hay pocos con material original explotado exclusivamente para el curso, y, si tienen material original, no se ha observado una especial atención por la maquetación. Por otro lado, hay muchos otros sin material original, y, en ambos casos, no se ha encontrado ningún curso que ofrezca material audiovisual exclusivo para el curso, presentando algunos en su lugar material audiovisual encontrado en la red (Youtube, etc). A la vista de estos hechos, se ha realizado un proyecto que intenta aportar soluciones ante estas carencias, y se presenta un curso procedente de diversas referencias bibliográficas, para la parte textual, y material audiovisual original e inédito que también se ha explotado específicamente para este curso. Este material ha sido por un lado vídeo, que se ha visionado, editado y subtitulado con software de libre distribución, y por otro lado, audio, que complementa un completo glosario que se ha añadido como extra al curso y cuyo planteamiento no se ha encontrado en ningún curso online de los revisados. Todo esto se ha envuelto en una maquetación cuidada que ha sido fruto del estudio de los lenguajes web html y CSS, de forma que, por un lado, el curso sea un lugar agradable en el que aprender dentro de internet, y por otro, se pudiesen realizar ciertas operaciones que sin estos conocimientos habrían sido imposibles, como la realización del glosario o la incrustación de imágenes y vídeos. A su vez, se ha tratado de dar un enfoque didáctico a toda la memoria del proyecto, de forma que pueda ser de utilidad a un usuario futuro que quisiese profundizar en los usos de Moodle, introducirse en el lenguaje web, o introducirse en el mundo de la edición de vídeo. ABSTRACT: Since the explosion of Internet growth beginning in the 90s, many tools have been created and made available for users to share information and services in various ways, from the birth of the first browser until today, where there are plenty of web programming languages. This growth stage would give individual users tools that would allow everyone to make an own personal website, with their contents exposed. Later, the "community" phenomenon appeared with, for example, forums, or websites where multiple users enjoyed the content or web services that those websites offered. Also, this growth in the web community world has progressed in many fields, including education, with the emerge of platforms such as the one that this project uses as its basis, and which is the basic and imperative tool in college education: Moodle. Moodle is a tool designed to share resources and design activities for the potential user, completing class learning, or even letting this user learn in an autonomous way. In this project a study on the current situation of the content present in Moodle courses around the net has been carried out, and it has been found that most of them lack of original material exploited exclusively for the courses, and if they have original material, there has been not observed concern on the layout where that material lies. On the other hand, there are many other with non original material, and in both cases, there has not been found any course that offers audio- visual material made specifically for the course, instead of presenting some audiovisual material found on the net (Youtube, etc). In view of these facts, the project presented here seeks to provide solutions to these shortcomings, presenting a course with original material exploited from various references, and unpublished audioevisual material which also has been exploited specifically for this course. This material is, on one hand, video, which has been viewed, edited and subtitled with free software, and on the other, audio, which complements a comprehensive glossary that has been added as an extra feature to the course and whose approach was not found in any of the online courses reviewed. All of this has been packaged in a neat layout that has been the result of the study of web languages HTML and CSS, so that first, the course was a pleasant place to learn on the internet, and second, certain operations could be performed which without this knowledge would have been impossible, as the glossary design or embedding images and videos. Furthermore, a didactic approach has been adopted to the entire project memory, so it can be useful to a future user who wanted to go deeper on the uses of Moodle, containing an intro into the web language, or in the world video editing.

Experiments in abstract interpretation-based code certification for pervasive systems

Proof carrying code (PCC) is a general is originally a roof in ñrst-order logic of certain vermethodology for certifying that the execution of an un- ification onditions and the checking process involves trusted mobile code is safe. The baste idea is that the ensuring that the certifícate is indeed a valid ñrst-order code supplier attaches a certifícate to the mobile code proof. which the consumer checks in order to ensure that the The main practical difñculty of PCC techniques is in code is indeed safe. The potential benefit is that the generating safety certiñeates which at the same time: i) consumer's task is reduced from the level of proving to allow expressing interesting safety properties, ii) can be the level of checking. Recently, the abstract interpre- generated automatically and, iii) are easy and efficient tation techniques developed, in logic programming have to check. In [1], the abstract interpretation techniques been proposed as a basis for PCC. This extended ab- [5] developed in logic programming1 are proposed as stract reports on experiments which illustrate several is- a basis for PCC. They offer a number of advantages sues involved in abstract interpretation-based certifica- for dealing with the aforementioned issues. In particution. First, we describe the implementation of our sys- lar, the xpressiveness of existing abstract domains will tem in the context of CiaoPP: the preprocessor of the be implicitly available in abstract interpretation-based Ciao multi-paradigm programming system. Then, by code certification to deñne a wide range of safety propermeans of some experiments, we show how code certifi- ties. Furthermore, the approach inherits the automation catión is aided in the implementation of the framework. and inference power of the abstract interpretation en- Finally, we discuss the application of our method within gines used in (Constraint) Logic Programming, (C)LP. the área, of pervasive systems

A model for inter-module analysis and optimizing compilation

Recent research into the implementation of logic programming languages has demonstrated that global program analysis can be used to speed up execution by an order of magnitude. However, currently such global program analysis requires the program to be analysed as a whole: sepárate compilation of modules is not supported. We describe and empirically evalúate a simple model for extending global program analysis to support sepárate compilation of modules. Importantly, our model supports context-sensitive program analysis and multi-variant specialization of procedures in the modules.

Concurrency in prolog using threads and a shared database

Concurrency in Logic Programming has received much attention in the past. One problem with many proposals, when applied to Prolog, is that they involve large modifications to the standard implementations, and/or the communication and synchronization facilities provided do not fit as naturally within the language model as we feel is possible. In this paper we propose a new mechanism for implementing synchronization and communication for concurrency, based on atomic accesses to designated facts in the (shared) datábase. We argüe that this model is comparatively easy to implement and harmonizes better than previous proposals within the Prolog control model and standard set of built-ins. We show how in the proposed model it is easy to express classical concurrency algorithms and to subsume other mechanisms such as Linda, variable-based communication, or classical parallelism-oriented primitives. We also report on an implementation of the model and provide performance and resource consumption data.

Global analysis of standard prolog programs

Abstract interpretation-based data-flow analysis of logic programs is, at this point, relatively well understood from the point of view of general frameworks and abstract domains. On the other hand, comparatively little attention has been given to the problems which arise when analysis of a full, practical dialect of the Prolog language is attempted, and only few solutions to these problems have been proposed to date. Existing proposals generally restrict in one way or another the classes of programs which can be analyzed. This paper attempts to fill this gap by considering a full dialect of Prolog, essentially the recent ISO standard, pointing out the problems that may arise in the analysis of such a dialect, and proposing a combination of known and novel solutions that together allow the correct analysis of arbitrary programs which use the full power of the language.

Analyzing logic programs with dynamic scheduling

Traditional logic programming languages, such as Prolog, use a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, usually provide more flexible scheduling in which computation generally proceeds leftto- right but in which some calis are dynamically "delayed" until their arguments are sufRciently instantiated to allow the cali to run efficiently. Such dynamic scheduling has a significant cost. We give a framework for the global analysis of logic programming languages with dynamic scheduling and show that program analysis based on this framework supports optimizations which remove much of the overhead of dynamic scheduling.

A simulation study of or- and independent and-parallelism

Although studies of a number of parallel implementations of logic programming languages are now available, the results are difficult to interpret due to the multiplicity of factors involved, the effect of each of which is difficult to sepárate. In this paper we present the results of a highlevel simulation study of or- and independent and-parallelism with a wide selection of Prolog programs that aims to facilítate this separation. We hope this study will be instrumental in better understanding and comparing results from actual implementations, as shown by an example in the paper. In addition, the paper examines some of the issues and tradeoffs associated with the combination of and- and or-parallelism and proposes reasonable solutions based on the simulation data.

On the correctness and efficiency of independent and-parallelism in logic programs

This paper presents and proves some fundamental results for independent and-parallelism (IAP). First, the paper treats the issues of correctness and efficiency: after defining strict and non-strict goal independence, it is proved that if strictly independent goals are executed in parallel the solutions obtained are the same as those produced by standard sequential execution. It is also shown that, in the absence of failure, the parallel proof procedure doesn't genérate any additional work (with respect to standard SLDresolution) while the actual execution time is reduced. The same results hold even if non-strictly independent goals are executed in parallel, provided a trivial rewriting of such goals is performed. In addition, and most importantly, treats the issue of compile-time generation of IAP by proposing conditions, to be written at compile-time, to efficiently check strict and non-strict goal independence at run-time and proving the sufficiency of such conditions. It is also shown how simpler conditions can be constructed if some information regarding the binding context of the goals to be executed in parallel is available to the compiler trough either local or program-level analysis. These results therefore provide a formal basis for the automatic compile-time generation of IAP. As a corollary of such results, the paper also proves that negative goals are always non-strictly independent, and that goals which share a first occurrence of an existential variable are never independent.

An abstract machine for restricted and-parallel execution of logic programs

Although the sequential execution speed of logic programs has been greatly improved by the concepts introduced in the Warren Abstract Machine (WAM), parallel execution represents the only way to increase this speed beyond the natural limits of sequential systems. However, most proposed parallel logic programming execution models lack the performance optimizations and storage efficiency of sequential systems. This paper presents a parallel abstract machine which is an extension of the WAM and is thus capable of supporting ANDParallelism without giving up the optimizations present in sequential implementations. A suitable instruction set, which can be used as a target by a variety of logic programming languages, is also included. Special instructions are provided to support a generalized version of "Restricted AND-Parallelism" (RAP), a technique which reduces the overhead traditionally associated with the run-time management of variable binding conflicts to a series of simple run-time checks, which select one out of a series of compiled execution graphs.

Tools for constraint visualization: The VIFID/TRIFID tool

Visualization of program executions has been used in applications which include education and debugging. However, traditional visualization techniques often fall short of expectations or are altogether inadequate for new programming paradigms, such as Constraint Logic Programming (CLP), whose declarative and operational semantics differ in some crucial ways from those of other paradigms. In particular, traditional ideas regarding the behavior of data often cannot be lifted in a straightforward way to (C)LP from other families of programming languages. In this chapter we discuss techniques for visualizing data evolution in CLP. We briefly review some previously proposed visualization paradigms, and also propose a number of (to our knowledge) novel ones. The graphical representations have been chosen based on the perceived needs of a programmer trying to analyze the behavior and characteristics of an execution. In particular, we concéntrate on the representation of the run-time valúes of the variables, and the constraints among them. Given our interest in visualizing large executions, we also pay attention to abstraction techniques, i.e., techniques which are intended to help in reducing the complexity of the visual information.

Optimization of logic programs with dynamic scheduling

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.