Move λ-calcul workshop code to subdirectory

8 files changed, 1895 insertions, 0 deletions

diff --git a/lambda-calcul/rust/src/ast.rs b/lambda-calcul/rust/src/ast.rs
new file mode 100644
index 0000000..d0f1d6f
--- /dev/null
+++ b/lambda-calcul/rust/src/ast.rs
@@ -0,0 +1,117 @@
+use proptest::{
+    prelude::*,
+    string::{string_regex, RegexGeneratorStrategy},
+};
+use serde::{Deserialize, Serialize};
+use std::fmt::{self, Display};
+
+#[derive(Debug, PartialEq, Clone, Serialize, Deserialize)]
+pub enum Value {
+    Num(i32),
+    Bool(bool),
+    Sym(String),
+    App(Box<Value>, Box<Value>),
+    Lam(String, Box<Value>),
+    Def(String, Box<Value>),
+    Let(String, Box<Value>, Box<Value>),
+}
+
+use Value::*;
+
+impl Value {
+    /// Return the spine of an application
+    fn spine(&self) -> Vec<Value> {
+        match self {
+            App(l, r) => {
+                let mut spine = l.spine();
+                spine.push(*r.clone());
+                spine
+            }
+            _ => vec![self.clone()],
+        }
+    }
+}
+
+impl Display for Value {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Value::Num(i) => write!(f, "{}", i),
+            Value::Bool(b) => write!(f, "{}", b),
+            Value::Sym(s) => write!(f, "{}", s),
+            Value::App(_, _) => {
+                let app = self
+                    .spine()
+                    .iter()
+                    .map(|v| v.to_string())
+                    .collect::<Vec<String>>()
+                    .join(" ");
+                write!(f, "({})", app)
+            }
+            Value::Lam(var, body) => write!(f, "(lam {} {})", var, body),
+            Value::Def(var, value) => write!(f, "(def {} {})", var, value),
+            Value::Let(var, value, body) => write!(f, "(let ({} {}) {})", var, value, body),
+        }
+    }
+}
+
+pub const IDENTIFIER: &str = "\\pL(\\pL|\\pN)*";
+
+pub fn identifier() -> RegexGeneratorStrategy<String> {
+    string_regex(IDENTIFIER).unwrap()
+}
+
+pub fn ascii_identifier() -> RegexGeneratorStrategy<String> {
+    string_regex("[a-zA-Z][a-zA-Z0-9]*").unwrap()
+}
+
+impl Arbitrary for Value {
+    type Parameters = ();
+    type Strategy = BoxedStrategy<Self>;
+
+    fn arbitrary_with(_args: ()) -> Self::Strategy {
+        let any_num = any::<i32>().prop_map(Num);
+        let any_bool = any::<bool>().prop_map(Bool);
+        let leaf = prop_oneof![
+            any_num,
+            any_bool,
+            // see https://unicode.org/reports/tr18/#General_Category_Property for one letter unicode categories
+            identifier().prop_map(Sym),
+        ];
+        let expr = leaf.prop_recursive(4, 128, 5, move |inner| {
+            prop_oneof![
+                (inner.clone(), inner.clone()).prop_map(|(l, r)| App(Box::new(l), Box::new(r))),
+                (identifier(), inner.clone()).prop_map(|(var, body)| Lam(var, Box::new(body))),
+                (identifier(), inner.clone(), inner.clone()).prop_map(|(var, body, expr)| {
+                    Value::Let(var, Box::new(body), Box::new(expr))
+                }),
+            ]
+        });
+        prop_oneof![
+            expr.clone(),
+            (identifier(), expr).prop_map(|(var, body)| Def(var, Box::new(body)))
+        ]
+        .boxed()
+    }
+}
+
+#[cfg(test)]
+mod ast_tests {
+
+    use super::Value::{self, *};
+    use proptest::collection::vec;
+    use proptest::prelude::*;
+
+    proptest! {
+
+       #[test]
+        fn display_multiple_applications_as_a_sequence(atoms in vec("[a-z]".prop_map(Sym), 2..10)) {
+            let init  = atoms.first().unwrap().clone();
+            let value = atoms.iter().skip(1).fold(init, |acc, expr| {
+              Value::App(Box::new(acc.clone()), Box::new(expr.clone()))
+            });
+            assert_eq!(value.to_string(),
+                       format!("({})",
+                               atoms.iter().map(|v| v.to_string()).collect::<Vec<String>>().join(" ")));
+      }
+    }
+}
diff --git a/lambda-calcul/rust/src/io.rs b/lambda-calcul/rust/src/io.rs
new file mode 100644
index 0000000..8c628ba
--- /dev/null
+++ b/lambda-calcul/rust/src/io.rs
@@ -0,0 +1,73 @@
+use std::{
+    fs::read_to_string,
+    io::{BufRead, BufReader, Read, Write},
+};
+
+use crate::{
+    ast::Value,
+    lambda::{eval_all, eval_whnf, Environment},
+    parser::parse,
+};
+
+pub fn eval_file(file_name: &str) -> String {
+    let content = read_to_string(file_name).unwrap();
+    let values = parse(&content.to_string());
+    eval_all(&values)
+        .iter()
+        .map(|v| v.to_string())
+        .collect::<Vec<String>>()
+        .join(" ")
+}
+
+pub fn batch_eval<I: Read, O: Write>(inp: &mut I, outp: &mut O) {
+    let mut env = Environment::new();
+    let mut reader = BufReader::new(inp);
+    loop {
+        let mut input = String::new();
+        outp.flush().unwrap();
+        match reader.read_line(&mut input) {
+            Ok(0) => break,
+            Ok(_) => (),
+            Err(e) => {
+                writeln!(outp, "{}", e).unwrap();
+                break;
+            }
+        }
+        let values = parse(&input);
+        let results = values
+            .iter()
+            .map(|v| eval_whnf(v, &mut env))
+            .collect::<Vec<Value>>();
+        for result in results {
+            writeln!(outp, "{}", result).unwrap();
+            outp.flush().unwrap();
+        }
+    }
+}
+
+pub fn repl<I: Read, O: Write>(inp: &mut I, outp: &mut O) {
+    let mut env = Environment::new();
+    let mut reader = BufReader::new(inp);
+    loop {
+        let mut input = String::new();
+        write!(outp, "> ").unwrap();
+        outp.flush().unwrap();
+        match reader.read_line(&mut input) {
+            Ok(0) => break,
+            Ok(_) => (),
+            Err(e) => {
+                writeln!(outp, "{}", e).unwrap();
+                break;
+            }
+        }
+        let values = parse(&input);
+        let results = values
+            .iter()
+            .map(|v| eval_whnf(v, &mut env))
+            .collect::<Vec<Value>>();
+        for result in results {
+            writeln!(outp, "{}", result).unwrap();
+            outp.flush().unwrap();
+        }
+    }
+}
diff --git a/lambda-calcul/rust/src/lambda.rs b/lambda-calcul/rust/src/lambda.rs
new file mode 100644
index 0000000..a73ca34
--- /dev/null
+++ b/lambda-calcul/rust/src/lambda.rs
@@ -0,0 +1,292 @@
+use proptest::{
+    arbitrary::any,
+    prelude::*,
+    strategy::{Strategy, ValueTree},
+    test_runner::TestRunner,
+};
+use rand::Rng;
+use std::collections::HashMap;
+
+use crate::ast::*;
+
+#[derive(Debug, PartialEq)]
+pub struct Environment<'a> {
+    parent: Box<Option<&'a Environment<'a>>>,
+    bindings: HashMap<String, Value>,
+}
+
+impl<'a> Environment<'a> {
+    pub fn new() -> Self {
+        Environment {
+            parent: Box::new(None),
+            bindings: HashMap::new(),
+        }
+    }
+
+    fn bind(&mut self, var: &str, value: &Value) {
+        self.bindings.insert(var.to_string(), value.clone());
+    }
+
+    fn extends(&'a self) -> Self {
+        Environment {
+            parent: Box::new(Some(self)),
+            bindings: HashMap::new(),
+        }
+    }
+
+    fn lookup(&self, var: &str) -> Option<&Value> {
+        self.bindings.get(var).or_else(|| match *self.parent {
+            Some(parent) => parent.lookup(var),
+            None => None,
+        })
+    }
+}
+
+impl<'a> Default for Environment<'a> {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+pub fn eval_all(values: &[Value]) -> Vec<Value> {
+    let mut env = Environment::new();
+    values.iter().map(|v| eval_whnf(v, &mut env)).collect()
+}
+
+/// Reduce the given value to weak head normal form using call-by-name
+/// evaluation strategy.
+///
+/// call-by-name reduces the leftmost outermost redex first, which is
+/// not under a lambda abstraction.
+pub fn eval_whnf(arg: &Value, env: &mut Environment) -> Value {
+    match arg {
+        Value::Def(var, value) => {
+            env.bind(var, value);
+            Value::Bool(true) // TODO: return a more meaningful value?
+        }
+        Value::Let(var, value, expr) => {
+            let mut newenv = env.extends();
+            newenv.bind(var, value);
+            eval_whnf(expr, &mut newenv)
+        }
+        Value::App(l, r) => match eval_whnf(l, env) {
+            Value::Lam(v, body) => eval_whnf(&subst(&v, &body, r), env),
+            Value::Sym(var) => match env.lookup(&var) {
+                Some(val) => eval_whnf(&Value::App(Box::new(val.clone()), r.clone()), env),
+                None => arg.clone(),
+            },
+            other => Value::App(Box::new(other), r.clone()),
+        },
+        Value::Sym(var) => env.lookup(var).unwrap_or(arg).clone(),
+        other => other.clone(),
+    }
+}
+
+fn subst(var: &str, body: &Value, e: &Value) -> Value {
+    match body {
+        Value::Sym(x) if x == var => e.clone(),
+        Value::Lam(x, b) if x == var => {
+            let y = gensym();
+            let bd = subst(x, b, &Value::Sym(y.clone()));
+            Value::Lam(y, Box::new(bd))
+        }
+        Value::Lam(x, b) => Value::Lam(x.to_string(), Box::new(subst(var, b, e))),
+        Value::App(l, r) => Value::App(Box::new(subst(var, l, e)), Box::new(subst(var, r, e))),
+        other => other.clone(),
+    }
+}
+
+pub fn gensym() -> String {
+    let mut rng = rand::thread_rng();
+
+    let n1: u8 = rng.gen();
+    format!("x_{}", n1)
+}
+
+pub fn generate_expr(size: u32, runner: &mut TestRunner) -> Value {
+    match size {
+        0 | 1 => {
+            let n = any::<u16>().new_tree(runner).unwrap().current();
+            Value::Num(n.into())
+        }
+        2 => Value::Sym(ascii_identifier().new_tree(runner).unwrap().current()),
+        3 => any_sym().new_tree(runner).unwrap().current(),
+        4 => simple_app().new_tree(runner).unwrap().current(),
+        5 => nested_simple_app().new_tree(runner).unwrap().current(),
+        6 => simple_lambda().new_tree(runner).unwrap().current(),
+        7 => app_to_lambda().new_tree(runner).unwrap().current(),
+        8 => multi_app().new_tree(runner).unwrap().current(),
+        _ => any::<u32>()
+            .prop_flat_map(gen_terms)
+            .new_tree(runner)
+            .unwrap()
+            .current(),
+    }
+}
+
+pub fn generate_exprs(size: u32, runner: &mut TestRunner) -> Vec<Value> {
+    let sz = (0..size).new_tree(runner).unwrap().current();
+    (0..sz)
+        .collect::<Vec<_>>()
+        .into_iter()
+        .map(|_| generate_expr(size, runner))
+        .collect()
+}
+
+fn simple_app() -> impl Strategy<Value = Value> {
+    let leaf = prop_oneof![any_num(), any_sym()];
+    (leaf.clone(), leaf.clone()).prop_map(|(l, r)| Value::App(Box::new(l), Box::new(r)))
+}
+
+fn multi_app() -> impl Strategy<Value = Value> {
+    let leaf = prop_oneof![any_num(), any_sym()];
+    (leaf.clone(), leaf.clone()).prop_map(|(l, r)| Value::App(Box::new(l), Box::new(r)))
+}
+
+fn any_num() -> impl Strategy<Value = Value> {
+    any::<i32>().prop_map(Value::Num)
+}
+
+fn nested_simple_app() -> impl Strategy<Value = Value> {
+    let leaf = prop_oneof![any_num(), ascii_identifier().prop_map(Value::Sym)];
+    leaf.prop_recursive(4, 128, 5, move |inner| {
+        (inner.clone(), inner.clone()).prop_map(|(l, r)| Value::App(Box::new(l), Box::new(r)))
+    })
+}
+
+fn any_sym() -> impl Strategy<Value = Value> {
+    identifier().prop_map(Value::Sym)
+}
+
+fn simple_lambda() -> impl Strategy<Value = Value> {
+    // TODO: there's nothing to guarantee the variable appears in the body
+    (ascii_identifier(), nested_simple_app()).prop_map(|(v, b)| Value::Lam(v, Box::new(b)))
+}
+
+fn app_to_lambda() -> impl Strategy<Value = Value> {
+    let lam = simple_lambda();
+    let arg = prop_oneof![any_num(), any_sym(), nested_simple_app()];
+    (lam, arg).prop_map(|(l, a)| Value::App(Box::new(l), Box::new(a)))
+}
+
+/// Cantor pairing function
+/// See https://en.wikipedia.org/wiki/Pairing_function
+fn pairing(k: u32) -> (u32, u32) {
+    let a = ((((8 * (k as u64) + 1) as f64).sqrt() - 1.0) / 2.0).floor();
+    let b = (a * (a + 1.0)) / 2.0;
+    let n = (k as f64) - b;
+    (n as u32, (a - n) as u32)
+}
+
+fn gen_terms(u: u32) -> impl Strategy<Value = Value> {
+    if u % 2 != 0 {
+        let j = (u - 1) / 2;
+        if j % 2 == 0 {
+            let k = j / 2;
+            let (n, m) = pairing(k);
+            let r = (gen_terms(n), gen_terms(m))
+                .prop_map(move |(l, r)| Value::App(Box::new(l), Box::new(r)));
+            r.boxed()
+        } else {
+            let k = (j - 1) / 2;
+            let (n, m) = pairing(k);
+            let r = gen_terms(m).prop_map(move |v| Value::Lam(format!("x_{}", n), Box::new(v)));
+            r.boxed()
+        }
+    } else {
+        let j = u / 2;
+        Just(Value::Sym(format!("x_{}", j))).boxed()
+    }
+}
+
+#[cfg(test)]
+mod lambda_test {
+    use crate::parser::parse;
+
+    use super::{eval_all, eval_whnf, Environment, Value};
+
+    fn parse1(string: &str) -> Value {
+        parse(string).pop().unwrap()
+    }
+
+    fn eval1(value: &Value) -> Value {
+        eval_whnf(value, &mut Environment::new())
+    }
+
+    #[test]
+    fn evaluating_a_non_reducible_value_yields_itself() {
+        let value = parse1("(foo 12)");
+        assert_eq!(value, eval1(&value));
+    }
+
+    #[test]
+    fn evaluating_application_on_an_abstraction_reduces_it() {
+        let value = parse1("((lam x x) 12)");
+        assert_eq!(Value::Num(12), eval1(&value));
+    }
+
+    #[test]
+    fn substitution_occurs_within_abstraction_body() {
+        let value = parse1("(((lam x (lam y x)) 13) 12)");
+        assert_eq!(Value::Num(13), eval1(&value));
+    }
+
+    #[test]
+    fn substitution_occurs_within_application_body() {
+        let value = parse1("(((lam x (lam y (y x))) 13) 12)");
+        assert_eq!(
+            Value::App(Box::new(Value::Num(12)), Box::new(Value::Num(13))),
+            eval1(&value)
+        );
+    }
+
+    #[test]
+    fn substitution_does_not_capture_free_variables() {
+        let value = parse1("(((lam x (lam x x)) 13) 12)");
+        assert_eq!(Value::Num(12), eval1(&value));
+    }
+
+    #[test]
+    fn interpretation_applies_to_both_sides_of_application() {
+        let value = parse1("((lam x x) ((lam x x) 12))");
+        assert_eq!(Value::Num(12), eval1(&value));
+    }
+
+    #[test]
+    fn reduction_is_applied_until_normal_form_is_reached() {
+        let value = parse1("((((lam y (lam x (lam y (x y)))) 13) (lam x x)) 11)");
+        assert_eq!(Value::Num(11), eval1(&value));
+    }
+
+    #[test]
+    fn reduction_always_select_leftmost_outermost_redex() {
+        // this should not terminate if we evaluate the rightmost redex first, eg.
+        // applicative order reduction
+        let value = parse1("((lam x 1) ((lam x (x x)) (lam x (x x))))");
+        assert_eq!(Value::Num(1), eval1(&value));
+    }
+
+    #[test]
+    fn defined_symbols_are_evaluated_to_their_definition() {
+        let values = parse("(def foo 12)  foo");
+        assert_eq!(vec![Value::Bool(true), Value::Num(12)], eval_all(&values));
+    }
+
+    #[test]
+    fn let_expressions_bind_symbol_to_expression_in_environment() {
+        let values = parse("(let (foo (lam x x))  (foo 12))");
+        assert_eq!(vec![Value::Num(12)], eval_all(&values));
+    }
+
+    #[test]
+    fn let_expressions_introduce_new_scope_for_bindings() {
+        let values = parse("(let (foo (lam x x)) ((let (foo foo) foo) 13))");
+        assert_eq!(vec![Value::Num(13)], eval_all(&values));
+    }
+
+    #[test]
+    fn bound_symbol_in_higher_scope_are_resolved() {
+        let values = parse("(let (id (lam x x)) (let (foo 12) (id foo)))");
+        assert_eq!(vec![Value::Num(12)], eval_all(&values));
+    }
+}
diff --git a/lambda-calcul/rust/src/lib.rs b/lambda-calcul/rust/src/lib.rs
new file mode 100644
index 0000000..a8cf18e
--- /dev/null
+++ b/lambda-calcul/rust/src/lib.rs
@@ -0,0 +1,4 @@
+pub mod ast;
+pub mod io;
+pub mod lambda;
+pub mod parser;
diff --git a/lambda-calcul/rust/src/main.rs b/lambda-calcul/rust/src/main.rs
new file mode 100644
index 0000000..8d52c46
--- /dev/null
+++ b/lambda-calcul/rust/src/main.rs
@@ -0,0 +1,18 @@
+use std::{
+    env::args,
+    io::{stdin, stdout, IsTerminal},
+};
+
+use lambda::io::{batch_eval, eval_file, repl};
+
+fn main() {
+    if args().count() > 1 {
+        for file in args().skip(1) {
+            println!("{}", eval_file(&file));
+        }
+    } else if stdin().is_terminal() {
+        repl(&mut stdin(), &mut stdout());
+    } else {
+        batch_eval(&mut stdin(), &mut stdout());
+    }
+}
diff --git a/lambda-calcul/rust/src/parser.rs b/lambda-calcul/rust/src/parser.rs
new file mode 100644
index 0000000..52aad5a
--- /dev/null
+++ b/lambda-calcul/rust/src/parser.rs
@@ -0,0 +1,392 @@
+use crate::ast::*;
+
+#[derive(Debug, PartialEq)]
+enum Token {
+    LParen,
+    RParen,
+    Lambda,
+    Word(String),
+    Define,
+    Let,
+}
+
+#[derive(Debug)]
+struct Parser {
+    tokens: Vec<Token>,
+    index: usize,
+}
+
+impl Parser {
+    fn expect(&mut self, token: Token) -> Result<(), String> {
+        if self.tokens.get(self.index) == Some(&token) {
+            Ok(())
+        } else {
+            Err(format!(
+                "Expected {:?}, got {:?}",
+                token,
+                self.tokens.get(self.index)
+            ))
+        }
+        .map(|_| {
+            self.next();
+        })
+    }
+
+    fn expect_symbol(&mut self) -> Result<String, String> {
+        if let Token::Word(s) = self.tokens.get(self.index).ok_or("Expected a symbol")? {
+            Ok(s.clone())
+        } else {
+            Err("Expected a symbol".to_string())
+        }
+        .map(|s| {
+            self.next();
+            s
+        })
+    }
+
+    fn next(&mut self) {
+        self.index += 1;
+    }
+
+    fn backtrack(&mut self) {
+        self.index -= 1;
+    }
+}
+
+pub fn parse(arg: &str) -> Vec<Value> {
+    parse_total(arg)
+        .map_err(|e| panic!("Syntax error: {}", e))
+        .unwrap()
+}
+
+pub fn parse_total(arg: &str) -> Result<Vec<Value>, String> {
+    let tokens = tokenize(arg);
+    let mut parser = Parser { tokens, index: 0 };
+    let mut result = Vec::new();
+    while parser.index < parser.tokens.len() {
+        let expr = parse_toplevel(&mut parser)?;
+        result.push(expr);
+    }
+    Ok(result)
+}
+
+fn parse_toplevel(parser: &mut Parser) -> Result<Value, String> {
+    parse_definition(parser).or_else(|_| parse_expression(parser))
+}
+
+fn parse_definition(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    parser.expect(Token::Define).map_err(|e| {
+        parser.backtrack();
+        e.to_string()
+    })?;
+    let var = parse_variable(parser)?;
+    let body = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    Ok(Value::Def(var, Box::new(body)))
+}
+
+fn parse_expression(parser: &mut Parser) -> Result<Value, String> {
+    parse_value(parser)
+        .or_else(|_| parse_abstraction(parser))
+        .or_else(|_| parse_let(parser))
+        .or_else(|_| parse_application(parser))
+}
+
+fn parse_abstraction(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    parser.expect(Token::Lambda).map_err(|e| {
+        parser.backtrack();
+        e.to_string()
+    })?;
+    let vars = parse_variables(parser)?;
+    let body = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    let result = vars
+        .iter()
+        .rev()
+        .fold(body, |acc, var| Value::Lam(var.clone(), Box::new(acc)));
+    Ok(result)
+}
+
+fn parse_variables(parser: &mut Parser) -> Result<Vec<String>, String> {
+    parse_variable(parser)
+        .map(|s| vec![s])
+        .or_else(|_| parse_variables_list(parser))
+}
+
+fn parse_variables_list(parser: &mut Parser) -> Result<Vec<String>, String> {
+    let mut vars = Vec::new();
+    parser.expect(Token::LParen)?;
+    while let Ok(var) = parse_variable(parser) {
+        vars.push(var);
+    }
+    parser.expect(Token::RParen)?;
+    Ok(vars)
+}
+
+fn parse_variable(parser: &mut Parser) -> Result<String, String> {
+    let var = parser.expect_symbol()?;
+    Ok(var)
+}
+
+fn parse_let(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    parser.expect(Token::Let).map_err(|e| {
+        parser.backtrack();
+        e.to_string()
+    })?;
+    parser.expect(Token::LParen)?;
+    let var = parse_variable(parser)?;
+    let body = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    let expr = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    Ok(Value::Let(var, Box::new(body), Box::new(expr)))
+}
+
+fn parse_application(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    let init = parse_expression(parser)?;
+    let mut exprs = Vec::new();
+    while let Ok(expr) = parse_expression(parser) {
+        exprs.push(expr);
+    }
+    if exprs.is_empty() {
+        return Err("Application needs two values".to_string());
+    }
+    parser.expect(Token::RParen)?;
+    let app: Value = exprs.iter().fold(init, |acc, expr| {
+        Value::App(Box::new(acc.clone()), Box::new(expr.clone()))
+    });
+    Ok(app.to_owned())
+}
+
+fn parse_value(parser: &mut Parser) -> Result<Value, String> {
+    let token = parser.tokens.get(parser.index).ok_or("Expected a value")?;
+    let val = parse_number(token)
+        .or_else(|_| parse_bool(token))
+        .or_else(|_| parse_symbol(token))?;
+    parser.next();
+    Ok(val)
+}
+
+fn tokenize(arg: &str) -> Vec<Token> {
+    let mut result = Vec::new();
+    let mut word = String::new();
+
+    for c in arg.chars() {
+        match c {
+            '(' => {
+                terminate(&mut result, &mut word);
+                result.push(Token::LParen)
+            }
+            ')' => {
+                terminate(&mut result, &mut word);
+                result.push(Token::RParen)
+            }
+            c if c.is_whitespace() => terminate(&mut result, &mut word),
+            c => word.push(c),
+        }
+    }
+    terminate(&mut result, &mut word);
+    result
+}
+
+fn terminate(result: &mut Vec<Token>, word: &mut String) {
+    if !word.is_empty() {
+        let w = word.clone();
+        if w == "lam" {
+            result.push(Token::Lambda);
+        } else if w == "def" {
+            result.push(Token::Define);
+        } else if w == "let" {
+            result.push(Token::Let);
+        } else {
+            result.push(Token::Word(w));
+        }
+        word.clear();
+    }
+}
+
+fn parse_symbol(token: &Token) -> Result<Value, String> {
+    match token {
+        Token::Word(s) => Ok(Value::Sym(s.clone())),
+        _ => Err(format!("Expected a symbol, got {:?}", token)),
+    }
+}
+
+fn parse_bool(token: &Token) -> Result<Value, String> {
+    match token {
+        Token::Word(s) => s
+            .parse::<bool>()
+            .map(Value::Bool)
+            .map_err(|e| e.to_string()),
+        _ => Err("Expected a boolean".to_string()),
+    }
+}
+
+fn parse_number(token: &Token) -> Result<Value, String> {
+    match token {
+        Token::Word(s) => s.parse::<i32>().map(Value::Num).map_err(|e| e.to_string()),
+        _ => Err("Expected an integer".to_string()),
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::parse_total;
+
+    use super::Token::*;
+    use super::Value;
+    use super::Value::*;
+    use super::{parse, tokenize};
+    use proptest::prelude::*;
+
+    proptest! {
+            #[test]
+            fn parse_integer_as_number(i in -1000i32..1000) {
+                let result = parse(&i.to_string());
+                assert_eq!(vec![Num(i)], result);
+            }
+
+    }
+
+    #[test]
+    fn parse_truth_values_as_booleans() {
+        assert_eq!(vec![Bool(true)], parse("true"));
+        assert_eq!(vec![Bool(false)], parse("false"));
+    }
+
+    #[test]
+    fn parse_identifiers_values_as_symbols() {
+        assert_eq!(vec![Sym("foo".to_string())], parse("foo"));
+    }
+
+    #[test]
+    fn ignores_whitespace() {
+        assert_eq!(vec![Sym("foo".to_string())], parse("  foo  \n\r"));
+        assert_eq!(vec![Num(-42)], parse("\n-42"));
+    }
+
+    #[test]
+    fn tokenize_several_values() {
+        assert_eq!(
+            vec![
+                Word("42".to_string()),
+                Word("foo".to_string()),
+                Word("true".to_string())
+            ],
+            tokenize("42 foo    \ntrue  ")
+        );
+    }
+
+    #[test]
+    fn tokenize_string_with_parens() {
+        assert_eq!(
+            vec![
+                LParen,
+                LParen,
+                RParen,
+                Word("42".to_string()),
+                RParen,
+                Word("true".to_string()),
+                LParen,
+            ],
+            tokenize("(   \r() 42)  \ntrue(  ")
+        );
+    }
+
+    #[test]
+    fn tokenize_lambda_symbol() {
+        assert_eq!(vec![Lambda, LParen,], tokenize("lam  ("));
+    }
+
+    #[test]
+    fn parse_application_of_two_values() {
+        assert_eq!(
+            vec![App(Box::new(Sym("foo".to_string())), Box::new(Num(42)))],
+            parse("(foo 42)")
+        );
+    }
+
+    #[test]
+    fn reject_application_of_single_value() {
+        assert_eq!(
+            Err("Application needs two values".to_string()),
+            parse_total("(foo )")
+        );
+    }
+
+    #[test]
+    fn desugar_application_of_more_than_two_values() {
+        assert_eq!(
+            vec![App(
+                Box::new(App(
+                    Box::new(App(Box::new(Sym("foo".to_string())), Box::new(Num(42)))),
+                    Box::new(Bool(true))
+                )),
+                Box::new(Sym("f".to_string()))
+            )],
+            parse("(foo 42 true f)")
+        );
+    }
+
+    #[test]
+    fn parse_abstraction() {
+        assert_eq!(
+            vec![Lam(
+                "x".to_string(),
+                Box::new(App(
+                    Box::new(Sym("x".to_string())),
+                    Box::new(Sym("x".to_string()))
+                ))
+            )],
+            parse("(lam x (x x))")
+        );
+    }
+
+    #[test]
+    fn desugar_abstraction_with_several_variables_into_nested_lambdas() {
+        assert_eq!(
+            vec![Lam(
+                "x".to_string(),
+                Box::new(Lam("y".to_string(), Box::new(Sym("y".to_string()))))
+            )],
+            parse("(lam (x y) y)")
+        );
+    }
+
+    #[test]
+    fn parse_definition() {
+        assert_eq!(
+            vec![Def("x".to_string(), Box::new(Num(12)))],
+            parse("(def x 12)")
+        );
+    }
+
+    #[test]
+    fn parse_multiple_values() {
+        assert_eq!(vec![Sym("foo".to_string()), Num(42)], parse("foo 42"));
+    }
+
+    #[test]
+    fn parse_let_expressions() {
+        assert_eq!(
+            vec![Value::Let(
+                "x".to_string(),
+                Box::new(Num(12)),
+                Box::new(Sym("x".to_string()))
+            )],
+            parse("(let (x 12) x)")
+        );
+    }
+
+    proptest! {
+            #[test]
+            fn parse_is_inverse_to_display(values in any::<Vec<Value>>()) {
+                let result : Vec<String> = values.iter().map(|v:&Value| v.to_string()).collect();
+                assert_eq!(values, result.iter().flat_map(|s| parse(s)).collect::<Vec<Value>>());
+            }
+    }
+}
diff --git a/lambda-calcul/rust/src/tester.rs b/lambda-calcul/rust/src/tester.rs
new file mode 100644
index 0000000..eb66d4e
--- /dev/null
+++ b/lambda-calcul/rust/src/tester.rs
@@ -0,0 +1,100 @@
+use serde::{Deserialize, Serialize};
+use std::{
+    fs::{self, read_to_string, File},
+    path::PathBuf,
+    process::{Command, Stdio},
+    time::Instant,
+};
+
+pub fn main() {
+    let mut args: Vec<String> = std::env::args().collect();
+    // name of the process to run
+    let proc = args.remove(1);
+    if args.len() > 1 {
+        let run = traverse(&args)
+            .and_then(|paths| run_test(&proc, &paths))
+            .expect("Failed to traverse directory");
+        println!("{}", serde_json::to_string_pretty(&run).unwrap());
+    } else {
+        println!(
+            r#"Usage: tester [options] <directory>+
+
+Options:
+    -p, --process   The process to run. If the given process is not a
+                    an absolute path, it will be resolved against the
+                    PATH environment variable.
+    -j, --json      Output the results in JSON format (default: false)
+    -h, --help      Display this help message
+    -v, --version   Display the version of the tester
+"#
+        );
+    }
+}
+
+fn traverse(args: &[String]) -> Result<Vec<PathBuf>, String> {
+    let mut files: Vec<PathBuf> = Vec::new();
+    for arg in args.iter().skip(1) {
+        let entries = fs::read_dir(arg).map_err(|e| e.to_string())?;
+        for entry in entries {
+            let dir = entry.map_err(|e| e.to_string())?;
+            let f = dir.metadata().map_err(|e| e.to_string())?;
+            if f.is_dir() {
+                files.push(dir.path());
+            }
+        }
+    }
+    Ok(files)
+}
+
+#[derive(Debug, Serialize, Deserialize)]
+pub enum TestResult {
+    TestSucceeded,
+    TestFailed(String, String),
+}
+
+#[derive(Debug, Serialize, Deserialize)]
+pub struct TestRun {
+    file: String,
+    test_result: TestResult,
+    duration: u128,
+}
+
+fn run_test(proc: &str, files: &Vec<PathBuf>) -> Result<Vec<TestRun>, String> {
+    let mut result = Vec::new();
+    for file in files {
+        let mut inp = file.clone();
+        let mut outp = file.clone();
+        inp.push("input");
+        outp.push("output");
+        let (test_result, duration) = run_test_case(proc, &inp, &outp)?;
+        result.push(TestRun {
+            file: inp.as_path().to_str().unwrap().to_string(),
+            test_result,
+            duration,
+        });
+    }
+    Ok(result)
+}
+
+fn run_test_case(
+    proc: &str,
+    inp: &std::path::PathBuf,
+    outp: &std::path::PathBuf,
+) -> Result<(TestResult, u128), String> {
+    let input = File::open(inp).map_err(|e| e.to_string())?;
+    let expected = read_to_string(outp).map_err(|e| e.to_string())?;
+    let start = Instant::now();
+
+    let actual = Command::new(proc)
+        .stdin(Stdio::from(input))
+        .output()
+        .map_err(|e| e.to_string())?;
+
+    let duration = (Instant::now() - start).as_millis();
+    if expected.as_bytes() == actual.stdout {
+        Ok((TestResult::TestSucceeded, duration))
+    } else {
+        let actual_string = String::from_utf8(actual.stdout).map_err(|e| e.to_string())?;
+        Ok((TestResult::TestFailed(expected, actual_string), duration))
+    }
+}
diff --git a/lambda-calcul/rust/src/web.rs b/lambda-calcul/rust/src/web.rs
new file mode 100644
index 0000000..3f8f056
--- /dev/null
+++ b/lambda-calcul/rust/src/web.rs
@@ -0,0 +1,899 @@
+use actix_web::{get, middleware::Logger, post, web, App, HttpResponse, HttpServer, Responder};
+use chrono::{DateTime, Utc};
+use clap::Parser;
+use handlebars::{DirectorySourceOptions, Handlebars};
+use log::info;
+use proptest::test_runner::{Config, RngAlgorithm, TestRng, TestRunner};
+use rand::Rng;
+use serde::{Deserialize, Serialize};
+use std::sync::Mutex;
+use std::time::Duration;
+use std::{collections::HashMap, sync::Arc};
+use tokio::task::{self, JoinHandle};
+use uuid::Uuid;
+
+use lambda::lambda::{eval_all, eval_whnf, generate_expr, generate_exprs, gensym, Environment};
+use lambda::parser::{parse, parse_total};
+
+#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
+struct Registration {
+    url: String,
+    name: String,
+}
+
+#[derive(Debug, Serialize, Deserialize, Clone)]
+struct ClientData {
+    name: String,
+    grade: u8,
+    last_query: DateTime<Utc>,
+    success: bool,
+}
+
+impl ClientData {
+    fn from(client: &Client) -> Self {
+        ClientData {
+            name: client.name.clone(),
+            grade: client.grade,
+            last_query: client
+                .results
+                .last()
+                .map_or(chrono::offset::Utc::now(), |q| q.timestamp),
+            success: client
+                .results
+                .last()
+                .map_or(false, |q| matches!(q.result, TestResult::TestSucceeded)),
+        }
+    }
+}
+
+#[derive(Debug, Serialize, Deserialize, Clone)]
+struct Leaderboard {
+    clients: Vec<ClientData>,
+}
+
+trait AppState: Send + Sync {
+    fn register(&mut self, registration: &Registration) -> RegistrationResult;
+    fn unregister(&mut self, url: &String);
+}
+
+#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
+enum RegistrationResult {
+    RegistrationSuccess { id: String, url: String },
+    UrlAlreadyRegistered { url: String },
+}
+
+#[derive(Debug, Clone)]
+struct Client {
+    id: Uuid,
+    name: String,
+    url: String,
+    grade: u8,
+    runner: TestRunner,
+    results: Vec<Test>,
+    delay: std::time::Duration,
+}
+
+#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
+struct Test {
+    timestamp: DateTime<Utc>,
+    result: TestResult,
+}
+
+#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
+enum TestResult {
+    TestFailed(String),
+    ErrorSendingTest(String),
+    TestSucceeded,
+}
+
+impl Client {
+    fn new(url: String, name: String, delay: Duration) -> Self {
+        let id = Uuid::new_v4();
+        let runner = TestRunner::new_with_rng(
+            Config::default(),
+            TestRng::from_seed(RngAlgorithm::XorShift, &id.to_bytes_le()),
+        );
+        Self {
+            id,
+            url,
+            name,
+            grade: 1,
+            runner,
+            results: Vec::new(),
+            delay,
+        }
+    }
+
+    fn time_to_next_test(&self) -> Duration {
+        self.delay
+    }
+
+    fn generate_expr(&mut self) -> (String, String) {
+        if self.grade >= 10 {
+            self.generate_exprs()
+        } else {
+            let input = generate_expr(self.grade.into(), &mut self.runner);
+            let expected = eval_whnf(&input, &mut Environment::new());
+            (input.to_string(), expected.to_string())
+        }
+    }
+
+    fn generate_exprs(&mut self) -> (String, String) {
+        let exprs = generate_exprs(self.grade.into(), &mut self.runner);
+        let input = exprs
+            .iter()
+            .map(|v| format!("{}", v))
+            .collect::<Vec<_>>()
+            .join("\n");
+        let expected = eval_all(&exprs);
+        (
+            input,
+            expected
+                .iter()
+                .map(|v| format!("{}", v))
+                .collect::<Vec<_>>()
+                .join("\n"),
+        )
+    }
+
+    /// Applies a `Test` to update client's state
+    fn apply(&mut self, test: &Test) {
+        match test.result {
+            TestResult::TestSucceeded => {
+                self.grade = self.grade.saturating_add(1);
+                self.delay = Duration::from_secs_f64(self.delay.as_secs_f64() * 0.8);
+                if self.delay.as_millis() < 500 {
+                    self.delay = Duration::from_millis(500);
+                }
+            }
+            TestResult::TestFailed(_) => {
+                self.delay = Duration::from_secs_f64(self.delay.as_secs_f64() * 1.2);
+                if self.delay.as_secs() > 30 {
+                    self.delay = Duration::from_secs(30);
+                }
+            }
+            _ => (),
+        }
+        self.results.push(test.clone());
+    }
+
+    fn check_result(&self, expected: &String, response: &Result<String, TestResult>) -> Test {
+        let result = match response {
+            Ok(expr) => {
+                let vals = parse(expr);
+                let actual = eval_all(&vals)
+                    .iter()
+                    .map(|v| format!("{}", v))
+                    .collect::<Vec<_>>()
+                    .join("\n");
+                if actual == *expected {
+                    TestResult::TestSucceeded
+                } else {
+                    TestResult::TestFailed(actual)
+                }
+            }
+            Err(res) => res.clone(),
+        };
+        Test {
+            result,
+            timestamp: chrono::offset::Utc::now(),
+        }
+    }
+}
+
+#[derive(Debug)]
+struct State {
+    base_duration: Duration,
+    clients: HashMap<String, (Arc<Mutex<Client>>, JoinHandle<()>)>,
+}
+
+impl State {
+    fn new() -> Self {
+        State::with_duration(Duration::from_secs(10))
+    }
+
+    fn with_duration(base_duration: Duration) -> Self {
+        Self {
+            base_duration,
+            clients: HashMap::new(),
+        }
+    }
+
+    fn client_events(&self, url: &String) -> usize {
+        let client = self.clients.get(url).unwrap().0.lock().unwrap();
+        client.results.len()
+    }
+}
+
+impl AppState for State {
+    fn register(&mut self, registration: &Registration) -> RegistrationResult {
+        if self.clients.contains_key(&registration.url) {
+            RegistrationResult::UrlAlreadyRegistered {
+                url: registration.url.clone(),
+            }
+        } else {
+            let client = Client::new(
+                registration.url.clone(),
+                registration.name.clone(),
+                self.base_duration,
+            );
+            let id = client.id.to_string();
+            let client_ref = Arc::new(Mutex::new(client));
+            // let it run in the background
+            // FIXME: should find a way to handle graceful termination
+            let client_handle = task::spawn(send_tests(client_ref.clone()));
+
+            self.clients.insert(
+                registration.url.clone(),
+                (client_ref.clone(), client_handle),
+            );
+
+            RegistrationResult::RegistrationSuccess {
+                id,
+                url: registration.url.clone(),
+            }
+        }
+    }
+
+    fn unregister(&mut self, url: &String) {
+        let (_, handle) = self.clients.get(url).unwrap();
+        handle.abort()
+    }
+}
+
+#[post("/register")]
+async fn register(
+    app_state: web::Data<Arc<Mutex<State>>>,
+    registration: web::Json<Registration>,
+) -> impl Responder {
+    let result = app_state.lock().unwrap().register(&registration);
+    match result {
+        RegistrationResult::RegistrationSuccess { .. } => HttpResponse::Ok().json(result),
+        RegistrationResult::UrlAlreadyRegistered { .. } => HttpResponse::BadRequest().json(result),
+    }
+}
+
+#[post("/eval")]
+async fn eval(input: String) -> impl Responder {
+    let exprs = parse_total(&input);
+    match exprs {
+        Ok(exprs) => {
+            let mut rng = rand::thread_rng();
+            if rng.gen_range(0..10) <= 2 {
+                return HttpResponse::Ok().body(gensym());
+            }
+            let output = eval_all(&exprs)
+                .iter()
+                .map(|v| format!("{}", v))
+                .collect::<Vec<_>>()
+                .join("\n");
+            HttpResponse::Ok().body(output.to_string())
+        }
+        Err(e) => HttpResponse::BadRequest().body(e.to_string()),
+    }
+}
+
+#[get("/leaderboard")]
+async fn leaderboard(
+    app_state: web::Data<Arc<Mutex<State>>>,
+    hb: web::Data<Handlebars<'_>>,
+) -> impl Responder {
+    let clients = &app_state.lock().unwrap().clients;
+    let mut client_data = vec![];
+    for client in clients.values() {
+        let client = client.0.lock().unwrap();
+        client_data.push(ClientData::from(&client));
+    }
+    client_data.sort_by(|a, b| b.grade.cmp(&a.grade));
+
+    let body = hb
+        .render(
+            "leaderboard",
+            &Leaderboard {
+                clients: client_data,
+            },
+        )
+        .unwrap();
+
+    web::Html::new(body)
+}
+
+#[derive(Parser, Debug)]
+struct Options {
+    /// The port to listen on
+    /// Defaults to 8080
+    #[arg(short, long, default_value_t = 8080)]
+    port: u16,
+    /// The host to bind the server to
+    /// Defaults to 127.0.0.1
+    #[arg(long, default_value = "127.0.0.1")]
+    host: String,
+}
+
+#[tokio::main]
+async fn main() -> std::io::Result<()> {
+    let options = Options::parse();
+    let app_state = Arc::new(Mutex::new(State::new()));
+
+    env_logger::init();
+    // Handlebars uses a repository for the compiled templates. This object must be
+    // shared between the application threads, and is therefore passed to the
+    // Application Builder as an atomic reference-counted pointer.
+    let mut handlebars = Handlebars::new();
+    handlebars
+        .register_templates_directory(
+            "./templates",
+            DirectorySourceOptions {
+                tpl_extension: ".html".to_owned(),
+                hidden: false,
+                temporary: false,
+            },
+        )
+        .unwrap();
+
+    HttpServer::new(move || {
+        App::new()
+            .wrap(Logger::default())
+            .app_data(web::Data::new(app_state.clone()))
+            .app_data(web::Data::new(handlebars.clone()))
+            .service(register)
+            .service(eval)
+            .service(leaderboard)
+    })
+    .bind((options.host, options.port))?
+    .run()
+    .await
+}
+
+fn get_test(client_m: &Mutex<Client>) -> (String, String, String) {
+    let mut client = client_m.lock().unwrap();
+    let (input, expected) = client.generate_expr();
+    (input, client.url.clone(), expected)
+}
+
+async fn send_tests(client_m: Arc<Mutex<Client>>) {
+    loop {
+        let sleep = sleep_time(&client_m);
+        tokio::time::sleep(sleep).await;
+        {
+            let (input, url, expected) = get_test(&client_m);
+
+            let response = send_test(&input, &url, sleep).await;
+
+            apply_result(&client_m, expected, response);
+        }
+    }
+}
+
+fn apply_result(client_m: &Mutex<Client>, expected: String, response: Result<String, TestResult>) {
+    let mut client = client_m.lock().unwrap();
+    let test = client.check_result(&expected, &response);
+    client.apply(&test);
+}
+
+fn sleep_time(client_m: &Arc<Mutex<Client>>) -> Duration {
+    client_m.lock().unwrap().time_to_next_test()
+}
+
+async fn send_test(input: &String, url: &String, timeout: Duration) -> Result<String, TestResult> {
+    info!("Sending {} to {}", input, url);
+    let body = input.clone();
+    let response = reqwest::Client::new()
+        .post(url)
+        .timeout(timeout)
+        .header("content-type", "text/plain")
+        .body(body)
+        .send()
+        .await;
+    match response {
+        Ok(response) => {
+            let body = response.text().await.unwrap();
+            info!("Response from {}: {}", url, body);
+            Ok(body)
+        }
+        Err(e) => {
+            info!("Error sending test: {}", e);
+            Err(TestResult::ErrorSendingTest(e.to_string()))
+        }
+    }
+}
+
+#[cfg(test)]
+mod app_tests {
+    use std::str::from_utf8;
+    use std::sync::Arc;
+
+    use actix_web::http::header::TryIntoHeaderValue;
+    use actix_web::{body, http::header::ContentType, middleware::Logger, test, App};
+    use lambda::ast::Value;
+
+    use super::*;
+
+    #[actix_web::test]
+    async fn post_registration_returns_success_with_unique_id() {
+        let state = Arc::new(Mutex::new(State::new()));
+        // FIXME should only be called once, move to setup
+        env_logger::init();
+
+        let app = test::init_service(
+            App::new()
+                .wrap(Logger::default())
+                .app_data(web::Data::new(state))
+                .service(register),
+        )
+        .await;
+        let url = "http://192.168.1.1".to_string();
+        let req = test::TestRequest::post()
+            .uri("/register")
+            .set_json(Registration {
+                url: url.clone(),
+                name: "foo".to_string(),
+            })
+            .insert_header(ContentType::json())
+            .to_request();
+
+        let resp = test::call_service(&app, req).await;
+
+        assert!(resp.status().is_success());
+
+        let body = resp.into_body();
+        let bytes = body::to_bytes(body).await;
+        match serde_json::from_slice::<RegistrationResult>(bytes.as_ref().unwrap()).unwrap() {
+            RegistrationResult::RegistrationSuccess { id: _, url: url1 } => assert_eq!(url1, url),
+            _ => panic!("Expected RegistrationSuccess, got {:?}", bytes.unwrap()),
+        };
+    }
+
+    #[actix_web::test]
+    async fn post_registration_returns_400_when_register_fails() {
+        let state = Arc::new(Mutex::new(State::new()));
+
+        let app = test::init_service(
+            App::new()
+                .wrap(Logger::default())
+                .app_data(web::Data::new(state.clone()))
+                .service(register),
+        )
+        .await;
+        let url = "http://192.168.1.1".to_string();
+        let registration = Registration {
+            url: url.clone(),
+            name: "foo".to_string(),
+        };
+
+        state.lock().unwrap().register(&registration);
+
+        let req = test::TestRequest::post()
+            .uri("/register")
+            .set_json(registration)
+            .insert_header(ContentType::json())
+            .to_request();
+
+        let resp = test::call_service(&app, req).await;
+
+        assert!(resp.status().is_client_error());
+        assert_eq!(
+            ContentType::json().try_into_value().unwrap(),
+            resp.headers().get("content-type").unwrap()
+        );
+    }
+
+    #[actix_web::test]
+    async fn post_expression_returns_evaluation() {
+        let app = test::init_service(App::new().wrap(Logger::default()).service(eval)).await;
+
+        let req = test::TestRequest::post()
+            .uri("/eval")
+            .set_payload("((lam (x y) x) 1 2)")
+            .insert_header(ContentType::plaintext())
+            .to_request();
+
+        let resp = test::call_service(&app, req).await;
+
+        assert!(resp.status().is_success());
+
+        let body = resp.into_body();
+        let bytes = body::to_bytes(body).await.unwrap();
+        assert_eq!(bytes, "1".to_string().into_bytes());
+    }
+
+    #[actix_web::test]
+    async fn post_expression_returns_multiple_evaluations() {
+        let app = test::init_service(App::new().wrap(Logger::default()).service(eval)).await;
+
+        let req = test::TestRequest::post()
+            .uri("/eval")
+            .set_payload("((lam (x y) x) 1 2)\n42")
+            .insert_header(ContentType::plaintext())
+            .to_request();
+
+        let resp = test::call_service(&app, req).await;
+
+        assert!(resp.status().is_success());
+
+        let body = resp.into_body();
+        let bytes = body::to_bytes(body).await.unwrap();
+        assert_eq!("1\n42".to_string().into_bytes(), bytes);
+    }
+
+    #[actix_web::test]
+    async fn get_leaderboard_returns_html_page_listing_clients_state() {
+        let app_state = Arc::new(Mutex::new(State::new()));
+        app_state.lock().unwrap().register(&Registration {
+            url: "http://1.2.3.4".to_string(),
+            name: "client1".to_string(),
+        });
+
+        let mut handlebars = Handlebars::new();
+        handlebars
+            .register_templates_directory(
+                "./templates",
+                DirectorySourceOptions {
+                    tpl_extension: ".html".to_owned(),
+                    hidden: false,
+                    temporary: false,
+                },
+            )
+            .unwrap();
+
+        let app = test::init_service(
+            App::new()
+                .wrap(Logger::default())
+                .app_data(web::Data::new(app_state.clone()))
+                .app_data(web::Data::new(handlebars.clone()))
+                .service(leaderboard),
+        )
+        .await;
+
+        let req = test::TestRequest::get().uri("/leaderboard").to_request();
+
+        let resp = test::call_service(&app, req).await;
+
+        assert!(resp.status().is_success());
+
+        let bytes = body::to_bytes(resp.into_body()).await.unwrap();
+        assert!(from_utf8(&bytes).unwrap().contains("client1"));
+    }
+
+    #[test]
+    async fn app_does_not_register_same_url_twice() {
+        let mut app_state = State::new();
+        let registration = Registration {
+            name: "foo".to_string(),
+            url: "http://1.2.3.4".to_string(),
+        };
+
+        app_state.register(&registration);
+        let result = app_state.register(&registration);
+
+        assert_eq!(
+            RegistrationResult::UrlAlreadyRegistered {
+                url: "http://1.2.3.4".to_string()
+            },
+            result
+        );
+    }
+
+    #[test]
+    async fn unregistering_registered_client_stops_tester_thread_from_sending_tests() {
+        let mut app_state = State::with_duration(Duration::from_millis(100));
+        let registration = Registration {
+            name: "foo".to_string(),
+            url: "http://1.2.3.4".to_string(),
+        };
+
+        let reg = app_state.register(&registration);
+        assert!(matches!(
+            reg,
+            RegistrationResult::RegistrationSuccess { .. }
+        ));
+
+        tokio::time::sleep(Duration::from_millis(500)).await;
+
+        app_state.unregister(&registration.url);
+
+        let grade_before = app_state.client_events(&registration.url);
+        tokio::time::sleep(Duration::from_millis(500)).await;
+        let grade_after = app_state.client_events(&registration.url);
+
+        assert_eq!(grade_before, grade_after);
+    }
+
+    fn client() -> Client {
+        Client::new(
+            "http://1.2.3.4".to_string(),
+            "foo".to_string(),
+            Duration::from_secs(10),
+        )
+    }
+
+    #[test]
+    async fn client_generates_constant_at_level_1() {
+        let mut client = client();
+
+        let (input, _) = client.generate_expr();
+
+        match parse(&input)[..] {
+            [Value::Num(_)] => (),
+            _ => panic!("Expected constant 3"),
+        }
+    }
+
+    #[test]
+    async fn client_generates_different_inputs_on_each_call() {
+        let mut client = client();
+
+        let (input1, _) = client.generate_expr();
+        let (input2, _) = client.generate_expr();
+
+        assert_ne!(input1, input2);
+    }
+
+    #[test]
+    async fn client_generates_ascii_variables_at_level_2() {
+        let mut client = client();
+        client.grade = 2;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            [Value::Sym(name)] => {
+                assert!(name.chars().all(|c| c.is_ascii_alphanumeric()));
+            }
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
+
+    #[test]
+    async fn client_generates_unicode_variables_at_level_3() {
+        let mut client = client();
+        client.grade = 3;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            [Value::Sym(_)] => (),
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
+
+    #[test]
+    async fn client_generates_binary_application_at_level_4() {
+        let mut client = client();
+        client.grade = 4;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            [Value::App(_, _)] => (),
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
+
+    #[test]
+    async fn client_generates_nested_applications_and_constants_at_level_5() {
+        let mut client = client();
+        client.grade = 5;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            [Value::App(_, _)] => (),
+            [Value::Sym(_)] => (),
+            [Value::Num(_)] => (),
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
+
+    #[test]
+    async fn client_generates_lambda_terms_at_level_6() {
+        let mut client = client();
+        client.grade = 6;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            [Value::Lam(_, _)] => (),
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
+
+    #[test]
+    async fn client_generates_application_with_lambda_terms_at_level_7() {
+        let mut client = client();
+        client.grade = 7;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match &parsed[..] {
+            [Value::App(t1, _)] if matches!(**t1, Value::Lam(_, _)) => (),
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
+
+    #[test]
+    async fn client_generates_applications_with_more_than_2_terms_at_level_8() {
+        let mut client = client();
+        client.grade = 8;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        if let [Value::App(_, _)] = &parsed[..] {
+            assert!(input.split(' ').count() >= 2)
+        }
+    }
+
+    #[test]
+    async fn client_generates_more_complex_terms_at_level_9() {
+        let mut client = client();
+        client.grade = 9;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+
+        assert!(!parsed.is_empty());
+    }
+
+    #[test]
+    async fn client_generates_multiple_terms_at_level_10() {
+        let mut client = client();
+        client.grade = 10;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+
+        assert!(!parsed.is_empty());
+    }
+
+    #[test]
+    async fn client_increases_grade_on_successful_test() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestSucceeded,
+        };
+
+        client.apply(&test);
+
+        assert_eq!(2, client.grade);
+    }
+
+    #[test]
+    async fn client_stores_test_results() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestSucceeded,
+        };
+
+        client.apply(&test);
+
+        assert_eq!(test, client.results.first().unwrap().clone());
+    }
+
+    #[test]
+    async fn client_returns_test_successful_if_result_match() {
+        let client = client();
+        let expected = "1".to_string();
+        let response = Ok("1".to_string());
+
+        let test = client.check_result(&expected, &response);
+
+        assert_eq!(TestResult::TestSucceeded, test.result);
+    }
+
+    #[test]
+    async fn client_returns_test_failed_given_result_do_not_match() {
+        let client = client();
+        let expected = "1".to_string();
+        let response = Ok("2".to_string());
+
+        let test = client.check_result(&expected, &response);
+
+        assert_eq!(TestResult::TestFailed("2".to_string()), test.result);
+    }
+
+    #[test]
+    async fn client_does_not_increase_grade_on_failed_test() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestFailed("2".to_string()),
+        };
+
+        client.apply(&test);
+
+        assert_eq!(1, client.grade);
+    }
+
+    #[test]
+    async fn client_starts_delay_to_next_test_at_10s() {
+        let client = client();
+
+        let delay = client.time_to_next_test();
+
+        assert_eq!(std::time::Duration::from_secs(10), delay);
+    }
+
+    #[test]
+    async fn client_increases_delay_to_next_upon_failed_test() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestFailed("2".to_string()),
+        };
+        let delay_before = client.time_to_next_test();
+
+        client.apply(&test);
+
+        assert!(delay_before < client.time_to_next_test());
+    }
+
+    #[test]
+    async fn client_increases_delay_to_maximum_of_30s() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestFailed("2".to_string()),
+        };
+
+        for _ in 0..100 {
+            client.apply(&test);
+        }
+
+        assert_eq!(Duration::from_secs(30), client.time_to_next_test());
+    }
+
+    #[test]
+    async fn client_score_cannot_go_beyond_255() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestSucceeded,
+        };
+
+        for _ in 0..256 {
+            client.apply(&test);
+        }
+
+        assert_eq!(255, client.grade);
+    }
+
+    #[test]
+    async fn client_decreases_delay_to_next_upon_successful_test() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestSucceeded,
+        };
+        let delay_before = client.time_to_next_test();
+
+        client.apply(&test);
+
+        assert!(delay_before > client.time_to_next_test());
+    }
+
+    #[test]
+    async fn client_decreases_delay_to_minimum_of_500ms() {
+        let mut client = client();
+        let test = Test {
+            timestamp: chrono::offset::Utc::now(),
+            result: TestResult::TestSucceeded,
+        };
+
+        for _ in 0..100 {
+            client.apply(&test);
+        }
+
+        assert_eq!(Duration::from_millis(500), client.time_to_next_test());
+    }
+}