12
\$\begingroup\$

I loved Norvig's Lispy, and made the first version of it in Rust, to learn Rust. I would love your thoughts :)

A few specific questions:

  1. Is there a way to write ensure_tonicity without a macro? I tried, but was having trouble typing it
  2. What do you think of passing in &mut RispEnv in eval. I needed to do this to implement def, as it mutates env. Is my approach the idiomatic rust way, anything I'm missing?
  3. In my implementation of PartialEq for RispExp, I had to use a default false. This removes the win of exhaustive typechecking, but I had to do it, I think, in order to avoid writing out all the combinations of RispExp a, with RispExp b. Is there some way I can do exhaustive typechecking here, without writing out all combinations? i.e no different enum types (RispExp::Symbol, with RispExp::Number for ex) should ever be equal.
  4. How is my use of references, Rc, etc?

And of course, any other thoughts greatly appreciated :)

use std::collections::HashMap;
use std::io;
use std::num::ParseFloatError;
use std::rc::Rc;

/* 
  Types
*/


#[derive(Clone)]
enum RispExp {
  Bool(bool),
  Symbol(String),
  Number(f64),
  List(Vec<RispExp>),
  Func(fn(&[RispExp]) -> Result<RispExp, RispErr>),
  Lambda(RispLambda)
}

#[derive(Debug)]
enum RispErr {
  Reason(String),
}

#[derive(Clone)]
struct RispEnv {
  data: HashMap<String, RispExp>,
  outer: Option<Rc<RispEnv>>,
}

#[derive(Clone)]
struct RispLambda {
  params_exp: Rc<RispExp>,
  body_exp: Rc<RispExp>,
}

impl PartialEq for RispExp {
  fn eq(&self, other: &RispExp) -> bool {
    match (self, other) {
      (RispExp::Bool(ref a), RispExp::Bool(ref b)) => a == b,
      (RispExp::Symbol(ref a), RispExp::Symbol(ref b)) => a == b,
      (RispExp::Number(ref a), RispExp::Number(ref b)) => a == b,
      (RispExp::List(ref a), RispExp::List(ref b)) => a == b,
      _ => false,
    }
  }
}

/*
  Print
*/

fn to_str(exp: &RispExp) -> String {
  match exp {
    RispExp::Symbol(s) => s.clone(),
    RispExp::Number(n) => n.to_string(),
    RispExp::Bool(b) => b.to_string(),
    RispExp::List(list) => {
      let xs: Vec<String> = list
        .iter()
        .map(|x| to_str(x))
        .collect();
      return format!("({})", xs.join(","));
    },
    RispExp::Func(_) => "Function {}".to_string(),
    RispExp::Lambda(_) => "Lambda {}".to_string(),
  }
}

/* 
  Env
*/

fn parse_single_float(exp: &RispExp) -> Result<f64, RispErr> {
  match exp {
    RispExp::Number(num) => Ok(*num),
    _ => Err(
      RispErr::Reason(
        format!("expected a number, got form='{}'", to_str(exp))
      )
    ),
  }
}

fn parse_list_of_floats(args: &[RispExp]) -> Result<Vec<f64>, RispErr> {
  return args
    .iter()
    .map(|x| parse_single_float(x))
    .collect::<Result<Vec<f64>, RispErr>>();
}

macro_rules! ensure_tonicity {
  ($check_fn:expr) => {{
    |args: &[RispExp]| -> Result<RispExp, RispErr> {
      let floats = parse_list_of_floats(args)?;
      let first = floats.first().ok_or(RispErr::Reason("expected at least one number".to_string()))?;
      let rest = &floats[1..];
      fn f (prev: &f64, xs: &[f64]) -> bool {
        match xs.first() {
          Some(x) => $check_fn(prev, x) && f(x, &xs[1..]),
          None => true,
        }
      };
      return Ok(RispExp::Bool(f(first, rest)));
    }
  }};
}

fn default_env() -> RispEnv {
  let mut data: HashMap<String, RispExp> = HashMap::new();
  data.insert(
    "+".to_string(), 
    RispExp::Func(
      |args: &[RispExp]| -> Result<RispExp, RispErr> {
        let sum = parse_list_of_floats(args)?.iter().fold(0.0, |sum, a| sum + a);
        return Ok(RispExp::Number(sum));
      }
    )
  );
  data.insert(
    "-".to_string(), 
    RispExp::Func(
      |args: &[RispExp]| -> Result<RispExp, RispErr> {
        let floats = parse_list_of_floats(args)?;
        let first = *floats.first().ok_or(RispErr::Reason("expected at least one number".to_string()))?;
        let sum_of_rest = floats[1..].iter().fold(0.0, |sum, a| sum + a);

        return Ok(RispExp::Number(first - sum_of_rest));
      }
    )
  );
  data.insert(
    "=".to_string(), 
    RispExp::Func(ensure_tonicity!(|a, b| a == b))
  );
  data.insert(
    ">".to_string(), 
    RispExp::Func(ensure_tonicity!(|a, b| a > b))
  );
  data.insert(
    ">=".to_string(), 
    RispExp::Func(ensure_tonicity!(|a, b| a >= b))
  );
  data.insert(
    "<".to_string(), 
    RispExp::Func(ensure_tonicity!(|a, b| a < b))
  );
  data.insert(
    "<=".to_string(), 
    RispExp::Func(ensure_tonicity!(|a, b| a <= b))
  );

  return RispEnv {data: data, outer: None}
}

/* 
  Eval
*/

fn eval_if_args(arg_forms: &[RispExp], env: &mut RispEnv) -> Result<RispExp, RispErr> {
  let test_form = arg_forms.first().ok_or(
    RispErr::Reason(
      "expected test form".to_string(),
    )
  )?;
  let test_eval = eval(test_form, env)?;
  match test_eval {
    RispExp::Bool(b) => {
      let form_idx = if b { 1 } else { 2 };
      let res_form = arg_forms.get(form_idx)
        .ok_or(RispErr::Reason(
          format!("expected form idx={}", form_idx)
        ))?;
      let res_eval = eval(res_form, env);

      return res_eval;
    },
    _ => Err(
      RispErr::Reason(format!("unexpected test form='{}'", to_str(test_form)))
    )
  }
}

fn eval_def(arg_forms: &[RispExp], env: &mut RispEnv) -> Result<RispExp, RispErr> {
  let first_form = arg_forms.first().ok_or(
    RispErr::Reason(
      "expected first form".to_string(),
    )
  )?;
  let first_str = match first_form {
    RispExp::Symbol(s) => Ok(s.clone()),
    _ => Err(RispErr::Reason(
      "expected first form to be a symbol".to_string(),
    ))
  }?;
  let second_form = arg_forms.get(1).ok_or(
    RispErr::Reason(
      "expected second form".to_string(),
    )
  )?;
  if arg_forms.len() > 2 {
    return Err(
      RispErr::Reason(
        "def can only have two forms ".to_string(),
      )
    )
  } 
  let second_eval = eval(second_form, env)?;
  env.data.insert(first_str, second_eval);
  return Ok(first_form.clone());
}

fn eval_lambda(arg_forms: &[RispExp]) -> Result<RispExp, RispErr> {
  let params_exp = arg_forms.first().ok_or(
    RispErr::Reason(
      "expected args form".to_string(),
    )
  )?;
  let body_exp = arg_forms.get(1).ok_or(
    RispErr::Reason(
      "expected second form".to_string(),
    )
  )?;
  if arg_forms.len() > 2 {
    return Err(
      RispErr::Reason(
        "fn deefinition can only have two forms ".to_string(),
      )
    )
  }
  return Ok(
    RispExp::Lambda(
      RispLambda {
        body_exp: Rc::new(body_exp.clone()),
        params_exp: Rc::new(params_exp.clone()),
      }
    )
  );
}

fn eval_built_in_symbol(sym: String, arg_forms: &[RispExp], env: &mut RispEnv) -> Result<RispExp, RispErr> {
  match sym.as_ref() {
    "if" => eval_if_args(arg_forms, env),
    "def" => eval_def(arg_forms, env),
    "fn" => eval_lambda(arg_forms),
    _ => Err(RispErr::Reason(format!("unknown built-in symbol='{}'", sym))),
  }
}

fn eval_forms(arg_forms: &[RispExp], env: &mut RispEnv) -> Result<Vec<RispExp>, RispErr> {
  return arg_forms
    .iter()
    .map(|x| eval(x, env))
    .collect::<Result<Vec<RispExp>, RispErr>>();
}


fn parse_list_of_symbol_strings(form: Rc<RispExp>) -> Result<Vec<String>, RispErr> {
  let list = match form.as_ref() {
    RispExp::List(s) => Ok(s.clone()),
    _ => Err(RispErr::Reason(
      "expected args form to be a list".to_string(),
    ))
  }?;
  return list
    .iter()
    .map(
      |x| {
        return match x {
          RispExp::Symbol(s) => Ok(s.clone()),
          _ => Err(RispErr::Reason(
            "expected symbols in the argument list".to_string(),
          ))
        }   
      }
    ).collect::<Result<Vec<String>, RispErr>>();
}

fn env_for_lambda(
  params: Rc<RispExp>, 
  arg_forms: &[RispExp],
  outer_env: &mut RispEnv,
) -> Result<RispEnv, RispErr> {
  let ks = parse_list_of_symbol_strings(params)?;
  if ks.len() != arg_forms.len() {
    return Err(
      RispErr::Reason(
        format!("expected {} arguments, got {}", ks.len(), arg_forms.len())
      )
    );
  }
  let vs = eval_forms(arg_forms, outer_env)?;

  let mut data: HashMap<String, RispExp> = HashMap::new();
  for (k, v) in ks.iter().zip(vs.iter()) {
    data.insert(k.clone(), v.clone());
  }
  return Ok(
    RispEnv {
      data: data,
      outer: Some(Rc::new(outer_env.clone())),
    }
  );
}

fn env_get(k: &str, env: &RispEnv) -> Option<RispExp> {
  return match env.data.get(k) {
    Some(exp) => Some(exp.clone()),
    None => {
      return match &env.outer {
        Some(outer_env) => env_get(k, &outer_env),
        None => None
      }
    }
  };
}

fn eval(exp: &RispExp, env: &mut RispEnv) -> Result<RispExp, RispErr> {
  match exp {
    RispExp::Symbol(k) =>
      env_get(k, env)
        .or(Some(exp.clone()))
        .ok_or(
          RispErr::Reason(
            format!("unexpected symbol k='{}'", k)
          )
        )
    ,
    RispExp::Bool(_a) => Ok(exp.clone()),
    RispExp::Number(_a) => Ok(exp.clone()),
    RispExp::List(list) => {
      let first_form = list
        .first()
        .ok_or(RispErr::Reason("expected a non-empty list".to_string()))?;
      let arg_forms = &list[1..];
      let first_eval = eval(first_form, env)?;
      return match first_eval {
        RispExp::Symbol(sym) => eval_built_in_symbol(sym, arg_forms, env),
        RispExp::Func(f) => {
          return f(&eval_forms(arg_forms, env)?);
        },
        RispExp::Lambda(lambda) => {
          let new_env = &mut env_for_lambda(lambda.params_exp, arg_forms, env)?;
          return eval(&lambda.body_exp, new_env); 
        },
        _ => Err(
          RispErr::Reason(
            format!("first form must be a function, but got form='{}'", to_str(&first_eval))
          )
        ),
      }
    },
    RispExp::Func(_) => Err(
      RispErr::Reason(
        format!("unexpected form='{}'", to_str(exp))
      )
    ),
    RispExp::Lambda(_) => Err(
      RispErr::Reason(
        format!("unexpected form='{}'", to_str(exp))
      )
    ),
  }
}

/* 
  Parse
*/

fn read_seq(tokens: &[String], start: usize) -> Result<(RispExp, usize), RispErr> {
  let mut res: Vec<RispExp> = vec![];
  let mut next = start;
  loop {
    let next_token = tokens
      .get(next)
      .ok_or(RispErr::Reason("could not find closing `)`".to_string()))
      ?;
    if next_token == ")" {
      return Ok((RispExp::List(res), next + 1)) // skip `)`, head to the token after
    }
    let (exp, new_next) = parse(&tokens, next)?;
    res.push(exp);
    next = new_next;
  }
}

fn parse_atom(token: &str) -> RispExp {
  match token.as_ref() {
    "true" => RispExp::Bool(true),
    "false" => RispExp::Bool(false),
    _ => {
      let potential_float: Result<f64, ParseFloatError> = token.parse();
      return match potential_float {
        Ok(v) => RispExp::Number(v),
        Err(_) => RispExp::Symbol(token.to_string().clone())
      }
    }
  }
}

fn parse(tokens: &[String], pos: usize) -> Result<(RispExp, usize), RispErr> {
  let token = tokens
    .get(pos)
    .ok_or(
      RispErr::Reason(format!("could not get token for pos='{}'", pos))
    )?;
  let to_match = &token[..];
  match to_match {
    "(" => read_seq(tokens, pos + 1),
    ")" => Err(RispErr::Reason("unexpected `)`".to_string())),
    _ => Ok(
      (parse_atom(token), pos + 1)
    ),
  }
}

fn tokenize(expr: String) -> Vec<String> {
  return expr
    .replace("(", " ( ")
    .replace(")", " ) ")
    .split(" ")
    .map(|x| x.trim().to_string())
    .filter(|x| !x.is_empty())
    .collect();
}

/*
  REPL
*/

fn parse_eval_print(expr: String, env: &mut RispEnv) -> Result<String, RispErr> {
  let (parsed_exp, _) = parse(&tokenize(expr), 0)?;
  let evaled_exp = eval(&parsed_exp, env)?;
  return Ok(to_str(&evaled_exp));
}

fn slurp_expr() -> String {
  let mut expr = String::new();

  io::stdin().read_line(&mut expr)
    .expect("Failed to read line");

  return expr;
}

fn main() {
  let env = &mut default_env();
  loop {
    println!("risp >");
    let expr = slurp_expr();;
    match parse_eval_print(expr, env) {
      Ok(res) => println!("// 🔥 => {}", res),
      Err(e) => match e {
        RispErr::Reason(msg) => println!("// 🙀 => {}", msg),
      },
    }
  }
}
```
\$\endgroup\$
2
\$\begingroup\$

Organization

Let's first take a look at the organization of the code. The gigantic code block is stored in one file, with comments like /* Types */ and /* Print */ separating different logical blocks and names that start with the relevant prefixes.

Instead, take advantage of Rust's powerful module system:

// main.rs

pub mod core;
pub mod eval;
pub mod parse;
// etc.
// core.rs

#[derive(Clone, Debug)]
pub enum Expr {
    // ...
}

#[derive(Clone, Debug)]
pub struct Error(String);

// ...

and so on.

cargo fmt and cargo clippy

cargo fmt automatically formats your code according to the official Rust Style Guide.

cargo clippy reported a lot of issues (1 error and 34 warnings). Here are some typical examples:

warning: unneeded `return` statement
  --> src\main.rs:82:5
   |
82 | /     return args
83 | |         .iter()
84 | |         .map(|x| parse_single_float(x))
85 | |         .collect::<Result<Vec<f64>, RispErr>>();
   | |________________________________________________^
   |
   = note: `#[warn(clippy::needless_return)]` on by default
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#needless_return
help: remove `return`
   |
82 |     args
83 |         .iter()
84 |         .map(|x| parse_single_float(x))
85 |         .collect::<Result<Vec<f64>, RispErr>>()
   |
warning: redundant field names in struct initialization
   --> src\main.rs:152:9
    |
152 |         data: data,
    |         ^^^^^^^^^^ help: replace it with: `data`
    |
    = note: `#[warn(clippy::redundant_field_names)]` on by default
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_field_names
warning: use of `ok_or` followed by a function call
   --> src\main.rs:124:18
    |
124 |                 .ok_or(RispErr::Reason("expected at least one number".to_string()))?;
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try this: `ok_or_else(|| RispErr::Reason("expected at least one number".to_string()))`
    |
    = note: `#[warn(clippy::or_fun_call)]` on by default
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#or_fun_call
warning: redundant clone
   --> src\main.rs:369:60
    |
369 |                 Err(_) => RispExp::Symbol(token.to_string().clone()),
    |                                                            ^^^^^^^^ help: remove this
    |
    = note: `#[warn(clippy::redundant_clone)]` on by default
note: this value is dropped without further use
   --> src\main.rs:369:43
    |
369 |                 Err(_) => RispExp::Symbol(token.to_string().clone()),
    |                                           ^^^^^^^^^^^^^^^^^
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_clone
warning: this call to `as_ref` does nothing
   --> src\main.rs:362:11
    |
362 |     match token.as_ref() {
    |           ^^^^^^^^^^^^^^ help: try this: `token`
    |
    = note: `#[warn(clippy::useless_asref)]` on by default
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#useless_asref
warning: single-character string constant used as pattern
   --> src\main.rs:392:16
    |
392 |         .split(" ")
    |                ^^^ help: try using a `char` instead: `' '`
    |
    = note: `#[warn(clippy::single_char_pattern)]` on by default
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#single_char_pattern

You can follow the suggestions given in the help sections to improve your code.

One of the diagnostics given by clippy is worth noting:

error: strict comparison of `f32` or `f64`
   --> src\main.rs:132:47
    |
132 |         RispExp::Func(ensure_tonicity!(|a, b| a == b)),
    |                                               ^^^^^^ help: consider comparing them within some error: `(a - b).abs() < error`
    |
    = note: `#[deny(clippy::float_cmp)]` on by default
    = note: `f32::EPSILON` and `f64::EPSILON` are available for the `error`
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#float_cmp

clippy apparently considers testing for strict equality on floating-point numbers to be an oversight, but the exact behavior is desired in this case. I would define a wrapper function that clearly communicates the intent and turn off the lint for it:

#[allow(clippy::float_cmp)]
fn strictly_equal<T, U>(lhs: T, rhs: U) -> bool
where
    T: PartialEq<U>,
{
    lhs == rhs
}

Thus, strictly_equal(a, b) can be used in place of a == b to avoid triggering the warning.

(Technically, the #[allow(clippy::float_cmp)] is redundant here, since clippy::float_cmp ignores functions whose name contains the substring eq. I decided to include it for clarity.)

Built-in functions and ensure_tonicity!

Instead of storing a function pointer in RispExp, why not simply store a token and define associated operations? For example:

#[derive(Clone, Debug)]
enum RispExp {
    Func(Func),
    // ...
}

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
enum Func {
    Compare(std::cmp::Ordering),
    Add,
    Minus,
    // ...
}

impl Func {
    fn eval(args: &[RispExp]) -> RispExp {
        // ...
    }
}

Passing environments around

Instead of taking &mut Env arguments everywhere, define the functions as methods on Env.

matching on two operands of the same enum

In my implementation of PartialEq for RispExp, I had to use a default false. This removes the win of exhaustive typechecking, but I had to do it, I think, in order to avoid writing out all the combinations of RispExp a, with RispExp b. Is there some way I can do exhaustive typechecking here, without writing out all combinations? i.e no different enum types (RispExp::Symbol, with RispExp::Number for ex) should ever be equal.

Personally, I wouldn't worry about it at all. If you want to ensure that you have handled all homogenenous cases in non-_ match arms, you can use std::mem::discriminant to perform a runtime check:

match (lhs, rhs) {
    // ...
    _ => {
        use std::mem::discriminant;
        // ensure that we've handled all homogeneous cases explicitly
        assert_eq!(discriminant(lhs), discriminant(rhs));
        false
    }
}

I am not aware of a simple compile-time solution, unfortunately.

Reference counting

To me, reference counting seems like a viable solution for pointing to expressions from multiple places. I would consider using some Weak references to avoid reference cycles, though.


These should be enough to get you started.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.