Views: Pattern-matching for Abstract Types
Version 2.1, August 2008
Richard Cobbe <cobbe at ccs dot neu dot edu>
This module defines two forms that allow you to construct pattern-matching views on arbitrary data structures, including abstract data structures.
These views are inspired by Phil Wadler’s notion of views (as published in POPL 1987), but they are somewhat simpler. Unlike Wadler’s original proposal, these forms do not build new constructors for the data types, so we do not have to establish an isomorphism between a view and its underlying data type.
1 Overview
To understand the idea of a view, consider the following structure definitions, which model an abstract syntax tree for the untyped lambda calculus:
(define-struct term ()) |
(define-struct (var term) (name)) |
(define-struct (lam term) (arg body)) |
(define-struct (app term) (rator rand)) |
One can define the following views on lambda terms:
(define-view var-view var? (var-name)) |
(define-view lam-view lam? (lam-arg lam-body)) |
(define-view app-view app? (app-rator app-rand)) |
With these definitions, the expression
(match t |
[(var-view n) ....] |
[(lam-view arg body) ....] |
[(app-view op arg) ....]) |
has the same semantics as
(match t |
[(struct var (n)) ....] |
[(struct lam (arg body)) ....] |
[(struct app (op arg)) ....]) |
Views are useful when programmers cannot use the built-in pattern constructors, either because the representation of the value is not visible, or because they are not interested in every property of the representation and do not want to have to write underscore patterns for all of the irrelevant fields.
To allow pattern-matching on values of an abstract data types, the ADT’s author might define views in the ADT’s module and export the views but not the underlying structure definitions. Alternatively, if the ADT author exports the necessary predicates and selectors for the data type’s variants, but not the actual implementation, a client can define views to support pattern matching.
Views are also often helpful when the client wants to ignore irrelevant properties during pattern-matching. Consider our lambda-calculus AST, but with a slight change to the term structure:
(define-struct term (src)) |
; the other three structure definitions are the same |
Now, the term structure (and thus each AST node) contains a src field, which may contain some sort of source-location information for error messages. Pattern-matching clients must now include patterns for the source location field, even in contexts where this information is irrelevant. As a result, clients have to include underscore patterns in most pattern-matching decompositions of ASTs. But by using the views above, which work unmodified on the new structure layout, clients can pattern-match on AST nodes without patterns for the source location, as the views “skip over” this field. Should they need the source location, it is available through the term-src selector.
2 Definitions
(define-view view-id predicate-expr (selector-expr ....)) |
Defines a new pattern (view-id pat ....) for use with match. The pattern expects one sub-pattern for each selector sub-form.
A value v matches this pattern if (predicate-expr v) is not #f, and if the value of (selector-expr v) matches the corresponding sub-pattern for each selector.
The predicate-expr and selector-expr sub-forms are each evaluated exactly once, when the define-view form is evaluated. The relative order of evaluation of these sub-forms, however, is unspecified.
The predicate-expr sub-form must evaluate to a function that can accept a single argument of any type and that returns a single value. The match form may apply this function multiple times, so be careful with side effects, especially continuations.
Each selector-expr sub-form must evaluate to a function that can accept a single argument and returns a single value. These functions may assume that their argument satisfies the view’s predicate. As with the predicate, match may apply the selectors multiple times and in unexpected orders.
The selectors are not otherwise constrained; in particular, they do not have to be define-struct selectors:
(define positive-natural? (lambda (x) (and (integer? x) (> x 0)))) |
(define natural-zero? (lambda (x) (and (integer? x) (zero? x)))) |
|
(define-view peano-zero natural-zero? ()) |
(define-view peano-succ positive-natural? (sub1)) |
|
(define factorial |
[(peano-zero) 1] |
(view predicate-expr ((selector-expr pattern) ....)) |
An “anonymous view” pattern. Writing
(match expr |
[(view pred? ((sel1 pat1) (sel2 pat2))) ....] |
....) |
is (mostly) equivalent to writing
(define-view fresh-view-id pred? (sel1 sel2)) |
(match expr |
[(fresh-view-id pat1 pat2) ....] |
....) |
where fresh-view-id is an identifier that does not appear within the containing lexical scope.
That is, a value v matches an anonymous view if (predicate-expr v) is not #f, and if (selector-expr v) matches the corresponding pattern, for each selector.
As with define-view, the predicate and selectors must evaluate to functions that can accept one argument and return exactly one value. Unlike define-view, however, the view form may evaluate the predicate-expr and selector-expr sub-forms multiple times per evaluation of the containing match form. The match library may apply the resulting functions multiple times, as with define-view.
3 License
Views: pattern-matching views for abstract data types.
Copyright (C) 2006-2008 Richard Cobbe
This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Clarification: I, Richard Cobbe, consider that simply using this library as a client, by specifying its PLaneT module path in a require clause, is "mere aggregation" according to the terms of the GNU LGPL, and therefore this usage does not constrain the terms of the license under which you release your client program.