• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed
• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection
• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops
• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably
• Chaining replaces nested loops with a readable, composable pipeline
parse_expr → call parse_term, then check for '+', then call parse_expr again
parse_term → call parse_atom, then check for '*', then call parse_term again
parse_atom → parse a number#[derive(Debug)]
pub enum Expr {
Num(i64),
Add(Box<Expr>, Box<Expr>), // Box for heap allocation — recursive type
Mul(Box<Expr>, Box<Expr>),
}
// parse_expr handles lowest precedence (+)
fn parse_expr<'a>(tokens: &'a [&str]) -> Result<(Expr, &'a [&str]), String> {
let (left, rest) = parse_term(tokens)?; // parse higher-precedence first
if let Some(("+", rest)) = rest.split_first() {
let (right, rest) = parse_expr(rest)?; // right-recursive for +
Ok((Expr::Add(Box::new(left), Box::new(right)), rest))
} else {
Ok((left, rest))
}
}
// parse_term handles * (tighter than +)
fn parse_term<'a>(tokens: &'a [&str]) -> Result<(Expr, &'a [&str]), String> {
let (left, rest) = parse_atom(tokens)?;
if let Some(("*", rest)) = rest.split_first() {
let (right, rest) = parse_term(rest)?;
Ok((Expr::Mul(Box::new(left), Box::new(right)), rest))
} else {
Ok((left, rest))
}
}
// parse_atom handles numbers (highest precedence — leaves of the AST)
fn parse_atom<'a>(tokens: &'a [&str]) -> Result<(Expr, &'a [&str]), String> {
match tokens.split_first() {
Some((token, rest)) => Ok((Expr::Num(token.parse()?), rest)),
None => Err("unexpected end of input".into()),
}
}pub fn eval(expr: &Expr) -> i64 {
match expr {
Expr::Num(n) => *n,
Expr::Add(a, b) => eval(a) + eval(b),
Expr::Mul(a, b) => eval(a) * eval(b),
}
}| Concept | OCaml | Rust |
|---|---|---|
| Mutual recursion | `let rec ... and ...` keyword | Functions simply call each other |
| Recursive types | Implicit heap allocation | `Box<Expr>` — explicit heap |
| Token consumption | Pattern match on list head | `split_first()` on slice |
| Error handling | `raise` / `failwith` | `Result<T, String>`, `?` operator |
| Lifetime | Not needed | `'a` on slice refs — ties output to input |
//! # Simple Recursive Descent Parser
//!
//! Parse arithmetic expressions into an AST with correct precedence.
//! OCaml's mutual recursion with `and` maps to Rust functions calling each other.
#[derive(Debug, PartialEq)]
pub enum Expr {
Num(i64),
Add(Box<Expr>, Box<Expr>),
Mul(Box<Expr>, Box<Expr>),
}
// ---------------------------------------------------------------------------
// Approach A: Slice-based parser (mirrors OCaml's list consumption)
// ---------------------------------------------------------------------------
pub fn parse<'a>(tokens: &'a [&'a str]) -> Result<Expr, String> {
let (expr, rest) = parse_expr(tokens)?;
if rest.is_empty() {
Ok(expr)
} else {
Err(format!("unexpected tokens: {:?}", rest))
}
}
fn parse_expr<'a>(tokens: &'a [&'a str]) -> Result<(Expr, &'a [&'a str]), String> {
let (left, rest) = parse_term(tokens)?;
if let Some((&"+", rest)) = rest.split_first() {
let (right, rest) = parse_expr(rest)?;
Ok((Expr::Add(Box::new(left), Box::new(right)), rest))
} else {
Ok((left, rest))
}
}
fn parse_term<'a>(tokens: &'a [&'a str]) -> Result<(Expr, &'a [&'a str]), String> {
let (left, rest) = parse_atom(tokens)?;
if let Some((&"*", rest)) = rest.split_first() {
let (right, rest) = parse_term(rest)?;
Ok((Expr::Mul(Box::new(left), Box::new(right)), rest))
} else {
Ok((left, rest))
}
}
fn parse_atom<'a>(tokens: &'a [&'a str]) -> Result<(Expr, &'a [&'a str]), String> {
match tokens.split_first() {
Some((token, rest)) => {
let n: i64 = token.parse().map_err(|_| format!("not a number: {}", token))?;
Ok((Expr::Num(n), rest))
}
None => Err("unexpected end of input".to_string()),
}
}
// ---------------------------------------------------------------------------
// Approach B: Evaluator (mirrors OCaml's eval)
// ---------------------------------------------------------------------------
pub fn eval(expr: &Expr) -> i64 {
match expr {
Expr::Num(n) => *n,
Expr::Add(a, b) => eval(a) + eval(b),
Expr::Mul(a, b) => eval(a) * eval(b),
}
}
// ---------------------------------------------------------------------------
// Approach C: Index-based parser (avoids slice lifetimes)
// ---------------------------------------------------------------------------
pub fn parse_and_eval(tokens: &[&str]) -> Result<i64, String> {
let expr = parse(tokens)?;
Ok(eval(&expr))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_simple_add() {
assert_eq!(parse_and_eval(&["2", "+", "3"]), Ok(5));
}
#[test]
fn test_simple_mul() {
assert_eq!(parse_and_eval(&["2", "*", "3"]), Ok(6));
}
#[test]
fn test_precedence() {
assert_eq!(parse_and_eval(&["2", "+", "3", "*", "4"]), Ok(14));
}
#[test]
fn test_single_number() {
assert_eq!(parse_and_eval(&["42"]), Ok(42));
}
#[test]
fn test_empty() {
assert!(parse_and_eval(&[]).is_err());
}
#[test]
fn test_complex() {
assert_eq!(parse_and_eval(&["1", "+", "2", "+", "3"]), Ok(6));
}
}
type expr = Num of int | Add of expr * expr | Mul of expr * expr
let rec parse_expr tokens =
let left, rest = parse_term tokens in
match rest with
| "+" :: rest' ->
let right, rest'' = parse_expr rest' in
(Add (left, right), rest'')
| _ -> (left, rest)
and parse_term tokens =
let left, rest = parse_atom tokens in
match rest with
| "*" :: rest' ->
let right, rest'' = parse_term rest' in
(Mul (left, right), rest'')
| _ -> (left, rest)
and parse_atom = function
| n :: rest -> (Num (int_of_string n), rest)
| [] -> failwith "unexpected end"
let rec eval = function
| Num n -> n | Add (a,b) -> eval a + eval b | Mul (a,b) -> eval a * eval b
let () =
let tokens = ["2";"+";"3";"*";"4"] in
let ast, _ = parse_expr tokens in
Printf.printf "2+3*4 = %d\n" (eval ast)
The parser structure is nearly identical: `parse_expr` calls `parse_term` calls `parse_atom`, with each level consuming tokens and returning (AST, remaining_tokens). The key Rust difference is `Box<Expr>` — recursive enum variants must be heap-allocated because Rust needs compile-time size. OCaml's GC handles this transparently.
🐪 Show OCaml equivalent
type expr = Num of int | Add of expr * expr | Mul of expr * expr
let rec parse_expr tokens =
let left, rest = parse_term tokens in
match rest with
| "+" :: rest' -> let right, rest'' = parse_expr rest' in (Add (left, right), rest'')
| _ -> (left, rest)
and parse_term tokens =
let left, rest = parse_atom tokens in
match rest with
| "*" :: rest' -> let right, rest'' = parse_term rest' in (Mul (left, right), rest'')
| _ -> (left, rest)
fn parse_expr<'a>(tokens: &'a [&str]) -> Result<(Expr, &'a [&str]), String> {
let (left, rest) = parse_term(tokens)?;
if let Some(("+", rest)) = rest.split_first() {
let (right, rest) = parse_expr(rest)?;
Ok((Expr::Add(Box::new(left), Box::new(right)), rest))
} else { Ok((left, rest)) }
}| Aspect | OCaml | Rust |
|---|---|---|
| Recursive type | `expr * expr` directly | `Box<Expr>` required |
| Mutual recursion | `and` keyword | Functions call each other |
| Token consumption | `"+" :: rest'` list match | `split_first()` on slice |
| Error handling | `failwith` exception | `Result<T, String>` |
| Tuple return | `(ast, rest)` | `(Expr, &[&str])` with lifetime |
| Parse int | `int_of_string` | `str::parse::<i64>()` |