Creating Closure from string

help
#1

This is a simple question that probably has a complex answer.

given the some string like:

let infix = "x ^ 2 + 3";

how would I mutate it into a closure like:

let closure = |x: <T>| -> <T> { x.powf(2) + 3 }

I currently have my project using a shunting yard and rpn calculator, but it has massive failures in scalability

#2

You’re basically talking about writing a mini-compiler. If the source strings are all literals, you could probably write it as a procedural macro but there’s no easy way if you get the strings at runtime.

Your current solution doesn’t sound like a particularly inefficient approach, but the details matter a lot. Can you show some of the code you’re using?

#3

I'm using the now abandoned eval crate. It's enough for my simple use case.

#4 
pub unsafe extern "C" fn coord_vector_maker (input: *const c_char, x_lower: f64, x_upper: f64, y_lower: f64, y_upper: f64, x_precision: f64, y_precision: f64) ->  *mut CoordPair<f64> {
    let input_c_str: &CStr = CStr::from_ptr(input);
    let str_slice: &str = input_c_str.to_str().unwrap();
    let expression: String = str_slice.to_owned(); 
    
    let x_all : Vec<f64> = x_vector_maker(x_lower, x_upper, x_precision);
    let y_all : Vec<f64> = round_y_to_precision(func_of_x(expression, x_lower, x_upper, x_precision, y_lower, y_upper), y_precision);
    let x_ptr = x_all.as_ptr();
    let y_ptr = y_all.as_ptr();
    let c_out = CoordPair::new(x_ptr, y_ptr);
    
    Box::into_raw(Box::new(c_out))
}

pub fn func_of_x (expression: String, x_lower: f64, x_upper: f64, x_precision: f64, y_lower: f64, y_upper: f64) -> Vec<f64> {
    let ys: Vec<f64> = make_all_x_strings(expression, x_lower, x_upper, x_precision).into_iter().map(|expr| infix_calculator(expr) as f64).collect();
    ys //.into_iter().map(|y| if y >= y_lower && y <= y_upper  { y } else { std::f64::NAN } ).collect()
}

pub fn infix_calculator(expression: String) -> f64 {
    let mut s: s_y::ShuntingYard = s_y::ShuntingYard::new();
    assert_eq!(s.calculate("2 + 3").unwrap(), 5.0);
    let r: Result<f64, Vec<String>> = s.calculate(&expression);
    match r {
        Ok(result) => result,
        Err(e) => {
            println!("Errors: {:?}", e);
            f64::NAN
        }
    }
}

this particular part is very ugly

pub fn make_all_x_strings (expression: String, x_lower: f64, x_upper: f64, x_precision: f64) -> Vec<String> {
    let x_fl_vector = x_vector_maker(x_lower, x_upper, x_precision);
    let x_string_vector: Vec<String> = x_fl_vector.into_iter().map(|x| expression.replace("x", &x.to_string())).collect();
    x_string_vector
}

and unfortunately they are given "at runtime", the rust part of this is a stateless backend for a dart application

#5

unfortunately, I've looked at that one myself, forget why, but it didn't meet requirements for one reason or another

#6

It looks like you’re working directly with Strings throughout. I suspect it’s more efficient to tokenize the string into a vector of enums first and work with that instead:

enum Token {
    Operator(char),
    Literal(f64),
    Variable(char)  // or String if necessary
}

It probably also makes sense to have an intermediate representation after you’ve transformed the expression into postfix but before you calculate the final result: That way you can parse each expression once and then calculate it with different variable values.

1 Like
#7

I do have them as tokens in the shunting yard part.

pub enum Token {   
    Operator(char, u32, u32),   // Operator, associativity, precedence
    Variable(char),
    WholeNumber(i64),
    DecimalNumber(f64),
    FunctionCall(String),
    Comma,
    LeftParenthesis,
    RightParenthesis,
    Whitespace
}

making that intermediate representation is the part I'm having a nightmare doing really.
specifically that variable token in keeping me awake at night.

to clarify, the current goal is to find roots of a polynomial, the graphing vector part was just an example to show how it can end up scaling up quickly. Currently, just trying to find the root of x^2 is taking 2 minutes with bounds of [-2,2] and a precision of 0.000_1 on a decent computer. This will eventually be running on a phone with far less memory and processing

edit:
and the precision[epsilon] would preferably be

right_hand_side / (2.0 as f64).powf(51.0)

which is much smaller

#8

I don't mind writing a whole big parser to represent things correctly e.g.

x^2 -> x.powf(2)

Im mostly trying to turn these into 'actual code' from a string

or if there's a better way to do this that would be fine as well, I'm not married to closures

#9

IIRC, there efficient ways to do this involving differentiation, e.g. Newton’s method.

#10

I was planning that, the autodiff crate happens to require a closure, that's actually where the question started

#11

I see. Symbolic differentiation would be an option, too.

#12

You’re basically talking about writing a mini-compiler

where would one begin to do this (or is it even possible given the the platform reqs)

in the same vein, I know rust is coded in rust, where can I find the source code for a closure, maybe I can use that with a parser to create closures automagically

#13

Not sure that pulling in LLVM would be a smart choice, however I know the people who make cranelift have been able to get live code compilation working (JIT).

This is most likely what you're looking for, since cranelift is (don't take my word for this) from what I've heard lightweight.

Obviously, you could always implement an extremely fast interpreter/formula re-arranger, instead of trying to generate machine code at runtime.

2 Likes
#14

2 minutes for the bounds stated really sounds like you're doing some sort of re-parsing or similar every time you try a new value. You can try to boil things down to structures which can evaluate at a given value, or if you really need the flexibility of composing closures, you could look to creating Box dyn Fn instead.

Playground

However, you're never going to get something fast enough to look at 2^51 values, even if you made something that compiled to machine code on the fly. If you want values that exact, you'll almost surely need a higher level algorithmic approach, like @steffahn suggested.

1 Like
#15

building them into structures is definitely the way to go, now to try and make an abstraction of all mathematical equations :joy:

you were right on the money about it reparsing each time, the shunting yard was built to be used for (effectively) a calculator, so it was never intended for use at this scale. I was basically trying to figure out a clever way to make it obsolete

#16

I've used the evalexpr crate before, in toy things. If this isn't a toy thing of some sort, I'd seriously question whether this sort of thing is a good idea.

#17

I’ve taken this opportunity to try out using a parser combinator library for the first time in Rust. My code is here:

I’m not sure what the optimal evaluation strategy is for creating a closure apart from actually using a compiler / JIT compilation, one would need to benchmark those probably; but the tree data-structure can still serve as an intermediate step for building the final representation used for evaluating these expressions. I’ve also sketched up a bit of symbolic differentiation. No guarantees that I didn’t mess anything up there.

2 Likes