Sergio Antoy

LOPSTR Conference 2016 Conference Paper

A New Functional-Logic Compiler for Curry: Sprite

• Sergio Antoy
• Andy Jost

Abstract We introduce a new native code compiler for Curry codenamed Sprite. Sprite is based on the Fair Scheme, a compilation strategy that provides instructions for transforming declarative, non-deterministic programs of a certain class into imperative, deterministic code. We outline salient features of Sprite, discuss its implementation of Curry programs, and present benchmarking results. Sprite is the first-to-date operationally complete implementation of Curry. Preliminary results show that ensuring this property does not incur a significant penalty.

LOPSTR Conference 2015 Conference Paper

Compiling Collapsing Rules in Certain Constructor Systems

• Sergio Antoy
• Andy Jost

Abstract The implementation of functional logic languages by means of graph rewriting requires a special handling of collapsing rules. Recent advances about the notion of a needed step in some constructor systems offer a new approach to this problem. We present two results: a transformation of a certain class of constructor-based rewrite systems that eliminates collapsing rules, and a rewrite-like relation that takes advantage of the absence of collapsing rules. We formally state and prove the correctness of these results. When used together, these results simplify without any loss of efficiency an implementation of graph rewriting and consequently of functional logic computations.

LOPSTR Conference 2015 Conference Paper

From Boolean Equalities to Constraints

• Sergio Antoy
• Michael Hanus

Abstract Although functional as well as logic languages use equality to discriminate between logically different cases, the operational meaning of equality is different in such languages. Functional languages reduce equational expressions to their Boolean values, True or False, logic languages use unification to check the validity only and fail otherwise. Consequently, the language Curry, which amalgamates functional and logic programming features, offers two kinds of equational expressions so that the programmer has to distinguish between these uses. We show that this distinction can be avoided by providing an analysis and transformation method that automatically selects the appropriate operation. Without this distinction in source programs, the language design can be simplified and the execution of programs can be optimized. As a consequence, we show that one kind of equational expressions is sufficient and unification is nothing else than an optimization of Boolean equality.

LOPSTR Conference 2013 Conference Paper

Compiling a Functional Logic Language: The Fair Scheme

• Sergio Antoy
• Andy Jost

Abstract We present a compilation scheme for a functional logic programming language. The input program to our compiler is a constructor-based graph rewriting system in a non-confluent, but well-behaved class. This input is an intermediate representation of a functional logic program in a language such as Curry or \(\mathcal{TOY}\). The output program from our compiler consists of three procedures that make recursive calls and execute both rewrite and pull-tab steps. This output is an intermediate representation that is easy to encode in any number of programming languages. We formally and tersely define the compilation scheme from input to output programs. This compilation scheme is the only one to date that implements a deterministic strategy for non-deterministic computations with a proof of optimality and correctness.

LOPSTR Conference 2005 Conference Paper

Declarative Programming with Function Patterns

• Sergio Antoy
• Michael Hanus

Abstract We propose an extension of functional logic languages that allows the definition of operations with patterns containing other defined operation symbols. Such “function patterns” have many advantages over traditional constructor patterns. They allow a direct representation of specifications as declarative programs, provide better abstractions of patterns as first-class objects, and support the high-level programming of queries and transformation of complex structures. Moreover, they avoid known problems that occur in traditional programs using strict equality. We define their semantics via a transformation into standard functional logic programs. Since this transformation might introduce an infinite number of rules, we suggest an implementation that can be easily integrated with existing functional logic programming systems.

LOPSTR Conference 2000 Conference Paper

Measuring the Effectiveness of Partial Evaluation

• Elvira Albert
• Sergio Antoy
• Germán Vidal

TCS Journal 1996 Journal Article

A sequential reduction strategy

• Sergio Antoy
• Aart Middeldorp

Kennaway proved the remarkable result that every (almost) orthogonal term rewriting system admits a computable sequential normalizing reduction strategy. In this paper we present a computable sequential reduction strategy similar in scope, but simpler and more general. Our strategy can be thought of as an outermost-fair-like strategy that is allowed to be unfair to some redex of a term when contracting the redex is useless for the normalization of the term. Unlike the strategy of Kennaway, our strategy does not rely on syntactic restrictions that imply confluence. On the contrary, it can easily be applied to any term rewriting system, and we show that the class of term rewriting systems for which our strategy is normalizing properly includes all (almost) orthogonal systems. Our strategy is more versatile; in case of (almost) orthogonal term rewriting systems, it can be used to detect certain cases of non-termination. Our normalization proof is more accessible than Kennaway's. We also show that our sequential strategy sometimes succeeds where the parallel-outermost strategy fails.

LOPSTR Conference 1992 Conference Paper

Non-Determinism and Lazy Evaluation in Logic Programming

• Sergio Antoy

Abstract We propose a transformation of term rewriting systems in logic programs. The systems we consider may be non-confluent and/or non-terminating. The programs we generate compute lazily. Our approach is based on a generalization of the concept of definitional trees. We propose an algorithm for code generation and discuss code optimization. We present a benchmark comparing the efficiency of various approaches to program design. We address the adequacy of Prolog to interpret the generated programs. We characterize a situation in which non-determinism and lazy evaluation do not mix well. We show the application of our ideas to two simple, but non-trivial problems.