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)


 Introduction

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:

 Starting Toy

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

 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:

Computation tree

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:

Shapiro

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

Shapiro2

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:


For any comment contact us at    mail
Last update: 25 Nov 2009