Selected research
(Abstracts and links)
Integration of Paradigms
Expressivity of Functional Logic Languages and their Implementation
The paper studies the expressivity of declarative languages and, in
particular,
functional-logic languages. Different advanced language features are
explored
showing that functional-logic programs have a very high expressivity.
Several
examples are presented.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Implementations
Graph based Implementation of a Functional Logic Language
We investigate the development of a graph reduction machine for a
higher-order
functional logic language by extension of an appropiate architecture
for
purely functional languages. To execute logic programs the machine must
be capable of perfoming unification and backtracking. We show the
integration
of these mechanisms in a programmed (functional) graph reduction
machine.
The new machine has been implemented on a transputer system.
Bib-Tex,
PS,
ftp
(compressed
postscript)
Graph-Narrowing to Implement a Functional Logic Language
We investigate the development of a graph narrowing machine for a
higher
order functional logic language by extension of an appropriate
architecture
for purely functional languages. To execute logic programs the machine
must be capable of unification and backtracking. We show the
integration
of these mechanisms in a programmed (functional) graph reduction
machine.
The resulting abstract machine has been realized in C code as part of
the
implementation of the functional logic language BABEL. A brief
introduction
to this language is included. Moreover, we show a comparison between
BABEL
and PROLOG based on the runtimes of some example programs.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Lazy Narrowing in a Graph Machine
The paper investigates the implementation of lazy narrowing in the
framework
of a graph reduction machine. By extending an appropriate architecture
for purely functional languages an abstract graph narrowing machine for
a functional logic language is constructed. The machine is capable of
performing
unification and backtracking. The techniques used in functional
languages
to cope with lazy evaluation are not directly applicable, but must be
modified
due to the logic component of the implemented language. A prototype
implementation
of the new machine has been developed.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Efficient Compilation of Lazy Narrowing into Prolog
The paper presents new techniques for the transformation of lazy
narrowing
in logic programs. A formalism, called demand patterns, is
introduced,
and used to define a demand driven strategy to compute lazy narrowing.
The strategy is used to produce standard PROLOG code from programs
written
in a functional-logic language. Our method has a number of advantages
over
other approaches. While it can compute a larger class of program, it
needs
less reevaluation effort, and fully uses efficient elements of PROLOG
compilers.
The gain of efficiency is shown by presenting the execution times of
some
example programs.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Implementing a Lazy Functional Logic Language with Disequality
Constraints
In this paper, we investigate the implementation of a lazy functional
logic
language (in particular the language BABEL) which uses disequality
constraints
for solving equations and building answers. We specify a new
operational
semantics which combines lazy narrowing with disequality constraints
and
we define an abstract machine tailored to the execution of BABEL
programs
according to this semantics. The machine is designed as a quite natural
extension of a lazy graph narrowing machine. Disjunctions of
disequalities
are handled using the backtracking mechanism.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscrip)
Lazy strategies and Program Analysis
Efficient Lazy Narrowing using Demandedness Analysis
In this paper we investigate the efficient implementation of lazy
narrowing,
the usual operational semantics of functional logic languages, by using
abstract interpretation. In order to avoid reevaluations of arguments
in
a function call, they must be evaluated as soon as possible. The
detection
of which (parts of the) arguments need evaluation is done by using demandedness
analysis. In contrast to previous approaches our analysis retains
laziness
and gives a very accurate information even in the presence of strong
dependencies
between the arguments (for instance, two recursive arguments).
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Demandedness Analysis with Dependence Information for Narrowing
based Languages
Functional logic programming languages have a functional syntax and use
narrowing as operational semantics. Here we consider the efficient
implementation
of lazy narrowing, a strategy which only evaluates the arguments of a
function
application, if their evaluation is really demanded. For an efficient
implementation
of lazy narrowing it is crucial to evaluate the arguments as early as
possible.
Otherwise the arguments are frequently reevaluated. A demandedness
analysis
is used to detect which parts of the arguments can safely be evaluated
before the call to the function. Several approaches also use this idea,
but they sacrifice laziness in order to avoid inefficiency. Our
approach
is more lazy than the previous approaches, and it uses a more powerful
notion of demandedness, which allows to express infinite demand
patterns
like e.g. spine normal form. Moreover, in contrast to the previous
approaches,
we take into account dependencies between the arguments of a function
in
order to improve the efficiency.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Partial Predicates for Demand Analysis
This work studies demand analysis - which is closely related to
backwards
strictness analysis - in a semantic framework of
partial predicates, which in turn are constructive realizations
of ideals in a domain. This will allow us to give a concise, unified
presentation
of our previous work on the subject, to relate it to other analyses
based
on abstract interpretation or strictness logics and, more
important,
to prove the soundness of our analysis based on demand equations.
There are also some innovative results. One of them is the possibility
of using program transformation techniques to perform the
analysis,
specially in those domains of properties where algorithms based on
constraint
solving are too weak. The other one is a proposal to lift partial
predicates
in order to cope with higher order demand properties.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Bottom-up Evaluation of Functional Logic
Programs
This paper introduces semantics and transformation techniques for the bottom-up execution of functional
logic programs with a narrowing
based execution mechanism. We first propose a notion of bottom-up
evaluation with possibly higher-order and non-strict semantics. Then we
consider the question of making this execution goal-directed by adapting the
well-known magic-sets transform for logic programs. Coping with
non-strict semantics is far from trivial and several solutions for this
issue are proposed.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Parallel Implementations
Independent AND-Parallel Implementation of Narrowing
We present a parallel graph narrowing machine, which is used to
implement
a functional logic language on a shared memory multiprocessor. It is an
extension of an abstract machine for a purely functional language. The
result is a programmed graph reduction machine which integrates the
mechanisms
of unification, backtracking, and independent and-parallelism. In the
machine,
the subexpressions of an expression can run in parallel. In the case of
backtracking, the structure of an expression is used to avoid the
reevaluation
of subexpressions as far as possible. Deterministic computations are
detected.
Their results are maintained and need not be reevaluated after
backtracking.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Independent Subexpressions Parallelism with Delayed Synchronization
for
Functional Logic Languages
The paper describes the implementation of a parallel graph narrowing
machine.
The machine implements a functional logic language on a shared memory
multiprocessor.
The model of parallelism uses an independence condition to decide which
subexpressions of an expression can run in parallel. The outer
expression
continues its execution and the synchronization with a subtask is only
performed when its result is needed. The machine is fully implemented
and
some experimental results are shown.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Default Rules
Default Rules: An Extension of Constructive Negation for
Narrowing-based
Languages
In this paper an extension of narrowing-based functional logic
languages
is proposed: Every partial definition of a function can be completed
with
a default rule. In a concrete function call, the default rule is
applicable
when the normal ones determine that they cannot compute the value of
the
call. The use of the default rule, in the presence of a goal with
variables,
is constructive. The operational semantics provides constraints to the
variables to make the default rule applicable. Narrowing semantics are
modified extending the technique of constructive negation.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Extending Constructive Negation for Partial Functions in Lazy
Narrowing-based
Languages
In this paper the mechanism of Default Rules for narrowing-based
languages
previously proposed is adapted to lazy narrowing. Every partial
definition
of a function can be completed with a default rule. In a concrete
function
call, the default rule is applicable when the normal ones determine
that
they cannot compute the value of the call. Furthermore, when the goal
has
variables the evaluation mechanism provides constraints to the
variables
to make the default rule applicable. Lazy narrowing semantics are
extended
with the technique of constructive negation The main advantage is that
the coroutining implementation technique described by Chan, which is
the
basis for an efficient implementation, can be fully formalized in our
framework.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Curry: A New Proposal
Curry: A Truly Functional Logic Language
Functional and logic programming are the most important declarative
programming
paradigms, and interest in combining them has grown over the last
decade.
However, integrated functional logic languages are currently not widely
used. This is due to the fact that the operational principles are not
well
understood and many different evaluation strategies have been proposed
which resulted in many different functional logic languages. To
overcome
this situation, we propose the functional logic language Curry which
can
deal as a standard language in this area. It includes important ideas
of
existing functional logic languages and recent developments, and
combines
the most important features of functional and logic languages. Thus,
Curry
can be the basis to combine the currently separated research efforts of
the functional and logic programming communities and to boost
declarative
programming in general. Moreover, since functions provide for more
efficient
evaluation strategies and are a declarative replacement of some impure
features of Prolog (in particular, pruning operators), Curry can be
also
used as a declarative successor of Prolog.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Adding Type Classes to Functional-logic Languages
The paper discusses the advantages of introducing type classes into
functional-logic
languages. Type classes are a powerful type system included in the
functional
language Haskell that allow to model some of the object oriented
programming
features. A number of problems arise when type classes are combined
with
the functional and logic characteristics of the language, and we sketch
some solutions. On the other hand it has a number of advantages like
the
declarative model of Prolog attribute variables or the integration in
the
language of bounded quantifiers.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Technical Report version:
Reference LML-LSIIS-FIM/2/96
DVI,
PS,
ftp
(compressed postscript)
On the Expressive Power of Functional-logic
Languages
for the Real World
Functional-logic languages (FLL) has been proposed as a new programming
paradigm aiming at the combination of the most important declarative
languages:
logic programming (LP), functional programming (FP) and constraint LP.
To achieve such an integration is a highly desirable goal, since the
resulting
languages would fully exploit the facilities of logic programming in a
general sense (functions, predicates and equality) and allow their
users
to keep them separate or to mix them in the way that best suits to a
particular
application. Among the existing languages (Babel, Alf, Escher, Oz) we
will
focus on the result of a recent international cooperation: Curry.
Functional-logic languages are very expressive languages, including
features from FP (nested expressions, lazy evaluation, higher-order
functions)
and LP (logical variables, partial data structures, automatic
management
of searches, constraint evaluation). Moreover, the amalgamated use of
them
develops new programming techniques.
The talk presents the main elements of functional-logic languages
focused
on two aspects: the expressive power of the language constructs and how
to establish declarative programming as a major paradigm in the
non-academic
world. From this point of view, FLL have a enormous potential is a
variety
of areas: interfaces with databases, natural language engineering and
natural
language query to databases, planning and scheduling systems,
knowledge-based
decision support systems, symbolic computation systems, etc.
To show that Curry is quite adequate for the development of real
world
applications: creation of reliable programs (improved by the logic
semantics
of the language which allows the use of very advanced compilers,
declarative
debuggers, the type system, ...), support for programming-in-the-large
(provided by the use of type classes, amodule system, interface with
external
functions, and object oriented extensions), program maintenance
(improved
again by the clear semantics, the use of automatic tools for analysis
and
program transformation, etc.) and the access to external databases.
Recovering Sequentiality in Functional-Logic
Programs
Efficient code generation in implementations of functional logic
languages
relies on the sequentiality of the program rules --- existence of an
optimal
evaluation order for arguments. Parallel evaluation of arguments in the
presence
of free variables is
out of the question due to the possibility of backtracking and sharing
of these variables among different arguments. In this paper we show
that
the lack of sequentiality is often syntactic rather than semantic and
that
a clever use of type information and strictness analysis can enable a
compiler
to generate sequential code from most programs.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Sequentiality Analysis in Functional-Logic
Programs
The efficient implementation of functional logic languages relies on
finding
(if it exists) an optimal evaluation order for the arguments of
functions.
Both problems, the right evaluation order, and the sequentiality
of program rules are difficult and can benefit from using static
analysis techniques. The second problem is of special interest because
the parallel evaluation of arguments is out of the question due
to
the possibility of backtracking and sharing of free logical
variables
among different arguments. However, the lack of sequentiality is
often syntactic rather than semantic. In this paper we show that
an adequate use of type information and strictness analysis can
help
a compiler to (i) derive an optimal evaluation order, and
(ii)
generate sequential code from most programs.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Partial Predicates for Demand Analysis
This work studies demand analysis - which is closely related to
backwards
strictness analysis - in a semantic framework of
partial predicates, which in turn are constructive realizations of
ideals in a domain. This will allow us to give a concise,
unified
presentation of our previous work on the subject, to relate it to other
analyses based on abstract interpretation or strictness logics
and,
more important, to prove the soundness of our analysis based on demand
equations. There are also some innovative results. One of them is the
possibility
of using program transformation techniques to perform the analysis,
specially in those domains of properties where algorithms based
on
constraint solving are too weak. The other one is a proposal to lift
partial
predicates in order to cope with higher order demand properties.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
On the Role of Functional-logic Languages
for the
Debugging of Imperative Programs
The paper presents some aspects of the debugging subsystem of the
ongoing
project SLAM where the language Curry plays a significant role. The
SLAM
project is an attempt to amalgamate most of the best facilities
of
declarative languages to the development of imperative programs.
The SLAM system is composed by i) an object oriented specification
language.
(Functional style) Rules are used to define class operations each of
them
with logical pre and post-conditions. ii) A
development
environment that, among other features, is able to generate
readable
code in a high level object oriented (imperative) language. iii)
The generated code includes (part of) the pre and post-conditions as
assertions,
that can be automatically checked in the debug mode execution of
programs.
We concentrate on the latter aspect. Many useful properties can be
expressed
in the SLAM language and these properties are translated into a
Curry
program that is linked (via an adequate interface) with the
generated
program. The Curry execution is responsible for checking properties,
interacting
with the debugging execution of the program.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
The SLAM project (the
SLAM language
and environment / Specification and Visualization of the WAM / the
Friendly-WAM
)
A Formal Definition of an Abstract Prolog Compiler
In this paper, an abstract view of the WAM (Warren Abstract Machine), a
Prolog compiler, is presented. Optimizations and implementation details
are hidden in order to give a description that clearly explains how the
WAM implements SLD resolution with a depth search strategy and
backtracking.
The Abstract WAM is derived by stepwise refinement from SLD resolution.
It is formally specified by using abstract data types in an object
oriented
style.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Visualization as Debugging: Understanding/Debugging the Warren
Abstract
Machine
This paper presents a twofold proposal to understand the Warren
Abstract
Machine. A stepwise definition of the WAM by using abstract data types
(for every WAM component) is briefly presented. Furthermore, we
describe
a visual environment which can be used for the emulation of the Warren
Abstract Machine. It has been designed as a high level debugger for
object
oriented programs, following a methodology sketched in the paper. The
tool
has the capability to show the user the internal behaviour of the WAM
during
a program execution by showing its components at the desired level of
abstraction.
The tool provides an interactive and friendly interface. Configurable
tracing
and dynamic breakpoint location can be used in a simple and coherent
way.
All the features included in the tool allow for an easy and powerful
examination
of the WAM.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
The SLAM project
Draft report on the SLAM language
SLAM is an object oriented formal specification language. The language
is the soul of a system that integrates all the stages in the
programming
process: analysis, design, implementation and validation. In other
words,
SLAM is designed
for the "specifying-in-the-large". SLAM is a notation with a
well-defined
formal semantics. It integrates algebraic specifications and
model-based
specifications using the object oriented model and abstract state
machines.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Towards Automating the Iterative Rapid
Prototyping
Process with the SLAM system
This paper shows the outlines of the SLAM project, designed for
automating
the Iterative Rapid Prototyping Process.
The SLAM project system includes a very expressive object oriented
specification language that integrates algebraic specifications
and model-based specifications. Class operations are defined by
using rules each of them with logical pre- and post-conditions but with
a functional flavour.
The main novel feature of the system is that contains a development
environment that, among other features, is able
to generate (reasonable) efficient and readable code in another
high level object oriented language (C++, Java, etc.). The
generated
code includes (part of) the pre- and post-conditions as assertions,
that
can be automatically checked in the
debug mode execution of programs.
SLAM can be used to generate prototypes that can be used to validate
the requirements with the user. The additional advantage is that the
prototype
is not throw-away because most part of the generated code can be
used at it is and the other part can be optimized with the additional
help
of the declarative debugging of the modified code.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Generation of and Debugging with Logical
Pre and
Post Conditions
This paper shows the debugging facilities provided by the SLAM
system.
The SLAM system includes i) a specification language that
integrates
algebraic specifications and model-based specifications using the
object oriented model. Class operations are defined by using
rules
each of them with logical pre and post-conditions but with a functional
flavour. ii) A development environment that, among other features, is
able
to generate readable code in a high level object oriented
language.
iii) The generated code includes (part of) the pre and post-conditions
as assertions, that can be automatically checked in the debug mode
execution
of programs.
We focus on this last aspect. The SLAM language is expressive
enough to describe many useful properties and these properties are
translated
into a Prolog program that is linked (via an adequate interface) with
the
user program. The debugging execution of the program interacts with the
Prolog engine which is responsible for checking properties.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
On the Role of Functional-logic Languages
for the
Debugging of Imperative Programs
The paper presents some aspects of the debugging subsystem of the
ongoing
project SLAM where the language Curry plays a significant role. The
SLAM
project is an attempt to amalgamate most of the best facilities
of
declarative languages to the development of imperative programs.
The SLAM system is composed by i) an object oriented specification
language.
(Functional style) Rules are used to define class operations each of
them
with logical pre and post-conditions. ii) A
development
environment that, among other features, is able to generate
readable
code in a high level object oriented (imperative) language. iii)
The generated code includes (part of) the pre and post-conditions as
assertions,
that can be automatically checked in the debug mode execution of
programs.
We concentrate on the latter aspect. Many useful properties can be
expressed
in the SLAM language and these properties are translated into a
Curry
program that is linked (via an adequate interface) with the
generated
program. The Curry execution is responsible for checking properties,
interacting
with the debugging execution of the program.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Negation and Inheritance in Logic Programming
On the Power of Inheritance in (Constraint) Logic Programming
In this paper, we present a new form of inheritance for (constraint)
logic
programming. This inheritance is informally defined in the following
terms:
a module inherits from the other one the definitions that are not
covered
by itself (with respect to fixed tuple of arguments). A computable
approximation
to this definition is studied. In particular, we define the declarative
semantics (based on Kunen's 3-valued semantics) and the operational
semantics
(based on constructive negation). Several examples showing the
usefulness
of the proposal are presented as well as some hints for the
implementation.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Technical Report version:
Reference LML-LSIIS-FIM/1/96
DVI,
PS,
ftp
(compressed postscript)
How to Incorporate Negation in a Prolog
Compiler
Knowledge representation based applications require a more complete set
of capabilities than those offered by conventional Prolog compilers.
Negation
is, probably, the most important one. The inclusion of negation
among
the logical facilities of LP has been a very active area of research,
and
several techniques have been proposed. However, the negation
capabilities
accepted by current Prolog compilers are very limited. In this
paper,
we discuss the possibility to incorporate some of these techniques in a
Prolog compiler in an efficient way. Our idea is to mix some of the
existing
proposals guided by the information provided by a global analysis of
the
source code.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)
Efficient Implementation of General
Negation Using
Abstract Interpretation
While negation has been a very active area of research in logic
programming,
comparatively few papers have been devoted
to implementation issues. Furthermore, the negation-related
capabilities
of current Prolog systems are limited. We recently
presented a novel method for incorporating negation in a Prolog
compiler
which takes a number of existing methods (some modified and improved)
and
uses them in a combined fashion. The method makes use of information
provided
by a global analysis of the source code. Our previous work focused on
the
systematic description of the techniques and the reasoning about
correctness
and completeness of the method, but provided no experimental evidence
to
evaluate the proposal. In
this paper, after proposing some extensions to the method, we provide
experimental data which indicates that the method is not only feasible
but also quite promising from the efficiency point of view. In
addition,
the tests have provided new insight as to how to improve the proposal
further.
Abstract interpretation techniques (in particular those included in
the CIAO Prolog system preprocessor) have had a significant role in the
success of the technique.
DVI,
Bib-Tex,
PS,
ftp
(compressed postscript)