1. Fast Checking by Precomputation

Whenever a new checklet is added to the database, A$\lambda$goVista generates a new search procedure ${\cal S}_{{\cal T},{\cal C}}$ automatically. This procedure is hardcoded to handle exactly the set of transformations $\cal T$ which are available in the transformation database, and the set of checklets $\cal C$which are currently available in the checklet coop. ${\cal S}_{{\cal T},{\cal C}}$is constructed such that given an input query q whose type is ${\cal T}\Lbrack q\Rbrack$, ${\cal S}_{{\cal T},{\cal C}}$ will apply exactly those combinations of transformations to q that will result in viable mutated queries. A query is viable if it is correctly typed for checking by at least one checklet.

In other words, A$\lambda$goVista's optimized search procedure ${\cal S}_{{\cal T},{\cal C}}$ will never perform a useless transformation, one that could not possibly lead to a mutated query correctly typed for some checklet.

In order to apply transformations and to test checklets efficiently, A$\lambda$goVista determines the signature of an input query upon its arrival. Given the query's signature, A$\lambda$goVista knows exactly which, if any, checklets to test, and which, if any, transformations to apply. Furthermore, A$\lambda$goVista knows the exact signature of each newly-generated query because it knows the input query signature and how the transformation will transform the signature. (For example, A$\lambda$goVista knows that applying the FlipPair transform to Map(Pair(Float,Int),Float) will yield Map(Pair(Int,Float),Float).) This observation yields a very simple, but highly optimized architecture for A$\lambda$goVista to apply transformations and test checklets based on signatures, in which there is one function per signature responsible for all the operations that affect queries of that signature. Each function has three parts: verifying the originality of the query, testing all matching checklets, and generating isomorphic queries by applying transformations. All generated queries are simply handed off to the function that handles their signature.

For the given checklets and transformations above, the function that handles the signature Map(Pair(Float,Int),Float) is as follows:

The AlreadySeen-set prevents the same query mutation from being produced more than once:

The only non-trivial aspect of the generated function is knowing which transformations can be applied to a given signature, and where. For instance, given the query signature, Map(Pair(Pair(Int,Float),Pair(Float,Int))), it is possible to apply the FlipPair transformation at any of the four Pairs in the query--even the nested ones.

In addition to the signature-specific functions, it is also necessary to generate a large decision tree that determines the signature of the original query before that query is dispatched to the appropriate function.