Search

The goal of this paper is to improve the type error messages in the presence of Haskell 98 type classes, in particular for the non-expert user. As a language feature, type classes are very pervasive, and strongly influence what is reported and when, even in relatively simple programs. We propose four type class directives, and specialized type rules, to lend high-level support to compilers to improve the type error messages. Both have been implemented, and can be used to easily modify the behavior of the type inference process. Keywords: type error messages, type classes, directives, domain-specific programming [ABSTRACT FROM AUTHOR]

In this article we investigate a novel execution paradigm - ML-like pattern-matching - for XML query processing. We show that such a paradigm is well adapted for a common and frequent set of queries and advocate that it constitutes a candidate for efficient execution of XML queries far better than the current XPath-based query mechanisms. We support our claim by comparing performances of XPath-based queries with pattern based ones, and by comparing the latter with the two efficiency-best XQuery processor we are aware of. [ABSTRACT FROM AUTHOR]

Truth values associated to fuzzy variables can be represented in an ordeal of different flavors, such as real numbers, percentiles, intervals, unions of intervals, and continuous or discrete functions on different domains. Many of the most interesting fuzzy problems deal with a discrete range of truth values. In this work we represent these ranges using Constraint Logic Programming over Finite Domains (CLP($\mathcal{FD}$)). This allows to produce finite enumerations of constructive answers instead of complicated, hardly self-explanatory, constraints expressions. Another advantage of representing fuzzy models through finite domains is that some of the existing techniques and algorithms of the field of distributed constraint programming can be borrowed. In this paper we exploit these considerations in order to create a new generation of collaborative fuzzy agents in a distributed environment. Keywords: Fuzzy Prolog, Modeling Uncertainty, (Constraint) Logic Programming, Constraint Programming Application, Finite Domains, Multi-Agent Systems, Collaborative Agents. [ABSTRACT FROM AUTHOR]

An unsatisfiable set of constraints is minimal if all its (strict) subsets are satisfiable. The task of type error diagnosis requires finding all minimal unsatisfiable subsets of a given set of constraints (representing an error), in order to generate the best explanation of the error. Similarly circuit error diagnosis requires finding all minimal unsatisfiable subsets in order to make minimal diagnoses. In this paper we present a new approach for efficiently determining all minimal unsatisfiable sets for any kind of constraints. Our approach makes use of the duality that exists between minimal unsatisfiable constraint sets and maximal satisfiable constraint sets. We show how to incrementally compute both these sets, using the fact that the complements of the maximal satisfiable constraint sets are the hitting sets of the minimal unsatisfiable constraint sets. We experimentally compare our technique to the best known method on a number of large type problems and show that considerable improvements in running time are obtained. Keywords: Minimal unsatisfiable sets, constraint solving, hitting sets, hypergraph transversals. [ABSTRACT FROM AUTHOR]

In this paper, we present a constraint solver for constraints on sets of spatial objects. With this aim, we define a constraint system for handling spatial data types (points, lines, polygons and regions) and constraints on them (equalities and inequalities, memberships, metric, topological and structural constraints), and provide a suitable theory for this constraint system. The constraint solver is presented in the form of transformation rules. These transformation rules handle a special kind of constraints used for consistency checking, enabling an optimized and efficient solving of spatial constraints. [ABSTRACT FROM AUTHOR]

A critical issue in the design of logic programming systems is their memory performance, both in terms of total memory usage and locality in memory accesses. BEAM, as most modern Prolog systems, requires both good emulator design and good memory performance for best performance. We report on a detailed study of the memory management techniques used on our sequential implementation of the EAM. We address questions like how effective are the techniques the BEAM uses to recover and reuse memory space, how garbage collection affects performance and how to classify and unify variables in a EAM environment. We also propose a finer variable allocation scheme to reduce memory overheads that is quite effective at reducing memory pressure, with only a small overhead. Keywords: Logic Programming, Extended Andorra Model, MemoryManagement, Language Implementation. [ABSTRACT FROM AUTHOR]

We describe the design of the olps system, an implementation of the preferred answer set semantics for ordered logic programs. The basic algorithm we propose computes the extended answer sets of a simple program using an intuitive 9-valued lattice, called T9. During the computation, this lattice is employed to keep track of the status of the literals and the rules while evolving to a solution. It turns out that the basic algorithm needs little modification in order to be able to compute the preferred answer sets of an ordered logic program. We illustrate the system using an example from diagnostic reasoning and we present some preliminary benchmark results comparing olps with existing answer set solvers such as smodels and dlv. Keywords: Preference, Answer Set Programming, Implementation [ABSTRACT FROM AUTHOR]

We present an optimizing compiler for the π-calculus that significantly improves the time and space performance of the MMC model checker. MMC exploits the similarity between the manner in which resolution techniques handle variables in a logic program and the manner in which the operational semantics of the π-calculus handles names by representing π-calculus names in MMC as Prolog variables, with distinct names represented by distinct variables. Given a π-calculus process P, our compiler for MMC produces an extremely compact representation of P's symbolic state space as a set of transition rules. It also uses AC unification to recognize states that are equivalent due to symmetry. [ABSTRACT FROM AUTHOR]

Provably correct compilation is an important aspect in development of high assurance software systems. In this paper we explore approaches to provably correct code generation based on programming language semantics, particularly Horn logical semantics, and partial evaluation. We show that the definite clause grammar (DCG) notation can be used for specifying both the syntax and semantics of imperative languages. We next show that continuation semantics can also be expressed in the Horn logical framework. [ABSTRACT FROM AUTHOR]

The need for direct memory manipulation through pointers is essential in many applications. However, it is also commonly understood that the use (or probably misuse) of pointers is often a rich source of program errors. Therefore, approaches that can effectively enforce safe use of pointers in programming are highly sought after. ATS is a programming language with a type system rooted in a recently developed framework Applied Type System, and a novel and desirable feature in ATS lies in its support for safe programming with pointers through a novel notion of stateful views. In particular, even pointer arithmetic is allowed in ATS and guaranteed to be safe by the type system of ATS. In this paper, we give an overview of this feature in ATS, presenting some interesting examples based on a prototype implementation of ATS to demonstrate the practicality of safe programming with pointer through stateful views. [ABSTRACT FROM AUTHOR]

The hybrid probabilistic programs framework [1] allows the user to explicitly encode both logical and statistical knowledge available about the dependency among the events in the program. In this paper, we extend the language of hybrid probabilistic programs by allowing disjunctive composition functions to be associated with heads of clauses, and we modify its semantics to make it more suitable to encode real-world applications. The new semantics is a natural extension of standard logic programming semantics. The new semantics of hybrid probabilistic programs also subsumes the implication-based probabilistic approach proposed by Lakshmanan and Sadri [12]. We provide also a sound and complete algorithm to compute the least fixpoint of hybrid probabilistic programs with annotated atomic formulas as rule heads. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of encoding complex concurrency control in reconfigurable systems. Such systems can be often reconfigured, either statically, or dynamically, in order to adapt to new requirements and a changing environment. We therefore take a declarative approach and introduce a set of high-level programming abstractions which allow the programmer to easily express complex synchronization constraints in multithreaded programs. The constructs are based on our model of role-based synchronization (RBS) which assumes attaching roles to concurrent threads and expressing a synchronization policy between the roles. The model is illustrated by describing an experimental implementation of our language as a design pattern library in OCaml. Finally, we also sketch a small application of a web access server that we have implemented using the RBS design pattern. [ABSTRACT FROM AUTHOR]

We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g. temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible. [ABSTRACT FROM AUTHOR]

An important property of strategies used to solve goals in functional logic programming (FLP) languages is the complete exploration of the solution space. Integrating constraints into FLP proved to be useful in many cases, as the resulting constraint functional logic programming (CFLP) offers more facilities and more efficient operational semantics. CFLP can be achieved by means of conditional rewrite systems with a narrowing-based operational semantics. A common idea to improve the efficiency of such operational semantics is to use specific algorithms from operations research as constraint solvers. If the algorithm does not return a complete set of solutions, the property of completeness might be lost. We present a real world timetabling problem illustrating this approach. We propose an algorithm, obtained as an integration of three known optimization algorithms for the linear assignment problem (LAP), enumerating solutions to the LAP in order of increasing weight, such that resolution of goals is complete again. We show, how the narrowing process can be tailored to use this algorithm and provide an efficient way to solve the timetable generation problem. Keywords: Functional-logic programming, Constraints, Narrowing,Timetable generation. [ABSTRACT FROM AUTHOR]

We present an application of functional programming in the domain of sound generation and processing. We use the lazy language Clean to define purely functional stream generators, filters and other processors, such as reverberators. Audio signals are represented (before the final output to arrays processed by the system primitives) as co-recursive lazy streams, and the processing algorithms have a strong dataflow taste. This formalism seems particularly appropriate to implement the ‘waveguide', or ‘physically-oriented' sound models. Lazy programming allocates the dynamical memory quite heavily, so we do not propose a real-time, industrial strength package, but rather a pedagogical library, offering natural, easy to understand coding tools. We believe that, thanks to their simplicity and clearness, such functional tools can be also taught to students interested in audio processing, but with a limited competence in programming. Keywords: Lazy streams, Sounds, DSP, Clean. [ABSTRACT FROM AUTHOR]

For at least 25 years, the most effective way to retarget systems software has been by using machine descriptions. But "machine description" doesn't mean what you think. A traditional machine description does contain information about the machine, but its utility is compromised in one of two ways: The description is useful only in support of a particular algorithm, such as instruction-set emulation, LR parsing, or bottom-up tree matching. Information about the machine is inextricably intertwined with information about a particular tool's internal representation, such as a compiler's intermediate code. [ABSTRACT FROM AUTHOR]

Increasingly, we see a trend where programmeable processors are incorporated into a wide variety of everyday devices, ranging from "smart badges," copy and fax machines, phones, and automobiles to traffic lights and wireless sensor networks. At the same time, the functionality expected of the software deployed on such processors becomes increasingly complex (e.g., general-purpose operating systems such as Linux on cell phones, intrusion-detection and related security security measures on wireless sensor devices). The increasing complexity of such software, and the reliability expected of them, suggest a plausible application of declarative languages. However, programs in declarative languages very often experience a significant increase in code size when they are compiled down to native code. This can be a problem in situations where the amount of memory available is limited. This talk discusses a number of different techniques for reducing the memory footprint of executables. [ABSTRACT FROM AUTHOR]