Type system

Meta-language for describing types

A type expression can be described by the following language:

TypeExpression
 : Constant
 | TypeConstructorInvocation
 | Variable
 | Tuple
   
Constant
 : Integer
 | TypeName

TypeConstructorInvocation
 : TypeName '(' TypeExpression (',' TypeExpression)* ')'

Variable
  : IDENTIFIER

Tuple
  : '{' (TypeExpression (',' TypeExpression)*)? '}

Some examples are:

• bigint
• array(bigint)
• map(varchar(10), bigint)
• array(a)
• ->({array[a], array[a]}, array[a])

The last entry is the type of a function that takes two arrays of some arbitrary type as arguments and returns an array of that same type (e.g., a 2-arg concat function). This form will be necessary for representing the type of lambdas.

A "type constructor invocation" is the instantiation of what we currently call a "parametric type"