Identifiers

Identifiers are sequences of characters for naming variables, functions, and data types. They are a nonempty sequences of letters, digits, underscores, and single quotes, where the first character must be a letter or underscore.

In short: they are C identifiers which may also contain single quotes after the first character.

Identifiers which name top-level definitions must also be valid as C identifiers.

The single quote allows identifiers such as x' (pronounced "ex prime"), which can be convenient in mathematical expressions.

Reserved names

Reserved names are special identifiers which are reserved for the programming language, and may not be used for any other purpose.

This is the list of reserved names:

module import extern static inline __C__
struct type storing
mat vec for in out inout
while if then else specialize
True False Void T _ __
and or return assert

Operators

An operator is a special sequence of symbols which represents an operation, such as addition or multiplication, on one or two operands. Operators are parsed greedily, so x<-2 is not the comparison between x and -2, but rather storing 2 into x.

Operators will described in more detail later.

Constant Literals

Like in C, Plover provides syntax for basic data such as numbers and strings. The syntax for literals is derived from Haskell.

22
0x16
0o26

22.2
2.22e1
222e-1

"hello, \
     \world!"

Whitespace

Whitespace is not significant except for the purpose of separating identifiers and reserved names.

-- this is a comment at the beginning of the line
x := 22; -- this is a comment later in the line
{- this is a nested comment
   -- ordinary comments have no special significance inside a nested comment -}
y := 23; -- this is outside the nested comment
{- nested comments {- may be {- nested -} -} -}

---
--- Multiple hyphens may be used
---

{--- in nested comments as well ---}

{-
  x := 22;
  y := 23; -- Usually -} is ok in an ordinary comment
-}

Integer Types

Integers can be signed or unsigned of the standard bit widths 8, 16, 32, and 64. They are denoted by s8, u8, s16, u16, s32, u32, s64, and u64. The type int is also available, and it represents the default integer type, which defaults to s32 unless otherwise constrained.

Plover expects these types to be defined in the C environment, and there are implementations in the default prelude.plv.

Floating-Point Types

There are two floating-point types, float and double, which represent the types of 32- and 64-bit IEEE floating-point numbers, respectively. As in C, arithmetic defaults to double.

Boolean Type

The type of boolean values is bool. Plover uses bool from stdbool.h for the implementation.

String Type

The string type is denoted by string. Plover uses char * for their C implementation.

Pointer Types

A pointer is a value which represents the location to a value. The syntax for a pointer to something of type T is written *T (unlike in C, where the * is written after the type; this is so that * always is a prefix operator for both types and values).

Since Plover treats the locations of vector and scalar types differently, the underlying implementation of pointers is treated differently in each case as well. This will be discussed in the section on the * and & operators.

Vector Types

A vector type, in its basic form, with base type T, is written as T[n1,...,nm] to create a (dense) vector with m indices (also known as bounds). For instance, the type of a five by three dense matrix is written double[5,3].

Vectors may have different underlying storage formats to take advantage of properties of the vector or matrix. For a given storage type S, the syntax of vector with the given storage type is S T[n1,...,nm]. This is parsed with the same precedence of function application.

A matrix is simply a vector type with two indices. When it is not otherwise confusing to say so, a vector is a vector type with one index.

These are the known storage types:

• Dense is for dense matrices where every element is stored. They are stored row-normal, and can have any number of indices. This storage type is the default result of operations on vectors.
• Diagonal stores only the diagonal of a matrix, and it is presumed that every other non-diagonal element is zero. Diagonal matrices must be square.
• UpperTriangular stores only the upper triangular portion of a matrix in packed column-normal form. They must be square. An UpperTriangular T[n,n] is stored in a C array with n * (n + 1) / 2 entries.
• LowerTriangular stores only the lower triangular portion of a matrix in packed row-normal form. It has the same storage considerations as UpperTriangular.
• Symmetric stores the lower triangular portion of a symmetric matrix, where the upper triangular portion is derived from the lower portion. The storage is the same as LowerTriangular.
• Scalar stores a diagonal matrix whose diagonal is a single constant. The underlying storage holds only a single element. Such matrices are also known as homotheties or dilations. These also must be square.

The effective type of a vector for the purposes of an arithmetic operation is the dense version with all of the indices concatenated appropriately, since the underlying storage is merely an implementation detail. For instance, the effective type of the vector in the note is double[m,m,n,n,o,p] (i.e., a 6-index tensor).

The implementation in C for a vector type is simply T *, where T is the C type for the base type of the vector, no matter how many levels of storage types there are.

Tuple Types

The type of a tuple uses the same syntax as a tuple value, but with some number of types. So, (double, int) is the type for pairs whose first element is a double and whose second element is an integer.

One particular tuple type is very important, and it is () (with alias Void), which is the tuple of no subtypes. In the C implementation, this type is compiled as void, and, like in C, does not actually have a reifiable value.

Function Types

The type of a function cannot be written in Plover, though all functions have a type. The type is the types of each of the parameters declared for the function, whether each is implicit or explicit, whether each is in, out, or inout, what the type of the variadic parts are (if the function is variadic), and the return type of the function. See the section on top-level function definitions for more information.

Struct Types

Structures are named types with a collection of fields (also known as members) with types.

Since Plover is meant to interoperate with C, each field has an internal and external type. The external type describes to C how the object should be represented in memory, and the internal type describes to Plover how to interact with the value. This separation is mainly useful for vector types. See the section on dependent types and the storing reserved name.

Type Holes

Type holes are unknown types which are solved by the unification algorithm in the plover compiler. See the section on type and value holes.

Parentheses and Dollar

Parentheses can be used to override the default order of operations. The $ operator groups everything to the right: it is like an open parenthesis that doesn't need to be closed. Some examples:

            f a + b  --vs--  f (a + b)
(not False or True)  --vs--  (not $ False or True)

Remember that parentheses are not used to mark function calls. Attemping to pass a comma separated list of arguments will result in syntax errors.

Sequencing

Unlike C, everything in Plover is an expression with a value (possibly the void value ()). Like C, the semicolon is the expression sequencing operator. Plover treats the final expression in a sequence as the value of the sequence. Hence,

(a; b; c)

has value c, after evaluating a and b (in that order). Like for other operators, parentheses are used to delimit sequences of expressions (not curly braces, which are instead used to delimit implicit function arguments). A sequence of expressions is sometimes called a block.

Plover allows an optional dangling semicolon, as in

(a; b; c;)

This is in no way functionally different from the previous sequence.

In a sequence, the results of the non-terminal expressions are dropped, so in the following, the result of the first A + B is not computed:

( printf "The quantity A+B is not computed.\n";
  A + B;
  printf "But the result following is if the value of this block is used.\n";
  A + B
)

Variable Definitions

There are two ways to define a new variable. Both are done inside a sequence, and the binding extends through the end of the sequence. There must be some expression after the binding.

The first is for defining a new, uninitialized variable.:

( x :: ${Type};
  ${expressions} )

The variable x is declared to be of type Type (with some reserved stack space) for the following expressions.

The second is for defining a new variable with an initial value.:

( x := ${value};
  ${expressions} )

or

( x :: ${Type} := ${value};
  ${expressions} )

The value is evaluated before the variable x is brought into scope, and then the result is stored at the location for x.

The type is optional because Plover is able to infer the type from the value. However, when dealing with integer or floating-point types it can be useful to give a type when a specific width is wanted.

Another example to demonstrate scoping rules:

( x := 22;
  y := x + 1;
  z := foo (&z); -- this is an error, since z is not bound on the r.h.s.
  w := ( b := 1;
         x := 23; -- this is an error, since x shadows x
         b + 100; );
  -- now w is 101
  c := b + 1; -- this is an error since b is no longer bound
)

Ranges

There are two syntaxes for ranges of integers, each useful for different circumstances, but in the end are equivalent.

The expression a:b represents all integers from a to b, excluding b, where a..b represents all integers from a through b, including b. The second syntax is especially useful when implementing a numerical algorithm from a textbook.

Step sizes are specified using an extra :step. For instance,

0:6     -- is 0,1,2,3,4,5
0..6    -- is 0,1,2,3,4,5,6
0:6:2   -- is 0,2,4
0:5:2   -- is 0,2,4
0..6:2  -- is 0,2,4,6
0..5:2  -- is 0,2,4
5:0:-1  -- is 5,4,3,2,1
5:-1:-1 -- is 5,4,3,2,1,0
5..0:-1 -- is 5,4,3,2,1,0

A benefit of : is that 0:i and i:n together cover all elements in 0:n. On the other hand, 1..i-1 and i:n together cover all elements 1..n.

The type of a range expression is an integer-valued vector.

The lower bounds and upper bounds of a range can be omitted if Plover is able to infer their values. If the lower bound is omitted, it is always assumed to be 0, so :6 is the range 0:6. If the upper bound is omitted and is being used as an index, then it is assumed to be the length that index of the vector.

for i in 1..n ->
  foo A[i-1];

Tuples

Tuples are a comma-separated list of values of varying types. The tuple with a single element is, like in Python, designated by using a trailing comma. The following are equivalent tuples:

1,2
1,2,
(1,2)
(1,2,)

These are all of type (int,int). Notice that parentheses are optional, and are only used for grouping.

One way to understand the tuple operator is as compared to sequences: a sequence is like a tuple which drops all but the last element, and a tuple is like a sequence which accumulates all elements of the sequence. However, a tuple makes no guarantee on evaluation order.

Locations

Locations are places which can hold values. Variables are a basic kind of location, but there are other kinds of locations, too.

The first is from indexing. Suppose A is some kind of location which is vector typed, and i is some integer. Then A[i] is the location of row i of A. If A is a 1d vector, then this is a scalar, but if it is a matrix, then it is the full row. There are subtleties which will be discussed in its own section.

The second is from selecting a structure's field. If o is of some structure type, or a pointer to a structure, or a pointer to a pointer to a structure (and so on), then o.f selects the f field from o, like in C. There is no need for -> with pointers since Plover can easily figure out when o is a pointer to a ... to a struct.

The third is from dereferencing a pointer. If p is some pointer, then *p is the location p points to.

The <- operator assigns a value into a location by copying. For scalars and structs, it behaves like C assignment, but for vector types it will generate the necessary loops to copy every element. The precise loops will depend on the type of the left-hand side, so, for instance, assigning into a diagonal matrix type will only copy out the diagonal of the right-hand side.

A :: double[10];
A <- vec i in 10 -> i; -- now A is filled with 0 through 9
A[2] <- 22; -- now A[2] is 22
B :: Diagonal double[11,11];
B <- vec i in 11, j in 11 -> i * j; -- now B has i^2 on diagonal
o :: MyStruct; -- suppose has field f
o.f <- 100;
z := &o;
z.f <- 222;

Locations do not necessarily take stack space. They will only take stack space if an operator determines it will iterate over the elements of a location multiple times. This behavior can be overridden with nomemo.

A[A < 0] <- 0;

Type Specification

An expression can be asserted to have a particular type using the :: operator. The left-hand side is a value, and the right-hand side is a type, as in Haskell.

This operator is also used for declaring the type of a new variable, as described above for :=.

The operator is useful for getting a particular integer or floating-point type, as in 5 :: s8, but it can also be used to ensure the programmer has the same understanding of the intermediate types in an expression as Plover does.

Pointer Operators

The * operator, as described in the locations section, takes a pointer and gets the location which the pointer points to. It is prefix.

The (pseudo-)inverse of this operator is &, which takes a location and gives a pointer which can be later dereferenced by *.

Since Plover treats scalar types and vector types differently, the underlying implementation of * and & is different for each. First of all, *T for a scalar type T is implemented as TT * in C, where T is the corresponding C type for T. When T is a vector type, then the C implementation of *T is TT, since TT is already a pointer to the base type (as described in the vector types section). This rule keeps the number of indirections down in the compiled C.

When & is applied to a vector location, Plover will guarantee reified stack space for the location. Plover will not guarantee any modifications made to what that pointer points to will be reflected in the original location, unless that location is just a reference. That is, &A[2:5,2] will not guarantee reflecting modifications, but &A will.

There is no arithmetic on pointer operators in Plover. Pointers are only useful for passing references to locations.

Operators

These are listed in roughly decreasing order of precedence.

Function Application

A function call is a function name followed by each of its arguments. They are passed by juxtaposition, like in Haskell. Implicit arguments are optional if Plover can determine what they should be, but required arguments must always be supplied. A basic example is calling sqrt from prelude:

sqrt 2

The precedence of function application is higher than any other operator, so the following are equivalent:

1 + sqrt 2 + 3
1 + (sqrt 2) + 3

Implicit arguments, like in the function declaration, are delimited by braces. Suppose foo is declared as

foo {n} (A :: double[n]) :: double;

and suppose B is a double[m]. Then the following are equivalent:

foo B
foo {m} B

If a function takes no arguments, a dummy void value must be supplied as an argument, otherwise there is an ambiguity between function call and variable value. If do_it is a function of no arguments, this looks like

do_it ()

foo (in B)
foo {m} (in B)

matrix_inverse {n} A (out B) -- returns -1 if A is singular

Built-in Functions

not False --> True
not True --> False

sum vec(1.0,2,3,4) --> 10.0

x :: double[2,3,4];
shape x  -->  vec(2,3,4);

x :: double[2,2];
z0 := x * x * x;
z1 := nomemo (x * x) * x;

f () :: () := void $ printf "hi there\n";

Iteration Constructs

There are three basic iteration constructs in Plover: the for loop, the vec constructor, and the while loop

for ${i} in ${range} -> ${body}

for i in 0:n -> printf "The variable i is currently %d\n" i;

for i in 0:n, j in 0:m -> printf "(i,j) = (%d,%d)\n" i j;

for i in 0:n ->
  for j in 0:n ->
    printf "(i,j) = (%d,%d)\n" i j;

for i in n, j in m -> printf "(i,j) = (%d,%d)\n" i j;

I := vec i in n, j in n -> if i == j then 1 else 0;

while ${test} -> ${body};
while ${test};

binary_search {n} (A :: u8[n]) (key :: u8) :: int
  := ( imin := 0; imax := n;
       while (imax >= imin) -> (
         imid := imin + (imax - imin) / 2;
         if A[imid] == key then
           return imid;
         else if A[imid] < key then
           imin <- imid + 1;
         else
           imax <- imid - 1;
       );
       return -1;
     );

rand_normal() :: double
  := ( x1 :: double; x2 :: double;
       w :: double;
       while (x1 <- 2 * rand_uniform() - 1.0;
              x2 <- 2 * rand_uniform() - 1.0;
              w <- x1 ^ 2 + x2 ^ 2;

              w >= 1.0);
       w <- sqrt( -2 * log w / w );
       return x1 * w;
     );

Value and type holes

The Plover language supports introducing holes into a program which, depending on context, may in some circumstances be filled during normal typechecking. This feature allows a programmer some flexibility when prototyping and debugging. The holes come in two flavors: quiet and noisy. The difference between the two is that noisy holes will cause an error which will describe what the type system believes may be a valid substitution for the holes, whereas quiet holes will not cause an error so long as a valid substitution is found. The syntax for a quiet hole is a single underscore (_) and for a noisy hole a double underscore (__).

A common example is in function parameter lists. One may drop off the types as in the following:

foo (x :: _) :: _  := x + 1;

and because of defaulting rules, x will be int, as is the return type of foo.

The following is the same as the above example:

foo x :: _ := x + 1;

Noisy holes let a programmer see the type of intermediate results. For instance,

B :: __  := (G^T * G :: __)^(-1) * G^T;

to get the types of B and of G^T * G.

Specialize

The specialize syntax can be used to discriminate on an integer value at any point in a program. An example from prelude.plv:

det {n} (A :: double[n,n]) :: double
  := specialize n (
       0 -> 1;
       1 -> A[0,0];
       2 -> det2 A;
       3 -> det3 A;
       4 -> det4 A;
       _ -> gen_det_qr A;
     );

It is implemented with a C switch statement.

Functions

Structs

Typedefs and Aliases

Add a type alias using

type ${new_name} := ${type_name};

This does not generate a C typedef; it simply replaces occurrences of the name on the left hand side with that on the right.

To add a C typedef to your generated code, use the inline C feature:

__C__
  "typedef int8_t s8;\n\
  \typedef int16_t s16;\n";

Plover does not analyze code inside a __C__ block, so any names introduced here will be unavailable to the typechecker.

External Definitions

External C code is generally easy to call within Plover code. The primary obligation is to specify a Plover type for any externally defined constant or function. This allows the Plover typechecker to verify all references to the external definition. The mechanism to do this is the extern keyword. An example from prelude.plv:

__C__ "#include <stdlib.h>";
extern (
  struct div_t (
    quot :: int;
    rem :: int;
  );
  div (n :: int) (denom :: int) :: div_t;
);

This enables references to div_t structs and the div function.

Note that omitting struct members is possible, and if your code only passes a particular type around to external functions, never scrutinizing it itself, it may even make use of empty extern struct definitions. For instance, a somewhat awkward way of calling the qsort function using an external comparison function:

extern (
  struct cmp (
  );
  cmp_int :: cmp;
  qsort (array :: *s32) (length :: int) (size :: int) (comparison :: cmp) :: ();
);

qsort_int {n} (array :: s32[n]) :: s32[n] := (
  result := array;
  qsort (&result[0]) n 4 cmp_int;
  result;
);

Giving qsort a type that would allow plover-defined comparisons is problematic because it is currently impossible to have functions as parameters.