From a1c946b747325b4d7df778ebc70112338482f143 Mon Sep 17 00:00:00 2001 From: Brian Cully Date: Thu, 21 Aug 2025 15:26:44 -0400 Subject: factorial working --- src/forth/interp.rs | 205 +++++++++++++++++++++++++++++++++------------------- src/forth/mod.rs | 33 +++++++++ src/forth/parser.rs | 26 ++++--- src/lib.rs | 0 4 files changed, 182 insertions(+), 82 deletions(-) mode change 100644 => 100755 src/forth/mod.rs mode change 100644 => 100755 src/lib.rs (limited to 'src') diff --git a/src/forth/interp.rs b/src/forth/interp.rs index c7e8588..f1af4ae 100644 --- a/src/forth/interp.rs +++ b/src/forth/interp.rs @@ -1,4 +1,3 @@ -use std::collections::HashMap; use std::ops::Index; #[derive(Clone, Debug, PartialEq)] @@ -11,13 +10,22 @@ pub enum OpCode { TIf(usize, Option), // tail version Add, Sub, + Mul, + Div, + Dup, + Drop, + EQ, + GT, + GTE, + LT, + LTE, // todo: maybe get rid of ret? it's only used in word definitions, // which are bounded, so running of the end can be treated as an // implicit ‘ret’. Ret, } -#[derive(Debug)] +#[derive(Clone, Debug)] pub(super) struct ByteCode(pub(super) Vec); impl ByteCode { @@ -55,17 +63,16 @@ pub(super) struct DataStack(pub(super) Vec); #[derive(Debug)] pub(super) struct CallStack(pub(super) Vec); -#[derive(Debug)] +#[derive(Clone, Debug)] pub(super) struct WordList(pub(super) Vec); -#[derive(Debug)] -pub(super) struct WordCatalog<'a>(pub(super) HashMap<&'a str, usize>); - #[derive(Debug)] pub struct Interp { - stack: DataStack, + // todo: don't be pub, probably + pub stack: DataStack, callstack: CallStack, - wordlist: WordList, + // todo: don't be pub + pub wordlist: WordList, ip: InstructionPointer, } @@ -75,12 +82,12 @@ pub enum RuntimeError { } impl Interp { - pub fn new() -> Self { + pub fn new(wordlist: WordList) -> Self { Self { stack: DataStack(Vec::new()), callstack: CallStack(Vec::new()), - wordlist: WordList(vec![]), ip: InstructionPointer::new(), + wordlist, } } @@ -94,9 +101,9 @@ impl Interp { self.jmp(word); } - pub fn tick(&mut self) -> Result<(), RuntimeError> { + // bool is still_running + pub fn tick(&mut self) -> Result { let bc = &self.wordlist.0[self.ip.word]; - eprintln!("debug: executing {:?}", bc[self.ip.offset]); match bc[self.ip.offset] { OpCode::Num(n) => self.stack.0.push(n), OpCode::Str(start, end) => eprintln!("got str: {} to {}", start, end), @@ -110,51 +117,94 @@ impl Interp { let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; self.stack.0.push(n2 - n1); }, + OpCode::Mul => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n2 * n1); + }, + OpCode::Div => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n2 / n1); + }, + OpCode::Dup => { + let n = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + self.stack.0.push(n); + self.stack.0.push(n); + }, + OpCode::Drop => { + self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + }, + OpCode::EQ => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 == n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::GT => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 > n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::GTE => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 >= n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::LT => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 < n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, + OpCode::LTE => { + let n1 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let n2 = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; + let v = if n2 <= n1 { -1 } else { 0 }; + self.stack.0.push(v); + }, OpCode::Ret => { self.ip = self.callstack.0.pop().ok_or(RuntimeError::StackUnderflow)?; }, OpCode::Call(i) => { - eprintln!("should call word based on index {}", i); self.call(i); // skip the offset increment - return Ok(()) + return Ok(true) }, OpCode::TCall(i) => { - eprintln!("should jump to word based on index {}", i); self.jmp(i); // skip the offset increment - return Ok(()) + return Ok(true) }, OpCode::If(true_clause, false_clause) => { let flag = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; if flag != 0 { - eprintln!("should call true branch {}", true_clause); self.call(true_clause); - return Ok(()) + return Ok(true) } else if let Some(false_clause) = false_clause { - eprintln!("should call false branch {}", false_clause); self.call(false_clause); - return Ok(()) - } else { - eprintln!("should false fall through"); + return Ok(true) } }, OpCode::TIf(true_clause, false_clause) => { let flag = self.stack.0.pop().ok_or(RuntimeError::StackUnderflow)?; if flag != 0 { - eprintln!("should call true branch {}", true_clause); self.jmp(true_clause); - return Ok(()) + return Ok(true) } else if let Some(false_clause) = false_clause { - eprintln!("should call false branch {}", false_clause); self.jmp(false_clause); - return Ok(()) - } else { - eprintln!("should false fall through"); + return Ok(true) } }, } self.ip.offset += 1; + Ok(self.ip.offset < self.wordlist.0[self.ip.word].len()) + } + + pub fn run(&mut self) -> Result<(), RuntimeError> { + while self.tick()? {} Ok(()) } } @@ -166,20 +216,20 @@ mod tests { #[test] fn simple_ticks() -> Result<(), RuntimeError> { - - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Num(3), OpCode::Add])); - interp.tick()?; + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Num(3), OpCode::Add])); + let mut interp = Interp::new(wordlist); + assert_eq!(interp.tick()?, true, "first arg running"); assert_eq!(interp.ip.word, 0); assert_eq!(interp.ip.offset, 1); assert_eq!(interp.stack.0.len(), 1); assert_eq!(interp.stack.0[0], 2, "first argument"); - interp.tick()?; + assert_eq!(interp.tick()?, true, "second arg running"); assert_eq!(interp.ip.word, 0); assert_eq!(interp.ip.offset, 2); assert_eq!(interp.stack.0.len(), 2); assert_eq!(interp.stack.0[1], 3, "second argument"); - interp.tick()?; + assert_eq!(interp.tick()?, false, "stopped after addition"); assert_eq!(interp.ip.word, 0); assert_eq!(interp.ip.offset, 3); assert_eq!(interp.stack.0.len(), 1); @@ -190,11 +240,12 @@ mod tests { #[test] fn custom_word() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![ + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![ OpCode::Num(2), OpCode::Num(3), OpCode::Call(1), OpCode::Num(-2), OpCode::Add, OpCode::Sub, OpCode::Ret, ])); + let mut interp = Interp::new(wordlist); // "sub" definition interp.wordlist.0.push(ByteCode(vec![ OpCode::Sub, OpCode::Ret, @@ -244,11 +295,11 @@ mod tests { #[test] fn tail_call() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Call(1)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::TCall(2), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Ret])); - + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1)])); + wordlist.0.push(ByteCode(vec![OpCode::TCall(2), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; // call assert_eq!(interp.callstack.0.len(), 1, "callstack after call"); @@ -261,9 +312,10 @@ mod tests { #[test] fn if_then_true() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, None), OpCode::Num(0)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, None), OpCode::Num(0)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); @@ -285,9 +337,10 @@ mod tests { #[test] fn if_then_false() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, None), OpCode::Num(-1)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, None), OpCode::Num(-1)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); @@ -303,10 +356,11 @@ mod tests { #[test] fn if_else_then_true() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, Some(2)), OpCode::Num(-2)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::If(1, Some(2)), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 1, "push -1 stack len"); @@ -328,10 +382,11 @@ mod tests { #[test] fn if_else_then_false() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, Some(2)), OpCode::Num(-2)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::If(1, Some(2)), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 1, "push 0 stack len"); @@ -353,10 +408,11 @@ mod tests { #[test] fn tail_if_then_true() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, None), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, None), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); @@ -380,10 +436,11 @@ mod tests { #[test] fn tail_if_then_false() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, None), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(0)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, None), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); @@ -403,11 +460,12 @@ mod tests { #[test] fn tail_if_else_then_true() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, Some(3)), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(-1), OpCode::TIf(2, Some(3)), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); @@ -431,11 +489,12 @@ mod tests { #[test] fn tail_if_else_then_false() -> Result<(), RuntimeError> { - let mut interp = Interp::new(); - interp.wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, Some(3)), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); - interp.wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut wordlist = WordList(vec![]); + wordlist.0.push(ByteCode(vec![OpCode::Call(1), OpCode::Num(-2)])); + wordlist.0.push(ByteCode(vec![OpCode::Num(0), OpCode::TIf(2, Some(3)), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(1), OpCode::Ret])); + wordlist.0.push(ByteCode(vec![OpCode::Num(2), OpCode::Ret])); + let mut interp = Interp::new(wordlist); interp.tick()?; assert_eq!(interp.stack.0.len(), 0, "call(1) stack len"); diff --git a/src/forth/mod.rs b/src/forth/mod.rs old mode 100644 new mode 100755 index fdda066..5792148 --- a/src/forth/mod.rs +++ b/src/forth/mod.rs @@ -1,2 +1,35 @@ mod interp; mod parser; + +#[cfg(test)] +mod tests { + use super::{ + interp::{Interp, WordList}, + parser::Parser + }; + + fn parser_for(text: &str) -> Parser { + let mut p = Parser::new(text); + p.parse().expect("badparse"); + p + } + + fn eprintwordlist(wordlist: &WordList) { + for i in 0..wordlist.0.len() { + eprintln!("wordlist[{}]: {:?}", i, wordlist.0[i]); + } + } + + // recursive! + #[test] + fn fac() { + let prog = ": fac dup 1 > if dup 1 - fac * then ; 5 fac\n"; + let p = parser_for(prog); + eprintwordlist(&p.wordlist); + let mut interp = Interp::new(p.wordlist); + interp.run().expect("should run to completion"); + eprintln!("stack: {:?}", interp.stack); + assert_eq!(interp.stack.0.len(), 1, "factorial result stack len"); + assert_eq!(interp.stack.0[0], 120, "factorial result value"); + } +} diff --git a/src/forth/parser.rs b/src/forth/parser.rs index ddc48a9..55ad64b 100644 --- a/src/forth/parser.rs +++ b/src/forth/parser.rs @@ -1,4 +1,4 @@ -use super::interp::{ByteCode, OpCode, WordCatalog, WordList}; +use super::interp::{ByteCode, OpCode, WordList}; use std::collections::HashMap; use std::iter::{Enumerate, Iterator}; @@ -27,6 +27,9 @@ impl std::error::Error for ParseError {} type ParseResult = Result; +#[derive(Debug)] +pub struct WordCatalog<'a>(pub(super) HashMap<&'a str, usize>); + #[derive(Debug)] pub enum IfClauses { True(usize), @@ -39,7 +42,8 @@ pub struct Parser<'a> { enumerator: Enumerate>, // list of all word definitions, in the order defined. the main // routine is always in the first entry. - wordlist: WordList, + // todo: don't be pub, have a method to extract a wordlist + pub wordlist: WordList, // catalog of word to word index in `wordlist` wordalog: WordCatalog<'a>, // holds a stack of indices into `wordlist` that are currently @@ -74,7 +78,7 @@ impl<'a> Parser<'a> { let (end, _c) = self.enumerator.by_ref() .find(|(_i, c)| c.is_whitespace())?; - let word = self.text.get(start..end).unwrap(); + let word = &self.text[start..end]; Some((word, start, end)) } @@ -98,7 +102,7 @@ impl<'a> Parser<'a> { Ok(()) } - fn parse(&mut self) -> ParseResult<()> { + pub fn parse(&mut self) -> ParseResult<()> { while let Some((word, _start, end)) = self.next_word() { if let Ok(i) = word.parse::() { self.bc_push(OpCode::Num(i))?; @@ -139,7 +143,6 @@ impl<'a> Parser<'a> { self.defstack.pop().ok_or(ParseError::DefStackEmpty)?; }, "if" => { - eprintln!("got if, if_stack: {:?}", self.if_stack); let i = self.wordlist.0.len(); self.wordlist.0.push(ByteCode(vec![])); self.defstack.push(i); @@ -147,7 +150,6 @@ impl<'a> Parser<'a> { self.if_stack.push(IfClauses::True(i)); }, "else" => { - eprintln!("got else, if_stack: {:?}", self.if_stack); self.bc_push(OpCode::Ret)?; self.defstack.pop(); @@ -163,24 +165,30 @@ impl<'a> Parser<'a> { self.if_stack.push(IfClauses::TrueFalse(true_clause, i)); }, "then" => { - eprintln!("got then, if_stack: {:?}", self.if_stack); self.bc_push(OpCode::Ret)?; self.defstack.pop(); match self.if_stack.pop() { None => return Err(ParseError::MissingIf), Some(IfClauses::True(true_clause)) => { - eprintln!("single clause true at {}", true_clause); self.bc_push(OpCode::If(true_clause, None))?; }, Some(IfClauses::TrueFalse(true_clause, false_clause)) => { - eprintln!("two clause true at {} and {}", true_clause, false_clause); self.bc_push(OpCode::If(true_clause, Some(false_clause)))?; } } }, "+" => self.bc_push(OpCode::Add)?, "-" => self.bc_push(OpCode::Sub)?, + "*" => self.bc_push(OpCode::Mul)?, + "/" => self.bc_push(OpCode::Div)?, + "dup" => self.bc_push(OpCode::Dup)?, + "drop" => self.bc_push(OpCode::Drop)?, + "=" => self.bc_push(OpCode::EQ)?, + ">" => self.bc_push(OpCode::GT)?, + ">=" => self.bc_push(OpCode::GTE)?, + "<" => self.bc_push(OpCode::LT)?, + "<=" => self.bc_push(OpCode::LTE)?, other => return Err(ParseError::UnknownWord(String::from(other))), } } diff --git a/src/lib.rs b/src/lib.rs old mode 100644 new mode 100755 -- cgit v1.3