csa-rhdl 0.1.0

Carry-save adder compressor trees composed via comp-cat-rs, with hdl-cat backend
Documentation 
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

//! Interpret a free-category [`Path`] over a [`TreeGraph`] as a
//! composed [`CircuitArrow`].
//!
//! Uses [`comp_cat_rs::collapse::free_category::interpret`] — the
//! universal property of the free category — to extend the
//! [`TreeMorphism`] graph morphism to a functor.

use comp_cat_rs::collapse::free_category::{interpret, Path};

use crate::category::arrow::CircuitArrow;
use crate::category::graph::{TreeGraph, TreeMorphism};
use crate::shape::Shape;

/// Interpret a `TreeGraph` path as a composed circuit morphism.
///
/// The identity path interprets to [`CircuitArrow::identity`] on the
/// path's source vertex shape.  A non-empty path folds its edges
/// via series composition.
#[must_use]
pub fn interpret_tree(graph: &TreeGraph, path: &Path) -> CircuitArrow {
    let morphism = TreeMorphism::new(graph);
    interpret::<TreeGraph, _>(
        &morphism,
        path,
        |shape: &Shape| CircuitArrow::identity(*shape),
        CircuitArrow::compose_unchecked,
    )
}

#[cfg(test)]
mod tests {
    use super::interpret_tree;
    use crate::category::graph::TreeGraph;
    use crate::shape::Shape;
    use comp_cat_rs::collapse::free_category::{Edge, FreeCategoryError, Graph, Path};

    fn full_path(g: &TreeGraph) -> Result<Path, FreeCategoryError> {
        (0..g.edge_count()).try_fold(
            Path::singleton(g, Edge::new(0))?,
            |acc, i| match i {
                0 => Ok(acc),
                _ => acc.compose(Path::singleton(g, Edge::new(i))?),
            },
        )
    }

    #[test]
    fn identity_path_interprets_to_id_arrow() {
        let g = TreeGraph::build(2, 8);
        let p = Path::identity(comp_cat_rs::collapse::free_category::Vertex::new(0));
        let arrow = interpret_tree(&g, &p);
        assert_eq!(arrow.source(), Some(Shape::new(2, 8)));
    }

    #[test]
    fn nine_op_path_interprets_to_composed_chain() -> Result<(), FreeCategoryError> {
        let g = TreeGraph::build(9, 16);
        let p = full_path(&g)?;
        let arrow = interpret_tree(&g, &p);
        assert_eq!(arrow.source(), Some(Shape::new(9, 16)));
        assert_eq!(arrow.target(), Some(Shape::new(2, 20)));
        Ok(())
    }
}