--- /dev/null
+(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
projects / ghc-hetmet.git / blobdiff