Research Goal

Background Information

In order to first understand the workings of the functional logic language virtual machine, it is important to first understand some background of the functional logic programming languages. Functional logic programming aims at integrating in a single paradigm the characteristic features of functional and logic programming. It tries to add on three main features to typical functional programming which are: non-determinism, narrowing, and residuation. But to start out with, we should first look at the functional and logical programming languages to begin to understand what is characteristic about each of them.

Functional Programming

The basis of functional languages is to offer an alternative to the step by step imperative languages that we may be used to. Typical examples of imperative languages are C, Java, Pascal, etc. where the programs are a series of instructions expected to be executed in order. A functional language instead is evaluated as an expression that does not put restrictions on the order of execution, except in regards to dependancies that need to be used within an expression. Another way to think about it is from an example given at http://www.haskell.org/aboutHaskell.html. If we considered a spreadsheet, many of the columns in our spreadsheet may not be concrete values themselves, but formulas that rely on values from other cells. The importance is not in how the spreadsheet calculates the end results, but just that they are correct when finished. The sequence of calculations is up to the spreadsheet, as the data is provided.

Other great examples and more information can be found at:

• http://www.haskell.org
• http://www.wikipedia.org/wiki/Functional_programming
• Haskell Tutorial

Logic Programming

Logic programming in contrast has a very different method of evaluation. Logic programming specifies some properties that a solution should have for a valid answer. By specifying the properties, the interpreter will execute the given set of facts, and verify whether or not amongst those facts, there are any answers that meet the properties specified. A classic example of a logical programming language would be Prolog. In Prolog, a program would consist of a set of predicates that represent facts, and rules for interpreting those predicates.

Example

In Prolog, the basic unit is a predicate, such as:

    parent(bill, steve).

This predicate is considered to be true, although it does not have defined behavior yet. What I mean by defined behavior, is that the two elements bill and steve are in a fixed order parent relationship, but it is not stated here which one is the parent. If we enter the goal: parent(bill, steve). the interpreter will return yes, because that is how we defined the predicate. If we changed the order and entered the goal: parent(steve, bill). the interpreter will return no, as expected since that is not the predicate we specified. But if we wanted to change this in order to define who is the parent in a relationship, we must also define a rule for the relationship of the parent.

Here, we will use par to represent the rule to define a parent relationship. If we want to define the parent relationship to mean that the second person is the parent of the first, which in our example would mean that steve is a parent of bill, then we would define the rule par as such:

    par(X):-parent(X, Y).

By defining the par rule using the variables X, and Y, we are looking to see if for any person that we enter into par as a goal, if there is a Y that exists to satisfy the relationship. In other words, if we enter the goal: par(bill) the interpreter will return yes because bill does exist in a relationship with steve, where steve satisfies the variable Y in our search to see if bill has a parent. However, if we searched using par(steve). as a goal, this would return no, because we defined the relationship to only be valid as the second person being the parent of the first.

The advantage that we would like to utilize from this logic programming model is the ability to have a non-deterministic search technique. Non-determinism allows us to have more than one possible relationship that could satisfy our goal. For our example, you could think of this as bill having both a father and mother that could satisfy our rule par, and to the interpreter either answer is sufficient.

Functional Logic Programming

Now that we have looked at functional and logic languages, it gives us a basis to understand what we are capable of with a functional logic language. It should provide the ability to incorporate the expressiveness of a functional language, with the non-determinism of a logic language. Additionally, it will use narrowing and residuation to allow complex expressions to be broken down and simplified for computation. One example of a functional logic language is Curry. It is not necessary to understand functional logic languages in order to understand the working of the vitual machine, however, it may be useful in understanding some examples presented. If you would like to get a better feel for functional logic languages, it might be helpful to look over a tutorial on Curry.

The main features that allow for the non-deterministic abilities to be appreciated for Curry are equational constraints, concurrent conjuctions, and existential quantification. Included below is an explanation of each of these three concepts, and how non-determinism is used in them.

Equational Constraint

Equational constraint is a feature to the functional logic languages that returns values from a pair of expressions that are reducible to the same ground data term. For a simple example of this, first lets suppose we have a function that returns a fixed set of numbers. A simple example is a function one23 that returns a 1, 2, or 3 (for the 3 line code example of one23, look at page 10 of the Curry tutorial). If then we want to see what is returned from another function, that is within the domain we have specified. We could use the equational constraint to do just that. Now if we had another function that returned values from 2 to 5, we could find the intersection of the two functions though the use of the equational constraint. Lets say that our function returning numbers from 2 to 5 is named similar to our first example, two345. The code for our equational constraint would be:

    one23 =:= two345

Since the values returned for both sides must be equivalent, the result from both equations combined with the equational constraint would be 2 and 3. While this is a simple example, it gives a small illustration of how our non-determinism can be utilized in combination with constraints to obtain a result, without having multiple lines of code to compare a set of all possible answers from each expression. Instead, the philosophy is to let the machine do the work of calculate and compare, while we are more interested with the results.

Concurrent Conjuction

The concurrent conjunctiion is rather similar to the equational constraint concept, but has a primary difference to consider. The equational constraints have a notion of equality that can be satisfied if both sides are reducible to the same ground data term. This leads to a potential that one side could be undefined (nonterminating), which would not allow for the equality to be satisfied. This condition would cause the strict equality to not hold for the two expressions. Alternatively, concurrent conjuction allows for the evaluation of terms concurrently. Concurrent conjuction which is of the form,

    e1 & e2

allows the expressions to be evaluated together. For example, if the execution of e₁ suspends, the evaluation of e₂ can proceed which may cause the reactivation of e₁ at some point. The expression may then be solvable due to the binding of common variables. The seperation of sequential (non-concurrent) and concurrent computations allows the use of efficient evaluation strategies for the sequential computations, where similar techniques for the concurrent parts are not available. The use of the concurrent evaluations though, gives us greater expressive power for our computations. For an example of this that combines the use of equational constraing with concurrent conjuction, we'll once again look at an example from the Curry tutorial. Our expressions will also contain a free variable X in them. The complete expression and results are:

choose> X=:=one23 & X+X=:=X*X
Free variables in goal: X
Result: success
Bindings:
X=2 ?

The execution of this example requires the computation of both sides of the concurrent conjuction to produce the results. Since X is bound to 1,2, or 3 by the first equational constraint, that is necessary for the computation of X in the second equational constraint. The second set of expressions can then compute to see for what values of X that X+X=:=X*X. Which obviously the only value of X from 1 to 3 that satisfies that equality is 2, so the result is success when X is bound to that. This gives a basic example of the goal for functional languages. Where we can use constraints to define properties that a valid solution will have, along with the expressiveness of the functional languages.

Existential Quantification

Existential Quantification should be a rather easy topic to understand in comparison. It is the ability to qualify free variables in an expression. For example, a function definition that we will use later is palind (that determines if an odd length string is a palindrome), and is defined as follows:

    palind s = s =:= x ++ y : rev x where x, y free

By defining x and y free, they are non-deterministic since they can be bound to any values. The one main thing to remember though, is although they are free, multiple occurences of the same variable in the same expression must be bound to the same values. Therefore, x must be the same value at both occurences, but that value is free to be determined non-deterministically. With the equational constraint used in here as well, the values that they take on must be reducible to the same base terms that s contains, and so they are constrained in that aspect, but in regards to themselves, they are not set values. This is a quick example of how existential quantification might be used, and where it comes in handy.

The more practice you get with a functional logic language will of course allow you to have a better understanding of how functional logic languages work, but this is sufficient for now to discuss the need for operationally complete non-determinism in the virtual machine.