merge(glittershark/achilles): Subtree import at 'b93268085a' r/2279

Imported from https://github.com/glittershark/achilles/

git-subtree-dir: users/glittershark/achilles
git-subtree-mainline: 4d193f239525954631ba9d789ca3aea9a2f4e14d
git-subtree-split: b93268085aab14c80a400c299da5d04d2781098e
Change-Id: I64a583b454bbe03e20358ad7808939a4cbc212ba

4 files changed, 958 insertions, 0 deletions

diff --git a/users/glittershark/achilles/src/parser/expr.rs b/users/glittershark/achilles/src/parser/expr.rs
new file mode 100644
index 000000000000..12c55df02b80
--- /dev/null
+++ b/users/glittershark/achilles/src/parser/expr.rs
@@ -0,0 +1,620 @@
+use std::borrow::Cow;
+
+use nom::alt;
+use nom::character::complete::{digit1, multispace0, multispace1};
+use nom::{
+    call, char, complete, delimited, do_parse, flat_map, many0, map, named, opt, parse_to,
+    preceded, separated_list0, separated_list1, tag, tuple,
+};
+use pratt::{Affix, Associativity, PrattParser, Precedence};
+
+use crate::ast::{BinaryOperator, Binding, Expr, Fun, Literal, UnaryOperator};
+use crate::parser::{arg, ident, type_};
+
+#[derive(Debug)]
+enum TokenTree<'a> {
+    Prefix(UnaryOperator),
+    // Postfix(char),
+    Infix(BinaryOperator),
+    Primary(Expr<'a>),
+    Group(Vec<TokenTree<'a>>),
+}
+
+named!(prefix(&str) -> TokenTree, map!(alt!(
+    complete!(char!('-')) => { |_| UnaryOperator::Neg } |
+    complete!(char!('!')) => { |_| UnaryOperator::Not }
+), TokenTree::Prefix));
+
+named!(infix(&str) -> TokenTree, map!(alt!(
+    complete!(tag!("==")) => { |_| BinaryOperator::Equ } |
+    complete!(tag!("!=")) => { |_| BinaryOperator::Neq } |
+    complete!(char!('+')) => { |_| BinaryOperator::Add } |
+    complete!(char!('-')) => { |_| BinaryOperator::Sub } |
+    complete!(char!('*')) => { |_| BinaryOperator::Mul } |
+    complete!(char!('/')) => { |_| BinaryOperator::Div } |
+    complete!(char!('^')) => { |_| BinaryOperator::Pow }
+), TokenTree::Infix));
+
+named!(primary(&str) -> TokenTree, alt!(
+    do_parse!(
+        multispace0 >>
+        char!('(') >>
+        multispace0 >>
+        group: group >>
+        multispace0 >>
+        char!(')') >>
+        multispace0 >>
+            (TokenTree::Group(group))
+    ) |
+    delimited!(multispace0, simple_expr, multispace0) => { |s| TokenTree::Primary(s) }
+));
+
+named!(
+    rest(&str) -> Vec<(TokenTree, Vec<TokenTree>, TokenTree)>,
+    many0!(tuple!(
+        infix,
+        delimited!(multispace0, many0!(prefix), multispace0),
+        primary
+        // many0!(postfix)
+    ))
+);
+
+named!(group(&str) -> Vec<TokenTree>, do_parse!(
+    prefix: many0!(prefix)
+        >> primary: primary
+        // >> postfix: many0!(postfix)
+        >> rest: rest
+        >> ({
+            let mut res = prefix;
+            res.push(primary);
+            // res.append(&mut postfix);
+            for (infix, mut prefix, primary/*, mut postfix*/) in rest {
+                res.push(infix);
+                res.append(&mut prefix);
+                res.push(primary);
+                // res.append(&mut postfix);
+            }
+            res
+        })
+));
+
+fn token_tree(i: &str) -> nom::IResult<&str, Vec<TokenTree>> {
+    group(i)
+}
+
+struct ExprParser;
+
+impl<'a, I> PrattParser<I> for ExprParser
+where
+    I: Iterator<Item = TokenTree<'a>>,
+{
+    type Error = pratt::NoError;
+    type Input = TokenTree<'a>;
+    type Output = Expr<'a>;
+
+    fn query(&mut self, input: &Self::Input) -> Result<Affix, Self::Error> {
+        use BinaryOperator::*;
+        use UnaryOperator::*;
+
+        Ok(match input {
+            TokenTree::Infix(Add) => Affix::Infix(Precedence(6), Associativity::Left),
+            TokenTree::Infix(Sub) => Affix::Infix(Precedence(6), Associativity::Left),
+            TokenTree::Infix(Mul) => Affix::Infix(Precedence(7), Associativity::Left),
+            TokenTree::Infix(Div) => Affix::Infix(Precedence(7), Associativity::Left),
+            TokenTree::Infix(Pow) => Affix::Infix(Precedence(8), Associativity::Right),
+            TokenTree::Infix(Equ) => Affix::Infix(Precedence(4), Associativity::Right),
+            TokenTree::Infix(Neq) => Affix::Infix(Precedence(4), Associativity::Right),
+            TokenTree::Prefix(Neg) => Affix::Prefix(Precedence(6)),
+            TokenTree::Prefix(Not) => Affix::Prefix(Precedence(6)),
+            TokenTree::Primary(_) => Affix::Nilfix,
+            TokenTree::Group(_) => Affix::Nilfix,
+        })
+    }
+
+    fn primary(&mut self, input: Self::Input) -> Result<Self::Output, Self::Error> {
+        Ok(match input {
+            TokenTree::Primary(expr) => expr,
+            TokenTree::Group(group) => self.parse(&mut group.into_iter()).unwrap(),
+            _ => unreachable!(),
+        })
+    }
+
+    fn infix(
+        &mut self,
+        lhs: Self::Output,
+        op: Self::Input,
+        rhs: Self::Output,
+    ) -> Result<Self::Output, Self::Error> {
+        let op = match op {
+            TokenTree::Infix(op) => op,
+            _ => unreachable!(),
+        };
+        Ok(Expr::BinaryOp {
+            lhs: Box::new(lhs),
+            op,
+            rhs: Box::new(rhs),
+        })
+    }
+
+    fn prefix(&mut self, op: Self::Input, rhs: Self::Output) -> Result<Self::Output, Self::Error> {
+        let op = match op {
+            TokenTree::Prefix(op) => op,
+            _ => unreachable!(),
+        };
+
+        Ok(Expr::UnaryOp {
+            op,
+            rhs: Box::new(rhs),
+        })
+    }
+
+    fn postfix(
+        &mut self,
+        _lhs: Self::Output,
+        _op: Self::Input,
+    ) -> Result<Self::Output, Self::Error> {
+        unreachable!()
+    }
+}
+
+named!(int(&str) -> Literal, map!(flat_map!(digit1, parse_to!(u64)), Literal::Int));
+
+named!(bool_(&str) -> Literal, alt!(
+    complete!(tag!("true")) => { |_| Literal::Bool(true) } |
+    complete!(tag!("false")) => { |_| Literal::Bool(false) }
+));
+
+fn string_internal(i: &str) -> nom::IResult<&str, Cow<'_, str>, nom::error::Error<&str>> {
+    let (s, rem) = i
+        .split_once('"')
+        .ok_or_else(|| nom::Err::Error(nom::error::Error::new(i, nom::error::ErrorKind::Tag)))?;
+    Ok((rem, Cow::Borrowed(s)))
+}
+
+named!(string(&str) -> Literal, preceded!(
+    complete!(char!('"')),
+    map!(
+        string_internal,
+        |s| Literal::String(s)
+    )
+));
+
+named!(literal(&str) -> Literal, alt!(int | bool_ | string));
+
+named!(literal_expr(&str) -> Expr, map!(literal, Expr::Literal));
+
+named!(binding(&str) -> Binding, do_parse!(
+    multispace0
+        >> ident: ident
+        >> multispace0
+        >> type_: opt!(preceded!(tuple!(tag!(":"), multispace0), type_))
+        >> multispace0
+        >> char!('=')
+        >> multispace0
+        >> body: expr
+        >> (Binding {
+            ident,
+            type_,
+            body
+        })
+));
+
+named!(let_(&str) -> Expr, do_parse!(
+    tag!("let")
+        >> multispace0
+        >> bindings: separated_list1!(alt!(char!(';') | char!('\n')), binding)
+        >> multispace0
+        >> tag!("in")
+        >> multispace0
+        >> body: expr
+        >> (Expr::Let {
+            bindings,
+            body: Box::new(body)
+        })
+));
+
+named!(if_(&str) -> Expr, do_parse! (
+    tag!("if")
+        >> multispace0
+        >> condition: expr
+        >> multispace0
+        >> tag!("then")
+        >> multispace0
+        >> then: expr
+        >> multispace0
+        >> tag!("else")
+        >> multispace0
+        >> else_: expr
+        >> (Expr::If {
+            condition: Box::new(condition),
+            then: Box::new(then),
+            else_: Box::new(else_)
+        })
+));
+
+named!(ident_expr(&str) -> Expr, map!(ident, Expr::Ident));
+
+fn ascripted<'a>(
+    p: impl Fn(&'a str) -> nom::IResult<&'a str, Expr, nom::error::Error<&'a str>> + 'a,
+) -> impl Fn(&'a str) -> nom::IResult<&str, Expr, nom::error::Error<&'a str>> {
+    move |i| {
+        do_parse!(
+            i,
+            expr: p
+                >> multispace0
+                >> complete!(tag!(":"))
+                >> multispace0
+                >> type_: type_
+                >> (Expr::Ascription {
+                    expr: Box::new(expr),
+                    type_
+                })
+        )
+    }
+}
+
+named!(paren_expr(&str) -> Expr,
+       delimited!(complete!(tag!("(")), expr, complete!(tag!(")"))));
+
+named!(funcref(&str) -> Expr, alt!(
+    ident_expr |
+    paren_expr
+));
+
+named!(no_arg_call(&str) -> Expr, do_parse!(
+    fun: funcref
+        >> multispace0
+        >> complete!(tag!("()"))
+        >> (Expr::Call {
+            fun: Box::new(fun),
+            args: vec![],
+        })
+));
+
+named!(fun_expr(&str) -> Expr, do_parse!(
+    tag!("fn")
+        >> multispace1
+        >> args: separated_list0!(multispace1, arg)
+        >> multispace0
+        >> char!('=')
+        >> multispace0
+        >> body: expr
+        >> (Expr::Fun(Box::new(Fun {
+            args,
+            body
+        })))
+));
+
+named!(fn_arg(&str) -> Expr, alt!(
+    ident_expr |
+    literal_expr |
+    paren_expr
+));
+
+named!(call_with_args(&str) -> Expr, do_parse!(
+    fun: funcref
+        >> multispace1
+        >> args: separated_list1!(multispace1, fn_arg)
+        >> (Expr::Call {
+            fun: Box::new(fun),
+            args
+        })
+));
+
+named!(simple_expr_unascripted(&str) -> Expr, alt!(
+    let_ |
+    if_ |
+    fun_expr |
+    literal_expr |
+    ident_expr
+));
+
+named!(simple_expr(&str) -> Expr, alt!(
+    call!(ascripted(simple_expr_unascripted)) |
+    simple_expr_unascripted
+));
+
+named!(pub expr(&str) -> Expr, alt!(
+    no_arg_call |
+    call_with_args |
+    map!(token_tree, |tt| {
+        ExprParser.parse(&mut tt.into_iter()).unwrap()
+    }) |
+    simple_expr
+));
+
+#[cfg(test)]
+pub(crate) mod tests {
+    use super::*;
+    use crate::ast::{Arg, Ident, Type};
+    use std::convert::TryFrom;
+    use BinaryOperator::*;
+    use Expr::{BinaryOp, If, Let, UnaryOp};
+    use UnaryOperator::*;
+
+    pub(crate) fn ident_expr(s: &str) -> Box<Expr> {
+        Box::new(Expr::Ident(Ident::try_from(s).unwrap()))
+    }
+
+    mod operators {
+        use super::*;
+
+        #[test]
+        fn mul_plus() {
+            let (rem, res) = expr("x*y+z").unwrap();
+            assert!(rem.is_empty());
+            assert_eq!(
+                res,
+                BinaryOp {
+                    lhs: Box::new(BinaryOp {
+                        lhs: ident_expr("x"),
+                        op: Mul,
+                        rhs: ident_expr("y")
+                    }),
+                    op: Add,
+                    rhs: ident_expr("z")
+                }
+            )
+        }
+
+        #[test]
+        fn mul_plus_ws() {
+            let (rem, res) = expr("x * y    +    z").unwrap();
+            assert!(rem.is_empty(), "non-empty remainder: \"{}\"", rem);
+            assert_eq!(
+                res,
+                BinaryOp {
+                    lhs: Box::new(BinaryOp {
+                        lhs: ident_expr("x"),
+                        op: Mul,
+                        rhs: ident_expr("y")
+                    }),
+                    op: Add,
+                    rhs: ident_expr("z")
+                }
+            )
+        }
+
+        #[test]
+        fn unary() {
+            let (rem, res) = expr("x * -z").unwrap();
+            assert!(rem.is_empty(), "non-empty remainder: \"{}\"", rem);
+            assert_eq!(
+                res,
+                BinaryOp {
+                    lhs: ident_expr("x"),
+                    op: Mul,
+                    rhs: Box::new(UnaryOp {
+                        op: Neg,
+                        rhs: ident_expr("z"),
+                    })
+                }
+            )
+        }
+
+        #[test]
+        fn mul_literal() {
+            let (rem, res) = expr("x * 3").unwrap();
+            assert!(rem.is_empty());
+            assert_eq!(
+                res,
+                BinaryOp {
+                    lhs: ident_expr("x"),
+                    op: Mul,
+                    rhs: Box::new(Expr::Literal(Literal::Int(3))),
+                }
+            )
+        }
+
+        #[test]
+        fn equ() {
+            let res = test_parse!(expr, "x * 7 == 7");
+            assert_eq!(
+                res,
+                BinaryOp {
+                    lhs: Box::new(BinaryOp {
+                        lhs: ident_expr("x"),
+                        op: Mul,
+                        rhs: Box::new(Expr::Literal(Literal::Int(7)))
+                    }),
+                    op: Equ,
+                    rhs: Box::new(Expr::Literal(Literal::Int(7)))
+                }
+            )
+        }
+    }
+
+    #[test]
+    fn bools() {
+        assert_eq!(
+            test_parse!(expr, "true"),
+            Expr::Literal(Literal::Bool(true))
+        );
+        assert_eq!(
+            test_parse!(expr, "false"),
+            Expr::Literal(Literal::Bool(false))
+        );
+    }
+
+    #[test]
+    fn simple_string_lit() {
+        assert_eq!(
+            test_parse!(expr, "\"foobar\""),
+            Expr::Literal(Literal::String(Cow::Borrowed("foobar")))
+        )
+    }
+
+    #[test]
+    fn let_complex() {
+        let res = test_parse!(expr, "let x = 1; y = x * 7 in (x + y) * 4");
+        assert_eq!(
+            res,
+            Let {
+                bindings: vec![
+                    Binding {
+                        ident: Ident::try_from("x").unwrap(),
+                        type_: None,
+                        body: Expr::Literal(Literal::Int(1))
+                    },
+                    Binding {
+                        ident: Ident::try_from("y").unwrap(),
+                        type_: None,
+                        body: Expr::BinaryOp {
+                            lhs: ident_expr("x"),
+                            op: Mul,
+                            rhs: Box::new(Expr::Literal(Literal::Int(7)))
+                        }
+                    }
+                ],
+                body: Box::new(Expr::BinaryOp {
+                    lhs: Box::new(Expr::BinaryOp {
+                        lhs: ident_expr("x"),
+                        op: Add,
+                        rhs: ident_expr("y"),
+                    }),
+                    op: Mul,
+                    rhs: Box::new(Expr::Literal(Literal::Int(4))),
+                })
+            }
+        )
+    }
+
+    #[test]
+    fn if_simple() {
+        let res = test_parse!(expr, "if x == 8 then 9 else 20");
+        assert_eq!(
+            res,
+            If {
+                condition: Box::new(BinaryOp {
+                    lhs: ident_expr("x"),
+                    op: Equ,
+                    rhs: Box::new(Expr::Literal(Literal::Int(8))),
+                }),
+                then: Box::new(Expr::Literal(Literal::Int(9))),
+                else_: Box::new(Expr::Literal(Literal::Int(20)))
+            }
+        )
+    }
+
+    #[test]
+    fn no_arg_call() {
+        let res = test_parse!(expr, "f()");
+        assert_eq!(
+            res,
+            Expr::Call {
+                fun: ident_expr("f"),
+                args: vec![]
+            }
+        );
+    }
+
+    #[test]
+    fn call_with_args() {
+        let res = test_parse!(expr, "f x 1");
+        assert_eq!(
+            res,
+            Expr::Call {
+                fun: ident_expr("f"),
+                args: vec![*ident_expr("x"), Expr::Literal(Literal::Int(1))]
+            }
+        )
+    }
+
+    #[test]
+    fn call_funcref() {
+        let res = test_parse!(expr, "(let x = 1 in x) 2");
+        assert_eq!(
+            res,
+            Expr::Call {
+                fun: Box::new(Expr::Let {
+                    bindings: vec![Binding {
+                        ident: Ident::try_from("x").unwrap(),
+                        type_: None,
+                        body: Expr::Literal(Literal::Int(1))
+                    }],
+                    body: ident_expr("x")
+                }),
+                args: vec![Expr::Literal(Literal::Int(2))]
+            }
+        )
+    }
+
+    #[test]
+    fn anon_function() {
+        let res = test_parse!(expr, "let id = fn x = x in id 1");
+        assert_eq!(
+            res,
+            Expr::Let {
+                bindings: vec![Binding {
+                    ident: Ident::try_from("id").unwrap(),
+                    type_: None,
+                    body: Expr::Fun(Box::new(Fun {
+                        args: vec![Arg::try_from("x").unwrap()],
+                        body: *ident_expr("x")
+                    }))
+                }],
+                body: Box::new(Expr::Call {
+                    fun: ident_expr("id"),
+                    args: vec![Expr::Literal(Literal::Int(1))],
+                })
+            }
+        );
+    }
+
+    mod ascriptions {
+        use super::*;
+
+        #[test]
+        fn bare_ascription() {
+            let res = test_parse!(expr, "1: float");
+            assert_eq!(
+                res,
+                Expr::Ascription {
+                    expr: Box::new(Expr::Literal(Literal::Int(1))),
+                    type_: Type::Float
+                }
+            )
+        }
+
+        #[test]
+        fn fn_body_ascription() {
+            let res = test_parse!(expr, "let const_1 = fn x = 1: int in const_1 2");
+            assert_eq!(
+                res,
+                Expr::Let {
+                    bindings: vec![Binding {
+                        ident: Ident::try_from("const_1").unwrap(),
+                        type_: None,
+                        body: Expr::Fun(Box::new(Fun {
+                            args: vec![Arg::try_from("x").unwrap()],
+                            body: Expr::Ascription {
+                                expr: Box::new(Expr::Literal(Literal::Int(1))),
+                                type_: Type::Int,
+                            }
+                        }))
+                    }],
+                    body: Box::new(Expr::Call {
+                        fun: ident_expr("const_1"),
+                        args: vec![Expr::Literal(Literal::Int(2))]
+                    })
+                }
+            )
+        }
+
+        #[test]
+        fn let_binding_ascripted() {
+            let res = test_parse!(expr, "let x: int = 1 in x");
+            assert_eq!(
+                res,
+                Expr::Let {
+                    bindings: vec![Binding {
+                        ident: Ident::try_from("x").unwrap(),
+                        type_: Some(Type::Int),
+                        body: Expr::Literal(Literal::Int(1))
+                    }],
+                    body: ident_expr("x")
+                }
+            )
+        }
+    }
+}
diff --git a/users/glittershark/achilles/src/parser/macros.rs b/users/glittershark/achilles/src/parser/macros.rs
new file mode 100644
index 000000000000..406e5c0e699e
--- /dev/null
+++ b/users/glittershark/achilles/src/parser/macros.rs
@@ -0,0 +1,16 @@
+#[cfg(test)]
+#[macro_use]
+macro_rules! test_parse {
+    ($parser: ident, $src: expr) => {{
+        let res = $parser($src);
+        nom_trace::print_trace!();
+        let (rem, res) = res.unwrap();
+        assert!(
+            rem.is_empty(),
+            "non-empty remainder: \"{}\", parsed: {:?}",
+            rem,
+            res
+        );
+        res
+    }};
+}
diff --git a/users/glittershark/achilles/src/parser/mod.rs b/users/glittershark/achilles/src/parser/mod.rs
new file mode 100644
index 000000000000..dd7874aff853
--- /dev/null
+++ b/users/glittershark/achilles/src/parser/mod.rs
@@ -0,0 +1,197 @@
+use nom::character::complete::{multispace0, multispace1};
+use nom::error::{ErrorKind, ParseError};
+use nom::{alt, char, complete, do_parse, many0, named, separated_list0, tag, terminated};
+
+#[macro_use]
+mod macros;
+mod expr;
+mod type_;
+
+use crate::ast::{Arg, Decl, Fun, Ident};
+pub use expr::expr;
+pub use type_::type_;
+
+pub type Error = nom::Err<nom::error::Error<String>>;
+
+pub(crate) fn is_reserved(s: &str) -> bool {
+    matches!(
+        s,
+        "if" | "then"
+            | "else"
+            | "let"
+            | "in"
+            | "fn"
+            | "int"
+            | "float"
+            | "bool"
+            | "true"
+            | "false"
+            | "cstring"
+    )
+}
+
+pub(crate) fn ident<'a, E>(i: &'a str) -> nom::IResult<&'a str, Ident, E>
+where
+    E: ParseError<&'a str>,
+{
+    let mut chars = i.chars();
+    if let Some(f) = chars.next() {
+        if f.is_alphabetic() || f == '_' {
+            let mut idx = 1;
+            for c in chars {
+                if !(c.is_alphanumeric() || c == '_') {
+                    break;
+                }
+                idx += 1;
+            }
+            let id = &i[..idx];
+            if is_reserved(id) {
+                Err(nom::Err::Error(E::from_error_kind(i, ErrorKind::Satisfy)))
+            } else {
+                Ok((&i[idx..], Ident::from_str_unchecked(id)))
+            }
+        } else {
+            Err(nom::Err::Error(E::from_error_kind(i, ErrorKind::Satisfy)))
+        }
+    } else {
+        Err(nom::Err::Error(E::from_error_kind(i, ErrorKind::Eof)))
+    }
+}
+
+named!(ascripted_arg(&str) -> Arg, do_parse!(
+    complete!(char!('(')) >>
+        multispace0 >>
+        ident: ident >>
+        multispace0 >>
+        complete!(char!(':')) >>
+        multispace0 >>
+        type_: type_ >>
+        multispace0 >>
+        complete!(char!(')')) >>
+        (Arg {
+            ident,
+            type_: Some(type_)
+        })
+));
+
+named!(arg(&str) -> Arg, alt!(
+    ident => { |ident| Arg {ident, type_: None}} |
+    ascripted_arg
+));
+
+named!(fun_decl(&str) -> Decl, do_parse!(
+    complete!(tag!("fn"))
+        >> multispace0
+        >> name: ident
+        >> multispace1
+        >> args: separated_list0!(multispace1, arg)
+        >> multispace0
+        >> char!('=')
+        >> multispace0
+        >> body: expr
+        >> (Decl::Fun {
+            name,
+            body: Fun {
+                args,
+                body
+            }
+        })
+));
+
+named!(ascription_decl(&str) -> Decl, do_parse!(
+    name: ident
+        >> multispace0
+        >> complete!(char!(':'))
+        >> multispace0
+        >> type_: type_
+        >> (Decl::Ascription {
+            name,
+            type_
+        })
+));
+
+named!(pub decl(&str) -> Decl, alt!(
+    ascription_decl |
+    fun_decl
+));
+
+named!(pub toplevel(&str) -> Vec<Decl>, terminated!(many0!(decl), multispace0));
+
+#[cfg(test)]
+mod tests {
+    use std::convert::TryInto;
+
+    use crate::ast::{BinaryOperator, Expr, FunctionType, Literal, Type};
+
+    use super::*;
+    use expr::tests::ident_expr;
+
+    #[test]
+    fn fn_decl() {
+        let res = test_parse!(decl, "fn id x = x");
+        assert_eq!(
+            res,
+            Decl::Fun {
+                name: "id".try_into().unwrap(),
+                body: Fun {
+                    args: vec!["x".try_into().unwrap()],
+                    body: *ident_expr("x"),
+                }
+            }
+        )
+    }
+
+    #[test]
+    fn ascripted_fn_args() {
+        test_parse!(ascripted_arg, "(x : int)");
+        let res = test_parse!(decl, "fn plus1 (x : int) = x + 1");
+        assert_eq!(
+            res,
+            Decl::Fun {
+                name: "plus1".try_into().unwrap(),
+                body: Fun {
+                    args: vec![Arg {
+                        ident: "x".try_into().unwrap(),
+                        type_: Some(Type::Int),
+                    }],
+                    body: Expr::BinaryOp {
+                        lhs: ident_expr("x"),
+                        op: BinaryOperator::Add,
+                        rhs: Box::new(Expr::Literal(Literal::Int(1))),
+                    }
+                }
+            }
+        );
+    }
+
+    #[test]
+    fn multiple_decls() {
+        let res = test_parse!(
+            toplevel,
+            "fn id x = x
+             fn plus x y = x + y
+             fn main = plus (id 2) 7"
+        );
+        assert_eq!(res.len(), 3);
+        let res = test_parse!(
+            toplevel,
+            "fn id x = x\nfn plus x y = x + y\nfn main = plus (id 2) 7\n"
+        );
+        assert_eq!(res.len(), 3);
+    }
+
+    #[test]
+    fn top_level_ascription() {
+        let res = test_parse!(toplevel, "id : fn a -> a");
+        assert_eq!(
+            res,
+            vec![Decl::Ascription {
+                name: "id".try_into().unwrap(),
+                type_: Type::Function(FunctionType {
+                    args: vec![Type::Var("a".try_into().unwrap())],
+                    ret: Box::new(Type::Var("a".try_into().unwrap()))
+                })
+            }]
+        )
+    }
+}
diff --git a/users/glittershark/achilles/src/parser/type_.rs b/users/glittershark/achilles/src/parser/type_.rs
new file mode 100644
index 000000000000..c90ceda4d72e
--- /dev/null
+++ b/users/glittershark/achilles/src/parser/type_.rs
@@ -0,0 +1,125 @@
+use nom::character::complete::{multispace0, multispace1};
+use nom::{alt, delimited, do_parse, map, named, opt, separated_list0, tag, terminated, tuple};
+
+use super::ident;
+use crate::ast::{FunctionType, Type};
+
+named!(function_type(&str) -> Type, do_parse!(
+    tag!("fn")
+        >> multispace1
+        >> args: map!(opt!(terminated!(separated_list0!(
+            tuple!(
+                multispace0,
+                tag!(","),
+                multispace0
+            ),
+            type_
+        ), multispace1)), |args| args.unwrap_or_default())
+        >> tag!("->")
+        >> multispace1
+        >> ret: type_
+        >> (Type::Function(FunctionType {
+            args,
+            ret: Box::new(ret)
+        }))
+));
+
+named!(pub type_(&str) -> Type, alt!(
+    tag!("int") => { |_| Type::Int } |
+    tag!("float") => { |_| Type::Float } |
+    tag!("bool") => { |_| Type::Bool } |
+    tag!("cstring") => { |_| Type::CString } |
+    function_type |
+    ident => { |id| Type::Var(id) } |
+    delimited!(
+        tuple!(tag!("("), multispace0),
+        type_,
+        tuple!(tag!(")"), multispace0)
+    )
+));
+
+#[cfg(test)]
+mod tests {
+    use std::convert::TryFrom;
+
+    use super::*;
+    use crate::ast::Ident;
+
+    #[test]
+    fn simple_types() {
+        assert_eq!(test_parse!(type_, "int"), Type::Int);
+        assert_eq!(test_parse!(type_, "float"), Type::Float);
+        assert_eq!(test_parse!(type_, "bool"), Type::Bool);
+        assert_eq!(test_parse!(type_, "cstring"), Type::CString);
+    }
+
+    #[test]
+    fn no_arg_fn_type() {
+        assert_eq!(
+            test_parse!(type_, "fn -> int"),
+            Type::Function(FunctionType {
+                args: vec![],
+                ret: Box::new(Type::Int)
+            })
+        );
+    }
+
+    #[test]
+    fn fn_type_with_args() {
+        assert_eq!(
+            test_parse!(type_, "fn int, bool -> int"),
+            Type::Function(FunctionType {
+                args: vec![Type::Int, Type::Bool],
+                ret: Box::new(Type::Int)
+            })
+        );
+    }
+
+    #[test]
+    fn fn_taking_fn() {
+        assert_eq!(
+            test_parse!(type_, "fn fn int, bool -> bool, float -> float"),
+            Type::Function(FunctionType {
+                args: vec![
+                    Type::Function(FunctionType {
+                        args: vec![Type::Int, Type::Bool],
+                        ret: Box::new(Type::Bool)
+                    }),
+                    Type::Float
+                ],
+                ret: Box::new(Type::Float)
+            })
+        )
+    }
+
+    #[test]
+    fn parenthesized() {
+        assert_eq!(
+            test_parse!(type_, "fn (fn int, bool -> bool), float -> float"),
+            Type::Function(FunctionType {
+                args: vec![
+                    Type::Function(FunctionType {
+                        args: vec![Type::Int, Type::Bool],
+                        ret: Box::new(Type::Bool)
+                    }),
+                    Type::Float
+                ],
+                ret: Box::new(Type::Float)
+            })
+        )
+    }
+
+    #[test]
+    fn type_vars() {
+        assert_eq!(
+            test_parse!(type_, "fn x, y -> x"),
+            Type::Function(FunctionType {
+                args: vec![
+                    Type::Var(Ident::try_from("x").unwrap()),
+                    Type::Var(Ident::try_from("y").unwrap()),
+                ],
+                ret: Box::new(Type::Var(Ident::try_from("x").unwrap())),
+            })
+        )
+    }
+}