# Internals

This document describes some internals of Pythran compiler.

Pythran pass management is used throughout the document:

    >>> from pythran import passmanager, analyses, optimizations, backend
    >>> pm = passmanager.PassManager('dummy')

To retrieve the code source from a function definition, the `inspect` module is used:

    >>> from inspect import getsource

And to turn source code into an AST(Abstract Syntax tree), Python provides the `ast` module:

    >>> import gast as ast
    >>> getast = lambda f: ast.parse(getsource(f))

## Scoping

There are only two scopes in Python: `globals()` and `locals()`. When generating C++ code, Pythran tries its best not to declare variables at the function level, but using the deepest scope. This provides two benefits:

1. It makes writing OpenMP clauses easier, as local variables are automatically marked as private;

2. It avoids to build variables with the empty constructor then assigning them a value.

Let’s illustrate this with two simple examples. In the following function, variable `a` has to be declared outside of the `if` statement:

    >>> def foo(n):
    ...     if n:
    ...         a = 1
    ...     else:
    ...         a = 2
    ...     return n*a

When computing variable scope, one gets a dictionary binding nodes to variable names:

    >>> foo_tree = getast(foo)
    >>> scopes = pm.gather(analyses.Scope, foo_tree)

`n` is a formal parameter, so it has function scope:

    >>> sorted(scopes[foo_tree.body[0]])
    ['a', 'n']

`a` is used at the function scope (in the `return` statement), so even if it’s declared in an `if` it has function scpe too.

Now let’s see what happen if we add a loop to the function:

    >>> def foo(n):
    ...     s = 0
    ...     for i in __builtin__.range(n):
    ...         if i:
    ...             a = 1
    ...         else:
    ...             a = 2
    ...         s *= a
    ...     return s
    >>> foo_tree = getast(foo)
    >>> scopes = pm.gather(analyses.Scope, foo_tree)

Variable `a` is only used in the loop body, so one can declare it inside the loop:

    >>> scopes[tuple(foo_tree.body[0].body[1].body)]
    {'a'}

In a similar manner, the iteration variable `i` gets a new value at each iteration step, and is declared at the loop level.

OpenMP directives interacts a lot with scoping. In C or C++, variables declared inside a parallel region are automatically marked as private. Pythran emulates this whenever possible:

    >>> def foo(n):
    ...     s = 0
    ...     "omp parallel for reduction(*:s)"
    ...     for i in __builtin__.range(n):
    ...         if i:
    ...             a = 1
    ...         else:
    ...             a = 2
    ...         s += a
    ...     return s

Without scoping directive, both `i` and `a` are private:

    >>> foo_tree = getast(foo)
    >>> scopes = pm.gather(analyses.Scope, foo_tree)
    >>> scopes[foo_tree.body[0].body[2]]
    {'i'}
    >>> scopes[tuple(foo_tree.body[0].body[2].body)]
    {'a'}

But if one adds a `lastprivate` clause, as in:

    >>> def foo(n):
    ...     s = 0
    ...     a = 0
    ...     "omp parallel for reduction(*:s) lastprivate(a)"
    ...     for i in __builtin__.range(n):
    ...         if i:
    ...             a = 1
    ...         else:
    ...             a = 2
    ...         s += a
    ...     return s, a
    >>> foo_tree = getast(foo)

The scope information change. Pythran first needs to understand OpenMP directives, using a dedicated pass:

    >>> from pythran import openmp
    >>> _ = pm.apply(openmp.GatherOMPData, foo_tree)

Then let’s have a look to

    >>> scopes = pm.gather(analyses.Scope, foo_tree)
    >>> list(scopes[foo_tree.body[0].body[2]])  # 3nd element: omp got parsed
    ['i']
    >>> list(scopes[foo_tree.body[0]])
    ['n']
    >>> list(scopes[foo_tree.body[0].body[0]])
    ['s']
    >>> list(scopes[foo_tree.body[0].body[1]])
    ['a']

`a` now has function body scope, which keeps the OpenMP directive legal.

When the scope can be attached to an assignment, Pythran uses this piece of information:

    >>> def foo(n):
    ...     s = 0
    ...     "omp parallel for reduction(*:s)"
    ...     for i in __builtin__.range(n):
    ...         a = 2
    ...         s *= a
    ...     return s
    >>> foo_tree = getast(foo)
    >>> _ = pm.apply(openmp.GatherOMPData, foo_tree)
    >>> scopes = pm.gather(analyses.Scope, foo_tree)
    >>> scopes[foo_tree.body[0].body[1].body[0]] == set(['a'])
    True

Additionally, some OpenMP directives, when applied to a single statement, are treated by Pythran as if they created a bloc, emulated by a dummy conditional:

    >>> def foo(n):
    ...     "omp parallel"
    ...     "omp single"
    ...     s = 1
    ...     return s
    >>> foo_tree = getast(foo)
    >>> _ = pm.apply(openmp.GatherOMPData, foo_tree)
    >>> print(pm.dump(backend.Python, foo_tree))
    def foo(n):
        'omp parallel'
        'omp single'
        if 1:
            s = 1
        return s

However the additional if bloc makes it clear that `s` should have function scope, and the scope is not attached to the first assignment:

    >>> scopes = pm.gather(analyses.Scope, foo_tree)
    >>> scopes[foo_tree.body[0]] == set(['s'])
    True

## Lazyness

`Expressions templates` used by numpy internal representation enable laziness computation. It means that operations will be computed only during assignation to avoid intermediate array allocation and improve data locality. Laziness analysis enable Expression template even if there is multiple assignment in some case.

Let’s go for some examples. In `foo`, no intermediate array are create for `+` and `*` operations and for each elements, two operations are apply at once instead of one by one:

    >>> def foo(array):
    ...     return array * 5 + 3

It also apply for other unary operations with numpy array. In this example, laziness doesn’t change anything as is it a typical case for Expression templates but peoples may write:

    >>> def foo(array):
    ...     a = array * 5
    ...     return a + 3

Result is the same but there is a temporary array. This case is detected as lazy and instead of saving the result of `array * 5` in `a`, we save an Expression template type `numpy_expr<operator*, ndarray, int>` instead of an evaluated `ndarray`.

Now, have a look at the lazyness analysis’s result:

    >>> foo_tree = getast(foo)
    >>> lazyness = pm.gather(analyses.LazynessAnalysis, foo_tree)

`array` is a parameter so even if we count use, it can’t be lazy:

    >>> lazyness['a']
    1

It returns the number of use of a variable.

Special case is for intermediate use:

    >>> def foo(array):
    ...     a = array * 2
    ...     b = a + 2
    ...     a = array * 5
    ...     return a, b

In this case, `b` is only use once BUT `b` depend on `a` and `a` change before the use of `b`. In this case, `b` can’t be lazy so its values is `inf`:

    >>> foo_tree = getast(foo)
    >>> lazyness = pm.gather(analyses.LazynessAnalysis, foo_tree)
    >>> sorted(lazyness.items())
    [('a', 1), ('array', 2), ('b', inf)]

We can notice that a reassignment reinitializes its value so even if `a` is used twice, its counters returns `1`. `inf` also happen in case of subscript use as we need to compute the value to subscript on it. Updated values can’t be lazy too and variables used in loops too. Laziness also cares about aliased values:

    >>> def foo(array):
    ...     a = array * 2
    ...     b = a
    ...     a_ = b * 5
    ...     return a_
    >>> foo_tree = getast(foo)
    >>> lazyness = pm.gather(analyses.LazynessAnalysis, foo_tree)
    >>> sorted(lazyness.items())
    [('a', 1), ('a_', 1), ('array', 1), ('b', 1)]

## Doc Strings

Pythran preserves docstrings:

    $> printf '#pythran export foo()\n\"top-level-docstring\"\n\ndef foo():\n  \"function-level-docstring\"\n  return 2' > docstrings.py
    $> pythran docstrings.py
    $> python -c 'import docstrings; print(docstrings.__doc__); print(docstrings.foo.__doc__)'
    top-level-docstring
    function-level-docstring

        Supported prototypes:

        - foo()
    $> rm -f docstrings.*

## PyPy3 support

Pythran has been said to work well with PyPy3.6 v7.2.0. However, this setup is not yet tested on Travis so compilation failure may happen. Report them!