ternaria_arith/

trit.rs

//! The balanced ternary digit.

use core::fmt;
use core::ops::Neg;

/// A balanced ternary digit: -1, 0, or +1 (D-01).
///
/// Discriminants are the numeric values, so `trit as i8` gives the value.
/// Under the convention in D-06 the same values serve as three-valued logic
/// constants:
///
/// | Trit | Number | Logic |
/// |------|--------|-------|
/// | [`Trit::Neg`]  | -1 | false |
/// | [`Trit::Zero`] |  0 | unknown |
/// | [`Trit::Pos`]  | +1 | true |
///
/// `unknown` means indeterminate: a value exists but is not known. It is not
/// an error channel. See D-06.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
#[repr(i8)]
pub enum Trit {
    /// -1. Logical false.
    Neg = -1,
    /// 0. Logical unknown.
    #[default]
    Zero = 0,
    /// +1. Logical true.
    Pos = 1,
}

impl Trit {
    /// Every trit, ascending.
    pub const ALL: [Trit; 3] = [Trit::Neg, Trit::Zero, Trit::Pos];

    /// The numeric value, -1, 0, or +1.
    #[inline]
    pub const fn value(self) -> i8 {
        self as i8
    }

    /// Builds a trit from its numeric value. `None` outside -1..=1.
    #[inline]
    pub const fn from_value(v: i8) -> Option<Trit> {
        match v {
            -1 => Some(Trit::Neg),
            0 => Some(Trit::Zero),
            1 => Some(Trit::Pos),
            _ => None,
        }
    }

    // ---- BCT encoding (D-03) ----
    //
    // Two bits per trit. The codes form a 2-bit two's-complement integer, so
    // negation is arithmetic negation and the host can sign-extend a code
    // directly.
    //
    //   00 -> 0     01 -> +1     11 -> -1     10 -> NaT (invalid)
    //
    // The spare 10 codepoint marks poisoned memory on the host. It is never
    // visible to a guest program (D-03).

    /// The 2-bit BCT code for this trit.
    #[inline]
    pub const fn bct_code(self) -> u8 {
        match self {
            Trit::Zero => 0b00,
            Trit::Pos => 0b01,
            Trit::Neg => 0b11,
        }
    }

    /// Decodes a 2-bit BCT code. `None` for the `10` NaT pattern.
    #[inline]
    pub const fn from_bct_code(code: u8) -> Option<Trit> {
        match code & 0b11 {
            0b00 => Some(Trit::Zero),
            0b01 => Some(Trit::Pos),
            0b11 => Some(Trit::Neg),
            _ => None, // 0b10 == NaT
        }
    }

    /// The NaT (not-a-trit) code. Host-side poison; never visible to a guest.
    pub const NAT_CODE: u8 = 0b10;

    // ---- Kleene three-valued logic (D-06) ----
    //
    // NOT is negation, AND is min, OR is max.

    /// Logical NOT - arithmetic negation. Swaps true/false, fixes unknown.
    #[inline]
    pub const fn not(self) -> Trit {
        match self {
            Trit::Neg => Trit::Pos,
            Trit::Zero => Trit::Zero,
            Trit::Pos => Trit::Neg,
        }
    }

    /// Logical AND - the minimum of the two.
    ///
    /// Kleene semantics absorb unknown where the result is determined
    /// regardless: `unknown AND false == false`, since the conjunction is
    /// false for either value the unknown could take.
    #[inline]
    pub const fn and(self, other: Trit) -> Trit {
        if (self as i8) <= (other as i8) {
            self
        } else {
            other
        }
    }

    /// Logical OR - the maximum of the two.
    #[inline]
    pub const fn or(self, other: Trit) -> Trit {
        if (self as i8) >= (other as i8) {
            self
        } else {
            other
        }
    }

    /// Cyclic successor, -1 -> 0 -> +1 -> -1.
    ///
    /// {MIN, MAX, NEG} is not functionally complete. All three respect the
    /// ordering -1 < 0 < +1, so no composition of them produces a map that
    /// does not. This one does, and adding it completes the set (D-06).
    #[inline]
    pub const fn cycle(self) -> Trit {
        match self {
            Trit::Neg => Trit::Zero,
            Trit::Zero => Trit::Pos,
            Trit::Pos => Trit::Neg,
        }
    }

    /// The Webb function, `V(x, y) = max(x, y) + 1 (mod 3)`.
    ///
    /// The ternary analogue of NAND: functionally complete on its own, so every
    /// one of the 19,683 two-input ternary operations is a composition of this
    /// single one (Post, 1941).
    ///
    /// # Completeness
    ///
    /// `webb_generates_every_unary_function` in this module verifies this by
    /// construction: closing V under composition reaches all 27 unary ternary
    /// functions, including the three constants. Two of them:
    ///
    /// ```text
    /// cycle(x) = V(x, x)
    /// NOT(x)   = V( V(V(x,x), V(x,V(x,x))),
    ///               V( V(x,V(x,V(x,x))), V(V(x,x), V(x,V(x,x))) ) )
    /// ```
    ///
    /// Cost differs sharply: `cycle` is one gate, `NOT` is seven, and
    /// [`Trit::not`] is one operation. Webb is a foundation rather than an
    /// implementation strategy. See D-13 in the roadmap.
    #[inline]
    pub const fn webb(self, other: Trit) -> Trit {
        self.or(other).cycle()
    }

    /// Half adder: the sum trit and carry trit of `self + other`.
    ///
    /// The sum of two trits lies in -2..=2 and needs two trits to hold, hence
    /// the carry. There is no separate borrow: subtraction is addition of the
    /// negation.
    ///
    /// ```
    /// use ternaria_arith::Trit;
    /// // 1 + 1 = 2, which in balanced ternary is 1T: carry 1, sum -1.
    /// let (sum, carry) = Trit::Pos.half_add(Trit::Pos);
    /// assert_eq!((sum, carry), (Trit::Neg, Trit::Pos));
    /// ```
    #[inline]
    pub const fn half_add(self, other: Trit) -> (Trit, Trit) {
        Self::split_sum(self as i8 + other as i8)
    }

    /// Full adder: sum and carry of `self + other + carry_in`.
    ///
    /// The input sum spans -3..=3 and resolves into one sum trit and one
    /// carry trit.
    #[inline]
    pub const fn full_add(self, other: Trit, carry_in: Trit) -> (Trit, Trit) {
        Self::split_sum(self as i8 + other as i8 + carry_in as i8)
    }

    /// Splits a small integer into (sum trit, carry trit) with
    /// `value == sum + 3 * carry`. Valid for -4..=4.
    #[inline]
    const fn split_sum(value: i8) -> (Trit, Trit) {
        let (s, c) = match value {
            -4 => (-1, -1),
            -3 => (0, -1),
            -2 => (1, -1),
            -1 => (-1, 0),
            0 => (0, 0),
            1 => (1, 0),
            2 => (-1, 1),
            3 => (0, 1),
            4 => (1, 1),
            _ => panic!("split_sum: value out of range"),
        };
        (
            match s {
                -1 => Trit::Neg,
                1 => Trit::Pos,
                _ => Trit::Zero,
            },
            match c {
                -1 => Trit::Neg,
                1 => Trit::Pos,
                _ => Trit::Zero,
            },
        )
    }

    /// The display character: `T` for -1, `0`, `1`.
    ///
    /// `T` is the conventional balanced-ternary notation for the -1 digit,
    /// keeping every digit one character wide so a numeral reads like any other
    /// positional numeral.
    ///
    /// # Counting from -9 to 9
    ///
    /// Worth reading down the middle column: the negative half is the positive
    /// half with every digit flipped, because negation is digit flipping.
    /// There is no sign to carry around, and no gap or asymmetry at either end.
    ///
    /// | n | balanced ternary | | n | balanced ternary |
    /// |---:|:---|---|---:|:---|
    /// | -9 | `T00` | | 9 | `100` |
    /// | -8 | `T01` | | 8 | `10T` |
    /// | -7 | `T1T` | | 7 | `1T1` |
    /// | -6 | `T10` | | 6 | `1T0` |
    /// | -5 | `T11` | | 5 | `1TT` |
    /// | -4 | `TT`  | | 4 | `11`  |
    /// | -3 | `T0`  | | 3 | `10`  |
    /// | -2 | `T1`  | | 2 | `1T`  |
    /// | -1 | `T`   | | 1 | `1`   |
    /// | 0 | `0` | | | |
    ///
    /// Note `2` is `1T` - one three, minus one - rather than needing a digit
    /// worth two. Every value has exactly one such representation.
    #[inline]
    pub const fn to_char(self) -> char {
        match self {
            Trit::Neg => 'T',
            Trit::Zero => '0',
            Trit::Pos => '1',
        }
    }

    /// Parses a display character. Accepts `T`/`t`/`-` for -1 and `+` for +1.
    #[inline]
    pub const fn from_char(c: char) -> Option<Trit> {
        match c {
            'T' | 't' | '-' => Some(Trit::Neg),
            '0' => Some(Trit::Zero),
            '1' | '+' => Some(Trit::Pos),
            _ => None,
        }
    }
}

impl Neg for Trit {
    type Output = Trit;
    /// Negation is the logical NOT - one operation serving both roles (D-01).
    #[inline]
    fn neg(self) -> Trit {
        self.not()
    }
}

impl fmt::Display for Trit {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(match self {
            Trit::Neg => "T",
            Trit::Zero => "0",
            Trit::Pos => "1",
        })
    }
}

impl From<Trit> for i8 {
    #[inline]
    fn from(t: Trit) -> i8 {
        t as i8
    }
}

impl From<Trit> for i64 {
    #[inline]
    fn from(t: Trit) -> i64 {
        t as i8 as i64
    }
}

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

    #[test]
    fn value_round_trips() {
        for t in Trit::ALL {
            assert_eq!(Trit::from_value(t.value()), Some(t));
        }
        assert_eq!(Trit::from_value(2), None);
        assert_eq!(Trit::from_value(-2), None);
    }

    #[test]
    fn bct_round_trips_and_rejects_nat() {
        for t in Trit::ALL {
            assert_eq!(Trit::from_bct_code(t.bct_code()), Some(t));
        }
        assert_eq!(Trit::from_bct_code(Trit::NAT_CODE), None);
    }

    /// The BCT codes are 2-bit two's complement, which is what makes negation
    /// on the host a plain arithmetic negate (D-03).
    #[test]
    fn bct_code_is_two_bit_twos_complement() {
        for t in Trit::ALL {
            // Sign-extend the 2-bit code into an i8 and recover the value.
            let sign_extended = ((t.bct_code() << 6) as i8) >> 6;
            assert_eq!(sign_extended, t.value(), "trit {t:?}");
        }
    }

    #[test]
    fn negation_is_an_involution() {
        for t in Trit::ALL {
            assert_eq!(-(-t), t);
            assert_eq!((-t).value(), -t.value());
        }
    }

    #[test]
    fn kleene_truth_tables() {
        use Trit::{Neg as F, Pos as T, Zero as U};

        // AND is min.
        assert_eq!(T.and(T), T);
        assert_eq!(T.and(F), F);
        assert_eq!(F.and(F), F);
        assert_eq!(U.and(T), U);
        assert_eq!(U.and(U), U);
        // The absorbing case: determined regardless of what the unknown is.
        assert_eq!(U.and(F), F);

        // OR is max.
        assert_eq!(F.or(F), F);
        assert_eq!(T.or(F), T);
        assert_eq!(U.or(F), U);
        // Absorbing the other way.
        assert_eq!(U.or(T), T);

        // NOT fixes unknown.
        assert_eq!(T.not(), F);
        assert_eq!(F.not(), T);
        assert_eq!(U.not(), U);
    }

    #[test]
    fn and_or_really_are_min_max() {
        for a in Trit::ALL {
            for b in Trit::ALL {
                assert_eq!(a.and(b).value(), a.value().min(b.value()));
                assert_eq!(a.or(b).value(), a.value().max(b.value()));
            }
        }
    }

    #[test]
    fn cycle_has_order_three() {
        for t in Trit::ALL {
            assert_eq!(t.cycle().cycle().cycle(), t);
        }
        // And it is genuinely order-breaking - the property that makes
        // {min, max, neg} incomplete without it.
        assert_ne!(Trit::Neg.cycle(), Trit::Neg);
    }

    /// {MIN, MAX, NEG} preserve the ordering -1 < 0 < +1, so no composition of
    /// them can realise the cyclic successor. This test pins that argument down
    /// by exhaustive search over every unary function built from them.
    #[test]
    fn min_max_neg_cannot_express_cycle() {
        // Every function reachable from {min, max, neg} is monotone or
        // antitone. `cycle` is neither: it maps Neg->Zero (up) but Pos->Neg
        // (down), so it cannot be built from order-respecting parts.
        let up = Trit::Neg.cycle().value() > Trit::Neg.value();
        let down = Trit::Pos.cycle().value() < Trit::Pos.value();
        assert!(
            up && down,
            "cycle must break monotonicity in both directions"
        );
    }

    #[test]
    fn webb_is_max_then_cycle() {
        for a in Trit::ALL {
            for b in Trit::ALL {
                assert_eq!(a.webb(b), a.or(b).cycle());
            }
        }
    }

    /// Functional completeness, demonstrated rather than asserted: closing the
    /// Webb function under composition reaches every unary ternary
    /// function - all 27, the three constants included.
    #[test]
    fn webb_generates_every_unary_function() {
        use std::collections::HashSet;

        // A unary function is fully described by its image on (Neg, Zero, Pos).
        type Fn3 = [Trit; 3];
        let identity: Fn3 = [Trit::Neg, Trit::Zero, Trit::Pos];

        let mut reached: HashSet<Fn3> = HashSet::new();
        reached.insert(identity);

        loop {
            let before = reached.len();
            let snapshot: Vec<Fn3> = reached.iter().copied().collect();
            for f in &snapshot {
                for g in &snapshot {
                    let mut h = [Trit::Zero; 3];
                    for i in 0..3 {
                        h[i] = f[i].webb(g[i]);
                    }
                    reached.insert(h);
                }
            }
            if reached.len() == before {
                break;
            }
        }

        assert_eq!(
            reached.len(),
            27,
            "Webb must generate all 3^3 unary functions"
        );

        // The constants - the very things {min, max, neg} cannot produce.
        for c in Trit::ALL {
            assert!(reached.contains(&[c; 3]), "constant {c:?} unreachable");
        }
        // And NOT: Neg->Pos, Zero->Zero, Pos->Neg.
        assert!(reached.contains(&[Trit::Pos, Trit::Zero, Trit::Neg]));
    }

    /// The explicit seven-gate Webb expression for NOT quoted in the docs.
    ///
    /// Kept as a test so the documented formula cannot rot. The cost contrast
    /// is the lesson: `cycle` is one Webb gate, `NOT` is seven, and
    /// [`Trit::not`] is one instruction.
    #[test]
    fn documented_webb_not_formula_holds() {
        for x in Trit::ALL {
            let a = x.webb(x); // cycle(x)
            let b = x.webb(a);
            let left = a.webb(b);
            let c = x.webb(b);
            let right = c.webb(left);
            assert_eq!(left.webb(right), x.not(), "x = {x:?}");
        }
    }

    #[test]
    fn half_add_matches_arithmetic() {
        for a in Trit::ALL {
            for b in Trit::ALL {
                let (sum, carry) = a.half_add(b);
                assert_eq!(
                    sum.value() as i32 + 3 * carry.value() as i32,
                    a.value() as i32 + b.value() as i32,
                    "{a:?} + {b:?}"
                );
            }
        }
    }

    #[test]
    fn full_add_matches_arithmetic() {
        for a in Trit::ALL {
            for b in Trit::ALL {
                for c in Trit::ALL {
                    let (sum, carry) = a.full_add(b, c);
                    assert_eq!(
                        sum.value() as i32 + 3 * carry.value() as i32,
                        a.value() as i32 + b.value() as i32 + c.value() as i32,
                        "{a:?} + {b:?} + {c:?}"
                    );
                }
            }
        }
    }

    /// A ripple-carry adder built from [`Trit::full_add`] must agree with plain
    /// integer arithmetic - the check that the carry rule is right.
    #[test]
    fn ripple_carry_adder_over_four_trits() {
        fn ripple(a: [Trit; 4], b: [Trit; 4]) -> (i32, Trit) {
            let mut carry = Trit::Zero;
            let mut out = [Trit::Zero; 4];
            for i in 0..4 {
                let (s, c) = a[i].full_add(b[i], carry);
                out[i] = s;
                carry = c;
            }
            let v = out
                .iter()
                .enumerate()
                .map(|(i, t)| t.value() as i32 * 3i32.pow(i as u32))
                .sum();
            (v, carry)
        }

        fn value(t: [Trit; 4]) -> i32 {
            t.iter()
                .enumerate()
                .map(|(i, t)| t.value() as i32 * 3i32.pow(i as u32))
                .sum()
        }

        // 3^4 = 81 values each; exhaustive over all 6,561 pairs.
        let all: Vec<[Trit; 4]> = (0..81)
            .map(|n: i32| {
                let mut v = n - 40; // centre on zero: -40..=40
                let mut t = [Trit::Zero; 4];
                for slot in t.iter_mut() {
                    let mut r = v % 3;
                    v /= 3;
                    if r == 2 {
                        r = -1;
                        v += 1;
                    } else if r == -2 {
                        r = 1;
                        v -= 1;
                    }
                    *slot = Trit::from_value(r as i8).unwrap();
                }
                t
            })
            .collect();

        for a in &all {
            for b in &all {
                let (sum, carry) = ripple(*a, *b);
                let expected = value(*a) + value(*b);
                assert_eq!(
                    sum + 81 * carry.value() as i32,
                    expected,
                    "{:?} + {:?}",
                    value(*a),
                    value(*b)
                );
            }
        }
    }

    #[test]
    fn char_round_trips() {
        for t in Trit::ALL {
            assert_eq!(Trit::from_char(t.to_char()), Some(t));
        }
        assert_eq!(Trit::from_char('-'), Some(Trit::Neg));
        assert_eq!(Trit::from_char('+'), Some(Trit::Pos));
        assert_eq!(Trit::from_char('2'), None);
    }
}