summaryrefslogtreecommitdiff
path: root/lambda-calcul/rust/src
diff options
context:
space:
mode:
Diffstat (limited to 'lambda-calcul/rust/src')
-rw-r--r--lambda-calcul/rust/src/ast.rs117
-rw-r--r--lambda-calcul/rust/src/io.rs73
-rw-r--r--lambda-calcul/rust/src/lambda.rs292
-rw-r--r--lambda-calcul/rust/src/lib.rs4
-rw-r--r--lambda-calcul/rust/src/main.rs18
-rw-r--r--lambda-calcul/rust/src/parser.rs392
-rw-r--r--lambda-calcul/rust/src/tester.rs100
-rw-r--r--lambda-calcul/rust/src/web.rs899
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());
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-06 03:31:48 +0000