Functions and Nested Calls

Functions and Composition

• Functions are defined by program rules:
  They establish when a function call is equal to another expression.
  => Definition of the equality predicate "=". Semantic equality.
  Equality in PROLOG => syntactic identity,
  

  fun append: list A -> list A -> list A.
      append [] L = L.
      append [X | Xs] L = [X | append Xs L].
  

  The method is exactly the same that one can found in modern functional programming languages (ML, Miranda, Haskell, etc.).

• Conditional equations to define functions.
  Condition: any user defined or predefined predicate (for instance, the equality).
  

  type signs = positive | zero | negative.
  
  fun sign: int -> signs.
      sign X = (X > 0) => positive.
      sign X = (X = 0) => zero.
      sign X = (X < 0) => negative.
  

• The condition can include new logical variables -- extra variables, that are not present in the formal parameters --, in order to keep the facilities of logic programming.
  These variables are implicitly existentially quantified
  => Search for adequate values for them during the computation.
  

  fun last : list A -> A.
      last L = (append _ [X]) = L => X.
  
  eval last [2, Z, 6].
  >    result: 6.
  

• Additional requirement for a function definition
  => Nonambiguity condition: the rules must define a function in the mathematical sense giving at most one result for ground arguments.
  Ensured by:
  • Syntactical restrictions on the program (as in K-LEAF or BABEL)
  • the user
  • the implementation using a priority order for the rules in case of ambiguity.
• Nested function and predicate calls in any consistent way. Example: Decide if a list is a sublist of another one.

  fun sublist: list A -> list A -> bool.
      sublist L1 L2 = L2 = (append X (append A Y)).
  

• Predicates:
  Two alternative views:
  • Function rules are Horn clauses defining the predicate "=". Horn clauses can still be used to specify different predicates.
  • Predicates as boolean functions returning only the value true.
  
  We use PROLOG syntax for predicate definitions.

  p t1 . . . tN = true.               p (t1, . . ., tN).
  p t1 . . . tN = C => true.          p (t1, . . ., tN) :- C.
  
  eval p t1 . . . tN => true          solve p (t1, . . ., tN).
  

• Backtracking: The narrowing rule is usually implemented in a depth-first fashion and failures are handled by backtracking.

Expressivity of Functions and Nested Calls

• When to use a function or a predicate to define a problem entity?

  Usually a matter of taste.

  Our definition of expressivity prefers the use of functions to define functions and the use of predicates to define predicates.

  It is not a clear source of expressivity.

• Where does the increment of expressivity come?

  The possibility of making nested calls.

  Cleaner and clearer programs if the level of nesting is high.

  Easier to understand than PROLOG programs.

  Composed or modal knowledge.

  The functional structure of the program makes also easier a static analysis of the program, what it is very useful from the implementation point of view.

Once the hatter expressed his believe that the hare does not believe that all three (the hatter, the hare and the dormouse) are sane. The dormouse also believes that the hare is sane. What is the mental state of these three friends?. (One accepts that sane people tell the truth while mad people always lie).

Narrowing strategy

• Innermost narrowing have been defined in several places and it has been proved to be complete Fribourg 84.
• The early implementations of functional logic languages were based on interpreters written usually in PROLOG:
  RAP Hussmann 86
  LPG Bert, Echahed 86
  SLOG Fribourg 84, 85
  
• More elaborated implementation:

  Compiling the functional logic language into a high level language

  The language is usually PROLOG.
  

  • Functions are compiled into predicates with an extra argument to represent the result.
  • Nested function calls are managed by flattening: logical variables are used to connect a the result of an expression with the place it is used.
  • The order in which the flatten predicates are located modifies the evaluation order.
  • Innermost evaluation: compilation of arguments before the function that uses them - Bosco, Giovanetti 88, van Emden, Yukawa 87.

  Best performance: Compiling the functional logic language into a low-level abstract machine, designed to be efficiently implemented on conventional hardware.

  Abstract Machine Implementation

  Two alternatives:

  • Modify a logic programming machine (the WAM).
    Done: Logical variables, unification and backtracking
    To add: Function applications.
    A-WAM Hanus90
    Mück 90
    FLANG implementation, Mantsivoda 91, 93

  • Extend a functional programming implementation
    Done: Function application, higher order, matching
    To add: Logical variables, backtracking
    • Matching -> Unification.
    • Basic data structure:
      • Graph as the basic data structure.
        Very simple and easier to parallelize.
        BAM Kuchen, Loogen, Moreno-Navarro, Rodríguez-Artalejo 90, 92
      • Stack as the basic data structure.
        More efficient.
        SBAM Loogen 91
        JUMP machine (modification of the spineless tagless G-machine) Chakravarty, Lock 91
        CAMEL (extension of the fully verified Categorical Abstract Machine) Mück 92
        

  Although both approaches seem to be different, in practice they converge to very similar solutions.

  Current implementations are highly competitive with Prolog implementations.

  Efficiency of functional logic programs is often better than their Prolog equivalents when the functional structure of the program is used.

  One possible optimization is the detection of deterministic computations.

  The implementation can detect that a function call can only return a single result. In such this situation backtracking is not needed and no more rules are tried after a success in case of failure.

  => Implicit cut is inserted before the code for the left hand side of the rule.

  Speedups reported in Bosco, Cechi, Moiso 89, Kuchen, Loogen, Moreno-Navarro, Rodríguez-Artalejo 92, Loogen 91

  ---

  Go to index