User Tools

Site Tools


polca_language_definition

This page collects the set of annotations of the POLCA programming model.

General Syntax

The approach is based on the use of compiler pragmas to annotate the original C code, as this is a rather unobtrusive option for the programming model. All POLCA annotations start with #pragma polca followed by the information that is needed. We have defined the POLCA annotation syntax to avoid having long lines with too much information in the same directive. We have considered that splitting the information in several lines makes the syntax more scalable, easy to read (and write) and also simplifies the parsing process. For this reason each statement (or group of statements) in the program can be annotated by none or more annotations:

#pragma polca <polca_ann>

where

<polca_ann> ::= <def_ann> | <io_ann> | <kernel_ann> | <adapt_ann> | <func_ann> | <mem_ann> | <varinfo_ann> | <math_ann> | <hardwareio_ann> | <guard_ann> | <smath>

The different <polca_ann> options determine the kind of information that the directive is going to express about the referenced code statement. The details of each of this options are explained in the next sections of this chapter.

POLCA Definition

POLCA definition annotation allows statements to receive a unique user defined name (except in case of the kernels, where equivalent kernels for different destination platforms must share the name) so that later they can be referred from other annotations. This name is used to refer to this statement from other annotations and create a well-defined and non-ambiguous binding.

Group of statements can also be annotated by grouping them between curly brackets. Annotations placed just before the header of a function are applied to the whole function.

<def_ann> ::= "def" <polca_var_id>

where

<polca_var_id> ::= <identifier>

The next code exemplifies how to name a C single statement, a group of statements or a C function where A) annotates a single statement, B) a group of statements and C) a function.

A)
#pragma polca def ADD
  x = x + y;
 
B)
#pragma polca def INIT
{
  x = 0;
  y = N;
  ...    // Some C code
}
 
C)
#pragma polca def FUNC
int myFunc(int val) {
  ...    // Some C code
}

Input / Output Parameters

Input / Output parameters allow the programmer to explicitly indicate the POLCA tool box which are the parameters that have to be considered relevant input and output for a given statement. The Input / Output parameters have to be correctly identified for the tool to create the correct data dependency graph and perform correct transformations.

<io_ann> ::= "input" <io_var_list> | "output" <io_var_list> | "inout" <io_var_list>

where <io_var_list> is a list of existing procedural code variables.

The next code exemplifies how C statements can be annotated with respect to their I/O properties.

A)
#pragma polca input y
#pragma polca inout x
  x = x + y;
 
B)
#pragma polca output x y
{
  x = 0;
  y = N; // N is a constant
}

Functions can also be annotated with respect to their data I/O. Not only the variables (and memory locations) that are passed as arguments should be in the annotations but also those that are relevant and are available by other means (i.e. global variables, pointer indirections, etc.).

The next code shows a function annotated. When called as shown in A) the return value of the function is considered output, while in B) the return value is ignored and not considered as output value of the function.

#pragma polca input val
int myFunc(int val) {
  ...
}
 
A)
#pragma polca output val
int val = myFunc(x);
 
B)
myFunc(x); // return value is ignored

POLCA Kernels

POLCA Kernels are defined by giving the specific destination platform characteristics of the kernel code (in some cases it can be a list as some parameters are not mutually exclusive, e.g. x86-64 and AVX are compatible while ARM-v8 and AVX would not be a valid combination as the AVX instructions are only available in some x86-64 CPUs. In case that many equivalent Kernels are provided for different destination platforms, the user given name to the statement has to be exactly the same.

<kernel_ann> ::= "kernel" <platform_list>
<platform_list> ::= <platform> | <platform_list> <platform> 

<platform> ::= "" | "maxj" | "opencl" | "avx" | "x86-64" | "ARM-v8" | ...

The different platforms allowed by <platform> is not limited to the options shown in this document and will be updated with new platforms as the tool evolves. An empty list means “generic code” or the code that should be used and transformed accordingly if not suitable specific code is found for the destination hardware platform. The data input/output for each equivalent kernel definition has to be the same.

The following code exemplifies the usage of kernel definitions where A) is an OpenCL specific kernel while B) is the generic alternative kernel.

A)
#pragma polca def myKernel
#pragma polca kernel opencl
#pragma polca inout val1, val2
{
  ...
}
 
B)
#pragma polca def myKernel
#pragma polca kernel
#pragma polca inout val1, val2
{
...
}

Explicit Adaptation

Explicit Adaptation annotations allow the programmer to hardcode into the source code the destination platforms that an specific segment of code has to be adapted to without the need to do it interactively with the toolbox. A list can be provided if it should be adapted to different destination platforms.

<adapt_ann> ::= "adapt" <adapt_platform_list>

where

<adapt_platform_list> ::= <adapt_platform> | <adapt_platform_list> <adapt_platform> 

<adapt_platform> ::= "maxj" | "opencl" | "mpi" | "openmp" | ...

The different platforms allowed by <adapt\_platform> is not limited to the options shown in this document and will be updated with new platforms as the tool evolves. The following listing shows a snippet on how to use this annotation.

#pragma polca adapt opencl, openmp
#pragma polca inout val1, val2
{
  ...
}

Functional Annotations

Functional Annotations are Higher-Order Functions (HOFs) used to describe the application mathematical behaviour and execution structure.

<func_ann> ::= "func" <func>

<func> ::= <itn> | <itb> | <map> | <zipWith> | <foldl> | <scanl> | <stencil1D> | <stencil2D> | ...

Non-Terminal <itn> symbol is defined as:

<itn> ::= "itn" <polca_var_id> <func_in_data> <func_parameter> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with one input parameter and one output parameter, both of the same type.
  • <func_in_data>: the initial data.
  • <func_parameter>: the number of times the operation has to be executed.
  • <func_out_data>: the element where the execution output is stored.
int i;
float a = 1.234f;
 
#pragma polca itn OPER a N_ITER a
for(i=0; i<N_ITER; ++i) {
#pragma polca def OPER
#pragma polca inout a
  a = someFunc(a);
}

<itn> execution structure:

<itn> execution structure

Non-Terminal <itb> symbol is defined as:

<itb> ::= "itb" <polca_var_id> <func_in_data> <boolean_expression> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with one input parameter and one output parameter, both of the same type.
  • <func_in_data>: the initial data.
  • <boolean_expression>: a boolean expression that when resolved true a new iteration will be executed.
  • <func_out_data>: the element where the execution output is stored.
int i;
float a = 1.234f;
 
#pragma polca itn OPER a (a>0) a
while(a>0) {
#pragma polca def OPER
#pragma polca inout a
  a = someFunc(a);
}

Non-Terminal <map> symbol is defined as:

<map> ::= "map" <polca_var_id> <func_in_data> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with one input parameter and one output parameter, which can be of different type.
  • <func_in_data>: the initial data array.
  • <func_out_data>: the array where the execution output is stored.
int i;
float a[N_ELEM] = {...}; // Initialization
float b[N_ELEM];
 
#pragma polca map OPER a b
for(i=0; i<N_ELEM; ++i) {
#pragma polca def OPER
#pragma polca input a[i]
#pragma polca output b[i]
  b[i] = someFunc(a[i]);
}

<map> execution structure:

<map> execution structure

Non-Terminal <zipWith> symbol is defined as:

<zipWith> ::= "zipWith" <polca_var_id> <func_in_data> <func_in_data> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with two input parameter and one output parameter, which can be of different type.
  • <func_in_data>: first input data array.
  • <func_in_data>: second input data array.
  • <func_out_data>: the array where the execution output is stored.
int i;
float a[N_ELEM] = {...}; // Initialization
float b[N_ELEM] = {...}; // Initialization
float c[N_ELEM];
 
#pragma polca zipWith OPER a b c
for(i=0; i<N_ELEM; ++i) {
#pragma polca def OPER
#pragma polca input a[i] b[i]
#pragma polca output c[i]
  c[i] = someFunc(a[i], b[i]);
}

<zipWith> execution structure:

<zipWith> execution structure

Non-Terminal <foldl> symbol is defined as:

<foldl> ::= "foldl" <polca_var_id> <func_in_data> <func_in_data> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with two input parameter and one output parameter, the first input parameter and the output data type have to be the same, while the second parameter can be a different one.
  • <func_in_data>: the initial data (single element).
  • <func_in_data>: an array of data.
  • <func_out_data>: the element where the execution output is stored.
int i;
float a[N_ELEM] = {...}; // Initialization
float b = 1.234f;
 
#pragma polca foldl OPER b a b
for(i=0; i<N_ITER; ++i) {
#pragma polca def OPER
#pragma polca input b a[i]
#pragma polca output b
  b += a[i]
}

<foldl> execution structure:

<foldl> execution structure

Non-Terminal <scanl> symbol is defined as:

<scanl> ::= "scanl" <polca_var_id> <func_in_data> <func_in_data> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with two input parameter and one output parameter, the first input parameter and the output data type have to be the same, while the second parameter can be a different one.
  • <func_in_data>: the initial data (single element).
  • <func_in_data>: an array of data.
  • <func_out_data>: the element where the execution output is stored.
int i;
float a[N_ELEM] = {...}; // Initialization
float b[N_ELEM+1] = {...}; // Initialization
float b[0] = 1.234f;
 
#pragma polca scanl OPER b[0] a b
for(i=0; i<N_ITER; ++i) {
#pragma polca def OPER
#pragma polca input b[i] a[i]
#pragma polca output b[i+1]
  b[i+1] = a[i] + b[i]
}

<scanl> execution structure:

<scanl> execution structure

Non-Terminal <stencil1D> symbol is defined as:

<stencil1D> ::= "stencil1D" <polca_var_id> <func_parameter> <func_in_data> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with one input parameter and one output parameter, both of the same type.
  • <func_parameter>: width of the stencil window to each side.
  • <func_in_data>: the initial data array.
  • <func_out_data>: the element where the execution output is stored.
int i;
float a[N_ELEM] = {...}; // Initialization
float b[N_ELEM];
 
#pragma polca stencil1D OPER 1 a b
for(i=1; i<N_Elem-1; ++i) {
#pragma polca def OPER
#pragma polca input a[i-1] a[i] a[i+1]
#pragma polca output b[i]
  b[i] = someFunc(a[i-1], a[i], a[i+1]);
}

<stencil1D> execution structure:

<stencil1D> execution structure

Non-Terminal <stencil2D> symbol is defined as:

<stencil2D> ::= "stencil2D" <polca_var_id> <func_parameter> <func_parameter> <func_in_data> <func_out_data>

The different parameters represent in order of appearance:

  • <polca_var_id>: is the name given to a group of statements that behave as the operator for the HOF, with one input parameter and one output parameter, both of the same type.
  • <func_parameter>: width of the stencil horizontal window to each side.
  • <func_parameter>: width of the stencil vertical window to each side.
  • <func_in_data>: the initial data matrix.
  • <func_out_data>: the element where the execution output is stored.
int i, j;
float a[N_ELEM_H, N_ELEM_W] = {...}; // Initialization
float b[N_ELEM_H, N_ELEM_W];
 
#pragma polca stencil2D OPER 1 1 a b
for(j=1; j<N_Elem_H-1; ++j) {
  for(i=1; i<N_Elem_W-1; ++i) {
#pragma polca def OPER
#pragma polca input a[j-1,i] a[j,i-1] a[j,i] a[j,i+1] a[j+1,i]
#pragma polca output b[i]
    b[j,i] = someFunc(a[j-1,i], a[j,i-1], a[j,i], a[j,i+1], a[j+1,i]);
  }
}

where func_parameter is defined as:

<func_parameter> ::= <C_location> | <polca_var_id> | <INT>

and

<func_in_data> ::= <func_parameter> | (<func_ann>) | (<func_helper>)

and

<func_out_data> ::= <C_location>

Helper Functions

Helper Functions directives are used to introduce functions that perform some organizative manipulation on the data, i.e., they do not perform operations or change the values of the data, but change their organization in memory. This family of annotations can be extended in future versions of the POLCA programming model as required for future examples and use cases.

<func_helper> ::= <splitEvery> | <zip> | <transpose> | ... 

Non-Terminal <splitEvery> symbol is defined as:

<splitEvery> ::= "splitEvery" <func_parameter> <func_in_data> <func_parameter>

It transform an array of data in an array of arrays of size determined by the first parameter. The second parameter is the original array and the third parameter is the resulting array of arrays. Although this annotation can be used by developers it is designed to be used by the toolbox to re-annotate the code while performing transformations.

Non-Terminal <zip> symbol is defined as:

<zip> ::= "zip" (<C_location_list>)

It allows to create a tuple to join a set of variables into a single one so that functions that in principle only take one input parameter can take more without breaking the input pattern. The next Listing shows how to use the <zip> annotation to enable the usage of an operator with 3 inputs in a foldl HOF, that in principle only accepts operators with two input parameters.

t = 0;
#pragma polca foldl MULADD t (zip(u v)) t
for(i = 0; i < NELEM; i++) {
#pragma polca MULADD
#pragma polca input t u[i] v[i]
#pragma polca output t
  t += u[i] * v[i] 
}

Non-Terminal <transpose> symbol is defined as:

<transpose> ::= "transpose" (<C_location>)

The transpose annotation allows for the logical algebraic transpose of a 2D array. This annotation is important to keep the consistency of functional POLCA annotations when the row/column indexes of a matrix are exchanged in the C code. The following Listing shows how to use the <transpose> annotation.

int a[N][M];
int b[M][N];
int c[N][M];
 
#pragma polca map f zip(a, transpose(b)) c
for(int j=0; j<N; j++) {
  for(int i=0; i<M; i++) {
#pragma polca def f
#pragma polca input a[i][j] b[j][i]
#pragma polca output c[i][j]
#pragma polca smath (a[i][j] + b[j][i]) c[i][j]
    c[i][j] = a[i][j] + b[j][i];
  }
}

Simple Math

Simple Math directives are used to introduce first order mathematical functions so that the code can be reformulated and/or to allow the offloading to accelerators.

<smath> ::= smath (<math_expr) | smath (<math_expr) <C_location>

where

<math_expr> ::= <math_term> + <math_expr> | <math_term> - <math_expr> | <math_func> | <math_term>
<math_expr_list> :: <math_expr> | <math_expr_list> <math_expr>
<math_term> ::= <math_factor> * <math_term> | <math_factor> / <math_term> | <math_factor>^<math_term> | <math_factor> \% <math_term> | <math_factor> 
<math_factor> ::= (<math_expr>) | <c_number> | <c_var> | <c_location>

The term <C\_location> indicates the location where the result is stored. In case this annotation affects the whole function it can be omitted as the location will be the result of evaluating the function.

The following Listing shows an example on how to use the <smath> annotation. In this case the annotation and the actual source code represent the same expression under different formulations.

#pragma polca smath ((x-y)^2) z
#pragma polca input x y
#pragma polca output z
{
  z = (x-y)*(x-y);
}

Simple Math Functions

Simple Math Functions express mathematical functions to be used within the Simple Math annotations. This kind of information is often difficult to be extracted by analysis of the code.

<math_func> ::= sqrt(<math_expr>) | avg(<math_expr_list>) | min(<math_expr_list>) | max(<math_expr_list>) | ...

where

  • sqrt(<math_expr>) is the square root of a <math_expr>, the data type does not need to be explicitely determined, i.e. the same annotation can be used for the functions sqrt or sqrtf from the math.h library or any user's custom version
  • avg(<math_expr_list>) is the average value of a list of <math_expr>
  • min(<math\_expr\_list> is the element with the minimum value of a list of <math_expr>
  • max(<math\_expr\_list> is the element with the maximum value of a list of <math_expr>
  • other Simple Math Functions extended by users

The POLCA syntax allows for the extension of the Simple Math semantics as needed in the future by the different users. In the current definition of the POLCA syntax and semantics a small set of these functions have been defined to exemplify on how to use them and to be used in the use cases selected for the evaluation of the POLCA project. Further development of POLCA allows for the extension of these functions as needed by future users.

The next Listing shows the code an annotation of a set of C statements that perform the calculation of two square roots on two different types and add the respective results.

#include <math.h>
 
double pid = 3.1415926536;
float  ef  = 2.71828;
double result;
 
#pragma polca input pid ef
#pragma polca output result
#pragma polca smath(sqrt(pi) + sqrt(ef));
{
  result = sqrt(pid) + sqrtf(ef);
}

The code in the following Listing shows the use of the <avg> function, where the average of all the elements of an array is calculated.

#define SIZE ...
int a[SIZE];
int average;
 
for(int i=0; i<SIZE; i++) {
  a[i] = random(0, 100);
}
 
#pragma polca input a
#pragma polca output average
#pragma polca smath(avg(a))
{
  average = 0;
  for(int i=0; i<SIZE; i++) {
    average += a[i];
  }
  average = average/SIZE;
}

The next Listing shows three usage examples of the <min> function (the usage of the <max> function is equivalent). The first function calculates the minimum of two elements, the second function calculates the minimum of three elements (using the implementation of the previous function), and the third example calculates the minimum of the elements of an array with at least one element, using the implementation of the first function.

#pragma polca input a b
#pragma polca smath(min(a, b))
int function min(int a, int b) {
  if(a < b)
    return a;
  else
    return b;
}
 
#pragma polca input a b c
#pragma polca smath(min(a, b, c))
int function min3(int a, int b, int c) {
  return min(a, min(b, c));
}
 
#pragma polca input a
#pragma polca smath(max(a))
int function minArray(int* a, int sizea) {
  int m = a[0]
  for(int i=1; i<sizea; i++) {
    m = min(m, a[i]);
  }
  return m;
}

Variable Information

Variable Information are used to give properties to variables. It is similar to the malloc annotations but can be used for memory that is not allocated dynamically through system calls, such as when they are allocated in the stack when a function is called.

<varinfo_ann> ::= "varinfo" <type_size> <total_size> | "varinfo" <type_size>

<type_size> ::= <C_VAR> | <C_EXP>

<total_size> ::= <C_VAR> | <C_EXP>

The <type_size> symbol is used to give the size of the individual data elements in bytes and <total_size> to determine the number of elements.

The following Listing shows how to annotate an array (contiguous region of memory with many elements of the same type) and a single memory element, in this case a C struct that internally may hold different elements.

struct myStruct {
  ...
};
 
void func() {
#pragma polca varinfo sizeof(int) N
  int myArray[N]; // N is a defined constant
 
#pragma polca varinfo sizeof(struct myStruct)
  struct myStruct somestruct;
 
  ... // Function code
}

Mathematical Properties

Mathematical Properties annotations are used to give the toolbox information about the mathematical properties of the variables and the transformations that can be performed with them according to mathematical laws. At the current moment we have defined the possibility of annotating ring structures due to their ubiquity.

<math_ann> ::= <ring_ann> | ...

The template for ring annotations is:

<ring_ann> ::= "ring" (<add_op>, <add_neutral>, <add_inverse>, <mult_op>, <mult_neutral>)  | "ring" (<add_op>, <add_neutral>, <add_inverse>, <mult_op>, <mult_neutral>) <data_type>

where

<add_op> ::= <operation>
<mult_op> ::= <operation>
<operation> ::= <polca_var_id> | + | - | * | \
<add_neutral> ::= <neutral_element>
<mult_neutral> ::= <neutral_element>
<neutral_element> ::= <C_location> | <polca_var_id> | <INT> | <FLOAT>
<add_inverse> ::= <polca_var_id> | + | - | * | \
<data_type> ::= <identifier>

The different parameters represent, in order of appearance:

  • <add_op> is the additive operation of the ring. It can be a predefined operator, a C function name or a POLCA identifier given to a group of statements.
  • <add_neutral> is the value of the neutral element for the additive operation.
  • <add_inverse> is the inverse operation for the additive operation of the ring.
  • <mult_op> is the multiplicative operation of the ring.
  • <mult_neutral> is the value of the neutral element for the multiplicative operation.
  • <data_type> (optional) is a valid data type used by the operators, which has to be specified if the operations are overloaded.

The next Listing shows two examples of ring annotation. In A) the predefined arithmetic operators are annotated to be a ring, but only for their instantiation on floats. In B) a ring of square matrices is declared by providing a set of functions and constants.

A)
#pragma polca ring ('+', 0.0f, '-', '*', 1.0f) float
 
B)
#pragma polca ring (mat_add, null_matrix, mat_sub, mat_mul, id_matrix)

Memory

Memory annotations allow the POLCA toolbox to understand the memory handling of the procedural code and this way be able to correctly perform the desired transformations.

<mem_ann> ::= <mem_alloc> | <mem_calloc> | <mem_realloc> | <mem_free> | <mem_copy>

Allocation – Non-Terminal <alloc> symbol is used to indicate how the memory is reserved in memory. The first parameter is the size of the elements to be allocated in bytes, the second parameter is the amount of those elements and the third parameter is the pointer in the procedural code that will point to the new allocated section of memory.

<mem_alloc> ::= "alloc" <mem_parameter> <mem_parameter> <mem_parameter>

Zero Allocation – Non-Terminal <calloc> symbol is used to indicate how zero-initialized memory is reserved in memory. The first parameter is the size of the elements to be allocated –in bytes–, the second parameter is the amount of those elements and the third parameter is the pointer in the procedural code that will point to the new allocated section of memory.

<mem_calloc> ::= "calloc" <mem_parameter> <mem_parameter> <mem_parameter>

ReAllocation – Non-Terminal <realloc> annotation allows to resize a contiguous section of memory. The first parameter is the pointer to the original memory location, the second parameter is the size of the elements allocated –in bytes–, the third parameter indicates the amount of those elements and the forth parameter is the pointer in the procedural code that will point to the new allocated section of memory.

<mem_realloc> ::= "realloc" <mem_parameter> <mem_parameter> <mem_parameter> <mem_parameter>

Free (De-Allocation) – Non-Terminal <free> annotations are used to indicate when a certain region of memory that was previously allocated is freed. The parameter of this annotation is the pointer to the previously allocated memory.

<mem_free> ::= "free" <mem_parameter> 

Copy – Non-Terminal <copy> annotation is used to indicate when the content of set of contiguous memory locations are copied into another memory locations. The first parameter is the pointer to the original memory location, the second parameter is the size of the elements allocated –in bytes–, the third parameter indicates the amount of those elements to be copied and the forth parameter is the pointer in the procedural code that points to the memory location where the data is copied.

<mem_copy> ::= "copy" <mem_parameter> <mem_parameter> <mem_parameter> <mem_parameter>

where

<mem_parameter> ::= <C_location> | <polca_var_id> | <INT>

Hardware Input / Output

Hardware Input / Output annotations allow the programmer to indicate the POLCA toolbox that hardware input / output operations are happening (such as writing to the file system or printing to screen) so certain considerations to maintain correctness and order of this operations should be taken when applying transformations, such as keeping order of writing to a file or other conditions that may lead to race conditions or wrong results, or because the necessary I/O hardware can only be accessed with certain restrictions (e.g. the screen or keyboard are only attached to a certain node of a distributed system).

<hardwareio_ann> ::= "io"

The next Listing shows how to apply this annotation to a printf system call for printing on screen. It can also be used to annotate a group of statements that hold hardware I/O operations.

int var;
 
... // some code that writes on var
 
#pragma polca io
printf("Variable Value: %d\n", var);

Boolean Expressions

Boolean Expressions are logical statements that are evaluated as either true or false. In the context of POLCA they are use by the guards as a way of testing whether some property of a value (or several of them) are true or false and act accordingly.

<boolean_expression> ::= (<boolean_expression>) | <unary_negation> | <logical-or-expression> | <logical_and_expression> | <equality_expression> | <inequality_expression> | <relational_expression_lt> | <relational_expression_gt> | <relational_expression_let> | <relational_expression_get> |  <C_location>

where

<unary_negation> ::= "!" <boolean_expression>

is an unary arithmetic operator as defined in the Chapter 6.5.3.3 of the C99 Standard and where

<logical_and_expression> ::= <boolean_expression> "&&" <boolean_expression>

is a logical AND operator as defined in the Chapter 6.5.13 of the C99 Standard and where

<logical_or_expression> ::= <boolean_expression> "||" <boolean_expression>

is a logical OR operator as defined in the Chapter 6.5.14 of the C99 Standard and where

<relational_expression_lt> ::= <boolean_expression> "<" <boolean_expression>
<relational_expression_gt> ::= <boolean_expression> ">" <boolean_expression>
<relational_expression_let> ::= <boolean_expression> "<=" <boolean_expression>
<relational_expression_get> ::= <boolean_expression> ">=" <boolean_expression>

are relational operators as defined in the Chapter 6.5.8 of the C99 Standard and where

<equality_expression> ::= <boolean_expression> "==" <boolean_expression>
<inequality_expression> ::= <boolean_expression> "!=" <boolean_expression>

are equality operators as defined in the Chapter 6.5.9 of the C99 Standard.

Control structures

Control structures allow for expressing a choice between different values or actions. C language and Haskell, the functional base of POLCA, have means to determine what actions to take under certain conditions. The POLCA branching mechanism is based on Haskell style guards, in which the parameter a condition statement condX depending on the parameter a which is an input parameter to function f is evaluated and when True the corresponding statementX is evaluated.

f :: A -> B
f a
  | cond1(a)  = expression1
  | cond2(a)  = expression2
  | otherwise = expression3

Recall that guards are evaluated in the order they appear and that otherwise is just an alias to True, and thus the last guard is a catch-all, playing the role of the final else of the if expression. In POLCA the input and output parameters for the statement of each guard has to be identical.

The POLCA guards can be easily matched with C-style if-then-else statements as shown in the next Listing.

#pragma polca guard(cond1(a) : s1; cond2(a) : s2; otherwise : s3)
if(cond1(a)) {
#pragma polca def s1
  statement1;
}
else if (cond2(a)) {
#pragma polca def s2
  statement2;
}
else {
#pragma polca def s3
  statement3;
}

Or in case that all the conditions are a comparison with an specific value it can also be converted into a C-style switch statement as shown in the next Listing.

#pragma polca guard(a == N : s1; a == M : s2; otherwise : s3)
switch(a) {
  N:
#pragma polca def s1
    statement1;
    break;
  M:
#pragma polca def s2
    statement2;
    break;
  default:
#pragma polca def s3
    statement3;
    break;
}
<guard_ann> ::= "guard" <guard_data>

where

<guard_data> ::= "(" <guard_list> ")"
<guard_list> ::=  <guard_param> | <guard_param> ";" <guard_list>
<guard_param> ::= <guard_cond_list> ":" <guard_statement_list>

<guard_cond_list> ::=  <boolean_expression> | <boolean_expression> "," <guard_cond_list>
<guard_statement_list> ::= <guard_statement> | <guard_statement> "," <guard_statement_list>
<guard_statement> ::= <polca_var_id>

The <c_array>

The <c_array>, which are part of the annotation grammar, describe a contiguously allocated nonempty set of objects with a particular member object type (as defined in the Chapter 6.2.5 of the C99 Standard) and is expressed as

<C_array> ::= <C_VAR>"["<C_EXP>"]" | <C_VAR>"["<C_EXP>","<C_EXP>"]"

The POLCA annotations can refer to C-arrays when the toolbox is aware of the size and amount of elements that are being stored in them. To achieve this the arrays have to be declared statically or annotated with the memory annotations when declared dynamically.

The next Listing shows the annotated code of two arrays b and c declared statically and then all the values of b copied into c at the same positions. Note that the POLCA annotations do not need to be specified any ranges as this implies the whole array length.

int b[N]
int c[N]
 
...
 
#pragma polca map f b c
for(int i=0; i<N; i++) {
#pragma polca def f
  c[i] = b[i];
}

But sometimes it will not be possible to always use “whole” arrays because we are only interested in certain sections of it, or because we are operating on different arrays with different sizes each.

An example of this is shown in the next Listing where the array a is twice as big as the arrays b or c. This code is annotated to copy the lower-half of the array a to the whole array b and then copy the higher-half of the array a to the whole array c.

int a[2*N]
int b[N]
int c[N]
 
...
 
#pragma polca map f a[0,N-1] b
for(int i=0; i<N; i++) {
#pragma polca def f
  b[i] = a[i];
}
 
#pragma polca map f a[N,2*N-1] c
for(int i=0; i<N; i++) {
#pragma polca def f
  c[i] = a[N+i];
}

Other non-terminal symbols

Other non-terminal symbols that were used in the previous definitions.

<identifier> ::= <nondigit> | <identifier> <nondigit> | <identifier> <digit>

<nondigit> ::= <letterMinus> | <letterCapital> | "_"

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<letterMinus> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

<letterCapital> ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

<C_location_list> ::= <C_location> | <C_location> <C_location_list>

<io_var_list> ::=  <C_location> | <C_location> <io_var_list> | <zip> | <zip> <io_var_list>

<C_location> ::= <C_VAR> | <C_array> | "*" <C_VAR> | "&" <C_VAR>

<C_array> ::= <C_VAR> "[" <C_EXP> "]" | <C_VAR> "[" <C_EXP> "," <C_EXP> "]"

<C_VAR> ::= <identifier>

<C_number> ::= <INT> | <FLOAT>
  • <INT> is a non-terminal symbol that can take a valid Integer Constant value as defined in the Chapter 6.4.4.1 of the C99 Standard.
  • <FLOAT> is a non-terminal symbol that can take a valid single or double precision floating point constant value as defined in the Chapter 6.4.4.2 of the C99 Standard.
  • <C_EXP> is a non-terminal symbol that can take a valid C Expression value as defined in Chapters 6.5 and 6.6 of the C99 Standard.
  • <C_OP> is a non-terminal symbol that can take a valid C Operand value as defined in the Chapter 6.5 of the C99 Standard.
  • <C_VAR> is a non-terminal symbol that identifies a valid variable in the underlying C code.
  • <C_TYPE> is a non-terminal symbol that identifies a defined data type as defined in Chapters 6.2.5, 6.2.6 and 6.2.7 of the C99 Standard.
polca_language_definition.txt · Last modified: 2016/11/28 15:46 by daniel