.. _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 Op
=======




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




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

