PIL: Parallel Intermediate Language

Basic Properties

• PIL programs are target of translators from C, Fortran, MPI/OpenMP/etc. They can also be written by humans.
• PIL should be a high-level language like CIVL-C.
• PIL programs can be easily translated to PFG.
• PIL must also have a totally well-defined semantics and syntax.
• PIL programs can have nested funtion definitions.
• PIL programs can use preprocessor directives like in C
• There are no automatic conversions. All must be done by explicit casts.
• $input/$output variables in global scope (like CIVL-C)
• Identifiers are like in C, e.g., x, f10, ...
• Keywords, functions, etc. not in C start with $ (like CIVL-C)
• Libraries: similar to C, #include <stdlib.h>, but these name PIL libraries and there are additional PIL libraries
• PIL programs can be divided into multiple files (translation units)
  • One TU can refer to a variable, function, type, in another TU.
  • the variable just needs to be declared somewhere in the TU
  • the function just needs a prototype somewhere in the TU
  • the use of "static" in a variable decl or function def makes it private to that TU (so two can have same name)
  • no need for "extern"
  • at most one of the TUs declaring the variable can have an initializer
  • at most one of the TUs can have a definition for a function
• Program order:
  • a program is a sequence of variable, function, and type definitions.
  • the order is totally irrelevant.
  • a variable can be used anywhere it is in scope
  • a function can be called anywhere it is in scope

Types

• type names look like int[], int*[](double), etc.
• basic types: same as C: _Bool, char, short, int, long, long long, unsigned, float, double, ...
• what are the limits of these types? to be decided
• $int, $real (mathematical types)
• struct: as in C
• union: as in C
• T[]: sequence of T. Note: no "T[n]". sequences can be assigned, returned, passed as arguments, etc.
• $set<T> : finite set of T, ops to add, contains, remove, size, ...
• $map<T1,T2> : finite map from T1 to T2, ops to put, get, containsKey, ...
• $fun<T1,T2> : total functions from T1 to T2
• $tuple<T,...> : tuples of specified type (similar to struct)
• $rel<T,...> : relations of specified type (set of tuples)
• T*: pointer to T
  • what can be pointed to: var, array element, struct element, union member, ...
• Type definitions: typedef typename ID;

Tuples

Non-mutating expressions:

• t1 == t2
• t.i
• ($tuple<T1,...>){ x1, ... }
• $pure $tuple<T1,...> $tuple_write($tuple<T1,...> t, $int i, Ti x);

Mutating expressions:

• t.i = x;

Sets

Non-mutating expressions:

• s1 == s2
• ($set<T>)$empty empty set of type T
• $pure _Bool $set_in(T x, $set<T> s); is x an element of s?

$pure $set<T> $set_with($set<T> s, T x); s U {x} $pure $set<T> $set_without($set<T> s, T x); s - {x} $pure $set<T> $set_union($set<T> s1, $set<T> s2); s1 U s2 $pure $set<T> $set_difference($set<T> s1, $set<T> s2); s1-s2 $pure $set_intersection($set<T> s1, $set<T> s2); s1 \cap s2 $pure T[] $set_elements($set<T> s); $pure _Bool $set_isSubsetOf($set<T> s1, $set<T> s2); $pure $set<U> $set_map($set<T> s, $fun<T,U> f);

Mutation functions: _Bool $set_add($set<T> * this, T x); _Bool $set_remove($set<T> * this, T x); void $set_addAll($set<T> * this, $set<T> that); void $set_removeAll($set<T> * this, $set<T> that); void $set_keepOnly($set<T> * this, $set<T> that);

Sequences (arrays) ========= Expressions: a1 == a2 a[i] (T[]){ x1, ... }

Built-in logic functions: $pure T[] $seq_fun($int len, $fun<$int,T> f); $pure T[] $seq_uniform($int n, T val); $pure $int $length(T[] a); length of a $pure T[] $seq_write(T[] a, int i, T x); a[i:=x] $pure T[] $seq_subseq(T[] a, int i, int n); a[i..i+n-1] $pure T[] $seq_without(T[] a, int i); a with position i removed $pure T[] $seq_with(T[] a, int i, T x); $pure T[] $seq_concat(T[] a1, T[] a2); $pure U[] $seq_map(T[] a, $fun<T,U> f); $pure T[] $seq_filter(T[] a, $fun<T,_Bool> f); $pure U $seq_foldl(T[] a, $fun<$tuple<T,U>,U> f, U init); $pure U $seq_foldr(T[] a, $fun<$tuple<T,U>,U> f, U init);

Mutating operations: a[i]=x;

Mutating Procedures: T $seq_remove(T[] * this, int i); void $seq_insert(T[] * this, int i, T x); void $seq_append(T[] * this, T[] that);

Maps ==== Non-mutation: m1 == m2 ($map<K,V>)$empty $pure V $map_get($map<K,V> K key); $pure _Bool $map_containsKey($map<K,V> map, K key); $pure _Bool $map_containsValue($map<K,V> map, V val); $pure $map<K,V> $map_with($map<K,V> map, K key, V val); $pure $map<K,V> $map_without($map<K,V> map, K key); $pure $set<K> $map_keys($map<K,V> map); $pure $set<$tuple<K,V>> $map_entries($map<K,V> map);

Mutation: V $map_put($map<K,V> * this, K key, V val); V $map_remove($map<K,V> * this, K key); void $map_removeAll($map<K,V> * this, $set<K> keys); void $map_addAll($map<K,V> * this, $map<K,V> that);

Functions ========= There are two kinds of functions in PIL:

1. (Imperative) procedures, like in C. These can be nested. Obviously they can have side-effects, be nondeterministic, and the behavior can depend on non-local state. A procedure call f(x1,...,xn) is an expression that can be used anywhere an expression with side-effects is allowed. Imperative procedures are not values and cannot be assigned to anything. However, as in C, a pointer to a procedure is a first-class value that can be assigned, used as an argument, returned, etc. There is a procedure type, exactly like C's function type, e.g.,

typedef int(int) i2i;

defines i2i to be the type "procedure consuming int and returning int". Most commonly, pointers to procedure types will be used, e.g.,

typedef int(int)* i2ip;

defines the type "pointer to procedure from int to int". As in C, a pointer to a procedure can be used in a procedure call.

A procedure definition can be templated:

<T1,T2,...> <procedure def>

This defines one procedure for each assignment of types to the Ti.

2. Logic functions. Typically specified by a $lambda expression. These are first-class objects in PIL: they can be assigned to variables, passed as an argument in a function call (including a procedure call), and can be returned by a function. Each has a type of the form $fun<T1,...,Tn;U> (functions from T1 x...x Tn to U). They are side-effect-free. An application of a logic function f(x1,...,xn) is an expression that can be used anywhere an expression is allowed. A logic function is not necessarily pure, i.e., the value of an application may depend on any part of the state, not just the arguments.

Lambda expressions: have the form

$lambda (T1 x1, ..., Tn xn) {U1 v1=init1; ... Um vm=initm; expr}

where the Ti and Uj are types, the xi and vj are variables, and expr is an expression in which the only variables that can occur free are the x1,..., xn, v1,..., vm. The initializer expressions initj are expressions using any variables in scope. The expression has type $fun<T1,...,Tn; V>, where V is the type of expr.

Semantics: the lambda expression is evaluated to yield a *closure*: an ordered pair consisting of a dyscope and an expression. The dyscope has variables v1, ..., vm, initialized by evaluating init1, ..., initm. The dyscope has no parent scope, it is associated only with the closure. The expression is expr. The dyscope is destroyed whenever it becomes unreachable, i.e., whenever no part of the state is assigned the closure.

A logic function application f(e1,...,en) is evaluated by first evaluating the arguments ei, then assigning the ei to the xi and evaluating expr in the closure dyscope. Note that since expr has no side effects, the values of the xi are constant. [Note: a possible change is to allow side-effects in logic functions.]

Heaps =====

There is a single heap for dynamic allocation. The following built-in procedures are provided:

T* $new<T>(): creates an object A of type T in heap and returns &A.

T* $alloc<T>(int n): creates an array A of length n of T in heap and returns &A[0].

[Question: how to model C's malloc? Must be able to execute it without knowing T.]

void $free<T>(T* p): frees the object referred to by p, the pointer returned by an earlier call to $new or $alloc.

Questions

how to deal with "undefined" values?

can there be nondeterministic expressions, i.e., expressions that evaluate to a set of values instead of one value?

how to implement C's malloc?

Union of all types occurring in program: typedef union {

T1 t1; T2 t2; ...

} BigUnion;

A call to malloc returns a memory block:

• size (in bytes) (int)
• num_elements (int)
• sequence of tuples:
  • offset (int)
  • size (int)
  • value (type BigUnion)