#lang scribble/doc @(require scribble/manual (for-label scheme/match) (for-label scheme/base) (for-label (planet cobbe/views:2/views))) @title{@bold{Views}: Pattern-matching for Abstract Types} Version 2.1, August 2008 Richard Cobbe @defmodule[(planet cobbe/views:2/views)] This module defines two forms that allow you to construct pattern-matching @deftech{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. @section{Overview} To understand the idea of a view, consider the following structure definitions, which model an abstract syntax tree for the untyped lambda calculus: @elemtag[(list 'tag "ast-defn")]{} @schemeblock[ (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: @elemtag[(list 'tag "ast-views")]{} @schemeblock[ (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 @schemeblock[ (match t [(var-view n) ....] [(lam-view arg body) ....] [(app-view op arg) ....]) ] has the same semantics as @schemeblock[ (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 @elemref[(list 'tag "ast-defn")]{our lambda-calculus AST}, but with a slight change to the @scheme[term] structure: @schemeblock[(define-struct term (src)) (code:comment #, @t{the other three structure definitions are the same})] Now, the @scheme[term] structure (and thus each AST node) contains a @scheme[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 @elemref[(list 'tag "ast-views")]{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 @scheme[term-src] selector. @section{Definitions} @defform[(define-view view-id predicate-expr (selector-expr ....))]{ Defines a new pattern @scheme[(view-id pat ....)] for use with @scheme[match]. The pattern expects one sub-pattern for each selector sub-form. A value @scheme[v] matches this pattern if @scheme[(predicate-expr v)] is not @scheme[#f], and if the value of @scheme[(selector-expr v)] matches the corresponding sub-pattern for each selector. The @scheme[predicate-expr] and @scheme[selector-expr] sub-forms are each evaluated exactly once, when the @scheme[define-view] form is evaluated. The relative order of evaluation of these sub-forms, however, is unspecified. The @scheme[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 @scheme[match] form may apply this function multiple times, so be careful with side effects, especially continuations. Each @scheme[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, @scheme[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 @scheme[define-struct] selectors: @schemeblock[ (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 (match-lambda [(peano-zero) 1] [(and (peano-succ pred) n) (* n (factorial pred))])) ]} @defform[(view predicate-expr ((selector-expr pattern) ....))]{ An ``anonymous view'' pattern. Writing @schemeblock[ (match expr [(view pred? ((sel1 pat1) (sel2 pat2))) ....] ....) ] is (mostly) equivalent to writing @schemeblock[ (define-view fresh-view-id pred? (sel1 sel2)) (match expr [(fresh-view-id pat1 pat2) ....] ....) ] where @scheme[fresh-view-id] is an identifier that does not appear within the containing lexical scope. That is, a value @scheme[v] matches an anonymous view if @scheme[(predicate-expr v)] is not @scheme[#f], and if @scheme[(selector-expr v)] matches the corresponding pattern, for each selector. As with @scheme[define-view], the predicate and selectors must evaluate to functions that can accept one argument and return exactly one value. Unlike @scheme[define-view], however, the @scheme[view] form may evaluate the @scheme[predicate-expr] and @scheme[selector-expr] sub-forms multiple times per evaluation of the containing @scheme[match] form. The @scheme[match] library may apply the resulting functions multiple times, as with @scheme[define-view].} @section{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.