add tail call elimination for call and if.

1 files changed, 268 insertions, 5 deletions

diff --git a/src/forth/interp.rs b/src/forth/interp.rs
index 406c424..c7e8588 100644
--- a/src/forth/interp.rs
+++ b/src/forth/interp.rs
@@ -6,8 +6,14 @@ pub enum OpCode {
     Num(i32),
     Str(usize, usize),
     Call(usize),
+    TCall(usize), // tail call, really just ‘jmp’, but named to indicate desired usage.
+    If(usize, Option<usize>), // true word index, optional false word index.
+    TIf(usize, Option<usize>), // tail version
     Add,
     Sub,
+    // 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,
 }
 
@@ -28,7 +34,6 @@ impl Index<usize> for ByteCode {
     }
 }
 
-// .0 is wordlist entry's bytecode, .1 is index into that bytecode
 #[derive(Debug, Copy, Clone, PartialEq)]
 pub(super) struct InstructionPointer {
     pub(super) word: usize,
@@ -79,8 +84,19 @@ impl Interp {
         }
     }
 
+    pub fn jmp(&mut self, word: usize) {
+        self.ip.word = word;
+        self.ip.offset = 0;
+    }
+
+    pub fn call(&mut self, word: usize) {
+        self.callstack.0.push(self.ip);
+        self.jmp(word);
+    }
+
     pub fn tick(&mut self) -> Result<(), RuntimeError> {
         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),
@@ -98,13 +114,45 @@ impl Interp {
                 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(())
+            },
+            OpCode::TCall(i) => {
                 eprintln!("should jump to word based on index {}", i);
-                self.callstack.0.push(self.ip);
-                self.ip.word = i;
-                self.ip.offset = 0;
+                self.jmp(i);
                 // skip the offset increment
                 return Ok(())
-            }
+            },
+            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(())
+                } 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");
+                }
+            },
+            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(())
+                } 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");
+                }
+            },
         }
         self.ip.offset += 1;
         Ok(())
@@ -193,4 +241,219 @@ mod tests {
 
         Ok(())
     }
+
+    #[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]));
+
+
+        interp.tick()?; // call
+        assert_eq!(interp.callstack.0.len(), 1, "callstack after call");
+        interp.tick()?; // tcall
+        assert_eq!(interp.callstack.0.len(), 1, "callstack after tcall");
+        interp.tick()?; // ret
+        assert_eq!(interp.callstack.0.len(), 0, "callstack after ret");
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push -1 stack len");
+        assert_eq!(interp.stack.0[0], -1, "push -1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "if stack ");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 1 stack len");
+        assert_eq!(interp.stack.0[0], 1, "push 1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "ret stack len");
+        assert_eq!(interp.stack.0[0], 1, "ret stack val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 2, "push 0 stack len");
+        assert_eq!(interp.stack.0[1], 0, "push 0 stack val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 0 stack len");
+        assert_eq!(interp.stack.0[0], 0, "push 0 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "if stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push -1 stack len");
+        assert_eq!(interp.stack.0[0], -1, "push -1 val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push -1 stack len");
+        assert_eq!(interp.stack.0[0], -1, "push -1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "if stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 1 stack len");
+        assert_eq!(interp.stack.0[0], 1, "push 1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "ret stack len");
+        assert_eq!(interp.stack.0[0], 1, "ret val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 2, "push -2 stack len");
+        assert_eq!(interp.stack.0[1], -2, "push -2 val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 0 stack len");
+        assert_eq!(interp.stack.0[0], 0, "push 0 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "if");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 2 stack len");
+        assert_eq!(interp.stack.0[0], 2, "push 2 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "ret");
+        assert_eq!(interp.stack.0[0], 2, "ret");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 2, "push -2 stack len");
+        assert_eq!(interp.stack.0[1], -2, "push -2 val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "call(1) stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push -1 stack len");
+        assert_eq!(interp.stack.0[0], -1, "push -1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "tif stack ");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 1 stack len");
+        assert_eq!(interp.stack.0[0], 1, "push 1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "ret stack len");
+        assert_eq!(interp.stack.0[0], 1, "ret stack val");
+        interp.tick()?; // no ret on wordlist[1] since it's ‘tif’
+        assert_eq!(interp.stack.0.len(), 2, "push 0 stack len");
+        assert_eq!(interp.stack.0[1], 0, "push 0 stack val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "call(1) stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 0 stack len");
+        assert_eq!(interp.stack.0[0], 0, "push 0 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "tif stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "ret stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 0 stack len");
+        assert_eq!(interp.stack.0[0], 0, "push 0 val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "call(1) stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push -1 stack len");
+        assert_eq!(interp.stack.0[0], -1, "push -1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "tif stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 1 stack len");
+        assert_eq!(interp.stack.0[0], 1, "push 1 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "ret stack len");
+        assert_eq!(interp.stack.0[0], 1, "ret val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 2, "push -2 stack len");
+        assert_eq!(interp.stack.0[1], -2, "push -2 val");
+
+        Ok(())
+    }
+
+    #[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]));
+
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "call(1) stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 0 stack len");
+        assert_eq!(interp.stack.0[0], 0, "push 0 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 0, "tif stack len");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "push 2 stack len");
+        assert_eq!(interp.stack.0[0], 2, "push 2 val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 1, "ret stack len");
+        assert_eq!(interp.stack.0[0], 2, "ret val");
+        interp.tick()?;
+        assert_eq!(interp.stack.0.len(), 2, "push -2 stack len");
+        assert_eq!(interp.stack.0[1], -2, "push -2 val");
+
+        Ok(())
+    }
 }