Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizing a Math Expression Parser in Rust

rpallas.xyz

Post reply on HN
Print view View original

21–30 of 60 posts

Re: Optimizing a Math Expression Parser in Rust

#21

Post by felixnavid »

amelius wrote: post #7

Can somebody explain this line: n => Token::Operand(n.parse().unwrap()), How does the compiler derive the type of n?

`n` is the same type as `s` from "match s" and 'n' is just `s` but renamed, if none of the previous conditions passed.

Because `match ` could have contained an expression, you might need to handle a "catch all" case where you can refer to the result of that expression.

The code could have been `match s.doSomething() { ...`. The lines above what you have quoted just compare the result to a couple of a constants. If none are true, the line that you have quoted is equivalent to renaming the result of that expression to `n` and then handling that case.

Re: Optimizing a Math Expression Parser in Rust

#22

Post by tialaramex »

amelius wrote: post #12
tialaramex wrote: post #9

Earlier quoted context omitted.

We're doing a pattern match, so, this variable n has to be something that matches the entire value matched, its type will be identical to the type of the value matched, s a few lines earlier. That value is an item from the iterator we got from calling split_whitespace() and split_whitespace() returns a SplitWhiteSpace, a custom iterator whose items are themselves sub-strings of the input string with (no surprise) no…

Aha. But what type does n.parse() have then, and how does the compiler derive it?

In this case the compiler actually first wants the type for a parameter to the function Token::Operand

That function is not shown, but it is included in the full source code which was linked. Well, technically we need to know that Rust says if there's a sum type Token::Operand which has an associated value, we can always call a function to make a Token::Operand with that value, and it just names this function Token::Operand too.

So, Token::Operand takes an i32, a 32-bit signed integer. The compiler knows we're eventually getting an i32 to call this function, if not our program isn't valid.

Which means n.parse().unwrap() has the type i32

We know n is an &str, the &str type has a generic function parse(), with the following signature:

    pub fn parse(&self) -> Result::Err> where F: FromStr
So the type you now care about, that of n.parse() has to be Result of some kind, and we're going to call Result::unwrap() on that, to get an i32

This can only work if the type F in that generic signature above is i32

Which means the new type you care about was Result and the parse function called will be the one which makes Ok(i32) when presented an in-range integer.

Edited: Word-smithing, no significant change of meaning.

Re: Optimizing a Math Expression Parser in Rust

#23

Post by catfacts »

VGHN7XDuOXPAzol wrote: post #18
catfacts wrote: post #6

I am not even a newbye in Rust and also this could be just nitpicking, but it seems that match is comparing strings and not characters, if this is the case then I think Common Lisp can optimize more, since there is a special comparison for characters in CL. Edited: In the optimized version the author use bytes and generators and avoid using strings. I don't know if Rust generators are optimized for speed or memory, i…

> what happens when there is an error reading the file? the question mark `?` denotes the fact that the error is bubbled up (kind of like an exception, but with stronger typing and less silent)

Thanks for the info. I imagine that in this care, since it seems the error is not captured, it should end producing panic. So a question mark is used when the expected result is of type Result or Error. Also the web page, https://doc.rust-lang.org/rust-by-example/error/result.html, describe the result type as Ok(T) or Err(E), and indicates that is a richer version of Option.

Re: Optimizing a Math Expression Parser in Rust

#24

Post by catfacts »

VGHN7XDuOXPAzol wrote: post #17
catfacts wrote: post #6

I am not even a newbye in Rust and also this could be just nitpicking, but it seems that match is comparing strings and not characters, if this is the case then I think Common Lisp can optimize more, since there is a special comparison for characters in CL. Edited: In the optimized version the author use bytes and generators and avoid using strings. I don't know if Rust generators are optimized for speed or memory, i…

If you wanted to match on characters (`char`s) then you could do this with single quotes (`'+'`) Or if you wanted to do it on bytes, you could also do this, with (`b'+'`). Unsure if that would provide a meaningful boost or not

Thanks for all the information you provided. I will read Rust by Example and stop posting in this thread to avoid deviating from the OP. Anyway, perhaps other readers are learning Rust and having the same questions in their minds, so your answers are also welcome for them.

Edited: I will eliminate my catfacts username (changing passsord to a random one), I don't like being downvoted and I know I should not mention it, but things are what they are. Good bye catfacts !.

Re: Optimizing a Math Expression Parser in Rust

#25

Post by sondr3 »

amelius wrote: post #7

Can somebody explain this line: n => Token::Operand(n.parse().unwrap()), How does the compiler derive the type of n?

If you've never been exposed to a Hindley-Milner type system[1] it can seem a bit magical, but it essentially works by trying to figure out the types from the inside and out by inferring usage all the way to the top. The type of `n` however is `&str`, but I take it you mean the matching. `n.parse()` can be anything that implements `FromStr`, but `Token::Operand` can only take a `u32`, so it can immediately infer that the result of `n.parse().unwrap()` must be `u32` (`n.parse()` is a `Result`).

[1]: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_sy...

Re: Optimizing a Math Expression Parser in Rust

#26

Post by VGHN7XDuOXPAzol »

catfacts wrote: post #23
VGHN7XDuOXPAzol wrote: post #18

Earlier quoted context omitted.

> what happens when there is an error reading the file? the question mark `?` denotes the fact that the error is bubbled up (kind of like an exception, but with stronger typing and less silent)

Thanks for the info. I imagine that in this care, since it seems the error is not captured, it should end producing panic. So a question mark is used when the expected result is of type Result or Error. Also the web page, https://doc.rust-lang.org/rust-by-example/error/result.html , describe the result type as Ok(T) or Err(E), and indicates that is a richer version of Option.

Yeah, if `main` returns an error I think it exits with an error code and prints it out, so quite similar to a panic.

I think the blog post is not focussing on error handling too much, but in any case this is 'safe', just could likely be handled better in a real-world case.

Re: Optimizing a Math Expression Parser in Rust

#27

Post by zokier »

> We’re paying a cost for each split_whitespace call, which allocates intermediate slices.

This part seems bit confused, I don't think `split_whitespace` does any allocations. I wish there were few intermediary steps here, e.g. going from &str and split_whitespace to &[u8] and split.

The tokenizer at that point is bit clunky, it is not really comparable to split_whitespace. The new tokenizer doesn't actually have any whitespace handling, it just assumes that every token is followed by exactly one whitespace. That alone might explain some of the speedup.

Re: Optimizing a Math Expression Parser in Rust

#28

Post by biorach »

catfacts wrote: post #6

I am not even a newbye in Rust and also this could be just nitpicking, but it seems that match is comparing strings and not characters, if this is the case then I think Common Lisp can optimize more, since there is a special comparison for characters in CL. Edited: In the optimized version the author use bytes and generators and avoid using strings. I don't know if Rust generators are optimized for speed or memory, i…

> I should stop comparing Rust to CL, better learn Rust first

Yes

Re: Optimizing a Math Expression Parser in Rust

#29

Post by thrance »

tialaramex wrote: post #2

This reminds me I should actually write a "natural" arithmetic expression parser for my Rust crate realistic Right now, realistic can parse "(* (^ 40 0.5) (^ 90 0.5))" and it will tell you that's 60, because yeah, it's sixty, that's how real arithmetic works. But it would be nice to write "(40^0.5) * (90^0.5)" or similar and have that work instead or as well. The months of work on realistic meant I spent so long with…

I think having a polish notation parser is good enough for math-y applciations, I wouldn't worry about it too much if I were you. Nice crate by the way!
Post reply on HN