Higher Order


Higher Order

There are two ways to include higher order in a functional logic language:

  1. Higher Order Functional Logic Programming with First Order Logical Variables
  2. Example

    We say that a list L is bounded by another list L' if we can get L by adding the same quantity to all the elements of L'.
    
         fun map : (A -> B) -> list A -> list B.
             map F [] = [].
             map F [X|Xs] = [ (F X) | (map F Xs) ].
    
         pred bounded_by : list nat * list nat.
             bounded_by Bigs Smalls :- (map (+ Offset) Smalls) = Bigs.
    
         solve bounded_by [1, Y] [X, 3].
    
         >   result: true  answer: X = 0, Y = 4.
         >   result: true  answer: X = 1, Y = 5.
         >   no (more) solutions.
    
    
    A more elaborated example of the expressivity of higher order features:

    Problem: Ranks

    Given a list Xs of integers, compute another list Ys of the same length, obtained by replacing each element X of Xs by its rank within Xs, defined as the number of elements less than X which occur in Xs (without counting repetitions). For instance, for Xs = [3,5,1,3,7,5,4] we get Ys = [1,3,0,1,4,3,2]. The program below constructs Ys by traversing Xs only once and consulting the ranks associated with the members of Xs in a tree structured dictionary. Since the dictionary is initially unknown, it has to be guessed by the predicate ranks_of. After this, the function ranks can traverse the given list and build the result list at the same time, by consulting the dictionary. Operationally, the computation can be described as follows. Before starting the traversal of the given list, the dictionary is an unbound logic variable, provided by the call to the ranks_of predicate. During the traversal, the dictionary gets narrowed to an incomplete data structure where the elements of the given list have been already inserted but their associated ranks are still unbound logic variables. Upon finishing the traversal, ranks calls the complete predicate, which completes the dictionary. Declaratively, the program states that any complete dictionary can be used by the function ranks for computing the result. From this point of view, the final call to complete merely checks that ranks_of has indeed guessed a complete dictionary. This is done by checking that the integer values associated to the keys in the dictionary are allocated in order (w.r.t. the ordering of keys), starting with value 0 and leaving some N as the first unused value.
    Try to solve it in your favourite language before you check the solution in a functional logic language

  3. Higher Order Logical Variables

  4. Higher Order - Implementation -

    Translation to PROLOG

    • Higher order facilities of functional logic languages can be simulated in PROLOG too.
    • The transformation follows the idea introduced by Warren 82 for coding higher order programming features into first order PROLOG.
      The idea is based on the first order axiomatization of the lambda-calculus
    • Ideal project Bosco, Giovanetti 86.
      As far as we know this is the only implementation of a functional logic language with higher order logical variables.

    Abstract Machine Implementation

    • An implementation of a functional logic language with higher order facilities but with first order logical variables is presented in Kuchen, Loogen, Moreno-Navarro, Rodríguez-Artalejo 90, 92.

    Go to index