From 12c6ac3ca30293ebb968eb3e8b445f0a17e74b58 Mon Sep 17 00:00:00 2001 From: bnewbold Date: Mon, 25 Apr 2016 12:49:10 -0400 Subject: rust: big refactor of SchemeExpr; add env (partial) I changed SchemeExpr to own any internal strings, instead of having &str references with a lifetime tied to to the SchemeExpr. This removes the lifetime annotation from the SchemeExpr, horray! This was to support the (WIP) top-level environment context, which will be necessary for `define` and `set!`. --- rust/spectrum.rs | 141 ++++++++++++++++++++++++++++++++----------------------- 1 file changed, 83 insertions(+), 58 deletions(-) diff --git a/rust/spectrum.rs b/rust/spectrum.rs index fa67a9c..f736f14 100644 --- a/rust/spectrum.rs +++ b/rust/spectrum.rs @@ -13,9 +13,10 @@ use std::collections::HashMap; //////////// Types and Constants -// TODO: how to avoid the '32' here? -const SCHEME_BUILTINS: [&'static str; 32] = [ +// TODO: how to avoid the '34' here? +const SCHEME_BUILTINS: [&'static str; 34] = [ "lambda", "quote", "cond", "else", "display", + "define", "set!", "cons", "car", "cdr", "boolean?", "symbol?", "procedure?", "pair?", "number?", "string?", "null?", "atom?", "zero?", @@ -28,21 +29,21 @@ const SCHEME_BUILTINS: [&'static str; 32] = [ // The SchemeExpr type is basically the complete AST. // There doesn't seem to be a symbol or quote type in Rust, so i'm using typed strings. #[derive(Clone, PartialEq)] -enum SchemeExpr<'a> { +enum SchemeExpr { SchemeNull, SchemeTrue, SchemeFalse, SchemeNum(f64), - SchemeBuiltin(&'a str), - SchemeSymbol(&'a str), - SchemeIdentifier(&'a str), - SchemeStr(&'a str), + SchemeBuiltin(String), + SchemeSymbol(String), + SchemeIdentifier(String), + SchemeStr(String), SchemeProcedure( - Vec<&'a str>, - Vec>, - HashMap<&'a str, SchemeExpr<'a>>), - SchemeList(Vec>), - SchemeQuote(Vec>), + Vec, + Vec, + HashMap), + SchemeList(Vec), + SchemeQuote(Vec), } //////////// Lexing, Parsing, and Printing @@ -142,7 +143,7 @@ fn scheme_parse_token(token: &str) -> Result { // Is it a builtin? if SCHEME_BUILTINS.contains(&token) { - return Ok(SchemeExpr::SchemeBuiltin(token)); + return Ok(SchemeExpr::SchemeBuiltin(token.to_string())); } // Try to parse as a number @@ -153,17 +154,17 @@ fn scheme_parse_token(token: &str) -> Result { // Is it a string? if token.starts_with("\"") && token.ends_with("\"") { - return Ok(SchemeExpr::SchemeStr(token)); + return Ok(SchemeExpr::SchemeStr(token.to_string())); } // Is it a symbol? if token.starts_with("'") && is_valid_identifier(&token[1..]) { - return Ok(SchemeExpr::SchemeSymbol(token)); + return Ok(SchemeExpr::SchemeSymbol(token.to_string())); } // Else, we'll treat it as an identifier if is_valid_identifier(token) { - return Ok(SchemeExpr::SchemeIdentifier(token)); + return Ok(SchemeExpr::SchemeIdentifier(token.to_string())); } return Err("unparsable token"); @@ -173,7 +174,7 @@ fn scheme_parse_token(token: &str) -> Result { * This function takes a flat sequence of string tokens (as output by scheme_tokenize) and parses * into a SchemeExpression (eg, a nested list of expressions). */ -fn scheme_parse<'a>(tokens: &Vec<&'a str>, depth: u32) -> Result<(Vec>, usize), &'static str> { +fn scheme_parse<'a>(tokens: &Vec<&'a str>, depth: u32) -> Result<(Vec, usize), &'static str> { let mut i: usize = 0; if tokens.len() == 0 { return Ok((vec![SchemeExpr::SchemeNull], 0)); @@ -229,10 +230,10 @@ fn scheme_repr(ast: &SchemeExpr) -> Result { &SchemeExpr::SchemeFalse => Ok("#f".to_string()), &SchemeExpr::SchemeNull => Ok("'()".to_string()), &SchemeExpr::SchemeNum(num) => Ok(format!("{}", num).to_string()), - &SchemeExpr::SchemeBuiltin(b)=> Ok(b.to_string()), - &SchemeExpr::SchemeStr(s)=> Ok(s.to_string()), - &SchemeExpr::SchemeSymbol(s)=> Ok(s.to_string()), - &SchemeExpr::SchemeIdentifier(s)=> Ok("'".to_string() + s), + &SchemeExpr::SchemeBuiltin(ref b)=> Ok(b.clone()), + &SchemeExpr::SchemeStr(ref s)=> Ok(s.clone()), + &SchemeExpr::SchemeSymbol(ref s)=> Ok(s.clone()), + &SchemeExpr::SchemeIdentifier(ref s)=> Ok("'".to_string() + &s), &SchemeExpr::SchemeProcedure(ref binds, ref body, _) => { let mut ret = "(lambda (".to_string(); for bind in binds { @@ -264,8 +265,7 @@ fn scheme_repr(ast: &SchemeExpr) -> Result { //////////// Expression Evaluation -#[allow(unused_variables)] -fn quote_action<'a>(list: &Vec>, ctx: HashMap<&str, SchemeExpr<'a>>) -> Result, &'static str> { +fn quote_action<'a>(list: &Vec) -> Result { // XXX: why can't I '.map()' here? (try .iter().skip(1)...) let mut body = Vec::::new(); for el in list[1..].to_vec() { @@ -274,7 +274,9 @@ fn quote_action<'a>(list: &Vec>, ctx: HashMap<&str, SchemeExpr<'a Ok(SchemeExpr::SchemeQuote(body)) } -fn cond_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { +fn cond_action<'a, 'b>(list: &Vec, + ctx: HashMap, + env: &mut HashMap) -> Result { for line in list.iter().skip(1) { match line { &SchemeExpr::SchemeList(ref inner) => { @@ -283,9 +285,9 @@ fn cond_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr< } let pred = &inner[0]; let val = &inner[1]; - let m = try!(scheme_meaning(&pred, ctx.clone())); + let m = try!(scheme_meaning(&pred, ctx.clone(), env)); if m != SchemeExpr::SchemeFalse && m != SchemeExpr::SchemeNull { - return scheme_meaning(&val, ctx); + return scheme_meaning(&val, ctx, env); } }, _ => { return Err("cond must contain tuples of (predicate, value)"); }, @@ -295,19 +297,20 @@ fn cond_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr< Ok(SchemeExpr::SchemeNull) } -fn lambda_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { +fn lambda_action<'a>(list: &Vec, + ctx: HashMap) -> Result { if list.len() < 3 { return Err("lambda must have a bind and at least one body expr"); } - let mut binds = Vec::<&str>::new(); + let mut binds = Vec::::new(); let bind_list = match &list[1] { &SchemeExpr::SchemeList(ref bl) => bl, _ => { return Err("second arg to lambda must be a list of binds") }, }; for bind in bind_list { match bind { - &SchemeExpr::SchemeIdentifier(name) => - binds.push(name), + &SchemeExpr::SchemeIdentifier(ref name) => + binds.push(name.clone()), _ => return Err("lambda binds must all be non-builtin symbols") } } @@ -315,7 +318,7 @@ fn lambda_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExp Ok(SchemeExpr::SchemeProcedure(binds, body, ctx.clone())) } -fn apply_math_op<'a>(action: &'a str, args: Vec) -> Result, &'static str> { +fn apply_math_op<'a>(action: &'a str, args: Vec) -> Result { if args.len() < 2 { return Err("math builtins take two or more args"); } @@ -337,7 +340,7 @@ fn apply_math_op<'a>(action: &'a str, args: Vec) -> Result(action: &'a str, args: Vec) -> Result, &'static str> { +fn apply_typecheck<'a>(action: &'a str, args: Vec) -> Result { if args.len() != 1 { return Err("typecheck builtins take a single argument"); } @@ -367,16 +370,20 @@ fn apply_typecheck<'a>(action: &'a str, args: Vec) -> Result(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { +fn apply_action<'a, 'b>(list: &Vec, + ctx: HashMap, + env: &mut HashMap) -> Result { if list.len() == 0 { // TODO: is this correct? return Ok(SchemeExpr::SchemeNull); } let action = &list[0]; - let args: Vec = list.iter().skip(1).map(|x| scheme_meaning(x, ctx.clone()).unwrap()).collect(); + // TODO: make this a single line? + let arg_meanings: Result, _> = list.iter().skip(1).map(|x| scheme_meaning(x, ctx.clone(), env)).collect(); + let args: Vec = try!(arg_meanings); match action { - &SchemeExpr::SchemeBuiltin(builtin) => { - return match builtin { + &SchemeExpr::SchemeBuiltin(ref builtin) => { + return match builtin.as_str() { "+" | "-" | "*" | "/" => apply_math_op(builtin, args), "null?" | "number?" | "zero?" | "atom?" => apply_typecheck(builtin, args), "eq?" => { @@ -427,7 +434,7 @@ fn apply_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr _ => Err("unimplemented builtin"), }; }, &SchemeExpr::SchemeList(_) => { - let procedure: SchemeExpr = try!(scheme_meaning(&action, ctx.clone())); + let procedure: SchemeExpr = try!(scheme_meaning(&action, ctx.clone(), env)); match procedure { SchemeExpr::SchemeProcedure(binds, body, proc_ctx) => { // This block of code implements procedure (lambda) application @@ -439,9 +446,9 @@ fn apply_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr } let mut closure = proc_ctx.clone(); for (name, arg) in binds.iter().zip(args) { - closure.insert(name, arg.clone()); + closure.insert(name.clone(), arg.clone()); } - return scheme_meaning(&body[0], closure); + return scheme_meaning(&body[0], closure, env); }, _ => { return Err("non-procedure at head of expression"); }, } }, @@ -452,7 +459,10 @@ fn apply_action<'a>(list: &Vec>, ctx: HashMap<&'a str, SchemeExpr /* * This is the main entry point for eval: it recursively evaluates an AST and returns the result. */ -fn scheme_meaning<'a>(ast: &SchemeExpr<'a>, ctx: HashMap<&'a str, SchemeExpr<'a>>) -> Result, &'static str> { +fn scheme_meaning<'a, 'b>(ast: &SchemeExpr, + ctx: HashMap, + env: &mut HashMap) -> Result { + return match ast { // "identity actions" &SchemeExpr::SchemeTrue => Ok(ast.clone()), @@ -465,42 +475,55 @@ fn scheme_meaning<'a>(ast: &SchemeExpr<'a>, ctx: HashMap<&'a str, SchemeExpr<'a> &SchemeExpr::SchemeProcedure(_, _, _) => Ok(ast.clone()), &SchemeExpr::SchemeQuote(ref list) => Ok(SchemeExpr::SchemeList(list.clone())), - &SchemeExpr::SchemeIdentifier(sym) => match ctx.get(sym) { - // the "lookup action" - Some(val) => Ok(val.clone()), - None => Err("symbol not defined"), + &SchemeExpr::SchemeIdentifier(ref sym) => { + match ctx.get(sym) { + // the "lookup action" + Some(val) => Ok(val.clone()), + None => { + match env.get(sym) { + // fall through to env... + //Some(val) => Ok(val.clone()), + Some(val) => { + println!("{}", scheme_repr(val).unwrap()); + Ok(SchemeExpr::SchemeNull) + }, + None => Err("symbol not defined"), + } + } + } }, &SchemeExpr::SchemeList(ref list) => { if list.len() == 0 { return Ok(SchemeExpr::SchemeNull); } match list[0] { - SchemeExpr::SchemeBuiltin("quote") => - quote_action(&list, ctx), - SchemeExpr::SchemeBuiltin("cond") => - cond_action(&list, ctx), - SchemeExpr::SchemeBuiltin("lambda") => + SchemeExpr::SchemeBuiltin(ref b) if b == "quote" => + quote_action(&list), + SchemeExpr::SchemeBuiltin(ref b) if b == "cond" => + cond_action(&list, ctx, env), + SchemeExpr::SchemeBuiltin(ref b) if b == "lambda" => lambda_action(&list, ctx), SchemeExpr::SchemeBuiltin(_) => - apply_action(&list, ctx), + apply_action(&list, ctx, env), SchemeExpr::SchemeProcedure(_, _, _) => - apply_action(&list, ctx), + apply_action(&list, ctx, env), SchemeExpr::SchemeList(_) => - apply_action(&list, ctx), + apply_action(&list, ctx, env), _ => Ok(SchemeExpr::SchemeNull) } }, } } -fn scheme_eval<'a>(ast: &'a SchemeExpr) -> Result, &'static str> { - let ctx = HashMap::<&str, SchemeExpr>::new(); - Ok(try!(scheme_meaning(ast, ctx))) +fn scheme_eval<'a, 'b>(ast: &'a SchemeExpr, + env: &mut HashMap) -> Result { + let ctx = HashMap::::new(); + Ok(try!(scheme_meaning(ast, ctx, env))) } //////////// Top-Level Program -fn repl(verbose: bool) { +fn repl<'b>(verbose: bool, top_env: &mut HashMap) { let stdin = io::stdin(); let mut stdout = io::stdout(); @@ -550,7 +573,7 @@ fn repl(verbose: bool) { continue; } }; - let resp = match scheme_eval(&ast) { + let resp = match scheme_eval(&ast, top_env) { Ok(x) => x, Err(e) => { println!("couldn't eval: {}", e); @@ -563,7 +586,9 @@ fn repl(verbose: bool) { fn main() { + let mut top_env = HashMap::::new(); + // For now only REPL mode is implemented - repl(true); + repl(true, &mut top_env); } -- cgit v1.2.3