1. The A$\lambda$goVista Type System

In Section 7 we show how type analysis can speed up A$\lambda$goVista's search engine. The idea is to assign a type signature to every query, checklet, and query transformation, and only submit a query to a checklet if the signature of the query matches that of the checklet.

Figure 7(a) shows the A$\lambda$goVista type hierarchy. Only some of these types are directly expressible in QL. For example, even though A$\lambda$goVista has a set type, there is no concrete QL syntax for sets. Rather, as we will see in Section 5, query transformations are responsible for inferring a collection of possible types from a QL query, including that a vector $\ulcorner\hspace*{-2pt}$ [1,2,3] $\hspace*{-2pt}\urcorner$could represent the set $\{1,2,3\}$. This allows checklets to be very specific about what types of queries they will accept, and it allows A$\lambda$goVista users to be very non-specific in how they formulate their queries. For example, an unsophisticated user might issue the query

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

in the search for the set union operation. He is not required by the A$\lambda$goVista type system to explicitly state that the three operands are sets, since he may not even be familiar with this concept. Rather, he can simply represent the sets as vectors, A$\lambda$goVista's general term for ``collections of objects''.

The set union checklet, on the other hand, can specify explicitly that it will only accept queries that map two sets to a third set, i.e. that has the signature

Map(Pair(Set(Int),Set(Int)),Set(Int)).

Type-checking queries and checklets will prevent a query such as

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

from being submitted to the set union checklet since one of the vectors is not a set.

Figure 7(b) shows the mapping from QL queries to type signatures. Figure 7(c) gives some examples.