The ALF System

ALF is a language which combines functional and logic programming techniques. The foundation of ALF is Horn clause logic with equality which consists of predicates and Horn clauses for logic programming, and functions and equations for functional programming. Since ALF is a genuine integration of both programming paradigms, any functional expression can be used in a goal literal and arbitrary predicates can occur in conditions of equations. The operational semantics of ALF is based on the resolution rule to solve literals and narrowing to evaluate functional expressions. In order to reduce the number of possible narrowing steps, a leftmost-innermost basic narrowing strategy is used which can be efficiently implemented. Furthermore, terms are simplified by rewriting before a narrowing step is applied and also equations are rejected if the two sides have different constructors at the top. Rewriting and rejection can result in a large reduction of the search tree. Therefore this operational semantics is more efficient than Prolog's resolution strategy.

The ALF system is an efficient implementation of the combination of resolution, narrowing, rewriting and rejection. Similarly to 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. The abstract machine is based on the Warren Abstract Machine (WAM) with several extensions to implement narrowing and rewriting. In the current implementation programs of this abstract machine are executed by an emulator written in C.

A detailed user manual describing the language and the use of the system ALF is available.

You can get the ALF System for free, but if you take the system it is assumed that you agree with the license agreement. It would be nice if you send us your name, institution and email address so that we can inform you about updates and other things concerning the ALF system.

More information about getting and installing the ALF system can be found >here<.

Contact person: Michael Hanus


Publications Related to the ALF System

ALF User's Manual (with Andreas Schwab)
Available: PDF

Compiling Logic Programs with Equality
2nd International Workshop on Programming Language Implementation and Logic Programming (PLILP'90), Springer LNCS 456, pp. 387-401, 1990
Available: Abstract PDF BibTeX-Entry

Efficient Implementation of Narrowing and Rewriting
International Workshop on Processing Declarative Knowledge (PDK'91), Springer LNAI 567, pp. 344-365, 1991
Available: Abstract PDF BibTeX-Entry

Improving Control of Logic Programs by Using Functional Logic Languages
4th International Symposium on Programming Language Implementation and Logic Programming (PLILP'92), Springer LNCS 631, pp. 1-23, 1992
Available: Abstract PDF BibTeX-Entry

Incremental Rewriting in Narrowing Derivations
3rd International Conference on Algebraic and Logic Programming (ALP'92), Springer LNCS 632, pp. 228-243, 1992
Available: Abstract PDF BibTeX-Entry

A Debugging Model for Functional Logic Programs (with Berthold Josephs)
5th International Symposium on Programming Language Implementation and Logic Programming (PLILP'93), Springer LNCS 714, pp. 28-43, 1993
Available: Abstract PDF BibTeX-Entry

Towards the Global Optimization of Functional Logic Programs
5th International Conference on Compiler Construction (CC'94), Springer LNCS 786, pp. 68-82, 1994
Available: Abstract PDF BibTeX-Entry

Mode Analysis of Functional Logic Programs (with Frank Zartmann)
1st International Static Analysis Symposium (SAS'94), Springer LNCS 864, pp. 26-42, 1994
Available: Abstract PDF BibTeX-Entry

Michael Hanus