Initial commit.

Not sure if everything here will be needed eventually, but we have a
working bytecode interpreter. Next I will write the linker, then the
core compiler, and finish with the macro expander.

1 files changed, 543 insertions, 0 deletions

diff --git a/bytecode/src/bytecode.rs b/bytecode/src/bytecode.rs
new file mode 100644
index 0000000..ab6edf9
--- /dev/null
+++ b/bytecode/src/bytecode.rs
@@ -0,0 +1,543 @@
+use crate::heap::{Heap, Pointer};
+use std::io::{BufWriter, Read, StdinLock, Write};
+
+// The cute scheme virtual machine has two stacks:
+//   - the data stack and
+//   - the locals stack.
+// There are four pointers:
+//   - the instruction pointer,
+//   - the argument pointer,
+//   - and the (data) stack pointer.
+// These pointers cannot be manipulated directly, but are referred to in
+// the comments below on the opcodes.
+
+#[derive(Debug, Eq, PartialEq)]
+pub enum Op {
+    // Signed arithmetic
+    // =================
+
+    // ( -- n )
+    // Pushes a constant.
+    Const(i64),
+    // ( n1 n2 -- n3 )
+    // Adds two integers.
+    Add,
+    // ( n1 n2 -- n3 )
+    // Subtracts two integers.
+    Sub,
+    // ( n1 n2 -- n3 )
+    // Multiplies two integers.
+    Mul,
+    // ( n1 n2 -- n3 )
+    // Divides two integers and truncates the result.
+    Div,
+    // ( n1 n2 -- n3 )
+    // Remainder from Div.
+    Mod,
+
+    // Heap
+    // ======
+
+    // ( n -- a )
+    // Allocates n bytes and returns the address.
+    Alloc,
+    // ( a -- u )
+    // Fetches a 64 bit word from the specified address plus the
+    // given offset.
+    Peek(u8),
+    // ( u a )
+    // Stores a 64 bit word at the specified address plus the
+    // given offset.
+    Poke(u8),
+    // ( a -- n )
+    // Fetches a byte from the specified address.
+    PeekByte,
+    // ( n a )
+    // Stores a byte at the specified address.
+    PokeByte,
+
+    // Stack
+    // =====
+
+    // ( n -- )
+    // Deletes an element from the stack.
+    Pop,
+    // ( -- n )
+    // Copies an argument from the locals stack to the data stack. The argument is an index above the argument pointer.
+    Local(u8),
+
+    // Control flow
+    // ============
+
+    // ( f -- )
+    // Jumps to the specified offset if the argument is non-zero.
+    If(i64),
+    // ( i-addr a1 a2 ... an  )
+    // ( Locals stack: -- instruction-ptr a1 a2 ... an argument-ptr )
+    // Pushes the instruction pointer, moves n arguments to the locals
+    // stack, pushes the old argument pointer, and jumps to the
+    // specified location.
+    Call(u8),
+    // ( Locals stack: instruction-ptr a1 a2 ... an argument-ptr )
+    // Pops the argument pointer (effectively popping n more arguments which were added by Call),
+    // and then pops the instruction pointer.
+    Ret,
+    // ( n )
+    // Terminates the interpreter with the given status code.
+    Exit,
+
+    // Input and output
+    // ================
+
+    // ( b file -- f )
+    // Writes a byte to a file. Returns true on success, false on error.
+    PutC,
+    // ( file -- b )
+    // Reads one byte from a file. Returns -1 on EOF, 0 on error.
+    GetC,
+}
+
+struct Stack {
+    v: Vec<u64>,
+}
+
+impl Stack {
+    fn pop(&mut self) -> Result<u64, String> {
+        self.v.pop().ok_or(String::from("stack underflow"))
+    }
+
+    fn pop_int(&mut self) -> Result<i64, String> {
+        Ok(self.pop()? as i64 >> 1)
+    }
+
+    fn push_int(&mut self, i: i64) {
+        self.v.push((i as u64) << 1 | 1);
+    }
+
+    fn pop_pointer(&mut self) -> Result<Pointer, String> {
+        Ok(Pointer::from_bytes(self.pop()?))
+    }
+
+    fn push_pointer(&mut self, p: Pointer) {
+        self.v.push(p.bytes());
+    }
+
+    fn pop_usize(&mut self) -> Result<usize, String> {
+        Ok(usize::try_from(self.pop()?).unwrap() >> 1)
+    }
+
+    fn push_usize(&mut self, p: usize) {
+        self.v.push(u64::try_from(p).unwrap() << 1 | 1);
+    }
+}
+
+fn fn_const(stack: &mut Stack, n: i64) {
+    stack.push_int(n);
+}
+
+fn add(stack: &mut Stack) -> Result<(), String> {
+    let n2 = stack.pop_int()?;
+    let n1 = stack.pop_int()?;
+    stack.push_int(n1.wrapping_add(n2));
+    Ok(())
+}
+
+fn sub(stack: &mut Stack) -> Result<(), String> {
+    let n2 = stack.pop_int()?;
+    let n1 = stack.pop_int()?;
+    stack.push_int(n1.wrapping_sub(n2));
+    Ok(())
+}
+
+fn mul(stack: &mut Stack) -> Result<(), String> {
+    let n2 = stack.pop_int()?;
+    let n1 = stack.pop_int()?;
+    stack.push_int(n1.wrapping_mul(n2));
+    Ok(())
+}
+
+fn div(stack: &mut Stack) -> Result<(), String> {
+    let n2 = stack.pop_int()?;
+    let n1 = stack.pop_int()?;
+    stack.push_int(n1.wrapping_div(n2));
+    Ok(())
+}
+
+fn fn_mod(stack: &mut Stack) -> Result<(), String> {
+    let n2 = stack.pop_int()?;
+    let n1 = stack.pop_int()?;
+    stack.push_int(n1.wrapping_rem(n2));
+    Ok(())
+}
+
+fn alloc(stack: &mut Stack, heap: &mut Heap) -> Result<(), String> {
+    let n = stack.pop_int()?;
+    let n_usize = match n.try_into() {
+        Ok(x) => x,
+        Err(_) => {
+            return Err(String::from("invalid size"));
+        }
+    };
+    stack.push_pointer(heap.alloc(n_usize));
+    Ok(())
+}
+
+fn peek(stack: &mut Stack, heap: &Heap, n: u8) -> Result<(), String> {
+    let a = stack.pop_pointer()?;
+    stack.v.push(heap.peek(a.offset(n))?);
+    Ok(())
+}
+
+fn poke(stack: &mut Stack, heap: &mut Heap, n: u8) -> Result<(), String> {
+    let a = stack.pop_pointer()?;
+    let u = stack.pop()?;
+    heap.poke(u, a.offset(n))?;
+    Ok(())
+}
+
+fn peek_byte(stack: &mut Stack, heap: &Heap) -> Result<(), String> {
+    let a = stack.pop_pointer()?;
+    stack.push_int(i64::from(heap.peek_byte(a)));
+    Ok(())
+}
+
+fn poke_byte(stack: &mut Stack, heap: &mut Heap) -> Result<(), String> {
+    let a = stack.pop_pointer()?;
+    let n = stack.pop_int()?;
+    heap.poke_byte((n & 0xff).try_into().unwrap(), a);
+    Ok(())
+}
+
+fn pop(stack: &mut Stack) -> Result<(), String> {
+    stack.pop()?;
+    Ok(())
+}
+
+fn local(stack: &mut Stack, locals: &Stack, n: u8) -> Result<(), String> {
+    let i = locals
+        .v
+        .len()
+        .checked_sub(usize::from(n) + 1)
+        .ok_or("out of bounds")?;
+    stack.v.push(locals.v[i]);
+    Ok(())
+}
+
+fn fn_if(stack: &mut Stack, ip: &mut usize, n: i64) -> Result<(), String> {
+    let f = stack.pop_int()?;
+    if f != 0 {
+        if n > 0 {
+            *ip = ip
+                .checked_add(n.try_into().unwrap())
+                .ok_or("invalid offset")?;
+        } else {
+            *ip = ip
+                .checked_sub((-n).try_into().unwrap())
+                .ok_or("invalid offset")?;
+        }
+    }
+    Ok(())
+}
+
+fn call(stack: &mut Stack, locals: &mut Stack, ip: &mut usize, n: u8) -> Result<(), String> {
+    // Push the instruction pointer.
+    locals.push_usize(*ip);
+    let old_ap = locals.v.len();
+    // Move n arguments to the locals stack.
+    let a1_idx = stack.v.len() - usize::from(n);
+    for i in a1_idx..stack.v.len() {
+        locals.v.push(stack.v[i]);
+    }
+    stack.v.truncate(a1_idx);
+    // Push the old argument pointer.
+    locals.push_usize(old_ap);
+    // Jump to the specified location.
+    let i_addr = stack.pop_int()?;
+    let i_addr_usize = match usize::try_from(i_addr) {
+        Ok(x) => x,
+        Err(_) => {
+            return Err(String::from("invalid address"));
+        }
+    };
+    // Subtract 1 because the interpreter will also increment the
+    // instruction pointer.
+    *ip = i_addr_usize - 1;
+    Ok(())
+}
+
+fn ret(locals: &mut Stack, ip: &mut usize) -> Result<(), String> {
+    let ap = locals.pop_usize()?;
+    locals.v.truncate(ap);
+    let return_address = locals.pop_usize()?;
+    *ip = return_address;
+    Ok(())
+}
+
+trait File: Write + Read {}
+
+struct FileTable<'a> {
+    files: Vec<Box<dyn File + 'a>>,
+}
+
+impl<'a> FileTable<'a> {
+    fn file(&mut self, f: i64) -> Result<&mut (dyn File + 'a), String> {
+        if !(0 <= f && usize::try_from(f).unwrap() < self.files.len()) {
+            return Err(String::from("invalid file"));
+        }
+        Ok(&mut *self.files[usize::try_from(f).unwrap()])
+    }
+}
+
+struct Stdin<'a>(StdinLock<'a>);
+
+impl<'a> Write for Stdin<'a> {
+    fn write(&mut self, _: &[u8]) -> std::io::Result<usize> {
+        Err(std::io::Error::new(
+            std::io::ErrorKind::InvalidInput,
+            "can't write to stdin",
+        ))
+    }
+
+    fn flush(&mut self) -> std::io::Result<()> {
+        Ok(())
+    }
+}
+
+impl<'a> Read for Stdin<'a> {
+    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
+        let Stdin(ref mut handle) = self;
+        handle.read(buf)
+    }
+}
+
+impl<'a> File for Stdin<'a> {}
+
+struct Out<T>(T);
+
+impl<T: Write> Write for Out<T> {
+    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
+        let Out(ref mut handle) = self;
+        handle.write(buf)
+    }
+
+    fn flush(&mut self) -> std::io::Result<()> {
+        let Out(ref mut handle) = self;
+        handle.flush()
+    }
+}
+
+impl<T> Read for Out<T> {
+    fn read(&mut self, _: &mut [u8]) -> std::io::Result<usize> {
+        Err(std::io::Error::new(
+            std::io::ErrorKind::InvalidInput,
+            "invalid file for reading",
+        ))
+    }
+}
+
+impl<T: Write> File for Out<T> {}
+
+fn putc(stack: &mut Stack, files: &mut FileTable) -> Result<(), String> {
+    let file = stack.pop_int()?;
+    let byte = stack.pop_int()?;
+    match files
+        .file(file)?
+        .write(&vec![(byte & 0xff).try_into().unwrap()])
+    {
+        Ok(_) => {
+            stack.push_int(-1);
+        }
+        Err(_) => {
+            stack.push_int(0);
+        }
+    }
+    Ok(())
+}
+
+fn getc(stack: &mut Stack, files: &mut FileTable) -> Result<(), String> {
+    let file = stack.pop_int()?;
+    let mut buf = vec![0];
+    match files.file(file)?.read(&mut buf) {
+        Ok(1) => {
+            stack.push_int(buf[0].into());
+        }
+        Ok(0) => {
+            stack.push_int(-1);
+        }
+        _ => {
+            stack.push_int(0);
+        }
+    }
+    Ok(())
+}
+
+pub fn eval(prog: &[Op]) -> Result<u8, String> {
+    let mut stack = Stack { v: Vec::new() };
+    let mut locals_stack = Stack { v: Vec::new() };
+    let mut heap = Heap::new();
+    let mut ip = 0;
+    let stdin = std::io::stdin();
+    let mut files = FileTable {
+        files: vec![
+            Box::new(Stdin(stdin.lock())),
+            Box::new(Out(BufWriter::new(std::io::stdout()))),
+            Box::new(Out(BufWriter::new(std::io::stderr()))),
+        ],
+    };
+    loop {
+        if ip >= prog.len() {
+            return Err(String::from("invalid instruction pointer"));
+        }
+        match prog[ip] {
+            Op::Const(n) => fn_const(&mut stack, n),
+            Op::Add => add(&mut stack)?,
+            Op::Sub => sub(&mut stack)?,
+            Op::Mul => mul(&mut stack)?,
+            Op::Div => div(&mut stack)?,
+            Op::Mod => fn_mod(&mut stack)?,
+            Op::Alloc => alloc(&mut stack, &mut heap)?,
+            Op::Peek(n) => peek(&mut stack, &heap, n)?,
+            Op::Poke(n) => poke(&mut stack, &mut heap, n)?,
+            Op::PeekByte => peek_byte(&mut stack, &heap)?,
+            Op::PokeByte => poke_byte(&mut stack, &mut heap)?,
+            Op::Pop => pop(&mut stack)?,
+            Op::Local(n) => local(&mut stack, &locals_stack, n)?,
+            Op::If(n) => fn_if(&mut stack, &mut ip, n)?,
+            Op::Call(n) => call(&mut stack, &mut locals_stack, &mut ip, n)?,
+            Op::Ret => ret(&mut locals_stack, &mut ip)?,
+            Op::PutC => putc(&mut stack, &mut files)?,
+            Op::GetC => getc(&mut stack, &mut files)?,
+            Op::Exit => {
+                let n = stack.pop_int()?;
+                return Ok(u8::try_from(n & 0xff).unwrap());
+            }
+        }
+        ip += 1;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::Op::*;
+    use super::*;
+
+    #[test]
+    fn eval_const() {
+        assert_eq!(Ok(5), eval(&vec![Const(5), Exit]));
+    }
+
+    #[test]
+    fn eval_add() {
+        assert_eq!(Ok(10), eval(&vec![Const(5), Const(5), Add, Exit]));
+    }
+
+    #[test]
+    fn eval_sub() {
+        assert_eq!(Ok(2), eval(&vec![Const(5), Const(3), Sub, Exit]));
+    }
+
+    #[test]
+    fn eval_mul() {
+        assert_eq!(Ok(25), eval(&vec![Const(5), Const(5), Mul, Exit]));
+    }
+
+    #[test]
+    fn eval_div() {
+        assert_eq!(Ok(2), eval(&vec![Const(5), Const(2), Div, Exit]));
+    }
+
+    #[test]
+    fn eval_mod() {
+        assert_eq!(Ok(1), eval(&vec![Const(5), Const(2), Mod, Exit]));
+    }
+
+    #[test]
+    fn eval_alloc() {
+        assert_eq!(Ok(0), eval(&vec![Const(10), Alloc, Pop, Const(0), Exit]));
+    }
+
+    #[test]
+    fn eval_peek() {
+        assert_eq!(Ok(0), eval(&vec![Const(8), Alloc, Peek(0), Exit]));
+    }
+
+    #[test]
+    fn eval_poke() {
+        assert_eq!(
+            Ok(0),
+            eval(&vec![Const(5), Const(8), Alloc, Poke(0), Const(0), Exit])
+        );
+    }
+
+    #[test]
+    fn eval_peek_byte() {
+        assert_eq!(Ok(0), eval(&vec![Const(1), Alloc, PeekByte, Exit]));
+    }
+
+    #[test]
+    fn eval_poke_byte() {
+        assert_eq!(
+            Ok(0),
+            eval(&vec![Const(5), Const(1), Alloc, PokeByte, Const(0), Exit])
+        );
+    }
+
+    #[test]
+    fn eval_pop() {
+        assert_eq!(Ok(5), eval(&vec![Const(5), Const(10), Pop, Exit]));
+    }
+
+    #[test]
+    fn eval_if_true() {
+        assert_eq!(
+            Ok(5),
+            eval(&vec![Const(5), Const(1), If(2), Const(5), Add, Exit])
+        );
+    }
+
+    #[test]
+    fn eval_if_false() {
+        assert_eq!(
+            Ok(10),
+            eval(&vec![Const(5), Const(0), If(2), Const(5), Add, Exit])
+        );
+    }
+
+    #[test]
+    fn eval_call() {
+        assert_eq!(
+            Ok(5),
+            eval(&vec![Const(3), Const(5), Call(1), Local(1), Exit])
+        );
+    }
+
+    #[test]
+    fn eval_ret() {
+        assert_eq!(
+            Ok(5),
+            eval(&vec![Const(4), Const(5), Call(1), Exit, Local(1), Ret])
+        );
+    }
+
+    #[test]
+    fn eval_putc() {
+        assert_eq!(
+            Ok(5),
+            eval(&vec![
+                Const(5),
+                Const(88),
+                Const(1),
+                PutC,
+                If(2),
+                Const(5),
+                Add,
+                Exit
+            ])
+        );
+    }
+
+    #[test]
+    fn eval_getc_err() {
+        assert_eq!(Ok(0), eval(&vec![Const(1), GetC, Exit]));
+    }
+}