open_hypergraphs/strict/
eval.rs

1//! An array-backend-agnostic evaluator
2//!
3use crate::array::*;
4use crate::finite_function::*;
5use crate::indexed_coproduct::*;
6use crate::semifinite::*;
7
8use crate::strict::layer::{converse, layer};
9use crate::strict::open_hypergraph::*;
10
11use num_traits::Zero;
12use std::default::Default;
13
14// Given a "layering function" `f : N → K` which maps each operation `n ∈ N` into some layer `k ∈
15// K`,
16// return the converse relation `r : K → N*` giving the list of operations in each layer as a list
17// of `FiniteFunction`.
18fn layer_function_to_layers<K: ArrayKind>(f: FiniteFunction<K>) -> Vec<FiniteFunction<K>>
19where
20    K::Type<K::I>: NaturalArray<K>,
21    K::I: Into<usize> + From<usize>,
22{
23    let c = converse(&IndexedCoproduct::elements(f));
24    c.into_iter().collect()
25}
26
27/// Evaluate an acyclic open hypergraph `f` thought of as a function using some specified input
28/// values `s`, and a function `apply` which maps a list of operations and their inputs to their
29/// outputs.
30pub fn eval<K: ArrayKind, O, A, T: Default>(
31    f: &OpenHypergraph<K, O, A>,
32    s: K::Type<T>,
33    apply: impl Fn(
34        SemifiniteFunction<K, A>,
35        IndexedCoproduct<K, SemifiniteFunction<K, T>>,
36    ) -> IndexedCoproduct<K, SemifiniteFunction<K, T>>,
37) -> Option<K::Type<T>>
38where
39    K::I: Into<usize> + From<usize>,
40    K::Type<K::I>: NaturalArray<K>,
41    K::Type<T>: Array<K, T>,
42    K::Type<O>: Array<K, O>,
43    K::Type<A>: Array<K, A>,
44{
45    let (order, unvisited) = layer(f);
46    let layering = layer_function_to_layers(order);
47
48    // Check that max of 'unvisited' is 0: i.e., no unvisited nodes.
49    // TODO: this has to evaluate the whole array, when it could just use 'any'.
50    if unvisited.max().unwrap_or(K::I::zero()) == K::I::zero() {
51        let (_, outputs) = eval_order(f, s, layering, apply);
52        Some(outputs)
53    } else {
54        None
55    }
56}
57
58// Evaluate an acyclic open hypergraph using a specified order of operations.
59fn eval_order<K: ArrayKind, O, A, T: Default>(
60    // The term to evaluate
61    f: &OpenHypergraph<K, O, A>,
62    // Source wire inputs
63    s: K::Type<T>,
64    // A chosen order of operations
65    // TODO: this should be an *iterator* over arrays?
66    //order: &IndexedCoproduct<K, FiniteFunction<K>>,
67    order: Vec<FiniteFunction<K>>,
68    apply: impl Fn(
69        SemifiniteFunction<K, A>,
70        IndexedCoproduct<K, SemifiniteFunction<K, T>>,
71    ) -> IndexedCoproduct<K, SemifiniteFunction<K, T>>,
72) -> (K::Type<T>, K::Type<T>)
73where
74    K::Type<K::I>: NaturalArray<K>,
75    K::Type<T>: Array<K, T>,
76    K::Type<O>: Array<K, O>,
77    K::Type<A>: Array<K, A>,
78{
79    // Create memory prefilled with default data
80    let mut mem: SemifiniteFunction<K, T> =
81        SemifiniteFunction::new(K::Type::<T>::fill(T::default(), f.h.w.len()));
82
83    // Overwrite input locations with values in s.
84    mem.0.scatter_assign(&f.s.table, s);
85
86    for op_ix in order {
87        // Compute *labels* of operations to pass to `apply`.
88        let op_labels = (&op_ix >> &f.h.x).unwrap();
89
90        // Get the wire indices and values which are inputs to the operations in op_ix.
91        let input_indexes = f.h.s.map_indexes(&op_ix).unwrap();
92        let input_values = input_indexes.map_semifinite(&mem).unwrap();
93
94        // Compute an IndexedCoproduct of output values.
95        let outputs = apply(op_labels, input_values);
96
97        let output_indexes = f.h.t.map_indexes(&op_ix).unwrap();
98
99        // write outputs to memory
100        mem.0
101            .scatter_assign(&output_indexes.values.table, outputs.values.0);
102
103        // TODO: evaluate all 'ops' in parallel using a user-supplied function
104    }
105    let outputs = mem.0.gather(f.t.table.get_range(..));
106    (mem.0, outputs)
107}
open_hypergraphs/strict/eval.rs

open_hypergraphs/strict/
eval.rs
