4. The Query Language

To make the use of A$\lambda$goVista a pleasant experience, users must be able to easily formalize their queries. This necessitates the design of a natural and expressive query language. QL, the A$\lambda$goVista query language, is essentially a domain-specific language where the domain is very large: users need to be able to express any reasonable mapping between any reasonable literal data structures.

As is always the case with domain-specific languages, there is a tension between a minimalist syntax (LISP-like, for example) and a ``kitchen-sink'' syntax. The former has a few simple primitives whereas the latter has many complex primitives, one for each anticipated use. The minimalist syntax is easy to learn but combining the primitives into complex sentences (queries, in our case) can be cumbersome. The kitchen-sink syntax, on the other hand, has a steeper learning-curve, but common sentences (those anticipated by the language designers) are easier to express.

QL is of ``medium'' complexity: while it has some kitchen-sink features, there are many data structures which cannot be expressed directly but have to be constructed by combining simple primitives. QL primitives include integers, floats, booleans, lists, tuples, atoms, and links. Links are (directed and undirected) edges between atoms that are used to build up linked structures such as graphs and trees. Special syntax was provided for these structures since we anticipate that many A$\lambda$goVista users will be wanting to classify graph structures and problems on graphs.

  

Figure 6(a) shows the syntax of QL, and Figure 6(b) gives some example queries. In the query in Figure 6(b)  a pair of integers (1 and 2) is mapped to an integer (3). A$\lambda$goVista returns the result set $\langle$Binary or, Integer add$\rangle$since 1+2=3 and $1\mid2=3$. In the query in Figure 6(b)  a directed graph is mapped to a directed graph. Each graph is represented, by convention, as a pair of a node-list and an edge-list. The query in Figure 6(b)  asks A$\lambda$goVista to classify a particular graph, which turns out to be a strongly connected directed graph.

Figure 6(b) , finally, shows a query that maps a pair of vectors to a vector:

$\ulcorner\hspace*{-2pt}$ ([3,7],[5,1,6])==>[5,1,6,3,7] $\hspace*{-2pt}\urcorner$.

A$\lambda$goVista returns the result $\langle$List append$\rangle$since append([5,1,6],[3,7])=[5,1,6,3,7]. To arrive at this result A$\lambda$goVista first swapped the input pair using a query transformation. We discuss this further in Section 5.