From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Blake Shaw Newsgroups: gmane.lisp.guile.devel Subject: [PATCH v4] docs/match: pattern matcher example makeover Date: Fri, 03 Feb 2023 20:32:06 +0700 Message-ID: <7zbkmalvqp.fsf@reproduciblemedia.com> References: <20230203132615.17788-1-blake@reproduciblemedia.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="17921"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Blake Shaw To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Fri Feb 03 14:33:44 2023 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pNwCE-0004NN-94 for guile-devel@m.gmane-mx.org; Fri, 03 Feb 2023 14:33:42 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pNwBw-0004mQ-Fn; Fri, 03 Feb 2023 08:33:24 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pNwBs-0004lD-FI for guile-devel@gnu.org; Fri, 03 Feb 2023 08:33:20 -0500 Original-Received: from out-77.mta1.migadu.com ([95.215.58.77]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pNwBp-00039T-6h for guile-devel@gnu.org; Fri, 03 Feb 2023 08:33:20 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=reproduciblemedia.com; s=key1; t=1675431195; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=YCf3/PMZ44dWH0kRi/uhsYjniOe38wrVbLKufqNBAFQ=; b=W8ZA1muAsqm4G8Iupd7SWNXb9w9o4BtP+5B93gr/+4YgipYuVj5MOZEWJ2rN4VGzH2sKlY NGNgY1EXb+3KFzE0cnZLx/hmcRd+20DHKcmwgiJAPqSJqTywLO5fcLrCFAxYSI0CNGuGap gDzfRoqK9bmeS+O+uQCNc7pXMI5pgbo= X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. In-reply-to: <20230203132615.17788-1-blake@reproduciblemedia.com> X-Migadu-Flow: FLOW_OUT Received-SPF: pass client-ip=95.215.58.77; envelope-from=blake@reproduciblemedia.com; helo=out-77.mta1.migadu.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.lisp.guile.devel:21678 Archived-At: Sorry, this is meant to be V4*, I've updated the subject accordingly Blake Shaw 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}.