Functional Logic Programming


Sergio Antoy
ACM Student Chapter talk
Wed. May 12th, 2004

Overview

  1. the calculator metaphor
  2. defining functions
  3. defining types
  4. laziness
  5. non-determinism
  6. solving equations
  7. programming
  8. conclusion
  9. links

The calculator metaphor

Functional logic computations can be executed using an interpreter that prompts for an expression to evaluate

    [antoy@localhost acm-students]$ pakcs
    ...
    Type ":h" for help
   
    prelude> 2+3*4
    Result: 14 ? user presses enter key
    prelude>

The interpreter knows about the integers and other familiar types and their most common operations. These are defined in a module or library knows as the prelude (like the java.lang package).

Defining functions

Functions and types not found in the prelude can be coded by the user in a file. The file is loaded by the interpreter which then knows about these functions and types. Suppose this is the content of the file aver.curry:

    average x y = (x+y) `div` 2

The user can load the file and execute the functions it defines.

    prelude> :l aver
    aver> average 234 66
    Result: 150 ? user presses enter key
    aver>

Notice that function are applied to arguments by juxtposition. Function application is almost all one can do in these languages, thus the notation is the simplest possible. A convenient feature for defining functions is pattern matching. A pattern is sort of an example of what the argument of a function may look like. The pattern avoids if or switch statements.

    not True  = False
    not False = True

Defines the Boolean not operation (both the Booleans and not are defined in the prelude).

Laziness

An expression can be infinite as long as only a finite portion of the expression is used. Lists have a special notation for ease of use. The empty list is [], the list with head h and tail t is denote h:t. E.g, compute the n-th Fibonacci number.

    allFibo = fiboList 0 1
        where fiboList x y = x : fiboList y (x+y)
    fibo n = nth n allFibo

The expression allFibo is the infinite sequence of the Fibonacci numbers: 0,1,1,2,3,5,8,... The function nth, defined in the prelude, returns the n-th element of a list. Laziness promotes reusability and simplicity. Without it, the code for computing a structure and the code for using the structure may have to be combined.

Defining types

User-defined types are declared by enumerating the possible forms that instances can take. Below is the definition of the type binary tree of integers.

    data IBTree = Leaf | Branch Int IBTree IBTree

    -- an instance of IBTree
    mytree = Branch 7 (Branch 5 Leaf Leaf) Leaf

A tree is either a leaf or a branch consisting of an integer (generally referred to as the decoration) and two trees (generally referred to as the left and right children). Pattern matching is very convenient for user defined types.

    -- add together all the decorations of a tree
    addAll Leaf = 0
    addAll (Branch i l r) = addAll l + i + addAll r

    -- count how many decorations are in a tree
    countAll Leaf = 0
    countAll (Branch i l r) = countAll l + 1 + countAll r

    -- find if a decoration is in in a tree
    isIn _ Leaf = False
    isIn n (Branch i l r) = n==i || isIn n l || isIn n r

    -- average value of the decorations of in a tree
    treeAver t = addAll t `div` countAll t   -- watch out

Types, including user-defined, can be polymorphic. e.g., list and trees are. Some functions on these types are polymorphic as well, e.g., countAll. Others, such as addAll, are specialized.

Non-determinism

One can define functions (including constants) that return distinct results for the same arguments

    coin = 0
    coin = 1

The constant coin has two distinct values, 0 and 1. Well-used non-determinism "programs for you" if you make non-deterministic choices and constrain them for a purpose. E.g., a hospital information system may find an available doctor as follows:

    oncall Joan = Monday
    oncall Joan = Tuesday
    oncall Richard = Monday
    oncall Luc = Wednesday
    ...

Suppose that today is a variable holding the day of the week.  The function available tells whether its argument is an available doctor at the time of the call.

    available x = oncall x =:= today

Solving equations

A major feature of functional logic languages is the ability to evaluate an expression containing variables. It is interesting to do so when the expression is an equation. The variables get values that solves the equation. As an example, consider the operation ++, list concatenation, defined by the prelude.

    prelude> X++[3,4]=:=[1,2,3,4]
    Free variables in goal: X
    Result: success
    Bindings:
    X=[1,2] ? user presses enter key
    prelude>

The value of the expression is success and the variable X is bound to [1,2].  An equation may have more than one solution. Solutions are computed non-deterministically.

    prelude> X++Y=:=[1,2,3,4]
    Free variables in goal: X, Y
    Result: success
    Bindings:
    X=[]
    Y=[1,2,3,4] ? ;
    Result: success
    Bindings:
    X=[1]
    Y=[2,3,4] ? ;
    Result: success
    Bindings:
    X=[1,2]
    Y=[3,4] ? ;
    Result: success
    Bindings:
    X=[1,2,3]
    Y=[4] ? ;
    Result: success
    Bindings:
    X=[1,2,3,4]
    Y=[] ? ;
    No more solutions.
    prelude>

The mechanism for solving equations is called narrowing and it is the subject of active research.

Programming

Example 1. Find if a poker hand scores four-of-a-kind.

    data Card = Card Rank Suit
    data Suit = Club | Spade | Heart | Diamond
    data Rank = Ace | King | Queen | Jack  ...
    rank (Card r _) = r

    fourOfAKind hand | hand =:= x++y:z & map rank (x++z) =:= [r,r,r,r]
                     = r
                     where x,y,z,r free
Example 2. Color a map of the Pacific NW states so that adjacent states have different colors.

    data State = WA | OR | ID | BC
    data Color = Red | Green | Blue
   
    states = [WA,OR,ID,BC]
   
    adjacent = (BC,ID)
    adjacent = (BC,WA)
    adjacent = (ID,OR)
    adjacent = (ID,WA)
    adjacent = (OR,WA)
   
    pick = Red
    pick = Green
    pick = Blue
  
    solve | colored =:= map (\x -> (x,pick)) states
          & wrong colored =:= []
          = colored
      where colored free
            wrong colored = findall (\_ -> let u,v,w,s1,s2,c free
                                           in adjacent =:= (s1,s2) &
                                              colored =:= u++(s1,c):v++(s2,c):w)

Conclusion

Functional logic programming is an interesting paradigm that supports terse code and elegant algorithms. It is the subject of active research on theoretical foundations, design and implementation of new languages. PSU has received various grants
for a total of about $600K to study non-determinism, narrowing, and the implementation of a Virtual Machine for functional logic computations.

Two virtual machines are being implemented concurrently at PSU, one in Java and one in ML. Several students have contributed substantially to the Java implementation, in particular Stephen Johnson, Jimeng Liu and Jason Wilcox.

Links

Sergio Antoy: http://www.cs.pdx.edu/~antoy
Research: http://www.cs.pdx.edu/~antoy/research/index.html
Virtual Machine: http://redstar.cs.pdx.edu/~antoy/flp/vm
Curry: http://www.informatik.uni-kiel.de/~curry/
Pakcs: http://www.informatik.uni-kiel.de/~pakcs/