.. module:: Base.Cartesian

.. _devdocs-cartesian:

Base.Cartesian
==============

The (non-exported) Cartesian module provides macros that facilitate
writing multidimensional algorithms. It is hoped that Cartesian will
not, in the long term, be necessary; however, at present it is one of
the few ways to write compact and performant multidimensional code.


Principles of usage
-------------------

A simple example of usage is::

    @nloops 3 i A begin
        s += @nref 3 A i
    end

which generates the following code::

    for i_3 = 1:size(A,3)
        for i_2 = 1:size(A,2)
	    for i_1 = 1:size(A,1)
                s += A[i_1,i_2,i_3]
	    end
	end
    end

In general, Cartesian allows you to write generic code that contains
repetitive elements, like the nested loops in this example.  Other
applications include repeated expressions (e.g., loop unwinding) or
creating function calls with variable numbers of arguments without using
the "splat" construct (``i...``).

Basic syntax
------------

The (basic) syntax of ``@nloops`` is as follows:

-  The first argument must be an integer (*not* a variable) specifying
   the number of loops.
-  The second argument is the symbol-prefix used for the iterator
   variable. Here we used ``i``, and variables ``i_1, i_2, i_3`` were
   generated.
-  The third argument specifies the range for each iterator variable. If
   you use a variable (symbol) here, it's taken as ``1:size(A,dim)``.
   More flexibly, you can use the anonymous-function expression syntax
   described below.
-  The last argument is the body of the loop. Here, that's what appears
   between the ``begin...end``.

There are some additional features of ``@nloops`` described in the
:ref:`reference section <devdoc-cartesian-reference>`.

``@nref`` follows a similar pattern, generating ``A[i_1,i_2,i_3]`` from
``@nref 3 A i``. The general practice is to read from left to right,
which is why ``@nloops`` is ``@nloops 3 i A expr`` (as in
``for i_2 = 1:size(A,2)``, where ``i_2`` is to the left and the range is
to the right) whereas ``@nref`` is ``@nref 3 A i`` (as in
``A[i_1,i_2,i_3]``, where the array comes first).

If you're developing code with Cartesian, you may find that debugging is
easier when you examine the generated code, using ``macroexpand``::

    julia> macroexpand(:(@nref 2 A i))
    :(A[i_1,i_2])


Supplying the number of expressions
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The first argument to both of these macros is the number of
expressions, which must be an integer. When you're writing a function
that you intend to work in multiple dimensions, this may not be
something you want to hard-code.  Perhaps the most straightforward
approach is to use the ``@ngenerate`` macro.

Perhaps the easiest way to understand ``@ngenerate`` is to see it in
action.  Here's a slightly cleaned up example::

    julia> macroexpand(:(@ngenerate N typeof(A) function mysum{T,N}(A::Array{T,N})
            s = zero(T)
            @nloops N i A begin
                s += @nref N A i
            end
            s
        end))
    :(begin
        function mysum{T}(A::Array{T,1}) # none, line 2:
            s = zero(T) # line 3:
            for i_1 = 1:size(A,1) # line 293:
                s += A[i_1]
            end # line 295:
            s
        end
        function mysum{T}(A::Array{T,2}) # none, line 2:
            s = zero(T) # line 3:
            for i_2 = 1:size(A,2) # line 293:
                for i_1 = 1:size(A,1) # line 293:
                    s += A[i_1,i_2]
                end # line 295:
            end # line 295:
            s
        end
        function mysum{T}(A::Array{T,3}) # none, line 2:
            s = zero(T) # line 3:
            for i_3 = 1:size(A,3) # line 293:
                for i_2 = 1:size(A,2) # line 293:
                    for i_1 = 1:size(A,1) # line 293:
                        s += A[i_1,i_2,i_3]
                    end # line 295:
                end # line 295:
            end # line 295:
            s
        end
        function mysum{T}(A::Array{T,4}) # none, line 2:
            ...
        end
        let mysum_cache = Dict{Int,Function}() # line 113:
            function mysum{T,N}(A::Array{T,N}) # cartesian.jl, line 100:
                if !(haskey(mysum_cache,N)) # line 102:
                    localfunc = quote
		        function _F_{T}(A::Array{T,$N})
                            s = zero(T)
                            @nloops $N i A begin
                                s += @nref $N A i
                            end
                            s
                        end
                    end
		    mysum_cache[N] = eval(quote
                        local _F_
                        $localfunc
                        _F_
                    end)
                end
                mysum_cache[N](A)::typeof(A)
            end
        end
    end)

You can see that ``@ngenerate`` causes explicit versions to be
generated for dimensions 1 to 4 (a setting controlled by the constant
``CARTESIAN_DIMS``).  To allow arbitrary-dimensional arrays to be
handled, it also generates a version in which different methods are
cached in a dictionary.  If a given method has not yet been generated,
it creates a version specific to that dimensionality and then stores
it in the dictionary.  Creating the method is slow---it involves
generating expressions and then evaluating them---but once created the
function can be looked up from the cache, and is reasonably efficient
(but still less efficient than the versions generated for explicit
dimensionality).

The arguments to ``@ngenerate`` are:

- The symbol of the variable that will be used for generating
  different versions (in the example, ``N``)
- The return type of the function (in the example,
  ``typeof(A)``). This is not used for the versions that are generated
  for specific ``N``, but is needed for the dictionary-backed
  version.  Julia cannot infer the return type of the function looked
  up from the dictionary.
- The actual function declaration.  Use ``N`` as you would a normal
  parameter.


Anonymous-function expressions as macro arguments
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Perhaps the single most powerful feature in ``Cartesian`` is the
ability to supply anonymous-function expressions that get evaluated at
parsing time.  Let's consider a simple example::

    @nexprs 2 j->(i_j = 1)

``@nexprs`` generates ``n`` expressions that follow a pattern. This
code would generate the following statements::

    i_1 = 1
    i_2 = 1

In each generated statement, an "isolated" ``j`` (the variable of the
anonymous function) gets replaced by values in the range ``1:2``.
Generally speaking, Cartesian employs a LaTeX-like syntax.  This
allows you to do math on the index ``j``.  Here's an example computing
the strides of an array::

    s_1 = 1
    @nexprs 3 j->(s_{j+1} = s_j * size(A, j))

would generate expressions
::

    s_1 = 1
    s_2 = s_1 * size(A, 1)
    s_3 = s_2 * size(A, 2)
    s_4 = s_3 * size(A, 3)

Anonymous-function expressions have many uses in practice.

.. _devdoc-cartesian-reference:

Macro reference
~~~~~~~~~~~~~~~

Macros for creating functions
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. function:: @ngenerate Nsym returntypeexpr functiondeclexpr

    Generate versions of a function for different values of ``Nsym``.

.. function:: @nsplat Nsym functiondeclexpr
              @nsplat Nsym dimrange functiondeclexpr

    Generate explicit versions of a function for different numbers of
    arguments.  For example::

        @nsplat N 2:3 absgetindex(A, I::NTuple{N,Real}...) = abs(getindex(A, I...))

    generates::

        absgetindex(A, I_1::Real, I_2::Real) = abs(getindex(A, I_1, I_2))
        absgetindex(A, I_1::Real, I_2::Real, I_3::Real) = abs(getindex(A, I_1, I_2, I_3))


Macros for function bodies
^^^^^^^^^^^^^^^^^^^^^^^^^^

.. function:: @nloops N itersym rangeexpr bodyexpr
              @nloops N itersym rangeexpr preexpr bodyexpr
              @nloops N itersym rangeexpr preexpr postexpr bodyexpr

    Generate ``N`` nested loops, using ``itersym`` as the prefix for
    the iteration variables. ``rangeexpr`` may be an
    anonymous-function expression, or a simple symbol ``var`` in which
    case the range is ``1:size(var,d)`` for dimension ``d``.

    Optionally, you can provide "pre" and "post" expressions. These
    get executed first and last, respectively, in the body of each
    loop. For example,
    ::

        @nloops 2 i A d->j_d=min(i_d,5) begin
            s += @nref 2 A j
        end

    would generate
    ::

        for i_2 = 1:size(A, 2)
            j_2 = min(i_2, 5)
            for i_1 = 1:size(A, 1)
                j_1 = min(i_1, 5)
                s += A[j_1,j_2]
            end
        end

    If you want just a post-expression, supply
    ``nothing`` for the pre-expression. Using parenthesis and
    semicolons, you can supply multi-statement expressions.

.. function:: @nref N A indexexpr

    Generate expressions like ``A[i_1,i_2,...]``.  ``indexexpr`` can
    either be an iteration-symbol prefix, or an anonymous-function
    expression.

.. function:: @nexprs N expr

    Generate ``N`` expressions. ``expr`` should be an
    anonymous-function expression.

.. function:: @ntuple N expr

    Generates an ``N``-tuple.  ``@ntuple 2 i`` would generate ``(i_1, i_2)``, and ``@ntuple 2 k->k+1`` would generate ``(2,3)``.

.. function:: @nall N expr

    ``@nall 3 d->(i_d > 1)`` would generate the expression
    ``(i_1 > 1 && i_2 > 1 && i_3 > 1)``. This can be convenient for
    bounds-checking.

.. function:: @nif N conditionexpr expr
              @nif N conditionexpr expr elseexpr

    Generates a sequence of ``if ... elseif ... else ... end`` statements. For example::

        @nif 3 d->(i_d >= size(A,d)) d->(error("Dimension ", d, " too big")) d->println("All OK")

    would generate::

        if i_1 > size(A, 1)
	    error("Dimension ", 1, " too big")
        elseif i_2 > size(A, 2)
	    error("Dimension ", 2, " too big")
        else
	    println("All OK")
	end


Frequently asked questions
^^^^^^^^^^^^^^^^^^^^^^^^^^


I got an error ``ERROR: N not defined`` when using ``@ngenerate``. Why?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Most likely you forgot to define your function with ``N`` as a type parameter, e.g., ``@ngenerate N returntype myfunc{N}(...)``.