Declarative Debugging of Missing Answers in Functional and Logic Programming

(Mario Rodríguez Artalejo & Rafael Caballero Roldán & Rafael del Vado Vírseda & Fernando Pérez Morente)

In this page you can find a prototype of the functional-logic language Toy including a prototype for debugging missing answers in lazy functional-logic programs.

What is Toy?

TOY is a constraint functional logic system, designed to support the main declarative programming styles and their combination. It has been designed and developed mainly by the Declarative Programming Group at the University Complutense of Madrid. A short overview of the language features can be found here. A more detailed description of the system and its possibilities can be found in the Toy Report (.pdf document).

Observe however, that the missing answer debugger is still in alpha phase and hence it is included neither in the main distribution nor in the Toy Report. We hope to have the tool included in the system distribution for the next version of the Toy system. At the moment it can be downloaded only from this page following the instructions below.

Downloading and Installing the Tool

A version of the system including the debugger for missing answers can be downloaded from here. After unzipping the file a folder Toy is created. This folder includes the source code of the system with the embebbed debugger. The requirements for executing the debugger are:

Windows: The JRE (Jave Runtime Environment), which can be downloaded from here.
Other O.S.: The JRE plus a SICStus Prolog environment (version 3.8.4 or later running on most common operating systems).

Starting Toy

To start Toy in Windows just double-click on the toywin.exe file. In other operating systems:

Start Sicstus Prolog.
Move to the Toy directory by typing at the SICStus prompt:
- use_module(library(system)).
- working_directory(D, PathToToy).
where PathToToy must be the path to the toy folder, e.g.:
- working_directory(D, 'c:/toy').
Type [toy] at the Sicstus prompt.

Example

Let's start with a small functional-logic program including a missing answer. The example can be compiled and loaded from the Toy prompt by typing Toy>/run(example1). The code of the example is:

   % f must return 1,2 and 3.
     f = 1
     f = 3



   % g must return X+1 for every X
     g X = X+1



   % h must return X+1 for every value X returned by f
     h = R <== f == X, g X == R

In this example the user has forgotten the program rule f = 2 in the definition of the non-deterministic function f. The symbol % is used for including comments. The symbol <== in the program rule for function h denotes a condition in Toy, meaning in this example that a value R is returned by the function if it is possible to find a value X such that X is returned by f and R y returned by g X.

Computations in Toy are started by asking goals to the system. For instance we can try the goal:

Toy> h == A

asking by values of the variable A (i.e. substitutions) corresponding to returned values of h. The system answers with all the possible values of A fulfilling the goal, after each answer the system asks the uses if more answers are required. The answer a means 'show all the answers':

   Toy> h == A
        { A -> 2 }     
  
   sol.1, more solutions (y/n/d/a) [y]? a
          { A -> 4 } 

   sol.2, more solutions (y/n/d/a) [y]? 
          no

Therefore two answers are obtained. However this is an incomplete answer since three answers (2, 3, and 4) where expected. From this incomplete answer the user detects that there must be some error in the program definition. In order to find the bug the debugger for missing answers is started by typing:



   Toy> /missing

After this command the debugger repeats internally the computation, producing a computation tree that is displayed by means of a Java interface:

For instance the node

h 
==>[2,4]

means that if h returns a value then it is either 2 or 4. In order to find the bug the user must provide information about the validity of each node w.r.t. the intended interpretation of the program. This can be done either manually, selecting nodes and choosing their state in the Node submenu, or by using some automatic strategy, which can be selected in the submenu Strategy. For instance if we choose the Divide & Query strategy proposed by E.Y. Shapiro, the system asks the following question:

The selected node contains information about the results returned by f. This node is non-valid because the possibility [2]. Thus the user selects the red cross, the symbol used by the debugger in order to represent non-validity; the first one stands for validy, the third for don't know, and the last one for trusted, which means that the user assumes that all the nodes associated to the function are valid. Although usually several questions are required, in this small example the first question is enough for finding the error and the user displays

meaning that f is an incomplete function.

Another example can be executed by typing Toy>/run(example2)in the prompt. Additional examples of Toy programs are available in the directory /examples of the distribution of the Toy system.

Deficiencies in the Current Debugger Prototype

Since the tool is still in the alpha phase there are some flaws, which are listed below:

Variables: Variables are shown as Prolog variables in the computation tree. This makes the computation tree more difficult to read.
Constraints: Toy allows several contraint solvers (real number, finite domains). At the moment only disequality constraints are allowed. The same ideas can be used for other domains and we plan to extend the debugger in this direction.
Functions with underscores on its name are not transformed when generating the debugging tree.

For any comment contact us at

Last update: 25 Nov 2009