# On-Demand Relations

There are often times relations/predicates where you know that would not need to be fully computed.
This would include the infinite relations.
This means that, we want to define such relations without worrying about its infinite-ness while also being able to supply it with information needed for the computation.
Such relations are called **On-Demand Relations**.

We show here one on-demand relation which is the `fibonacci`

number relation:

```
type fib(bound x: i32, y: i32)
rel fib = {(0, 1), (1, 1)}
rel fib(x, y1 + y2) = fib(x - 1, y1) and fib(x - 2, y2) and x > 1
query fib(10, y)
```

Normally, if we define the fibonacci relation, it would only contain the second and the third line, which respectively defines the base cases and the recursive cases. However, as we all know, there are infinitely many fibonacci numbers and it would not be wise to compute the relation fully. Usually, we want to infer some fact inside of the infinite relation, based on some inputs. In this case, as noted on the last line, we want to know the 10th fibonacci number.

It is hinted that when we want to compute a fibonacci number, we usually supply the `x`

value, in this case, 10, in order to get the value `y`

.
This is exactly what we tell the compiler in the first line.
Inside of the type declaration, we provide an additional **adornment** to each of the variables.

`x`

is adorned by`bound`

, denoting that it is treated as an**input**(or**bounded**) variable to the relation`y`

is not adorned by anything, suggesting that it is a**free**variable which will be computed by the rules of the relation

Getting

`x`

based on`y`

is out-of-scope in this tutorial.

By providing the adornments (with at least one `bound`

), we are telling Scallop that the relation should be computed *on-demand*.
From there, Scallop will search for every place where the relation is **demanded**, and restrict the computation of the relation only on the demand.

In our case, there is just one single place where the `fib`

relation is demanded (where `x`

is `10`

).
Therefore, Scallop will compute only the necessary facts in order to derive the final solution.

## Adornments

There are only two kinds of adornments:

`bound`

`free`

Annotating whether the variable is treated as *bounded* variable or *free* variable.

If an adornment is not provided on a variable, then it is by default a `free`

variable.
In this sense, all normal relations without any adornment would be treated as **non**-on-demand relations.

When at least one `bound`

adornment is annotated on a relation type declaration, we know that the relation needs to be computed *on-demand*.

## More Examples

### On-Demand Path

Let's go back to our example of edge-and-path. Consider that there is a huge graph, but we only want to know a path ending at a specific node:

```
rel path(a, b) = edge(a, b) or (edge(a, c) and path(c, b))
query path(a, 1024)
```

In this case, enumerating all paths would be strictly more expensive than just exploring from the end point.
Therefore, we add an adornment to the `path`

relation like the following:

```
type path(free i32, bound i32)
```

We say the second argument is `bound`

and the first argument is `free`

, matching what we expect from the query.

### On-Demand To-String

Let's consider an simple arithmetic expression language and a `to_string`

predicate for the language:

```
type Expr = Const(i32) | Var(String) | Add(Expr, Expr) | Sub(Expr, Expr)
rel to_string(e, $format("{}", i)) = case e is Const(i)
rel to_string(e, $format("{}", v)) = case e is Var(e)
rel to_string(e, $format("({} + {})", s1, s2)) = case e is Add(e1, e2) and to_string(e1, s1) and to_string(e2, s2)
rel to_string(e, $format("({} - {})", s1, s2)) = case e is Sub(e1, e2) and to_string(e1, s1) and to_string(e2, s2)
```

Now that let's say there are many expressions declared as constants:

```
const EXPR_1 = Add(Const(1), Add(Const(5), Const(3)))
const EXPR_2 = Add(Const(1), Var("x"))
const EXPR_3 = Const(13)
```

Scallop would have automatically generated string for all of the expressions.

However, let's say we are only interested in one of the expressions:

```
query to_string(EXPR_3, s)
```

Then most of the computations for `to_string`

would be redundant.

In this case, we would also declare `to_string`

as an on-demand predicate, like this:

```
type to_string(bound Expr, String)
```

Then only the queried expression will be `to_string`

-ed.

## Internals

Internally, when there are relations being annotated with adornments, the whole Scallop program is undergone a program transformation.
This transformation is traditionally called **Magic-Set Transformation** or **Demand Transformation**.
There are multiple papers on the topic, which we reference below: