(Lisp in (Rust))

Question

我喜欢诺维格的李皮，并制作了它的第一个版本的锈，以学习锈。我喜欢你的想法:)

以下是几个具体问题：

1. 有没有一种没有宏的编写ensure_tonicity的方法？我试过了，但是是打字有困难
2. 你觉得在eval中传入D8怎么样？我需要这样做来实现def，因为它会变异env。我的方法是惯用的生锈方式吗，我遗漏了什么？
3. 在PartialEq for RispExp的实现中，我必须使用默认的false。这就消除了穷尽的打字机的优点，但我认为，为了避免用RispExp b写出所有RispExp a的组合，我必须这样做。有什么方法可以在这里进行详尽的打印，而不写出所有的组合呢？也就是说，没有不同的枚举类型(RispExp：：符号，其中RispExp::Number表示ex)应该是相等的。
4. 我对参考资料、Rc等的使用如何？

当然，任何其他的想法都会受到极大的赞赏:)

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),
  Func(fn(&[RispExp]) -> Result),
  Lambda(RispLambda)
}

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

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

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

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 = 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 {
  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, RispErr> {
  return args
    .iter()
    .map(|x| parse_single_float(x))
    .collect::, RispErr>>();
}

macro_rules! ensure_tonicity {
  ($check_fn:expr) => {{
    |args: &[RispExp]| -> Result {
      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 = HashMap::new();
  data.insert(
    "+".to_string(), 
    RispExp::Func(
      |args: &[RispExp]| -> Result {
        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 {
        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 {
  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 {
  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 {
  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 {
  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, RispErr> {
  return arg_forms
    .iter()
    .map(|x| eval(x, env))
    .collect::, RispErr>>();
}


fn parse_list_of_symbol_strings(form: Rc) -> Result, 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::, RispErr>>();
}

fn env_for_lambda(
  params: Rc, 
  arg_forms: &[RispExp],
  outer_env: &mut RispEnv,
) -> Result {
  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 = 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 {
  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 {
  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 = 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 = 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 {
  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 {
  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),
      },
    }
  }
}
```#qcStackCode#

Answer 1

组织

让我们先来看看代码的组织。巨大的代码块存储在一个文件中，像/* Types */和/* Print */这样的注释将以相关前缀开头的不同逻辑块和名称分隔开来。

相反，利用Rust强大的模块系统：

// 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);

// ...

诸若此类。

cargo fmt和cargo clippy

cargo fmt根据官方的锈蚀式导轨自动格式化代码。

cargo clippy报告了许多问题(1次错误和34次警告)。以下是一些典型的例子：

warning: unneeded `return` statement
  --> src\main.rs:82:5
   |
82 | /     return args
83 | |         .iter()
84 | |         .map(|x| parse_single_float(x))
85 | |         .collect::, 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::, 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

您可以按照这些警告中的建议来改进代码。

值得注意的是，clippy提供的一种诊断方法是：

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显然认为对浮点数进行严格相等的测试是一种疏忽，但在这种情况下需要的是精确的行为。我定义了一个包装器函数，它清楚地传达了意图并关闭了它的衬里：

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

因此，可以使用strictly_equal(a, b)代替a == b来避免触发警告。

(从技术上讲，#[allow(clippy::float_cmp)]在这里是多余的，因为clippy::float_cmp忽略了其名称包含子字符串eq的函数。不过，为了清楚起见，我决定把它包括进去。)

内置函数与ensure_tonicity!

与其将函数指针存储在RispExp中，为什么不简单地存储令牌并定义相关操作呢？例如：

#[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 {
        // ...
    }
}

围绕

的

传递环境

与其到处使用&mut Env参数，不如将函数定义为Env上的方法。

matching在同一个enum

的两个操作数上

在PartialEq for RispExp的实现中，我必须使用默认的false。这就消除了穷尽的打字机的优点，但我认为，为了避免用RispExp b写出所有RispExp a的组合，我必须这样做。有什么方法可以在这里进行详尽的打印，而不写出所有的组合呢？也就是说，没有不同的枚举类型(RispExp：：符号，其中RispExp::Number表示ex)应该是相等的。

就我个人而言，我一点也不担心。如果要确保已处理了非_匹配臂中的所有同质情况，则可以使用std::mem::discriminant执行运行时检查：

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

不幸的是，我不知道有一个简单的编译时解决方案。

参考计数

对我来说，引用计数似乎是指向来自多个位置的表达式的可行解决方案。不过，我会考虑使用一些Weak引用来避免引用周期。

这些应该足以让你开始工作。