knube 0.2.0

//! Simple expression construction.
//!
//! This module defines an expression type that is able to describe simple expressions composed of
//! constants, variables, and applications.
//!
//! # Usage
//!
//! To construct expressions, the API provides the functions `cst`, `var`, and `app` which
//! construct constants, variables, and applications respectively. The corresponding `Exp` enum
//! variants can be used directly but require a call to `Box::new` to construct each value of the
//! `App` tuple.
//!
//! These functions allow the expressions to be constructed similarly to how they would be in
//! functional languages like OCaml, for example:
//!
//! ```
//! use knube::exp::{cst, var, app};
//!
//! let e = app(app(cst("f"), cst("a")), var("x"));
//! ```
//!
//! Which would translate to the expression `((f a) x)` (OCaml style) or `f(a)(x)` (Rust style).
//! This crate uses the Rust style to display expressions.

/// An alias to make functions signatures returning expressions easier to read and write.
pub type ExpBox = Box<Exp>;

/// A simple expression, as described in the module documentation.
///
/// This recursive form is what we study in class. Other implementations might be completely
/// different.
#[derive(Eq, Clone, Debug)]
pub enum Exp {
    Cst(&'static str), // Keeping string lifetimes static for simplicity.
    Var(&'static str),
    App(ExpBox, ExpBox),
}

/// Constructs a constant with the given name.
///
/// Constant names are usually single letters close to the beginning of the alphabet, i.e. `a`,
/// `b`, `f`, etc.
pub fn cst(name: &'static str) -> ExpBox {
    Exp::new(Exp::Cst(name))
}

/// Constructs a variable with the given name. Variables are just identifiers, they don't hold any
/// value.
///
/// Variable names, similarly to constant names, are usually a single letter. However their name is
/// usually a letter close to the end of the alphabet, i.e. `x`, `y`, etc.
pub fn var(name: &'static str) -> ExpBox {
    Exp::new(Exp::Var(name))
}

/// Constructs an application with the given left and right expressions.
///
/// Applications would translate to functions calls, i.e. if `left` is `f` and `right` is `x`, then
/// `app(left, right)` is `(f x)` or `f(x)` depending on the style.
pub fn app(left: ExpBox, right: ExpBox) -> ExpBox {
    Exp::new(Exp::App(left, right))
}

impl Exp {
    fn new(exp: Exp) -> ExpBox {
        Box::new(exp)
    }

    /// Computes the size of the given expression.
    ///
    /// The size of an expression is equal to the number of constants it contains added to the
    /// number of variables it contains.
    pub fn size(&self) -> usize {
        match self {
            Exp::Cst(_) | Exp::Var(_) => 1,
            Exp::App(left, right) => left.size() + right.size(),
        }
    }
}

use std::cmp::PartialEq;

/// The comparison is done as follows:
///
/// - `Cst(a) == Cst(b)` *iff* `a == b`, where `a` and `b` are strings.
/// - `Var(a) == Var(b)` *iff* `a == b`, where `a` and `b` are strings.
/// - `App(a, b) == App(c, d)` *iff* `(a == c) && (b == d)`, where `a`, `b`, `c`, and `d` are
/// expressions.
///
/// This definition of the equality operator matches the behavior of OCaml's sum type comparison.
impl PartialEq for Exp {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            // Only compare the name for constants and variables.
            (Exp::Cst(name_l), Exp::Cst(name_r)) | (Exp::Var(name_l), Exp::Var(name_r)) => {
                name_l == name_r
            }
            // Recurse for applications.
            (Exp::App(left_l, right_l), Exp::App(left_r, right_r)) => {
                (left_l == left_r) && (right_l == right_r)
            }
            _ => false,
        }
    }
}

use std::fmt;

/// Formats the expressions using the Rust style of expressions.
///
/// The expressions are formatted as follows:
///
/// - Variables and constants are replaced by their name. For example `Cst("a")` becomes `a`
/// and `Cst("x")` becomes `x`.
/// - Applications are replaced by a function call. For example `App(Cst("f"), Var("x"))` becomes `f(x)`.
impl fmt::Display for Exp {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Exp::Cst(name) => write!(f, "{}", name),
            Exp::Var(name) => write!(f, "{}", name),
            Exp::App(left, right) => write!(f, "{}({})", left, right), // Write recursively.
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn exp_display_format() {
        let e = app(cst("f"), cst("a"));
        assert_eq!("f(a)", format!("{}", e));
    }

    #[test]
    fn exp_size() {
        let e = app(cst("f"), cst("a"));
        assert_eq!(2, e.size());
    }
}