Module FlatCurry.Types

This library supports meta-programming, i.e., the manipulation of Curry programs in Curry. For this purpose, the library contains definitions of data types for the representation of Curry programs in the FlatCurry format where all function definitions are at the top-level and pattern matching is replaced by case expressions and disjunctions.

Author: Michael Hanus

Version: July 2016

Summary of exported operations:

showQNameInModule :: String -> (String,String) -> String  Deterministic 
Shows a qualified type name as a name relative to a module (first argument).
showQName :: (String,String) -> String  Deterministic 
Shows a qualified name.

Exported datatypes:


Prog

Data type for representing a Curry module in the intermediate form. A value of this data type has the form

(Prog modname imports typedecls functions opdecls)

where modname is the name of this module, imports is the list of modules names that are imported, and typedecls, functions, and opdecls are the list of data type, function, and operator declarations contained in this module, respectively.

Constructors:


QName

The data type for representing qualified names. In FlatCurry all names are qualified to avoid name clashes. The first component is the module name and the second component the unqualified name as it occurs in the source program.

Type synonym: QName = (String,String)


Visibility

Data type to specify the visibility of various entities.

Constructors:

  • Public :: Visibility
  • Private :: Visibility

TVarIndex

The data type for representing type variables. They are represented by (TVar i) where i is a type variable index.

Type synonym: TVarIndex = Int


TVarWithKind

Kinded type variables are represented by a tuple of type variable index and kind.

Type synonym: TVarWithKind = (TVarIndex,Kind)


TypeDecl

Data type for representing definitions of algebraic data types and type synonyms.

A data type definition of the form

data t x1...xn = ...| c t1....tkc |...

is represented by the FlatCurry term

(Type t [i1,...,in] [...(Cons c kc [t1,...,tkc])...])

where each ij is the index of the type variable xj.

Note: the type variable indices are unique inside each type declaration and are usually numbered from 0

Thus, a data type declaration consists of the name of the data type, a list of type parameters and a list of constructor declarations.

Constructors:


ConsDecl

A constructor declaration consists of the name and arity of the constructor and a list of the argument types of the constructor.

Constructors:


NewConsDecl

A constructor declaration for a newtype consists of the name of the constructor and the argument type of the constructor.

Constructors:


TypeExpr

Data type for type expressions. A type expression is either a type variable, a function type, or a type constructor application.

Note: the names of the predefined type constructors are "Int", "Float", "Bool", "Char", "IO", "()" (unit type), "(,...,)" (tuple types), "[]" (list type)

Constructors:


Kind

Constructors:

  • KStar :: Kind
  • KArrow :: Kind -> Kind -> Kind

OpDecl

Data type for operator declarations. An operator declaration fix p n in Curry corresponds to the FlatCurry term (Op n fix p).

Constructors:


Fixity

Data types for the different choices for the fixity of an operator.

Constructors:

  • InfixOp :: Fixity
  • InfixlOp :: Fixity
  • InfixrOp :: Fixity

VarIndex

Data type for representing object variables. Object variables occurring in expressions are represented by (Var i) where i is a variable index.

Type synonym: VarIndex = Int


Arity

Arity of a function.

Type synonym: Arity = Int


FuncDecl

Data type for representing function declarations.

A function declaration in FlatCurry is a term of the form

(Func name k type (Rule [i1,...,ik] e))

and represents the function name with definition

name :: type
name x1...xk = e

where each ij is the index of the variable xj.

Note: the variable indices are unique inside each function declaration and are usually numbered from 0

External functions are represented as

(Func name arity type (External s))

where s is the external name associated to this function.

Thus, a function declaration consists of the name, arity, type, and rule.

Constructors:


Rule

A rule is either a list of formal parameters together with an expression or an "External" tag.

Constructors:

  • Rule :: [VarIndex] -> Expr -> Rule
  • External :: String -> Rule

CaseType

Data type for classifying case expressions. Case expressions can be either flexible or rigid in Curry.

Constructors:

  • Rigid :: CaseType
  • Flex :: CaseType

CombType

Data type for classifying combinations (i.e., a function/constructor applied to some arguments).

Constructors:

  • FuncCall :: CombType : a call to a function where all arguments are provided
  • ConsCall :: CombType : a call with a constructor at the top, all arguments are provided
  • FuncPartCall :: Arity -> CombType : a partial call to a function (i.e., not all arguments are provided) where the parameter is the number of missing arguments
  • ConsPartCall :: Arity -> CombType : a partial call to a constructor (i.e., not all arguments are provided) where the parameter is the number of missing arguments

Expr

Data type for representing expressions.

Remarks:

if-then-else expressions are represented as rigid case expressions:

(if e1 then e2 else e3)

is represented as

(case e1 of { True -> e2; False -> e3})

Higher-order applications are represented as calls to the (external) function apply. For instance, the rule

app f x = f x

is represented as

(Rule  [0,1] (Comb FuncCall ("Prelude","apply") [Var 0, Var 1]))

A conditional rule is represented as a call to an external function cond where the first argument is the condition (a constraint). For instance, the rule

equal2 x | x=:=2 = True

is represented as

(Rule [0]
      (Comb FuncCall ("Prelude","cond")
            [Comb FuncCall ("Prelude","=:=") [Var 0, Lit (Intc 2)],
             Comb FuncCall ("Prelude","True") []]))

Constructors:

  • Var :: VarIndex -> Expr : variable (represented by unique index)
  • Lit :: Literal -> Expr : literal (Int/Float/Char constant)
  • Comb :: CombType -> QName -> [Expr] -> Expr : application (f e1 ... en) of function/constructor f with n<=arity(f)
  • Let :: [(VarIndex,Expr)] -> Expr -> Expr : introduction of local variables via (recursive) let declarations
  • Free :: [VarIndex] -> Expr -> Expr : introduction of free local variables
  • Or :: Expr -> Expr -> Expr : disjunction of two expressions (used to translate rules with overlapping left-hand sides)
  • Case :: CaseType -> Expr -> [BranchExpr] -> Expr : case distinction (rigid or flex)
  • Typed :: Expr -> TypeExpr -> Expr : typed expression to represent an expression with a type declaration

BranchExpr

Data type for representing branches in a case expression.

Branches "(m.c x1...xn) -> e" in case expressions are represented as

(Branch (Pattern (m,c) [i1,...,in]) e)

where each ij is the index of the pattern variable xj, or as

(Branch (LPattern (Intc i)) e)

for integers as branch patterns (similarly for other literals like float or character constants).

Constructors:


Pattern

Data type for representing patterns in case expressions.

Constructors:


Literal

Data type for representing literals occurring in an expression or case branch. It is either an integer, a float, or a character constant.

Constructors:

  • Intc :: Int -> Literal
  • Floatc :: Float -> Literal
  • Charc :: Char -> Literal

Exported operations:

showQNameInModule :: String -> (String,String) -> String  Deterministic 

Shows a qualified type name as a name relative to a module (first argument). Thus, names not defined in this module (except for names defined in the prelude) are prefixed with their module name.

Further infos:
  • partially defined

showQName :: (String,String) -> String  Deterministic 

Shows a qualified name.

Further infos:
  • solution complete, i.e., able to compute all solutions