aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBryan Newbold <bnewbold@robocracy.org>2021-11-13 16:02:14 -0800
committerBryan Newbold <bnewbold@robocracy.org>2021-11-13 16:03:09 -0800
commit6666f23e6b8a54e402f2aaf9e64f658f3d7fae29 (patch)
treea6ff2dd408086866aa66b2f14c613257c4703463
parent4955c32416cc7a825475fe58cf7937c954537b43 (diff)
downloadcasual-6666f23e6b8a54e402f2aaf9e64f658f3d7fae29.tar.gz
casual-6666f23e6b8a54e402f2aaf9e64f658f3d7fae29.zip
initial work on term rewrite rule parsingHEADmaster
-rw-r--r--src/lib.rs2
-rw-r--r--src/rewrite.rs216
2 files changed, 218 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs
index 4137840..609dc79 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2,9 +2,11 @@ use std::io;
use std::io::Write;
mod cexpr;
+mod rewrite;
mod sexpr;
pub use cexpr::{CExpr, CNumber};
+pub use rewrite::Rule;
pub use sexpr::{sexpr_parse_file, SExpr};
pub type Result<T, E = String> = std::result::Result<T, E>;
diff --git a/src/rewrite.rs b/src/rewrite.rs
new file mode 100644
index 0000000..eb45640
--- /dev/null
+++ b/src/rewrite.rs
@@ -0,0 +1,216 @@
+/*
+ * Minimal term re-writing system
+ */
+
+use crate::cexpr::{CExpr, CNumber};
+use crate::sexpr::SExpr;
+use crate::Result;
+use std::collections::HashMap;
+
+// for now these are hard coded
+#[derive(Clone, PartialEq, Debug)]
+pub enum RulePredicate {
+ IsNumber,
+ IsSymbol,
+ IsInteger,
+ IsEven,
+ IsOdd,
+ IsPositive,
+ IsNegative,
+}
+
+#[derive(Clone, PartialEq, Debug)]
+pub enum CExprType {
+ Sum,
+ Product,
+ Factorial,
+ Exponential,
+ UnaryFunction(String),
+}
+
+#[derive(Clone, PartialEq, Debug)]
+pub enum RuleExpr {
+ Var(char),
+ VarList(char),
+ Atom(CExpr),
+ List(CExprType, Vec<RuleExpr>),
+}
+
+#[derive(Clone, PartialEq, Debug)]
+pub struct Rule {
+ variables: HashMap<char, Vec<RulePredicate>>,
+ pattern: RuleExpr,
+ substitute: RuleExpr,
+}
+
+impl RulePredicate {
+ pub fn from_sexpr(sexpr: &SExpr) -> Result<RulePredicate> {
+ use RulePredicate::*;
+ match sexpr {
+ SExpr::SIdentifier(v) => match v.as_str() {
+ "number?" => Ok(IsNumber),
+ "symbol?" => Ok(IsSymbol),
+ "integer?" => Ok(IsInteger),
+ "even?" => Ok(IsEven),
+ "odd?" => Ok(IsOdd),
+ "positive?" => Ok(IsPositive),
+ "negative?" => Ok(IsNegative),
+ _ => Err(format!("not a known predicate: {:?}", sexpr)),
+ },
+ _ => Err(format!("not a known predicate: {:?}", sexpr)),
+ }
+ }
+
+ pub fn check(self, cexpr: &CExpr) -> bool {
+ use CExpr::*;
+ use CNumber::*;
+ use RulePredicate::*;
+ match (self, cexpr) {
+ (IsNumber, Number(_)) => true,
+ (IsSymbol, Symbol(_)) => true,
+ (IsInteger, Number(Integer(_))) => true,
+ (IsEven, Number(Integer(n))) => n % 2 == 0,
+ (IsOdd, Number(Integer(n))) => n % 2 == 1,
+ (IsPositive, Number(Integer(n))) => n >= &0,
+ (IsNegative, Number(Integer(n))) => n < &0,
+ _ => false,
+ }
+ }
+}
+
+fn extract_vars(sexpr: &SExpr) -> Result<Option<HashMap<char, Vec<RulePredicate>>>> {
+ let slist = match sexpr {
+ SExpr::SList(l) => l,
+ _ => return Ok(None),
+ };
+ if matches!(slist.as_slice(), [SExpr::SIdentifier(head), SExpr::SIdentifier(var_name), ..] if head == "?" && var_name.len() == 1)
+ {
+ if let [SExpr::SIdentifier(_), SExpr::SIdentifier(var_name), pred_list @ ..] =
+ slist.as_slice()
+ {
+ let predicates: Vec<RulePredicate> = pred_list
+ .iter()
+ .map(|v| RulePredicate::from_sexpr(v))
+ .collect::<Result<Vec<RulePredicate>>>()?;
+ // TODO: why did HashMap::from([(c, predicates)]) not work here? rustc version?
+ let mut hm = HashMap::new();
+ hm.insert(var_name.chars().nth(0).unwrap(), predicates);
+ return Ok(Some(hm));
+ }
+ }
+ let sub_vars = slist.iter().filter_map(|v| extract_vars(v).unwrap()).fold(
+ HashMap::new(),
+ |mut acc, hm| {
+ acc.extend(hm);
+ acc
+ },
+ );
+ if sub_vars.is_empty() {
+ return Ok(None);
+ } else {
+ return Ok(Some(sub_vars));
+ }
+}
+
+impl RuleExpr {
+ pub fn from_sexpr(sexpr: &SExpr) -> Result<RuleExpr> {
+ // not all cases are handled; some atoms are covered trivialy
+ match sexpr {
+ SExpr::SNull | SExpr::SBoolean(_) | SExpr::SString(_) => {
+ Err("unhandled s-expr atoms; expected rule pattern".to_string())
+ }
+ SExpr::SInteger(_) | SExpr::SFloat(_) | SExpr::SIdentifier(_) => {
+ Ok(RuleExpr::Atom(CExpr::from_sexpr(sexpr)?))
+ }
+ SExpr::SList(list) => {
+ if let [SExpr::SIdentifier(ident), rest @ ..] = list.as_slice() {
+ match (ident.as_str(), rest.len()) {
+ ("?", 1..=5000) => {
+ if let SExpr::SIdentifier(var_name) = &rest[0] {
+ Ok(RuleExpr::Var(var_name.chars().nth(0).unwrap()))
+ } else {
+ Err("expected single-character pattern name".to_string())
+ }
+ }
+ ("?*", 1..=5000) => {
+ if let SExpr::SIdentifier(var_name) = &rest[0] {
+ Ok(RuleExpr::VarList(var_name.chars().nth(0).unwrap()))
+ } else {
+ Err("expected single-character pattern name".to_string())
+ }
+ }
+ ("factorial", 1) => Ok(RuleExpr::List(
+ CExprType::Factorial,
+ rest.iter()
+ .map(|v| RuleExpr::from_sexpr(v))
+ .collect::<Result<Vec<RuleExpr>>>()?,
+ )),
+ ("cos" | "sin" | "tan", 1) => Ok(RuleExpr::List(
+ CExprType::UnaryFunction(ident.to_string()),
+ rest.iter()
+ .map(|v| RuleExpr::from_sexpr(v))
+ .collect::<Result<Vec<RuleExpr>>>()?,
+ )),
+ ("^", 2) => Ok(RuleExpr::List(
+ CExprType::Exponential,
+ rest.iter()
+ .map(|v| RuleExpr::from_sexpr(v))
+ .collect::<Result<Vec<RuleExpr>>>()?,
+ )),
+ ("+", 2..=5000) => Ok(RuleExpr::List(
+ CExprType::Sum,
+ rest.iter()
+ .map(|v| RuleExpr::from_sexpr(v))
+ .collect::<Result<Vec<RuleExpr>>>()?,
+ )),
+ ("*", 2..=5000) => Ok(RuleExpr::List(
+ CExprType::Product,
+ rest.iter()
+ .map(|v| RuleExpr::from_sexpr(v))
+ .collect::<Result<Vec<RuleExpr>>>()?,
+ )),
+ _ => Err("unhandled rule expression type".to_string()),
+ }
+ } else {
+ Err("unhandled rule expression type".to_string())
+ }
+ }
+ }
+ }
+}
+
+impl Rule {
+ pub fn from_sexpr(sexpr: &SExpr) -> Result<Rule> {
+ let slist = match sexpr {
+ SExpr::SList(l) => l,
+ _ => return Err("expected a rule".to_string()),
+ };
+ let (pattern, substitute) =
+ if let [SExpr::SIdentifier(name), pattern, substitute] = slist.as_slice() {
+ if name != "rule" {
+ return Err("expected a rule".to_string());
+ }
+ (pattern, substitute)
+ } else {
+ return Err("expected a rule".to_string());
+ };
+
+ // extract vars and predicates from pattern
+ let vars = match extract_vars(&pattern)? {
+ Some(hm) => hm,
+ None => HashMap::new(),
+ };
+
+ // parse pattern and substitute as RuleExpr
+ Ok(Rule {
+ variables: vars,
+ pattern: RuleExpr::from_sexpr(&pattern)?,
+ substitute: RuleExpr::from_sexpr(&substitute)?,
+ })
+ }
+
+ pub fn from_str(raw: &str) -> Result<Rule> {
+ let ast = SExpr::from_str(raw)?;
+ Rule::from_sexpr(&ast)
+ }
+}