Framework
Python implementation of fast Practicable Inducers/Framework
Sections
Histogram and HistogramRepa
Histograms are defined in the overview in section ‘States, histories and histograms’ P8 and in the paper in section ‘Histograms’ P94. The discussion of the Python implementation of Histograms is in the Python implementation of the Overview.
The set of all histograms $\mathcal{A}$ is a subset of the positive rational valued functions of states, $\mathcal{A} \subset \mathcal{S} \to \mathbf{Q}_{\geq 0}$.
The Histogram type is defined in module Alignment with a Map.Map from State to Rational,
newtype Histogram = Histogram (Map.Map State Rational)
This set-theoretic implementation is a poset binary map representation discussed in the paper in section ‘Computation of histograms’ P405. The definition of binary maps is in appendix ‘Binary maps’ P1164.
In the case where the histogram $A \in \mathcal{A}$ is complete, $A^{\mathrm{S}} = V^{\mathrm{CS}}$ where $V = \mathrm{vars}(A)$, the binary map histogram representation has accessor time complexity of $\ln v$ where volume $v = |V^{\mathrm{C}}|$. In the case of a regular histogram of valency $\{d\} = \{|U_w| : w \in V\}$, the time complexity is $n \ln d$, where dimension $n = |V|$.
An array histogram representation (P402) is implemented as an array of counts, $\mathbf{Q}_{\geq 0}^v$, of size $v$. If indexing is implemented with an ordered list state representation the accessor time complexity is $n$. The array histogram representation may require less time, but the array must be of cardinality equal to the volume, and so its space complexity is $v$, which may be greater than that of the effective binary map histogram representation, $|A^{\mathrm{F}}| \ln |A^{\mathrm{F}}|$.
For the cases where the volume is practicable, the module AlignmentRepa defines type HistogramRepa in terms of the multi-dimensional shape polymorphic parallel array which is defined in the numpy library,
data HistogramRepa = HistogramRepa {
histogramRepasVectorVar :: !(V.Vector Variable),
histogramRepasMapVarInt :: Map.Map Variable Int,
histogramRepasArray :: !(Array U VShape Double)}
A HistogramRepa can be constructed from a Histogram,
systemsHistogramsHistogramRepa :: System -> Histogram -> Maybe HistogramRepa
systemsHistogramRepasHistogram :: System -> HistogramRepa -> Maybe Histogram
For example,
aarr = systemsHistogramsHistogramRepa
rraa = systemsHistogramRepasHistogram
aa = regdiag(2,2)
aa
# {({(1, 1), (2, 1)}, 1 % 1), ({(1, 2), (2, 2)}, 1 % 1)}
ar = aarr(sys(aa),aa)
ar
# ([1, 2], {(1, 0), (2, 1)}, array([[1., 0.],
# [0., 1.]]))
rraa(sys(aa),ar)
# {({(1, 1), (2, 1)}, 1 % 1), ({(1, 1), (2, 2)}, 0 % 1), ({(1, 2), (2, 1)}, 0 % 1), ({(1, 2), (2, 2)}, 1 % 1)}
trim(rraa(sys(aa),ar)) == aa
# True
A HistogramRepa consists of (i) a bijective map between tuple position and variable, histogramRepasVectorVar, (ii) the inverse of this map, histogramRepasMapVarInt, and (iii) the multi-dimensional array of Double, histogramRepasArray. For example
histogramRepasVectorVar(ar)
# [1, 2]
histogramRepasMapVarInt(ar)
# {(1, 0), (2, 1)}
histogramRepasArray(ar)
# array([[1., 0.],
# [0., 1.]])
The shape of the histogram is obtained
histogramRepasArray(ar).shape
# (2, 2)
The array can be indexed
histogramRepasArray(ar)[0,0]
# 1.0
histogramRepasArray(ar)[0,1]
# 0.0
Like Histogram, HistogramRepa can be reduced,
setVarsHistogramRepasReduce :: Set.Set Variable -> HistogramRepa -> HistogramRepa
For example,
def arred(aa,vv):
return setVarsHistogramRepasReduce(vv,aa)
arred(ar,sset([VarInt(2)]))
# ([2], {(2, 0)}, array([1., 1.]))
arred(ar,sset())
# ([], {}, 2.0)
arred(ar,vars(aa)) == ar
# True
The independent, $A^{\mathrm{X}}$, has an intermediate representation in terms of a vector of its normalised perimeters, $\{\hat{A}\%\{w\} : w \in V\}$. Module AlignmentRepa defines type HistogramRepaRed,
data HistogramRepaRed = HistogramRepaRed {
histogramRepaRedsVectorVar :: !(V.Vector Variable),
histogramRepaRedsMapVarInt :: Map.Map Variable Int,
histogramRepaRedsShape :: !VShape,
histogramRepaRedsVectorArray :: !(V.Vector (UV.Vector Double))}
Instead of an array, histogramRepasArray, the HistogramRepaRed has a vector of vectors of Double representing the normalised reductions to each of the variables, histogramRepaRedsVectorArray,
histogramRepasRed_u :: Double -> HistogramRepa -> HistogramRepaRed
For example,
rrpr = histogramRepasRed_u
histogramRepaRedsVectorArray(rrpr(2,ar))
# [array([0.5, 0.5]), array([0.5, 0.5])]
Given the HistogramRepaRed the independent may be calculated,
histogramRepaRedsIndependent :: Double -> HistogramRepaRed -> HistogramRepa
For example,
prind = histogramRepaRedsIndependent
rraa(sys(aa),prind(2,rrpr(2,ar))) == ind(aa)
# True
Often a histogram and its shuffle are processed together, so module AlignmentRepa also defines type HistogramRepaVec which implements a vector of congruent histograms each in array histogram representation. That is, the size and set of variables are the shared by all of the histograms,
data HistogramRepaVec = HistogramRepaVec {
histogramRepaVecsVectorVar :: !(V.Vector Variable),
histogramRepaVecsMapVarInt :: Map.Map Variable Int,
histogramRepaVecsSize :: !Double,
histogramRepaVecsShape :: !VShape,
histogramRepaVecsArray :: !(V.Vector (UV.Vector Double))}
History and HistoryRepa
Histories are defined in the overview in section ‘States, histories and histograms’ P8 and in the paper in section ‘Histories’ P92. The discussion of the Python implementation of Histories is in the Python implementation of the Overview.
The set of histories is a subset of the state valued functions of event identifiers, $\mathcal{H} \subset \mathcal{X} \to \mathcal{S}$.
The History type is defined in module Alignment with a Map.Map from Id to State,
newtype History = History (Map.Map Id State)
This set-theoretic implementation is a poset binary map representation.
Section ‘Computation of histograms’ P406 of the paper discusses the list representation of histograms. Here the histogram, $A \in \mathcal{S} \to \mathbf{Q}_{\geq 0}$, is represented as a vector of pairs of the state and count, $\mathcal{L}(\mathbf{N}^n \times \mathbf{Q}_{\geq 0})$, where a state $S \in A^{\mathrm{S}}$ is represented in terms of a vector of length $n$ consisting of integral values, $\{u : (w,u) \in S\}^n \subset \mathcal{L}(\mathbf{N})$.
Similarly, a history $H \in \mathcal{H}$ can be represented as a list of the states, $\mathrm{ran}(H) \subset \mathcal{S}$, in a two dimensional array of integral values, $\mathbf{N}^{zn}$, of size $zn$, where $z = |H|$. The literal event identifiers, $\mathrm{dom}(H) \subset \mathcal{X}$, are dropped and are encoded instead by the order of the states in the vector.
The module AlignmentRepa defines type HistoryRepa in terms of the two-dimensional array,
data HistoryRepa = HistoryRepa {
historyRepasVectorVar :: !(V.Vector Variable),
historyRepasMapVarInt :: Map.Map Variable Int,
historyRepasShape :: !VShape,
historyRepasArray :: !(Array U DIM2 Int)}
A HistoryRepa can be constructed from a History,
systemsHistoriesHistoryRepa :: System -> History -> Maybe HistoryRepa
For example,
hhhr = systemsHistoriesHistoryRepa
hrhh = systemsHistoryRepasHistory_u
def aahr(aa):
return hhhr(sys(aa),aahh(aa))
aa = regdiag(2,2)
aa
# {({(1, 1), (2, 1)}, 1 % 1), ({(1, 2), (2, 2)}, 1 % 1)}
hr = aahr(aa)
hr
# ([1, 2], {(1, 0), (2, 1)}, (2, 2), array([[0, 1],
# [0, 1]]))
A HistoryRepa consists of (i) a bijective map between tuple position and variable, historyRepasVectorVar, (ii) the inverse of this map, historyRepasMapVarInt, (iii) the shape, historyRepasShape, and (iv) the two-dimensional array of Int, historyRepasArray. For example
historyRepasVectorVar(hr)
# [1, 2]
historyRepasMapVarInt(hr)
# {(1, 0), (2, 1)}
historyRepasShape(hr)
# (2, 2)
historyRepasArray(hr)
# array([[0, 1],
# [0, 1]])
Another example,
aa = regcart(3,2)
rpln(aall(aa))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
hr = aahr(aa)
hr
# ([1, 2], {(1, 0), (2, 1)}, (3, 3), array([[0, 0, 0, 1, 1, 1, 2, 2, 2],
# [0, 1, 2, 0, 1, 2, 0, 1, 2]]))
historyRepasVectorVar(hr)
# [1, 2]
historyRepasArray(hr)
# array([[0, 0, 0, 1, 1, 1, 2, 2, 2],
# [0, 1, 2, 0, 1, 2, 0, 1, 2]])
rpln(aall(hhaa(hrhh(sys(aa),hr))))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
Given a list of event identifier positions, a subset of events or a slice of a HistoryRepa may be selected,
eventsHistoryRepasHistoryRepaSelection :: [Int] -> HistoryRepa -> HistoryRepa
For example,
def hrsel(hr,ll):
return eventsHistoryRepasHistoryRepaSelection(ll,hr)
rpln(aall(hhaa(hrhh(sys(aa),hrsel(hr,[])))))
rpln(aall(hhaa(hrhh(sys(aa),hrsel(hr,[0])))))
# ({(1, 1), (2, 1)}, 1 % 1)
rpln(aall(hhaa(hrhh(sys(aa),hrsel(hr,[0,4,8])))))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
rpln(aall(hhaa(hrhh(sys(aa),hrsel(hr,list(range(0,8+1)))))))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
A HistoryRepa can be reduced to another HistoryRepa,
setVarsHistoryRepasHistoryRepaReduced :: Set.Set Variable -> HistoryRepa -> HistoryRepa
For example,
def hrhrred(hr,vv):
return setVarsHistoryRepasHistoryRepaReduced(vv,hr)
rpln(aall(hhaa(hrhh(sys(aa),hrhrred(hr,[VarInt(1),VarInt(2)])))))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
rpln(aall(hhaa(hrhh(sys(aa),hrhrred(hr,[VarInt(1)])))))
# ({(1, 1)}, 3 % 1)
# ({(1, 2)}, 3 % 1)
# ({(1, 3)}, 3 % 1)
rpln(aall(hhaa(hrhh(sys(aa),hrhrred(hr,[VarInt(2)])))))
# ({(2, 1)}, 3 % 1)
# ({(2, 2)}, 3 % 1)
# ({(2, 3)}, 3 % 1)
rpln(aall(hhaa(hrhh(sys(aa),hrhrred(hr,[])))))
# ({}, 9 % 1)
A HistoryRepa can be reduced to a HistogramRepa,
setVarsHistoryRepasReduce :: Double -> Set.Set Variable -> HistoryRepa -> HistogramRepa
For example,
def hrred(hr,vv):
return setVarsHistoryRepasReduce(1,vv,hr)
rpln(aall(rraa(sys(aa),hrred(hr,[VarInt(1),VarInt(2)]))))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
rpln(aall(rraa(sys(aa),hrred(hr,[VarInt(1)]))))
# ({(1, 1)}, 3 % 1)
# ({(1, 2)}, 3 % 1)
# ({(1, 3)}, 3 % 1)
rpln(aall(rraa(sys(aa),hrred(hr,[VarInt(2)]))))
# ({(2, 1)}, 3 % 1)
# ({(2, 2)}, 3 % 1)
# ({(2, 3)}, 3 % 1)
rpln(aall(rraa(sys(aa),hrred(hr,[]))))
# ({}, 9 % 1)
The vector of its normalised perimeters may be obtained from the HistoryRepa,
historyRepasRed :: HistoryRepa -> HistogramRepaRed
For example,
hrhx = historyRepasRed
histogramRepaRedsVectorArray(hrhx(hr))
# [array([0.33333333, 0.33333333, 0.33333333]), array([0.33333333, 0.33333333, 0.33333333])]
histogramRepaRedsVectorArray(hrhx(hrredhr(hr,[VarInt(1)])))
# [array([0.33333333, 0.33333333, 0.33333333])]
histogramRepaRedsVectorArray(hrhx(hrredhr(hr,[])))
# []
The vector of its normalised perimeters may be obtained from the HistoryRepa for a subset of the variables,
setVarsHistoryRepasRed :: Set.Set Variable -> HistoryRepa -> HistogramRepaRed
For example,
def hrredhx(hr,vv):
return setVarsHistoryRepasRed(vv,hr)
histogramRepaRedsVectorArray(hrredhx(hr,[VarInt(1),VarInt(2)]))
# [array([0.33333333, 0.33333333, 0.33333333]), array([0.33333333, 0.33333333, 0.33333333])]
histogramRepaRedsVectorArray(hrredhx(hr,[VarInt(1)]))
# [array([0.33333333, 0.33333333, 0.33333333])]
histogramRepaRedsVectorArray(hrredhx(hr,[]))
# []
Transform and TransformRepa
Transforms are defined in the overview in section ‘Transforms’ P35 and in the paper in section ‘Transforms’ P111. The discussion of the Python implementation of Transforms is in the Python implementation of the Overview.
The set of all transforms is $\mathcal{T} := \{(X,W) : X \in \mathcal{A},~W \subseteq \mathrm{vars}(X)\}$.
Given a histogram $X \in \mathcal{A}$ and a subset of its variables $W \subseteq \mathrm{vars}(X)$, the pair $T = (X,W)$ forms a transform.
The Transform type is defined in module Alignment with a pair of a Histogram and a Variable set,
newtype Transform = Transform (Histogram, (Set.Set Variable))
The implementation of the Histogram is a poset binary map representation.
Given a histogram $A \in \mathcal{A}$, the multiplication of the histogram, $A$, by the transform $T \in \mathcal{T}$ equals the multiplication of the histogram, $A$, by the transform histogram $X = \mathrm{his}(T)$ followed by the reduction to the derived variables $W = \mathrm{der}(T)$, $A * T := A * X~\%~W$. Section ‘Computation of histograms’ P407 discusses the reduction and multiplication of histograms. Then the discussion goes on (P408) to consider the multiplication to two histograms $A * B$ where the second histogram, $B$, is the histogram of some one functional transform $T \in \mathcal{T}_{U,\mathrm{f},1}$. This multiplication can be thought of as adding variables to $A$ without changing the cardinality or the counts. The computation of the application need only remap the states without modifying the counts however they are represented. No multiplications nor additions are computed. See section ‘Computation of the application of a transform’ P409.
Consider the case where the one functional transform, $T$, has a single derived variable $\{w\} = \mathrm{der}(T)$. The histogram, $X$, may then be represented as an array of the derived values, $U_w^v$, of size equal to the underlying volume, $v$.
The module AlignmentRepa defines type TransformRepa in terms of a multi-dimensional array of the integral values of the derived variable,
data TransformRepa = TransformRepa {
transformRepasVectorVar :: !(V.Vector Variable),
transformRepasMapVarInt :: Map.Map Variable Int,
transformRepasVarDerived :: !Variable,
transformRepasValency :: !Int,
transformRepasArray :: !(Array U VShape Int)}
A TransformRepa can be constructed from a Transform,
systemsTransformsTransformRepa :: System -> Transform -> Maybe TransformRepa
For example,
tt = cdtt([1,2,3],[[1,1,1],[1,2,1],[1,3,1],[2,1,2],[2,2,2],[2,3,2],[3,1,2],[3,2,2],[3,3,1]])
rpln(aall(ttaa(tt)))
# ({(1, 1), (2, 1), (3, 1)}, 1 % 1)
# ({(1, 1), (2, 2), (3, 1)}, 1 % 1)
# ({(1, 1), (2, 3), (3, 1)}, 1 % 1)
# ({(1, 2), (2, 1), (3, 2)}, 1 % 1)
# ({(1, 2), (2, 2), (3, 2)}, 1 % 1)
# ({(1, 2), (2, 3), (3, 2)}, 1 % 1)
# ({(1, 3), (2, 1), (3, 2)}, 1 % 1)
# ({(1, 3), (2, 2), (3, 2)}, 1 % 1)
# ({(1, 3), (2, 3), (3, 1)}, 1 % 1)
def tttr(tt):
return systemsTransformsTransformRepa_u(sys(ttaa(tt)),tt)
tr = tttr(tt)
tr
# ([1, 2], {(1, 0), (2, 1)}, 3, 2, array([[0, 0, 0],
# [1, 1, 1],
# [1, 1, 0]]))
A TransformRepa consists of (i) a bijective map between tuple position and variable, transformRepasVectorVar, (ii) the inverse of this map, transformRepasMapVarInt, (iii) the derived variable, transformRepasVarDerived, (iv) the derived valency, transformRepasValency and (v) the multi-dimensional array of Int, transformRepasArray. For example
transformRepasVectorVar(tr)
# [1, 2]
transformRepasMapVarInt(tr)
# {(1, 0), (2, 1)}
transformRepasVarDerived(tr)
# 3
transformRepasValency(tr)
# 2
transformRepasArray(tr)
# array([[0, 0, 0],
# [1, 1, 1],
# [1, 1, 0]])
A TransformRepa may be applied to a HistoryRepa to generate a HistoryRepa reduced to the derived variable,
historyRepasTransformRepasApply_u :: HistoryRepa -> TransformRepa -> HistoryRepa
For example,
aa = regcart(3,2)
rpln(aall(aa))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 1), (2, 2)}, 1 % 1)
# ({(1, 1), (2, 3)}, 1 % 1)
# ({(1, 2), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 2), (2, 3)}, 1 % 1)
# ({(1, 3), (2, 1)}, 1 % 1)
# ({(1, 3), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
hr = aahr(aa)
trmul = historyRepasTransformRepasApply_u
rpln(aall(hhaa(hrhh(sysreg(3,3),trmul(hr,tr)))))
# ({(3, 1)}, 4 % 1)
# ({(3, 2)}, 5 % 1)
aa = regdiag(3,2)
rpln(aall(aa))
# ({(1, 1), (2, 1)}, 1 % 1)
# ({(1, 2), (2, 2)}, 1 % 1)
# ({(1, 3), (2, 3)}, 1 % 1)
hr = aahr(aa)
rpln(aall(hhaa(hrhh(sysreg(3,3),trmul(hr,tr)))))
# ({(3, 1)}, 2 % 1)
# ({(3, 2)}, 1 % 1)
Section ‘Computation of functional definition sets’ P408 discusses the application of a one functional definition set $F \in \mathcal{F}_{U,1}$ of one functional transforms to a histogram, $A * F$. The sequence of the application of the transforms can be ordered by layer so that the cardinality of the intermediate histogram remains that of the given histogram, $|A|$.
A vector of TransformRepa can be ordered by layer,
listVariablesListTransformRepasSort :: V.Vector Variable -> V.Vector TransformRepa -> V.Vector TransformRepa
This sort followed by the application in sequence allows the application of a fud consisting of an arbitrary vector of TransformRepa to a HistoryRepa. Note that the application is really a multiply because the resultant HistoryRepa is not reduced to the fud derived variables,
historyRepasListTransformRepasApply :: HistoryRepa -> V.Vector TransformRepa -> HistoryRepa
For example,
tt1 = cdtt([1,3],[[1,1],[2,1],[3,2]])
tt2 = cdtt([1,4],[[1,1],[2,2],[3,2]])
tt3 = cdtt([3,4,5],[[1,1,1],[1,2,1],[2,1,1],[2,2,2]])
ltrmul = historyRepasListTransformRepasApply
rpln(aall(hhaa(hrhh(sysreg(3,5),ltrmul(hr,[tttr(tt3),tttr(tt1),tttr(tt2)])))))
# ({(1, 1), (2, 1), (3, 1), (4, 1), (5, 1)}, 1 % 1)
# ({(1, 2), (2, 2), (3, 1), (4, 2), (5, 1)}, 1 % 1)
# ({(1, 3), (2, 3), (3, 2), (4, 2), (5, 2)}, 1 % 1)
Given a fud, the construction of the vector of TransformRepa and its application to a HistoryRepa is wrapped up as
systemsFudsHistoryRepasMultiply :: System -> Fud -> HistoryRepa -> Maybe HistoryRepa
For example,
def frmul(hr,ff):
return systemsFudsHistoryRepasMultiply_u(fsys(ff),ff,hr)
ff = llff([tt3,tt1,tt2])
rpln(aall(hhaa(hrhh(sysreg(3,5),frmul(hr,ff)))))
# ({(1, 1), (2, 1), (3, 1), (4, 1), (5, 1)}, 1 % 1)
# ({(1, 2), (2, 2), (3, 1), (4, 2), (5, 1)}, 1 % 1)
# ({(1, 3), (2, 3), (3, 2), (4, 2), (5, 2)}, 1 % 1)