-
Notifications
You must be signed in to change notification settings - Fork 1
/
ILTrans.lhs
321 lines (278 loc) · 12.5 KB
/
ILTrans.lhs
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
% -*- LaTeX -*-
% $Id: ILTrans.lhs 3178 2015-10-04 08:56:55Z wlux $
%
% Copyright (c) 1999-2015, Wolfgang Lux
% See LICENSE for the full license.
%
\nwfilename{ILTrans.lhs}
\section{Translating Curry into the Intermediate Language}\label{sec:il-trans}
After desugaring and lifting have been performed, the source code is
translated into the intermediate language.
Because of name conflicts between the source and intermediate language
representations, we can only use a qualified import of the \texttt{IL}
module.
\begin{verbatim}
> module ILTrans(ilTrans) where
> import Base
> import Curry
> import CurryUtils
> import Env
> import qualified IL
> import List
> import Maybe
> import PredefIdent
> import Set
> import TopEnv
> import Types
> import TypeInfo
> import TypeSubst
> import ValueInfo
\end{verbatim}
\paragraph{Modules}
At the top-level, the compiler has to translate data, type, function,
and foreign declarations. When translating data type and type synonym
declarations, we ignore the types in the declarations and look up the
types of the constructors in the type (constructor) environment
instead because these types are already fully expanded, i.e., they do
not include any alias types.
\begin{verbatim}
> ilTrans :: TCEnv -> ValueEnv -> Module Type -> IL.Module
> ilTrans tcEnv tyEnv (Module m es _ ds) =
> IL.Module m (exports es) (imports m ds') ds'
> where ds' = concatMap (translTopDecl m tcEnv tyEnv) ds
> exports (Just (Exporting _ es)) =
> filter (isJust . localIdent m) (concatMap values es)
> values (Export x) = [x]
> values (ExportTypeWith tc cs) = map (qualifyLike tc) cs
> translTopDecl :: ModuleIdent -> TCEnv -> ValueEnv -> TopDecl Type -> [IL.Decl]
> translTopDecl m _ tyEnv (DataDecl _ tc tvs cs) =
> [translData m tyEnv tc tvs cs]
> translTopDecl m tcEnv _ (TypeDecl _ tc _ _) = [translAlias m tcEnv tc]
> translTopDecl m tcEnv tyEnv (BlockDecl d) = translDecl m tcEnv tyEnv d
> translDecl :: ModuleIdent -> TCEnv -> ValueEnv -> Decl Type -> [IL.Decl]
> translDecl m _ tyEnv (FunctionDecl _ ty _ eqs) =
> map (translFunction m tyEnv ty) eqs
> translDecl m tcEnv _ (ForeignDecl _ fi ty f _) =
> [translForeign m f fi (expandForeignFunctionType tcEnv ty)]
> translDecl _ _ _ _ = []
> translData :: ModuleIdent -> ValueEnv -> Ident -> [Ident] -> [ConstrDecl]
> -> IL.Decl
> translData m tyEnv tc tvs cs =
> IL.DataDecl (qualifyWith m tc) (length tvs)
> (map (translConstrDecl m tyEnv) cs)
> translAlias :: ModuleIdent -> TCEnv -> Ident -> IL.Decl
> translAlias m tcEnv tc = IL.TypeDecl tc' n (translType ty)
> where [AliasType tc' n ty] = qualLookupTopEnv (qualifyWith m tc) tcEnv
> translConstrDecl :: ModuleIdent -> ValueEnv -> ConstrDecl -> IL.ConstrDecl
> translConstrDecl m tyEnv d = IL.ConstrDecl c (map translType (arrowArgs ty))
> where c = qualifyWith m (constr d)
> ty = rawType (snd (conType c tyEnv))
> translForeign :: ModuleIdent -> Ident -> ForeignImport -> Type -> IL.Decl
> translForeign m f (cc,_,ie) ty =
> IL.ForeignDecl (qualifyWith m f) (callConv cc) (fromJust ie) (translType ty)
> where callConv CallConvPrimitive = IL.Primitive
> callConv CallConvCCall = IL.CCall
> callConv CallConvRawCall = IL.RawCall
\end{verbatim}
\paragraph{Types}
The type representation of the intermediate language is the same as
the internal representation except that it does not support
constrained type variables and skolem types. The former are fixed and
the latter are replaced by fresh type constructors.
\begin{verbatim}
> translType :: Type -> IL.Type
> translType (TypeConstructor tc tys) =
> IL.TypeConstructor tc (map translType tys)
> translType (TypeVariable tv) = IL.TypeVariable tv
> translType (TypeConstrained tys _) = translType (head tys)
> translType (TypeArrow ty1 ty2) =
> IL.TypeArrow (translType ty1) (translType ty2)
> translType (TypeSkolem k) =
> IL.TypeConstructor (qualify (mkIdent ("_" ++ show k))) []
\end{verbatim}
\paragraph{Foreign Functions}
To facilitate proper marshaling of foreign function arguments and
results with the \texttt{ccall} calling convention, the compiler must
expand all renaming types in their types. However, due to its special
semantics the compiler must be careful to not expand an \texttt{IO}
type, even though it is considered a type synonym internally to allow
$\eta$-expansion of primitive IO actions. Note that while the
arguments and results of foreign functions using the \texttt{ccall}
convention must ultimately expand to a basic foreign type, this
restriction is not enforced for other calling conventions.
\begin{verbatim}
> expandForeignFunctionType :: TCEnv -> Type -> Type
> expandForeignFunctionType tcEnv (TypeArrow ty1 ty2) =
> TypeArrow (expandForeignType tcEnv ty1)
> (expandForeignFunctionType tcEnv ty2)
> expandForeignFunctionType tcEnv ty = expandResultType tcEnv ty
> expandForeignType :: TCEnv -> Type -> Type
> expandForeignType tcEnv ty = last (typeExpansions (renamedType tcEnv) ty)
> expandResultType :: TCEnv -> Type -> Type
> expandResultType tcEnv ty =
> case expandForeignType tcEnv ty of
> TypeConstructor tc [ty] | tc == qIOId ->
> TypeConstructor tc [expandForeignType tcEnv ty]
> ty -> ty
> renamedType :: TCEnv -> QualIdent -> Maybe Type
> renamedType tcEnv tc = if tc /= qIOId then typeAlias tc tcEnv else Nothing
\end{verbatim}
\paragraph{Functions}
Every function in the program is translated into a function of the
intermediate language. Recall that every function has only a single
equation and all arguments are variables at this point.
\begin{verbatim}
> translFunction :: ModuleIdent -> ValueEnv -> Type -> Equation a -> IL.Decl
> translFunction m tyEnv ty (Equation _ (FunLhs f ts) rhs) =
> IL.FunctionDecl (qualifyWith m f) vs (translType ty)
> (translRhs tyEnv vs rhs)
> where vs = [v | VariablePattern _ v <- ts]
> translRhs :: ValueEnv -> [Ident] -> Rhs a -> IL.Expression
> translRhs tyEnv vs (SimpleRhs p e _) =
> IL.SrcLoc (show p) (translExpr tyEnv vs e)
\end{verbatim}
\paragraph{Patterns}
Since pattern matching has been transformed already, patterns can be
translated almost directly into the intermediate language. The only
complication arises from as-patterns, which are not supported in the
intermediate language. Therefore, we return the respective variables
along with the transformed patterns.
\begin{verbatim}
> translLiteral :: Literal -> IL.Literal
> translLiteral (Char c) = IL.Char c
> translLiteral (Int i) = IL.Int i
> translLiteral (Float f) = IL.Float f
> translTerm :: ConstrTerm a -> ([Ident],IL.ConstrTerm)
> translTerm (LiteralPattern _ l) = ([],IL.LiteralPattern (translLiteral l))
> translTerm (VariablePattern _ v) = ([],IL.VariablePattern v)
> translTerm (ConstructorPattern _ c ts) =
> ([],IL.ConstructorPattern c [v | VariablePattern _ v <- ts])
> translTerm (AsPattern v t) = (v:vs,t')
> where (vs,t') = translTerm t
\end{verbatim}
\paragraph{Expressions}
The translation of expressions from lifted Curry source code into the
intermediate language is also almost straightforward. The only
exception are case expressions with alternatives using as-patterns.
Such expressions are transformed into an outer, flexible case
expression that evaluates the scrutinized expression and binds the
as-pattern variable,\footnote{Recall that case expressions in the
intermediate language always evaluate the scrutinized expression.}
and an inner case expression that matches this variable against the
actual pattern. We always use a flexible match for the outer case
expression because the compiler would generate a redundant switch
statement during the translation of the intermediate language into
abstract machine code otherwise.
\begin{verbatim}
> translExpr :: ValueEnv -> [Ident] -> Expression a -> IL.Expression
> translExpr _ _ (Literal _ l) = IL.Literal (translLiteral l)
> translExpr tyEnv vs (Variable _ v)
> | not (isQualified v) && v' `elem` vs = IL.Variable v'
> | otherwise = IL.Function v (arity v tyEnv)
> where v' = unqualify v
> translExpr tyEnv _ (Constructor _ c) = IL.Constructor c (arity c tyEnv)
> translExpr tyEnv vs (Apply e1 e2) =
> IL.Apply (translExpr tyEnv vs e1) (translExpr tyEnv vs e2)
> translExpr tyEnv vs (Let ds e) =
> case ds of
> [FreeDecl _ vs'] -> IL.Exist (bv vs') e'
> [d] -> IL.Let (rec d) [translBinding vs' d] e'
> _ -> IL.Let IL.Rec (map (translBinding vs') ds) e'
> where e' = translExpr tyEnv vs' e
> vs' = vs ++ bv ds
> translBinding vs (PatternDecl _ (VariablePattern _ v) rhs) =
> IL.Binding v (translRhs tyEnv vs rhs)
> rec d
> | any (`elem` bv d) (qfv (mkMIdent []) d) = IL.Rec
> | otherwise = IL.NonRec
> translExpr tyEnv vs (Case e as) =
> caseExpr IL.Rigid (translExpr tyEnv vs e) (nub (concat vss')) as'
> where (vss',as') = unzip (map (translAlt tyEnv vs) as)
> translExpr tyEnv vs (Fcase e as) =
> case e of
> Let [FreeDecl _ [FreeVar _ v]] (Variable _ v')
> | qualify v == v' && all isChoice as ->
> IL.Choice [translRhs tyEnv vs rhs | Alt _ _ rhs <- as]
> _ -> caseExpr IL.Flex (translExpr tyEnv vs e) (nub (concat vss')) as'
> where (vss',as') = unzip (map (translAlt tyEnv vs) as)
> isChoice (Alt _ t rhs) = all (`notElem` qfv (mkMIdent []) rhs) (bv t)
> translAlt :: ValueEnv -> [Ident] -> Alt a -> ([Ident],IL.Alt)
> translAlt tyEnv vs (Alt _ t rhs) = (filter (`elem` fv e') vs',IL.Alt t' e')
> where (vs',t') = translTerm t
> e' = translRhs tyEnv (vs ++ bv t) rhs
> caseExpr :: IL.Eval -> IL.Expression -> [Ident] -> [IL.Alt] -> IL.Expression
> caseExpr ev e vs as =
> case (e,vs) of
> (IL.Variable v,_) -> match ev v (filter (v /=) vs) as
> (_,[]) -> IL.Case ev e as
> (_,v:vs) ->
> IL.Case IL.Flex e [IL.Alt (IL.VariablePattern v) (match ev v vs as)]
> where match ev v vs as =
> IL.Let IL.NonRec [IL.Binding v' e | v' <- vs] (IL.Case ev e as)
> where e = IL.Variable v
> instance QuantExpr IL.ConstrTerm where
> bv (IL.LiteralPattern _) = []
> bv (IL.ConstructorPattern _ vs) = vs
> bv (IL.VariablePattern v) = [v]
> instance Expr IL.Expression where
> fv (IL.Literal _) = []
> fv (IL.Variable v) = [v]
> fv (IL.Function _ _) = []
> fv (IL.Constructor _ _) = []
> fv (IL.Apply e1 e2) = fv e1 ++ fv e2
> fv (IL.Case _ e as) = fv e ++ fv as
> fv (IL.Choice es) = fv es
> fv (IL.Exist vs e) = filter (`notElem` vs) (fv e)
> fv (IL.Let rec bs e) =
> fvBinds rec vs (fv es) ++ filter (`notElem` vs) (fv e)
> where (vs,es) = unzip [(v,e) | IL.Binding v e <- bs]
> fvBinds IL.NonRec _ = id
> fvBinds IL.Rec vs = filter (`notElem` vs)
> fv (IL.SrcLoc _ e) = fv e
> instance Expr IL.Alt where
> fv (IL.Alt t e) = filterBv t (fv e)
\end{verbatim}
\paragraph{Auxiliary Definitions}
The list of import declarations in the intermediate language code is
determined by collecting all module qualifiers used in the current
module.
\begin{verbatim}
> imports :: ModuleIdent -> [IL.Decl] -> [ModuleIdent]
> imports m = toListSet . deleteFromSet m . fromListSet . flip modules []
> class HasModule a where
> modules :: a -> [ModuleIdent] -> [ModuleIdent]
> instance HasModule a => HasModule [a] where
> modules = flip (foldr modules)
> instance HasModule IL.Decl where
> modules (IL.DataDecl _ _ cs) = modules cs
> modules (IL.TypeDecl _ _ ty) = modules ty
> modules (IL.FunctionDecl _ _ ty e) = modules ty . modules e
> modules (IL.ForeignDecl _ _ _ ty) = modules ty
> instance HasModule IL.ConstrDecl where
> modules (IL.ConstrDecl _ tys) = modules tys
> instance HasModule IL.Type where
> modules (IL.TypeConstructor tc tys) = modules tc . modules tys
> modules (IL.TypeVariable _) = id
> modules (IL.TypeArrow ty1 ty2) = modules ty1 . modules ty2
> instance HasModule IL.ConstrTerm where
> modules (IL.LiteralPattern _) = id
> modules (IL.ConstructorPattern c _) = modules c
> modules (IL.VariablePattern _) = id
> instance HasModule IL.Expression where
> modules (IL.Literal _) = id
> modules (IL.Variable _) = id
> modules (IL.Function f _) = modules f
> modules (IL.Constructor c _) = modules c
> modules (IL.Apply e1 e2) = modules e1 . modules e2
> modules (IL.Case _ e as) = modules e . modules as
> modules (IL.Choice es) = modules es
> modules (IL.Exist _ e) = modules e
> modules (IL.Let _ bs e) = modules bs . modules e
> modules (IL.SrcLoc _ e) = modules e
> instance HasModule IL.Alt where
> modules (IL.Alt t e) = modules t . modules e
> instance HasModule IL.Binding where
> modules (IL.Binding _ e) = modules e
> instance HasModule QualIdent where
> modules x = maybe id (:) $ fst $ splitQualIdent x
\end{verbatim}