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.,
there is an intermediate language, called FlatCurry,
for representing functional logic programs.
This document provides an overview about the ideas and structure
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
- a list of data type declarations (defining the data constructors used
in the program) and
- a list of function definitions.
with the following components:
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
- The name of the module represented by this structure.
- The names of the modules imported by this program.
- 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).
- 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.
- 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.
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.
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
Curry representation of FlatCurry
The XML representation for FlatCurry programs is intended
for computer-based tools and thus not very readable for humans.
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
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
partial evaluator for Curry programs.
Curry Homepage |
DTD for FlatCurry |
Example programs |
interactive translator Curry->FlatCurry