Views: Pattern-matching for Abstract Types

Version 2.0

Richard Cobbe

<cobbe at ccs dot neu dot edu>

(require (planet cobbe/views:2/views))

This package provides one file, "views.ss". This file defines two macros that allow you to construct pattern-matching views on arbitrary data structures, including abstract data structures.

These macros 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 macros 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))

Thereafter, one may use these views in match expressions:

(match t

[(var-view n) ....]

[(lam-view arg body) ....]

[(app-view op arg) ....])

So far, views, do just what the scheme/match (struct ....) pattern does, although with slightly less typing. In certain situations, though, views have significant benefits over the built-in patterns.

First, views allow clients of an abstract data type to pattern-match on values of that type without having to know its underlying representation. For example, the AST structure definitions could be in a module that does not export the predicates or selectors. Alternatively, the ASTs could be represented as a true abstract data type (that is, not a struct, but some opaque type that comes with selector functions). In either case, clients of the AST type cannot pattern-match on values of that type directly. If, however, the AST author provides views that are defined in terms of the private representation and exports those views, clients may pattern-match against these values without knowing any details of their type. Alternatively, if the AST author provides the necessary predicates and selectors, the client can define the views.

Second, views are often helpful in order to ignore certain common fields that are often irrelevant. Consider a program that uses our lambda-calculus AST, but with a slight change to the term structure:

  (define-struct term (src))

The other three structures are unchanged.

Now, the term structure (and thus each AST node) contains a src field, which may contain some sort of source-location info for error messages. Pattern-matching clients must now include patterns for the source information. In most cases, though, this information is irrelevant, so the programmer has to sprinkle underscore patterns throughout the pattern-matching code. The views above, however, “skip over” the src field, allowing clients to pattern-match on AST nodes without specifying patterns for the source location. 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. (You’re on your own if the predicate stores or invokes a continuation.)

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 natural-number?

(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 natural-number? (sub1))

(define factorial

(match-lambda

[(peano-zero) 1]

[(and (peano-succ pred) n) (* n (factorial pred))]))

(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. 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.