ALF(ID:1804/alf001)

for Algebraic Logic Functional language

Michael Hanus Uni of Kiel 1990

A language which combines functional and logic programming techniques.

ALF is a functional logic language whose operational semantics is based on innermost narrowing with normalization. Its implementation is based on an extension of the WAM.


Structures:
Related languages
coq => ALF   Based on
References:
  • Hanus, M. and Schwab, A. "The Implementation of the Functional-Logic Language ALF" view details Extract: Introduction
    A language which combines functional and logic programming techniques. The foundation of ALF is Horn logic with equality which consists of predicates and Horn clauses for logic programming, and functions and equations for functional programming.  The operational semantics of ALF is based on the resolution rule to solve literals and narrowing to evaluate functional expressions.  The ALF system is an efficient implementation of the combination of resolution, narrowing, rewriting, and rejection. Similar to PROLOG, ALF uses a backtracking strategy corresponding to a depth-first search in the derivination tree. Therefore this operational semantics is more efficient than PROLOG's resolution strategy.

    ALF (Algebraic Logic/Functional programming language) is a programming language that combines functional and logic programming techniques. ALF is based on Horn clause logic with equality. Predicates and Horn clauses are used for logic programming, and functions and equations for functional programming. Any functional expression can be used in a goal literal, and any predicate can occur in the conditions of an equation.

    The ALF system is implemented using a combination of resolution, narrowing, rewriting and rejection. The resolution rule is used to solve literals and narrowing to evaluate functional expressions.  The number of possible narrowing steps is reduced by a leftmost-innermost basic narrowing strategy, and terms are simplified by rewriting before narrowing is applied.  Equations are also rejected if the two sides have different constructors at the top.  Rewriting and rejection can result in a large reduction of the search tree.  Thus the operational semantics of ALF is more efficient than Prolog's resolution strategy.

    Like Prolog, ALF uses a backtracking strategy corresponding to a depth-first search in the derivation tree.  ALF programs are compiled into instructions of an abstract machine based on the Warren Abstract Machine (WAM) with several extensions to implement narrowing and rewriting. The emulator for A-WAM programs is written in C.
  • Hanus, Michael "Compiling Logic Programs with Equality" view details Abstract: Horn clause logic with equality is an amalgamation of functional and logic programming languages. A sound and complete operational semantics for logic programs with equality is based on resolution to solve literals, and rewriting and narrowing to evaluate functional expressions. This paper proposes a technique for compiling programs with these inference rules into programs of a low-level abstract machine which can be efficiently executed on conventional architectures. The presented approach is based on an extension of the Warren abstract machine (WAM). In our approach pure logic programs without function definitions are compiled in the same way as in the WAM-approach, and for logic programs with function definitions particular instructions are generated for occurrences of functions inside clause bodies. In order to obtain an efficient implementation of functional computations, a stack of occurrences of function symbols in goals is managed by the abstract machine. The compiler generates the necessary instructions for the efficient manipulation of the occurrence stack from the given equational logic program.


          in 2nd International Workshop on Programming Language Implementation and Logic Programming (PLILP'90), Springer LNCS 456, 1990 view details
  • Hanus, Michael "Efficient Implementation of Narrowing and Rewriting" pp344-365 view details Abstract: We present an efficient implementation method for a language that amalgamates functional and logic programming styles. The operational semantics of the language consists of resolution to solve predicates and narrowing and rewriting to evaluate functional expressions. The implementation is based on an extension of the Warren Abstract Machine (WAM). This extension causes no overhead for pure logic programs and allows the execution of functional programs by narrowing and rewriting with the same efficiency as their relational equivalents. Moreover, there are many cases where functional programs are more efficiently executed than their relational equivalents.
          in 2nd International Workshop on Programming Language Implementation and Logic Programming (PLILP'90), Springer LNCS 456, 1990 view details
  • Hanus, Michael "Improving Control of Logic Programs by Using Functional Logic Languages" pp1-23 view details Abstract: This paper shows the advantages of amalgamating functional and logic programming languages. In comparison with pure functional languages, an amalgamated functional logic language has more expressive power. In comparison with pure logic languages, functional logic languages have a better control behaviour. The latter will be shown by presenting methods to translate logic programs into a functional logic language with a narrowing/rewriting semantics. The translated programs produce the same set of answers and have at least the same efficiency as the original programs. But in many cases the control behaviour of the translated programs is improved. This requires the addition of further knowledge to the programs. We discuss methods for this and show the gain in efficiency by means of several examples.
          in 4th International Symposium on Programming Language Implementation and Logic Programming (PLILP'92), Springer LNCS 631, 1992 view details
  • Hanus, Michael "Incremental Rewriting in Narrowing Derivations" pp228-243 view details Abstract: The operational semantics of many proposals for the integration of functional and logic programming languages is based on narrowing. In order to reduce the search space and to prefer deterministic computations, the goal is rewritten to normal form between narrowing steps (normalizing narrowing). This rewriting process may be costly since the entire goal must be reduced to normal form after each narrowing step. We propose a useful optimization of the rewriting process: since the goal is in normal form before the narrowing step is applied and the narrowing step changes only small parts of the goal, rewriting can be restricted to a small number of positions in the narrowed goal in order to compute a new normal form. This optimization can speed up the execution mechanism of programming languages based on normalizing narrowing like SLOG or ALF.
          in Narrowing Derivations 3rd International Conference on Algebraic and Logic Programming" (ALP'92), Springer LNCS 632, 1992 view details
  • Hanus, Michael and Berthold Josephs "A Debugging Model for Functional Logic Programs" pp28-43 view details Abstract: This paper presents a box-oriented debugging model for the functional logic language ALF. Due to the sophisticated operational semantics of ALF which is based on innermost basic narrowing with simplification, the debugger must reflect the application of the different computation rules during program execution. Hence our debugging model includes not only one box type as in Byrd's debugging model for logic programs but several different kinds of boxes corresponding to the various computation rules of the functional logic language (narrowing, simplification etc.). Moreover, additional box types are introduced in order to allow skips over (sometimes) uninteresting program parts like proofs of the condition in a conditional equation. Since ALF is a genuine amalgamation of functional and logic languages, our debugging model subsumes operational aspects of both kinds of languages. As a consequence, it can be also used for pure logic languages, pure functional languages with eager evaluation, or functional logic languages with a less sophisticated operational semantics like SLOG or eager BABEL.
          in 5th International Symposium on Programming Language Implementation and Logic Programming (PLILP'93), Springer LNCS 714, 1993 view details
  • Hanus, Michael "Towards the Global Optimization of Functional Logic Programs" pp68-82 view details Abstract: Functional logic languages amalgamate functional and logic programming paradigms. They can be efficiently implemented by extending techniques known from logic programming. In this paper we show how global information about the call modes of functions can be used to optimize the compilation of functional logic programs. Since mode information has been successfully used to improve the implementation of pure logic programs and these techniques can be applied to implementations of functional logic programs as well, we concentrate on optimizations which are unique to the operational semantics of functional logic programs. We define a suitable notion of modes for functional logic programs and present compile-time techniques to optimize the normalization process during the execution of functional logic programs.
          in Compiler Construction '94. (Proc. 5th Intl. Conf. on Compiler Construction, Edinburgh, 1994) (CC'94) ed P.A. Fritzson, LNCS786 Springer Verlag view details
  • Hanus, Michael and Frank Zartmann "Mode Analysis of Functional Logic Programs" pp26-42 view details Abstract: Functional logic languages amalgamate functional and logic programming paradigms. They can be efficiently implemented by extending techniques known from logic programming. Such implementations can be largely improved if information about the run-time behavior, in particular the modes of function calls, is available at compile time. In this paper we present a framework to derive such global information. The concrete operational semantics considered in this paper is normalizing innermost narrowing, which combines the deterministic reduction principle of functional languages with the nondeterministic search principle of logic languages. Due to the normalization process between narrowing steps, standard analysis frameworks for logic programming cannot be applied. Therefore we develop new techniques to correctly approximate the effect of the intermediate normalization process.

          in Proceedings of the 1st International Static Analysis Symposium (SAS'94), Springer LNCS 864, 1994 view details
    Resources