
We are concerned with loops that iterate over the contents of one or
more containers and which may create new containers of the same type.
For the purposes
of this paper we will only consider looping over lists although the
algorithm can be extended to support other container data types, and looping
over sets is also supported in the current implementation.
We will illustrate the problem and notation with an example. Consider
the sequence of actions:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$A(-[a\ b\ c], -k)$ \\
$C(+a)$ \\
$B(+k, +a, -s)$ \\
$C(+s)$ \\
$B(+k, +b, -t)$ \\
$C(+t)$ \\
$B(+k, +c, -u)$ \\
$C(+u)$ \\
$D(+[s\ t\ u])$
\end{tabbing}
\end{minipage}
\end{center}
Here the uppercase letters denote actions, the lowercase letters
letters denote primitive data values and lists are enclosed in square
brackets. We wish to find programs consistent with the
demonstration that may contain zero or more non-nested loops.
For example:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$A(-L, -X)$ \\
$C(+{\it head}(L))$ \\
${\bf for }\ Y\ {\bf in}\ L\ {\bf building}\ H\ {\bf do}$ \\
$\ \ \ \ B(+X, +Y, -Z)$ \\
$\ \ \ \ C(+Z)$ \\
$\ \ \ \ H\ {\bf accumulate}\ Z$ \\
${\bf od}$ \\
$D(+H)$
\end{tabbing}
\end{minipage}
\end{center}
Here capital letter arguments denote variables. In a program, output
positions of actions may only contain variables --- no pattern
matching is allowed. Input positions in general may contain
expressions formed from variables, constants and operators. For the
purposes of this paper we will only consider variables, and the
operators ${\it head}$ and ${\it tail}$ which extract the first and last
elements respectively from a list. {\em For-loops} iterate over one or more
lists (which must have the same length if multiple lists are involved) and
generate zero or more lists where each generated list accumulates one
element at the end of the loop body. The accumulated elements must be
given by a variable occurring as an output in the
loop body. Generated lists are not available for use until after the
end of the loop.

A program $P$ is {\em consistent} with a demonstration $D$ if $D$ can be
produced by executing $P$ under the assumption that each action, when
executed in the same context (i.e. with the same previous actions
having taken place) and with the same inputs as an occurrence
in $D$ will generate the same outputs as seen in that occurrence.

In general there may be multiple
programs consistent with a given demonstration and we are interested
in generating them all. That way we can apply some post learning
selection mechanism, for example by pruning programs that are
inconsistent with a second demonstration, to yield the final learned
program.

Often when there are multiple programs learnable from a given
demonstration, there will be programs that have the same structure but
differ in the support for a given value; i.e. they will have a
different variable or expression as an input to some action.
For example consider the
demonstration:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$A(-[a\ b\ c], -k)$ \\
$B(+k, -a)$ \\
$C(+a, +a)$ \\
$C(+a, +b)$ \\
$C(+a, +c)$ \
\end{tabbing}
\end{minipage}
\end{center}
Here there is ambiguity about where the $a$ that is passed as the first
argument to each of the $C$ actions comes from. In order to represent
this situation compactly, we will instead work with {\em generalized
programs} where each input argument to an action, and each container
to be looped over is actually a nonempty set of
alternatives. For example the two alternative programs that could be
learned from the above example can be represented by the single
generalized program:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$A(-L, -X)$ \\
$B(+\{X\}, -Y)$ \\
${\bf for }\ Z\ {\bf in}\ \{ L\}\ {\bf do}$ \\
$\ \ \ \ C(+\{Y, {\it head}(L)\}, +\{Z\})$ \\
${\bf od}$
\end{tabbing}
\end{minipage}
\end{center}
Here all the input arguments are sets and the first argument of the
$C$ action is the non-singleton set $\{Y, {\it head}(L)\}$.
This is because the value $a$, that occurs as the first argument to
each of the demonstration instances of $C$, could have come from the
list that was the output of the $A$ action (and which was replaced by
the variable $L$), or the from the sole output of the $B$ action (which was
replaced by the variable $Y$).

The overall structure of the algorithm is that of a search, where
there may be alternative choices to be considered.
\begin{enumerate}
\item There may be alternatives for supports; these are captured by sets of
alternatives for input arguments or containers to be looped over.
\item There may be be choices about where and if to start a loop and
how long the loop body should be; these are structural choices and are
captured by different generalized programs.
\end{enumerate}
Only the second case requires actual branching.
Each branch of the search returns a set of
generalized program fragments consistent with a suffix portion of the
demonstration sequence. This set may be empty in the case that the
branch of the search failed.

The key data structure in this search is a multimap $M$ which maps
data values (primitive and containers) to supports. A support for a
data value $v$ is an entity that can
potentially provide $v$; for example a fresh variable that has
replaced an instance of $v$ on the current branch of the search, or a
container data value that contains $v$. Since $M$
will need to be updated on one branch in a search and then
restored to its previous state before exploring a parallel branch, it
is crucial to efficiency that this multimap is stored as a {\em fully
persistent} data structure where any previous state is available and
can be used as a basis for future updates.

The algorithm can be considered as a pair of mutually recursive procedures,
LinearGenerator and LoopGenerator that search for generalizations of
the demonstration.
LinearGenerator takes a index $i$ into the demonstration and the
multimap $M$ of known supports and generates a
set of generalized programs that are consistent with the
demonstration suffix starting from $i$, and using the supports in $M$.
It generates linear code by {\em variablizing} demonstration actions, 
and also detects potential loops.
LoopGenerator takes a index $i$ into the demonstration and the
multimap $M$ of known supports together with
a loop body length $b$ and a number of iterations $n$ and generates a 
set of generalized programs that are consistent with the
demonstration suffix starting from $i$, and using the supports in
$M$, where the next $n\times b$ actions are
explained by a loop over one or more lists of length $n$ which has a loop
body of length $b$.

The algorithm starts with a call to LinearGenerator with index $0$ and an
empty multimap of supports.

\subsection{Variablization}

In creating a program action from a demonstration action $\alpha$, each output
value $u$ is replaced by a fresh variable which is then added to the
multimap $M$ as a support for $u$ in later actions. If $u$ happens to
be a list then $u$ itself is recorded as a support for both its first and last elements.

Each input value
$v$ is replaced by a set of {\em support expressions} which is computed
recursively. The set of support expressions for $v$ is the union of
the sets of support expressions for each support $s$ that $v$ has in $M$.

In the base case, $s$ is a variable and the resulting set of support
expressions is the singleton set containing just $s$ itself. If $s$ is
a container $c$ that contains $v$, we recursively compute the set $S$ of support
expressions for $c$ and for each $e\in S$ we generate a new expression
by using $f(e)$ where $f$ is the appropriate accessor function for
obtaining $v$ from $c$.

When an input value $v$ to a demonstration action $\alpha$ has no supports,
the attempt to variablize $\alpha$ fails.

\subsection{LinearGenerator}

LinearGenerator starts with an empty set $G$ of generalized program fragments and
considers demonstration actions in order, starting at index $i$.
When an action $\alpha$ is considered, LinearGenerator attempts to variablize
it as explained above. If variablization fails then all branches of
the search that required linear code from index i up to and including
the failed index are dead and
LinearGenerator returns the set $G$ of generalized program fragments
accumulated so far.

In variablizing an action $\alpha$, every time we form a support expression
${\it head} (e)$ for input value $v$,  there is the possibility that instead of
accessing $v$ using the head operation, $\alpha$ could be the first action
that accesses the loop variable in a loop that iterates over the list
given by support expression $e$. In this case we say $\alpha$ is the
{\em anchor} of the loop. Let $l$ list that supported $v$.
To account for the possible iteration over $l$ we insert the length of $l$ into a set $I$ of iteration counts
for loops anchored by $\alpha$. We do not record $l$ itself as it possible that
$\alpha$ could be part of a loop that is iterating over multiple lists
(of the same length). It is also possible  that the
loop body actually started before $\alpha$.

To detect potential loops anchored at $\alpha$ we consider each iteration
count $n\in I$ in turn, and try alternative loop body lengths, $b$, and loop body
start indices, $j$, looking for a
pair $(j, b)$ where the sequence of action names in the demonstration
fragment $[j, j+b-1]$ that corresponds to the first iteration is equal
to sequence of action names in the demonstration fragments
$[j+k.b, j+k.b + b-1]$ for each $k\in \{1,\ldots, n-1\}$ which
correspond to the subsequent $n-1$ iterations. Such a pair $(j, b)$
describes a putative list loop of $n$ iterations.

For each such pair $(j, b)$ we call LoopGenerator on $(j, M_j,  b, n)$
where $M_j$ is the state of the support multiset $M$ just before the
variablization of the demonstration action at index $j$. This previous
state of $M$ is available because $M$ is implemented by a fully persistent
data structure.
LoopGenerator will return the sets of
generalized program fragments starting with a list loop of body length $b$
with $n$ iterations can be constructed, continuing from index $j$
in the demonstration, using supports in $M_j$. Since the same
combination of arguments to
LoopGenerator can potentially be found from multiple anchors, a set of argument
combinations already tried is maintained to avoid redundant work.

The generalized program fragments returned by LoopGenerator are each
grafted on to the current generalized program fragment for actions
up to but not including index $j$ and the resulting generalized program fragments are added
to the set $G$.

Once all the putative
loops anchored at $\alpha$ have been explored, LinearGenerator moves on to
the next action.
When the last demonstration action had been processed, the set $G$ of
generalized program fragments
accumulated so far is returned.

\subsection{LoopGenerator}

LoopGenerator tries to generate a loop with a body of length $b$ that
iterates over one or more lists of length $n$, starting with the
action at index $i$ and using the supports from multiset $M$. It
proceeds in two phases.

In the first phase, the putative loop body is constructed by
variablizing the first $b$ actions starting at index $i$.
Finding supports for inputs and variablizing outputs and adding
supports to $M$ works much like it does in LinearGenerator. Since
supports will be local to this iteration of the loop, a reference to
the original state of $M$ is kept for use after the end of the loop.
Each input value $v$ that is supported as the first element of a list $l$ of
length $n$ causes $l$ to be recorded as a potential list to be looped
over and a loop variable is created for it. This loop variable then
becomes an alternative support for $v$. For example, suppose we have
have the demonstration:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$A(-[a\ b\ c], -[a\ b\ d])$\\
$B(+a, +a, -s)$\\
$B(+b, +a, -t)$\\
$B(+c, +a, -u)$
\end{tabbing}
\end{minipage}
\end{center}
Here the first action will have already been variablized, say to:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$A(-K, -L)$
\end{tabbing}
\end{minipage}
\end{center}
in LinearGenerator and the first $B$ action will trigger a call to
LoopGenerator to look for a loop with 3 iterations and body length of
1. LoopGenerator will variablize the first occurrence of input value
$a$ to $\{{\it head}(J), {\it head}(K)\}$. This use of the first
elements of lists variablized by $J$ and $K$ means they are both
potential lists to be looped over, and so fresh variables $X$ and $Y$
are created to iterator over $J$ and $K$ respectively. These
variables then become supports for $a$. A fresh variable $Z$ is
created to variablize the output argument of $B$  so the after the
first phase, the variablization of the first $B$ action looks like:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$B(\{ {\it head}(J), {\it head}(K), X, Y \},$\\
$\ \ \ \ \ \{ {\it head}(J), {\it head}(K), X, Y \}, Z)$
\end{tabbing}
\end{minipage}
\end{center}

In the second phase, the putative loop body is executed for the
remaining $n-1$ iterations, with inconsistent support expressions for
inputs being pruned.

A binding of variables to values is created at the start
of each iteration. Each loop variable receives its value from the list
it is iterating over. Each action in the loop body are then compared
the corresponding action for the current iteration in the
demonstration. Alternative support expressions for input values in the loop body
whose evaluation disagree with the actual values found in the demonstration are
pruned away. If an input loses all of its support expressions, failure occurs and
an empty set of generalized program fragments is returned.
Output values from the demonstration are used to update the value
bindings for this iteration. In our example the sets of support
expressions for the inputs arguments of $B$ are pruned, leaving:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
$B(\{ X \},
  \{ {\it head}(J), {\it head}(K) \}, Z)$
\end{tabbing}
\end{minipage}
\end{center}
Also each output occurring in the loop
body is potentially a list that is generated in by the loop and is
accumulated in a fresh variable for later use.

If the loop body survives the second phase, the loop variables are
checked, and those that no longer appear in a support expression for some action
input are themselves pruned. If all the loop variables are pruned we
again have failure. Otherwise we form a loop statement with the
surviving loop variables iterating over their lists, using the pruned
body. Thus in our example we
end up with a for-loop:
\begin{center}
\begin{minipage}{4in}
\begin{tabbing}
${\bf for}\ X\ {\bf in}\ \{J\}\ {\bf building}\ L\ {\bf do}$\\
$\ \ \ \ B(\{ X \}, \{ {\it head}(J), {\it head}(K) \}, Z)$\\
$\ \ \ \ L\ {\bf accumulate}\ Z$\\
${\bf od}$
\end{tabbing}
\end{minipage}
\end{center}

Finally LoopGenerator calls LinearGenerator, passing it the pre-loop
state of the support multiset $M$, to generate a set
of generalized program fragments for the rest of the demonstration.
Each of these generalized program fragments are grafted,
in turn, on the end of the newly constructed
loop to obtain the set of generalized program fragments that LoopGenerator will
return.

\subsection{Extensions}

The basic algorithm can be extended to handle other container types
and other operators. The current implementation supports sets, tuples
as well as operators to access the elements of tuples, and to construct fixed
length lists from their elements. Also supported are {\em
ungeneralizable} annotations for input arguments to an action. An
argument marked as ungeneralizable is passed though unchanged as a
constant in the resulting program.

Loops that iterate over sets present an additional problem
in that the order in which the elements of a set are accessed is
undefined. This limits set-based for-loops to iterating over a single
set since otherwise we would have an undefined correlation between
multiple loop variables. Also we cannot accumulate lists in a
set-based for-loop since otherwise we would be adding order
information that we do not have. We can however accumulate sets.

Detection of a putative set-based for-loop is triggered by the use of
any member $e$ of a set $s$. The code for checking of the
corresponding on action names between the first and subsequent
iterations also collects a list of the
input arguments that mirror the argument $e$ in the
remaining iterations. This list serves as early check on the feasibility of
a set-based for-loop (i.e. each elment of $s\setminus \{e\}$ must
occur exactly once in this list) and defines an order on the elements
of $s\setminus \{e\}$ to be
use in the execution based pruning phase after the loop body as been
constructed.
