Views

_Views_
_views_
_views.plt_

Version 1.0
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: These views will only work with plt-match.ss and not with match.ss
because of a limitation in match.ss's pattern language.  Also, in older
versions of MzLib, a bug in plt-match.ss prevented these views from working
if they were defined and used in different modules.  This should be fixed
for versions 350 and later.

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

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

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 argument and
each selector argument must evaluate to a function that can accept a single
argument and returns a single value; the predicate's result is interpreted
as a boolean.

> (view predicate ((selector pattern) ...))  :  SYNTAX

This macro allows one to define an "anonymous view."  Writing

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

is equivalent to writing

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

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.

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

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.