Type.lhs 4.22 KB
Newer Older
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
% $Id: IL.lhs,v 1.18 2003/10/28 05:43:38 wlux Exp $
%
% Copyright (c) 1999-2003 Wolfgang Lux
% See LICENSE for the full license.
%
% Modified by Martin Engelke (men@informatik.uni-kiel.de)
%
\nwfilename{IL.lhs}
\section{The intermediate language}
The module \texttt{IL} defines the intermediate language which will be
compiled into abstract machine code. The intermediate language removes
a lot of syntactic sugar from the Curry source language.  Top-level
declarations are restricted to data type and function definitions. A
newtype definition serves mainly as a hint to the backend that it must
provide an auxiliary function for partial applications of the
constructor. \textbf{Newtype constructors must not occur in patterns
and may be used in expressions only as partial applications.}

Type declarations use a de-Bruijn indexing scheme (starting at 0) for
type variables. In the type of a function, all type variables are
numbered in the order of their occurence from left to right, i.e., a
type \texttt{(Int -> b) -> (a,b) -> c -> (a,c)} is translated into the
type (using integer numbers to denote the type variables)
\texttt{(Int -> 0) -> (1,0) -> 2 -> (1,2)}.

Pattern matching in an equation is handled via flexible and rigid
\texttt{Case} expressions. Overlapping rules are translated with the
help of \texttt{Or} expressions. The intermediate language has three
kinds of binding expressions, \texttt{Exist} expressions introduce a
new logical variable, \texttt{Let} expression support a single
non-recursive variable binding, and \texttt{Letrec} expressions
introduce multiple variables with recursive initializer expressions.
The intermediate language explicitly distinguishes (local) variables
and (global) functions in expressions.

\em{Note:} this modified version uses haskell type \texttt{Integer}
instead of \texttt{Int} for representing integer values. This provides
an unlimited range of integer constants in Curry programs.
\begin{verbatim}

> {-# LANGUAGE DeriveDataTypeable #-}
42
> module IL.Type
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
43
44
45
46
47
48
49
50
51
52
53
54
55
56
>   ( -- * Data types
>     Module (..), Decl (..), ConstrDecl (..), CallConv (..), Type (..)
>   , Literal (..), ConstrTerm (..), Expression (..), Eval (..), Alt (..)
>   , Binding (..)
>   ) where

> import Data.Generics

> import Curry.Base.Ident
> import Curry.Base.Position (SrcRef(..))

> data Module = Module ModuleIdent [ModuleIdent] [Decl] deriving (Eq,Show)

> data Decl
57
58
>   = DataDecl     QualIdent Int [ConstrDecl [Type]]
>   | NewtypeDecl  QualIdent Int (ConstrDecl Type)
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
59
60
>   | FunctionDecl QualIdent [Ident] Type Expression
>   | ExternalDecl QualIdent CallConv String Type
61
>     deriving (Eq, Show)
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
62

63
64
> data ConstrDecl a = ConstrDecl QualIdent a deriving (Eq, Show)
> data CallConv = Primitive | CCall deriving (Eq, Show)
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
65
66
67

> data Type
>   = TypeConstructor QualIdent [Type]
68
69
70
>   | TypeVariable    Int
>   | TypeArrow       Type Type
>     deriving (Eq, Show, Typeable, Data)
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
71
72

> data Literal
73
74
>   = Char  SrcRef Char
>   | Int   SrcRef Integer
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
75
>   | Float SrcRef Double
76
>     deriving (Eq, Show)
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

> data ConstrTerm
>     -- |literal patterns
>   = LiteralPattern Literal
>     -- |constructors
>   | ConstructorPattern QualIdent [Ident]
>     -- |default
>   | VariablePattern Ident
>   deriving (Eq,Show)

> data Expression
>     -- |literal constants
>   = Literal Literal
>     -- |variables
>   | Variable Ident
>     -- |functions
>   | Function QualIdent Int
>     -- |constructors
>   | Constructor QualIdent Int
>     -- |applications
>   | Apply Expression Expression
>     -- |case expressions
>   | Case SrcRef Eval Expression [Alt]
>     -- |non-determinisismic or
>   | Or Expression Expression
>     -- |exist binding
>   | Exist Ident Expression
>     -- |let binding
>   | Let Binding Expression
>     -- |letrec binding
>   | Letrec [Binding] Expression
>   deriving (Eq,Show)

110
111
> data Eval    = Rigid | Flex deriving (Eq,Show)
> data Alt     = Alt ConstrTerm Expression deriving (Eq,Show)
Bjoern Peemoeller's avatar
Bjoern Peemoeller committed
112
113
114
115
116
117
118
119
120
121
122
123
> data Binding = Binding Ident Expression deriving (Eq,Show)

> instance SrcRefOf ConstrTerm where
>   srcRefOf (LiteralPattern l) = srcRefOf l
>   srcRefOf (ConstructorPattern i _) = srcRefOf i
>   srcRefOf (VariablePattern i) = srcRefOf i

> instance SrcRefOf Literal where
>   srcRefOf (Char s _)   = s
>   srcRefOf (Int s _)    = s
>   srcRefOf (Float s _)  = s

124
\end{verbatim}