2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
4 \section[DsBinds]{Pattern-matching bindings (HsBinds and MonoBinds)}
6 Handles @HsBinds@; those at the top level require different handling,
7 in that the @Rec@/@NonRec@/etc structure is thrown away (whereas at
8 lower levels it is preserved with @let@/@letrec@s).
11 #include "HsVersions.h"
13 module DsBinds ( dsBinds, dsInstBinds ) where
16 import DsLoop -- break dsExpr-ish loop
18 import HsSyn -- lots of things
19 import CoreSyn -- lots of things
20 import TcHsSyn ( TypecheckedHsBinds(..), TypecheckedHsExpr(..),
21 TypecheckedBind(..), TypecheckedMonoBinds(..) )
22 import DsHsSyn ( collectTypedBinders, collectTypedPatBinders )
25 import DsGRHSs ( dsGuarded )
27 import Match ( matchWrapper )
29 import CmdLineOpts ( opt_SccProfilingOn, opt_CompilingPrelude )
30 import CostCentre ( mkAllDictsCC, preludeDictsCostCentre )
31 import Id ( idType, DictVar(..), GenId )
32 import ListSetOps ( minusList, intersectLists )
33 import PprType ( GenType )
34 import PprStyle ( PprStyle(..) )
35 import Pretty ( ppShow )
36 import Type ( mkTyVarTys, mkForAllTys, splitSigmaTy,
37 tyVarsOfType, tyVarsOfTypes
39 import TyVar ( tyVarSetToList, GenTyVar{-instance Eq-} )
40 import Util ( isIn, panic )
42 isDictTy = panic "DsBinds.isDictTy"
45 %************************************************************************
47 \subsection[toplevel-and-regular-DsBinds]{Regular and top-level @dsBinds@}
49 %************************************************************************
51 Like @dsBinds@, @dsBind@ returns a @[CoreBinding]@, but it may be
52 that some of the binders are of unboxed type. This is sorted out when
53 the caller wraps the bindings round an expression.
56 dsBinds :: TypecheckedHsBinds -> DsM [CoreBinding]
59 All ``real'' bindings are expressed in terms of the
60 @AbsBinds@ construct, which is a massively-complicated ``shorthand'',
61 and its desugaring is the subject of section~9.1 in the static
66 AbsBinds [a1, ... ,aj] -- type variables
67 [d1, ... ,dk] -- dict variables
68 [(l1,g1), ..., (lm,gm)] -- overloaded equivs [Id pairs] (later...)
69 [db1=..., ..., dbn=...] -- dict binds
70 [vb1=..., ..., vbm=...] -- val binds; note: vb_i = l_i
72 we want to make, in the general case (non-Fozzie translation):
77 let(rec) <val-binds> in (vb1,...,vbm) -- NB: == ... in (l1,...,lm)
79 -- a bunch of selectors:
80 g1 a1...aj d1...dk = case (_tup a1...aj d1...dk) of (x1,x2,...,xm) -> x1
82 gm a1...aj d1...dk = case (_tup a1...aj d1...dk) of (x1,x2,...,xm) -> xm
84 But there are lots of special cases.
87 %==============================================
88 \subsubsection{Structure cases}
89 %==============================================
92 dsBinds (BindWith _ _) = panic "dsBinds:BindWith"
93 dsBinds EmptyBinds = returnDs []
94 dsBinds (SingleBind bind) = dsBind [] [] id [] bind
96 dsBinds (ThenBinds binds_1 binds_2)
97 = andDs (++) (dsBinds binds_1) (dsBinds binds_2)
101 %==============================================
102 \subsubsection{AbsBind case: no overloading}
103 %==============================================
105 Special case: no overloading.
110 We abstract each wrt the type variables, giving
112 x1' = /\tyvars -> e1[x1' tyvars/x1, x2' tyvars/x2]
113 x2' = /\tyvars -> e2[x1' tyvars/x1, x2' tyvars/x2]
115 There are some complications.
117 (i) The @val_binds@ might mention variable not in @local_global_prs@.
118 In this case we need to make up new polymorphic versions of them.
120 (ii) Exactly the same applies to any @inst_binds@ which may be
121 present. However, here we expect that mostly they will be simple constant
122 definitions, which don't mention the type variables at all, so making them
123 polymorphic is really overkill. @dsInstBinds@ deals with this case.
126 dsBinds (AbsBinds tyvars [] local_global_prs inst_binds val_binds)
127 = mapDs mk_poly_private_binder private_binders
128 `thenDs` \ poly_private_binders ->
130 full_local_global_prs = (private_binders `zip` poly_private_binders)
133 listDs [ mkSatTyApp global tyvar_tys `thenDs` \ app ->
134 returnDs (local, app)
135 | (local,global) <- full_local_global_prs
138 -- pprTrace "AbsBinds1:" (ppr PprDebug env) $
142 dsInstBinds tyvars inst_binds `thenDs` \ (inst_bind_pairs, inst_env) ->
143 extendEnvDs inst_env (
145 dsBind tyvars [] (lookupId full_local_global_prs) inst_bind_pairs val_binds
148 -- "private_binders" is the list of binders in val_binds
149 -- which don't appear in the local_global_prs list
150 -- These only really show up in stuff produced from compiling
151 -- class and instance declarations.
152 -- We need to add suitable polymorphic versions of them to the
154 private_binders = binders `minusList` [local | (local,_) <- local_global_prs]
155 binders = collectTypedBinders val_binds
156 mk_poly_private_binder id = newSysLocalDs (mkForAllTys tyvars (idType id))
158 tyvar_tys = mkTyVarTys tyvars
162 %==============================================
163 \subsubsection{AbsBind case: overloading}
164 %==============================================
166 If there is overloading we go for the general case.
168 We want the global identifiers to be abstracted wrt all types and
169 dictionaries; and the local identifiers wrt the non-overloaded types.
170 That is, we try to avoid global scoping of type abstraction. Example
172 f :: Eq a => a -> [(a,b)] -> b
175 Here, f is fully polymorphic in b. So we generate
177 f ab d = let ...dict defns...
179 letrec f' b = ...(f' b)...
182 *Notice* that we don't clone type variables, and *do* make use of
183 shadowing. It is possible to do cloning, but it makes the code quite
184 a bit more complicated, and the simplifier will clone it all anyway.
186 Why bother with this gloss? Because it makes it more likely that
187 the defn of f' can get floated out, notably if f gets specialised
188 to a particular type for a.
191 dsBinds (AbsBinds all_tyvars dicts local_global_prs dict_binds val_binds)
192 = -- If there is any non-overloaded polymorphism, make new locals with
193 -- appropriate polymorphism
194 (if null non_overloaded_tyvars
196 -- No non-overloaded polymorphism, so stay with current envt
197 returnDs (id, [], [])
199 -- Some local, non-overloaded polymorphism
200 cloneTyVarsDs non_overloaded_tyvars `thenDs` \ local_tyvars ->
202 mapDs mk_binder binders `thenDs` \ new_binders ->
204 old_new_pairs = binders `zip` new_binders
207 listDs [ mkSatTyApp new non_ov_tyvar_tys `thenDs` \ app ->
209 | (old,new) <- old_new_pairs
210 ] `thenDs` \ extra_env ->
212 local_binds = [NonRec old app | (old,app) <- extra_env, old `is_elem` locals]
213 is_elem = isIn "dsBinds"
215 returnDs (lookupId old_new_pairs, extra_env, local_binds)
217 `thenDs` \ (binder_subst_fn, local_env, local_binds) ->
219 -- pprTrace "AbsBinds:all:" (ppAbove (ppr PprDebug local_binds) (ppr PprDebug local_env)) $
221 extendEnvDs local_env (
223 dsInstBinds non_overloaded_tyvars dict_binds `thenDs` \ (inst_bind_pairs, inst_env) ->
225 extendEnvDs inst_env (
227 dsBind non_overloaded_tyvars [] binder_subst_fn inst_bind_pairs val_binds
228 )) `thenDs` \ core_binds ->
231 tuple_rhs = mkCoLetsAny core_binds (
232 mkCoLetsAny local_binds (
233 mkTupleExpr locals ))
235 mkTupleBind all_tyvars dicts local_global_prs tuple_rhs `thenDs` \ core_bind_prs ->
237 returnDs [ NonRec binder rhs | (binder,rhs) <- core_bind_prs ]
239 locals = [local | (local,global) <- local_global_prs]
240 non_ov_tyvar_tys = mkTyVarTys non_overloaded_tyvars
242 overloaded_tyvars = tyVarsOfTypes (map idType dicts)
243 non_overloaded_tyvars = all_tyvars `minusList` (tyVarSetToList{-????-} overloaded_tyvars)
245 binders = collectTypedBinders val_binds
246 mk_binder id = newSysLocalDs (mkForAllTys non_overloaded_tyvars (idType id))
249 @mkSatTyApp id tys@ constructs an expression whose value is (id tys).
250 However, sometimes id takes more type args than are in tys, and the
251 specialiser hates that, so we have to eta expand, to
252 @(/\ a b -> id tys a b)@.
255 mkSatTyApp :: Id -- Id to apply to the types
256 -> [Type] -- Types to apply it to
259 mkSatTyApp id [] = returnDs (Var id)
263 = returnDs ty_app -- Common case
265 = newTyVarsDs (drop (length tys) tvs) `thenDs` \ tyvars ->
266 returnDs (mkTyLam tyvars (mkTyApp ty_app (mkTyVarTys tyvars)))
268 (tvs, theta, tau_ty) = splitSigmaTy (idType id)
269 ty_app = mkTyApp (Var id) tys
272 There are several places where we encounter ``inst binds,''
273 @(Id, TypecheckedHsExpr)@ pairs. Many of these are ``trivial'' binds
274 (a var to a var or literal), which we want to substitute away; so we
275 return both some desugared bindings {\em and} a substitution
276 environment for the subbed-away ones.
278 These dictionary bindings are non-recursive, and ordered, so that
279 later ones may mention earlier ones, but not vice versa.
282 dsInstBinds :: [TyVar] -- Abstract wrt these
283 -> [(Id, TypecheckedHsExpr)] -- From AbsBinds
284 -> DsM ([(Id,CoreExpr)], -- Non-trivial bindings
285 [(Id,CoreExpr)]) -- Trivial ones to be substituted away
287 do_nothing = ([], []) -- out here to avoid dsInstBinds CAF (sigh)
288 prel_dicts_cc = preludeDictsCostCentre False{-not dupd-} -- ditto
290 dsInstBinds tyvars [] = returnDs do_nothing
292 dsInstBinds tyvars ((inst, expr@(HsVar _)) : bs)
293 = dsExpr expr `thenDs` \ rhs ->
294 let -- Need to apply dsExpr to the variable in case it
295 -- has a substitution in the current environment
296 subst_item = (inst, rhs)
298 extendEnvDs [subst_item] (
299 dsInstBinds tyvars bs
300 ) `thenDs` \ (binds, subst_env) ->
301 returnDs (binds, subst_item : subst_env)
303 dsInstBinds tyvars ((inst, expr@(HsLit _)) : bs)
304 = dsExpr expr `thenDs` \ core_lit ->
306 subst_item = (inst, core_lit)
308 extendEnvDs [subst_item] (
309 dsInstBinds tyvars bs
310 ) `thenDs` \ (binds, subst_env) ->
311 returnDs (binds, subst_item : subst_env)
313 dsInstBinds tyvars ((inst, expr) : bs)
315 = dsExpr expr `thenDs` \ core_expr ->
316 ds_dict_cc core_expr `thenDs` \ dict_expr ->
317 dsInstBinds tyvars bs `thenDs` \ (core_rest, subst_env) ->
318 returnDs ((inst, dict_expr) : core_rest, subst_env)
322 -- The inst mentions the type vars wrt which we are abstracting,
323 -- so we have to invent a new polymorphic version, and substitute
325 -- This can occur in, for example:
326 -- leftPoll :: [FeedBack a] -> FeedBack a
327 -- leftPoll xs = take poll xs
328 -- Here there is an instance of take at the type of elts of xs,
329 -- as well as the type of poll.
331 dsExpr expr `thenDs` \ core_expr ->
332 ds_dict_cc core_expr `thenDs` \ dict_expr ->
333 newSysLocalDs poly_inst_ty `thenDs` \ poly_inst_id ->
335 subst_item = (inst, mkTyApp (Var poly_inst_id) abs_tys)
337 extendEnvDs [subst_item] (
338 dsInstBinds tyvars bs
339 ) `thenDs` \ (core_rest, subst_env) ->
340 returnDs ((poly_inst_id, mkTyLam abs_tyvars dict_expr) : core_rest,
341 subst_item : subst_env)
343 inst_ty = idType inst
344 abs_tyvars = tyVarSetToList{-???sigh-} (tyVarsOfType inst_ty) `intersectLists` tyvars
345 abs_tys = mkTyVarTys abs_tyvars
346 poly_inst_ty = mkForAllTys abs_tyvars inst_ty
348 ------------------------
349 -- Wrap a desugared expression in `_scc_ "DICT" <expr>' if
350 -- appropriate. Uses "inst"'s type.
352 -- if profiling, wrap the dict in "_scc_ DICT <dict>":
354 | not opt_SccProfilingOn ||
355 not (isDictTy inst_ty)
356 = returnDs expr -- that's easy: do nothing
358 | opt_CompilingPrelude
359 = returnDs (SCC prel_dicts_cc expr)
362 = getModuleAndGroupDs `thenDs` \ (mod_name, grp_name) ->
363 -- ToDo: do -dicts-all flag (mark dict things
364 -- with individual CCs)
366 dict_cc = mkAllDictsCC mod_name grp_name False{-not dupd-}
368 returnDs (SCC dict_cc expr)
371 %************************************************************************
373 \subsection[dsBind]{Desugaring a @Bind@}
375 %************************************************************************
377 Like @dsBinds@, @dsBind@ returns a @[CoreBinding]@, but it may be that
378 some of the binders are of unboxed type.
380 For an explanation of the first three args, see @dsMonoBinds@.
383 dsBind :: [TyVar] -> [DictVar] -- Abstract wrt these
384 -> (Id -> Id) -- Binder substitution
385 -> [(Id,CoreExpr)] -- Inst bindings already dealt with
389 dsBind tyvars dicts binder_subst inst_bind_pairs EmptyBind
390 = returnDs [NonRec binder rhs | (binder,rhs) <- inst_bind_pairs]
392 dsBind tyvars dicts binder_subst inst_bind_pairs (NonRecBind monobinds)
393 = dsMonoBinds False tyvars dicts binder_subst monobinds `thenDs` ( \ val_bind_pairs ->
394 returnDs [NonRec binder rhs | (binder,rhs) <- inst_bind_pairs ++ val_bind_pairs] )
396 dsBind tyvars dicts binder_subst inst_bind_pairs (RecBind monobinds)
397 = dsMonoBinds True tyvars dicts binder_subst monobinds `thenDs` ( \ val_bind_pairs ->
398 returnDs [Rec (inst_bind_pairs ++ val_bind_pairs)] )
402 %************************************************************************
404 \subsection[dsMonoBinds]{Desugaring a @MonoBinds@}
406 %************************************************************************
408 @dsMonoBinds@ transforms @TypecheckedMonoBinds@ into @CoreBinds@.
409 In addition to desugaring pattern matching, @dsMonoBinds@ takes
410 a list of type variables and dicts, and adds abstractions for these
411 to the front of every binding. That requires that the
412 binders be altered too (their type has changed,
413 so @dsMonoBinds@ also takes a function which maps binders into binders.
414 This mapping gives the binder the correct new type.
416 Remember, there's also a substitution in the monad which maps occurrences
417 of these binders into applications of the new binder to suitable type variables
421 dsMonoBinds :: Bool -- True <=> recursive binding group
422 -> [TyVar] -> [DictVar] -- Abstract wrt these
423 -> (Id -> Id) -- Binder substitution
424 -> TypecheckedMonoBinds
425 -> DsM [(Id,CoreExpr)]
430 %==============================================
431 \subsubsection{Structure cases}
432 %==============================================
435 dsMonoBinds is_rec tyvars dicts binder_subst EmptyMonoBinds = returnDs []
437 dsMonoBinds is_rec tyvars dicts binder_subst (AndMonoBinds binds_1 binds_2)
438 = andDs (++) (dsMonoBinds is_rec tyvars dicts binder_subst binds_1)
439 (dsMonoBinds is_rec tyvars dicts binder_subst binds_2)
443 %==============================================
444 \subsubsection{Simple base cases: function and variable bindings}
445 %==============================================
447 For the simplest bindings, we just heave them in the substitution env:
450 {- THESE TWO ARE PLAIN WRONG.
451 The extendEnvDs only scopes over the nested call!
452 Let the simplifier do this.
454 dsMonoBinds is_rec tyvars dicts binder_subst (VarMonoBind was_var (HsVar new_var))
455 | not (is_rec || isExported was_var)
456 = extendEnvDs [(was_var, Var new_var)] (
459 dsMonoBinds is_rec tyvars dicts binder_subst (VarMonoBind was_var expr@(Lit _))
460 | not (isExported was_var)
461 = dsExpr expr `thenDs` ( \ core_lit ->
462 extendEnvDs [(was_var, core_lit)] (
466 dsMonoBinds is_rec tyvars dicts binder_subst (VarMonoBind var expr)
467 = dsExpr expr `thenDs` \ core_expr ->
468 returnDs [(binder_subst var, mkLam tyvars dicts core_expr)]
472 dsMonoBinds is_rec tyvars dicts binder_subst (FunMonoBind fun _ matches locn)
475 new_fun = binder_subst fun
476 error_string = "function " ++ showForErr fun
478 matchWrapper (FunMatch fun) matches error_string `thenDs` \ (args, body) ->
480 mkLam tyvars (dicts ++ args) body)]
482 dsMonoBinds is_rec tyvars dicts binder_subst (PatMonoBind (VarPat v) grhss_and_binds locn)
484 dsGuarded grhss_and_binds `thenDs` \ body_expr ->
485 returnDs [(binder_subst v, mkLam tyvars dicts body_expr)]
488 %==============================================
489 \subsubsection{The general base case}
490 %==============================================
492 Now the general case of a pattern binding. The monomorphism restriction
493 should ensure that if there is a non-simple pattern binding in the
494 group, then there is no overloading involved, so the dictionaries should
495 be empty. (Simple pattern bindings were handled above.)
496 First, the paranoia check.
499 dsMonoBinds is_rec tyvars (_:_) binder_subst (PatMonoBind pat grhss_and_binds locn)
500 = panic "Non-empty dict list in for pattern binding"
503 We handle three cases for the binding
507 \item[pat has no binders.]
508 Then all this is dead code and we return an empty binding.
510 \item[pat has exactly one binder, v.]
511 Then we can transform to:
513 v' = /\ tyvars -> case rhs of { pat -> v }
515 where \tr{v'} is gotten by looking up \tr{v} in the \tr{binder_subst}.
517 \item[pat has more than one binder.]
518 Then we transform to:
520 t = /\ tyvars -> case rhs of { pat -> (v1, ..., vn) }
522 vi = /\ tyvars -> case (t tyvars) of { (v1, ..., vn) -> vi }
527 dsMonoBinds is_rec tyvars [] binder_subst (PatMonoBind pat grhss_and_binds locn)
530 dsGuarded grhss_and_binds `thenDs` \ body_expr ->
532 {- KILLED by Sansom. 95/05
533 -- make *sure* there are no primitive types in the pattern
534 if any_con_w_prim_arg pat then
535 error ( "ERROR: Pattern-bindings cannot involve unboxed/primitive types!\n\t"
536 ++ (ppShow 80 (ppr PprForUser pat)) ++ "\n"
537 ++ "(We apologise for not reporting this more `cleanly')\n" )
539 -- Check whether the pattern already is a simple tuple; if so,
540 -- we can just use the rhs directly
543 mkSelectorBinds tyvars pat
544 [(binder, binder_subst binder) | binder <- pat_binders]
547 pat_binders = collectTypedPatBinders pat
548 -- NB For a simple tuple pattern, these binders
549 -- will appear in the right order!
552 Wild-card patterns could be made acceptable here, but it involves some
553 extra work to benefit only rather unusual constructs like
555 let (_,a,b) = ... in ...
557 Better to extend the whole thing for any irrefutable constructor, at least.