9. Related Work

A number of web sites, for example the CRC Dictionary [3] and the Encyclopedia of Mathematics [20], already provide encyclopedic information on algorithms, data structures, and mathematical results. Like all encyclopedias, however, they are of no use to someone unfamiliar with the terminology of the field they are investigating.

More relevant to the present research is Sloane's On-Line Encyclopedia of Integer Sequences [18]. This search service allows users to look up number sequences without knowing their name. For example, if a user entered the sequence $\ulcorner\hspace*{-2pt}$ 1,2,3,5,8,13,21,34 $\hspace*{-2pt}\urcorner$, the server would respond with ``Fibonacci numbers.'' It is interesting to note that, although many of the entries in the database include a program or formula to generate the sequences, these programs do not seem to be used in searching the database. A similar search service is Encyclopedia of Combinatorial Structures [15].

Inductive Logic Programming (ILP) [2] is a branch of Machine Learning. One application of ILP has been the automatic synthesis of programs from examples and counter-examples. For example, given a language of list-manipulation primitives (car, cdr, cons, and null) and a set of examples

an ILP system might synthesize the following Prolog-program for the append predicate:

Obviously, this application of ILP is far more ambitious than A$\lambda$goVista. While both ILP and A$\lambda$goVista produce programs from input $\Rightarrow$output examples, ILP synthesizes them while A$\lambda$goVista just retrieves them from its database. The ILP approach is, of course, very attractive (we would all like to have our programs written for us!), but has proven not to be particularly useful in practice. For example, in order to synthesize Quicksort from an input of sorting examples, a typical ILP system would first have to be taught Partition from a set of examples that split an array in two halves around a pivot element:

A$\lambda$goVista is essentially a reverse definition dictionary for Computer Science terminology. Rather than looking up a term to find its definition (as one would in a normal dictionary), a reverse definition dictionary allows you to look up the term given its definition or an example. The DUDEN [7] series of pictorial dictionaries is one example: to find out what that strange stringed musical instrument with a hand-crank and keys is called, you scan the musical instruments pages until you find the matching picture of the hurdy-gurdy. Another example is The Describer's Dictionary [11] where one can look up $\ulcorner\hspace*{-2pt}$ mixture of gypsum or limestone with sand and water and sometimes hair used primarily for walls and ceilings $\hspace*{-2pt}\urcorner$ to find that this concoction is called plaster.