diff options
Diffstat (limited to 'ghc/docs/NOTES.desugar')
| -rw-r--r-- | ghc/docs/NOTES.desugar | 323 |
1 files changed, 0 insertions, 323 deletions
diff --git a/ghc/docs/NOTES.desugar b/ghc/docs/NOTES.desugar deleted file mode 100644 index b9e6ce7a57..0000000000 --- a/ghc/docs/NOTES.desugar +++ /dev/null @@ -1,323 +0,0 @@ -(91/08/08: OLD!) - -These are notes about a _simple_ but complete pattern-matching -compiler for Haskell. I presume familiarity with Phil's -pattern-matching stuff in Simon's book and use roughly the same notation. - -Abbreviations: "p" for pattern, "e" (or "E") for expression, "g" for -guard, "v" for variable, "u" for new variable I made up. "[]" for -FATBAR. - -Subscripts: "p11" is really short for "p_{1,1}". Sometimes I'll use -a "?", as in "pm1 ... pm?", to mean the second subscript goes up to -something I'm really not worried about. - -NB: LETRECS NOT DEALT WITH YET. - ---------------------------------------------------------------------- -We need a slightly souped-up "match" for Haskell (vs the Phil-chapter -one). Simon suggested a re-arrangement of things, which I have then -further re-arranged... - -Proposal (Simon) -~~~~~~~~ - -Eliminate default arg of match (3rd arg in Phil-chapter match) in -favour of returning the variable (not special value) fail. Thus a -possible translation for - - f [] [] = e1 - f x y = e2 - -would be - - f p q = case p of - [] -> case q of - [] -> e1 - _ -> fail - _ -> fail - where - fail = e2 - -Now the issue of whether to duplicate code or share it becomes whether -to substitute copies of e2 or not. This is a decision we need to take -anyway for all other let-bound things, so why not for fail too? If -fail is used only once, we will certainly substitute for it. - -We could even detect that fail is used only in a head position, so it -can be implemented as a stack-adjust then a jump. This might well -apply to other let-bound things too. - -Now here's a proposal for the "match" function. The main difference is - 1) no default argument - 2) [contra simon's suggestion] Patterns are still per-row as in - Phil's chapter. - 3) [partain] even the input exprs are CoreExprs - -OK, for a "match" for m equations each with n patterns: - -match :: [Name] - -- n (variable) names, one per pattern column, bound - -- to the n expressions we are matching against the - -- patterns - - -> [([Pat], CoreExpr)] - -- one pair for each of the m equations: the n - -- patterns in that equation, then the CoreExpr that - -- is evaluated if we get a match. The CoreExpr may - -- contain free "fail"s; some hackery required to - -- ensure that is OK; see below - - -> CoreExpr - -- the resulting code to do the matching - -In words, - takes - (1) a list of n (match-expression, pattern-column) pairs - (2) a list of m post-match expressions, expr i to be inserted - immediately after equation i's lhs matches - returns - (1) a desugared expr equivalent of the whole "match" - -Meaning -~~~~~~~ - match [u1, ..., un] - [([p11, ..., p1n], e1), ..., ([pm1, ..., pmn], em)] - - match [ (e1, [p11, ...,pm1]), ..., (en, [p1n, ...,pmn])] - [ E1, ... Em ] - - ********* MEANS ********* - - case (u1, ..., un) of - (p11, ..., p1n) -> e1 - _ -> fail - where - fail = case (u1, ..., un) of - (p21, ..., p2n) -> e2 - _ -> fail - ... and so on ... - -Alternatively, this specification could be given in terms of -pattern-matching lambdas, as in Phil's chapter. - -NOT CHANGED BEYOND HERE - -------------------------------------------------------------------- -Cranking through a good old function definition with the above: - - f p11 p12 ... p1n | g11 = e11 - | g12 = e12 - ... - | g1? = e1? - ... - f pm1 pm2 ... pmn | gm1 = em1 - ... - | gm? = em? - -The "match" equivalent is: - -f = \u1.\u2...\un -> - match [ (u1, [p11, ...,pm1]), ..., (un, [p1n, ...,pmn])] - [ E1, ..., Em ] - where fail = error "pattern-match for f failed\n" - E1 = if g11 then e11 else if g12 then ... else fail - ... - Em = if gm1 then em1 else if gm2 then ... else fail - -Boring, huh? - -------------------------------------------------------------------- -It is helpful to me to think about the simple/base cases for this -complicated "match". - -ALL LISTS EMPTY - - match [] [] - - corresponds to the syntactically bogus (zero equations!?) - - case () of - () -> {- nothing!! -} - _ -> fail - - -EMPTY RULE -- no more patterns - - match [] [ ([], E1), ..., ([], Em) ] - - [where, incidentally, each Ei will be of the form - (not that it has to be...) - - Ei = let x1 = e1 in - let x2 = e2 in - ... - let x? = e? in - if g1 then e'1 - else if g2 then - ... - else if g? then e'? - else fail - ] - - becomes ("E1 [] E2 [] ... [] Em" in Phil's chapter...) - - E1 - where - fail = E2 - where - ... - fail = Em-1 - where fail = Em - - with any "fail" in Em being bound from an outer scope; perhaps it's - easier to see written as: - - let fail = Em - in let fail = Em-1 - in ... - let fail = E2 in E1 -------------------------------------------------------------------- -HANDLING LAZY ("TWIDDLE") PATTERNS - -For Haskell, the "mixture rule" (p.~88) looks at a pattern-column and -splits the equations into groups, depending on whether it sees - - * all constructors, or - * all variables _OR LAZY PATTERNS_ - -The following example shows what "match" does when confronted by one -of these variables/lazy-patterns combinations. Note the use of the -binding lists. - - f v | g11 = e11 - ... - | g1? = e1? - f ~p | g21 = e21 - ... - | g2? = e2? - -is - - f = \ u1 -> - match [(u1, [ v, ~p ])] - [ if g11 then e11 else if ... else fail, -- E1 - if g21 then e21 else if ... else fail -- E2 - ] - where fail = error "no match in f\n" - -which transmogrifies into - - f = \ u1 -> - let u2 = u1 in - match [] - [ -- E1 -- - let v = u2 - in - if g11 then e11 else if ... else fail - - ,-- E2 -- - let free_var1_of_p = match [(u2, [ p ])] [ free_var1_of_p ] - ... - free_var?_of_p = match [(u2, [ p ])] [ free_var?_of_p ] - in - if g21 then e21 else if ... else fail -- E2 - - ] - where fail = error "no match in f\n" - -For more specific match-failure error messages, one could insert -"let fail = ..."'s in strategic places. - -------------------------------------------------------------------- -"match" EQUIVALENTS FOR VARIOUS HASKELL CONSTRUCTS - -* function definition -- shown above - -* pattern-matching lambda (souped up version in static semantics) - - \ p1 p2 ... pn | g1 -> e1 - | g2 -> e2 - ... - | gm -> em - - is the same as - - \ u1.\u2 ... \un -> - match [ (u1, [p1]), ..., (un, [pn])] - [ if g1 then e1 else if ... then em else fail - ] - where fail = error "no match in pattern-matching lambda at line 293\n" - -* pattern-matching (simple, non-recursive) "let" - - let p = e - in E - - corresponds to - - case e of - ~p -> E - - which has a "match" equivalent of - - match [(e, [~p])] [ E ] - - The full-blown Haskell "let" is more horrible: - - let p | g1 = e1 - ... - | gn = en - in E - - corresponds to - - case ( if g1 then e1 else... else if gn then en else error "?" ) of - ~p -> E - - thinking about which I am not able to sleep well at night. - (Won't those g's have things bound from inside p ?) - -* pattern-matching (not-quite-so simple, non-recursive) "let" - -<mumble> - -* pattern binding - - p | g1 = e1 - | g2 = e2 - ... - | gm = em - - That's the same as - - p = if g1 then e1 else if ... else if gm then em else fail - where fail = "...some appropriate thing..." - - which corresponds to - - match [ (if g1 ... then em else fail, [ ~p ]) ] - [ {-nothing-} ] - where fail = "...some appropriate thing..." - -* "case" expressions (souped up version in static semantics) - - case e0 of - p1 | g11 -> e11 - ... - | g1? -> e1? - ... - pm | gm1 -> em1 - ... - | gm? -> em? - - is the same as - - match [ (e0, [p1, ..., pm]) ] - [ if g11 then e11 else if ... else fail -- E1 - , ... , - if gm1 then em1 else if ... else fail - ] - where fail = error "pattern-matching case at line xxx failed\n" - -* list comprehensions |