# Ruling the Queries
One of the common themes of systems that 'face the world' is that they often have to make decisions. There are many approaches to providing for such _classifications_ but one of the most robust is _rules_. There are also many forms of rule, here we will focus on a particular form of rule: _the inference rule_.

In general, a response to an external event goes through a series of phases:

1. Taking _measurements_ of the event;
2. applying some form of inference to the measurements to derive _facts_; and
3. based on certain criteria, deciding what to _do_ in response to the event.

A rule language, especially a logic rule language, is very well suited to expressing the logic (sic) of this kind of scenario. Our language, which is called **CnC**[^Code Named CnC], is an embedded language within **Star**.

But, before we go too far, it may be worth digressing a little to explore what it means to ask a question -- to have queries. This will help to understand why we can benefit from going beyond what we have already seen in **Star**.

## Queries

Consider, if you will, the problem of finding a set of grandparent-grandchild pairs -- given information about parent-child relationships. For example, suppose that we had a list of pairs - each pair indicating a parent and child:
```
parents:list[(string,string)].
parents = [("john","peter), ("peter","jane"), ... ].
```
and that we wanted to construct a result list -- also of pairs -- along the lines of:
```
GC:list[(string,string)].
GC = [("john","jane"),...].
```
Computing the list grandparent/grandchildren pairs involves searching the parents for pairs  that satisfy the grandparent relationship. This involves a double iteration: each pair in the `parent`s list might represent the upper or lower half of a grandparent/grandchild relationship. Based on the collection operators we have seen so far, we can build such a search using two `foldLeft` operations:
```
foldLeft(
 (SoFar,(X,Z)) => foldLeft(
   let {
     acc(gp1,(ZZ,Y)) where Z==ZZ => [gp1..,(X,Y)].
     acc(gp1,_) => gp1.
   } in acc,
   SoFar,parents),
   list of [],
  parents)
```
This, rather intimidating,[^There are, unfortunately, some functional programmers that revel in complex code expressions like this one. We are not one of them!] expression uses one `foldLeft` to look for the grandparent, for each candidate grandparent a second `foldLeft` finds all the grand-children. All without any explicit recursion.

The `acc` function defined above in the `let` expression implements the logic of deciding what to accumulate depending on whether we had found a grandparent or not.

The various filter, fmap and foldLeft functions *are* powerful ways of processing entire collections. However, as we can see, they can be difficult to construct and harder to follow; something that is not helped by the occasional need to construct complex functions in the middle, as in this case.

What is needed is a way of expressing such complex query conditions in a way that can be represented using `foldLeft` expressions but which is easier to read.

Consider the conjunction:
```
(X,Z) in parents and (Z,Y) in parents.
```
This should be read simply as:

>For which `X`, `Y` and `Z` can be assert that `X` is the parent of `Z`, and `Z` is the parent of `Y`?.

This should be significantly easier to follow than the complex expression above; and it is easier to be sure whether it is a correct representation of what it means to be a grand parent.

### Satisfaction semantics
Conditions like the ones above are boolean valued -- but they are not always expressions. For example, the first condition there being a parent:
```
(X,Z) in parents
```
is not evaluated in the way that expressions are normally evaluated -- by *testing* to see if a given pair of `X` and `Z` are in some `parents` collection. Instead, the condition is evaluated by trying to find `X` and `Z` that are in the collection. In effect, the condition becomes a _search_ for suitable candidate pairs.

Technically this is called *satisfying* the condition -- to distinguish what is going on from *evaluating* the condition. Of course, satisfying and evaluating are close cousins of each other and amount to the same thing when there is no search involved.

In addition to individual *search conditions* like this, it is also possible to use logical operators -- called *connectives* -- to combine conditions. In the case of our grand-parent query, there is a conjunction; which involves the variable `Z` that acts as a kind of glue to the two search conditions.

>In database query terminology, conjunctions like this one amount to _inner joins_. Languages like SQL have many operators and features to make expressing queries easier; the fundamental semantics of **Star**'s queries are similar to those of SQL.

The available connectives include the usual favorites: `and`, `or`, and `not`. They also include some less familiar connectives: `implies` and `otherwise`.

The `implies` connective is a way of testing complete compliance with a condition; for example, we can define a query capturing the situation that a manager earns more than his/her members by requiring that anyone who works for the manager earns less than they do:
```
(X,M) in worksFor implies X.salary=<M.salary.
```

## Code Named CnC

The essence of **CnC** is to take the form of query we see here and lift it into a full rules language; in fact, **CnC** is a so-called _logic_ language -- a term that has a precise if somewhat obscure meaning.

Like programming languages, it turns out that there are many kinds of logic. Again, like programming languages, there is a trade-off between expressivity and complexity. The primary source of complexity in a rule language is the machinery needed to realize it -- together with understanding it sufficiently to be able to predict the meaning of a written rule.

A, somewhat simplified, enumeration of the different kinds of logic might be:

* Propositional calculus. This is characterized by single-letter conditions (sometimes confusingly called _predicate variables_) and a guaranteed finite evaluation mechanism.
* Datalog. This is characterized by relations with simple unstructured values (i.e., strings and numbers). Execution in datalog has similar performance characteristics as querying databases.
* First Order Predicate Calculus. This is probably the most well known and well understood logic. From a expressiveness point of view it's focus is on the logical relationships amoungst individual entities -- which includes things like trees, lists and so on. Inference in First Order has many of the same characteristics as program evaluation: not decidable in general but many effective sub-cases.
* Higher Order Predicate Calculus. There are actually many higher-order logics. The main expressive enhancement over First Order is that one can directly talk about relationships between entities as well as entities themselves. The cost of this is that inference becomes problematic -- even equality is undecideable.

Each of these levels represents a step both in expressiveness and in complexity. In general, the right logic for your application is something only you can decide; however, in designing a language, we have to choose for you. We take our inspiration from the success of languages like SQL and the relative obscurity of languages like Oz and Lambda Prolog.

In our view, there is a sweet spot between Datalog and First Order Logic. Datalog allows one to right rules (unlike pure SQL) but is not capable of handling arbitrary data structures. On the other hand, it may be that _recursion_ is something that we can do without -- as we have seen earlier, many well structured functional programs have no explicit recursion!

The elements of **CnC** are simple:

* Relations[^A deliberately underspecified term at this point] are identified as sets of tuples.
* A **CnC** rule consists of a _predication_ -- identifying the relation that the rule is defining -- and a body.
* The body of a **CnC** rule is a logical combination of _conditions_, some of which are _predications_;
* The semantics of **CnC** are based on _satisfaction_ rather than expression _evaluation_.
* Although **CnC** rules sets are not permitted to be recursive, there are several fold-style operators that can be used to specify aggregate computations.

We can codify our grandparent query into a rule as:
```
grandparent(X,Y) :- (X,Z) in parents and (Z,Y) in parents
```
or, probably more realistically:
```
grandparent(X,Y) :- parent(X,Z) and parent(Z,Y).
parent(A,B) :- (A,B) in parents.
```
The `grandparent` rule states that:
> for every `X`, `Y` and `Z` such that there is a fact of the form `parent(X,Z)` and there is a fact of the form `parent(Z,Y)`, then there must also be a fact of the form `grandparent(X,Y)`.

The variables `X`, `Y` and `Z` are _placeholders_: they are not variables in the normal programming language sense. They stand for some unspecified individual; and, in this case, there is a `grandparent` fact for all possible ways of replacing the variables `X`, `Y` and `Z` with actual individuals in a way that satisfies the rule.[^One of the interesting restrictions in predicate logic is that there must be at least one individual: nothing can be said of an uninhabited world.]

### Assertions and facts
An assertion is a statement that something is true -- i.e., it is a fact.

>There is a subtle distinction between something being true, and stating that something is true.

**CnC** rules are rules about facts: each rule states that some class of fact is true. It is not actually that important to the design of **CnC** whether the stated fact is actually true!

There are two forms of assertion: the simple assertion and the given assertion.

**Star** has a special notation that makes this kind of complex computation significantly easier to write and comprehend. **Star**’s query notation is a very high level way of expressing combinatorial combinations of collections. We can write the equivalent of the previous grandparent expression in this query notation as:
```
GC = list of { all (X,Y) where
                 (X,Z) in parent && (Z,Y) in parent }
```
It may not be obvious, but these expressions compute the same values. What should be obvious is that the query is much easier to read and easier to verify that it is correct.

The syntax and style of **Star**’s query notation is similar to SQL’s syntax -- deliberately so.

Specifically, we take SQL’s *relational calculus* subset -- the language of wheres and of boolean combinations. **Star**’s query expressions do not have the equivalent of explicit relational join operators.

There are several variations of query expression, but the most common form is:

*SequenceType* of { *QuantifierTerm* where *Condition* *Modifier* }

where *SequenceType* is any type name that implements the stream contract, *QuantifierTerm* is a form that indicates the form of the result of the query, *Condition* is a condition and the optional *Modifier* is used to signal properties of the result -- such as whether the result is grouped or sorted.

### Query quantifiers

The *QuantifierTerm* in a query specifies ‘how many’ answers we want. There are essentially three forms of *QuantifierTerm* -- if we want all the answers then we use a term of the form:

{ all (X,Y) where ... }

On the other hand, if we want a fixed number, then we use:

{ 5 of (X,Y) where ... }

Of course, there might not be five answers, and so this is called a bounded *QuantifierTerm*.

We have only scratched the surface of possibilities of query expressions here. They are, in fact, one of **Star**’s most powerful high-level features.

### Querying for statistical purposes

We wrap up our exposition on collections with an example that highlights how we can combine many of the collection manipulation features; with a specific goal of statistical processing of data.

Statistics is, of course, one of the key application areas of computers in general. However, there is often a substantial gap between the theoretical aspects of statistical processing and the pragmatics of collecting and processing data. We aim to demonstrate **Star**’s power in both areas.

One fecund source of statistics is the web; we can even get statistics about the web. The on-line tool [Web Page Test](http://www.webpagetest.org/) can be used to generate a lot of data about how a browser responds to a website. Furthermore, we can down this data as a file of comma separated values (CSV). The first few lines of this file shows the detail of the data collected:

Date,...,URL,Response Code,Time to Load (ms),...,Bytes In,...

9/12/14,...,/,302,397,...1272,...

There are over 70 columns there. Suppose that we wanted to process this to find out how much time is spent loading Javascript data. Our first step is to introduce the CSV file to **Star** which we can do with a special macro:

import metaCSV.

worksheet{

generateCSV Wpt from "file:WPT_Sample.csv".

...

}

The generateCSV line is a macro that parses the sample CSV file, constructs a type (Wpt) that reflects the entries in the file and a parser that can parse similar CSV files into Wpt entries. The generated Wpt type looks like:

Wpt ::= Wpt{

Date:string.

...

URL:string.

'Response Code':integer.

'Time to Load (ms)':integer.

...

'Bytes In':integer.

...

};

One immediate feature to notice is that some of the field names are quoted. **Star** allows a variable (and by extension a field) identifier to have any characters in them -- so long as the identifier is quoted. This allows us to access ‘foreign’ data structures like this CSV file in a straightforward way.

Given the implicit generation of the type, and of a parser, we can use this to process real data files. For example, we can extract out from the CSV file records containing just the URLs, the file sizes and the load times using a query:

import metaCSV.

worksheet{

generateCSV Wpt from "file:WPT_Sample.csv".

wptData = WptParser("http:www.webpagetool.org/...csv").

extracted = list of { all

{ URL=D.URL

size=D.'Bytes In'

loadTime=D.'Time to Load (ms)'} where

D in wptData}

...

}

We used the generated parser to reach out to the website for the data and to parse the resulting content -- in a single high-powered statement.

A single run of the web page test may involve many separate browser actions -- the purpose of the tool is to test the performance of a website, which needs many trials to achieve statistical significance. So a better organization of the data is to categorize the raw data by URL. We can do this using a group by query:

import metaCSV.

worksheet{

generateCSV Wpt from "file:WPT_Sample.csv".

wptData = WptParser("http:www.webpagetool.org/...csv").

extracted = list of { all

{ URL=D.URL.

size=D.'Bytes In'.

loadTime=D.'Time to Load (ms)'} where

D in wptData} group by ((X)=>X.URL)

...

}

The group by operator takes a collection, and a categorization function, are produces a `map` of collections.

We want to produce average load times and standard deviations of the load times -- to smooth out the vagaries of the Internet. For now, we will assume that we have average and stddev functions that have type signatures:

average:all c,e ~~ stream[c->>e] |:(c,(e=>float))=>float.

stddev:all c,e ~~ stream[c->>e] |:(c,(e=>float))=>float.

I.e., we are assuming functions that take collections, and an ‘accessor’ function, and return the average and standard deviation respectively.

Given these functions, we can compute our statistics using:

import metaCSV.

import stats.

worksheet{

generateCSV Wpt from "file:WPT_Sample.csv".

wptData = WptParser("http:www.webpagetool.org/...csv").

extracted = list of { all

{ URL=D.URL.

size=D.'Bytes In'.

loadTime=D.'Time to Load (ms)'} where

D in wptData} group by ((X)=>X.URL)

ldTime:(Wpt)=>float.

ldTime(D) => D.loadTime::float.

show list of { all (K,average(V,ldTime),stddev(V,ldTime)) where

K->V in extracted }

}

The query condition:

K->V in extracted

is analogous to the regular search condition:

```
D in wptData
```
except that it is used to search within a `map`-based collection. The pattern K->V matches the successive key/value pairs in the `map`.

That is it! The final query should get output along the lines of:

```
...
("/o/oauth2/auth?...", 337.0, 0.0),
("/main-thumb-58380181-100-yqpttun...", 101.18518518519, 24.41468441456),
("/main-thumb-49759239-100-pcgldxn...",93.48148148148, 19.03285636867),
...
```

Notice that most of the remaining complexity in this example related to selecting the right parts of the data to pick up and process.[^fn1]

[^fn1]: A standard deviation of 0.0 is likely a signal that the indicated URL only occurred once in the sample data.
