[−][src]Crate libslide
libslide is the core of slide, implementing the end-to-end processing of a slide program.
slide is described as a "static expression optimizer", which can be thought of as rougly equivalent
to an "expression simplifier". Both of these terms are ambiguous ideas reasonable people can
disagree on. For example, depending on the evaluation context, either x ^ 2 or x * x may be
"optimized" form of the same expression.
slide uses reasonable (operation-reducing) simplification rules to achieve this goal. Recognizing the ambiguities described above, slide also hopes to make optimization customizable on the side of the user.
This isn't the only design goal of slide; others include
- Simplification as a platform, where optimization rules are configurable plugins.
- Strong support for environments slide is most used in (e.g. LaTeX and ad-hoc interactive queries).
- Easy integration with text editors and language servers.
- Evaluation of mathematical statements even in ambiguous contexts.
slide is still far from being complete. Contributions of any kind are warmly welcomed, as they help us progress in the achievement of these goals.
The rest of this document discusses the architecture of slide.
A brief overview of slide's architecture
slide's design is very similar to a compiler front end, sans the type checking and ups the partial evaluation.
The parser is a simple, hand-written RD parser designed to produce nice error messages. The parser module supports both expressions and expression patterns.
Given a parsed expression, the evaluator loops application of string and function rules until no rule further reduces the expression. This is the most interesting part of slide, which we discuss in the next section.
Finally, the simplified expression is emitted. Currently slide supports a few emission strategies, and we are interested in adding more.
Evaluator
The partial_evaluator module loops the application of simplification rules on an expression until
a rule no longer reduces an expression.
Kinds of simplification rules
slide supports "string" and "function" rules. String rules are expression patterns mappings that describe how the rule should be applied to an expression. For example, the string rule
1 * _a -> _a
says "1 times any expression a yields the expression a". String rules are applied to an
expression by pattern matching the ASTs of the LHS of the string rule and the expression to be
simplified. If the matching is successful, the matches are substituted on the RHS of the string
rule. As an example, we apply the above rule on several expressions:
1 * (2 + v) -> (2 + v)
1 + (2 + v) -> no match!
(2 + v) * 1 -> no match!
The fact that the third expression fails to match with the rule demonstrates one weakness of string
rules. Another rule, _a * 1 -> _a, is needed to represent this case. (In practice, slide tries to
permute the commutativity of an expression to induce the application of string rules written in a
particular way, but this is not perfect).
String rules also have no way to represent evaluation. Since they are purely mappings of terms, there is no way to describe the operation of addition with a string rule.
Because of these limitations in string rules, slide also supports function rules. These are functions of the form
fn(expr: Expr) -> Option<Expr>
Function rules are much more powerful because they have access to an entire expression tree and can perform evaluations, but are responsible for their own pattern matching and more difficult to prove correctness for.
As a summary, string rules are easy to write and inject into a slide program, but are very limited in their application. Function rules are more difficult to write and prove correct, but are much more flexible.
Function rule evaluation modules
slide-internal function rules may use a number of other modules to aid evaluation. We list the most common ones here:
math: the math module is a collection of algorithms used in the evaluation of an expression, like polynomial division. This module is often developed independently with the goal of eventual use in slide rules. The math module provides shims for converting between expression representation and the data representations used by the math module's algorithms.flatten/fold: this module tries to normalize an expression with postconditions rules can rely on in their evaluation.roll/unroll: these are utility functions that unroll an expression into a list of terms, or roll a list up into an expression AST.
Normalization
It is useful to normalize expressions in to a consistent form that can be expected by function rules
(and to some extent string rules). The flatten/fold module provides expression normalization like
combining like terms, normalizing similar operations (e.g. subtractions become additions), and other
procedures whose postconditions rules can then rely on.
Normalization is optional, and should be disabled when a user disables simplification rules used in the normalization process.
Expression Representation
Expressions are primarily represented as interned ASTs. For example, the expression "1 + 1" parses to an AST that looks like something like
(+ <1>@common-1 <1>@common-1)
where <1>@common-1 is the expression 1 held at the example pointer address common-1.
The point here is that the common expression 1 is eliminated, and both references to 1 point to
the same underlying expression.
Because expressions are already held in boxed AST nodes, this interning process does not take an additional memory hit and provides several advantages, like skipping evaluation passes on identical expressions.
Glossary
String rules
Simplification rules that describe the mapping of an expression pattern in a string form. For example,
1 * _a -> _a
is a string rule that describes the simplification "1 times any expression a yields the expression
a".
String rules are easy to write, but are strict in what they match and cannot express evaluation.
Function rules
Function rules are functions with the signature
fn(expr: Expr) -> Option<Expr>
Function rules are given an expression and can perform arbitrary evaluation to try to simplify the expression. Function rules are responsible for matching the expression themselves.
Function rules are more difficult to write and prove correct, but are very flexible.
Expressions
Expressions are the inputs to a slide instance. For example, given the expression
2x + 3 + 4 + x
slide should emit the lowered expression 3x + 7.
Expression Patterns
Expression patterns describe the shape of a expression. Expression patterns are used by string rules to describe how a rule should be applied.
The syntax of expressions and expression patterns is nearly identical, but expression patterns have pattern metavariables rather than variables. The following patterns are available:
| pattern | matches |
|---|---|
#<name> | A constant |
$<name> | A variable |
_<name> | Any expression |
A metavariable can match exactly one expression. This means that if _a matches 1 + 2, all other
references to _a must match 1 + 2 as well.
Some examples of expression patterns and matching expressions:
| expression pattern | matches |
|---|---|
1 + #a | 1 + 5.2 |
#a + $a | 10 + v |
_a / $a * _a | (9 + 1) / v * (9 + 1) |
_a + _b * $c * #d | (x ^ 2) + (5 / y) * w * 15 |
Re-exports
pub use scanner::scan; |
pub use scanner::ScanResult; |
pub use scanner::Token; |
Modules
| collectors | Module |
| common | Common types used by libslide. |
| diagnostics | libslide's diagnostic module. |
| emit | Emit strategies for the libslide grammar IR. |
| evaluator_rules | Grammar->Grammar transforming rules, used by the partial_evaluator. |
| grammar | The primary libslide IR. |
| linter | Provides linter-like diagnostics for a slide program. |
| math | A collection of algorithms used by evaluation rules. |
| parser | Parses slide programs into the slide |
| partial_evaluator | libslide's heavy-lifting optimizer, applying simplification rules on the libslide IR. |
| scanner | Tokenizes slide programs and produces lexing diagnostics. |
| utils | Library utilities. |
| visit | Traits for visiting slide grammar trees. |
Macros
| intern_str | Interns a string. |
| parse_asgn | Parses an assignment. |
| parse_expr | Parses an expression. |
| parse_stmt | Parses a statement. |
| poly | Creates a new Poly. |
| rc_expr | Interns an expression. |
| rc_expr_pat | Interns an expression. |
Structs
| Assignment | An assignment. |
| BinaryExpr | A binary expression. |
| EmitConfig | Configuration options for emitting a slide grammar. |
| EvaluationResult | Describes the result of a slide program evaluation. |
| InternedStr | An interned String type. |
| ParseResult | Describes the result of parsing a slide program. |
| Poly | A polynomial in integer space Z. TODO: Currently, this container only services polynomials with non-negative degrees. |
| ProgramContext | A context for evaluating a slide program. |
| RcExpr | An reference-counted version of an expression. |
| Span | Describes the character span of a substring in a text. |
| Stmt | A statement in a slide program. |
| StmtList | A list of statements in a slide program. |
| UnaryExpr | A unary expression. |
Enums
| EmitFormat | The format in which a slide grammar should be emitted. |
| Expr | An expression. |
| ExprPat | A slide expression pattern. |
| StmtKind | The kind of a statement. |
Traits
| Emit | Implements the emission of a type in an EmitFormat. |
| Grammar | Describes a top-level item in the libslide grammar. |
| RcExpression | Describes a reference-counted slide expression. |
Functions
| build_rules | Given an evaluator context, builds a set of evaluator rules to be used in partial evaluation. |
| evaluate | Evaluates a list of statements to as simplified a form as possible for each. The evaluation may be partial, as some values (like variables) may be unknown. |
| evaluate_expr | Evaluates an expression to as simplified a form as possible. The evaluation may be partial, as some values (like variables) may be unknown. The returned expression is normalized. |
| lint_expr_pat | Lints a slide expression pattern. |
| lint_stmt | Lints a slide statement list. |
| parse_expression_pattern | Parses a tokenized slide expression pattern, emitting the result and any diagnostics. |
| parse_statements | Parses a tokenized slide program, emitting the result and any diagnostics. |