/*  SEARCH.P  */


section $-search => search,
                    path_search,
                    trace_search,
                    untrace_search,
                    df_insert,
                    bf_insert,
                    eval_insert,
                    df_path_insert,
                    bf_path_insert,
                    eval_path_insert;


/*
SPECIFICATION
-------------

This module defines general routines for searching. They are very
general: by changing the arguments, you can configure them to do
depth-first, breadth-first, hill-climbing and many other types of
search.

To understand how, you have to know how the search is implemented.
Each search routine maintain a "queue": a list of those points which
have been marked for examination but not yet examined. The routine works
in a cycle, thus:

    1)  Take the first element off the queue. If there is none,
        the search has failed: return false. Otherwise, this is
        the next point to be explored.

    2)  If this point is the goal, return true.

    3)  Find all the neighbours of this point, eliminating any
        which have already been explored. Add the others to the
        queue, making sure that if a neighbour is generated more than
        once, only one copy gets added.

    4)  Go back to 1.

By altering the way that stage 3 adds neighbours to the queue, we can
determine the type of search. For example, if each neighbour is added to
the front of the queue, we get depth-first; the final neighbour added
will be the first to be explored. If each neighbour is added to the end
of the queue, we get breadth-first. If we sort the queue in order of
estimated distance from the goal, so that the nearest point is the first
to be explored, we get hill-climbing. This is explained in many
references, for example in the chapter on Search in "Artificial
Intelligence" by Winston. Those unfamiliar with the idea will find TEACH
SEARCHING useful: note how the 'insert' procedure is used.


PUBLIC search( here, is_goal, next_from, insert ):

The arguments are as follows:
here        : the initial point to search from.
is_goal     : a function
                  is_goal(point)
              which returns true if point is a goal, and false
              otherwise.
next_from   : a function
                  next_from(point)
              which returns a list of all the neighbours to be
              explored.
insert      : a function
                  insert(point, queue)
              which inserts point into queue returning a new queue.

'search' searches for a goal point from 'here' as described above,
returning true if it finds one and false otherwise.

'search' keeps track of the points which have already been visited, so
as to avoid getting into loops. You can therefore safely use it for
depth-first search, even if you suspect loops in the search tree.

It also (as mentioned above) avoids adding the same neighbour to the
queue more than once, if next_from returns several copies. However, for
efficiency, it's as well to write a generator that doesn't do so.


PUBLIC path_search( here, is_goal, next_from, insert ):

'path_search' is used when you want to know the path to the goal. If
one can be found, it returns this as a list of points: the first
element is 'here', the final one is the goal, and the others are the
points in between. If one can't be found, it returns false.

The arguments are the same as for 'search' with the exception of
'insert'. This is now a function
    insert( here, path, queue )
which returns a new queue. The queue is now a list of _lists_, each
of the form
    [% point, path_to_point %]

When examining an element, you must therefore get its head to get the
point. When constructing the element for 'here', its second element must
be 'path'. See the supplied insert functions below for examples.


PUBLIC trace_search():

Turns on tracing. When this is on, the routines make the following calls
in each cycle:
    printf('q %p\n', [%queue%] )
    printf('here %p\n', [%here%] )
    printf('neighbours %p\n', [%neighbours%] )
    printf('inserting %p\n', [%neighbour%] )
showing the queue, point being explored, neighbours (result of
next_from), and each neighbour being inserted.


PUBLIC untrace_search():

Turns off tracing.


PUBLIC df_insert( point, q ):

An insert routine for 'search' for implementing depth-first search.
Defined as
    define df_insert( point, q );
        lvars point, q;
        [ ^point ^^q ]
    enddefine;


PUBLIC bf_insert( point, q ):

An insert routine for 'search' for implementing breadth-first search.
Defined as
    define bf_insert( point, q );
        lvars point, q;
        [ ^^q ^point ]
    enddefine;


PUBLIC eval_insert( point, q, eval ):

An insert routine for 'search' for implementing evaluation-guided
search. 'eval' is a function eval(point)->number which maps a point to
an evaluation. The higher the evaluation, the better the point, so the
further forward in the queue it will go. Defined as
    define eval_insert( point, q, eval );
        lvars point, q, eval;
        if eval(point) > eval(hd(q)) then
            [ ^point ^^q ]
        else
            [ ^(hd(q)) ^^(eval_path_insert(point,tl(q),eval)) ]
        endif;
    enddefine;

Note: this may evaluate the same point several times. If evaluation is
expensive, store your evaluation in a property (or somewhere) and re-use
it.


PUBLIC df_path_insert( point, path, q ):

An insert routine for 'path_search' for implementing depth-first search.
Defined as
    define df_path_insert( point, path, q ):
        lvars point, path, q;
        [ [^point ^path] ^^q ]
    enddefine;


PUBLIC bf_path_insert( point, path, q ):

An insert routine for 'path_search' for implementing breadth-first
search. Defined as
    define bf_path_insert( point, path, q ):
        lvars point, path, q;
        [ ^^q [^point ^path] ]
    enddefine;


PUBLIC eval_path_insert( point, path, q, eval ):

An insert routine for 'path_search' for implementing evaluation-guided
search. 'eval' is a function eval(point)->number which maps a point to
an evaluation. The higher the evaluation, the better the point, so the
further forward in the queue it will go. Defined as
    define eval_path_insert( point, path, q, eval );
        lvars point, path, q, eval;
        if eval(point) > eval(hd(hd(q))) then
            [ [^point ^path] ^^q ]
        else
            [ ^(hd(q)) ^^(eval_path_insert(point,path,tl(q),eval)) ]
        endif;
    enddefine;


NB: both search routines compare two points for equality by using =. If
your representation of points is such that different structures can
denote the same point, this won't work. */


/*
IMPLEMENTATION
--------------

The idea of parameterising search by altering the way elements are added
to a queue is well-known, see (e.g.) the chapter on Search in
"Artificial Intelligence" by Winston. The code in this module is based
on that in TEACH SEARCHING. Originally, I used matching to extract
elements from the queue, because it was easy to write, and easy for
novices to compare with TEACH SEARCHING.

However, when I introduced sections, I had to change this, because
the matching operators ? and ?? don't work properly inside sections.
This is a shame - if we ever get a matcher that does, restore the
original code.

'path_search' works in the same way as 'search', except for the
structure of the queue. In 'search', this is a list of points to be
explored. In 'path_search', each element is itself a list. The first
element of this list is the point to be explored; the second element is
the path to it from the start point. Although much of the rest of the code
is duplicated, it seemed neater to have two different routines than to
try parameterising one.

The 'eval_insert' routine is inefficient unless you use memo-functions
or an equivalent such as properties, because it may evaluate a point
several times. What's a neat way to circumvent that without spoiling the
interface?
*/


vars tracing = false;


define global trace_search();
    true -> tracing;
enddefine;


define global untrace_search();
    false -> tracing;
enddefine;


define global search( here, is_goal, next_from, insert );              
    lvars here, is_goal, next_from, insert;
    lvars neighbours, visited, q;

    /*
    q      : points that are waiting to be explored.
    visited: all points that have been explored.
    q and visited are disjoint.
    */

    [% here %] -> q;
    [] -> visited;

    repeat forever
        if tracing then printf('q %p\n', [%q%] ) endif;

        if q = [] then return(false) else dest(q) -> q -> here endif;
        if is_goal(here) then return(true) endif;

        if tracing then printf('here %p\n', [%here%] ) endif;

        [^here ^^visited] -> visited;
        next_from(here) -> neighbours;
        if tracing then printf('neighbours %p\n', [%neighbours%] ) endif;

        /*
        Insert into q all those neighbours which we haven't already
        visited, and which are not already in it. The second check frees
        next_from from the need not to return the same point more than
        once (though for efficiency, it's a good idea for it not to).
        */
        while neighbours /= [] do
            dest(neighbours) -> neighbours -> here;
            unless member(here, visited) or member(here, q ) then
                if tracing then printf('here %p\n', [%here%] ) endif;
                insert(here, q) -> q
            endunless;
        endwhile;
    endrepeat;

enddefine;


vars inq;/*forward*/


define global path_search( here, is_goal, next_from, insert );
    lvars here, is_goal, next_from, insert;
    lvars neighbours, first, visited, q, path;

    /*
    The variables have the same meaning as in 'search', except for
    q. Each element is a list [% p, path %], where p is a point to
    be explored, and path is the path from the initial value of 'here'
    (root of the search tree) to p. This path includes its endpoints.
    */
    [% [% here, [%here%] %] %] -> q;
    [] -> visited;

    repeat forever
        if tracing then printf('q %p\n', [%q%] ) endif;

        if q = [] then
            return(false)
        else
            dest(q) -> q -> first;
            first(1) -> here;
            first(2) -> path;
        endif;
        if is_goal(here) then return(path) endif;

        if tracing then printf('here %p\n', [%here%] ) endif;

        [^here ^^visited] -> visited;

        next_from(here) -> neighbours;
        if tracing then printf('neighbours %p\n', [%neighbours%] ) endif;

        while neighbours /= [] do
            dest( neighbours ) -> neighbours -> here;
            if not(member(here, visited)) and not(inq(here, q)) then
                if tracing then printf('inserting %p\n', [%here%] ) endif;
                insert( here, [^^path ^here], q ) -> q
            endif;
        endwhile;
    endrepeat;

enddefine;


/*  inq( point, queue ):
        True if 'point' is in 'queue', where 'queue' is used by
        path_search. We can't use 'member' for this test, because
        each element of the queue is not a point, but a point and
        a partial path.       
*/
define inq( here, q );
    lvars here, q;
    lvars p;
    for p in q do
        if here = p(1) then return(true) endif;
    endfor;
    return(false);
enddefine;


define global df_insert( point, q );
    lvars point, q;
    [ ^point ^^q ]
enddefine;


define global bf_insert( point, q );
    lvars point, q;
    [ ^^q ^point ]
enddefine;


vars eval_path_insert;/*forward*/


define global eval_insert( point, q, eval );
    lvars point, q, eval;
    if eval(point) > eval(hd(q)) then
        [ ^point ^^q ]
    else
        [ ^(hd(q)) ^^(eval_path_insert(point,tl(q),eval)) ]
    endif;
enddefine;


define global df_path_insert( point, path, q );
    lvars point, path, q;
    [ [^point ^path] ^^q ]
enddefine;


define global bf_path_insert( point, path, q );
    lvars point, path, q;
    [ ^^q [^point ^path] ]
enddefine;


define global eval_path_insert( point, path, q, eval );
    lvars point, path, q, eval;
    if eval(point) > eval(hd(hd(q))) then
        [ [^point ^path] ^^q ]
    else
        [ ^(hd(q)) ^^(eval_path_insert(point,path,tl(q),eval)) ]
    endif;
enddefine;


endsection;