Set algebra parser
Overview
Some components in the software offer manipulation of sets of data. In Polybench, these operations can be performed using standard Set Theory notation. This section describes the syntax of the set theory operators.In Polybench, a set means a well-determined collection of integer values (or natural numbers) that is listed comma-separated and between curly brackets, for example:
{1,2,3,4,5}
- or -
{8,10,12,14,16}
The values inside the curly brackets are called elements, and all the elements together is called a set.
Elements can also be mathematical expressions, for example {n-2, n-1, n}.
Polybench has limited understanding of sets that contain ellipsis symbols ('...'). For example:
{1,2,...,5} is interpreted as {1,2,3,4,5}
- or -
{8,...,14,16} is interpreted as {8,10,12,14,16}
Polybench is also able of doing operations on sets (A and B denote two different sets, like {2,3,4} and {3,4,5}):
- Union: A ∪ B; write as A u B: all elements in A or B, or both.
- Intersection: A ∩ B; write as A n B: all elements that are both in A and in B.
- Set difference: A - B; write as A - B: all elements in A that are not in B.
- Symmetric difference: A ⊖ B; write as A o B: all elements that are in A or in B, but not in both.
- Complement: A'; write as A': all elements that do not belong to A.
Details
Use of sets in Polybench
Sets in Polybench are mainly used to refer to collections of channels or values. Therefore, Polybench only recognizes sets with integer values (or even only natural numbers), where the value 1 refers to the first channel or value, 2 to the second, etc.Because sets are used within a well-defined context (in Set Theory also called a 'universe'), the ellipsis operator '...' will be limited by the context. In fact, the ellipsis will be used in cases where the number of channels or values is not known at the time of programming.
For example: a set refers to signal channels of an operator, but the number of channels is dynamic and can change during usage of the app. It is then possible to refer to the channels similar to:
{...} refers to all available channels
{...,5} refers to the first 5 channels
{n-4, n-3, n-2, n-1, n} refers to the last 5 channels (letter n has a special meaning)
{1,3,...,15,16,17} refers to the odd channels 1 to 15 and 16 and 17
{4,5,6}' refers to all channels except 4, 5, and 6 (note the complement-symbol)
Properties of a set in Polybench
- Polybench takes care that a set is always ordered from lowest to highest value- a set never contains duplicate values (duplicates are removed)
- Polybench takes care that a set is always finite. Although {1,2,...} may look like an infinite collection of values, there will be a context that limits the set
- a set may be empty ({})
- one or multiple ellipsis symbols ('...') are allowed
- elements must be integer values, or mathematical expressions that result in an integer
- the letter n indicates the highest possible value (inclusive upper limit)
Pattern recognition with the ellipsis symbol
In Set Theory, use of the ellipsis '...' is always interpreted in relation to the context of a set, otherwise the interpretation of the incomplete set is ambiguous. Because Polybench uses sets to mark items in lists, that context implies these rules:- only first order patterns are recognized:
{1,4,7,...} is recognized to be equal to {1,4,7,10,13,16,...}, but
{2,4,8,16,...} will be interpreted like {2,4,8,16,18,20,24,32,34,36,40,48,50,...}
{1,...,5} does not really show a pattern, but is interpreted as {1,2,3,4,5}
- a pattern can be either before or after the ellipsis, so {2,4,...10} is equal to {2,...,8,10}.
- a pattern around an ellipsis must be either increasing, or decreasing. {1,3,2,...,9} is incorrect, {1,2,3,...,9} is correct.
Set algebra
The commonly used Set Theory (best known for the Venn-diagram) offers a number of operators to manipulate sets. Of these operators, Polybench understands Union 'u', Intersection 'n', Set difference '-', Symmetric difference 'o', and Complement ''', as is described in the overview above.In one expression, multiple operations are allowed. The order of operations should be indicated by correct placement of parentheses '(' and ')'. If multiple operations are written in one expression, then each operation must be enclosed in parentheses. For example:
{1,2,3} n {2,3,4} u {3,4,5} is wrong. This should be either
({1,2,3} n {2,3,4}) u {3,4,5} or
{1,2,3} n ({2,3,4} u {3,4,5})
The Polybench set parser obeys to the general laws that Set Theory describes. Each law shows behind the official notation an example in Polybench notation. Examples should be read like in "{2,3,4} n {3,4,5} = {3,4}": The intersection of {2,3,4} and {3,4,5} by Polybench is equally interpreted as {3,4}.
Empty set laws
A ∩ ∅ = ∅; {2,3,4} n {} = {}
A ∪ ∅ = A; {2,3,4} u {} = {2,3,4}
Commutative laws
A ∩ B = B ∩ A; {2,3,4} n {3,4,5} = {3,4,5} n {2,3,4}
A ∪ B = B ∪ A; {2,3,4} u {3,4,5} = {3,4,5} u {2,3,4}
Associative laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C; {2,3,4} n ({3,4,5} n {4,5,6}) = ({2,3,4} n {3,4,5}) n {4,5,6}
A ∪ (b ∪ C) = (A ∪ B) ∪ C; {2,3,4} u ({3,4,5} u {4,5,6}) = ({2,3,4} u {3,4,5}) u {4,5,6}
Distributative laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); {2,3,4} n ({3,4,5} u {4,5,6}) = ({2,3,4} n {3,4,5}) u ({2,3,4} n {4,5,6})
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Without providing examples, the following laws also apply:
Idempotancy laws
A ∩ A = A
A ∪ A = A
Absorption laws
A ∩ (A ∪ B) = A
A ∪ (A ∩ B) = A
DeMorgan's laws
A - (B ∩ C) = (A - B) ∪ (A - C)
A - (B ∪ C) = (A - B) ∩ (A - C)
Parsing errors
To write down a set operation, many characters have to be typed, so many errors may occur. The Polybench set parser recognizes a few syntax errors that may result in an error code, in stead of the intended result set. These error codes may be displayed:SyntaxError: Syntax error, for example when multiple ellipsis symbols ('...') are placed in a row
SyntaxErrorNoBrackets: Syntax error, no curly brackets written, for example 1,2,3,...
SyntaxErrorNoLeftBracket: Syntax error, opening curly bracket missing
SyntaxErrorNoRightBracket: Syntax error, closing curly bracket missing
BadValue: Element cannot be parsed to an integer value
NoIncreasingOrDecreasingPattern: A pattern is not consistently increasing or decreasing, for example: {1,3,2,...}
AmbiguousPattern: There is neither limit nor pattern before the ellipsis
Examples
It may help to look at examples to get a feeling how Polybench interprets sets, patterns and set operations:{3,1,5,2,4} -> {1,2,3,4,5}
{2,4,...,11} -> {2,4,6,8,10}
{11,9,...,3} -> {3,5,7,9,11}
{2,4,5,...,12} -> {2,4,5,7,9,10,12}
{1,...,8,10} -> {2,4,6,8,10}
{11,...,5,3} -> {3,5,7,9,11}
{1,3,2,...,10} -> NoIncreasingOrDecreasingPattern
{1,1,...,10} -> NoIncreasingOrDecreasingPattern
{1,2,...,-10} -> {}
{1,...,-10,-9} -> {}
{1,1,1,1,1} -> {1}
{1,3,...,5,7} -> {1,3,5,7}
{1,2,...,3,4} -> {1,2,3,4}
{1,2,...,5,7} -> {1,2,3,4,5,7}
{5,...,1} -> {1,2,3,4,5}
{1,2,...,5,7,...,11} -> {1,2,3,4,5,7,8,9,10,11}
{1,2,...,5,7,9,...,13} -> {1,2,3,4,5,7,9,11,13}
{1,...,5,7,8,...,11} -> {1,3,5,7,8,9,10,11}
{1,...,5,...,-5} -> {-5,-4,-3,-2,-1,0,1,2,3,4,5}
{n - 3,...,n} in a collection {1,...,5} -> {2,3,4,5}
{n - 3,...,n} in a collection {8,...,10} -> {8,9,10}
{1,...,...,5} -> SyntaxError
{1,2,...,...,5} -> {1,2,3,4,5}
{1,2...,5} -> BadValue (note that a comma is missing)
1,2,...,5} -> SyntaxErrorNoLeftBracket
{3,7,9,14} u {9,14,28} -> {3,7,9,14,28}
{3,7,9,14} n {9,14,28} -> {9,14}
{1, 2, 3} o {2, 3, 4} -> {1,4}
({1, 2, 3}u{2, 3, 4}) - ({1, 2, 3}n{2, 3, 4}) -> {1,4}
({1, 2, 3}-{2, 3, 4}) u ({2, 3, 4}-{1, 2, 3}) -> {1,4}
{2,3,4}' -> {1,5,6} when 1 until 6 are available
{2,3,4}' u {2,3,4} -> {1,2,3,4,5,6} when 1 until 6 are available