aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/cexpr.rs223
1 files changed, 169 insertions, 54 deletions
diff --git a/src/cexpr.rs b/src/cexpr.rs
index 1971feb..b183c4a 100644
--- a/src/cexpr.rs
+++ b/src/cexpr.rs
@@ -1,8 +1,7 @@
/*
- * Canonical Expressions
+ * "Canonical" Expressions
*
* AKA, simplified, normalized algebraic expressions.
- *
*/
use crate::sexpr::SExpr;
@@ -10,25 +9,30 @@ use std::fmt;
#[derive(Debug, Clone, PartialEq, PartialOrd)]
pub enum NumericConstant {
- Pi, // 3.141592...
- E, // 2.718281...
+ Pi,
+ E,
+ GoldenRatio,
}
impl NumericConstant {
- pub fn as_number(&self) -> CNumber {
- use CNumber::*;
- use NumericConstant::*;
- match self {
- Pi => Float(3.141592f64),
- E => Float(2.718281f64),
+ /*
+ pub fn as_number(&self) -> CNumber {
+ use CNumber::*;
+ use NumericConstant::*;
+ match self {
+ Pi => Float(3.14159265358979323846f64),
+ E => Float(2.71828182845904523536f64),
+ GoldenRatio => Float(1.61803398874989484820f64),
+ }
}
- }
+ */
pub fn as_string(&self) -> String {
use NumericConstant::*;
match self {
Pi => "pi".to_string(),
E => "e".to_string(),
+ GoldenRatio => "golden-ratio".to_string(),
}
}
}
@@ -53,6 +57,46 @@ impl CNumber {
CNumber::Float(v) => Ok(SExpr::SFloat(*v)),
}
}
+
+ pub fn sum(&self, other: &CNumber) -> CNumber {
+ use CNumber::*;
+ match (self, other) {
+ (Integer(a), Integer(b)) => Integer(a + b),
+ (Integer(i), Rational(n, d)) | (Rational(n, d), Integer(i)) => Rational(n + d * i, *d),
+ (Rational(a, b), Rational(c, d)) if b == d => Rational(a + c, *d),
+ (Rational(a, b), Rational(c, d)) => Rational(a * d + c * b, b * d),
+ (Float(a), Float(b)) => Float(a + b),
+ (Integer(i), Float(f)) | (Float(f), Integer(i)) => Float((*i as f64) + f),
+ (Rational(n, d), Float(f)) | (Float(f), Rational(n, d)) => {
+ Float(f + (*n as f64) / (*d as f64))
+ }
+ }
+ }
+
+ pub fn product(&self, other: &CNumber) -> CNumber {
+ use CNumber::*;
+ match (self, other) {
+ (Integer(0), _) | (_, Integer(0)) => Integer(0),
+ (Integer(a), Integer(b)) => Integer(a * b),
+ (Integer(i), Rational(n, d)) | (Rational(n, d), Integer(i)) => Rational(i * n, *d),
+ (Rational(a, b), Rational(c, d)) if a == d && b == c => Integer(1),
+ (Rational(a, b), Rational(c, d)) => Rational(a * c, b * d),
+ (Float(a), Float(b)) => Float(a * b),
+ (Integer(i), Float(f)) | (Float(f), Integer(i)) => Float((*i as f64) * f),
+ (Rational(n, d), Float(f)) | (Float(f), Rational(n, d)) => {
+ Float(f * (*n as f64) / (*d as f64))
+ }
+ }
+ }
+
+ pub fn is_negative(&self) -> bool {
+ use CNumber::*;
+ match self {
+ Integer(i) => *i < 0,
+ Rational(n, _) => *n < 0,
+ Float(f) => *f < 0.0f64,
+ }
+ }
}
#[derive(Clone, PartialEq, PartialOrd)]
@@ -68,6 +112,16 @@ pub enum CExpr {
UnaryFunction(String, Box<CExpr>),
}
+fn compute_factorial(n: i64) -> i64 {
+ if n < 0 {
+ panic!("tried to compute negative factorial");
+ } else if n == 0 {
+ return 1;
+ } else {
+ return n * compute_factorial(n - 1);
+ }
+}
+
impl CExpr {
pub fn from_sexpr(sexpr: &SExpr) -> Result<CExpr, String> {
// not all cases are handled; some atoms are covered trivialy
@@ -76,10 +130,11 @@ impl CExpr {
SExpr::SBoolean(_) => Err("booleans not handled".to_string()),
SExpr::SInteger(v) => Ok(CExpr::Number(CNumber::Integer(*v))),
SExpr::SFloat(v) => Ok(CExpr::Number(CNumber::Float(*v))),
- SExpr::SString(_) => Err("null not handled".to_string()),
+ SExpr::SString(_) => Err("strings not handled".to_string()),
SExpr::SIdentifier(v) => match v.as_str() {
"pi" => Ok(CExpr::Constant(NumericConstant::Pi)),
"e" => Ok(CExpr::Constant(NumericConstant::E)),
+ "golden-ratio" => Ok(CExpr::Constant(NumericConstant::GoldenRatio)),
_ => Ok(CExpr::Symbol(v.to_string())),
},
SExpr::SList(l) => CExpr::from_sexpr_list(l),
@@ -87,10 +142,19 @@ impl CExpr {
}
pub fn from_sexpr_list(list: &Vec<SExpr>) -> Result<CExpr, String> {
+ use CExpr::*;
+ use CNumber::*;
+ use SExpr::*;
// https://adventures.michaelfbryan.com/posts/daily/slice-patterns/
if let [SExpr::SIdentifier(ident), rest @ ..] = list.as_slice() {
match (ident.as_str(), rest.len()) {
- ("factorial", 1) => Ok(CExpr::Factorial(Box::new(CExpr::from_sexpr(&rest[0])?))),
+ ("factorial", 1) => match CExpr::from_sexpr(&rest[0])? {
+ Number(n) if n.is_negative() => {
+ Err("negative factorial is not defined".to_string())
+ }
+ Number(Integer(i)) if i <= 18 => Ok(Number(Integer(compute_factorial(i)))),
+ other => Ok(Factorial(Box::new(other))),
+ },
("cos" | "sin" | "tan", 1) => Ok(CExpr::UnaryFunction(
ident.to_string(),
Box::new(CExpr::from_sexpr(&rest[0])?),
@@ -98,40 +162,43 @@ impl CExpr {
("^", 2) => {
let base = CExpr::from_sexpr(&rest[0])?;
let power = CExpr::from_sexpr(&rest[1])?;
- use CExpr::*;
- use CNumber::*;
match (base, power) {
(Number(Integer(0)), _) => Ok(Number(Integer(0))),
(Number(Integer(1)), _) => Ok(Number(Integer(1))),
(_, Number(Integer(0))) => Ok(Number(Integer(1))),
(base, Number(Integer(1))) => Ok(base),
+ (Number(Rational(1, d)), Number(Integer(-1))) => Ok(Number(Integer(d))),
+ (Number(Rational(n, d)), Number(Integer(-1))) => Ok(Number(Rational(d, n))),
+ (Exponent(base, p1), p2) => match (*p1, p2) {
+ (Number(n1), Number(n2)) => {
+ Ok(Exponent(base, Box::new(Number(n1.product(&n2)))))
+ }
+ (p1, p2) => {
+ Ok(Exponent(base, Box::new(CExpr::new_product(vec![p1, p2])?)))
+ }
+ },
(base, power) => Ok(Exponent(Box::new(base), Box::new(power))),
}
}
- ("/", 2) => {
- use CExpr::*;
- use CNumber::*;
- use SExpr::*;
- match (&rest[0], &rest[1]) {
- (_, SInteger(0)) => Err("division by zero".to_string()),
- (SInteger(0), _) => Ok(Number(Integer(0))),
- (se, SInteger(1)) => CExpr::from_sexpr(se),
- (SInteger(a), SInteger(b)) if a == b => Ok(Number(Integer(1))),
- (SInteger(a), SInteger(b)) if a % b == 0 => Ok(Number(Integer(a / b))),
- (SInteger(a), SInteger(b)) => Ok(Number(Rational(*a, *b))),
- (SInteger(1), b) => {
- let denom = CExpr::from_sexpr(b)?;
- Ok(Exponent(Box::new(denom), Box::new(Number(Integer(-1)))))
- }
- (a, b) => {
- let (numer, denom) = (CExpr::from_sexpr(a)?, CExpr::from_sexpr(b)?);
- CExpr::new_product(vec![
- numer,
- Exponent(Box::new(denom), Box::new(Number(Integer(-1)))),
- ])
- }
+ ("/", 2) => match (&rest[0], &rest[1]) {
+ (_, SInteger(0)) => Err("division by zero".to_string()),
+ (SInteger(0), _) => Ok(Number(Integer(0))),
+ (se, SInteger(1)) => CExpr::from_sexpr(se),
+ (SInteger(a), SInteger(b)) if a == b => Ok(Number(Integer(1))),
+ (SInteger(a), SInteger(b)) if a % b == 0 => Ok(Number(Integer(a / b))),
+ (SInteger(a), SInteger(b)) => Ok(Number(Rational(*a, *b))),
+ (SInteger(1), b) => {
+ let denom = CExpr::from_sexpr(b)?;
+ Ok(Exponent(Box::new(denom), Box::new(Number(Integer(-1)))))
}
- }
+ (a, b) => {
+ let (numer, denom) = (CExpr::from_sexpr(a)?, CExpr::from_sexpr(b)?);
+ CExpr::new_product(vec![
+ numer,
+ Exponent(Box::new(denom), Box::new(Number(Integer(-1)))),
+ ])
+ }
+ },
// TODO: how to make range unbounded? or less bounded?
("+", 2..=5000) => {
CExpr::new_sum(rest.iter().map(|v| CExpr::from_sexpr(v)).collect::<Result<
@@ -150,8 +217,6 @@ impl CExpr {
("-", 2) => {
let a = CExpr::from_sexpr(&rest[0])?;
let b = CExpr::from_sexpr(&rest[1])?;
- use CExpr::*;
- use CNumber::*;
match (a, b) {
(expr, Number(Integer(0))) => Ok(expr),
(Number(Integer(a)), Number(Integer(b))) => Ok(Number(Integer(a - b))),
@@ -171,27 +236,77 @@ impl CExpr {
}
}
- pub fn new_sum(mut list: Vec<CExpr>) -> Result<CExpr, String> {
+ pub fn new_sum(list: Vec<CExpr>) -> Result<CExpr, String> {
use CExpr::*;
use CNumber::*;
- list.sort_by(|a, b| a.partial_cmp(b).unwrap());
- match list.as_slice() {
- [Number(Integer(0)), e] => Ok(e.clone()), // XXX: remove clone()
- [Number(Integer(a)), Number(Integer(b))] => Ok(Number(Integer(a + b))),
- [Number(Integer(a)), Number(Rational(n, d))] => Ok(Number(Rational(n + a * d, *d))),
- _ => Ok(Sum(None, list)),
+ let (numeric, mut rest): (Vec<CExpr>, Vec<CExpr>) = list
+ .into_iter()
+ .flat_map(|e| match e {
+ Sum(None, l) => l,
+ Sum(Some(num), mut l) => {
+ l.push(Number(num));
+ l
+ }
+ e => vec![e],
+ })
+ .partition(|v| {
+ if let Number(Integer(_) | Rational(_, _)) = v {
+ true
+ } else {
+ false
+ }
+ });
+
+ let num: Option<CNumber> = numeric
+ .into_iter()
+ .map(|v| if let Number(n) = v { n } else { unreachable!() })
+ .reduce(|a, b| a.sum(&b));
+
+ rest.sort_by(|a, b| a.partial_cmp(b).unwrap());
+
+ match (num, rest) {
+ (None, mut rest) if rest.len() == 1 => Ok(rest.remove(0)),
+ (None, rest) if rest.is_empty() => unreachable!("empty list passed to new_product()"),
+ (Some(n), rest) if rest.is_empty() => Ok(Number(n)),
+ (Some(Integer(0)), rest) => Ok(Sum(None, rest)),
+ (n, r) => Ok(Sum(n, r)),
}
}
- pub fn new_product(mut list: Vec<CExpr>) -> Result<CExpr, String> {
+ pub fn new_product(list: Vec<CExpr>) -> Result<CExpr, String> {
use CExpr::*;
use CNumber::*;
- list.sort_by(|a, b| a.partial_cmp(b).unwrap());
- match list.as_slice() {
- [Number(Integer(1)), e] => Ok(e.clone()), // XXX: remove clone()
- [Number(Integer(a)), Number(Integer(b))] => Ok(Number(Integer(a * b))),
- [Number(Integer(a)), Number(Rational(n, d))] => Ok(Number(Rational(a * n, *d))),
- _ => Ok(Product(None, list)),
+ let (numeric, mut rest): (Vec<CExpr>, Vec<CExpr>) = list
+ .into_iter()
+ .flat_map(|e| match e {
+ Product(None, l) => l,
+ Product(Some(num), mut l) => {
+ l.push(Number(num));
+ l
+ }
+ e => vec![e],
+ })
+ .partition(|v| {
+ if let Number(Integer(_) | Rational(_, _)) = v {
+ true
+ } else {
+ false
+ }
+ });
+
+ let num: Option<CNumber> = numeric
+ .into_iter()
+ .map(|v| if let Number(n) = v { n } else { unreachable!() })
+ .reduce(|a, b| a.product(&b));
+
+ rest.sort_by(|a, b| a.partial_cmp(b).unwrap());
+
+ match (num, rest) {
+ (None, mut rest) if rest.len() == 1 => Ok(rest.remove(0)),
+ (None, rest) if rest.is_empty() => unreachable!("empty list passed to new_product()"),
+ (Some(n), rest) if rest.is_empty() => Ok(Number(n)),
+ (Some(Integer(1)), rest) => Ok(Product(None, rest)),
+ (n, r) => Ok(Product(n, r)),
}
}