Changeset ce06be2 in report


Ignore:
Timestamp:
Jan 12, 2007 12:59:30 AM (11 years ago)
Author:
Isaac Potoczny-Jones <ijones@…>
Branches:
h2010, master
Children:
6d9baa1
Parents:
1083481
Message:

reworking the informal explanation of pattern gaurds
Modified the syntax again to talk about "guards" (which are pattern guards,
boolean guards, and let expressions) . Moved the "Pattern guards" section
I created before into the Case Expressions section.

Location:
report
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • report/decls.verb

    r1083481 rce06be2  
    15331533        |   gdrhs [@where@ decls]
    15341534
    1535 gdrhs   ->  gd @=@ exp [gdrhs]
    1536 
    1537 gd      ->  @|@ exp^0
     1535gdrhs   ->  guards @=@ exp [gdrhs]
     1536
     1537guards  ->  @|@ guard_1, ..., guard_n             & (n>=1)
     1538
    15381539@@@
    15391540\indexsyn{decl}%
    15401541\indexsyn{rhs}%
    15411542\indexsyn{gdrhs}%
    1542 \indexsyn{gd}%
     1543\indexsyn{qs}%
    15431544We distinguish two cases within this syntax: a {\em pattern binding}
    15441545occurs when the left hand side is a "pat^0";
  • report/exps.verb

    r1083481 rce06be2  
    664664types are in @Enum@ and their semantics.
    665665
    666 \subsection{Qualifiers in Patterns}
    667 \index{qualifier}
    668 \label{qualifiers-in-patterns}
    669 @@@
    670 qual    -> pat @<-@ exp         & (\tr{generator}, or \tr{pattern guard})
    671          | @let@ decls          & (\tr{local declaration})
    672          | exp                  & (\tr{guard})
    673 @@@
    674 \indexsyn{qual}
    675 
    676 A {\em qualifier}\index{qualifier} has one of the following forms:
    677 \begin{itemize}
    678 \item {\em generators}\index{generator} (also known as {\em pattern guards}\index{pattern guard} of the form "p @<-@ e", where
    679 "p" is a
    680 pattern (see Section~\ref{pattern-matching}) of type "t" and "e" is an
    681 expression of type "@[@t@]@"
    682 \item {\em guards},\index{guard} which are arbitrary expressions of
    683 type @Bool@
    684 \item {\em local bindings} that provide new definitions for use in
    685 the generated expression "e" or subsequent guards and generators.
    686 \end{itemize}
    687 
    688 The first qualifier has the same environment as the right-hand-side of
    689 the case-expression alternative, function definition, or pattern
    690 binding to which it is attached.  A qualifier creates successive
    691 environments for "e" created by the nested, depth-first evaluation of
    692 the generators and let bindings in the qualifier list.  Binding of
    693 variables within generators occurs according to the normal pattern
    694 matching rules (see Section~\ref{pattern-matching}), and may fail.  A
    695 qualifier matches if all of the guards in that qualifier evaluate to
    696 @True@ and all of the generators match, otherwise it fails.
    697 
    698666\subsection{List Comprehensions}
    699667\index{list comprehension}
     
    703671@@@
    704672aexp    -> @[@ exp @|@ qual_1 @,@ ... @,@ qual_n @]@    & (\tr{list comprehension}, n>=1)
     673qual    -> pat @<-@ exp         & (\tr{generator})
     674         | @let@ decls          & (\tr{local declaration})
     675         | exp                  & (\tr{boolean guard})
    705676@@@
    706677\indexsyn{aexp}
     678\indexsyn{qual}
    707679
    708680\noindent
    709 A {\em list comprehension} has the form "@[@ e @|@ q_1@,@ ...@,@ q_n
    710 @]@, n>=1," where the "q_i" are qualifiers as in
    711 Section~\ref{qualifiers-in-patterns}.
    712 
    713 Such a list comprehension returns the list of elements produced by
    714 evaluating "e" in the environments created by the qualifiers.  If a match
    715 fails then that element of the list is simply skipped over.  Thus:\nopagebreak[4]
     681A {\em list comprehension} has the form "@[@ e @|@ q_1@,@ ...@,@ q_n @]@,
     682n>=1," where the "q_i" qualifiers\index{qualifier} are either
     683\begin{itemize}
     684\item {\em generators}\index{generator} of the form "p @<-@ e", where
     685"p" is a
     686pattern (see Section~\ref{pattern-matching}) of type "t" and "e" is an
     687expression of type "@[@t@]@"
     688\item {\em boolean guards},\index{boolean guard} which are arbitrary expressions of
     689type @Bool@
     690\item {\em local bindings} that provide new definitions for use in
     691the generated expression "e" or subsequent boolean guards and generators.
     692\end{itemize}
     693
     694Such a list comprehension returns the list of elements
     695produced by evaluating "e" in the successive environments
     696created by the nested, depth-first evaluation of the generators in the
     697qualifier list.  Binding of variables occurs according to the normal
     698pattern matching rules (see Section~\ref{pattern-matching}), and if a
     699match fails then that element of the list is simply skipped over.  Thus:\nopagebreak[4]
    716700\bprog
    717701@
     
    720704@
    721705\eprog
    722 yields the list @[4,2]@.  If a qualifier is a guard, it must evaluate
     706yields the list @[4,2]@.  If a qualifier is a boolen guard, it must evaluate
    723707to @True@ for the previous pattern match to succeed. 
    724708As usual, bindings in list comprehensions can shadow those in outer
     
    833817        |                                       & (empty alternative)
    834818
    835 gdpat   ->  qs @->@ exp [ gdpat ]
    836 qs      ->  @|@ qual_1, ..., qual_n
     819gdpat   ->  guards @->@ exp [ gdpat ]
     820guards  ->  @|@ guard_1, ..., guard_n             & (n>=1)
     821guard   -> pat @<-@ exp^0       & (\tr{pattern guard})
     822         | @let@ decls          & (\tr{local declaration})
     823         | exp^0                & (\tr{boolean guard})
    837824@@@
    838825\indexsyn{exp}%
     
    840827\indexsyn{alt}%
    841828\indexsyn{gdpat}%
    842 \indexsyn{gd}%
     829\indexsyn{guards}%
     830\indexsyn{guard}%
     831
    843832
    844833A {\em case expression}\index{case expression} has the general form
     
    848837where each "match_i" is of the general form
    849838\[\ba{lll}
    850  & "@|@ q_{i1}"   & "@->@ e_{i1}" \\
     839 & "@|@ gs_{i1}"   & "@->@ e_{i1}" \\
    851840 & "..." \\
    852  & "@|@ q_{im_i}" & "@->@ e_{im_i}" \\
     841 & "@|@ gs_{im_i}" & "@->@ e_{im_i}" \\
    853842 & \multicolumn{2}{l}{"@where@ decls_i"}
    854843\ea\]
    855 (Notice that in the syntax rule for "qs", the ``@|@'' is a
     844(Notice that in the syntax rule for "guards", the ``@|@'' is a
    856845terminal symbol, not the syntactic metasymbol for alternation.)
    857846Each alternative "p_i match_i" consists of a
    858847pattern\index{pattern} "p_i" and its matches, "match_i".
    859848Each match in turn
    860 consists of a sequence of pairs of qualifiers\index{qualifier}
    861 "q_{ij}" and bodies "e_{ij}" (expressions), followed by
    862 optional bindings ("decls_i") that scope over all of the qualifiers and
    863 expressions of the alternative.  An alternative of the form
     849consists of a sequence of pairs of guards\index{guard}
     850"gs_{ij}" and bodies "e_{ij}" (expressions), followed by
     851optional bindings ("decls_i") that scope over all of the guards and
     852expressions of the alternative.
     853
     854\index{Pattern Guards}
     855\index{guards}
     856A {\em guard}\index{guard} has one of the following forms:
     857\begin{itemize}
     858\item {\em pattern guards}\index{pattern guard} are of the form "p @<-@ e", where
     859"p" is a
     860pattern (see Section~\ref{pattern-matching}) of type "t" and "e" is an
     861expression type "t".  They succeed if the expression "e" matches the pattern "p", and introduce the bindings of the pattern to the environment.
     862\item {\em boolean guards}\index{boolean guard} are arbitrary expressions of
     863type @Bool@.  They succeed if the expression evaluates to @True@, and they do not introduce new names to the environment.  A boolean guard, "g", is semantically equivalent to the pattern guard "@True <- @g".
     864\item {\em local bindings} are of the form "@let @decls".  They always succeed, and they introduce the names defined in "decls" to the environment.
     865\end{itemize}
     866
     867
     868An alternative of the form
    864869\[
    865870"pat @->@ exp @where@ decls"
     
    877882A case expression is evaluated by pattern matching the expression "e"
    878883against the individual alternatives.  The alternatives are tried
    879 sequentially, from top to bottom.  If "e" matches the pattern in the
    880 alternative, the qualifiers for that alternative are tried
    881 sequentially from top to bottom, in the environment of the case
     884sequentially, from top to bottom.  If "e" matches the pattern of an
     885alternative, then the guarded expressions for that alternative are
     886tried sequentially from top to bottom in the environment of the case
    882887expression extended first by the bindings created during the matching
    883 of the pattern, and then by the bindings of variables within the
    884 qualifier list (either by using a let clause or a generator), and then
    885 by the "decls_i" in the @where@ clause associated with that
    886 alternative.
    887 
    888 If one of the qualifiers matches (see
    889 Section~\ref{qualifiers-in-patterns}), the corresponding right-hand
    890 side is evaluated in the same environment as the guard.
    891 
    892 If none of the qualifiers for a given alternative match, matching
    893 continues with the next alternative.  If no match succeeds, the result
    894 is "\bot".  Pattern matching is described in
     888of the pattern, and then by the "decls_i" in the @where@ clause
     889associated with that alternative.
     890
     891For each guarded expression, the comma-separated guards are tried
     892sequentially from left to right.  If all of them succeed, then the
     893corresponding expression is evaluated in the environment extended with
     894the bindings introduced by the guards.  That is, the bindings that are
     895introduced by a guard (either by using a let clause or a pattern
     896guard) are in scope in the following guards and the corresponding
     897expression.  If any of the guards fail, then this guarded expression
     898fails and the next guarded expression is tried.
     899
     900If none of the guarded expressions for a given alternative succeed,
     901then matching continues with the next alternative.  If no alternative
     902succeeds, then the result is "\bot".  Pattern matching is described in
    895903Section~\ref{pattern-matching}, with the formal semantics of case
    896904expressions in Section~\ref{case-semantics}.
     
    911919parsers with limited lookahead may incorrectly commit to this choice, and hence
    912920reject the program.  Programmers are advised, therefore, to avoid guards that
    913 end with a type signature --- indeed that is why a "gd" contains
     921end with a type signature --- indeed that is why a "guard" contains
    914922an "exp^0" not an "exp".
    915923
Note: See TracChangeset for help on using the changeset viewer.