Backtracking products of f and b. Choice in f needs to be reduced to a scalar value. It is then compared to the fst values in b. From those, choice b selects.

The ADP-established product operation. Returns a vector of results, along the lines of what the ADP f *** b provides.

f **> g assumes a vector-to-vector function f, and a vector-to-scalar function g.

Creates instances for all products given a signature data type.

Returns the Name of the monad variable.

Returns the Names of the objective function variables, as well as the name of the objective function itself.

The left algebra type. Assumes that in choice :: Stream m x -> m r we have that x ~ r.

Here, we do not set any restrictions on the types m and r.

Build up the type for backtracking. We want laziness in the right return type. Hence, we have AppT ListT (VarT xR) ; i.e. we want to return results in a list.

1

we want a list for [xR] because this will make it lazy here. At least that was the reason for backtracking. For forward mode, we may not want this. We will have to change the function combination then?

Build up attribute and choice function. Here, we actually bind the left and right algebra to l and r.

Simple wrapper for creating the choice fun expression.

We take the left and right function name for one attribute and build up the combined attribute function. Mostly a wrapper around recBuildLampat which does the main work.

TODO need fun names from l and r

Now things become trickly. We are given all non-terminal names (to differentiate between a terminal (stack) and a syntactic variable; the left and right function; and the arguments to this attribute function (except the result parameter). We are given the latter as a result to an earlier call to getRuleSynVarNames.

We now look at each argument and determine wether it is a syntactic variable. If so, then we actually have a tuple arguments (x,ys) where x has to optimized value and ys the backtracking list. The left function receives just x in this case. For the right function, things are more complicated, since we have to flatten lists. See buildRns.

Terminals are always given "as is" since we do not have a need for tupled-up information as we have for syntactic variables.

Look at the argument type and build the capturing variables. In particular captures synvar arguments with a 2-tuple (x,ys).

Build the right-hand side of a function combined in f <|| g. This splits the paired synvars (x,xs) such that we calculate f x and g xs.

NOTE If we want to write

[ f x | x <- xs ]

then in template haskell, this looks like this:

CompE [BindS (VarP x) (VarE xs), NoBindS (AppE (VarE f) (VarE x))]

The NoBindS is the final binding of f to the individual x's, while the prior x <- xs comes from BindS (VarP x) (VarE xs).

TODO This is where we might be able to improve performance if we can optimize [f x y | x <- xs, y <- ys] for concatMap in vector.

Type for backtracking functions.

Not too interesting, mostly to keep track of choice.

Build up the backtracking choice function. This choice function will backtrack based on the first result, then return only the second.

TODO it should be (only?) this function we will need to modify to build all algebra products.

ysM can't be unboxed, as snd of each element is a list, lazily consumed. We build up ysM as this makes fusion happen. Of course, this is a boxed vector and not as efficient, but we gain the ability to have lazily created backtracking from this!

This means strict optimization AND lazy backtracking

TODO in principle, we do more work than necessary. The line hFres <- ... evaluates the optimal choice from the fst elements again. As long as the cost is small compared to the evaluation of snd (or the list-comprehension based creation of all parses), this won't matter much.

We assume parses of type (x,y) in a vector (x,y). the function acting on x will produce a subset x (in vector form). the function acting on y produces scalars y. We have actFst :: x -> x and actSnd :: y -> y. This in total should yield (x,y) -> (x,y).

TODO This should create generic vectors, that are specialized by the table they are stored into.

Turn a stream into a vector.

TODO need to be improved in terms of performance.

Gets the names used in the evaluation function. This returns one Name for each variable.

In case of TupleT 0 the type is () and there isn't a name to go with it. We just mkName "()" a name, but this might be slightly dangerous? (Not really sure if it indeed is)

With AppT _ _ we have a multidim terminal and produce another hackish name to be consumed above.

AppT (AppT ArrowT (AppT (AppT (ConT Data.Array.Repa.Index.:.) (AppT (AppT (ConT Data.Array.Repa.Index.:.) (ConT Data.Array.Repa.Index.Z)) (VarT c_1627675270))) (VarT c_1627675270))) (VarT x_1627675265)

Get all synvars, even if deep in a stack