Extended and not-necessarily-relational algebra

[julianhyde]

Allow the user to declare 'rewrite rules' that match patterns of operators in expressions, and apply those rewrite rules to optimize the expression.

This generalizes a relational algebra system. For example, Apache Calcite comes with the standard relational operators in the box (Scan, Project, Filter, Aggregate, Sort, Join, Union) and allows people to write rules that transform calls to those operators. For example, FilterJoinRule matches a Filter on top of a Join and transforms it to a Join with filters on one or more of its inputs.

In Calcite, as in any relational system, there is a huge difference between relational and ordinary expressions. Consider the (inner) Join operator and its three operands (left, right, condition). The relational operands (left and right) are called inputs, and the condition operand is a boolean expression operating on a record from the left and right. The output is also a relation.

In Morel, we can consider join and filter to be ordinary functions:

filter: {input: 'a list, condition: 'a -> boolean)} -> 'a list
join: {left: 'a list, right: 'b list, condition: ('a, 'b) -> boolean} -> ('a, 'b) list

and we can write a rewrite rule that matches a call to filter whose input operand is a call to join.

The relational system makes certain assumptions:

• the condition operands are never values, always constant lambdas that can be inspected by the rule;
• relations are unordered multisets of records; in contrast, Morel allows (see Should Morel's collection types indicate that a collection is sorted, unique, or has repeatable iteration order? #232) elements of types other than record, allows both ordered and unordered lists, and allows lists to have declared or deduced keys and functional dependencies.

But in Morel we can remove those assumptions, and apply rewrite rules to any functions. Let's sketch out the signature of a rule and of an engine to apply those rules.

(* An operand either matches any expression or matches an expression
 * with a N inputs, and supplies named operands for the inputs. *)
datatype operand =
     ANY
  | MATCH of {predicate: exp -> boolean, (string * operand) list: inputs};

(* Adds a rule. A rule has a name, a root operand, and a function that the
 * engine should call when the rule is matched. *)
val addRule: {name: string, operand: operand, apply: exp -> exp list} -> unit