aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBryan Newbold <bnewbold@robocracy.org>2021-11-11 17:08:15 -0800
committerBryan Newbold <bnewbold@robocracy.org>2021-11-11 17:08:15 -0800
commit4955c32416cc7a825475fe58cf7937c954537b43 (patch)
treee6555f7ac0709f59ba991b3bfc9f3f50c94968af
parent468bf78c172a483d8d6dd40a28230c9a3e771b94 (diff)
downloadcasual-4955c32416cc7a825475fe58cf7937c954537b43.tar.gz
casual-4955c32416cc7a825475fe58cf7937c954537b43.zip
notes on term rewriting
-rw-r--r--notes/term_rewriting.md54
1 files changed, 54 insertions, 0 deletions
diff --git a/notes/term_rewriting.md b/notes/term_rewriting.md
new file mode 100644
index 0000000..9d0255a
--- /dev/null
+++ b/notes/term_rewriting.md
@@ -0,0 +1,54 @@
+
+Syntax for term re-writing:
+
+ (rule <pattern>
+ <substitute>)
+
+Pattern examples:
+
+ (? a)
+ (? a number?)
+ (? a not-number?)
+ (? a number? odd?)
+ (? a (free? x))
+ (? a (neq? 0))
+
+ ; match zero or more into a list; expand list in-line, same order
+ (?* l)
+
+Full examples:
+
+ (rule (/ 1 (/ (? a) (? b)))
+ (/ (? b) (? a)))
+
+Simplifications:
+
+- variable names must be single Latin letter
+- predicates are fixed to a set of type checks
+
+## Implementation
+
+Separate rule lists, one for each "head" type (Sum, Product, Power, etc).
+
+ struct RuleSet {
+ sum_rules: Vec<Rule>,
+ product_rules: Vec<Rule>,
+ [...]
+ }
+
+ struct Rule {
+ variables: HashMap<type, char, Vec<predicates>>,
+ pattern: MatchExpr,
+ substitute: MatchExpr,
+ }
+
+ enum MatchExpr {
+ variable: char,
+ atom: CExpr,
+ list: { head: expr_type, tail: Vec<MatchExpr> },
+ }
+
+----------------
+
+Backburner:
+- are additional pattern-wide predicates necessary or helpful?