123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571 |
- use crate::ast::*;
- use rand::Rng;
- use std::cell::RefCell;
- use std::collections::HashMap;
- use std::fmt;
- use std::rc::Rc;
- use std::io;
- macro_rules! bail {
- ($fmt:expr) => { return Err(Error { message: format!($fmt), }) };
- ($fmt:expr, $($e:expr),*) => { return Err(Error { message: format!($fmt, $($e),*), }) }
- }
- #[derive(Debug, Clone)]
- pub enum Value {
- Lit(Literal),
- Tup(Vec<Thunk>),
- Builtin(&'static BuiltinFunc),
- Closure(Closure),
- Nil,
- }
- impl Value {
- fn as_num(&self) -> Result<i64, Error> {
- match self {
- Value::Lit(Literal::Num(n)) => Ok(*n),
- _ => self.with_str(|s| bail!("Expected number, got {}", s)),
- }
- }
- fn as_str(&self) -> Result<&str, Error> {
- match self {
- Value::Lit(Literal::Str(s)) => Ok(s),
- _ => self.with_str(|s| bail!("Expected string, got {}", s)),
- }
- }
- fn as_tup(&self) -> Result<&[Thunk], Error> {
- match self {
- Value::Tup(vals) => Ok(vals),
- _ => self.with_str(|s| bail!("Expected tuple, got {}", s)),
- }
- }
- fn as_closure(&self) -> Result<&Closure, Error> {
- match self {
- Value::Closure(closure) => Ok(closure),
- _ => self.with_str(|s| bail!("Expected tuple, got {}", s)),
- }
- }
- fn with_str<U>(&self, f: impl FnOnce(&str) -> U) -> U {
- match self {
- Value::Nil => f(""),
- Value::Lit(Literal::Str(s)) => f(s),
- Value::Lit(Literal::Atom(s)) => f(&format!("{:?}", s)),
- Value::Lit(Literal::Num(n)) => f(&format!("{}", n)),
- Value::Tup(values) => {
- let mut buf = String::new();
- buf.push('<');
- for (i, val) in values.iter().enumerate() {
- if i > 0 {
- buf.push_str(", ");
- }
- match val {
- Thunk::Value(v) => buf.push_str(&v.to_string()),
- Thunk::Expr(..) => buf.push_str("#<unevaluated>"),
- Thunk::Builtin(func) => buf.push_str(&format!("#<builtin {}>", func.name)),
- }
- }
- buf.push('>');
- f(&buf)
- }
- Value::Builtin(func) => f(&format!("#<builtin {}>", func.name)),
- Value::Closure(_) => f("#<lambda ...>"),
- }
- }
- }
- impl fmt::Display for Value {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- self.with_str(|s| write!(f, "{}", s))
- }
- }
- pub struct BuiltinFunc {
- name: &'static str,
- callback: &'static dyn Fn(&State, ExprRef, &Env) -> Result<Value, Error>,
- }
- #[derive(Debug)]
- pub struct Error {
- message: String,
- }
- impl From<lalrpop_util::ParseError<usize, crate::lexer::Token<'_>, crate::lexer::LexerError>>
- for Error
- {
- fn from(
- err: lalrpop_util::ParseError<usize, crate::lexer::Token<'_>, crate::lexer::LexerError>,
- ) -> Error {
- Error {
- message: format!("{:?}", err),
- }
- }
- }
- impl fmt::Display for Error {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- write!(fmt, "{}", self.message)
- }
- }
- impl std::error::Error for Error {}
- const BUILTINS: &[BuiltinFunc] = &[
- BuiltinFunc {
- name: "rep",
- callback: &|state: &State, expr: ExprRef, env: &Env| -> Result<Value, Error> {
- let (rep, expr) = {
- let ast = state.ast.borrow();
- let args = match &ast[expr] {
- Expr::Tup(tup) => tup,
- _ => bail!("`rep`: expected tuple"),
- };
- if args.len() != 2 {
- bail!("`rep`: expected two arguments, got {}", args.len())
- }
- (args[0], args[1])
- };
- let mut buf = String::new();
- let num = state.eval(rep, env)?.as_num()?;
- for _ in 0..num {
- buf.push_str(&state.eval(expr, env)?.as_str()?.to_string());
- }
- Ok(Value::Lit(Literal::Str(buf)))
- },
- },
- BuiltinFunc {
- name: "length",
- callback: &|state: &State, expr: ExprRef, _env: &Env| -> Result<Value, Error> {
- let ast = state.ast.borrow();
- let args = match &ast[expr] {
- Expr::Tup(tup) => tup,
- _ => bail!("`length`: expected tuple"),
- };
- Ok(Value::Lit(Literal::Num(args.len() as i64)))
- },
- },
- BuiltinFunc {
- name: "to-upper",
- callback: &|state: &State, expr: ExprRef, env: &Env| -> Result<Value, Error> {
- let s = state.eval(expr, env)?;
- Ok(Value::Lit(Literal::Str(s.as_str()?.to_uppercase())))
- },
- },
- BuiltinFunc {
- name: "to-lower",
- callback: &|state: &State, expr: ExprRef, env: &Env| -> Result<Value, Error> {
- let s = state.eval(expr, env)?;
- Ok(Value::Lit(Literal::Str(s.as_str()?.to_lowercase())))
- },
- },
- BuiltinFunc {
- name: "concat",
- callback: &|state: &State, expr: ExprRef, env: &Env| -> Result<Value, Error> {
- let val = state.eval(expr, env)?;
- let tup = val.as_tup()?;
- let mut contents = Vec::new();
- for elem in tup {
- for th in state.hnf(elem)?.as_tup()? {
- contents.push(th.clone());
- }
- }
- Ok(Value::Tup(contents))
- },
- },
- BuiltinFunc {
- name: "tuple-fold",
- callback: &|state: &State, expr: ExprRef, env: &Env| -> Result<Value, Error> {
- let val = state.eval(expr, env)?;
- let args = val.as_tup()?;
- if args.len() != 3 {
- bail!("`tuple-fold`: expected 3 arguments, got {}", args.len());
- }
- let func = &args[0];
- let init = &args[1];
- let tup = &args[2];
- let func = state.hnf(func)?;
- let tup = state.hnf(tup)?;
- let mut result = init.clone();
- for t in tup.as_tup()? {
- let partial = state.eval_closure(func.as_closure()?, result)?;
- result = Thunk::Value(state.eval_closure(partial.as_closure()?, t.clone())?);
- }
- state.hnf(&result)
- },
- },
- ];
- impl fmt::Debug for BuiltinFunc {
- fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
- writeln!(fmt, "BuiltinFunc {{ name: {:?}, ... }}", self.name)
- }
- }
- #[derive(Debug, Clone)]
- pub enum Thunk {
- Expr(ExprRef, Env),
- Value(Value),
- Builtin(&'static BuiltinFunc),
- }
- type Env = Option<Rc<Scope>>;
- #[derive(Debug)]
- pub struct Scope {
- vars: HashMap<Name, Thunk>,
- parent: Env,
- }
- #[derive(Debug, Clone)]
- pub struct Closure {
- func: ExprRef,
- scope: Env,
- }
- pub struct State {
- ast: RefCell<ASTArena>,
- root_scope: RefCell<HashMap<Name, Thunk>>,
- rand: RefCell<rand::rngs::ThreadRng>,
- parser: crate::grammar::StmtsParser,
- }
- impl Default for State {
- fn default() -> State {
- Self::new()
- }
- }
- impl State {
- pub fn new() -> State {
- let s = State {
- root_scope: RefCell::new(HashMap::new()),
- rand: RefCell::new(rand::thread_rng()),
- parser: crate::grammar::StmtsParser::new(),
- ast: RefCell::new(ASTArena::new()),
- };
- for builtin in BUILTINS {
- let sym = s.ast.borrow_mut().add_string(builtin.name);
- s.root_scope
- .borrow_mut()
- .insert(sym, Thunk::Builtin(builtin));
- }
- s
- }
- pub fn get_ast(&self) -> &RefCell<ASTArena> {
- &self.ast
- }
- fn lookup(&self, env: &Env, name: Name) -> Result<Thunk, Error> {
- if let Some(env) = env {
- if let Some(ne) = env.vars.get(&name) {
- Ok(ne.clone())
- } else {
- self.lookup(&env.parent, name)
- }
- } else {
- match self.root_scope.borrow().get(&name) {
- None => bail!("no such thing: {}", &self.ast.borrow()[name]),
- Some(ne) => Ok(ne.clone()),
- }
- }
- }
- pub fn run(&self, src: &str) -> Result<(), Error> {
- let lexed = crate::lexer::tokens(src);
- let stmts = self.parser.parse(&mut self.ast.borrow_mut(), lexed)?;
- let mut stdout = io::stdout();
- for stmt in stmts {
- self.execute(&stmt, &mut stdout)?;
- }
- Ok(())
- }
- pub fn run_repl(&self, src: &str) -> Result<(), Error> {
- let lexed = crate::lexer::tokens(src);
- let stmts = {
- let mut ast = self.ast.borrow_mut();
- self.parser.parse(&mut ast, lexed)
- };
- let stmts = match stmts {
- Ok(stmts) => stmts,
- Err(err) => {
- let with_puts = format!("puts {}", src);
- let lexed = crate::lexer::tokens(&with_puts);
- if let Ok(stmts) = self.parser.parse(&mut self.ast.borrow_mut(), lexed) {
- stmts
- } else {
- return Err(err.into());
- }
- }
- };
- for stmt in stmts {
- self.execute(&stmt, io::stdout())?;
- }
- Ok(())
- }
- pub fn autocomplete(&self, fragment: &str, at_beginning: bool) -> Vec<String> {
- let mut possibilities = Vec::new();
- for name in self.root_scope.borrow().keys() {
- if self.ast.borrow()[*name].starts_with(fragment) {
- possibilities.push(self.ast.borrow()[*name].to_string());
- }
- }
- if at_beginning && "puts".starts_with(fragment) {
- possibilities.push("puts ".to_owned());
- }
- possibilities
- }
- pub fn execute(&self, stmt: &Stmt, mut output: impl io::Write) -> Result<(), Error> {
- match stmt {
- Stmt::Puts(expr) => {
- let val = self.eval(*expr, &None)?;
- let val = self.force(val)?;
- writeln!(output, "{}", val.to_string()).unwrap();
- }
- Stmt::Fix(name) => {
- let (expr, env) = match self.lookup(&None, *name)? {
- Thunk::Expr(e, env) => (e, env),
- // if it's not an expr, then our work here is done
- _ => return Ok(()),
- };
- let val = self.eval(expr, &env)?;
- let val = self.force(val)?;
- self.root_scope
- .borrow_mut()
- .insert(*name, Thunk::Value(val));
- }
- Stmt::Assn(fixed, name, expr) => {
- if *fixed {
- let val = self.eval(*expr, &None)?;
- self.root_scope
- .borrow_mut()
- .insert(*name, Thunk::Value(val));
- } else {
- self.root_scope
- .borrow_mut()
- .insert(*name, Thunk::Expr(*expr, None));
- }
- }
- Stmt::LitAssn(fixed, name, strs) => {
- if *fixed {
- let choice = &strs[self.rand.borrow_mut().gen_range(0..strs.len())];
- self.root_scope.borrow_mut().insert(
- *name,
- Thunk::Value(Value::Lit(Literal::Str(choice.clone()))),
- );
- return Ok(());
- }
- let choices = strs
- .iter()
- .map(|s| Choice {
- weight: None,
- value: self
- .ast
- .borrow_mut()
- .add_expr(Expr::Lit(Literal::Str(s.clone()))),
- })
- .collect();
- let choices = self.ast.borrow_mut().add_expr(Expr::Chc(choices));
- self.root_scope
- .borrow_mut()
- .insert(*name, Thunk::Expr(choices, None));
- }
- }
- Ok(())
- }
- fn force(&self, val: Value) -> Result<Value, Error> {
- match val {
- Value::Tup(values) => Ok(Value::Tup(
- values
- .into_iter()
- .map(|t| {
- let v = self.hnf(&t)?;
- let v = self.force(v)?;
- Ok(Thunk::Value(v))
- })
- .collect::<Result<Vec<Thunk>, Error>>()?,
- )),
- _ => Ok(val),
- }
- }
- fn hnf(&self, thunk: &Thunk) -> Result<Value, Error> {
- match thunk {
- Thunk::Expr(expr, env) => self.eval(*expr, env),
- Thunk::Value(val) => Ok(val.clone()),
- Thunk::Builtin(b) => Ok(Value::Builtin(b)),
- }
- }
- fn eval(&self, expr_ref: ExprRef, env: &Env) -> Result<Value, Error> {
- let expr = &self.ast.borrow()[expr_ref];
- match expr {
- Expr::Lit(l) => Ok(Value::Lit(l.clone())),
- Expr::Nil => Ok(Value::Nil),
- Expr::Var(v) => {
- let (e, env) = match self.lookup(env, *v)? {
- Thunk::Expr(e, env) => (e, env),
- Thunk::Value(v) => return Ok(v),
- Thunk::Builtin(b) => return Ok(Value::Builtin(b)),
- };
- self.eval(e, &env)
- }
- Expr::Cat(cat) => {
- if cat.len() == 1 {
- self.eval(cat[0], env)
- } else {
- let mut buf = String::new();
- for expr in cat {
- let val = self.eval(*expr, env)?;
- let val = self.force(val)?;
- buf.push_str(&val.to_string());
- }
- Ok(Value::Lit(Literal::Str(buf)))
- }
- }
- Expr::Chc(choices) => {
- if choices.len() == 1 {
- self.eval(choices[0].value, env)
- } else {
- self.choose(choices, env)
- }
- }
- Expr::Tup(values) => Ok(Value::Tup(
- values
- .iter()
- .map(|v| Thunk::Expr(*v, env.clone()))
- .collect::<Vec<Thunk>>(),
- )),
- Expr::Range(from, to) => {
- let from = self.eval(*from, env)?.as_num()?;
- let to = self.eval(*to, env)?.as_num()?;
- Ok(Value::Lit(Literal::Num(
- self.rand.borrow_mut().gen_range(from..=to),
- )))
- }
- Expr::Fun(_) => Ok(Value::Closure(Closure {
- func: expr_ref,
- scope: env.clone(),
- })),
- Expr::Ap(func, val) => match self.eval(*func, env)? {
- Value::Closure(c) => {
- let scrut = Thunk::Expr(*val, env.clone());
- self.eval_closure(&c, scrut)
- }
- Value::Builtin(builtin) => (builtin.callback)(self, *val, env),
- _ => bail!("Bad function: {:?}", func),
- },
- _ => bail!("unimplemented: {:?}", expr),
- }
- }
- fn eval_closure(&self, closure: &Closure, mut scrut: Thunk) -> Result<Value, Error> {
- let ast = self.ast.borrow();
- let cases = match &ast[closure.func] {
- Expr::Fun(cases) => cases,
- _ => bail!("INVARIANT FAILED"),
- };
- for c in cases {
- let mut bindings = Vec::new();
- if !self.match_pat(&c.pat, &mut scrut, &mut bindings)? {
- continue;
- }
- let mut new_scope = HashMap::new();
- for (name, binding) in bindings {
- new_scope.insert(name, binding);
- }
- let new_scope = Rc::new(Scope {
- vars: new_scope,
- parent: closure.scope.clone(),
- });
- return self.eval(c.expr, &Some(new_scope));
- }
- bail!("No pattern in {:?} matched {:?}", cases, scrut);
- }
- fn match_pat(
- &self,
- pat: &Pat,
- scrut: &mut Thunk,
- bindings: &mut Vec<(Name, Thunk)>,
- ) -> Result<bool, Error> {
- if let Pat::Var(v) = pat {
- bindings.push((*v, scrut.clone()));
- return Ok(true);
- }
- if let Pat::Wildcard = pat {
- return Ok(true);
- }
- // if it's not just a variable, then we'll need to make sure
- // we've evaluated `scrut` at least one level from here
- if let Thunk::Expr(e, env) = scrut {
- *scrut = Thunk::Value(self.eval(*e, env)?)
- };
- // now we can match deeper patterns, at least a little
- match pat {
- Pat::Lit(lhs) => {
- if let Thunk::Value(Value::Lit(rhs)) = scrut {
- Ok(lhs == rhs)
- } else {
- Ok(false)
- }
- }
- Pat::Tup(pats) => {
- if let Thunk::Value(Value::Tup(thunks)) = scrut {
- if pats.len() != thunks.len() {
- return Ok(false);
- }
- for (p, t) in pats.iter().zip(thunks) {
- if !self.match_pat(p, t, bindings)? {
- return Ok(false);
- }
- }
- Ok(true)
- } else {
- Ok(false)
- }
- }
- _ => Ok(false),
- }
- }
- fn choose(&self, choices: &[Choice], env: &Env) -> Result<Value, Error> {
- let max = choices.iter().map(Choice::weight).sum();
- let mut choice = self.rand.borrow_mut().gen_range(0..max);
- for ch in choices {
- if choice < ch.weight() {
- return self.eval(ch.value, env);
- }
- choice -= ch.weight();
- }
- bail!("unreachable")
- }
- }
|