.. _scan_internals:

Developper documentation for Scan
+++++++++++++++++++++++++++++++++

Context
=======

This document is meant to act as reference material for developers working
on Theano's loop mechanism. This mechanism is called Scan and its internals
are highly complex, hence the need for a centralized repository of knoledge
regarding its inner workings.

The `theano.scan()` function is the public-facing interface for looping in
Theano. Under the hood, this function will perform some processing on its
inputs and instantiate the `Scan` Op class which implements the looping
mechanism. It achieves this by compiling it's own Theano function representing
the computation to be done at every iteration of the loop and calling it as
many times as necessary.

The correspondence between the parameters and behaviors of the function and the
op is not always simple since the former is meant for usability and the second
for performance. Since this document is intended to be used by developers
working inside scan itself, it will mostly discuss things from the point of view
of the `Scan` Op class. Nonetheless, it will attempt to link those elements to
their corresponding concepts in the scan function as often as is reasonnably
practical.


Pre-requisites
==============

The following sections assumes the reader is familiar with the following :

1. Theano's graph structure (Apply nodes, Variable nodes and Ops)
    http://deeplearning.net/software/theano/tutorial/extending_theano.html#theano-graphs

2. The interface and usage of Theano's `scan()` function
    http://deeplearning.net/software/theano/library/scan.html


Relevant code files
===================

The implementation of scan is spread over several files. The different
files, and section of the code they deal with, are :

* ``scan.py`` implements the ``scan`` function. The ``scan`` function
  arranges the arguments of scan correctly, constructs the scan op and
  afterwards calls the constructed scan op on the arguments. This function
  takes care of figuring out missing inputs and shared variables. 

* ``scan_op.py`` implements the ``Scan`` Op class. The ``Scan`` respects
  the ``Op`` interface, and contains most of the logic of the scan operator.

* ``scan_utils.py`` contains several helpful functions used through out the
  other files that are specific of the scan operator.

* ``scan_views.py`` contains different views of the scan op that have
  simpler and easier signatures to be used in specific cases.

* ``scan_opt.py`` contains the list of all optimizations for the scan
  operator.


Notation
========

Scan being a sizeable and complex module, it has its own naming convention for
functions and variables which this section will attempt to introduce.

Recall that a Scan op contains a Theano function representing the computation
that is done in a single iteration of the loop represented by the Scan op (in
other words, the computation given by the function provided as value to
theano.scan's ''fn'' argument ). Whenever we discuss a scan op, "outer function"
refers to the Theano function that *contains* the Scan op whereas the "inner
function" refers to the Theano function that is *contained* in the Scan op.

In the same spirit, the inputs to the Apply node wrapping the Scan op (or "Scan
node" for short) and its outputs are referred to as "outer inputs" and "outer
outputs", respectively, because these inputs and outputs are variables in the
outer function graph. The inputs and outputs of scan's inner function are
designated "inner inputs" and "inner outputs".


Scan variables
==============

The following are the different types of variables that Scan has the capacity to
handle, along with their various caracteristics.

**Sequence** : A sequence is a Theano variable which Scan will iterate over and
give sub-elements to its inner function. For a sequence variable `X`, at
timestep `t`, the inner function will receive as input the sequence element
`X[t]`. These variables are used through the argument `sequences` of the
`theano.scan()` function.

**Non-sequences** : A sequence is a Theano variable which Scan will provide
`as-is` to its inner function. For a non-sequence variable X, at timestep `t`,
the inner function will receive as input the variable X. These variables are
used through the argument `non_sequences` of the `theano.scan()` function.

**Nitsot (no input tap, single output tap)** : A nitsot is an output variable of
the inner function that is not fed back as an input to the next iteration of the
inner function. Nitsots are typically encountered in situations where Scan is
used to perform a 'map' operation (every element in a tensor is independently
altered using a given operation to produce a new tensor) such as squaring every
number in a vector.

**Sitsot (single input tap, single output tap)** : A sitsot is an output
variable of the inner function that is fed back as an input to the next
iteration of the inner function. A typical setting where a sistot might be
encountered is the case where scan is used  Sitsots are typically encountered in
situations where Scan is used to sum the elements of a vector and a sitsot
output is employed to act as an accumulator.

**Mitsot (multiple input taps, single output tap)** : A sitsot is an output
variable of the inner function that is fed back as an input to future iterations
of the inner function (either multiple future iterations or a single one that
isn't the immediate next one).

**Mitmot (multiple input taps, multiple output taps)** : These outputs exist but
not 'in the wild'. They can appear in a theano graph as a result of taking the
gradient of the output of a Scan : taking the gradient of the output of a Scan
wrt its inputs will result in the creation of a new Scan node used to compute
the gradients of the first Scan node. This new Scan might use mitmot outputs.


To synthesise :

.. list_table:: Scan variables
    :widths: 30 30 30
    :header-rows: 1

    *   - Type of scan variables
        - Corresponding outer input
        - Corresponding inner input at timestep `t` (indexed from 0)
        - Corresponding inner output at timestep `t` (indexed from 0)
        - Corresponding outer output `t`
        - Corresponding argument of the `theano.scan()` function

    *   - Sequence
        - Sequence of elements X
        - Individual sequence element X[t]
        - *No corresponding inner output*
        - *No corresponding outer output*
        - `sequences`

    *   - Non-Sequence
        - Any variable X
        - Variable identical to X
        - *No corresponding inner output*
        - *No corresponding outer output*
        - `non_sequences`

    *   - Non-recurring output (nitsot)
        - *No corresponding outer input*
        - *No corresponding inner input*
        - Output value at timestep `t`
        - Concatenation of the values of the output at all timestep
        - `outputs_info`

    *   - Singly-recurrent output (sitsot)
        - Initial value (value at timestep `-1`)
        - Output value at previous timestep (`t-1`)
        - Output value at timestep `t`
        - Concatenation of the values of the output at all timestep
        - `outputs_info`

    *   - Multiply-recurrent output (mitsot)
        - Initial values for the required timesteps where `t<0`
        - Output value at previous required timesteps
        - Output value at timestep `t`
        - Concatenation of the values of the output at all timestep
        - `outputs_info`

    *   - Multiply-recurrent multiple outputs (mitmot)
        - Initial values for the required timesteps where `t<0`
        - Output value at previous required timesteps
        - Output values for current and multiple future timesteps
        - Concatenation of the values of the output at all timestep
        - No corresponding argument. Mitmots cannot be created through
          `theano.scan()`


Optimizations
=============

remove_constants_and_unused_inputs_scan
---------------------------------------

This optimization serves two purposes, The first is to remove a Scan Op's
unused inputs. The second it to take a Scan Op's constant inputs and remove
them, instead injecting the constants directly into the graph or the Scan
Op's inner function. This will allow constant folding to happen inside the
inner function.

PushOutNonSeqScan
-----------------

This optimizations pushes, out of Scan's inner function and into the outer
function, computation that depends only on non-sequence inputs. Such
computation ends up being done every iteration on the same values so moving
it to the outer function to be executed only once, before the Scan Op,
reduces the amount of computation that needs to be performed.





Helper classes and functions
============================

Because of the complexity involved in dealing with Scan, a large number of
helper classes and functions have been developped over time to implement
operations commonly needed when dealing with the Scan op. The Scan op
itself defines a large number of them and others can be found in the file
`scan_utils.py`. This sections aims to point out the most useful ones and
organize them according to their uses.


Accessing/manipulating Scan's inputs and outputs by type
--------------------------------------------------------

Declared in `scan_utils.py`, the class `scan_args` handles the parsing
of the inputs and outputs (both inner and outer) to a format that is easier to
analyse and manipulate. Without this class, analysing scan's inputs and
outputs often required convoluted logic which make for code that is hard to
read and to maintain. Because of this, you should favor using `scan_args` when
it is practical and appropriate to do so.

The Scan op also defines a few helper functions for this purpose, such as
`inner_nitsot_outs()` or `mitmot_out_taps()`, but they are often poorly
documented and easy to misuse. These should be used with great care.


Navigating between outer inputs/outputs and inner inputs/outputs
----------------------------------------------------------------

Navigation between these four sets of variables can be done in two ways,
depending on the type of navigation that is required.

If the goal is to navigate between variables that are associated with the same
states (ex : going from an outer sequence input to the corresponding inner
sequence input, going from an inner output associated with a recurrent state
to the inner input(s) associated with that same recurrent state, etc.), then
the `var_mappings` attribute of the Scan op can be used.

This attribute is a dictionnary with 12 {key/value} pairs. The keys are listed
below :

*   "outer_inp_from_outer_out"
*   "inner_inp_from_outer_out"
*   "inner_out_from_outer_out"
*   "inner_inp_from_outer_inp"
*   "inner_out_from_outer_inp"
*   "outer_out_from_outer_inp"
*   "outer_inp_from_inner_inp"
*   "inner_out_from_inner_inp"
*   "outer_out_from_inner_inp"
*   "outer_inp_from_inner_out"
*   "inner_inp_from_inner_out"
*   "outer_out_from_inner_out"

Every corresponding value is a dictionary detailing a mapping from one set of
variables to another. For each of those dictionaries the keys are indices of
variables in one set and the values are the indices of the corresponding
variables in another set. For mappings to outer variables, the values are
individual indices or -1 if there is not corresponding outer variable.
For mappings to inner variables, the values are list of indices because
multiple inner variables may be associated with the same state.

If the goal is to navigate between variables that are *connected* (meaning
that one of them is used to compute the other), the methods
`connection_pattern()` and `inner_connection_pattern()` can be used.
The method `connection_pattern()` returns a list of list detailing, for every
pair of outer input and outer output whether they are connected or not. The
method `inner_connection_pattern()` accomplishes the same goal but for every
possible pair of inner output and inner input.
