[PATCH v4] docs/match: pattern matcher example makeover

[Blake Shaw <blake@reproduciblemedia.com>]

Sorry, this is meant to be V4*, I've updated the subject accordingly 

Blake Shaw <blake@reproduciblemedia.com> writes:

> [v4 update]
> style: revert bracketed/Indiana style conventions in for matching
> I'd rather not bikeshed over this, so reverting the style changes
> as per the mailing list discussion:
> https://lists.gnu.org/archive/html/guile-devel/2023-02/msg00001.html
>
> [V3 update]
> @xref{sxml-match} had been commented out because it was interfering
> with emacs makeinfo. This ammends that change.
>
> Also adding `--` to breakup changelog into a more digestible format.
>
> Reviewing everything all else, everything appears fine.
>
> [V2 update]
> All changes have been squashed into a single commit
>
> Before I was able to render only the pdf, but it was unclear
> how to render an individual texinfo page. Since then I discovered
> [makeinfo] in emacs which solves this problem.
>
> There is some conflict between PDF and Texinfo, and Guile currently
> seems to just choose texinfo. This update to the past patch series
> tailors the markup to best suit Texinfo, where previously PDF was
> was the rendered reference to compare against.
>
> -
> docs/match: add pattern matching examples
> --
> This commit introduces a set of examples to the documentation on
> pattern matching discussed in the Guix Days presentation which can
> be found here:
> https://xana.lepiller.eu/guix-days-2022/guix-days-2022-documentation.mp4
>
> As discussed in the Guix Days presentation, and agreed upon during the
> corresponding brainstorming session, I'm introducing a set of examples
> that intend to demonstrate the basics of the Shinn/Wright pattern
> matcher, as well as touch on some of its subtleties.
>
> Most paragraphs will be broken up into smaller peices with examples
> interspersed throughout, according to the refactoring strategy of
> "graduated expression" presented in my talk. The goal is to express the
> pedagogical aim of examples naturally through graduality, reducing
> "wordiness" primarily by with examples rather than reducing what has
> already been written.
>
> My apologies for taking so long to get to work on this! This summer
> I was confronted with a unanticipated event that subsequently turned
> my life upside down, causing my contributions to be low. I hope to be
> increasing my contributions from here on, and fulfilling my obligations
> concerning the documentation.
>
> -
> docs/match: rm unquote-splicing as it interferes with textinfo
> --
>
> -
> docs/match: add reverse nested list example
> --
>
> -
> docs/match: match-let* unwrap example
> --
> pdf now builds, but there are some spacing issues I want to correct
> in the PDF, that will be introduced next.
>
> -
> docs/fixup: @cindex was in the wrong place
> --
>
> -
> style: clean-up newlines
> --
> It appears that while the PDF needs additional newlines
> to be presentable, these appear to have a negative effect
> on the presentation of the texinfo doc.
>
> I don't know how to fix this, but from looking at the PDF,
> it appears that the strategy until now has been to privilege
> texinfo at the expense of PDF readability (the PDF is more
> or less "squished together")
>
> So in that regard, these edits make my past edits more in sync
> with past Guile docs.
>
> -
> examples: replace with didactic ex. that can copied & pasted
> --
> The existing example can't be copied and pasted.
>
> This example both fixes the past one and improves on its relation
> to the text.
>
> -
> style: switch to "Indiana style", bracketing lets and clauses
> --
> After spending much time looking at the examples in black & white
> to edit the texinfo document, it occurred to me just how much the
> brackets improve legibility. Therefore, I have decided to adopt
> the "Indiana" style of using brackets, used by Kent Dybvig, Dan
> Friedman and Will Byrd at Indiana University.
>
> Currently the docs use this style in some places but not in others.
>
> Considering some are color blind, and that few will have rigged
> their texinfo configuration to use rainbow-delimiters in the while
> reading documentation, I think this should be considered a general
> accessibility improvement.
>
> indentation: make consistent according to rule defined below
>
> If a new paragraph opens onto a new topic, it should naturally
> indent (i.e, no indentation markup is required)
>
> If a new paragraph is a continuation of the current subject,
> the markup @noident should be applied
>
> markup: replace @var with @code unless @var is a @defn argument
>
> The way that it renders in texinfo means that it renders @vars
> in uppercase, the way that is conventionally done for definition
> arguments.
>
> Therefore I've changed all @vars to @code unless @var is a @defn
> argument
>
> -
> remove: paragraph that referred to a since removed example
> --
>
> fix: uncomment @xref{sxml-match}
> ---
>  doc/ref/match.texi | 242 ++++++++++++++++++++++++++++++---------------
>  1 file changed, 162 insertions(+), 80 deletions(-)
>
> diff --git a/doc/ref/match.texi b/doc/ref/match.texi
> index f5ea43118..d69b54a81 100644
> --- a/doc/ref/match.texi
> +++ b/doc/ref/match.texi
> @@ -23,71 +23,142 @@ The @code{(ice-9 match)} module provides a @dfn{pattern matcher},
>  written by Alex Shinn, and compatible with Andrew K. Wright's pattern
>  matcher found in many Scheme implementations.
>  
> -@cindex pattern variable
> -A pattern matcher can match an object against several patterns and
> -extract the elements that make it up.  Patterns can represent any Scheme
> -object: lists, strings, symbols, records, etc.  They can optionally contain
> -@dfn{pattern variables}.  When a matching pattern is found, an
> -expression associated with the pattern is evaluated, optionally with all
> -pattern variables bound to the corresponding elements of the object:
> +@noindent A pattern matcher does precisely what the name implies: it
> +matches some arbitrary pattern, and returns some result accordingly.
>  
>  @example
> -(let ((l '(hello (world))))
> -  (match l           ;; <- the input object
> -    (('hello (who))  ;; <- the pattern
> -     who)))          ;; <- the expression evaluated upon matching
> -@result{} world
> +(define (english-base-ten->number name)
> +  (match name
> +    ('zero   0)
> +    ('one    1)
> +    ('two    2)
> +    ('three  3)
> +    ('four   4)
> +    ('five   5)
> +    ('six    6)
> +    ('seven  7)
> +    ('eight  8)
> +    ('nine   9)))
> +
> +(english-base-ten->number 'six)
> +@result{} 6
> +
> +(apply + (map english-base-ten->number '(one two three four)))
> +@result{} 10 
>  @end example
>  
> -In this example, list @var{l} matches the pattern @code{('hello (who))},
> -because it is a two-element list whose first element is the symbol
> -@code{hello} and whose second element is a one-element list.  Here
> -@var{who} is a pattern variable.  @code{match}, the pattern matcher,
> -locally binds @var{who} to the value contained in this one-element
> -list---i.e., the symbol @code{world}.  An error would be raised if
> -@var{l} did not match the pattern.
> +@page
> +@cindex pattern variable 
> +@noindent Pattern matchers may contain @dfn{pattern variables},
> +local bindings to all elements that match a pattern.
>  
> -The same object can be matched against a simpler pattern:
> +@example 
> +(let re ((ns '(one two three four 9)) (total 0)) 
> +  (match ns
> +    ((e) (+ total (english-base-ten->number e)))
> +    ((e . es) 
> +     (re es (+ total (english-base-ten->number e))))))
>  
> -@example
> -(let ((l '(hello (world))))
> -  (match l
> -    ((x y)
> -     (values x y))))
> -@result{} hello
> -@result{} (world)
> +@result{} 19
>  @end example
>  
> -Here pattern @code{(x y)} matches any two-element list, regardless of
> -the types of these elements.  Pattern variables @var{x} and @var{y} are
> -bound to, respectively, the first and second element of @var{l}.
> -
> -Patterns can be composed, and nested.  For instance, @code{...}
> +@noindent In this example, the list @code{ns} matches the pattern
> +@code{(e . es)}, where the pattern variable @code{e} corresponds 
> +to the metaphoical "car" of @code{ns} and the pattern variable @code{es}
> +corresponds to the "cdr" of @code{ns}.
> +
> +@noindent A tail call @code{re} is then initiated and we "cdr" down the
> +list by recurring on the tail @code{es}, applying our matcher
> +@code{english-base-ten->number} to each element of @code{ns} until
> +only a single element @code{(e)} remains, causing the @code{total}
> +to be computed.  In modern Scheme programming it is common to use
> +@code{match} in place of the more verbose but familiar combination
> +of @code{cond}, @code{car} and @code{cdr}, so it's important to
> +understand how these idioms translate. 
> +
> +Patterns can be composed and nested.  For instance, @code{...}
>  (ellipsis) means that the previous pattern may be matched zero or more
>  times in a list:
>  
>  @example
> -(match lst
> -  (((heads tails ...) ...)
> -   heads))
> +(match '((a.0 b.0 c.0 ((1.0 2.0 3.0) x.0 y.0 z.0))
> +         (a.1 b.1 c.1 ((1.1 2.1 3.1) x.1 y.1 z.1)))
> +  (((heads ... ((tails ...) . rest)) ...) 
> +   (begin 
> +    (format #t "heads: ~a ~%" heads)
> +    (format #t "tails: ~a ~%" tails)
> +    (format #t "rest:  ~a ~%" rest))))
> +@result{}
> +heads: ((a.0 b.0 c.0) (a.1 b.1 c.1)) 
> +tails: ((1.0 2.0 3.0) (1.1 2.1 3.1)) 
> +rest:  ((x.0 y.0 z.0) (x.1 y.1 z.1)) 
>  @end example
>  
> -@noindent
> -This expression returns the first element of each list within @var{lst}.
> -For proper lists of proper lists, it is equivalent to @code{(map car
> -lst)}.  However, it performs additional checks to make sure that
> -@var{lst} and the lists therein are proper lists, as prescribed by the
> -pattern, raising an error if they are not.
> -
> -Compared to hand-written code, pattern matching noticeably improves
> -clarity and conciseness---no need to resort to series of @code{car} and
> -@code{cdr} calls when matching lists, for instance.  It also improves
> -robustness, by making sure the input @emph{completely} matches the
> -pattern---conversely, hand-written code often trades robustness for
> -conciseness.  And of course, @code{match} is a macro, and the code it
> -expands to is just as efficient as equivalent hand-written code.
> -
> -The pattern matcher is defined as follows:
> +@noindent A pattern matcher can match an object against several
> +patterns and extract the elements that make it up. 
> +
> +@example
> +(match '((l1 . r1) (l2 . r2) (l3 . r3))
> +  (((left . right) ...)
> +   (list left right)))
> +
> +@result{} ((l1 l2 l3) (r1 r2 r3))
> +@end example
> +
> +@example
> +(match '((1 . (a . b)) (2 . (c . d)) (3 . (e . f)))
> +  (((key . (left . right)) ...) 
> +   (fold-right acons '() key right )))
> +
> +@result{} ((1 . b) (2 . d) (3 . f))
> +@end example
> +
> +@example
> +(match '(((a b c) e f g) 1 2 3)  
> +  ((((head ...) . rest) tails ...)
> +   (acons tails head rest )))
> +
> +@result {} (((1 2 3) a b c) e f g)
> +@end example
> +
> +Patterns can represent any Scheme object: lists, strings, symbols,
> +records, etc.
> +
> +@noindent When a matching pattern is found, an expression is evaluated
> +with pattern variables bound to the corresponding elements of the object.
> +
> +@example
> +(let re ((m #(a "b" c "d" e "f" g)))
> +   (match m
> +     ((or (e) #(e)) e)
> +     ((or #(e1 e2 es ...)
> +	   (e1 e2 es ...)) 
> +      (cons (cons e1 e2)
> + 	    (re es)))))
> +
> +@result{} ((a . "b") (c . "d") (e . "f") . g) 
> +@end example
> +
> +@example
> +(let re ((m '(a b c d e f g h i)))
> +   (match m
> +     ((e) e)
> +     ((e1 e2 es ...) 
> +      (acons e1 e2 (re es)))))
> +
> +@result{} ((a . b) (c . d) (e . f) (g . h) . i)
> +@end example
> +
> +@noindent Compared to hand-written code, pattern matching noticeably
> +improves clarity and conciseness---no need to resort to series of
> +@code{car} and @code{cdr} calls when matching lists, for instance.
> +It also improves robustness, by making sure the input @emph{completely}
> +matches the pattern---conversely, hand-written code often trades
> +robustness for conciseness.  And of course, @code{match} is a macro,
> +and the code it expands to is just as efficient as equivalent
> +hand-written code.
> +
> +@noindent We define @code{match} as follows: @*
>  
>  @deffn {Scheme Syntax} match exp clause1 clause2 @dots{}
>  Match object @var{exp} against the patterns in @var{clause1}
> @@ -96,9 +167,9 @@ value produced by the first matching clause.  If no clause matches,
>  throw an exception with key @code{match-error}.
>  
>  Each clause has the form @code{(pattern body1 body2 @dots{})}.  Each
> -@var{pattern} must follow the syntax described below.  Each body is an
> +@code{pattern} must follow the syntax described below.  Each body is an
>  arbitrary Scheme expression, possibly referring to pattern variables of
> -@var{pattern}.
> +@code{pattern}.
>  @end deffn
>  
>  @c FIXME: Document other forms:
> @@ -114,7 +185,7 @@ arbitrary Scheme expression, possibly referring to pattern variables of
>  @c
>  @c clause ::= (pat body) | (pat => exp)
>  
> -The syntax and interpretation of patterns is as follows:
> +@noindent @* The pattern language is specified as follows: @*
>  
>  @verbatim
>          patterns:                       matches:
> @@ -176,12 +247,12 @@ qp  ::= ()                              the empty list
>        | ,@pat                           a pattern
>  @end verbatim
>  
> -The names @code{quote}, @code{quasiquote}, @code{unquote},
> +@noindent The names @code{quote}, @code{quasiquote}, @code{unquote},
>  @code{unquote-splicing}, @code{?}, @code{_}, @code{$}, @code{and},
>  @code{or}, @code{not}, @code{set!}, @code{get!}, @code{...}, and
>  @code{___} cannot be used as pattern variables.
>  
> -Here is a more complex example:
> +Here is a more complex example using records and promises:
>  
>  @example
>  (use-modules (srfi srfi-9))
> @@ -205,12 +276,12 @@ Here is a more complex example:
>  
>  @noindent
>  Here the @code{$} pattern is used to match a SRFI-9 record of type
> -@var{person} containing two or more slots.  The value of the first slot
> -is bound to @var{name}.  The @code{=} pattern is used to apply
> +@code{person} containing two or more slots.  The value of the first slot
> +is bound to @code{name}.  The @code{=} pattern is used to apply
>  @code{force} on the second slot, and then checking that the result
>  matches the given pattern.  In other words, the complete pattern matches
> -any @var{person} whose second slot is a promise that evaluates to a
> -one-element list containing a @var{person} whose first slot is
> +any @code{person} whose second slot is a promise that evaluates to a
> +one-element list containing a @code{person} whose first slot is
>  @code{"Bob"}.
>  
>  The @code{(ice-9 match)} module also provides the following convenient
> @@ -229,11 +300,11 @@ expressions.
>  @end deffn
>  
>  @example
> -((match-lambda
> -   (('hello (who))
> -    who))
> - '(hello (world)))
> -@result{} world
> +(define flatten-singletons 
> +   (match-lambda (((s) ...) s)))
> +
> +(flatten-singletons '((x) (y) (z)))
> +@result{} (x y z) 
>  @end example
>  
>  @deffn {Scheme Syntax} match-lambda* clause1 clause2 @dots{}
> @@ -264,11 +335,10 @@ and can also be used for recursive functions which match on their
>  arguments as in @code{match-lambda*}.
>  
>  @example
> -(match-let (((x y) (list 1 2))
> -            ((a b) (list 3 4)))
> -  (list a b x y))
> -@result{}
> -(3 4 1 2)
> +(match-let (((x y ...) (list 1 2 3))
> +            ((a b ...) (list 3 4 5)))
> +  (list x a y b))
> +@result{} (1 3 (2 3) (4 5))
>  @end example
>  @end deffn
>  
> @@ -287,22 +357,34 @@ Similar to @code{match-let}, but analogously to @code{let*}, match and
>  bind the variables in sequence, with preceding match variables in scope.
>  
>  @example
> -(match-let* (((x y) (list 1 2))
> -             ((a b) (list x 4)))
> -  (list a b x y))
> +(match-let* (((x . y) (list 1 2 3))
> +             ((a . b) (list x 4 y)))
> +  (list a b))
>  @equiv{}
> -(match-let (((x y) (list 1 2)))
> -  (match-let (((a b) (list x 4)))
> -    (list a b x y)))
> -@result{}
> -(1 4 1 2)
> +(match-let (((x . y) (list 1 2)))
> +  (match-let (((a . b) (list x 4 y)))
> +    (list a b)))
> +@result{} (1 (4 (2 3)))
>  @end example
>  @end deffn
>  
> +@example
> +(define wrap '(((((unnest arbitrary nestings))))))
> +
> +(let unwrap ((peel wrap)) 
> +  (match-let* ((((core ...)) peel)
> +	       ((wrapper ...) core))
> +    (if (> (length wrapper) 1) 
> +	wrapper 
> +	(unwrap wrapper))))
> +
> +@result{} (unnest arbitrary nestings)
> +@end example
> +
>  @deffn {Scheme Syntax} match-letrec ((variable expression) @dots{}) body
>  Similar to @code{match-let}, but analogously to @code{letrec}, match and
>  bind the variables with all match variables in scope.
>  @end deffn
>  
> -Guile also comes with a pattern matcher specifically tailored to SXML
> -trees, @xref{sxml-match}.
> +@noindent Guile also comes with a pattern matcher specifically
> +tailored to SXML trees, @xref{sxml-match}.