1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

//! 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(Debug)]
pub enum Exp {
    Cst(&'static str),
    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)
    }
}

use std::fmt;

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.
        }
    }
}