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.

4 files changed, 863 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]));
+    }
+}
diff --git a/bytecode/src/encoding.rs b/bytecode/src/encoding.rs
new file mode 100644
index 0000000..b3a7983
--- /dev/null
+++ b/bytecode/src/encoding.rs
@@ -0,0 +1,225 @@
+use crate::bytecode::Op;
+use std::io::Read;
+
+fn read_tag<T: Read>(prog: &mut T) -> Result<u64, String> {
+    let mut buf = [0; 8];
+    match prog.read_exact(&mut buf) {
+        Ok(()) => (),
+        Err(_) => {
+            return Err(String::from("error reading input"));
+        }
+    };
+    Ok(u64::from_le_bytes(buf))
+}
+
+fn read_i64<T: Read>(prog: &mut T) -> Result<i64, String> {
+    let mut buf = [0; 8];
+    match prog.read_exact(&mut buf) {
+        Ok(()) => (),
+        Err(_) => {
+            return Err(String::from("error reading input"));
+        }
+    };
+    Ok(i64::from_le_bytes(buf))
+}
+
+fn read_u8<T: Read>(prog: &mut T) -> Result<u8, String> {
+    let mut buf = vec![0];
+    match prog.read_exact(&mut buf) {
+        Ok(()) => (),
+        Err(_) => {
+            return Err(String::from("error reading input"));
+        }
+    };
+    Ok(buf[0])
+}
+
+fn op_decoding<T: Read>(prog: &mut T) -> Result<Op, String> {
+    let op = match read_tag(prog)? {
+        1010 => Op::Const(read_i64(prog)?),
+        1020 => Op::Add,
+        1030 => Op::Sub,
+        1040 => Op::Mul,
+        1050 => Op::Div,
+        1060 => Op::Mod,
+        2010 => Op::Alloc,
+        2020 => Op::Peek(read_u8(prog)?),
+        2030 => Op::Poke(read_u8(prog)?),
+        2040 => Op::PeekByte,
+        2050 => Op::PokeByte,
+        3010 => Op::Pop,
+        3020 => Op::Local(read_u8(prog)?),
+        4010 => Op::If(read_i64(prog)?),
+        4020 => Op::Call(read_u8(prog)?),
+        4030 => Op::Ret,
+        4040 => Op::Exit,
+        5010 => Op::PutC,
+        5020 => Op::GetC,
+        _ => {
+            return Err(String::from("invalid opcode"));
+        }
+    };
+    Ok(op)
+}
+
+pub fn decode(prog: &[u8]) -> Result<Vec<Op>, String> {
+    let mut reader = prog;
+    let mut out = Vec::new();
+    while reader.len() > 0 {
+        out.push(op_decoding(&mut reader)?);
+    }
+    Ok(out)
+}
+
+mod tests {
+    use super::*;
+
+    #[test]
+    fn decode_const() {
+        assert_eq!(
+            Ok(vec![Op::Const(10)]),
+            decode(&vec![0xf2, 0x3, 0, 0, 0, 0, 0, 0, 0xa, 0, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_add() {
+        assert_eq!(
+            Ok(vec![Op::Add]),
+            decode(&vec![0xfc, 0x3, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_sub() {
+        assert_eq!(Ok(vec![Op::Sub]), decode(&vec![0x6, 0x4, 0, 0, 0, 0, 0, 0]));
+    }
+
+    #[test]
+    fn decode_mul() {
+        assert_eq!(
+            Ok(vec![Op::Mul]),
+            decode(&vec![0x10, 0x4, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_div() {
+        assert_eq!(
+            Ok(vec![Op::Div]),
+            decode(&vec![0x1a, 0x4, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_mod() {
+        assert_eq!(
+            Ok(vec![Op::Mod]),
+            decode(&vec![0x24, 0x4, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_alloc() {
+        assert_eq!(
+            Ok(vec![Op::Alloc]),
+            decode(&vec![0xda, 0x7, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_peek() {
+        assert_eq!(
+            Ok(vec![Op::Peek(10)]),
+            decode(&vec![0xe4, 0x7, 0, 0, 0, 0, 0, 0, 0xa])
+        );
+    }
+
+    #[test]
+    fn decode_poke() {
+        assert_eq!(
+            Ok(vec![Op::Poke(10)]),
+            decode(&vec![0xee, 0x7, 0, 0, 0, 0, 0, 0, 0xa])
+        );
+    }
+
+    #[test]
+    fn decode_peek_byte() {
+        assert_eq!(
+            Ok(vec![Op::PeekByte]),
+            decode(&vec![0xf8, 0x7, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_poke_byte() {
+        assert_eq!(
+            Ok(vec![Op::PokeByte]),
+            decode(&vec![0x2, 0x8, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_pop() {
+        assert_eq!(
+            Ok(vec![Op::Pop]),
+            decode(&vec![0xc2, 0xb, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_local() {
+        assert_eq!(
+            Ok(vec![Op::Local(10)]),
+            decode(&vec![0xcc, 0xb, 0, 0, 0, 0, 0, 0, 0xa])
+        );
+    }
+
+    #[test]
+    fn decode_if() {
+        assert_eq!(
+            Ok(vec![Op::If(10)]),
+            decode(&vec![0xaa, 0xf, 0, 0, 0, 0, 0, 0, 0xa, 0, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_call() {
+        assert_eq!(
+            Ok(vec![Op::Call(10)]),
+            decode(&vec![0xb4, 0xf, 0, 0, 0, 0, 0, 0, 0xa])
+        );
+    }
+
+    #[test]
+    fn decode_ret() {
+        assert_eq!(
+            Ok(vec![Op::Ret]),
+            decode(&vec![0xbe, 0xf, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_exit() {
+        assert_eq!(
+            Ok(vec![Op::Exit]),
+            decode(&vec![0xc8, 0xf, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_putc() {
+        assert_eq!(
+            Ok(vec![Op::PutC]),
+            decode(&vec![0x92, 0x13, 0, 0, 0, 0, 0, 0])
+        );
+    }
+
+    #[test]
+    fn decode_getc() {
+        assert_eq!(
+            Ok(vec![Op::GetC]),
+            decode(&vec![0x9c, 0x13, 0, 0, 0, 0, 0, 0])
+        );
+    }
+}
diff --git a/bytecode/src/heap.rs b/bytecode/src/heap.rs
new file mode 100644
index 0000000..d76456a
--- /dev/null
+++ b/bytecode/src/heap.rs
@@ -0,0 +1,82 @@
+fn transmute(p: &u8) -> Result<&u64, String> {
+    let u8_p = p as *const u8;
+    let u64_p = u8_p as *const u64;
+    if u64_p as usize % 8 != 0 {
+        return Err(String::from("not aligned"));
+    }
+    unsafe {
+        return Ok(&*u64_p);
+    }
+}
+
+fn transmute_mut(p: &mut u8) -> Result<&mut u64, String> {
+    let u8_p = p as *mut u8;
+    let u64_p = u8_p as *mut u64;
+    if u64_p as usize % 8 != 0 {
+        return Err(String::from("not aligned"));
+    }
+    unsafe {
+        return Ok(&mut *u64_p);
+    }
+}
+
+pub struct Heap {
+    heap: Vec<u8>,
+}
+
+pub struct Pointer(usize);
+
+impl Heap {
+    pub fn new() -> Self {
+        Heap {
+            heap: vec![0; 128], // 1 kB
+        }
+    }
+
+    pub fn alloc(&mut self, n: usize) -> Pointer {
+        let p = Pointer(self.heap.len());
+        self.heap.append(&mut vec![0; n]);
+        p
+    }
+
+    pub fn peek(&self, p: Pointer) -> Result<u64, String> {
+        let Pointer(x) = p;
+        let u8_p = &self.heap[x];
+        let u64_p = transmute(u8_p)?;
+        Ok(*u64_p)
+    }
+
+    pub fn poke(&mut self, u: u64, p: Pointer) -> Result<(), String> {
+        let Pointer(x) = p;
+        let u8_p = &mut self.heap[x];
+        let u64_p = transmute_mut(u8_p)?;
+        *u64_p = u;
+        Ok(())
+    }
+
+    pub fn peek_byte(&self, p: Pointer) -> u8 {
+        let Pointer(x) = p;
+        self.heap[x]
+    }
+
+    pub fn poke_byte(&mut self, u: u8, p: Pointer) {
+        let Pointer(x) = p;
+        self.heap[x] = u;
+    }
+}
+
+impl Pointer {
+    pub fn from_bytes(p: u64) -> Self {
+        Pointer(usize::try_from(p).unwrap() >> 1)
+    }
+
+    pub fn bytes(&self) -> u64 {
+        let Pointer(x) = self;
+        u64::try_from(*x).unwrap() << 1
+    }
+
+    pub fn offset(&self, off: u8) -> Pointer {
+        let Pointer(x) = self;
+        Pointer(*x + usize::from(off))
+    }
+}
diff --git a/bytecode/src/main.rs b/bytecode/src/main.rs
new file mode 100644
index 0000000..b5a05ef
--- /dev/null
+++ b/bytecode/src/main.rs
@@ -0,0 +1,13 @@
+mod bytecode;
+mod encoding;
+mod heap;
+
+use std::io::Read;
+
+fn main() {
+    let mut buf = Vec::new();
+    std::io::stdin().lock().read_to_end(&mut buf).unwrap();
+    let prog = encoding::decode(&buf).unwrap();
+    let exit_code = bytecode::eval(&prog).unwrap();
+    std::process::exit(i32::from(exit_code));
+}