Functional Action Language (FAL)

The Functional Action Language (FAL) is thought for describing constraint satisfaction problems that may involve temporal reasoning about actions and change. A problem is expressed in terms of a set of functions and a set of rules that establish the relation among values for those functions. Each solution to the problem is a possible assigment of function values that "agrees" with the set of rules.

Syntactically, FAL is very close to languages from Functional Logic Programming. Rules have a Prolog-style form like, for instance:

mother(X,Y) :- parent(X,Y), female(Y).

to be read as: "Y is X's mother if Y is one of X's parents and Y is female". As in Prolog, identifiers beginning with a capital letter, like X or Y, represent variables. The main difference with respect to Prolog is the posibility of referring to funcion values in place of predicate atoms. As an example, since there (usually) exists a unique mother, we could represent mother(X) as a function, rather than as a binary predicate:

mother(X)=Y :- parent(X,Y), female(Y).

But the most interesting advantage of using functions is, of course, that they can be nested as arguments of other functions or expressions. As an example, consider the rule:

Currently, the only FAL interpreter, falf, is a front-end for two existing solvers for ASP (Answer Set Programming): lparse/smodels, which is the default back-end, and dlv for which falf translation module is still quite limited (most examples involving arithmetics will not work). The front-end is programmed in Prolog using the SWI-Prolog interpreter, excepting a pre-parser which is written in language C for gcc (the GNU C compiler).

If you just want to try small examples, like the ones in this page, a simple choice is using the FAL online interpreter, which requires no installation at all. Otherwise, we recommend a local installation (by now, falf is only available for unix/linux systems).

The installation steps are the following:

1. Download and install gcc (only if not available in your unix/linux distribution).
   
2. Download and install lparse/smodels following the instructions in the corresponding web page. Do the same for dlv system, if you plan using this option (still under development).
3. Download and install the SWI-Prolog interpreter, following the instructions in the corresponding web page (note: there may exist a package-syle installation for your linux distribution).
4. Download and uncompress the file fal-1.0.tar.gz in a separate directory and then run make. To this aim, you can type the commands:
   
   
   $ gunzip fal-1.0.tar-gz
   $ tar -xvf fal-1.0.tar
   $ cd falf-1.0
   $ make
   
   
   
5. And that's all: at this point you should have the programs falf and getterms in the current directory. You will need both in order to run falf, so make sure they are accessible (execution permissions, path, etc) when you call falf. As a suggestion, move or make a link to both executables in some directory in your PATH (for instance, /usr/local/bin). You will also find a subdirectory called examples with some files containing FAL domains (including those in the tutorial below).

---

At the moment, a full reference manual for FAL, including a complete grammar description, is still under development. Meanwhile, the use of several examples may help. For a first simple example, consider the generation of the first eight values of the Fibonacci series. We begin defining a function called fib as follows:

static
  fib: index -> int.

The word static means that a set of function definitions follows. In fact, the term static further specifies that all the values of the functions below will not vary along time. We will see later that we can deal with transition systems and that other types of functions may change along time. A function declaration is done following the usual mathematical notation.

<function_name> : <set1> x <set2> x ... x <setN> -> <range> .

instances
  index 1..8.
  int 1..100.

meaning that index is a number varying from 1 to 8, and int a number from 1 to 100. The ordering among FAL sentences is irrelevant: you can declare functions referring to sorts that occur below in the code, or even in a different file. There exists a predefined sort called boolean, whose instances are true and false, as expected. When a function f(X) has a boolean range (i.e., it is a predicate) we allow the abbreviation of f(X)=true just as f(X) and the abbreviation of f(X)=false as not f(X).

When declaring functions or sorts, we can also refer to set expressions. For instance, function fib could also be defined as:

An extensional set is represented as a list of elements separated by commas and between braces, like for instance, {red, blue, green}. As we can see, the notation .. is used for comprising an interval of integer values. Another example of extensional set could be: {1, 3, 5..10, null}. Set union, intersection and difference are respectively represented by operators '+', '*' and '-'.

Note the use of a local variable X of type index used in the third rule of the previous example. All FAL variables must be declared with a given range. There are two ways of declaring a variable: as a local or as a global variable. A rule may include several declarations of local variables following the next pattern:

The term <vardecls> refers to a set of variable declarations separated by commas. When <vardecls> is empty, we remove the tag vars. Furthermore, if <body> is also empty, we remove the conditional operator ':-' too, and the rule (i.e., the head alone) is called a fact. Each variable declaration has the shape:

<varname> : <range>

mother(X)=Y :- parent(X,Y), female(Y) vars X : person, Y : person.

mother(X)=Y :- parent(X,Y), female(Y) vars X,Y : person.

vars
  X,Y : person.

rules
  mother(X)=Y :- parent(X,Y), female(Y).

This is sometimes more comfortable, as it avoids repeating the variable range in all the rules it is used. When there exists a coincidence in the names of a global and a local variable, the former is hidden by the latter, as expected.

One of the particular features of FAL functions is that they allow the definition of a default value. As an example, consider the following pair of definitions of boolean functions (or just predicates):

likes : person x person -> boolean.
parent : person x person -> boolean = false.

The first predicate has no default value and so, we may declare that likes(X,Y) is true or assert instead that it is false, but when we do not provide any information, it will have no defined value. When this happens, we say that likes(X,Y) is just unknown: in fact, we can use the boolean expression unknown(likes(X,Y)) (or its negation) in the body of any FAL rule. The second predicate, parent, has been defined as false by default. This means that when no evidence about parent(X,Y) is provided, we will assume by default that Y is not one of X's parents. Note that this is important, since we usually want to avoid describing all the people who are not parents of a given person.

Although, in practice, the inclusion of a default value seems a quite trivial feature, the theoretical consequences are extremely important. For instance, it was shown in [1] that the use of default values allows capturing Nonmonotonic Reasoning with the same expressiveness as standard Logic Programming (LP) with default negation. To understand why, note that a logic program can be captured by declaring predicates as boolean functions with a false value by default. In this way, the expression not f(X) becomes the usual LP default negation, as interpreted for instance, under Answer Set semantics. In fact, [1] introduced three semantic options for functional programs that were shown to correspond to three main LP semantics: Answer Set semantics, Well-Founded Semantics and Supported models. In this document, however, we will particularly focus on the functional version of Answer Set semantics.

Functional Answer Sets

In order to understand how default values work, consider by now that FAL rules had the simplified syntax:

where g and all the f_i are functions whereas v and the v_j are values. Any FAL program can be translated into a set of rules of this form by a grounding process: essentially, we remove variables and nested function references, replacing them by their possible values. A set of rules like (1) is called a ground FAL program.

An interpretation is a (possibly partial) mapping that assigns to each function f one value from its declared range, or perhaps no value at all, leaving f undefined or unknown. Of course, the latter may only happen when function f has no defined default value. The interpretation can be represented as a set of pairs (f=v) with at most one pair per each function f. An interpretation I is said to be a model of a ground FAL program when all rules like (1) in the program satisfy that(g=v) belongs to I if all the body pairs (f₁=v₁), ..., (f_n=v_n) belong to I. Given an interpretation I , we call default(I) to the set of pairs (f=v) in I for which v is the default value of f. An interpretation I is a functional answer set of a ground FAL program P when I is a minimal model of the augmented program: P U default(I).

In other words, we first guess some arbitrary possible model I for the program P. Then we add to P all the facts in I that correspond to default value assignments. Finally, getting the minimal model of this augmented program P U default(I) informally corresponds to an exhaustive application of its rules until no new fact is obtained. If, as a result of this process, we get back the original assumption I, then we have obtained a functional answer set.

Example: consider the following ground FAL program

Take the interpretation I = {f=0, g=3, h=5}. The default portion of I is default(I) = {f=0}, since it is the only assigment of a default value. Now we apply the second rule knowing {f=0} to get g=3. But as we have now {f=0, g=3} we apply the third rule to get h=5. As we cannot apply more rules, the final result of this process is {f=0, g=3, h=5} which coincides with the original I, and so, becomes a functional answer set. You can similarly check that this program actually has a second (functional) answer set: {f=7, g=0, h=0}.

As we have seen, FAL programs can be non-deterministic (i.e., generate more than one solution) due to the use of cyclic dependences among default values (in the example, for functions f and g). As happens in ASP, this feature can be used for representing search problems with different possible solutions. Using this technique of cyclic depdendences for representing constraint satisfaction problems is a possibility, but it usually forces us to introduce many auxiliary functions (typically, predicates) only used for generating multiple choices for the value of some function.

A simpler way to generate multiple possible values is using a value choice rule. The only syntactic difference with respect to usual rules relies on the form of the head:


The tag <function-reference> represents a term whose main operator is the reference to some function value. To see an example of this type of rule, consider the typical three-coloring problem, where we want to color (using say red, blue and green) all countries in a given map, so that no pair of neighbors is assigned the same color. We begin declaring the following functions and sorts:
 
The next rule generates all possible colorings:

At a first sight, it may seem strange to assert that the value of col(C) ranges in sort color twice: once in the function declaration and once again in the choice rule. However, both expressions have a different meaning. The range in the function declaration is just a definition of the possible values that col(C) could possibly take, but does not imply taking any of them at all -- in fact, without additional rules, the function would be left unknown. On the other hand, the choice rule forces col(C) to pick some value from a given set, which in this case coincides with the range of the function but need not. Note that if we add more instances to sort color adding the lines:

then we still can pick each col(C) from one of the three previous colors as follows:

Sometimes, it is useful to describe the extent of a set depending on function values. In FAL it is possible to define intensional sets with the following syntax:

All the previous examples have dealt with functions in a static context, but FAL also allows representing temporal problems for Reasoning about Actions and Change. Temporal scenarios in FAL correspond to transition systems, described in terms of two new types of functions: fluents and actions. A fluent is a function whose value may vary along time. An assigment of values for all fluents at a given moment is called a state.

An action is a function that can be "executed" to cause a change of state. An action is executed (or performed) when it is assigned a value different from its default value. An execution of actions is a possibly partial mapping assigning at most one value to each action. A transition <s_i,A_i,s_i+1> is a change from one state s_i (the predecessor state) to the next one s_i+1 (the successor state) caused by a given execution of actions A_i. A temporal narrative is a sequence of transitions like:


so that each <s_i,A_i,s_i+1> is a transition. We call situation to each integer subindex i=0..n.

Of course, rather than describing the transition system as a table with all the possible transitions (as would happen, for instance, with a finite state machine description), we will be interested instead in defining the transitions in terms of rules that relate the action and fluent values. Temporal rules in FAL are not very different from the ones we have seen before. In fact, the only actually new feature is the possibility of referrering to the values of fluents at the successor state. A reference to a fluent function, say f, in a rule is assumed to correspond to the fluent value at the predecessor state. However, when we use a primed version of the same function f', we assume we refer to the value of f at the successor state.

Let us see a simple example, proceeding from a typical scenario in actions reasoning. A light bulb is on if and only if two switches, sw(1) and sw(2), are closed. We begin defining the set of actions and fluents as follows:

would be not performed when press_brake=0. If we do not define a default value for the action, its non-execution can still be referred using the expression unknown(·). Now, back to the example, the switching effect of action toggle is captured by the pair of rules:

Note how sw'(I) refers to fluent sw(I) at the successor state. Primed fluents can be used in any part of the rule (including arguments of other functions). The only imposed restriction is that, if the rule contains some primed fluent, then the outmost fluent function in the head must be primed too. In other words, we cannot use information from the successor state to conclude facts for the predecessor one.

The indirect effect of the switches on the light bulb wouldd be simply captured by the rules:


Up to this point, we just have an scenario description but, what kind of reasoning problems can we solve about this domain? At the moment, FAL exclusively allows expressing (certain types of) planning problems. To be precise, we can specify an initial and a goal state, so that the FAL interpreter will try to obtain a plan, that is, sequence of actions that allows going from the initial state to the goal state, in a fixed number of steps called the plan length. To see how it works, consider the addition of the following lines:


Although we have used only facts in this example, below the initially and the goals clauses we can include any type of rule with only one syntactic limitation: actions and primed fluents cannot occur. Intuitively, in the rules under initially, all the occurring fluents will implicitly refer to their value at the initial state in the narrative s₀, whereas in rules under goals, the implicit situation is the final state s_n, being n>0 the plan length (note that n can also be 0). So, in this example, we look for a way of turning on the light bulb, when the initial state is that the switches are disconnected and the light is off.

Inertia Default

Inertia can also be understood as a special kind of default value. Each fluent, like light, can be seen as an implicit sequence of functions light₀, light₁, ..., light_n, where the subindex points out the situation in the narrative. Then, we could think that each one of these functions were implicitly declared as:


that is, the default value for light at state i is the value of light at state i-1.

Fluents can also have an associated default value (different from the inertial value we saw above) which is thought for describing the initial state. This (initial) default value can be very useful in some cases. To put an example, think for instance about a chessmate puzzle, where we begin with a few chessmen but most cells in the board are empty. In order to represent the board content we will need a fluent that varies along time, but at the same time, we would only like to specify the non-empty cells in the board, when describing the initial state. A possible declaration could look like:

Events

As we have said, the system state at each situation consists of all the fluent values. It is not so strange, therefore, that in order to get a compact description of transitions, we typically define all these fluents as inertial, so that our rules will only capture the relevant changes. However, in some cases, we may be interested in fluents that do not follow the inertia law. These "non-inertial" fluents are called events in FAL and they are typically used as auxiliary functions for expressing defaults or for a more comfortable handling of information about performed actions.

An event is a function whose value may vary along the narrative, but for which, in principle, there is no particular assumption relating its previous and successor value in any transition. As an example, assume that in our switches domain, each time the light turns on, a momentaneous click can be heard. This can be captured by adding the lines:



Events are quite similar to actions in many aspects. As we see above, we can declare a default value for an event, with a similar meaning to an action default value: it will represent that the event did not occur. Again, if no default value is declared, the non-occurrence of the event can be checked using unknown(·). The main difference between actions and events is that, in a planning problem, there exists an implicit value generation of action values at each transition, while for events this does not happen. Note that this slight difference can be removed by simply adding an explicit value choice rule for an event. To put an example, action toggle could be declared instead as:


but some features, like requiring non-concurrent actions, would be more uncomfortable in this way. Besides, actions are not thought, in principle, for being used in the head of any rule, while events typically are.

Action Qualifications

To illustrate the use of auxiliary events for expressing defaults, consider the following example. Assume we want to express that action toggle normally causes a change in the corresponding switch, but we want to leave open the possibility of specifying (perhaps in the future) new known conditions under which the toggling action fails. To put a particular example, assume that we currently know that toggle does not work when the switch mechanism is broken or when it is raining. We begin adding the declaration of the following fluents:


Now, we could simply add new conditions in the rule bodies, replacing the previous description of the toggling effects by:


But we may easily get interested in expressing more known situations under which toggling may fail. As a far as the list increases, we get forced to change these rules (and generally, all the ones dealing with effects of toggle(I)) more and more. This is usually called the qualification problem: listing explicitly all the situations in which an action fails, for all possible the effects of that action. To avoid this problem, we can define instead an auxiliary event abtoggle that will point out when the toggling results abnormal. Thus, the following part of FAL code does not need to be changed:

and we would simply add new rules (perhaps in a different file) for abtoggle(I) when new knowledge about toggling failures is available:

Action Attributes

As a second interesting use of events is as auxiliary functions for referring to some information about a performed action. This is called in the literature an action attribute. Consider the following classical example:

We can define an action:

so that move(M,C) establishes the number of moved missionaries and cannibals in each transition. However, if in some rule, we are just interested in the number of moved  missionaries, we would have to refer move(M,C) without using value C. Instead, we can define an event moved(P) as follows:

static  
  capacity = 2.
  
instances
  persontype mis, can.
  bank left, right.

static
  opposite : bank -> bank.
  
rules  
  opposite(left)=right.  opposite(right)=left.
  
actions
  move: {0 .. 2} x {0 .. 2} -> boolean = false.

fluents
  num : persontype x bank -> {0..3} = 0.
  boatbank : bank.

events
  moved : persontype -> {0..2} = 0.
  
vars
  M,C : {0 .. 2}.
  B : bank.
  P : persontype.

rules
  moved'(can)=C :- move(M,C).                     % (R1)
  moved'(mis)=M :- move(M,C).                     % (R2)
  
  :- moved'(mis)+moved'(can)=0.                   % (R3) 
  :- moved'(mis)+moved'(can)>capacity.            % (R5)  

  num'(P,boatbank)=num(P,boatbank)-moved'(P).     % (R6)  
  num'(P,boatbank')=num(P,boatbank')+moved'(P).   % (R7)  
  
  boatbank'=opposite(boatbank).                   % (R8)  
    
  :- num(mis,B)>0, num(can,B)>num(mis,B).         % (R9)  

initially
  num(can,left)=3.  num(mis,left)=3.  boatbank=left.
  
goals
  num(can,right)=3.  num(mis,right)=3.

Rules (R1) and (R2) fix the corresponding value for each attribute. After that, we can directly refer to the number of moved persons of type P by using the event moved(P). Action attributes can be located in the predecessor or in the successor state: it is a choice criterion. However, in this case it is more practical to place them in the successor state (this is why moved occurs primed). In this way we can add constraint (R3) forcing to move people in each transition, and then the rule for changing the boat bank (R7) does not depend on the action execution, avoiding an excessive number of ground rules.

[1] P. Cabalar and D. Lorenzo, "Logic Programs with Functions and Default Values," 9th European Conference on Logics in Artificial Intelligence (JELIA'04), Lisbon, Portugal, Lecture Notes in Artificial Intelligence, vol. 3229, pp. 294-306.

[2] P. Cabalar, "A Functional Action Language Front-end", presented at the 3rd Workshop on Answer Set Programming (ASP'05), Bath, UK, July 2005.

---

Join the FAL Team

Currently, the FAL team consists of:

• Pedro Cabalar   (project coordinator)
  
• José Manuel Pedrosa
  

Any help of any nature is eagerly welcome! These are possible ways of collaboration:

• As a user, please send an e-mail to the address above with detected errors, suggestions about desired new features or comments about language design. A FAL mail-list will be created with those users that wish to be added.
  
  
• As an associated programmer or developer.
  
  
• There exist several possibilities for students at Corunna (contact with Pedro Cabalar):
• Developing a graduate project ("Proyecto Fin de Carrera").
• Developing a PhD thesis on the subject.
  

To figure out the kind of work to do, these are some open topics:

• falf is the only current tool for FAL language, but other options are under consideration. An interesting project currently under development is a FAL grounder, fparse, that replaces the tandem falf+lparse and directly generates an smodels input program. More information will be available soon.
  
  
• Another possibility is building a direct solver for functional answer sets with ground FAL rules.
  
  
• Theoretical improvements and language design: addition of quantifiers/aggregates; objects and attributes; other types of temporal problems, etc.
  
  
• Implementation of other semantics: well-founded semantics and supported models.

---