202: Pattern-matching Variant of the and-let* Form that Supports Multiple Values

by Panicz Maciej Godek

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-202@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Received: 2020-06-19
Draft #1 published: 2020-06-25
Draft #2 published: 2020-11-17
Finalized: 2020-11-28

Abstract

The SRFI-2 library introduced the and-let* form for short-circuited evaluation in the style of the and form, with the ability to capture the (non-#f) results in the style of the let* form. This document extends the and-let* form with the ability to pattern-match (or "destructurally bind") the values of evaluated expressions (where the match failure causes short-circuiting rather than raising an error) and the ability to handle multiple values (where only the falsehood of the first value causes short-circuiting).

Rationale

It is well known that, in the context of the if condition, Scheme treats #f as a false value, and every other value is considered true (or "true-ish").

This design decision has led to the development of the idiom in which the #f is considered to represent "the absence of value" or a "failure of computation", whereas any other value is considered to represent a meaningful result.

In strongly typed languages, this pattern is usually expressed in terms of algebraic data types. For example, the Haskell language defines the polymorphic type Maybe a as either Just a or Nothing, where Just a is used to represent a value of type a, and Nothing is used to represent the absence of value.

Moreover, in many functional languages, the types isomorphic to Maybe are considered to be "monads", which means that they can use some facilities that those languages provide for sequencing functions that return things that are considered to be "monads". In particular, Haskell provides a special syntactic form called the do notation, which allows a function like

  h x = case (f x) of
          Just y -> case (g (k y)) of
                      Just z -> Just (l z)
                      Nothing -> Nothing
          Nothing -> Nothing

to be rewritten as

  h x = do
    y <- (f x)
    z <- (g (k y))
    return (l z)

where f and g (and h) return optional values, and k and l return obligatory values.

Since these facilities rely on some advanced features of type systems that are lacking from most Scheme implementations, Schemers have invented a special form specifically for dealing with optional values. The form is called and-let*, and was defined in SRFI 2.

Accordingly, the equivalent code using Scheme can be written as

  (define (h x)
    (and-let* ((y (f x))
               (z (g (k y))))
      (l z)))

However, the original definition of and-let* does not allow one to handle multiple values. It also doesn't allow one to destructure the value of the evaluated expression. The purpose of this SRFI is to extend the and-let* form with these capabilities.

Therefore, with the capabilities from this SRFI, the two first examples from the Rationale section of SRFI 2, namely:

  (and-let* ((my-list (compute-list))
             ((pair? my-list)))
    (do-something my-list))

  (define (lookup key alist)
    (and-let* ((x (assq key alist))
               ((pair? x)))
      (cdr x)))

could roughly be rewritten as:

  (and-let* ((`(,my . ,list) (compute-list)))
    (do-something `(,my . ,list)))

  (define (lookup key alist)
    (and-let* ((`(,key . ,value) (assq key alist)))
      key))

Specification

The extensions provided here do not invalidate or modify any of the prior uses of the SRFI 2's and-let* form.

In particular, the and-let* form allowed two types of expressions inside of its "claws":

(variable expression)

and

(guard-expression)

This SRFI document allows variable to be an arbitrary pattern that is a valid pattern of the underlying pattern matcher (see SRFI 200 Pattern Matching for more details):

(pattern expression)

In particular, since patterns can be literal values, it is possible to negate the condition:

  (and-let*  ((my-list (compute-list))
              (#f (null? my-list)))
    (do-something my-list))

If the value of an expression does not match the pattern, then the value of the whole and-let* form is #f.

This variant of the and-let* form also supports multiple values, each of which can be a pattern:

(pattern patterns ... expression)

If the first pattern is a variable, then it must have a non-#f value in order to proceed with evaluation — otherwise, the value of the whole and-let* form becomes #f.

If the expression returns fewer values than expected, then the value of the whole and-let* expression becomes #f. If it returns more values than expected, then the additional values are ignored.

In addition, following SRFI 71 and SRFI 201 - the extension proposed here supports the values keyword specially, allowing one to capture "the remaining values" in a list - for example, the claws of form

((values p1 p2 . v*) expression)

(where values is to be treated as a literal symbol) requires that expression returns at least two values; the first two will be bound to patterns p1 and p2 (if they match), and the remaining values, if present, will be captured in a list v*.

If the expression returns (in this case) less than two values, then the whole and-let* form short-circuits to #f.

Implementation

(define-syntax and-let*
  (lambda (stx)
    (syntax-case stx (values)

      ((_)
       #'#t)

      ((_ ())
       #'#t)

      ((_ () body ...)
       #'(let () body ...))

      ((_ ((name binding) rest ...) body ...)
       (identifier? #'name)
       #'(let ((name binding))
	   (and name
		(and-let* (rest ...)
	           body ...))))

      ((_ (((values . structure) expression) rest ...)
          body ...)
       #'(call-with-values (lambda () expression)
	   (lambda args
	     (match args
	       (structure
		(and-let* (rest ...)
		  body ...))
	       (_ #f)))))

      ((_ ((value expression) rest ...) body ...)
       #'(match expression
	   (value
	    (and-let* (rest ...)
	      body ...))
	   (_ #f)))

      ((_ ((condition) rest ...)
	  body ...)
       #'(and condition
	      (and-let* (rest ...)
		body ...)))

      ((_ ((value * ... expression) rest ...) body ...)
       (identifier? #'value)
       #'(call-with-values (lambda () expression)
	   (lambda args
	     (match args
	       ((value * ... . _)
		(and value
		     (and-let* (rest ...)
		       body ...)))
	       (_ #f)))))

      ((_ ((value ... expression) rest ...) body ...)
       #'(call-with-values (lambda () expression)
	   (lambda args
	     (match args
	       ((value ... . _)
		(and-let* (rest ...)
		  body ...))
	       (_ #f)))))

      )))

The repository for this SRFI contains an implementation for Guile built on top of the (ice-9 match) module a.k.a. Wright-Cartwright-Shinn matcher, and an implementation for Racket, built on top of Racket's racket/match module. A suite of testable examples is available for both Guile and Racket.

Acknowledgements

The original and-let* form was conceived by Oleg Kiselyov, who owes the credit for both the idea and the name. It was one of the earliest documents described within the SRFI process, as it received the number 2.

The editor of this SRFI turned out to be a real Schemer, and when I asked him if it would be possible to make sure that it gets the number 202, he said he would do his best. (I'm sorry for turning you in, Arthur. [ed. note: I confess that this wasn't the first numerical reservation for a SRFI.])

This SRFI owes the support for values keyword to Marc Nieper Wißkirchen, who pointed out the limitations of the solution that I initially proposed. Marc's remarks about backward compatibility also helped to improve this text.

The technique of pattern matching on data structures was brought to Scheme by Andrew K. Wright and Robert Cartwright through Alex Shinn's implementation, which has been distributed with many implementations of Scheme.

My first contact with Scheme was through Guile, which is a part of the GNU project. I found Guile to have exceptionally good documentation, optimized for people who spend their lives in VT100 terminal emulators. The maintainers of Guile at that time were Neil Jerram, Ludovic Courtes, Andy Wingo and Mark Weaver.

The person responsible for convincing me that it makes sense to express my ideas and developments regarding Scheme in the form of SRFI documents is John Cowan.

Copyright

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler