MCP-0010: Reduction Filter

[modelica-trac-importer]

Modified by dietmarw on 28 Apr 2016 09:24 UTC
This is an MCP regarding implementation of filters (guards) for reduction iterators, in order to for example select only part of an array.

The document is stored at: ​

• https://svn.modelica.org/projects/MCP/public/MCP-0010_ReductionFilter/

Please use this ticket to comment on this MCP, in particular if you want to have one guard for each iterator or one for the whole reduction expression. Both have their pros and cons.

---

Modified by sjoelund.se on 13 Nov 2015 07:58 UTC
This is an MCPI regarding implementation of filters (guards) for reduction iterators, in order to for example select only part of an array.

The document is stored at: ​https://svn.modelica.org/projects/MCP/MAinternal/MCP-0010_ReductionFilter

Please use this ticket to comment on this MCPI, in particular if you want to have one guard for each iterator or one for the whole reduction expression. Both have their pros and cons.

---

Reported by sjoelund.se on 22 May 2014 08:07 UTC
This is an MCPI regarding implementation of filters (guards) for reduction iterators, in order to for example select only part of an array.

The document is stored at: ​https://svn.modelica.org/projects/MCP-Ideas/MAinternal/MCPI-0010_ReductionFilter

Please use this ticket to comment on this MCPI, in particular if you want to have one guard for each iterator or one for the whole reduction expression. Both have their pros and cons.

---

Migrated-From: https://trac.modelica.org/Modelica/ticket/1499

[modelica-trac-importer]

Modified by otter on 18 Sep 2015 10:14 UTC

[modelica-trac-importer]

Modified by otter on 18 Sep 2015 10:22 UTC

[modelica-trac-importer]

Modified by otter on 18 Sep 2015 10:23 UTC

[modelica-trac-importer]

Modified by sjoelund.se on 13 Nov 2015 07:58 UTC

[modelica-trac-importer]

Modified by dietmarw on 28 Apr 2016 09:24 UTC

[modelica-trac-importer]

Comment by hansolsson on 29 Apr 2016 08:09 UTC
Replying to [comment:1 choeger]:

* the general concept of comprehensions should be discussed. Comprehensions are a mature and widely accepted concept. The only Modelica specific task would be to define how to handle array-sizes (and even that is probably done elsewhere. See e.g. http://www.haskell.org/haskellwiki/List_comprehension

This got me thinking, and one thing I find missing in this discussion is a description of how comprehensions (with guards) are done in other languages - since I think that we need that perspective (and also for other MCPs).

Both in terms of details, and in terms of syntax, since the proposed scoping seems a bit odd (the iterator is introduced in the middle and used both to the left and right):

https://en.wikipedia.org/wiki/Comparison_of_programming_languages_(list_comprehension)

With guards I found the following (obviously there is more to consider):

• range, guard, expression: C# / Clojure / Cobra / F# / Ruby / Scala / Scheme / Windows Powershell
• expression, range, guard: CoffeeScript / Common Lisp / Erlang / Haskell / JavaScript / Python / Smalltalk
• expression, guard, range: Perl 6
• no easy way to describe: R

(Skipping languages I haven't heard before, and for Haskell see also http://wiki.haskell.org/List_comprehension - "several Haskell programmers consider the list comprehension unnecessary now" - using a range-guard-expression variant based on do-notation.)

However, I don't see a reason to switch syntax without guard at this point (but it would have been good to consider it earlier).

So the only alternative syntax would be Perl 6-like:
{2*j if mod(j,2)==0 for j in 1:10}
I'm not convinced that it is better, but I think we should consider it - and I believe it is as easy to parse, and semantically the effort should be the same.

[modelica-trac-importer]

Comment by cbuerger on 2 May 2016 12:06 UTC
The proposal can be decomposed in three problems: syntax of reduction filters, static semantics defining the scopes of introduced variables and dynamic semantics defining the order of the elements of the result and when constraints are applied.

Syntax

I see two general ideas for set comprehensions (I come to the order of elements, i.e., list comprehension, later when talking about the dynamic semantics).

1. starting from a set of values (seed set), stepwise reduce it by eliminating elements using constrains until finally the content of the new set can be stated
2. beginning from the computation defining the elements of the new set, stepwise define their domains in terms of restrictions followed by the original seed set

The first is kind of an algorithmic approach. First define the seed sets; afterwards nested loops iterate their elements. The body of the loops constrains them and constructs the new set. The second is a more mathematical notation. First what is in the new set, then the conditions when it is in the set, except that in mathematics you usually first state the general domain (similar to function definitions in mathematics, where also first the result and then the conditions are stated like in f(n) = n : n is odd, -n : n is even).

Both approaches have a clear reading direction: either from most general to specialised or the other way around.

I propose that any syntax should provide such a deterministic reading direction (no jumping like in C as required to read complex types like function pointers). Thus, I dislike for example:

          i+j for          i in M, j in N,           if i<10 and j<20
// content of new set         seed  set                 constraints
//  most constrained  =======> general  ============> more constrained

This form has no straight forward reading direction; neither from most constrained to least nor the other way around.

Given that the existing Modelica syntax prefers the second form (start with the actual elements of the new set), I would prefer the following syntax:

{         i+j for        all i<10 and j<20 with       i in M, j in N       }
// content of new set        constraints             list of seed sets
//  most constrained  =====> constrained ================> general

If there is no restriction the syntax stays as used to, for example:

{         i+j for                                     i in M, j in N       }
// content of new set       no constraints           list of seed sets
//  most constrained  ===================================> general

Above form introduces two new keywords: all and with. They start and end the optional reduction constraint of a reduction expression. Each reduction expression has at most one constraint, which must be a boolean expression. Optimisations of this expression, like its splitting, reordering and partially early evaluation to reduce for example the number of iterations of an internal loop implementation is up to the Modelica compiler and should not obfuscate the syntax.

I dislike the keyword guard as it sounds like an exception handling construct. What does an reduction expression guard against?

Static semantics (scopes)

I propose to avoid any kind of implicit nested scoping for the sake of concise and clear meaning. All looping variables should be within the scope of the reduction filter. Thus, I oppose that for example (taking the syntax from the draft)

{ i+j for  i guard i<10 in N,   j guard j<20 in M }

implicitly means

{ i+j for (i guard i<10 in N), (j guard j<20 in M) }

with ( and ) opening and closing implicit scopes. There should be no need for developers to consider the nesting of implicit scopes. In particular as inconsistent as in the proposal, where the actual element computation can see inside nested scopes but guards only see their scope (in above example i+j can see both local definitions whereas the guards only see their respective). This is hard to understand. It also complicates the refactoring of conditions. For example, if one would like to change the conditions from guard i<10 and guard j<20 to guard i<10 and j<i both filter conditions must be unified, moved and one guard deleted instead of just changing a single constraint.

To have a single scope per reduction expression goes well with having exactly a single reduction constraint and pushing responsibility for optimisation to the compiler.

Remember, that developers can always nest reduction expression when they want to compose complex reductions with nested scopes.

Dynamic semantics (order of elements)

Given above proposal (for all single-constraint-expression with), the order of the elements of result lists is straight forward (let's talk about lists from now on, i.e., seed lists, result list etc.).

A sequence of seed lists i in N, j in M is treated like:

for i in N
   for j in M
      if constraints satisfied
         compute and add element
      fi
   done
done

Element-wise reduction could be written as i in M; j in N, whereas M and N must be of the same size. Its meaning is:

if size(M) != size(N)
   abort with exception
fi
for index = 1 to size(M)
   i = M(index)
   j = N(index)
   if constraints satisfied
      compute and add element
   fi
done

Reductions of the same type -- only cross-product or only element-wise -- can be chained. The meaning of i in M, j in N, ..., k in O is:

for i in M
   for j in N
      ...
            for k in O
               if constraints satisfied
                  compute and add element
               fi
            done
      ...
   done
done

Similarly, the meaning of i in M; j in N; ...; k in O is:

if size(M) != size(N) != ... != size(O)
   abort with exception
fi
for index = 1 to size(M)
   i = M(index)
   j = N(index)
   ...
   k = O(index)
   if constraints satisfied
      compute and add element
   fi
done

It should be prohibited to mix cross-product and element-wise reductions. The rational is, that semantics for mixed-nested seed lists are hard to define and obscure:

1. Given above proposal, constraints are checked at the innermost loop. Although this is sufficient for sound semantics, it is not obvious for mixed-nested seed lists. For example, consider a reduction i in M; h in (j in N, k in O) with size(M) = 10 and size(N) + size(O) = 13 and filtered by a constraint c. The reduction can be defined or undefined (abort with exception) depending if c filters elements of the inner combination N, O before element-wise combining them with M or not. If 3 elements are filtered before combining element-wise, M; (N, O) is well-defined; otherwise not.

Instead, developers can explicitly nest reduction expressions:

{ outer-new-element for all first-constraint with
     i in M;
     h in { inner-new-element for all second-constraint with j in N, k in O } }

{ outer-new-element for all first-constraint and second-constraint with
     i in M;
     h in { inner-new-element for j in N, k in O } }

Of course, the generated code can be optimised; in the above example, the inner reduction could be checked and computed only once, caching the result for the outer reduction.

n>2-dimensional entities

I did not consider n>2 dimensional entities yet (matrices etc.). I consider this to be not so straight forward. Maybe a general decomposition concepts is needed for such (composition operators that define in which order to traverse dimensions).