Replace generic list AST with typed expression tree

Each form (fn, let, for, set, do, call) now has its own variant with named fields instead of being a
plain list.

6 files changed, 1510 insertions, 156 deletions

diff --git a/compiler/src/ast/error.rs b/compiler/src/ast/error.rs
index 38b3916..5598376 100644
--- a/compiler/src/ast/error.rs
+++ b/compiler/src/ast/error.rs
@@ -10,8 +10,10 @@ pub enum Error {
     UnexpectedEscapeChar(char),
 
     // Par
-    UnexpectedRightPar,
-    UnclosedLeftPar,
+    UnexpectedClosePar,
+    UnclosedPar,
+
+    UnexpectedToken,
 
     UnexpectedEof,
 
@@ -26,8 +28,9 @@ impl fmt::Display for Error {
             }
             Error::UnclosedString(string) => write!(f, "unclosed string {string:?}"),
             Error::UnexpectedEscapeChar(ch) => write!(f, "unexpected escape char {ch:?}"),
-            Error::UnexpectedRightPar => write!(f, "unexpected right par"),
-            Error::UnclosedLeftPar => write!(f, "unclosed left par"),
+            Error::UnexpectedClosePar => write!(f, "unexpected `)`"),
+            Error::UnclosedPar => write!(f, "unclosed `(`"),
+            Error::UnexpectedToken => write!(f, "unexpected token"),
             Error::UnexpectedEof => write!(f, "unexpected eof"),
             Error::RecursionLimit => write!(f, "recursion limit"),
         }
diff --git a/compiler/src/ast/mod.rs b/compiler/src/ast/mod.rs
index 2a0be03..afd459e 100644
--- a/compiler/src/ast/mod.rs
+++ b/compiler/src/ast/mod.rs
@@ -3,7 +3,7 @@ mod models;
 mod parser;
 
 pub use error::Error;
-pub use models::{Ast, Atom, Expr};
+pub use models::{Ast, Atom, Expr, LetVar};
 pub use parser::Parser;
 
 #[cfg(test)]
diff --git a/compiler/src/ast/models.rs b/compiler/src/ast/models.rs
index 2a8c5ae..64fec19 100644
--- a/compiler/src/ast/models.rs
+++ b/compiler/src/ast/models.rs
@@ -2,22 +2,56 @@ use std::rc::Rc;
 
 use crate::span::Spanned;
 
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct LetVar {
+    pub name: Spanned<Rc<str>>,
+    pub expr: Spanned<Expr>,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
 pub enum Atom {
-    Integer(i64),
-    String(Rc<str>),
-    Symbol(Rc<str>),
+    Int(i64),
+    Str(Rc<str>),
+    Sym(Rc<str>),
     Bool(bool),
     Nil,
 }
 
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Clone, Debug, PartialEq, Eq)]
 pub enum Expr {
+    Fn {
+        name: Spanned<Rc<str>>,
+        args: Vec<Spanned<Rc<str>>>,
+        body: Vec<Spanned<Expr>>,
+    },
+    Const {
+        vars: Vec<Spanned<LetVar>>,
+    },
+    Let {
+        vars: Vec<Spanned<LetVar>>,
+        body: Vec<Spanned<Expr>>,
+    },
+    For {
+        loop_var: Spanned<Rc<str>>,
+        from: Spanned<Box<Expr>>,
+        to: Spanned<Box<Expr>>,
+        body: Vec<Spanned<Expr>>,
+    },
+    Set {
+        target_var: Spanned<Rc<str>>,
+        expr: Spanned<Box<Expr>>,
+    },
+    Do {
+        body: Vec<Spanned<Expr>>,
+    },
+    Call {
+        fn_name: Spanned<Rc<str>>,
+        args: Vec<Spanned<Expr>>,
+    },
     Atom(Atom),
-    List(Vec<Spanned<Expr>>),
 }
 
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Clone, Debug, PartialEq, Eq)]
 pub struct Ast(Vec<Spanned<Expr>>);
 
 impl Ast {
diff --git a/compiler/src/ast/parser.rs b/compiler/src/ast/parser.rs
index 4b4f949..12a6f0d 100644
--- a/compiler/src/ast/parser.rs
+++ b/compiler/src/ast/parser.rs
@@ -1,7 +1,7 @@
-use std::iter::Peekable;
+use std::{iter::Peekable, rc::Rc};
 
 use crate::{
-    ast::{Ast, Atom, Error, Expr},
+    ast::{Ast, Atom, Error, Expr, models::LetVar},
     lex::Token,
     span::{Pos, Span, Spanned},
 };
@@ -10,7 +10,7 @@ pub(super) const MAX_DEPTH: usize = 256; // TODO: make it a compile flag
 
 fn parse_number(number: &str) -> Result<Atom, Error> {
     match number.parse() {
-        Ok(ok) => Ok(Atom::Integer(ok)),
+        Ok(ok) => Ok(Atom::Int(ok)),
         Err(err) => Err(Error::InvalidIntegerLiteral(number.into(), err)),
     }
 }
@@ -41,7 +41,7 @@ fn parse_string(string: &str) -> Result<Atom, Error> {
         return Err(Error::UnclosedString(string.into()));
     }
 
-    Ok(Atom::String(result.into()))
+    Ok(Atom::Str(result.into()))
 }
 
 fn parse_symbol(symbol: &str) -> Atom {
@@ -49,7 +49,7 @@ fn parse_symbol(symbol: &str) -> Atom {
         "true" => Atom::Bool(true),
         "false" => Atom::Bool(false),
         "nil" => Atom::Nil,
-        _ => Atom::Symbol(symbol.into()),
+        _ => Atom::Sym(symbol.into()),
     }
 }
 
@@ -78,50 +78,275 @@ where
         self.tokens.peek().copied()
     }
 
-    fn consume(&mut self) -> Option<Spanned<Token<'a>>> {
-        self.tokens
-            .next()
-            .inspect(|s| self.last_token_span = s.span)
+    fn peek_token(&mut self) -> Result<Spanned<Token<'a>>, Spanned<Error>> {
+        match self.peek() {
+            Some(token) => Ok(token),
+            None => Err(Spanned::new(Error::UnexpectedEof, self.last_token_span)),
+        }
     }
 
-    fn parse_expr(&mut self) -> Result<Spanned<Expr>, Spanned<Error>> {
-        let Spanned { inner: token, span } = match self.peek() {
-            Some(token) => token,
-            None => return Err(Spanned::new(Error::UnexpectedEof, self.last_token_span)),
+    fn consume(&mut self) -> Result<(), Spanned<Error>> {
+        match self.tokens.next() {
+            Some(token) => {
+                let (token, span) = token.into_parts();
+
+                if let Token::LeftPar = token {
+                    self.depth = self.depth.saturating_add(1);
+                    if self.depth > MAX_DEPTH {
+                        return Err(Spanned::new(Error::RecursionLimit, span));
+                    }
+                } else if let Token::RightPar = token {
+                    self.depth = self.depth.saturating_sub(1);
+                }
+
+                self.last_token_span = span;
+                Ok(())
+            }
+            None => panic!("no tokens to consume"),
+        }
+    }
+
+    fn require_sym(&mut self, symbol: &str) -> Result<Span, Spanned<Error>> {
+        let (token, span) = self.peek_token()?.into_parts();
+        self.consume()?;
+        match token {
+            Token::Symbol(s) if s == symbol => Ok(span),
+            _ => Err(Spanned::new(Error::UnexpectedToken, span)),
+        }
+    }
+
+    fn require_left_par(&mut self) -> Result<Span, Spanned<Error>> {
+        let (token, span) = self.peek_token()?.into_parts();
+        self.consume()?;
+        match token {
+            Token::LeftPar => Ok(span),
+            _ => Err(Spanned::new(Error::UnexpectedToken, span)),
+        }
+    }
+
+    fn require_right_par(&mut self) -> Result<Span, Spanned<Error>> {
+        let (token, span) = self.peek_token()?.into_parts();
+        self.consume()?;
+        match token {
+            Token::RightPar => Ok(span),
+            _ => Err(Spanned::new(Error::UnexpectedToken, span)),
+        }
+    }
+
+    fn parse_sym(&mut self) -> Result<Spanned<&'a str>, Spanned<Error>> {
+        let (token, span) = self.peek_token()?.into_parts();
+        self.consume()?;
+        match token {
+            Token::Symbol(symbol) => Ok(Spanned::new(symbol, span)),
+            _ => Err(Spanned::new(Error::UnexpectedToken, span)),
+        }
+    }
+
+    fn parse_args(&mut self, open_span: Span) -> Result<Vec<Spanned<Rc<str>>>, Spanned<Error>> {
+        let mut args = Vec::new();
+        while let Some(token) = self.peek() {
+            let (token, span) = token.into_parts();
+
+            self.consume()?;
+            match token {
+                Token::Symbol(symbol) => args.push(Spanned::new(symbol.into(), span)),
+                Token::RightPar => return Ok(args),
+                _ => return Err(Spanned::new(Error::UnexpectedToken, span)),
+            }
+        }
+
+        Err(Spanned::new(Error::UnclosedPar, open_span))
+    }
+
+    fn parse_body(
+        &mut self,
+        open_span: Span,
+        non_empty: bool,
+    ) -> Result<Vec<Spanned<Expr>>, Spanned<Error>> {
+        let mut body = Vec::new();
+        if non_empty {
+            body.push(self.parse_expr()?);
+        }
+        while let Some(token) = self.peek() {
+            match token.inner {
+                Token::RightPar => {
+                    self.consume()?;
+                    return Ok(body);
+                }
+                _ => body.push(self.parse_expr()?),
+            }
+        }
+
+        Err(Spanned::new(Error::UnclosedPar, open_span))
+    }
+
+    fn parse_var(&mut self) -> Result<Spanned<LetVar>, Spanned<Error>> {
+        let open_span = self.require_left_par()?;
+        let name = self.parse_sym()?.map(Into::into);
+        let expr = self.parse_expr()?;
+        let close_span = self.require_right_par()?;
+
+        let let_var = LetVar { name, expr };
+        let span = Span::new(open_span.start, close_span.end);
+        Ok(Spanned::new(let_var, span))
+    }
+
+    fn parse_vars(&mut self, open_span: Span) -> Result<Vec<Spanned<LetVar>>, Spanned<Error>> {
+        let mut vars = Vec::new();
+        vars.push(self.parse_var()?);
+
+        while let Some(token) = self.peek() {
+            let (token, span) = token.into_parts();
+            match token {
+                Token::LeftPar => vars.push(self.parse_var()?),
+                Token::RightPar => {
+                    self.consume()?;
+                    return Ok(vars);
+                }
+                _ => return Err(Spanned::new(Error::UnexpectedToken, span)),
+            }
+        }
+
+        Err(Spanned::new(Error::UnclosedPar, open_span))
+    }
+
+    fn parse_fn(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        self.consume()?;
+
+        let name = self.parse_sym()?.map(Into::into);
+        let args_open_span = self.require_left_par()?;
+        let args = self.parse_args(args_open_span)?;
+
+        let body = self.parse_body(open_span, true)?;
+        let function = Expr::Fn { name, args, body };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+
+        Ok(Spanned::new(function, span))
+    }
+
+    fn parse_const(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        self.consume()?;
+
+        let vars = self.parse_vars(open_span)?;
+        let constant = Expr::Const { vars };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+        Ok(Spanned::new(constant, span))
+    }
+
+    fn parse_let(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        self.consume()?;
+
+        let vars_span = self.require_left_par()?;
+        let vars = self.parse_vars(vars_span)?;
+        let body = self.parse_body(open_span, true)?;
+        let let_vars = Expr::Let { vars, body };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+        Ok(Spanned::new(let_vars, span))
+    }
+
+    fn parse_for(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        self.consume()?;
+
+        let loop_var = self.parse_sym()?.map(Into::into);
+        self.require_sym("from")?;
+        let from = self.parse_expr()?.map(Box::new);
+        self.require_sym("to")?;
+        let to = self.parse_expr()?.map(Box::new);
+        let body = self.parse_body(open_span, true)?;
+
+        let for_loop = Expr::For {
+            loop_var,
+            from,
+            to,
+            body,
         };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+        Ok(Spanned::new(for_loop, span))
+    }
+
+    fn parse_set(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        self.consume()?;
+
+        let target_var = self.parse_sym()?.map(Into::into);
+        let expr = self.parse_expr()?.map(Box::new);
+        self.require_right_par()?;
+
+        let set = Expr::Set { target_var, expr };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+        Ok(Spanned::new(set, span))
+    }
+
+    fn parse_do(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        self.consume()?;
+
+        let body = self.parse_body(open_span, true)?;
+
+        let do_body = Expr::Do { body };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+        Ok(Spanned::new(do_body, span))
+    }
+
+    fn parse_call(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        let fn_name = self.parse_sym()?.map(Into::into);
+        let args = self.parse_body(open_span, false)?;
+
+        let call = Expr::Call { fn_name, args };
+        let span = Span::new(open_span.start, self.last_token_span.end);
+        Ok(Spanned::new(call, span))
+    }
+
+    fn parse_special_form(&mut self, open_span: Span) -> Result<Spanned<Expr>, Spanned<Error>> {
+        let (token, span) = self.peek_token()?.into_parts();
+
+        let symbol = match token {
+            Token::Symbol(symbol) => symbol,
+            Token::RightPar => {
+                self.consume()?;
+                let span = Span::new(open_span.start, span.end);
+                return Ok(Spanned::new(Expr::Atom(Atom::Nil), span));
+            }
+            _ => return Err(Spanned::new(Error::UnexpectedToken, span)),
+        };
+
+        match symbol {
+            "fn" => self.parse_fn(open_span),
+            "const" => self.parse_const(open_span),
+            "let" => self.parse_let(open_span),
+            "for" => self.parse_for(open_span),
+            "set" => self.parse_set(open_span),
+            "do" => self.parse_do(open_span),
+            _ => self.parse_call(open_span),
+        }
+    }
+
+    fn parse_expr(&mut self) -> Result<Spanned<Expr>, Spanned<Error>> {
+        let (token, span) = self.peek_token()?.into_parts();
 
         let expr = match token {
             Token::LeftPar => {
-                self.consume();
-                let list = self.parse_list(span)?;
-                let expr = if !list.is_empty() {
-                    Expr::List(list)
-                } else {
-                    Expr::Atom(Atom::Nil)
-                };
-
-                Spanned::new(expr, Span::new(span.start, self.last_token_span.end))
+                self.consume()?;
+                self.parse_special_form(span)?
             }
             Token::RightPar => {
-                self.consume();
-                return Err(Spanned::new(Error::UnexpectedRightPar, span));
+                self.consume()?;
+                return Err(Spanned::new(Error::UnexpectedClosePar, span));
             }
             Token::Number(number) => {
-                self.consume();
+                self.consume()?;
                 let atom = parse_number(number).map_err(|e| Spanned::new(e, span))?;
                 Spanned::new(Expr::Atom(atom), span)
             }
             Token::String(string) => {
-                self.consume();
+                self.consume()?;
                 let atom = parse_string(string).map_err(|e| Spanned::new(e, span))?;
                 Spanned::new(Expr::Atom(atom), span)
             }
             Token::UnclosedString(string) => {
-                self.consume();
+                self.consume()?;
                 return Err(Spanned::new(Error::UnclosedString(string.into()), span));
             }
             Token::Symbol(symbol) => {
-                self.consume();
+                self.consume()?;
                 let atom = parse_symbol(symbol);
                 Spanned::new(Expr::Atom(atom), span)
             }
@@ -130,28 +355,6 @@ where
         Ok(expr)
     }
 
-    fn parse_list(&mut self, left_par_span: Span) -> Result<Vec<Spanned<Expr>>, Spanned<Error>> {
-        let mut list = Vec::new();
-
-        self.depth += 1;
-        if self.depth >= MAX_DEPTH {
-            return Err(Spanned::new(Error::RecursionLimit, self.last_token_span));
-        }
-
-        while let Some(Spanned { inner: token, .. }) = self.peek() {
-            match token {
-                Token::RightPar => {
-                    self.consume();
-                    return Ok(list);
-                }
-                _ => list.push(self.parse_expr()?),
-            }
-        }
-        self.depth -= 1;
-
-        Err(Spanned::new(Error::UnclosedLeftPar, left_par_span))
-    }
-
     pub fn parse(mut self) -> Result<Ast, Spanned<Error>> {
         let mut ast = Vec::new();
 
diff --git a/compiler/src/ast/tests.rs b/compiler/src/ast/tests.rs
index 44789cb..5b2399f 100644
--- a/compiler/src/ast/tests.rs
+++ b/compiler/src/ast/tests.rs
@@ -1,7 +1,7 @@
-use std::{fmt::Debug, iter::repeat_n};
+use std::fmt::Debug;
 
 use crate::{
-    ast::{Atom, Error, Expr, Parser, parser::MAX_DEPTH, tests::E::*},
+    ast::{Atom, Error, Expr, LetVar, Parser, parser::MAX_DEPTH, tests::E::*},
     lex::Token::{self, *},
     span::{Pos, Span, Spanned},
 };
@@ -13,20 +13,62 @@ enum E {
     Sym(&'static str),
     Bool(bool),
     Nil,
-    List(Vec<E>),
+    Fn(&'static str, Vec<&'static str>, Vec<E>),
+    Const(Vec<(&'static str, E)>),
+    Let(Vec<(&'static str, E)>, Vec<E>),
+    For(&'static str, Box<E>, Box<E>, Vec<E>),
+    Set(&'static str, Box<E>),
+    Do(Vec<E>),
+    Call(&'static str, Vec<E>),
+}
+
+fn leak(s: &str) -> &'static str {
+    Box::leak(s.to_string().into_boxed_str())
+}
+
+fn convert_var(var: LetVar) -> (&'static str, E) {
+    (leak(&var.name.inner), var.expr.inner.into())
 }
 
 impl From<Expr> for E {
     fn from(expr: Expr) -> Self {
         match expr {
             Expr::Atom(atom) => match atom {
-                Atom::Integer(i) => Int(i),
-                Atom::String(s) => Str(Box::leak(s.into())),
-                Atom::Symbol(s) => Sym(Box::leak(s.into())),
+                Atom::Int(i) => Int(i),
+                Atom::Str(s) => Str(leak(&s)),
+                Atom::Sym(s) => Sym(leak(&s)),
                 Atom::Bool(b) => Bool(b),
                 Atom::Nil => Nil,
             },
-            Expr::List(l) => List(l.into_iter().map(|e| e.inner.into()).collect()),
+            Expr::Fn { name, args, body } => Fn(
+                leak(&name.inner),
+                args.into_iter().map(|a| leak(&a.inner)).collect(),
+                body.into_iter().map(|e| e.inner.into()).collect(),
+            ),
+            Expr::Const { vars } => Const(vars.into_iter().map(|v| convert_var(v.inner)).collect()),
+            Expr::Let { vars, body } => Let(
+                vars.into_iter().map(|v| convert_var(v.inner)).collect(),
+                body.into_iter().map(|e| e.inner.into()).collect(),
+            ),
+            Expr::For {
+                loop_var,
+                from,
+                to,
+                body,
+            } => For(
+                leak(&loop_var.inner),
+                Box::new(E::from(*from.inner)),
+                Box::new(E::from(*to.inner)),
+                body.into_iter().map(|e| e.inner.into()).collect(),
+            ),
+            Expr::Set { target_var, expr } => {
+                Set(leak(&target_var.inner), Box::new(E::from(*expr.inner)))
+            }
+            Expr::Do { body } => Do(body.into_iter().map(|e| e.inner.into()).collect()),
+            Expr::Call { fn_name, args } => Call(
+                leak(&fn_name.inner),
+                args.into_iter().map(|e| e.inner.into()).collect(),
+            ),
         }
     }
 }
@@ -142,72 +184,311 @@ fn test_string_escapes() {
 }
 
 #[test]
-fn test_lists() {
+fn test_call() {
     let cases = vec![
-        // (1)
+        // (foo 1)
         (
-            vec![LeftPar, Number("1"), RightPar],
-            vec![List(vec![Int(1)])],
+            vec![LeftPar, Symbol("foo"), Number("1"), RightPar],
+            vec![Call("foo", vec![Int(1)])],
         ),
-        // (1 2 3)
+        // (+ 1 2 3)
         (
-            vec![LeftPar, Number("1"), Number("2"), Number("3"), RightPar],
-            vec![List(vec![Int(1), Int(2), Int(3)])],
+            vec![
+                LeftPar,
+                Symbol("+"),
+                Number("1"),
+                Number("2"),
+                Number("3"),
+                RightPar,
+            ],
+            vec![Call("+", vec![Int(1), Int(2), Int(3)])],
         ),
-        // (()) -> (nil)
+        // (foo (bar 1) baz)
         (
-            vec![LeftPar, LeftPar, RightPar, RightPar],
-            vec![List(vec![Nil])],
+            vec![
+                LeftPar,
+                Symbol("foo"),
+                LeftPar,
+                Symbol("bar"),
+                Number("1"),
+                RightPar,
+                Symbol("baz"),
+                RightPar,
+            ],
+            vec![Call("foo", vec![Call("bar", vec![Int(1)]), Sym("baz")])],
         ),
-        // (a (b c) d)
+        // (f "s" foo true nil)
         (
             vec![
                 LeftPar,
-                Symbol("a"),
+                Symbol("f"),
+                String("s"),
+                Symbol("foo"),
+                Symbol("true"),
+                Symbol("nil"),
+                RightPar,
+            ],
+            vec![Call("f", vec![Str("s"), Sym("foo"), Bool(true), Nil])],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_fn() {
+    let cases = vec![
+        // (fn foo () 1)
+        (
+            vec![
+                LeftPar,
+                Symbol("fn"),
+                Symbol("foo"),
                 LeftPar,
-                Symbol("b"),
-                Symbol("c"),
                 RightPar,
-                Symbol("d"),
+                Number("1"),
                 RightPar,
             ],
-            vec![List(vec![
-                Sym("a"),
-                List(vec![Sym("b"), Sym("c")]),
-                Sym("d"),
-            ])],
+            vec![Fn("foo", vec![], vec![Int(1)])],
         ),
-        // (define x 42)
+        // (fn add (x y) (+ x y))
         (
             vec![
                 LeftPar,
-                Symbol("define"),
+                Symbol("fn"),
+                Symbol("add"),
+                LeftPar,
+                Symbol("x"),
+                Symbol("y"),
+                RightPar,
+                LeftPar,
+                Symbol("+"),
                 Symbol("x"),
-                Number("42"),
+                Symbol("y"),
+                RightPar,
                 RightPar,
             ],
-            vec![List(vec![Sym("define"), Sym("x"), Int(42)])],
+            vec![Fn(
+                "add",
+                vec!["x", "y"],
+                vec![Call("+", vec![Sym("x"), Sym("y")])],
+            )],
         ),
-        // (1 2.5 "s" foo true nil)
+        // (fn id (x) x x)
         (
             vec![
                 LeftPar,
+                Symbol("fn"),
+                Symbol("id"),
+                LeftPar,
+                Symbol("x"),
+                RightPar,
+                Symbol("x"),
+                Symbol("x"),
+                RightPar,
+            ],
+            vec![Fn("id", vec!["x"], vec![Sym("x"), Sym("x")])],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_const() {
+    let cases = vec![
+        // (const (x 1))
+        (
+            vec![
+                LeftPar,
+                Symbol("const"),
+                LeftPar,
+                Symbol("x"),
                 Number("1"),
-                Number("-1"),
-                String("s"),
-                Symbol("foo"),
-                Symbol("true"),
-                Symbol("nil"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Const(vec![("x", Int(1))])],
+        ),
+        // (const (x 1) (y 2))
+        (
+            vec![
+                LeftPar,
+                Symbol("const"),
+                LeftPar,
+                Symbol("x"),
+                Number("1"),
+                RightPar,
+                LeftPar,
+                Symbol("y"),
+                Number("2"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Const(vec![("x", Int(1)), ("y", Int(2))])],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_let() {
+    let cases = vec![
+        // (let ((x 1)) x)
+        (
+            vec![
+                LeftPar,
+                Symbol("let"),
+                LeftPar,
+                LeftPar,
+                Symbol("x"),
+                Number("1"),
+                RightPar,
+                RightPar,
+                Symbol("x"),
+                RightPar,
+            ],
+            vec![Let(vec![("x", Int(1))], vec![Sym("x")])],
+        ),
+        // (let ((x 1) (y 2)) (+ x y))
+        (
+            vec![
+                LeftPar,
+                Symbol("let"),
+                LeftPar,
+                LeftPar,
+                Symbol("x"),
+                Number("1"),
+                RightPar,
+                LeftPar,
+                Symbol("y"),
+                Number("2"),
+                RightPar,
+                RightPar,
+                LeftPar,
+                Symbol("+"),
+                Symbol("x"),
+                Symbol("y"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Let(
+                vec![("x", Int(1)), ("y", Int(2))],
+                vec![Call("+", vec![Sym("x"), Sym("y")])],
+            )],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_for() {
+    let cases = vec![
+        // (for i from 0 to 10 i)
+        (
+            vec![
+                LeftPar,
+                Symbol("for"),
+                Symbol("i"),
+                Symbol("from"),
+                Number("0"),
+                Symbol("to"),
+                Number("10"),
+                Symbol("i"),
+                RightPar,
+            ],
+            vec![For(
+                "i",
+                Box::new(Int(0)),
+                Box::new(Int(10)),
+                vec![Sym("i")],
+            )],
+        ),
+        // (for i from 0 to 10 i (+ i 1))
+        (
+            vec![
+                LeftPar,
+                Symbol("for"),
+                Symbol("i"),
+                Symbol("from"),
+                Number("0"),
+                Symbol("to"),
+                Number("10"),
+                Symbol("i"),
+                LeftPar,
+                Symbol("+"),
+                Symbol("i"),
+                Number("1"),
+                RightPar,
+                RightPar,
+            ],
+            vec![For(
+                "i",
+                Box::new(Int(0)),
+                Box::new(Int(10)),
+                vec![Sym("i"), Call("+", vec![Sym("i"), Int(1)])],
+            )],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_set() {
+    let cases = vec![
+        // (set x 5)
+        (
+            vec![LeftPar, Symbol("set"), Symbol("x"), Number("5"), RightPar],
+            vec![Set("x", Box::new(Int(5)))],
+        ),
+        // (set x (+ x 1))
+        (
+            vec![
+                LeftPar,
+                Symbol("set"),
+                Symbol("x"),
+                LeftPar,
+                Symbol("+"),
+                Symbol("x"),
+                Number("1"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Set("x", Box::new(Call("+", vec![Sym("x"), Int(1)])))],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_do() {
+    let cases = vec![
+        // (do 1)
+        (
+            vec![LeftPar, Symbol("do"), Number("1"), RightPar],
+            vec![Do(vec![Int(1)])],
+        ),
+        // (do 1 2 3)
+        (
+            vec![
+                LeftPar,
+                Symbol("do"),
+                Number("1"),
+                Number("2"),
+                Number("3"),
                 RightPar,
             ],
-            vec![List(vec![
-                Int(1),
-                Int(-1),
-                Str("s"),
-                Sym("foo"),
-                Bool(true),
-                Nil,
-            ])],
+            vec![Do(vec![Int(1), Int(2), Int(3)])],
         ),
     ];
     for (tokens, ast) in cases {
@@ -226,12 +507,14 @@ fn test_top_level() {
             vec![
                 LeftPar,
                 Symbol("a"),
+                Number("1"),
                 RightPar,
                 LeftPar,
                 Symbol("b"),
+                Number("2"),
                 RightPar,
             ],
-            vec![List(vec![Sym("a")]), List(vec![Sym("b")])],
+            vec![Call("a", vec![Int(1)]), Call("b", vec![Int(2)])],
         ),
     ];
     for (tokens, expected) in cases {
@@ -244,32 +527,103 @@ fn parse_err(tokens: Vec<Token<'static>>) -> Error {
 }
 
 #[test]
-fn test_unexpected_right_par() {
+fn test_unexpected_close_par() {
     let cases = vec![
+        // )
         vec![RightPar],
+        // 1 )
         vec![Number("1"), RightPar],
+        // (a) )
         vec![LeftPar, Symbol("a"), RightPar, RightPar],
+        // (do)
+        vec![LeftPar, Symbol("do"), RightPar],
+        // (set x)
+        vec![LeftPar, Symbol("set"), Symbol("x"), RightPar],
+        // (let ((x 1)))
+        vec![
+            LeftPar,
+            Symbol("let"),
+            LeftPar,
+            LeftPar,
+            Symbol("x"),
+            Number("1"),
+            RightPar,
+            RightPar,
+            RightPar,
+        ],
     ];
     for tokens in cases {
         assert_eq!(
             parse_err(tokens.clone()),
-            Error::UnexpectedRightPar,
+            Error::UnexpectedClosePar,
             "input: {tokens:?}"
         );
     }
 }
 
 #[test]
-fn test_unclosed_left_par() {
+fn test_unclosed_par() {
     let cases = vec![
+        // (foo
+        vec![LeftPar, Symbol("foo")],
+        // (foo 1
+        vec![LeftPar, Symbol("foo"), Number("1")],
+        // (foo 1 2
+        vec![LeftPar, Symbol("foo"), Number("1"), Number("2")],
+        // (foo (bar 1)
+        vec![
+            LeftPar,
+            Symbol("foo"),
+            LeftPar,
+            Symbol("bar"),
+            Number("1"),
+            RightPar,
+        ],
+    ];
+    for tokens in cases {
+        assert_eq!(
+            parse_err(tokens.clone()),
+            Error::UnclosedPar,
+            "input: {tokens:?}"
+        );
+    }
+}
+
+#[test]
+fn test_unexpected_eof() {
+    let cases = vec![
+        // (
         vec![LeftPar],
-        vec![LeftPar, Number("1")],
-        vec![LeftPar, LeftPar, Symbol("a"), RightPar],
+        // (fn foo ()
+        vec![LeftPar, Symbol("fn"), Symbol("foo"), LeftPar, RightPar],
     ];
     for tokens in cases {
         assert_eq!(
             parse_err(tokens.clone()),
-            Error::UnclosedLeftPar,
+            Error::UnexpectedEof,
+            "input: {tokens:?}"
+        );
+    }
+}
+
+#[test]
+fn test_unexpected_token() {
+    let cases = vec![
+        // (1 2 3)
+        vec![LeftPar, Number("1"), Number("2"), Number("3"), RightPar],
+        // (())
+        vec![LeftPar, LeftPar, RightPar, RightPar],
+        // ("hello")
+        vec![LeftPar, String("hello"), RightPar],
+        // (for)
+        vec![LeftPar, Symbol("for"), RightPar],
+        // (fn)
+        vec![LeftPar, Symbol("fn"), RightPar],
+    ];
+    for tokens in cases {
+        assert_eq!(
+            parse_err(tokens.clone()),
+            Error::UnexpectedToken,
             "input: {tokens:?}"
         );
     }
@@ -329,18 +683,34 @@ fn test_unexpected_escape_char_propagates() {
     );
 }
 
+fn run_with_large_stack(f: impl FnOnce() + Send + 'static) {
+    std::thread::Builder::new()
+        .stack_size(8 * 1024 * 1024)
+        .spawn(f)
+        .unwrap()
+        .join()
+        .unwrap();
+}
+
 #[test]
 fn test_recursion_limit() {
-    let mut tokens = Vec::with_capacity(MAX_DEPTH * 2);
-    tokens.extend(repeat_n(LeftPar, MAX_DEPTH));
-    tokens.extend(repeat_n(RightPar, MAX_DEPTH));
-    assert_eq!(
-        parse_err(tokens),
-        Error::RecursionLimit,
-        "input: {} LeftPar then {} RightPar",
-        MAX_DEPTH,
-        MAX_DEPTH,
-    );
+    run_with_large_stack(|| {
+        let n = MAX_DEPTH + 1;
+        let mut tokens = Vec::with_capacity(n * 2 + 1 + n);
+        for _ in 0..n {
+            tokens.push(LeftPar);
+            tokens.push(Symbol("foo"));
+        }
+        tokens.push(Number("1"));
+        for _ in 0..n {
+            tokens.push(RightPar);
+        }
+        assert_eq!(
+            parse_err(tokens),
+            Error::RecursionLimit,
+            "input: {n} nested calls",
+        );
+    });
 }
 
 fn p(line: usize, column: usize, offset: usize) -> Pos {
@@ -360,8 +730,6 @@ fn parse_sp(tokens: Vec<Spanned<Token<'static>>>) -> Vec<Spanned<Expr>> {
         .parse()
         .unwrap()
         .into_inner()
-        .into_iter()
-        .collect()
 }
 
 fn parse_sp_err(tokens: Vec<Spanned<Token<'static>>>) -> Spanned<Error> {
@@ -378,26 +746,33 @@ fn test_span_atom() {
 }
 
 #[test]
-fn test_span_list_covers_parens() {
-    // (foo)
+fn test_span_call_covers_parens() {
+    // (foo 1)
     let lp = sp((1, 0, 0), (1, 1, 1));
     let foo = sp((1, 1, 1), (1, 4, 4));
-    let rp = sp((1, 4, 4), (1, 5, 5));
-    let tokens = vec![tsp(LeftPar, lp), tsp(Symbol("foo"), foo), tsp(RightPar, rp)];
+    let one = sp((1, 5, 5), (1, 6, 6));
+    let rp = sp((1, 6, 6), (1, 7, 7));
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("foo"), foo),
+        tsp(Number("1"), one),
+        tsp(RightPar, rp),
+    ];
     let prog = parse_sp(tokens.clone());
 
-    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 5, 5)), "input: {tokens:?}");
+    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 7, 7)), "input: {tokens:?}");
 
-    if let Expr::List(items) = &prog[0].inner {
-        assert_eq!(items[0].span, foo, "input: {tokens:?}");
+    if let Expr::Call { fn_name, args } = &prog[0].inner {
+        assert_eq!(fn_name.span, foo, "input: {tokens:?}");
+        assert_eq!(args[0].span, one, "input: {tokens:?}");
     } else {
-        panic!("expected list, input: {tokens:?}");
+        panic!("expected call, input: {tokens:?}");
     }
 }
 
 #[test]
 fn test_span_empty_list_covers_parens() {
-    // () -> Atom::Nil, span [0..2]
+    // ()
     let lp = sp((1, 0, 0), (1, 1, 1));
     let rp = sp((1, 1, 1), (1, 2, 2));
     let tokens = vec![tsp(LeftPar, lp), tsp(RightPar, rp)];
@@ -408,12 +783,13 @@ fn test_span_empty_list_covers_parens() {
 }
 
 #[test]
-fn test_error_span_unexpected_right_par() {
+fn test_error_span_unexpected_close_par() {
+    // )
     let s = sp((1, 5, 5), (1, 6, 6));
     let tokens = vec![tsp(RightPar, s)];
     let err = parse_sp_err(tokens.clone());
 
-    assert_eq!(err.inner, Error::UnexpectedRightPar, "input: {tokens:?}");
+    assert_eq!(err.inner, Error::UnexpectedClosePar, "input: {tokens:?}");
     assert_eq!(err.span, s, "input: {tokens:?}");
 }
 
@@ -427,27 +803,68 @@ fn test_error_span_invalid_integer() {
 }
 
 #[test]
-fn test_error_span_unclosed_left_par() {
+fn test_error_span_unclosed_par() {
+    // (foo 1
     let lp = sp((1, 0, 0), (1, 1, 1));
-    let tokens = vec![tsp(LeftPar, lp)];
+    let foo = sp((1, 1, 1), (1, 4, 4));
+    let one = sp((1, 5, 5), (1, 6, 6));
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("foo"), foo),
+        tsp(Number("1"), one),
+    ];
     let err = parse_sp_err(tokens.clone());
 
-    assert_eq!(err.inner, Error::UnclosedLeftPar, "input: {tokens:?}");
+    assert_eq!(err.inner, Error::UnclosedPar, "input: {tokens:?}");
     assert_eq!(err.span, lp, "input: {tokens:?}");
 }
 
 #[test]
-fn test_error_span_unclosed_left_par_nested() {
+fn test_error_span_unclosed_par_nested() {
+    // (foo (bar 1
     let outer = sp((1, 0, 0), (1, 1, 1));
-    let inner = sp((1, 2, 2), (1, 3, 3));
-    let tokens = vec![tsp(LeftPar, outer), tsp(LeftPar, inner)];
+    let foo = sp((1, 1, 1), (1, 4, 4));
+    let inner = sp((1, 5, 5), (1, 6, 6));
+    let bar = sp((1, 6, 6), (1, 9, 9));
+    let one = sp((1, 10, 10), (1, 11, 11));
+    let tokens = vec![
+        tsp(LeftPar, outer),
+        tsp(Symbol("foo"), foo),
+        tsp(LeftPar, inner),
+        tsp(Symbol("bar"), bar),
+        tsp(Number("1"), one),
+    ];
     let err = parse_sp_err(tokens.clone());
 
-    assert_eq!(err.inner, Error::UnclosedLeftPar, "input: {tokens:?}");
+    assert_eq!(err.inner, Error::UnclosedPar, "input: {tokens:?}");
     assert_eq!(err.span, inner, "input: {tokens:?}");
 }
 
 #[test]
+fn test_error_span_unexpected_eof() {
+    // (
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let tokens = vec![tsp(LeftPar, lp)];
+    let err = parse_sp_err(tokens.clone());
+
+    assert_eq!(err.inner, Error::UnexpectedEof, "input: {tokens:?}");
+    assert_eq!(err.span, lp, "input: {tokens:?}");
+}
+
+#[test]
+fn test_error_span_unexpected_token() {
+    // (1)
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let one = sp((1, 1, 1), (1, 2, 2));
+    let rp = sp((1, 2, 2), (1, 3, 3));
+    let tokens = vec![tsp(LeftPar, lp), tsp(Number("1"), one), tsp(RightPar, rp)];
+    let err = parse_sp_err(tokens.clone());
+
+    assert_eq!(err.inner, Error::UnexpectedToken, "input: {tokens:?}");
+    assert_eq!(err.span, one, "input: {tokens:?}");
+}
+
+#[test]
 fn test_error_span_unclosed_string() {
     let s = sp((1, 0, 0), (1, 7, 7));
     let tokens = vec![tsp(UnclosedString("oops"), s)];
@@ -477,16 +894,16 @@ fn test_error_span_unexpected_escape_char() {
 
 #[test]
 fn test_error_span_deep_nested() {
-    // (a (b (c BAD)))
+    // (foo (bar (baz 99999999999999999999)))
     let bad_span = sp((1, 9, 9), (1, 29, 29));
     let any = sp((1, 0, 0), (1, 1, 1));
     let tokens = vec![
         tsp(LeftPar, any),
-        tsp(Symbol("a"), any),
+        tsp(Symbol("foo"), any),
         tsp(LeftPar, any),
-        tsp(Symbol("b"), any),
+        tsp(Symbol("bar"), any),
         tsp(LeftPar, any),
-        tsp(Symbol("c"), any),
+        tsp(Symbol("baz"), any),
         tsp(Number("99999999999999999999"), bad_span),
         tsp(RightPar, any),
         tsp(RightPar, any),
@@ -504,14 +921,707 @@ fn test_error_span_deep_nested() {
 
 #[test]
 fn test_error_span_recursion_limit() {
-    let mut tokens = Vec::with_capacity(MAX_DEPTH);
-    for i in 0..MAX_DEPTH {
-        let s = sp((1, i, i), (1, i + 1, i + 1));
-        tokens.push(tsp(LeftPar, s));
+    run_with_large_stack(|| {
+        let any = sp((0, 0, 0), (0, 0, 0));
+        let mut tokens = Vec::with_capacity((MAX_DEPTH + 1) * 2);
+        for i in 0..=MAX_DEPTH {
+            let s = sp((1, i, i), (1, i + 1, i + 1));
+            tokens.push(tsp(LeftPar, s));
+            tokens.push(tsp(Symbol("foo"), any));
+        }
+        let trigger = sp((1, MAX_DEPTH, MAX_DEPTH), (1, MAX_DEPTH + 1, MAX_DEPTH + 1));
+        let err = parse_sp_err(tokens);
+
+        assert_eq!(err.inner, Error::RecursionLimit, "MAX_DEPTH={MAX_DEPTH}");
+        assert_eq!(err.span, trigger, "MAX_DEPTH={MAX_DEPTH}");
+    });
+}
+
+#[test]
+fn test_keyword_prefixed_symbols() {
+    let cases = vec![
+        (vec![Symbol("fn-foo")], vec![Sym("fn-foo")]),
+        (vec![Symbol("let1")], vec![Sym("let1")]),
+        (vec![Symbol("from-here")], vec![Sym("from-here")]),
+        (vec![Symbol("do!")], vec![Sym("do!")]),
+        (vec![Symbol("set?")], vec![Sym("set?")]),
+        (vec![Symbol("for-each")], vec![Sym("for-each")]),
+        (vec![Symbol("const-x")], vec![Sym("const-x")]),
+        // (fn-foo 1)
+        (
+            vec![LeftPar, Symbol("fn-foo"), Number("1"), RightPar],
+            vec![Call("fn-foo", vec![Int(1)])],
+        ),
+        // (set! x 1)
+        (
+            vec![LeftPar, Symbol("set!"), Symbol("x"), Number("1"), RightPar],
+            vec![Call("set!", vec![Sym("x"), Int(1)])],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_long_symbol() {
+    let long: &'static str = leak(&"a".repeat(10_000));
+    let tokens = vec![Symbol(long)];
+    assert_eq!(parse(tokens), vec![Sym(long)]);
+}
+
+#[test]
+fn test_signed_zero() {
+    let cases = vec![
+        (vec![Number("+0")], vec![Int(0)]),
+        (vec![Number("-0")], vec![Int(0)]),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_double_backslash_in_string() {
+    let cases = vec![
+        (vec![String(r"\\")], vec![Str("\\")]),
+        (vec![String(r"a\\b")], vec![Str("a\\b")]),
+        (vec![String(r"\\\\")], vec![Str("\\\\")]),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_nil_as_value() {
+    let cases = vec![
+        // (foo () bar)
+        (
+            vec![
+                LeftPar,
+                Symbol("foo"),
+                LeftPar,
+                RightPar,
+                Symbol("bar"),
+                RightPar,
+            ],
+            vec![Call("foo", vec![Nil, Sym("bar")])],
+        ),
+        // (do () nil ())
+        (
+            vec![
+                LeftPar,
+                Symbol("do"),
+                LeftPar,
+                RightPar,
+                Symbol("nil"),
+                LeftPar,
+                RightPar,
+                RightPar,
+            ],
+            vec![Do(vec![Nil, Nil, Nil])],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_special_form_errors() {
+    let cases = vec![
+        // (fn foo)
+        (
+            vec![LeftPar, Symbol("fn"), Symbol("foo"), RightPar],
+            Error::UnexpectedToken,
+        ),
+        // (fn foo bar)
+        (
+            vec![
+                LeftPar,
+                Symbol("fn"),
+                Symbol("foo"),
+                Symbol("bar"),
+                RightPar,
+            ],
+            Error::UnexpectedToken,
+        ),
+        // (fn 1 2)
+        (
+            vec![LeftPar, Symbol("fn"), Number("1"), Number("2"), RightPar],
+            Error::UnexpectedToken,
+        ),
+        // (fn foo (1) body)
+        (
+            vec![
+                LeftPar,
+                Symbol("fn"),
+                Symbol("foo"),
+                LeftPar,
+                Number("1"),
+                RightPar,
+                Symbol("body"),
+                RightPar,
+            ],
+            Error::UnexpectedToken,
+        ),
+        // (let)
+        (
+            vec![LeftPar, Symbol("let"), RightPar],
+            Error::UnexpectedToken,
+        ),
+        // (let () body)
+        (
+            vec![
+                LeftPar,
+                Symbol("let"),
+                LeftPar,
+                RightPar,
+                Symbol("body"),
+                RightPar,
+            ],
+            Error::UnexpectedToken,
+        ),
+        // (for i)
+        (
+            vec![LeftPar, Symbol("for"), Symbol("i"), RightPar],
+            Error::UnexpectedToken,
+        ),
+        // (for i from 0)
+        (
+            vec![
+                LeftPar,
+                Symbol("for"),
+                Symbol("i"),
+                Symbol("from"),
+                Number("0"),
+                RightPar,
+            ],
+            Error::UnexpectedToken,
+        ),
+        // (for i from 0 to)
+        (
+            vec![
+                LeftPar,
+                Symbol("for"),
+                Symbol("i"),
+                Symbol("from"),
+                Number("0"),
+                Symbol("to"),
+                RightPar,
+            ],
+            Error::UnexpectedClosePar,
+        ),
+        // (for i wrong 0 to 10 body)
+        (
+            vec![
+                LeftPar,
+                Symbol("for"),
+                Symbol("i"),
+                Symbol("wrong"),
+                Number("0"),
+                Symbol("to"),
+                Number("10"),
+                Symbol("body"),
+                RightPar,
+            ],
+            Error::UnexpectedToken,
+        ),
+        // (set x y z)
+        (
+            vec![
+                LeftPar,
+                Symbol("set"),
+                Symbol("x"),
+                Symbol("y"),
+                Symbol("z"),
+                RightPar,
+            ],
+            Error::UnexpectedToken,
+        ),
+        // (const)
+        (
+            vec![LeftPar, Symbol("const"), RightPar],
+            Error::UnexpectedToken,
+        ),
+        // (const ())
+        (
+            vec![LeftPar, Symbol("const"), LeftPar, RightPar, RightPar],
+            Error::UnexpectedToken,
+        ),
+    ];
+    for (tokens, expected) in cases {
+        assert_eq!(parse_err(tokens.clone()), expected, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_stops_at_first_error() {
+    let cases = vec![
+        // ) ) )
+        (
+            vec![RightPar, RightPar, RightPar],
+            Error::UnexpectedClosePar,
+        ),
+        // 1 ) 2
+        (
+            vec![Number("1"), RightPar, Number("2")],
+            Error::UnexpectedClosePar,
+        ),
+    ];
+    for (tokens, expected) in cases {
+        assert_eq!(parse_err(tokens.clone()), expected, "input: {tokens:?}");
+    }
+    // 99999999999999999999 )
+    let tokens = vec![Number("99999999999999999999"), RightPar];
+    let err = parse_err(tokens.clone());
+    assert!(
+        matches!(err, Error::InvalidIntegerLiteral(..)),
+        "input: {tokens:?}, got: {err:?}",
+    );
+}
+
+#[test]
+fn test_nested_special_forms() {
+    let cases = vec![
+        // (do (do 1))
+        (
+            vec![
+                LeftPar,
+                Symbol("do"),
+                LeftPar,
+                Symbol("do"),
+                Number("1"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Do(vec![Do(vec![Int(1)])])],
+        ),
+        // (fn outer () (fn inner () 1))
+        (
+            vec![
+                LeftPar,
+                Symbol("fn"),
+                Symbol("outer"),
+                LeftPar,
+                RightPar,
+                LeftPar,
+                Symbol("fn"),
+                Symbol("inner"),
+                LeftPar,
+                RightPar,
+                Number("1"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Fn("outer", vec![], vec![Fn("inner", vec![], vec![Int(1)])])],
+        ),
+        // (let ((x (let ((y 1)) y))) x)
+        (
+            vec![
+                LeftPar,
+                Symbol("let"),
+                LeftPar,
+                LeftPar,
+                Symbol("x"),
+                LeftPar,
+                Symbol("let"),
+                LeftPar,
+                LeftPar,
+                Symbol("y"),
+                Number("1"),
+                RightPar,
+                RightPar,
+                Symbol("y"),
+                RightPar,
+                RightPar,
+                RightPar,
+                Symbol("x"),
+                RightPar,
+            ],
+            vec![Let(
+                vec![("x", Let(vec![("y", Int(1))], vec![Sym("y")]))],
+                vec![Sym("x")],
+            )],
+        ),
+        // (for i from 0 to (+ 1 2) (set sum (+ sum i)))
+        (
+            vec![
+                LeftPar,
+                Symbol("for"),
+                Symbol("i"),
+                Symbol("from"),
+                Number("0"),
+                Symbol("to"),
+                LeftPar,
+                Symbol("+"),
+                Number("1"),
+                Number("2"),
+                RightPar,
+                LeftPar,
+                Symbol("set"),
+                Symbol("sum"),
+                LeftPar,
+                Symbol("+"),
+                Symbol("sum"),
+                Symbol("i"),
+                RightPar,
+                RightPar,
+                RightPar,
+            ],
+            vec![For(
+                "i",
+                Box::new(Int(0)),
+                Box::new(Call("+", vec![Int(1), Int(2)])),
+                vec![Set("sum", Box::new(Call("+", vec![Sym("sum"), Sym("i")])))],
+            )],
+        ),
+        // (let ((x 1)) x (+ x 1))
+        (
+            vec![
+                LeftPar,
+                Symbol("let"),
+                LeftPar,
+                LeftPar,
+                Symbol("x"),
+                Number("1"),
+                RightPar,
+                RightPar,
+                Symbol("x"),
+                LeftPar,
+                Symbol("+"),
+                Symbol("x"),
+                Number("1"),
+                RightPar,
+                RightPar,
+            ],
+            vec![Let(
+                vec![("x", Int(1))],
+                vec![Sym("x"), Call("+", vec![Sym("x"), Int(1)])],
+            )],
+        ),
+    ];
+    for (tokens, ast) in cases {
+        assert_eq!(parse(tokens.clone()), ast, "input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_smoke_program() {
+    // (const (x 1))
+    // (fn add (a b) (+ a b))
+    // (let ((y 2)) (add x y))
+    let tokens = vec![
+        LeftPar,
+        Symbol("const"),
+        LeftPar,
+        Symbol("x"),
+        Number("1"),
+        RightPar,
+        RightPar,
+        LeftPar,
+        Symbol("fn"),
+        Symbol("add"),
+        LeftPar,
+        Symbol("a"),
+        Symbol("b"),
+        RightPar,
+        LeftPar,
+        Symbol("+"),
+        Symbol("a"),
+        Symbol("b"),
+        RightPar,
+        RightPar,
+        LeftPar,
+        Symbol("let"),
+        LeftPar,
+        LeftPar,
+        Symbol("y"),
+        Number("2"),
+        RightPar,
+        RightPar,
+        LeftPar,
+        Symbol("add"),
+        Symbol("x"),
+        Symbol("y"),
+        RightPar,
+        RightPar,
+    ];
+    let expected = vec![
+        Const(vec![("x", Int(1))]),
+        Fn(
+            "add",
+            vec!["a", "b"],
+            vec![Call("+", vec![Sym("a"), Sym("b")])],
+        ),
+        Let(
+            vec![("y", Int(2))],
+            vec![Call("add", vec![Sym("x"), Sym("y")])],
+        ),
+    ];
+    assert_eq!(parse(tokens), expected);
+}
+
+#[test]
+fn test_recursion_limit_via_do() {
+    run_with_large_stack(|| {
+        let n = MAX_DEPTH + 1;
+        let mut tokens = Vec::with_capacity(n * 2 + 1 + n);
+        for _ in 0..n {
+            tokens.push(LeftPar);
+            tokens.push(Symbol("do"));
+        }
+        tokens.push(Number("1"));
+        for _ in 0..n {
+            tokens.push(RightPar);
+        }
+        assert_eq!(parse_err(tokens), Error::RecursionLimit);
+    });
+}
+
+#[test]
+fn test_span_fn() {
+    // (fn id (x) x)
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let kw = sp((1, 1, 1), (1, 3, 3));
+    let name = sp((1, 4, 4), (1, 6, 6));
+    let lp_args = sp((1, 7, 7), (1, 8, 8));
+    let arg = sp((1, 8, 8), (1, 9, 9));
+    let rp_args = sp((1, 9, 9), (1, 10, 10));
+    let body_x = sp((1, 11, 11), (1, 12, 12));
+    let rp = sp((1, 12, 12), (1, 13, 13));
+
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("fn"), kw),
+        tsp(Symbol("id"), name),
+        tsp(LeftPar, lp_args),
+        tsp(Symbol("x"), arg),
+        tsp(RightPar, rp_args),
+        tsp(Symbol("x"), body_x),
+        tsp(RightPar, rp),
+    ];
+    let prog = parse_sp(tokens.clone());
+
+    assert_eq!(
+        prog[0].span,
+        sp((1, 0, 0), (1, 13, 13)),
+        "input: {tokens:?}"
+    );
+    if let Expr::Fn {
+        name: n,
+        args,
+        body,
+    } = &prog[0].inner
+    {
+        assert_eq!(n.span, name, "input: {tokens:?}");
+        assert_eq!(args[0].span, arg, "input: {tokens:?}");
+        assert_eq!(body[0].span, body_x, "input: {tokens:?}");
+    } else {
+        panic!("expected Fn, input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_span_let() {
+    // (let ((x 1)) x)
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let kw = sp((1, 1, 1), (1, 4, 4));
+    let lp_vars = sp((1, 5, 5), (1, 6, 6));
+    let lp_var = sp((1, 6, 6), (1, 7, 7));
+    let x_name = sp((1, 7, 7), (1, 8, 8));
+    let one = sp((1, 9, 9), (1, 10, 10));
+    let rp_var = sp((1, 10, 10), (1, 11, 11));
+    let rp_vars = sp((1, 11, 11), (1, 12, 12));
+    let body_x = sp((1, 13, 13), (1, 14, 14));
+    let rp = sp((1, 14, 14), (1, 15, 15));
+
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("let"), kw),
+        tsp(LeftPar, lp_vars),
+        tsp(LeftPar, lp_var),
+        tsp(Symbol("x"), x_name),
+        tsp(Number("1"), one),
+        tsp(RightPar, rp_var),
+        tsp(RightPar, rp_vars),
+        tsp(Symbol("x"), body_x),
+        tsp(RightPar, rp),
+    ];
+    let prog = parse_sp(tokens.clone());
+
+    assert_eq!(
+        prog[0].span,
+        sp((1, 0, 0), (1, 15, 15)),
+        "input: {tokens:?}"
+    );
+    if let Expr::Let { vars, body } = &prog[0].inner {
+        assert_eq!(
+            vars[0].span,
+            sp((1, 6, 6), (1, 11, 11)),
+            "input: {tokens:?}"
+        );
+        assert_eq!(vars[0].inner.name.span, x_name, "input: {tokens:?}");
+        assert_eq!(vars[0].inner.expr.span, one, "input: {tokens:?}");
+        assert_eq!(body[0].span, body_x, "input: {tokens:?}");
+    } else {
+        panic!("expected Let, input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_span_for() {
+    // (for i from 0 to 10 i)
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let kw = sp((1, 1, 1), (1, 4, 4));
+    let i = sp((1, 5, 5), (1, 6, 6));
+    let from = sp((1, 7, 7), (1, 11, 11));
+    let zero = sp((1, 12, 12), (1, 13, 13));
+    let to = sp((1, 14, 14), (1, 16, 16));
+    let ten = sp((1, 17, 17), (1, 19, 19));
+    let body_i = sp((1, 20, 20), (1, 21, 21));
+    let rp = sp((1, 21, 21), (1, 22, 22));
+
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("for"), kw),
+        tsp(Symbol("i"), i),
+        tsp(Symbol("from"), from),
+        tsp(Number("0"), zero),
+        tsp(Symbol("to"), to),
+        tsp(Number("10"), ten),
+        tsp(Symbol("i"), body_i),
+        tsp(RightPar, rp),
+    ];
+    let prog = parse_sp(tokens.clone());
+
+    assert_eq!(
+        prog[0].span,
+        sp((1, 0, 0), (1, 22, 22)),
+        "input: {tokens:?}"
+    );
+    if let Expr::For {
+        loop_var,
+        from: f,
+        to: t,
+        body,
+    } = &prog[0].inner
+    {
+        assert_eq!(loop_var.span, i, "input: {tokens:?}");
+        assert_eq!(f.span, zero, "input: {tokens:?}");
+        assert_eq!(t.span, ten, "input: {tokens:?}");
+        assert_eq!(body[0].span, body_i, "input: {tokens:?}");
+    } else {
+        panic!("expected For, input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_span_set() {
+    // (set x 5)
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let kw = sp((1, 1, 1), (1, 4, 4));
+    let x = sp((1, 5, 5), (1, 6, 6));
+    let five = sp((1, 7, 7), (1, 8, 8));
+    let rp = sp((1, 8, 8), (1, 9, 9));
+
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("set"), kw),
+        tsp(Symbol("x"), x),
+        tsp(Number("5"), five),
+        tsp(RightPar, rp),
+    ];
+    let prog = parse_sp(tokens.clone());
+
+    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 9, 9)), "input: {tokens:?}");
+    if let Expr::Set { target_var, expr } = &prog[0].inner {
+        assert_eq!(target_var.span, x, "input: {tokens:?}");
+        assert_eq!(expr.span, five, "input: {tokens:?}");
+    } else {
+        panic!("expected Set, input: {tokens:?}");
+    }
+}
+
+#[test]
+fn test_span_do() {
+    // (do 1 2)
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let kw = sp((1, 1, 1), (1, 3, 3));
+    let one = sp((1, 4, 4), (1, 5, 5));
+    let two = sp((1, 6, 6), (1, 7, 7));
+    let rp = sp((1, 7, 7), (1, 8, 8));
+
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("do"), kw),
+        tsp(Number("1"), one),
+        tsp(Number("2"), two),
+        tsp(RightPar, rp),
+    ];
+    let prog = parse_sp(tokens.clone());
+
+    assert_eq!(prog[0].span, sp((1, 0, 0), (1, 8, 8)), "input: {tokens:?}");
+    if let Expr::Do { body } = &prog[0].inner {
+        assert_eq!(body[0].span, one, "input: {tokens:?}");
+        assert_eq!(body[1].span, two, "input: {tokens:?}");
+    } else {
+        panic!("expected Do, input: {tokens:?}");
     }
-    let trigger = sp((1, MAX_DEPTH - 1, MAX_DEPTH - 1), (1, MAX_DEPTH, MAX_DEPTH));
-    let err = parse_sp_err(tokens);
+}
 
-    assert_eq!(err.inner, Error::RecursionLimit, "MAX_DEPTH={MAX_DEPTH}");
-    assert_eq!(err.span, trigger, "MAX_DEPTH={MAX_DEPTH}");
+#[test]
+fn test_span_const() {
+    // (const (x 1) (y 2))
+    let lp = sp((1, 0, 0), (1, 1, 1));
+    let kw = sp((1, 1, 1), (1, 6, 6));
+    let lp_x = sp((1, 7, 7), (1, 8, 8));
+    let x_name = sp((1, 8, 8), (1, 9, 9));
+    let one = sp((1, 10, 10), (1, 11, 11));
+    let rp_x = sp((1, 11, 11), (1, 12, 12));
+    let lp_y = sp((1, 13, 13), (1, 14, 14));
+    let y_name = sp((1, 14, 14), (1, 15, 15));
+    let two = sp((1, 16, 16), (1, 17, 17));
+    let rp_y = sp((1, 17, 17), (1, 18, 18));
+    let rp = sp((1, 18, 18), (1, 19, 19));
+
+    let tokens = vec![
+        tsp(LeftPar, lp),
+        tsp(Symbol("const"), kw),
+        tsp(LeftPar, lp_x),
+        tsp(Symbol("x"), x_name),
+        tsp(Number("1"), one),
+        tsp(RightPar, rp_x),
+        tsp(LeftPar, lp_y),
+        tsp(Symbol("y"), y_name),
+        tsp(Number("2"), two),
+        tsp(RightPar, rp_y),
+        tsp(RightPar, rp),
+    ];
+    let prog = parse_sp(tokens.clone());
+
+    assert_eq!(
+        prog[0].span,
+        sp((1, 0, 0), (1, 19, 19)),
+        "input: {tokens:?}"
+    );
+    if let Expr::Const { vars } = &prog[0].inner {
+        assert_eq!(
+            vars[0].span,
+            sp((1, 7, 7), (1, 12, 12)),
+            "input: {tokens:?}"
+        );
+        assert_eq!(vars[0].inner.name.span, x_name, "input: {tokens:?}");
+        assert_eq!(vars[0].inner.expr.span, one, "input: {tokens:?}");
+        assert_eq!(
+            vars[1].span,
+            sp((1, 13, 13), (1, 18, 18)),
+            "input: {tokens:?}"
+        );
+        assert_eq!(vars[1].inner.name.span, y_name, "input: {tokens:?}");
+        assert_eq!(vars[1].inner.expr.span, two, "input: {tokens:?}");
+    } else {
+        panic!("expected Const, input: {tokens:?}");
+    }
 }
diff --git a/compiler/src/span.rs b/compiler/src/span.rs
index 8686f4f..8b46b31 100644
--- a/compiler/src/span.rs
+++ b/compiler/src/span.rs
@@ -38,6 +38,10 @@ impl<T> Spanned<T> {
         Self { inner, span }
     }
 
+    pub fn into_parts(self) -> (T, Span) {
+        (self.inner, self.span)
+    }
+
     pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Spanned<U> {
         let Self { inner, span } = self;
         Spanned {