nach oben

2011 | Buch

Kapitel lesen Erstes Kapitel lesen

Functional and Constraint Logic Programming

20th International Workshop, WFLP 2011, Odense, Denmark, July 19th, Proceedings

herausgegeben von: Herbert Kuchen

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed conference proceedings of the 20th International Workshop on Functional and Constraint Logic Programming, WFLP 2011, held in Odense, Denmark, in July 2011 as Part of the 13th International Symposium on Principles and Practice of Declarative Programming (PPDP 2011), the 22st International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2011), and the 4th International Workshop on Approaches and Applications of Inductive Programming (AAIP 2011). From the 10 papers submitted, 9 were accepted for presentation the proceeding. The papers cover current research in all areas of functional and logic programming as well as the integration of constraint logic and object-oriented programming, and term rewriting.

Inhaltsverzeichnis

Frontmatter

Functional Logic Programming

KiCS2: A New Compiler from Curry to Haskell

Abstract

In this paper we present our first steps towards a new system to compile functional logic programs of the source language Curry into purely functional Haskell programs. Our implementation is based on the idea to represent non-deterministic results as values of the data types corresponding to the results. This enables the application of various search strategies to extract values from the search space. We show by several benchmarks that our implementation can compete with or outperform other existing implementations of Curry.

Bernd Braßel, Michael Hanus, Björn Peemöller, Fabian Reck

New Functional Logic Design Patterns

Abstract

Patterns distill successful experience in solving common software problems. We introduce a handful of new software design patterns for functional logic languages. Some patterns are motivated by the evolution of the paradigm in the last 10 years. Following usual approaches, for each pattern we propose a name and we describe its intent, applicability, structure, consequences, etc. Our patterns deal with fundamental aspects of the design and implementation of functional logic programs such as function invocation, data structure representation and manipulation, specification-driven implementation, pattern matching, and non-determinism. We present some problems and we show fragments of programs that solve these problems using our patterns. The programming language of our examples is Curry. The complete programs are available on-line.

Sergio Antoy, Michael Hanus

XQuery in the Functional-Logic Language Toy

Abstract

This paper presents an encoding of the XML query language XQuery in the functional-logic language \(\mathcal{TOY}\). The encoding is based on the definition of for-let-where-return constructors by means of \(\mathcal{TOY}\) functions, and uses the recently proposed XPath implementation for this language as a basis. XQuery expressions can be executed in \(\mathcal{TOY}\) obtaining sequences of XML elements as answers. Our setting exploits the non-deterministic nature of \(\mathcal{TOY}\) by retrieving the elements of the XML tree once at a time when necessary. We show that one of the advantages of using a rewriting-based language for implementing XQuery is that it can be used for optimizing XQuery expressions by query rewriting. With this aim, XQuery expressions are converted into higher order patterns that can be analyzed and modified by \(\mathcal{TOY}\) functions.

Jesus M. Almendros-Jiménez, Rafael Caballero, Yolanda García-Ruiz, Fernando Sáenz-Pérez

Functional Programming

Size Invariant and Ranking Function Synthesis in a Functional Language

Abstract

Size analysis is concerned with the compile-time determination of upper bounds to the size of program variables, including the size of the results returned by functions. It is useful in many situations and also as a prior step to facilitate other analyses, such as termination proofs. Ranking function synthesis is one way of proving termination of loops or of recursive definitions.

We present a result in automatic inference of size invariants, and of ranking functions proving termination of functional programs, by adapting linear techniques developed for other languages. The results are accurate and allow us to solve some problems left open in previous works on automatic inference of safe memory bounds.

Ricardo Peña, Agustin D. Delgado-Muñoz

Memoizing a Monadic Mixin DSL

Abstract

Modular extensibility is a highly desirable property of a domain-specific language (DSL): the ability to add new features without affecting the implementation of existing features. Functional mixins (also known as open recursion) are very suitable for this purpose.

We study the use of mixins in Haskell for a modular DSL for search heuristics used in systematic solvers for combinatorial problems, that generate optimized CC++ code from a high-level specification. We show how to apply memoization techniques to tackle performance issues and code explosion due to the high recursion inherent to the semantics of combinatorial search.

As such heuristics are conventionally implemented as highly entangled imperative algorithms, our Haskell mixins are monadic. Memoization of monadic components causes further complications for us to deal with.

Pieter Wuille, Tom Schrijvers, Horst Samulowitz, Guido Tack, Peter Stuckey

A Functional Approach to Worst-Case Execution Time Analysis

Abstract

Modern hard real-time systems demand safe determination of bounds on the execution times of programs. To this purpose, program execution for all possible combinations of input values is impracticable. In alternative, static analysis methods provide sound and efficient mechanisms for determining execution time bounds, regardless of input data.

We present a calculation-based and compositional development of a functional static analyzer using the Abstract Interpretation framework. Meanings of programs are expressed in fixpoint form, using a two-level denotational meta-language. At the higher level, we devise a uniform fixpoint semantics with a relational-algebraic shape, defined as the reflexive transitive closure of the program binary relations. Fixpoints are calculated in the point-free style using functional composition and a proper recursive operator. At the lower level, state transformations are specified by semantic transformers designed as abstract interpretations of the transition semantics.

Vítor Rodrigues, Mário Florido, Simão Melo de Sousa

Building a Faceted Browser in CouchDB Using Views on Views and Erlang Metaprogramming

Abstract

Consider sets of XML documents where documents from the same set adhere to the same schema, and documents from different sets adhere to a different schema. All documents describe language resources and tools, but as their schemas differ so differ their use of descriptors and the values they can hold. The collection of metadata documents and schemas is open and can get extended anytime. This paper describes a solution to the problem of storing all documents in a single database and making them accessible to naive users to easily identify language resources and tools according to their needs and interest. The proposed storage solution makes use of the document-based database CouchDB; for easy access, we propose a combination of faceted search and full-text search, allowing users without intricate knowledge about metadata descriptors to explore all documents in a systematic manner. Faceted search is entirely bootstrapped using CouchDB views and meta-views that we meta-programmed in Erlang given a declarative facet specification.

Claus Zinn

Integration of Constraint Logic and Object-Oriented Programming

Logic Java: Combining Object-Oriented and Logic Programming

Abstract

We have developed the programming language Logic Java which smoothly integrates the object-oriented language Java and logic programming concepts such as logic variables, constraint solving, and backtracking. It combines the advantages of object-orientation such as easy maintainability and adaptability due to inheritance and encapsulation of structure and behavior with the advantages of logic languages such as suitability for search problems. Java annotations and a symbolic Java virtual machine are used to handle the logic programming concepts. In contrast to previous approaches to integrate object-oriented and logic programming, we preserve the syntax of Java. Our language is not split into two distinguishable parts but as closely integrated as possible. Besides the design and implementation of Logic Java, providing a suitable interface between conventional and logic computations is the main contribution of this paper. A killer application, which can hardly be implemented more elegantly in any other language, is the tool Muggl which systematically generates glass-box test cases for Java programs. Applications requiring a substantial amount of search are also well suited.

Tim A. Majchrzak, Herbert Kuchen

Term Rewriting

On Proving Termination of Constrained Term Rewrite Systems by Eliminating Edges from Dependency Graphs

Abstract

In this paper, we propose methods for proving termination of constrained term rewriting systems, where constraints are interpreted by built-in semantics given by users, and rewrite rules are assumed to be sound for the interpretation. To this end, we extend the dependency pair framework for proving termination of unconstrained term rewriting systems to constrained term rewriting systems. Moreover, we extend the dependency pair framework so that dependency pair processors take a subgraph of the dependency graph as input and they output a finite set of graphs which can be obtained by eliminating nodes and/or edges from the input graph.

Tsubasa Sakata, Naoki Nishida, Toshiki Sakabe

Backmatter

Titel: Functional and Constraint Logic Programming
herausgegeben von: Herbert Kuchen
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-22531-4
Print ISBN: 978-3-642-22530-7
DOI: https://doi.org/10.1007/978-3-642-22531-4