[From the manual]

Rudolf  Opalla
Fachbereich Informatik
Universitaet Dortmund
W-4600 Dortmund 50, Germany
opalla@ls5.informatik.uni-dortmund.de


ALF (Algebraic Logic Functional programming language) 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 effici ently 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.  ALF  has  also  a  type  and  module  concept  which  allows  
the  definition  of  generic  modules.  A preprocessor checks the type 
consistence of the program and combines all needed modules into one flat-ALF  
program  which  is  compiled  into  a  compact  bytecode  representing an  
abstract  machine program.  The current implementation has the following 
properties:

       o  The machine code for pure logic programs without defined functions is 
identical to the code of  the  original  WAM  [War83],  i.e.,  for  logic  
programs  there  is no  overhead  because  of  the functional part of the 
language.

     o  Functional programs where only ground terms have to be evaluated are 
executed by deterministic rewriting without any dynamic search for subterms 
positions where the next rewriting step can be applied.  The compiler computes 
these positions and generates particular machine instructions.  Therefore such 
programs are also efficiently executed.

     o  In  mixed  functional  and  logic  programs  argument  terms  are  
simplified  by  rewriting  before narrowing is applied and therefore function 
calls with ground arguments are automatically evaluated  by  rewriting  and  
not  by  narrowing.   This  is  more  efficient  because  rewriting  is a  
deterministic  process.   Hence  in  most  practical  cases  the  combined  
rewriting/narrowing implementation  is  more  efficient  than  an  
implementation  of  narro wing  by  flattening  terms and applying SLD-
resolution [Han91].