Nesting terms should be permitted and exploited

[timothyhinrichs]

As I've been writing Rego recently I've tried to embed terms inside each other, which seems to not be allowed. Besides it being natural to write rules with embedded terms, embedding terms should allow for improved efficiency during evaluation. I've been defining virtual docs that have dictionaries/arrays as outputs (e.g. {id: ..., name: ...}), and then want to use those virtual docs to ask if one of the outputs has a particular value for one of its fields (e.g. name: "foo").

Here's a contrived example of how we do that today. Notice that when we query p, we are iterating over all the values of p and checking if the first element is an "a".

q["a"] = 1 :- true
q["b"] = 2 :- true
p[x] :- q[y] = z, x=[y,z]
p[x], x=["a", y]
Enter data.repl.p[x], eq(x, ["a", y])
| Eval data.repl.p[x]
| Enter p[x]
| | Eval eq(data.repl.q[y], z)
| | Enter q["a"] = 1
| | | Eval true
| | | Exit q["a"] = 1
| | Eval eq(x, ["a", 1])
| | Exit p[["a", 1]]
| Eval eq(["a", 1], ["a", y])
| Exit data.repl.p[x], eq(x, ["a", y])
Redo data.repl.p[x], eq(x, ["a", y])
| Redo true
| Redo p[["a", 1]]
| | Redo eq(1, z)
| | Redo q["b"] = 2
| | | Eval true
| | | Exit q["b"] = 2
| | Eval eq(x, ["b", 2])
| | Exit p[["b", 2]]
| Eval eq(["b", 2], ["a", y])
| Fail eq(["b", 2], ["a", y])
+---------+---+
| x | y |
+---------+---+
| ["a",1] | 1 |
+---------+---+

It would be more efficient if the fact that the first value in the output is an "a" is pushed down into the computation of p so that we only compute the slice of p where every array is of the form ["a", y]. Here is how I would imagine this working in the future. I embedded 3 comments with // explaining the difference with the trace above.

q["a"] = 1 :- true
q["b"] = 2 :- true
p[[y,z]] :- q[y] = z // moved x=[y,z] into the head of the rule
p[["a", y]] // moved x=["a", y] into head of query
Enter data.repl.p[["a", y]]
| Eval data.repl.p[["a", y]]
| Enter p[["a", y]]
| | Eval eq(data.repl.q["a"], z)
| | Enter q["a"] = 1
| | | Eval true
| | | Exit q["a"] = 1
| | Eval eq(x, ["a", 1])
| | Exit p[["a", 1]]
| Eval eq(["a", 1], ["a", y])
| Exit data.repl.p[x], eq(x, ["a", y])
// used index to lookup just the q["a"] values, so not scanning thru all q data
Redo data.repl.p[x], eq(x, ["a", y])
| Redo true
| Redo p[["a", 1]]
| | Redo q["a"] = 1
| | Fail
| Fail data.repl.p[x], eq(x, ["a", y])
+---------+---+
| x | y |
+---------+---+
| ["a",1] | 1 |
+---------+---+