Views

_Views_
_views_
_views.plt_

Version 1.1
Richard Cobbe
<cobbe at ccs dot neu dot edu>

This collection 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 datatype.

NOTE: In older versions of MzLib, a bug in the match library prevented
these views from working if they were defined and used in different
modules.  This should be fixed for versions 350 and later.

Version 1.0 of this library supported only plt-match.ss; this version now
supports match.ss as well.

======================================================================

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 plt-match.ss (struct ...) and match.ss
($ ...) patterns do, 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 datatype to pattern-match on
values of that type without having to know the underlying representation of
the type.  In the example above, the structure definitions could be in a
module that does not export their 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.  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, the client can define the view, so long as the AST
author has provided the necessary predicate and selectors.

Second, views are often helpful in order to ignore certain common fields
that are often irrelevant.  Consider a program that uses the AST defined
above, but with a slight change:

    (define-struct term (src))
    ;; other structure definitions as before.

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 will then have to include patterns for the source
information; in my experience these patterns are often _.  The views above,
however, "skip over" the src field, allowing clients to pattern-match on
AST nodes without specifying patterns for the source location.  If they
need the source location, it is available through the term-src selector.

======================================================================

> (define-view view-name predicate (selector ...))  :  SYNTAX

The define-view macro defines a new pattern (view-name pat ...) for use
with plt-match.ss.  This pattern expects one sub-pattern for each selector
in the view definition.

A value v matches this pattern if (predicate v) is not #f, and if
(selector v) matches the corresponding sub-pattern for each selector.

The view-name argument must be an identifier.

The predicate and selector arguments 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 form must evaluate to a function that can accept a single
argument and returns a single value.  This function should not have any
side effects when it is applied, as the matching library may apply it
multiple times.  (You're on your own if the predicate stores or invokes a
continuation.)

Each selector form must evaluate to a function that can accept a single
argument (which satisfies the view's predicate) and returns a single value.
As with the predicate, the selector functions should not have any side
effects during application, as the matching library may apply these
multiple times and in unexpected orders.

The selectors are not otherwise constrained; in particular, they do not
have to be structure 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 ((selector pattern) ...))  :  MATCH-EXPANDER

This match expander allows one to specify an "anonymous view."  Writing

    (match expr
      [(view pred? ((sel1 pat1) (sel2 pat2))) ...]
      ...)

is (mostly) equivalent to writing

    (define-view fresh-view-name pred? (sel1 sel2 ...))
    (match expr
      [(fresh-view-name pat1 pat2 ...) ...]
      ...)

where fresh-view-name is an identifier that does not appear within that
lexical scope.

That is, a value v matches an anonymous view if (predicate v) is not #f,
and if (selector v) matches the associated 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 the
define-view form, however, the view form may evaluate the predicate and
selector subforms multiple times.  The match library may apply the
resulting functions multiple times, as with define-view.

======================================================================

Views: pattern-matching views for abstract data types.
Copyright (C) 2006  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 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.