Traits for Lookup Tables

[lopeetall]

Currently we have a long and complicated src/lookup/lookup_table.rs with a lot of repeated code which generates lookup tables for add, mul, and xor. As suggested here by @CPerezz we should make a trait for lookup tables and have add, mul etc implement the trait. This can also address this comment from @bhgomes, as each lookup table can implement its own lookup function that knows which columns are to be considered "outputs", if any.

[bhgomes]

Here's an idea for a Lookup trait. It has a parameter Q called the query and depending on the query type, it has different completion types which represent the extra information that can be deduced from the given query:

trait Lookup<Q> {
    /// Completion Type
    ///
    /// This type is the corresponding completion for the query type `Q`.
    type Completion;

    /// Inserts a lookup query into the `compiler` returning the relevant completion for the query.
    fn lookup(&self, query: &Q, compiler: &mut StandardComposer) -> Option<Self::Completion>;
}

Here's a schematic example:

impl Lookup<Summands> for AddTable<3> {
    type Completion = Sum;

    fn lookup(&self, query: &Summands, compiler: &mut StandardComposer) -> Option<Self::Completion> {
        let row = self.find_row(query[0], query[1])?;
        compiler.assert_lookup(&self.table, row);
        Some(row[2])
    }
}

In this example, you have an arity-3 table called the AddTable which will look for a row with the given inputs query[0] and query[1] and return the row that they belong to (if it exists), in this case, row which is a row of the table so a vector of three elements where the third is the sum of the first two. It then asserts that a lookup should be registered in the constraint system and returns the completion which is the sum.

This can be made quite general I imagine for lots of kinds of queries. Since Q is a type parameter, a table can implement Lookup<Q> for many different Q. In some cases, if Q represents the entire relation underlying the lookup table, the completion should be () because there is no completion information.

However this trait is defined, we should think about how to handle the case of unknown (compile-time) vs known (proving-time) variables.

[lopeetall]

I'm working on this now because I want to get better with Rust and traits and I think this is a fairly manageable project to learn with. (But it's no problem if somebody beats me to the punch with a nice Lookup trait that resolves this issue)

[bhgomes]

Please go ahead! I don't think this is super urgent and it's good to take careful time designing APIs and definitely a good learning example.