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.

25 files changed, 1987 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..4756073
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,5 @@
+CSC = guile-compat/csc.fish
+
+.PHONY: test
+test: *.csc
+	$(CSC) <( cat *-test.csc test-main.csc )
diff --git a/bytecode/.gitignore b/bytecode/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/bytecode/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/bytecode/Cargo.lock b/bytecode/Cargo.lock
new file mode 100644
index 0000000..f495832
--- /dev/null
+++ b/bytecode/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "bytecode"
+version = "0.1.0"
diff --git a/bytecode/Cargo.toml b/bytecode/Cargo.toml
new file mode 100644
index 0000000..8303233
--- /dev/null
+++ b/bytecode/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "bytecode"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
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));
+}
diff --git a/format-test.csc b/format-test.csc
new file mode 100644
index 0000000..b7b2c99
--- /dev/null
+++ b/format-test.csc
@@ -0,0 +1,47 @@
+(import (scheme base)
+        (only (csc strings) str-quote)
+        (only (csc testing) define-test errorf subtest)
+        (csc format))
+
+
+(define-test (test-vsprintf t)
+  (define-record-type <test-case>
+    (test-case name fmt args want)
+    test-case?
+    (name name)
+    (fmt fmt)
+    (args args)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "single-string"
+                   "test-string"
+                   '()
+                   "test-string")
+                 (test-case
+                   "list"
+                   "{}"
+                   '((1 2 3))
+                   "(1 2 3)")
+                 (test-case
+                   "complex"
+                   "this {} is {} a {} test"
+                   '((1 2 3) 1 "bbb")
+                   "this (1 2 3) is 1 a bbb test")
+                 (test-case
+                   "escape open"
+                   "{{"
+                   '()
+                   "{")
+                 (test-case
+                   "escape close"
+                   "}}"
+                   '()
+                   "}"))))
+    (for-each
+      (lambda (tc)
+        (subtest t (name tc)
+                 (let ((got (vsprintf (fmt tc) (args tc))))
+                   (unless (equal? got (want tc))
+                     (errorf t "(vsprintf {} {}) = {}, want {}." (str-quote fmt) (args tc) got (want tc))))))
+      tests)))
diff --git a/format.csc b/format.csc
new file mode 100644
index 0000000..2c2da84
--- /dev/null
+++ b/format.csc
@@ -0,0 +1,70 @@
+(define-library (csc format)
+  (export
+    vfprintf
+    fprintf
+    vprintf
+    printf
+    vsprintf
+    sprintf)
+  (import (scheme base)
+          (only (scheme write) display)
+          (only (csc strings)
+                str-find
+                str-not-found-error?
+                str-prefix?))
+  (begin
+
+
+    (define (vfprintf port format-string format-args)
+      (let loop ((start 0)
+                 (args format-args))
+        (cond ((>= start (string-length format-string)))
+              ((str-prefix? "{{" format-string start)
+               (write-string "{" port)
+               (loop (+ 2 start) args))
+              ((str-prefix? "}}" format-string start)
+               (write-string "}" port)
+               (loop (+ 2 start) args))
+              ((str-prefix? "{}" format-string start)
+               (display (car args) port)
+               (loop (+ 2 start) (cdr args)))
+              ((str-prefix? "{" format-string start)
+               (raise (error "invalid format string" format-string)))
+              (else
+                (let* ((open-brace-pos (guard (e
+                                                ((str-not-found-error? e) (string-length format-string)))
+                                              (str-find "{" format-string start)))
+                       (close-brace-pos (guard (e
+                                                 ((str-not-found-error? e) (string-length format-string)))
+                                               (str-find "}" format-string start)))
+                       (format-pos (min open-brace-pos close-brace-pos)))
+                  (write-string format-string port start format-pos)
+                  (loop format-pos args))))))
+
+
+    (define-syntax fprintf
+      (syntax-rules ()
+                    ((_ port format-string format-args ...)
+                     (vfprintf port format-string (list format-args ...)))))
+
+
+    (define (vprintf format-string format-args)
+      (vfprintf (current-output-port) format-string format-args))
+
+
+    (define-syntax printf
+      (syntax-rules ()
+                    ((_ format-string format-args ...)
+                     (vprintf format-string (list format-args ...)))))
+
+
+    (define (vsprintf format-string format-args)
+      (let ((string-builder (open-output-string)))
+        (vfprintf string-builder format-string format-args)
+        (get-output-string string-builder)))
+
+
+    (define-syntax sprintf
+      (syntax-rules ()
+                    ((_ format-string format-args ...)
+                     (vsprintf format-string (list format-args ...)))))))
diff --git a/guile-compat/compat.scm b/guile-compat/compat.scm
new file mode 100644
index 0000000..5997267
--- /dev/null
+++ b/guile-compat/compat.scm
@@ -0,0 +1,3 @@
+(install-r7rs!)
+(set! %load-extensions (cons ".csc" %load-extensions))
+(add-to-load-path (string-append (dirname (current-filename)) "/lib"))
diff --git a/guile-compat/csc.fish b/guile-compat/csc.fish
new file mode 100755
index 0000000..ffda4d2
--- /dev/null
+++ b/guile-compat/csc.fish
@@ -0,0 +1,2 @@
+#!/usr/bin/env fish
+guile -l (dirname (status --current-filename))/compat.scm $argv
diff --git a/guile-compat/lib/csc b/guile-compat/lib/csc
new file mode 120000
index 0000000..c25bddb
--- /dev/null
+++ b/guile-compat/lib/csc
@@ -0,0 +1 @@
+../..
\ No newline at end of file
diff --git a/hash-map-test.csc b/hash-map-test.csc
new file mode 100644
index 0000000..8f51dfa
--- /dev/null
+++ b/hash-map-test.csc
@@ -0,0 +1,98 @@
+(import (scheme base)
+        (only (csc sort) sort)
+        (only (csc testing)
+              define-test
+              errorf
+              subtest)
+        (csc hash-map))
+
+
+(define (hash-symbol s)
+  (hash-bytevector (string->utf8 (symbol->string s))))
+
+
+(define (symbol<? s1 s2)
+  (string<? (symbol->string s1) (symbol->string s2)))
+
+
+(define-test (test-hash-map->alist t)
+  (define-record-type <test-case>
+    (test-case desc vals)
+    test-case?
+    (desc desc)
+    (vals vals))
+  (let ((tests (list
+                 (test-case
+                   "singleton"
+                   '((a . 1)))
+                 (test-case
+                   "two"
+                   '((a . 1) (b . 2)))
+                 (test-case
+                   "longer"
+                   '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6))))))
+    (for-each
+      (lambda (tc)
+        (subtest t (desc tc)
+                 (let* ((m (alist->hash-map hash-symbol symbol<? (vals tc)))
+                        (got (hash-map->alist m)))
+                   (unless (equal?
+                             (sort
+                               (lambda (x1 x2) (symbol<? (car x1) (car x2)))
+                               got)
+                             (sort
+                               (lambda (x1 x2) (symbol<? (car x1) (car x2)))
+                               (vals tc)))
+                     (errorf t "(hash-map->alist {}) = {}, want {}." m got (vals tc))))))
+      tests)))
+
+
+(define-test (test-alist->hash-map t)
+  (define-record-type <test-case>
+    (test-case desc vals want)
+    test-case?
+    (desc desc)
+    (vals vals)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "singleton"
+                   '((a . 1))
+                   '((a . 1)))
+                 (test-case
+                   "two"
+                   '((a . 1) (b . 2))
+                   '((a . 1) (b . 2)))
+                 (test-case
+                   "larger"
+                   '((m . 1) (n . 2) (q . 3) (f . 5) (n . 7) (x . 8))
+                   '((f . 5) (m . 1) (n . 7) (q . 3) (x . 8)))
+                 (test-case
+                   "in-order"
+                   '((a . ()) (b . ()) (c . ()) (d . ()) (e . ()) (f . ()) (g . ()) (h . ()))
+                   '((a . ()) (b . ()) (c . ()) (d . ()) (e . ()) (f . ()) (g . ()) (h . ())))
+                 (test-case
+                   "reversed"
+                   '((h . ()) (g . ()) (f . ()) (e . ()) (d . ()) (c . ()) (b . ()) (a . ()))
+                   '((a . ()) (b . ()) (c . ()) (d . ()) (e . ()) (f . ()) (g . ()) (h . ())))
+                 (test-case
+                   "overwrite"
+                   '((a . 1) (a . 2))
+                   '((a . 2)))
+                 (test-case
+                   "alternating"
+                   '((h . ()) (g . ()) (i . ()) (f . ()) (j . ()) (e . ()) (k . ()) (d . ()) (l . ()) (c . ()))
+                   '((c . ()) (d . ()) (e . ()) (f . ()) (g . ()) (h . ()) (i . ()) (j . ()) (k . ()) (l . ()))))))
+    (for-each
+      (lambda (tc)
+        (subtest t (desc tc)
+                 (let ((got (alist->hash-map hash-symbol symbol<? (vals tc))))
+                   (unless (equal?
+                             (sort
+                               (lambda (x1 x2) (symbol<? (car x1) (car x2)))
+                               (hash-map->alist got))
+                             (sort
+                               (lambda (x1 x2) (symbol<? (car x1) (car x2)))
+                               (want tc)))
+                     (errorf t "(alist->hash-map {}) = {}, want {}." (vals tc) (hash-map->alist got) (want tc))))))
+      tests)))
diff --git a/hash-map.csc b/hash-map.csc
new file mode 100644
index 0000000..2c95b36
--- /dev/null
+++ b/hash-map.csc
@@ -0,0 +1,251 @@
+(define-library (csc hash-map)
+  (export
+    alist->hash-map
+    hash-bytevector
+    hash-map->alist
+    hash-map-foreach
+    hash-map-insert
+    hash-map-lookup
+    hash-map?
+    make-hash-map)
+  (import (scheme base)
+          (only (csc format) sprintf))
+  (begin
+
+
+    (define-record-type <key-hash>
+      (make-key-hash hash k)
+      key-hash?
+      (hash key-hash-hash)
+      (k key-hash-value))
+
+
+    (define (key-hash<? k1 k2 key<?)
+      (cond ((< (key-hash-hash k1) (key-hash-hash k2)) #t)
+            ((> (key-hash-hash k1) (key-hash-hash k2)) #f)
+            ((key<? (key-hash-value k1) (key-hash-value k2)) #t)
+            (else #f)))
+
+
+    (define (key-hash=? k1 k2)
+      (and (= (key-hash-hash k1) (key-hash-hash k2)) (eqv? (key-hash-value k1) (key-hash-value k2))))
+
+
+    (define-record-type <node>
+      (make-node color key-hash val left right)
+      node?
+      (color node-color)
+      (key-hash node-key)
+      (val node-value)
+      (left node-left)
+      (right node-right))
+
+
+    (define (red? n)
+      (if (null? n)
+          #f
+        (eq? 'red (node-color n))))
+
+
+    (define (black? n)
+      (if (null? n)
+          #t
+        (eq? 'black (node-color n))))
+
+
+    (define (rebalance-left m)
+      (let ((p (node-left m))
+            (u (node-right m)))
+        (cond ((or
+                 (and
+                   (red? p)
+                   (red? (node-left p))
+                   (red? u))
+                 (and
+                   (red? p)
+                   (red? (node-right p))
+                   (red? u)))
+               ;     b          r
+               ;    / \        / \
+               ;   r   r =>   b   b
+               ;  /          /
+               ; r          r
+
+               ;   b        r
+               ;  / \      / \
+               ; r   r => b   b
+               ;  \        \
+               ;   r        r
+               (make-node 'red (node-key m) (node-value m)
+                          (make-node 'black (node-key p) (node-value p) (node-left p) (node-right p))
+                          (make-node 'black (node-key u) (node-value u) (node-left u) (node-right u))))
+              ((and
+                 (red? p)
+                 (red? (node-right p))
+                 (black? u))
+               ;   b        b
+               ;  / \      / \
+               ; r   b => r   r
+               ;  \            \
+               ;   r            b
+               (let ((n (node-right p)))
+                 (make-node 'black (node-key n) (node-value n)
+                            (make-node 'red (node-key p) (node-value p) (node-left p) (node-left n))
+                            (make-node 'red (node-key m) (node-value m) (node-right n) u))))
+              ((and
+                 (red? p)
+                 (red? (node-left p))
+                 (black? u))
+               ;     b        b
+               ;    / \      / \
+               ;   r   b => r   r
+               ;  /              \
+               ; r                b
+               (make-node 'black (node-key p) (node-value p)
+                          (node-left p)
+                          (make-node 'red (node-key m) (node-value m) (node-right p) u)))
+              (else m))))
+
+
+    (define (rebalance-right m)
+      (let ((u (node-left m))
+            (p (node-right m)))
+        (cond ((or
+                 (and
+                   (red? u)
+                   (red? p)
+                   (red? (node-left p)))
+                 (and
+                   (red? u)
+                   (red? p)
+                   (red? (node-right p))))
+               ;   b          r
+               ;  / \        / \
+               ; r   r   => b   b
+               ;      \          \
+               ;       r          r
+
+               ;   b        r
+               ;  / \      / \
+               ; r   r => b   b
+               ;    /        /
+               ;   r        r
+               (make-node 'red (node-key m) (node-value m)
+                          (make-node 'black (node-key u) (node-value u) (node-left u) (node-right u))
+                          (make-node 'black (node-key p) (node-value p) (node-left p) (node-right p))))
+              ((and
+                 (black? u)
+                 (red? p)
+                 (red? (node-left p)))
+               ;   b          b
+               ;  / \        / \
+               ; b   r =>   r   r
+               ;    /      /
+               ;   r      b
+               (let ((n (node-left p)))
+                 (make-node 'black (node-key n) (node-value n)
+                            (make-node 'red (node-key m) (node-value m) u (node-left n))
+                            (make-node 'red (node-key p) (node-value p) (node-right n) (node-right p)))))
+              ((and
+                 (black? u)
+                 (red? p)
+                 (red? (node-right p)))
+               ;   b            b
+               ;  / \          / \
+               ; b   r   =>   r   r
+               ;      \      /
+               ;       r    b
+               (make-node 'black (node-key p) (node-value p)
+                          (make-node 'red (node-key m) (node-value m) u (node-left p))
+                          (node-right p)))
+              (else m))))
+
+
+    (define (insert m k v key<?)
+      (cond ((null? m) (make-node 'red k v '() '()))
+            ((key-hash<? k (node-key m) key<?)
+             (rebalance-left
+               (make-node (node-color m) (node-key m) (node-value m)
+                          (insert (node-left m) k v key<?)
+                          (node-right m))))
+            ((key-hash=? k (node-key m)) (make-node (node-color m) k v (node-left m) (node-right m)))
+            (else
+              (rebalance-right
+                (make-node (node-color m) (node-key m) (node-value m)
+                           (node-left m)
+                           (insert (node-right m) k v key<?))))))
+
+
+    (define-record-type <hash-map>
+      (construct-hash-map hash key<? root)
+      hash-map?
+      (hash hash-map-hash)
+      (key<? hash-map-key<?)
+      (root hash-map-root))
+
+
+    (define (make-hash-map hash key<?)
+      (construct-hash-map hash key<? '()))
+
+
+    (define (hash-map-insert m k v)
+      (let* ((shuffle
+               (lambda (hash)
+                 (truncate-remainder
+                   (* #x9e3779b97f4a7c55 hash)
+                   #x10000000000000000)))
+             (res (insert (hash-map-root m) (make-key-hash (shuffle ((hash-map-hash m) k)) k) v (hash-map-key<? m))))
+        (construct-hash-map
+          (hash-map-hash m)
+          (hash-map-key<? m)
+          (make-node 'black (node-key res) (node-value res) (node-left res) (node-right res)))))
+
+
+    (define-record-type <key-not-found-error>
+      (make-key-not-found-error)
+      key-not-found-error?)
+
+
+    (define (hash-map-lookup m k)
+      (letrec ((lookup
+                 (lambda (n)
+                   (cond ((null? n) (raise (make-key-not-found-error)))
+                         ((key-hash<? k (node-key n) (hash-map-key<? m)) (lookup (node-left n)))
+                         ((key-hash=? k (node-key n)) (node-value n))
+                         (else (lookup (node-right n)))))))
+              (lookup (hash-map-root m))))
+
+
+    (define (hash-map-foreach f m)
+      (letrec ((node-foreach
+                 (lambda (n)
+                   (unless (null? n)
+                     (node-foreach (node-left n))
+                     (f (key-hash-value (node-key n)) (node-value n))
+                     (node-foreach (node-right n))))))
+              (node-foreach (hash-map-root m))))
+
+
+    (define (hash-map->alist m)
+      (let ((alist '()))
+        (hash-map-foreach
+          (lambda (k v)
+            (set! alist (cons (cons k v) alist)))
+          m)
+        alist))
+
+
+    (define (alist->hash-map hash key<? alist)
+      (let loop ((alist alist)
+                 (m (make-hash-map hash key<?)))
+        (if (null? alist)
+            m
+          (loop (cdr alist) (hash-map-insert m (caar alist) (cdar alist))))))
+
+
+    (define (hash-bytevector b)
+      (let loop ((i 0)
+                 (hash 0))
+        (if (>= i (bytevector-length b))
+            hash
+          (loop (+ 1 i) (+ (* hash #x100) (bytevector-u8-ref b i))))))))
diff --git a/list-test.csc b/list-test.csc
new file mode 100644
index 0000000..ec4b4ed
--- /dev/null
+++ b/list-test.csc
@@ -0,0 +1,127 @@
+(import (scheme base)
+        (only (csc testing) define-test errorf)
+        (csc list))
+
+
+(define-test (test-take t)
+  (define-record-type <test-case>
+    (test-case desc n xs want)
+    test-case?
+    (desc desc)
+    (n n)
+    (xs xs)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "simple"
+                   3
+                   '(1 2 3 4 5)
+                   '(1 2 3))
+                 (test-case
+                   "negative"
+                   -5
+                   '(1 2 3)
+                   '())
+                 (test-case
+                   "zero"
+                   0
+                   '(1 2 3)
+                   '())
+                 (test-case
+                   "short list"
+                   5
+                   '(1 2 3)
+                   '(1 2 3))
+                 (test-case
+                   "take whole list"
+                   3
+                   '(1 2 3)
+                   '(1 2 3)))))
+    (for-each
+      (lambda (tc)
+        (let ((got (take (n tc) (xs tc))))
+          (unless (equal? got (want tc))
+            (errorf t "(got {} {}) = {}, want {}." (n tc) (xs tc) got (want tc)))))
+      tests)))
+
+
+(define-test (test-split-at t)
+  (define-record-type <test-case>
+    (test-case desc n xs want-a want-b)
+    test-case?
+    (desc desc)
+    (n n)
+    (xs xs)
+    (want-a want-a)
+    (want-b want-b))
+  (let ((tests (list
+                 (test-case
+                   "simple"
+                   2
+                   '(1 2 3 4)
+                   '(1 2)
+                   '(3 4))
+                 (test-case
+                   "negative"
+                   -5
+                   '(1 2 3)
+                   '()
+                   '(1 2 3))
+                 (test-case
+                   "zero"
+                   0
+                   '(1 2 3)
+                   '()
+                   '(1 2 3))
+                 (test-case
+                   "short list"
+                   5
+                   '(1 2 3)
+                   '(1 2 3)
+                   '())
+                 (test-case
+                   "whole list"
+                   3
+                   '(1 2 3)
+                   '(1 2 3)
+                   '()))))
+    (for-each
+      (lambda (tc)
+        (let-values (((got-a got-b) (split-at (n tc) (xs tc))))
+          (unless (equal? got-a (want-a tc))
+            (errorf t "(split-at {} {}) = (values {}, _), want {}." (n tc) (xs tc) got-a (want-a tc)))
+          (unless (equal? got-b (want-b tc))
+            (errorf t "(split-at {} {}) = (values _, {}), want {}." (n tc) (xs tc) got-b (want-b tc)))))
+      tests)))
+
+
+(define-test (test-revappend t)
+  (define-record-type <test-case>
+    (test-case desc a b want)
+    test-case?
+    (desc desc)
+    (a a)
+    (b b)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "threes"
+                   '(3 2 1)
+                   '(4 5 6)
+                   '(1 2 3 4 5 6))
+                 (test-case
+                   "empty first list"
+                   '()
+                   '(1 2 3)
+                   '(1 2 3))
+                 (test-case
+                   "empty second list"
+                   '(3 2 1)
+                   '()
+                   '(1 2 3)))))
+    (for-each
+      (lambda (tc)
+        (let ((got (revappend (a tc) (b tc))))
+          (unless (equal? got (want tc))
+            (errorf t "(revappend {} {}) = {}, want {}." (a tc) (b tc) got (want tc)))))
+      tests)))
diff --git a/list.csc b/list.csc
new file mode 100644
index 0000000..c4bc013
--- /dev/null
+++ b/list.csc
@@ -0,0 +1,33 @@
+(define-library (csc list)
+  (export
+    revappend
+    split-at
+    take)
+  (import (scheme base))
+  (begin
+
+
+    (define (take n xs)
+      (let loop ((n n)
+                 (xs xs)
+                 (acc '()))
+        (if (or (not (positive? n)) (null? xs))
+            (reverse acc)
+          (loop (- n 1) (cdr xs) (cons (car xs) acc)))))
+
+
+    (define (split-at n xs)
+      (let loop ((n n)
+                 (xs xs)
+                 (acc '()))
+        (if (or (not (positive? n)) (null? xs))
+            (values (reverse acc) xs)
+          (loop (- n 1) (cdr xs) (cons (car xs) acc)))))
+
+
+    (define (revappend a b)
+      (let loop ((xs a)
+                 (acc b))
+        (if (null? xs)
+            acc
+          (loop (cdr xs) (cons (car xs) acc)))))))
diff --git a/sort-test.csc b/sort-test.csc
new file mode 100644
index 0000000..b922484
--- /dev/null
+++ b/sort-test.csc
@@ -0,0 +1,45 @@
+(import (scheme base)
+        (only (csc testing)
+              define-test
+              errorf)
+        (csc sort))
+
+
+(define-test (test-sort t)
+  (define-record-type <test-case>
+    (test-case desc xs want)
+    test-case?
+    (desc desc)
+    (xs xs)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "ten elem"
+                   '(9 4 5 100 3 2 4 6 0 -2)
+                   '(-2 0 2 3 4 4 5 6 9 100))
+                 (test-case
+                   "empty"
+                   '()
+                   '())
+                 (test-case
+                   "singleton"
+                   '(1)
+                   '(1))
+                 (test-case
+                   "two"
+                   '(2 1)
+                   '(1 2))
+                 (test-case
+                   "reversed"
+                   '(20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1)
+                   '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))
+                 (test-case
+                   "already sorted"
+                   '(1 2 3 4 5 6 7 8 9 10)
+                   '(1 2 3 4 5 6 7 8 9 10)))))
+    (for-each
+      (lambda (tc)
+        (let ((got (sort (lambda (x1 x2) (< x1 x2)) (xs tc))))
+          (unless (equal? got (want tc))
+            (errorf t "(sort {}) = {}, want {}." (xs tc) got (want tc)))))
+      tests)))
diff --git a/sort.csc b/sort.csc
new file mode 100644
index 0000000..62b1c9d
--- /dev/null
+++ b/sort.csc
@@ -0,0 +1,24 @@
+(define-library (csc sort)
+  (export sort)
+  (import (scheme base)
+          (only (csc list)
+                revappend
+                split-at))
+  (begin
+
+
+    (define (sort cmp xs)
+      (let ((len (length xs)))
+        (if (<= len 1)
+            xs
+          (let-values (((half-a half-b) (split-at (truncate-quotient len 2) xs)))
+            (let ((sorted-half-a (sort cmp half-a))
+                  (sorted-half-b (sort cmp half-b)))
+              (let loop ((a sorted-half-a)
+                         (b sorted-half-b)
+                         (acc '()))
+                (cond ((null? a) (revappend acc b))
+                      ((null? b) (revappend acc a))
+                      ((cmp (car b) (car a))
+                       (loop a (cdr b) (cons (car b) acc)))
+                      (else (loop (cdr a) b (cons (car a) acc))))))))))))
diff --git a/strings-test.csc b/strings-test.csc
new file mode 100644
index 0000000..f7c8e53
--- /dev/null
+++ b/strings-test.csc
@@ -0,0 +1,103 @@
+(import (scheme base)
+        (only (csc testing)
+              define-test
+              errorf
+              subtest)
+        (csc strings))
+
+
+(define-test (test-str-prefix? t)
+  (define-record-type <test-case>
+    (test-case name prefix str want)
+    test-case?
+    (name name)
+    (prefix prefix)
+    (str str)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "good"
+                   "asdf"
+                   "asdfjkl;"
+                   #t)
+                 (test-case
+                   "bad"
+                   "asdf"
+                   "asdbjkl;"
+                   #f)
+                 (test-case
+                   "too long"
+                   "asdf"
+                   "as"
+                   #f))))
+    (for-each
+      (lambda (tc)
+        (subtest t (name tc)
+                 (let ((got (str-prefix? (prefix tc) (str tc))))
+                   (unless (eq? got (want tc))
+                     (errorf t "(str-prefix? {} {}) = {}, want {}" (str-quote (prefix tc)) (str-quote (str tc)) got (want tc))))))
+      tests)))
+
+
+(define-test (test-str-quote t)
+  (define-record-type <test-case>
+    (test-case name str want)
+    test-case?
+    (name name)
+    (str str)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "simple"
+                   "hello"
+                   "\"hello\"")
+                 (test-case
+                   "escape"
+                   "this string \" has a quote"
+                   "\"this string \\\" has a quote\""))))
+    (for-each
+      (lambda (tc)
+        (subtest t (name tc)
+                 (let ((got (str-quote (str tc))))
+                   (unless (equal? got (want tc))
+                     (errorf t "(str-quote {}) = {}, want {}" (str tc) (got tc) (want tc))))))
+      tests)))
+
+
+(define-test (test-str-find t)
+  (define-record-type <test-case>
+    (test-case name match str want)
+    test-case?
+    (name name)
+    (match match)
+    (str str)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "ok"
+                   "abc"
+                   "dabsadfdabcdfdfd"
+                   8)
+                 (test-case
+                   "one letter"
+                   "a"
+                   "sdfdfdfsasdfe"
+                   8))))
+    (for-each
+      (lambda (tc)
+        (subtest t (name tc)
+                 (let ((got (str-find (match tc) (str tc))))
+                   (unless (= got (want tc))
+                     (errorf t "(str-find {} {}) = {}, want {}" (str-quote (match tc)) (str-quote (str tc)) got (want tc))))))
+      tests)))
+
+
+(define-test (test-str-find-notfound t)
+  (let* ((match "a")
+         (str "def")
+         (got-exception '()))
+    (guard (e
+             ((str-not-found-error? e) (set! got-exception e)))
+           (str-find match str))
+    (unless (str-not-found-error? got-exception)
+      (errorf t "str-find succeeded, wanted <str-not-found-error>"))))
diff --git a/strings.csc b/strings.csc
new file mode 100644
index 0000000..963565c
--- /dev/null
+++ b/strings.csc
@@ -0,0 +1,42 @@
+(define-library (csc strings)
+  (export
+    str-find
+    str-not-found-error?
+    str-prefix?
+    str-quote)
+  (import (scheme base)
+          (scheme case-lambda)
+          (only (scheme write) write))
+  (begin
+
+
+    (define str-prefix?
+      (let ((str-prefix?' (lambda (prefix str start)
+                            (and (<= (string-length prefix) (- (string-length str) start))
+                                 (string=? prefix (substring str start (+ start (string-length prefix))))))))
+        (case-lambda
+          ((prefix str) (str-prefix?' prefix str 0))
+          ((prefix str start) (str-prefix?' prefix str start)))))
+
+
+    (define (str-quote s)
+      (let ((out (open-output-string)))
+        (write s out)
+        (get-output-string out)))
+
+
+    (define-record-type <str-not-found-error>
+      (make-str-not-found-error)
+      str-not-found-error?)
+
+
+    (define str-find
+      (let ((str-find' (lambda (match str start end)
+                         (let loop ((i start))
+                           (cond ((>= i end) (raise (make-str-not-found-error)))
+                                 ((str-prefix? match str i) i)
+                                 (else (loop (+ 1 i))))))))
+        (case-lambda
+          ((match str) (str-find' match str 0 (string-length str)))
+          ((match str start) (str-find' match str start (string-length str)))
+          ((match str start end) (str-find' match str start end)))))))
diff --git a/test-main.csc b/test-main.csc
new file mode 100644
index 0000000..a8c3a6e
--- /dev/null
+++ b/test-main.csc
@@ -0,0 +1,5 @@
+(import (scheme base)
+        (only (csc testing) test-main))
+
+
+(test-main)
diff --git a/testing.csc b/testing.csc
new file mode 100644
index 0000000..f221388
--- /dev/null
+++ b/testing.csc
@@ -0,0 +1,104 @@
+(define-library (csc testing)
+  (export
+    define-test
+    errorf
+    fatalf
+    test-main
+    subtest)
+  (import (scheme base)
+          (only (csc format)
+                printf
+                sprintf)
+          (only (csc vec)
+                vec
+                vec-append
+                vec-length
+                vec-ref))
+  (begin
+
+
+    (define *all-tests-succeeded* #t)
+
+
+    (define (set-all-succeeded! val) (set! *all-tests-succeeded* val))
+
+
+    (define-record-type <test-handle>
+      (make-test-handle test-name subtest-name succeeded subtests-succeeded)
+      test-handle?
+      (test-name base-test-name)
+      (subtest-name subtest-name)
+      (succeeded test-succeeded? set-succeeded!)
+      (subtests-succeeded subtests-succeeded set-subtests-succeeded!))
+
+
+    (define (test-name t)
+      (let ((sn (subtest-name t)))
+        (if (equal? sn "")
+            (base-test-name t)
+          (sprintf "{}/{}" (base-test-name t) sn))))
+
+
+    (define-record-type <test-error>
+      (make-test-error)
+      test-error?)
+
+
+    (define-syntax define-test
+      (syntax-rules ()
+                    ((_ (name t) body ...)
+                     (let ((t (make-test-handle (symbol->string 'name) "" #t (vec))))
+                       (printf "=== RUN   {}\n" 'name)
+                       (guard (e ((test-error? e))
+                                 #;(else
+                                 (errorf t "{}" e)))
+                       body ...)
+                     (if (test-succeeded? t)
+                         (printf "--- PASS: {}\n" 'name)
+                       (begin
+                         (printf "--- FAIL: {}\n" 'name)
+                         (set-all-succeeded! #f)))
+                     (do ((i 0 (+ 1 i)))
+                         ((>= i (vec-length (subtests-succeeded t))))
+                       (printf "    --- {}: {}/{}\n"
+                               (if (cdr (vec-ref (subtests-succeeded t) i)) "PASS" "FAIL")
+                               'name
+                               (car (vec-ref (subtests-succeeded t) i))))))))
+
+
+  (define-syntax subtest
+    (syntax-rules ()
+                  ((_ t name body ...)
+                   (let ((old-t t)
+                         (t (make-test-handle (test-name t) name #t (vec))))
+                     (printf "=== RUN   {}\n" (test-name t))
+                     (guard (e ((test-error? e))
+                               #;(else
+                               (errorf t "{}" e)))
+                     body ...)
+                   (let ((succ (test-succeeded? t)))
+                     (set-subtests-succeeded! old-t (vec-append (subtests-succeeded old-t) (cons name succ)))
+                     (unless succ
+                       (set-succeeded! old-t #f)))))))
+
+
+    (define-syntax errorf
+      (syntax-rules ()
+                    ((_ t format-string format-args ...)
+                     (begin
+                       (set-succeeded! t #f)
+                       (printf "{}: {}\n" (test-name t) (sprintf format-string format-args ...))))))
+
+
+    (define-syntax fatalf
+      (syntax-rules ()
+                    ((_ t format-string format-args ...)
+                     (begin
+                       (errorf t format-string format-args ...)
+                       (raise (make-test-error))))))
+
+
+    (define (test-main)
+      (if *all-tests-succeeded*
+          (printf "PASS\n")
+        (printf "FAIL\n")))))
diff --git a/vec-test.csc b/vec-test.csc
new file mode 100644
index 0000000..681a7c0
--- /dev/null
+++ b/vec-test.csc
@@ -0,0 +1,94 @@
+(import (scheme base)
+        (only (csc testing)
+              subtest
+              define-test
+              errorf)
+        (csc vec))
+
+
+(define-test (test-vec t)
+  (define-record-type <test-case>
+    (test-case desc args want)
+    test-case?
+    (desc desc)
+    (args args)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "empty"
+                   '()
+                   '())
+                 (test-case
+                   "singleton"
+                   '(1)
+                   '(1)))))
+    (for-each
+      (lambda (tc)
+        (subtest t (desc tc)
+                 (let ((got (apply vec (args tc))))
+                   (unless (equal? (vec->list got) (want tc))
+                     (errorf t "(apply vec {}) = {}, want {}." (args tc) got (want tc)))
+                   (unless (equal? (vec-length got) (length (want tc)))
+                     (errorf t "(apply vec {}) length = {}, want {}." (args tc) (vec-length got) (length (want tc)))))))
+      tests)))
+
+
+(define-test (test-vec-append t)
+  (define-record-type <test-case>
+    (test-case desc in arg want)
+    test-case?
+    (desc desc)
+    (in in)
+    (arg arg)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "append to empty"
+                   '()
+                   1
+                   '(1))
+                 (test-case
+                   "append to singleton"
+                   '(1)
+                   2
+                   '(1 2))
+                 (test-case
+                   "append to 2-elem"
+                   '(1 2)
+                   3
+                   '(1 2 3)))))
+    (for-each
+      (lambda (tc)
+        (subtest t (desc tc)
+                 (let* ((v (list->vec (in tc)))
+                        (got (vec-append v (arg tc))))
+                   (unless (equal? (vec->list got) (want tc))
+                     (errorf t "(vec-append {} {}) = {}, want {}." v (arg tc) got (want tc))))))
+      tests)))
+
+
+(define-test (test-vec-ref t)
+  (define-record-type <test-case>
+    (test-case desc xs k want)
+    test-case?
+    (desc desc)
+    (xs xs)
+    (k k)
+    (want want))
+  (let ((tests (list
+                 (test-case
+                   "1"
+                   '(1 2)
+                   1
+                   2)
+                 (test-case
+                   "singleton"
+                   '(1)
+                   0
+                   1))))
+    (for-each
+      (lambda (tc)
+        (let ((got (vec-ref (list->vec (xs tc)) (k tc))))
+          (unless (= got (want tc))
+            (errorf t "(vec-ref {} {}) = {}, want {}." (xs tc) (k tc) got (want tc)))))
+      tests)))
diff --git a/vec.csc b/vec.csc
new file mode 100644
index 0000000..03f2b0f
--- /dev/null
+++ b/vec.csc
@@ -0,0 +1,54 @@
+(define-library (csc vec)
+  (export
+    list->vec
+    vec
+    vec->list
+    vec-append
+    vec-length
+    vec-ref
+    vec?)
+  (import (scheme base))
+  (begin
+
+
+    (define-record-type <vec>
+      (make-vec len arr)
+      vec?
+      (len vec-length)
+      (arr vec-arr))
+
+
+    (define (list->vec l)
+      (let ((arr (list->vector l)))
+        (make-vec (vector-length arr) arr)))
+
+
+    (define (vec->list v)
+      (vector->list (vec-arr v) 0 (vec-length v)))
+
+
+    (define (vec . xs)
+      (list->vec xs))
+
+
+    (define (vec-append v . xs)
+      (let ((append-one
+              (lambda (v x)
+                (let ((new-v (if (> (vector-length (vec-arr v)) (vec-length v))
+                                 v
+                               (let ((new-arr (make-vector (max 1 (* 2 (vec-length v))))))
+                                 (vector-copy! new-arr 0 (vec-arr v))
+                                 (make-vec (vec-length v) new-arr)))))
+                  (vector-set! (vec-arr new-v) (vec-length new-v) x)
+                  (make-vec (+ 1 (vec-length new-v)) (vec-arr new-v))))))
+        (let loop ((v v)
+                   (xs xs))
+          (if (null? xs)
+              v
+            (loop (append-one v (car xs)) (cdr xs))))))
+
+
+    (define (vec-ref v k)
+      (if (>= k (vec-length v))
+          (error "index out of bounds" k)
+        (vector-ref (vec-arr v) k)))))