FlatCurry: An intermediate representation for Curry programs

In order to provide a common interface for connecting different tools working on Curry programs or programs written in another (functional logic) declarative language (e.g., Toy), there is an intermediate language, called FlatCurry, for representing functional logic programs. This document provides an overview about the ideas and structure of FlatCurry.

Basic structure of FlatCurry

In FlatCurry, all functions are defined at the top level (i.e., local function declarations in source programs are globalized by lambda lifting) and the pattern-matching strategy is made explicit by the use of case expressions. Thus, a FlatCurry program basically consists of To support separate compilation, FlatCurry contains also information about modules (i.e., each module is represented as a FlatCurry program). To support interactive tools (e.g., debuggers, program verifiers, interactive back ends that allow the user to evaluate arbitrary expressions), the FlatCurry representation contains also some information about the syntactic representation of source programs (list of infix operator declarations and a translation table to map source program names into internal names and vice versa). Altogether, a FlatCurry program is a tuple

(module,imports,types,functions,operators,translation)

with the following components:
module:
The name of the module represented by this structure.
imports:
The names of the modules imported by this program.
types:
The list of data type declarations defined in this module. Each data type declaration consists of a list of type variables as parameters (for polymorphic data structures) and a list of constructor declarations where each constructor declaration contains the name and arity of the data constructor and a list of type expressions (the argument types of this data constructor).
functions:
The functions defined in this module. A function declaration consists of the name and arity of the function together with a type expression specifying the function's type and a single rule (where the right-hand side can contain case expressions and disjunctions) specifying the function's meaning. External functions (i.e., primitive functions not defined in this or another module) contain instead of the rule the external name of this function.
operators:
The infix operators declared in this module. An operator declaration contains the fixity (or associativity) and the precedence for each operator. Although an operator declaration contains no semantic information, it might be used by interactive tools to print or read expressions.
translation:
The translation table describes the mapping of identifiers (type constructors, data constructors, defined functions) used in the source program into their corresponding internal names used in the intermediate FlatCurry program (since it is often necessary to rename identifiers to avoid name clashes, e.g., the internal names are prefixed by the module name). Only the externally visible names (i.e., names exported by this module) are listed here. This information might be used by back ends for representing intermediate (e.g., during debugging) or final results or to allow the user to type in and evaluate arbitrary expressions.
Note: Since a complete program can consist of several FlatCurry modules, there should be no name conflict in the defined entities of the complete program, i.e., the names of all functions and constructors defined in the various modules must be pairwise different (similarly for the type names, but name clashes between type names and function/constructor names are allowed).

The abstract syntax of FlatCurry provides a description of the complete structure of FlatCurry programs.

XML representation of FlatCurry

To provide an implementation-independent format for FlatCurry programs, there is an XML representation of FlatCurry programs. The document type definition (DTD) for this representation specifies the structure of the components in detail. Here are example programs in this XML representation. You can also try an interactive translator for Curry programs into this XML representation.

Curry representation of FlatCurry

The XML representation for FlatCurry programs is intended for computer-based tools and thus not very readable for humans. The PAKCS implementation of Curry contains a system module which defines a collection of datatypes in order to represent and manipulate FlatCurry programs in Curry. You can find here the documentation of this system module. Since this is more or less equivalent to the external XML representation, PAKCS contains also a translator from XML into the internal FlatCurry representation and vice versa. This representation has been used in a number of tools written in Curry, e.g., a graphical programming environment for Curry (CIDER) or a partial evaluator for Curry programs.


Curry Homepage | DTD for FlatCurry | Example programs | interactive translator Curry->FlatCurry

Michael Hanus