Haskell Prime: Ticket #114: introduce lambda-match (explicit match failure and fall-through)
http://ghc.haskell.org/trac/haskell-prime/ticket/114
<h2 id="name:">name:</h2>
<p>
<strong>introduce lambda-match (explicit match failure and fall-through)</strong>
</p>
<h2 id="summary:">summary:</h2>
<p>
Haskell 98 provides *two different translations* of lambda
abstractions involving pattern matching, only one of which is
directly accessible (Section 3.3 - the other is embedded in the
translation of do-notation, see "ok" in Section 3.14).
</p>
<p>
Providing explicit source notation for the second translation,
substantially simplifies programmability of pattern-match
fall-through by reification of pattern-match failure, two
central language features that are so far only available
through the built-in, non-composable case construct.
</p>
<h2 id="what:">what:</h2>
<p>
In Section 3.3, the translation for conventional lambda
abstractions with patterns is given as
</p>
<pre class="wiki"> [| \p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of
(p1,..,pn) -> e
</pre><p>
with xi fresh identifiers, and pattern-match failure resulting in
_|_. the latter is unfortunate, and results in partial functions the
coverage of which cannot be combined, but it is forced by
translation into conventional lambda calculus.
</p>
<p>
since computational lambda calculus (\-M) has become a central part
of Haskell programming practice, there shall be an alternative form
of lambda abstraction, dubbed here <strong>lambda-match</strong>, with associated
translation into \-M:
</p>
<pre class="wiki"> [| |p1 .. pn-> e |] = \x1 .. xn-> case (x1,..,xn) of
{ (p1,..,pn) -> return e;
_ -> fail "no match" }
</pre><p>
<em>[note1: this is the translation in principle - in practice, to enable composition of lambda-matches without further language extensions, a slight modification is needed, wrapping the right-hand sides of the case in a Match constructor, see library, examples, and patch]</em>
</p>
<p>
a library for composing these lambda-matches provides for
composition of alternative lambda-matches ( <tt>(+++)</tt> ), match failure
(<tt>nomatch</tt>, <tt>matchError <message></tt>) and embedding of the explicit
match monad into pure expressions (<tt>splice</tt>, where
<tt> \p1..pn->e = splice |p1..pn->e </tt>, also <tt>spliceE</tt> -preserving
error messages by using <tt>(Either String)</tt> as the match monad, and
<tt>allMatches</tt>, using the <tt>[]</tt> monad to deliver all successful matches).
other lambda-match related auxiliaries include <tt>caseOf</tt> as a
user-defined version of <tt>case _ of _</tt>, argument supply to matches
( <tt>(>|)</tt> ), and joining of nested matches (so that, for instance
</p>
<pre class="wiki"> nest (|<outer>-> (|<inner>-> expr)) = (|<outer> <inner>-> expr)
</pre><p>
).
</p>
<p>
<em>[note2: an alternative translation would use do-notation instead of case as the target:
</em></p>
<pre class="wiki"> [| |p1 .. pn-> e |] = \x1 .. xn-> do {
(p1,..,pn) <- return (x1,..,xn);
return e }
</pre><p>
both translations easily accomodate guards and pattern guards as well, the former by building on existing support for these two features in case constructs, the latter without requiring any previous implementation of pattern guards, by lifting (pattern)guards into the match monad:
</p>
<pre class="wiki"> [| pat <- expr |] = pat <- return expr
[| expr |] = guard expr
</pre><p>
]<em>
</em></p>
<h2 id="implementationimpact:">implementation impact:</h2>
<p>
minimal - limited to an extension in parser/desugarer, employing
previously inaccessible syntax for lambda-match, and a slight
variation of the existing lambda translation; also adds a small
library to support composition of matches.
</p>
<p>
<em>[note3: an updated draft of the composition library and a patch for GHC (about a dozen new lines in the parser, changed from the original proposal email only in requiring parentheses) are provided as attachments to this proposal, together with some examples (updated since original email). please add patches for other Haskell implementations, and test whether they can handle the library code (tried for Hugs and GHC)]</em>
</p>
<h2 id="motivation:">motivation:</h2>
<ol><li>patterns/guards in lambda abstractions are of limited use if match failure cannot be handled
</li></ol><ul><li>match failure in lambda abstractions can only lead to an exception
</li></ul><ol start="2"><li>the only direct way of handling match-failure and fall-through to other alternatives, without something like lambda-match, is not by composing alternatives, but within the built-in construct case; a slightly more indirect way employs the built-in do notation, where again the functionality is not available to (monadic) composition, but only within the do notation
</li></ol><ol start="3"><li>workarounds to mimick the functionality of lambda-match without syntactic sugar (translating into lambda+do or lambda+case) are so cumbersome and unreadable as to be unusable in practice (translating into lambda+list-comprehension is almost readable, but restricted to lists). compare:
<pre class="wiki"> (|(Just x)-> x)
\fresh->do { Just x <- return fresh; return x }
\fresh->case fresh of { Just x -> return x; _ -> fail "no match" }
\fresh->[ x | Just x <- [fresh] ]
</pre></li></ol><ol start="4"><li>since the functionality is already available in the language, and even explicitly used in the report for a feature as frequently used as the do notation, there should be a language construct making this functionality directly accessible
</li></ol><ul><li>the functions named "ok", constructed in Section 3.14 of the report, can be expressed directly using lambda-match (the library contains a function <tt>ok</tt> for this purpose)
<pre class="wiki"> do { p <- e; stmts } = e >>= ok (|p-> stmts)
</pre></li></ul><ol start="5"><li>unlike lambda, lambda-match truly expresses a single alternative in a case statement, as a first-class language expression - it can be named, passed as parameter or result, manipulated as a function, and composed with other alternatives. as a corollary, lambda, case, and other monadic abstractions can be defined easily in terms of lambda-match and its support library
<pre class="wiki"> - splice (|x->expr) = \x->expr
- case expr of { pat -> expr; ..} = caseOf expr $ (| pat -> expr ) +++ ..
- ok (|pat->do statements) = \fresh->do { pat <- return fresh; statements }
</pre></li></ol><ol start="6"><li>while the present proposal suggests lambda-match as a small extension to the language, it also lays the groundwork for a major simplification
</li></ol><ul><li>as points 4 and 5 indicate, several core constructs of Haskell need no longer be considered as built into the language, but become user-definable; this would simplify the language definition, implementations, teaching, learning, and tool building
</li></ul><ol start="7"><li>although the present lambda-match proposal is fairly conservative, it also aims to lay the groundwork for a substantial increase in language expressiveness
</li></ol><ul><li>the fundamental idea, used here only to reify pattern-match failure and fall-through, is that of replacing built-in pattern matching with user-definable monadic data parsers and associated combinators
</li></ul><ul><li>this same idea lies at the heart of a more radical decomposition of pattern-matching, which has been studied in the literature as first-class patterns (eg, Tullsen, PADL2000)
</li></ul><ul><li>having pattern-match alternatives as first-class language constructs also paves the way for user-defined pattern abstractions, or more generally, views (various literature)
</li></ul><p>
this completes the main part of this proposal.
</p>
<hr />
<p>
relevant mailing list threads include the main proposal thread and an examples thread demonstrating monadic data parsing and views:
</p>
<ul><li><a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-October/001797.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-October/001797.html</a>
</li></ul><ul><li><a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-November/001892.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-November/001892.html</a>
</li></ul><ul><li><a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-November/001915.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-November/001915.html</a>
</li></ul><hr />
<h2 id="contextandreferences:">context and references:</h2>
<p>
as has been pointed out in the thread on replacing and improving
pattern guards, Haskell's pattern matching support, even before
pattern guards, is monolithic (built-in case is the only way to handle
multiple alternative matches) rather than compositional (lambdas
seem to represent individual alternatives, but cannot be composed on
match fall-through). this implies increased complexity of the language
definition, limited expressiveness of its features, and more difficult
reasoning, when compared with alternative models (eg, Wolfram Kahl has
suggested to adapt his pattern match calculus for Haskell). see, eg.:
</p>
<p>
<a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-October/001713.html</a>
<a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-October/001720.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-October/001720.html</a>
<a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-October/001723.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-October/001723.html</a>
<a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-October/001724.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-October/001724.html</a>
</p>
<p>
as well as the PMC home page
</p>
<p>
<a class="ext-link" href="http://www.cas.mcmaster.ca/~kahl/PMC/"><span class="icon"></span>http://www.cas.mcmaster.ca/~kahl/PMC/</a>
</p>
<p>
and a newer thread discussing some differences between
this lambda-match proposal and PMC
</p>
<p>
<a class="ext-link" href="http://www.haskell.org/pipermail/haskell-prime/2006-October/001823.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell-prime/2006-October/001823.html</a>
</p>
<p>
in principle, replacing Haskell's current pattern matching support
with a simpler, more compositional model, and defining the current
constructs on top of that new core is the way forward, IMHO. in
practice, however, I suspect that the committee is less than tempted
to introduce such a substantial simplification for Haskell'.
</p>
<p>
the present proposal is an attempt at a compromise, suggesting a
minimal language change to introduce compositional pattern-match
failure and fall-through. with lambda-match, it implements only a
single language extension (as syntactic sugar), delegating the rest
of the functionality to a library. without the sugar, the result of the
by-hand translation becomes so hard to read as to be near
unusable, while the chosen form of sugaring allows to provide
most of the language features discussed in the earlier threads to
be provided as a library. this does seem to be a useable balance.
</p>
<p>
building constructs of the simpler pattern-match model on top of
the more complex one is somewhat irksome from a language design
perspective, but does at least gain the expressiveness of the simpler
model. if programmers make substantial use of this new functionality
in Haskell' (as I strongly suspect they will - I have been doing similar
translations by hand for some time now), it will be up to Haskell' ' to
turn the table, and to define the current complex model on top of a
compositional one.
</p>
<p>
as a preview of this anticipated language refactoring;), it is instructive
to compare the two alternative translations of lambda-match sketched
above:
</p>
<ul><li>the first directly builds on the existing, complex case constructs with their built-in (pattern) guards and match fall-through support; this eases adding the new, simpler features to implementations that support the old, complex ones (like GHC), but completely foregoes any attempt to simplify those implementations in the process; <em>[the attached patch for GHC follows this route]</em>
</li></ul><ul><li>the second translation avoids any direct reference to case, employing do-notation instead; this requires slightly more effort, eg. in translating pattern guards into the match monad, but is eminently suitable for adding the new features to implementations that do not support pattern guards yet, or that simply want to reduce the number of built-in constructs. <em>[patchers for Hugs, etc., might want to follow this route]</em>
</li></ul><p>
finally, while it is not directly relevant for the present proposal,
Tullsen's PADL 2000 paper investigates one way in which monadic data
parsing can be built on to go beyond first-class match alternatives
all the way to first-class patterns:
</p>
<p>
<a class="ext-link" href="http://citeseer.ist.psu.edu/tullsen00first.html"><span class="icon"></span>http://citeseer.ist.psu.edu/tullsen00first.html</a>
</p>
<p>
this, in turn, relates directly to Views and <a class="wiki" href="http://ghc.haskell.org/trac/haskell-prime/wiki/PatternSynonyms">PatternSynonyms</a>.
</p>
en-usHaskell Prime/images/HaskellLogo_2.jpg
http://ghc.haskell.org/trac/haskell-prime/ticket/114
Trac 1.0.1clausMon, 30 Oct 2006 23:23:09 GMTattachment set
http://ghc.haskell.org/trac/haskell-prime/ticket/114
http://ghc.haskell.org/trac/haskell-prime/ticket/114
<ul>
<li><strong>attachment</strong>
set to <em>ControlMonadMatch.hs</em>
</li>
</ul>
<p>
main library support for lambda-match composition, etc
</p>
TicketclausMon, 30 Oct 2006 23:24:19 GMTattachment set
http://ghc.haskell.org/trac/haskell-prime/ticket/114
http://ghc.haskell.org/trac/haskell-prime/ticket/114
<ul>
<li><strong>attachment</strong>
set to <em>ControlMonadMatchInstances.hs</em>
</li>
</ul>
<p>
instances of standard types/classes, factored out of main support library
</p>
Ticketsimonpj@…Thu, 02 Nov 2006 09:17:35 GMTdescription changed
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:1
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/trac/haskell-prime/ticket/114?action=diff&version=1">diff</a>)
</li>
</ul>
<p>
Improve formatting
</p>
TicketclausWed, 08 Nov 2006 15:43:23 GMTattachment set
http://ghc.haskell.org/trac/haskell-prime/ticket/114
http://ghc.haskell.org/trac/haskell-prime/ticket/114
<ul>
<li><strong>attachment</strong>
set to <em>LambdaMatch.hunk</em>
</li>
</ul>
<p>
updated syntax patch for GHC: be conservative, require parentheses
</p>
TicketclausWed, 08 Nov 2006 15:45:23 GMTattachment set
http://ghc.haskell.org/trac/haskell-prime/ticket/114
http://ghc.haskell.org/trac/haskell-prime/ticket/114
<ul>
<li><strong>attachment</strong>
set to <em>LambdaMatchExamples.hs</em>
</li>
</ul>
<p>
update examples for modified syntax patch (few more parentheses)
</p>
TicketclausThu, 09 Nov 2006 14:42:53 GMTdescription changed
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:2
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/trac/haskell-prime/ticket/114?action=diff&version=2">diff</a>)
</li>
</ul>
<p>
make motivations explicit, and separate context from core proposal
</p>
TicketclausFri, 10 Nov 2006 00:14:10 GMTdescription changed
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:3
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/trac/haskell-prime/ticket/114?action=diff&version=3">diff</a>)
</li>
</ul>
<p>
add a missing return in motivation, point 3; fix more formatting bugs
</p>
TicketclausTue, 21 Nov 2006 11:32:31 GMTdescription changed
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:4
http://ghc.haskell.org/trac/haskell-prime/ticket/114#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/trac/haskell-prime/ticket/114?action=diff&version=4">diff</a>)
</li>
</ul>
<p>
add references to main proposal discussion thread and examples thread
</p>
Ticket