List comprehensions and pattern matching
Phil Bewig
highly useful forms of syntactic sugar. List comprehensions perform
looping computations involving lists. Pattern matching destructures
lists, selecting alternatives and binding variables. Together, they
enable concise but highly-readable expressions for processing lists.
This note describes a simple implementation of list comprehensions and
pattern matching.
List comprehensions are provided by the list-of macro. The syntax
(list-of expr clause ...) produces a possibly-null list of objects of
the type returned by expr. There are four types of clauses:
- (var range first past [step]) -- Bind var to first, first + step,
..., until reaching past, which is not included in the output.
If step is not given, it defaults to 1 if (< first past) and -1
otherwise. First, past and step may be of any numeric type; if
any of first, past or step are inexact, the length of the output
list may differ from (ceiling (- (/ (- past first) step) 1).
- (var in list-expr) -- Loop over the elements of list-expr, in
order from the start of the list, binding each element of the
list in turn to var.
- (var is expr) -- Bind var to the value obtained by evaluating
expr.
- (pred? expr) -- Include in the output list only those elements
x for which (pred? x) is non-#f.
The scope of variables bound in the list comprehension is the clauses
to the right of the binding clause (but not the binding clause itself)
plus the result expression. When two or more generators are present,
the loops are processed as if they are nested from left to right; that
is, the rightmost generator varies fastest. As a degenerate case, if
no generators are present, the result of a list comprehension is a
list containing the result expression; thus, (list-of 1) produces a
list containing only the element 1.
Consider the example list comprehension shown below:
(list-of (+ y 6)
(x in '(1 2 3 4 5))
(odd? x)
(y is (* x x)))
The first clause is (x in '(1 2 3 4 5)), where in is a keyword, x is
a binding variable, and '(1 2 3 4 5) is the input list; the list
comprehension will loop through '(1 2 3 4 5), binding each list
element in turn to the variable x, continuing through the rest of the
list comprehension.
The second clause is a predicate, (odd? x), which passes only those
elements which cause the predicate to be true. In this case, the loop
which originally had five elements will pass only three elements, 1,
3, and 5, to the remaining clauses of the list comprehension.
The third and final clause is (y is (* x x)), which binds y to the
value resulting from the expression (* x x). This binding is applied
to three items in turn, returning 1, 9, and 25.
Finally, the list comprehension returns the list (7 15 31), which is
the result of applying the result expression (+ y 6) to each of the
three items returned by the final clause. The list-of macro expands
this expression into something you are probably glad you don't have
to write yourself:
(let loop ((z '(1 2 3 4 5)))
(if (null? z)
'()
(let ((x (car z)))
(if (odd? x)
(let ((y (* x x)))
(cons (+ y 6) (loop (cdr z))))
(loop (cdr z))))))
That same list could be generated in several other ways. A range
clause loops over numeric sequences, so the in clause above could be
rewritten as shown below; note that the final argument of the range
clause never appears, which is useful in those frequent cases where
you want to iterate from 0 to n-1.
(list-of (+ y 6)
(x range 1 6)
(odd? x)
(y is (* x x)))
Another way to write that same comprehension uses a step size provided
by the user instead of the default step size of 1:
(list-of (+ y 6)
(x range 1 6 2)
(y is (* x x)))
List comprehensions are expanded by a macro that calls itself
recursively, one level of recursion for each clause plus a final level
of recursion for the base case. The complete implementation, which
is based on the set contructor in Kent Dybvig's book "The Scheme
Programming Language," is given below:
(define-syntax list-of
(syntax-rules (range in is)
((_ "aux" expr base)
(cons expr base))
((_ "aux" expr base (x range first past step) clauses ...)
(let ((more? (if (positive? step) < >)))
(let loop ((z first))
(if (more? z past)
(let ((x z))
(list-of "aux" expr (loop (+ z step)) clauses ...))
base))))
((_ "aux" expr base (x range first past) clauses ...)
(let* ((step (if (< first past) 1 -1))
(more? (if (positive? step) < >)))
(let loop ((z first))
(if (more? z past)
(let ((x z))
(list-of "aux" expr (loop (+ z step)) clauses ...))
base))))
((_ "aux" expr base (x in xs) clauses ...)
(let loop ((z xs))
(if (null? z)
base
(let ((x (car z)))
(list-of "aux" expr (loop (cdr z)) clauses ...)))))
((_ "aux" expr base (x is y) clauses ...)
(let ((x y))
(list-of "aux" expr base clauses ...)))
((_ "aux" expr base pred? clauses ...)
(if pred?
(list-of "aux" expr base clauses ...)
base))
((_ expr clauses ...)
(list-of "aux" expr '() clauses ...))))
Pattern matching on lists is provided by the list-match macro. The
syntax (list-match expr clause ...) takes an input expr that evaluates
to a list. Clauses are of the form (pattern [fender] expr),
consisting
of a pattern that matches a list of a particular shape, an optional
fender that must succeed if the pattern is to match, and an expr that
is evaluated if the pattern matches. There are four types of
patterns:
- () -- Matches the null list.
- (pat0 pat1 ...) -- Matches a list with length exactly equal to the
number of pattern elements.
- (pat0 pat1 ... . patRest) -- Matches a list with length at least
as great as the number of pattern elements before the literal dot.
PatRest is a list containing the remaining elements of the input
list after the initial prefix of the list before the literal dot.
- pat -- Matches an entire list. Should always appear as the last
clause; it's not an error to appear elsewhere, but subsequent
clauses could never match.
Each pattern element may be:
- An identifier -- Matches any list element. Additionally, the
value of the list element is bound to the variable named by the
identifier, which is in scope in the fender and expr of the
corresponding clause. Each identifier in a single pattern must
be unique.
- A literal underscore -- Matches any list element, but creates no
bindings.
- A constant -- Matches if the expression equals the constant value,
but creates no bindings.
- A quote expression -- Matches if the expression equals the quote
expression, but creates no bindings.
- A quasiquote expression -- Matches if the expression equals the
quasiquote expression, but creates no bindings.
All comparisons are made with equal?. The patterns are tested in
order,
left to right, until a matching pattern is found; if fender is
present,
it must evaluate as non-#f for the match to be successful. Pattern
variables are bound in the corresponding fender and expression. Once
the matching pattern is found, the corresponding expr is evaluated and
returned as the result of the match. An error is signaled if no
pattern
matches the input list.
A simple match expression that computes the length of a list is given
below; the first pattern is the null list, which forms the base of the
recursion, and the second pattern matches a non-null input list, using
an underscore to signal that the value of the list element is not
bound in the result expression:
(define (len xs)
(list-match xs
(() 0)
((_ . xs) (+ 1 (len xs)))))
Fenders can test the common case where two list elements must be
identical; (unique eql? xs) casts out adjacent duplicates from an
input list:
(define (unique eql? xs)
(list-match xs
(() '())
((x) (list x))
((x y . rest) (eql? x y) (unique eql? (cons y rest)))
((x . rest) (cons x (unique eql? rest)))))
A more complex example uses two nested matchers to merge two input
lists ordered by the lt? predicate:
(define (list-merge lt? xx yy)
(list-match xx
(() yy)
((x . xs)
(list-match yy
(() xx)
((y . ys)
(if (lt? y x)
(cons y (list-merge lt? xx ys))
(cons x (list-merge lt? xs yy))))))))
Pattern matching is performed by a macro that expands into a cond
expression with one clause per pattern; an auxiliary macro handles the
various types of pattern elements. The complete implementation, which
is based on an idea of Jos Koot, is given below:
(define-syntax list-match
(syntax-rules ()
((_ expr (pattern fender ... template) ...)
(let ((obj expr))
(cond ((list-match-aux obj pattern fender ...
(list template)) => car) ...
(else (error 'list-match "pattern failure")))))))
(define-syntax list-match-aux
(lambda (stx)
(define (underscore? x)
(and (identifier? x) (bound-identifier=? x (syntax _))))
(syntax-case stx (quote quasiquote)
((_ obj pattern template)
(syntax (list-match-aux obj pattern #t template)))
((_ obj () fender template)
(syntax (and (null? obj) fender template)))
((_ obj underscore fender template)
(underscore? (syntax underscore))
(syntax (and fender template)))
((_ obj var fender template)
(identifier? (syntax var))
(syntax (let ((var obj)) (and fender template))))
((_ obj (quote datum) fender template)
(syntax (and (equal? obj (quote datum)) template)))
((_ obj (quasiquote datum) fender template)
(syntax (and (equal? obj (quasiquote datum)) fender
template)))
((_ obj (kar . kdr) fender template)
(syntax (and (pair? obj)
(let ((kar-obj (car obj)) (kdr-obj (cdr obj)))
(list-match-aux kar-obj kar
(list-match-aux kdr-obj kdr fender
template))))))
((_ obj const fender template)
(syntax (and (equal? obj const) fender template))))))
There are other systems that provide list comprehensions and pattern
matching. Sebastian Egner provides list comprehensions in SRFI-42.
Andrew Wright wrote a popular pattern matching package. And there are
others. But the list-of and list-match macros given above seem to hit
a sweet spot among possible list comprehensions and pattern matching;
they provide essential features, but avoid "feeping creaturitis."
They
are useful, and belong in every Scheme programmer's toolkit.
Phil
Grant Rettke
Aaron Hsu
> Despite their simplicity, list comprehensions and pattern matching are
> highly useful forms of syntactic sugar. List comprehensions perform
> looping computations involving lists. Pattern matching destructures
> lists, selecting alternatives and binding variables. Together, they
> enable concise but highly-readable expressions for processing lists.
> This note describes a simple implementation of list comprehensions and
> pattern matching.
I'm going to say that I don't see this as particularly useful given the
existance of Foof Loop by Taylor Campbell. I'd be interested in seeing
what additional or new features or syntactic advantages your solution
provided over the Nested Foof Loop forms of collecting lists.
<http://mumble.net/~campbell/scheme/foof-loop.scm>
<http://mumble.net/~campbell/scheme/foof-loop.txt>
<http://mumble.net/~campbell/tmp/nested-foof-loop.scm>
<http://mumble.net/~campbell/tmp/nested-foof-loop.txt>
--
Aaron Hsu <arc...@sacrideo.us> | Jabber: arc...@jabber.org
``Government is the great fiction through which everybody endeavors to
live at the expense of everybody else.'' - Frederic Bastiat
klohm...@yahoo.de
Phil Bewig wrote:
> There are other systems that provide list comprehensions and pattern
> matching. Sebastian Egner provides list comprehensions in SRFI-42.
> Andrew Wright wrote a popular pattern matching package. And there are
> others. But the list-of and list-match macros given above seem to hit
> a sweet spot among possible list comprehensions and pattern matching;
> they provide essential features, but avoid "feeping creaturitis."
> They
> are useful, and belong in every Scheme programmer's toolkit.
Hi: Have you had a look at Bigloo its standard pattern matching
facility?
Phil Bewig
> Phil Bewig <pbe...@gmail.com> wrote:
> > Despite their simplicity, list comprehensions and pattern matching are
> > highly useful forms of syntactic sugar. List comprehensions perform
> > looping computations involving lists. Pattern matching destructures
> > lists, selecting alternatives and binding variables. Together, they
> > enable concise but highly-readable expressions for processing lists.
> > This note describes a simple implementation of list comprehensions and
> > pattern matching.
>
> I'm going to say that I don't see this as particularly useful given the
> existance of Foof Loop by Taylor Campbell. I'd be interested in seeing
> what additional or new features or syntactic advantages your solution
> provided over the Nested Foof Loop forms of collecting lists.
>
> <http://mumble.net/~campbell/scheme/foof-loop.scm>
> <http://mumble.net/~campbell/scheme/foof-loop.txt>
> <http://mumble.net/~campbell/tmp/nested-foof-loop.scm>
> <http://mumble.net/~campbell/tmp/nested-foof-loop.txt>
>
> --
> ``Government is the great fiction through which everybody endeavors to
> live at the expense of everybody else.'' - Frederic Bastiat
There are many looping systems, each with somewhat different features,
and mine has no particular advantage over any others. But mine is
small and simple, providing the essential features, and immediately
portable to any Scheme system.
Phil Bewig
No, but I've seen others. I intended to provide only something simple
and portable, with just the essential features.
Phil Bewig
> > Despite their simplicity, list comprehensions and pattern matching are
> > highly useful forms of syntactic sugar. List comprehensions perform
> > looping computations involving lists. Pattern matching destructures
> > lists, selecting alternatives and binding variables. Together, they
> > enable concise but highly-readable expressions for processing lists.
> > This note describes a simple implementation of list comprehensions and
> > pattern matching.
>
> I'm going to say that I don't see this as particularly useful given the
> existance of Foof Loop by Taylor Campbell. I'd be interested in seeing
> what additional or new features or syntactic advantages your solution
> provided over the Nested Foof Loop forms of collecting lists.
>
> <http://mumble.net/~campbell/scheme/foof-loop.scm>
> <http://mumble.net/~campbell/scheme/foof-loop.txt>
> <http://mumble.net/~campbell/tmp/nested-foof-loop.scm>
> <http://mumble.net/~campbell/tmp/nested-foof-loop.txt>
>
> --
> ``Government is the great fiction through which everybody endeavors to
> live at the expense of everybody else.'' - Frederic Bastiat
I just looked at foof-loop, and recalled that I had seen it before.
Foof, or any other looping system, has a different objective than list-
of. Loops are a general-purpose control-flow mechanism; list
comprehensions provide a syntactic framework to express map and
filter. The two concepts overlap only in a very small way.
Aaron Hsu
> I just looked at foof-loop, and recalled that I had seen it before.
> Foof, or any other looping system, has a different objective than list-
> of. Loops are a general-purpose control-flow mechanism; list
> comprehensions provide a syntactic framework to express map and
> filter. The two concepts overlap only in a very small way.
Did you look at COLLECT-LIST ?
For example, in your first example, I would do the same thing in
nested-foof-loop with:
(collect-list ((for x (in-list '(1 2 3 4 5)))
(let y (* x x)))
(if (odd? x))
(+ y 6))
And to follow your next example:
(collect-list ((for x (up-from 1 (to 6) (by 2)))
(let y (* x x)))
(+ y 6))
Foof-Loop is R5RS portable.
--
Aaron Hsu <arc...@sacrideo.us> | Jabber: arc...@jabber.org
Tzvetan Mikov
> > I'm going to say that I don't see this as particularly useful given the
> > existance of Foof Loop by Taylor Campbell. I'd be interested in seeing
> > what additional or new features or syntactic advantages your solution
> > provided over the Nested Foof Loop forms of collecting lists.
>
> > <http://mumble.net/~campbell/scheme/foof-loop.scm>
> > <http://mumble.net/~campbell/scheme/foof-loop.txt>
> > <http://mumble.net/~campbell/tmp/nested-foof-loop.scm>
> > <http://mumble.net/~campbell/tmp/nested-foof-loop.txt>
>
> and mine has no particular advantage over any others. But mine is
> small and simple, providing the essential features, and immediately
> portable to any Scheme system.
I agree. I took a look at Foof Loop and it is considerably more
complex (the non-nested implementation is 1200 lines without the
dependencies) - certainly not something that one (especially me) can
assimilate at one go. Generally I avoid using syntactic extensions
which I don't understand fully. This is meant in no way as a critique
of Foof Loop and is mostly a reflection of my inexperience.
Your implementation on the other hand is simple, understandable and is
immediately useful. Thanks!
regards,
Tzvetan
Alex Shinn
Phil> There are many looping systems, each with somewhat
Phil> different features, and mine has no particular
Phil> advantage over any others. But mine is small and
Phil> simple, providing the essential features, and
Phil> immediately portable to any Scheme system.
The original loop on which foof-loop was based was also
extremely small and simple (a core of about 100 lines, plus
another 100 or so of iterator definitions). It's also in
fully portable R5RS Scheme (as is foof-loop) and is far more
general than comprehensions.
I intentionally didn't include any comprehension syntax.
Comprehensions are a restricted case of looping, and it
seems to make more sense to start with the general case. If
you also want shorthand notation for comprehensions, they
can then be built on top of the loops, which is what
foof-loop does. This lessens the amount of syntax that
programmers need to learn.
The foof-loop implementation is big because it aims to
provide everything you could ever possibly want, but
everything is built up in layers and optional library
syntax. It's very well documented and commented, fully
tested, and gives intelligible error mesages when you use
the syntax incorrectly.
The original loop is still available as the loopy-loop
Chicken egg, and includes implicit pattern matching with the
portable MATCH
http://synthcode.com/scheme/match.scm
I agree destructuring is useful enough to be made implicit
and is the one missing feature of foof-loop that I'd want.
--
Alex
Phil Bewig
> >>>>> "Phil" == Phil Bewig writes:
>
> Phil> There are many looping systems, each with somewhat
> Phil> different features, and mine has no particular
> Phil> advantage over any others. But mine is small and
> Phil> simple, providing the essential features, and
> Phil> immediately portable to any Scheme system.
>
> provide everything you could ever possibly want, but
> everything is built up in layers and optional library
> syntax. It's very well documented and commented, fully
> tested, and gives intelligible error mesages when you use
> the syntax incorrectly.
As soon as you think you have included everything you could possibly
want, someone will come along and tell you that you must add just one
more little thing. In this very message, you talk about adding
comprehensions and destructuring. I don't want something big, built
up in layer on top of layer, with extensive documentation. I want
something small, that I can easily understand and build, that does
most of what I want quickly and easily.
I don't see any value in arguing about big-vs-small. You have your
preferences, and they shaped your implementation. I have my
preferences, and they shaped my implementation. Neither is
objectively right. And that's fine with me.
Alex Shinn
For clarification, "foof" is my handle, but foof-loop
is not my implementation. My implementation is available
only as the loopy-loop Chicken egg, and I included it
mostly as a proof-of-concept.
You're the one who said you wanted something small.
Big-vs-small is indeed besides the point, though it's
something we Schemers tend to get too hung up on. But
I like to stick by the introduction to R5RS as much as
possible. Comprehensions are a restricted form of
loops, so in the spirit of R5RS it makes sense to
remove the restriction that makes new features appear
necessary.
The idea of foof-loop is very, very general, and you
can add in your own extensions without needing to
change any of the core. The same is not true of your
macro, which needs to be rewritten for every new feature
that someone comes along and asks for.
--
Alex
Phil Bewig
Indeed, I did rewrite list-of to add a new feature. The original list-
of did not have the range operator. Instead, I had a function range
that given first, past and an optional step returned a list.
Sometimes I called that function as an argument to map, or some other
function that takes a list as an argument. Sometimes I called that
function in list-of's in clause. After about a year, I decided that I
used list-of and range often enough in conjunction that I added range
as a new built-in to list-of. So far, I haven't felt limited enough
to have to add any more features. And by the way, I've abandoned most
uses of the original range function in favor of list-of; I don't
recall at the moment the last time I used the range function itself.
phi5...@yahoo.ca
> Despite their simplicity, list comprehensions and pattern matching are
> highly useful forms of syntactic sugar. List comprehensions perform
> looping computations involving lists. Pattern matching destructures
> lists, selecting alternatives and binding variables. Together, they
> enable concise but highly-readable expressions for processing lists.
> This note describes a simple implementation of list comprehensions and
> pattern matching.
>
Hi, Phil.
I wrote a library quite similar to yours. I simplified Egner's list
comprehension library, so I could understand every bit of code. I also
substituted my code for anything I could not run on Bigloo. Finally, I
added a few features of my own. I wonder whether we could work
together to produce a list comprehension library, and a set of
examples for it. Please, take a look at my work at
Download the file list-comprehension.zip I wrote a short tutorial,
with examples ranging from numerical calculations to puzzle solving.
My suggestion is to add your functionality to mine, and work out a few
more examples. Of course, we would need to update the tutorial.
Derick Eddington
Here's my modified list-of which: allows the :range's first, past, and
step to safely be any expression by not having the macro duplicate
those expressions; does (x :range y) which is the same as (x :range 0
y); consolidates the macro's :range cases; prevents a step of 0 (which
would cause infinite loop for decreasing ranges); and is stricter
about the allowed syntax of list-of.
(define-syntax list-of
(syntax-rules ()
[(_ expr clauses ...)
(list-of-aux expr '() clauses ...)]))
(define-syntax list-of-aux
(syntax-rules (:range :in :is)
[(_ expr base)
(cons expr base)]
[(_ expr base (x :range first past step) clauses ...)
(let ([f first] [p past])
(let* ([s (let-syntax ([SM (syntax-rules ()
[(_ #f) (if (< f p) 1 -1)]
[(_ s) s])])
(SM step))]
[more? (cond [(positive? s) <]
[(negative? s) >]
[else (assertion-violation 'list-of
"step must not be zero" s)])])
(let loop ([z f])
(if (more? z p)
(let ([x z])
(list-of-aux expr (loop (+ z s)) clauses ...))
base))))]
[(_ expr base (x :range first past) clauses ...)
(list-of-aux expr base (x :range first past #f) clauses ...)]
[(_ expr base (x :range past) clauses ...)
(list-of-aux expr base (x :range 0 past) clauses ...)]
[(_ expr base (x :in xs) clauses ...)
(let loop ([z xs])
(if (null? z)
base
(let ([x (car z)])
(list-of-aux expr (loop (cdr z)) clauses ...))))]
[(_ expr base (x :is y) clauses ...)
(let ([x y])
(list-of-aux expr base clauses ...))]
[(_ expr base pred clauses ...)
(if pred
(list-of-aux expr base clauses ...)
base)]))
--
: Derick
----------------------------------------------------------------
Derick Eddington
match", which: fixes a bug where checking the fender was forgotten for
the (quote datum) case; fixes a bug where free-identifier=? should be
used instead of bound-identifier=? (otherwise it doesn't properly
detect _ and so binds a new _ in the var case); allows any number of
return values; and matches vectors, with an optimization for the case
where all sub-patterns are identifiers so it doesn't construct a
temporary list (nor nest let forms). There's still an issue with it
allowing duplicate pattern variables which shadow the preceding ones;
I'm going to solve this but I'm not yet sure how much more complicated
it's going to get, let me know if you want what I come up with.
(define-syntax smatch
(syntax-rules ()
[(_ expr (pattern fender ... body) ...)
(let ([obj expr])
(cond [(smatch-aux obj pattern fender ... (let-values ([vs
body]) vs))
=> (lambda (vs) (apply values vs))]
...
[else (assertion-violation 'smatch "failed to match"
obj)]))]))
(define-syntax smatch-aux
(lambda (stx)
(define (underscore? x)
(and (identifier? x) (free-identifier=? x #'_)))
(syntax-case stx (quote quasiquote)
[(_ obj pattern body)
#'(smatch-aux obj pattern #t body)]
[(_ obj () fender body)
#'(and (null? obj) fender body)]
[(_ obj underscore fender body)
(underscore? #'underscore)
#'(and fender body)]
[(_ obj var fender body)
(identifier? #'var)
#'(let ([var obj]) (and fender body))]
[(_ obj (quote datum) fender body)
#'(and (equal? obj (quote datum)) fender body)]
[(_ obj (quasiquote datum) fender body)
#'(and (equal? obj (quasiquote datum)) fender body)]
[(_ obj (pat-car . pat-cdr) fender body)
#'(and (pair? obj)
(let ([obj-car (car obj)] [obj-cdr (cdr obj)])
(smatch-aux obj-car pat-car
(smatch-aux obj-cdr pat-cdr fender body))))]
[(_ obj #(pat* ...) fender body)
#`(and (vector? obj)
(= (vector-length obj) #,(length #'(pat* ...)))
#,(if (for-all identifier? #'(pat* ...))
(with-syntax ([(idx* ...) (enumerate
#'(pat* ...))])
#'(let ([pat* (vector-ref obj idx*)] ...)
(and fender body)))
#'(let ([l (vector->list obj)])
(smatch-aux l (pat* ...) fender body))))]
[(_ obj const fender body)
#'(and (equal? obj const) fender body)])))
* (list-of x (x :range (length #'(pat* ...))))) could be used instead
of (enumerate #'(pat* ...))
--
: Derick
----------------------------------------------------------------