Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

..
Failed to load latest commit information.
Makefile
README.html
README.org
expand-match-syntax.em
expand-match.em
smatch-smatch0.em
smatch.em
smatch0.em
test-smatch-syntax.em
test-smatch.em

README.org

EuLisp Smatch module

#

Copyright

Youtoo is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

Youtoo 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 General Public License for more details.

You should have received a copy of the GNU General Public License along with Youtoo in the file COPYING. If not, see http://www.gnu.org/licenses/.

EuLisp index

General Description

Programmable pattern matcher based on smatch.em – portable hygienic pattern matcher written by Alex Shinn, extended by Stefan Israelsson Tampe and converted to EuLisp by Stefan Israelsson Tampe. This is a full super-set of the popular match package by Andrew Wright by written in itself and hence requires bootstrapping.

This is a simple generative pattern matcher - each pattern is expanded into the required tests, calling a failure continuation if the tests fail. This makes the logic easy to follow and extend, but produces sub-optimal code in cases where you have many similar clauses due to repeating the same tests. Nonetheless a smart compiler should be able to remove the redundant tests. For match-let and destructuring-bind type uses there is no performance hit.

Original: Portable hygienic pattern matcher

The original version was written on 2006/11/29 and described in the following Usenet post: http://groups.google.com/group/comp.lang.scheme/msg/0941234de7112ffd and is still available at http://synthcode.com/scheme/match-simple.scm. It’s just 80 lines for the core MATCH, and an extra 40 lines for match-let, match-lambda and other syntactic sugar.

A variant of this file which uses cond-expand in a few places for performance can be found at http://synthcode.com/scheme/match-cond-expand.scm.

Definition

The complete syntax of the pattern matching expressions follows:

match expressions:
exp ::= ...
      | (match exp clause ...)
      | (match-lambda clause ...)
      | (match-lambda* clause ...)
      | (match-let ((pat exp) ...) body)
      | (match-let* ((pat exp) ...) body)
      | (match-letfuns ((pat exp) ...) body)
      | (defmatchfun pat exp)

clause ::= (pat body) | (pat => exp)

The match-lambda and match-lambda* forms are convenient combinations of match and lambda, and can be explained as follows:

(match-lambda (pat body) ...)   =  (lambda (x) (match x (pat body) ...))

(match-lambda* (pat body) ...)  =  (lambda x (match x (pat body) ...))

where x is a unique variable. The match-lambda form is convenient when defining a single argument function that immediately destructures its argument. The match-lambda* form constructs a function that accepts any number of arguments; the patterns of match-lambda* should be lists. The match-let, match-let*, match-letfuns, and defmatchun forms generalize EuLisp’s let, let*, letfuns, and defun expressions to allow patterns in the binding position rather than just variables. For example, the following expression:

(match-let (((x y z) (list 1 2 3))) $body$)

binds x to 1, y to 2, and z to 3 in body. These forms are convenient for destructuring the result of a function that returns multiple values. As usual for letfuns and defun, pattern variables bound by match-letfuns and defmatchun should not be used in computing the bound value. The match, match-lambda, and match-lambda* forms allow the optional syntax (=> identifier) between the pattern and the body of a clause. When the pattern match for such a clause succeeds, the identifier is bound to a failure procedure of zero arguments within the body. If this procedure is invoked, it jumps back to the pattern matching expression, and resumes the matching process as if the pattern had failed to match. The body must not mutate the object being matched, otherwise unpredictable behavior may result.

Patterns

patterns:                               matches:

pat ::= identifier                      anything, and binds identifier
      | _                               anything
      | ()                              the empty list
      | t                               t
      | string                          a string
      | number                          a number
      | character                       a character
      | 'sexp                           an s-expression
      | 'symbol                         a symbol (special case of s-expr)
      | (pat_1 ... pat_n)               list of n elements
      | (pat_1 ... pat_n . pat_{n+1})   list of n or more
      | (pat_1 ... pat_n pat_n+1 ooo)   list of n or more, each element
                                        of remainder must match pat_n+1
      | #(pat_1 ... pat_n)              vector of n elements
      | #(pat_1 ... pat_n pat_n+1 ooo)  vector of n or more, each element
                                        of remainder must match pat_n+1
      | ($ class-name pat_1 ... pat_n)  a class
      | (= field pat)                   a field of a class
      | (and pat_1 ... pat_n)           if all of pat_1 thru pat_n match
      | (or pat_1 ... pat_n)            if any of pat_1 thru pat_n match
      | (not pat_1 ... pat_n)           if all pat_1 thru pat_n don't match
      | (? predicate pat_1 ... pat_n)   if predicate true and all of
                                        pat_1 thru pat_n match
      | (set identifier)                anything, and binds setter
      | (get identifier)                anything, and binds getter
      | `qp                             a quasi-pattern

ooo ::= ...                             zero or more
      | ___                             zero or more
      | (.. k)                          k or more
      | (__ k)                          k or more

quasi-patterns:                         matches:
qp  ::= ()                              the empty list
      | t                               t
      | ()                              ()
      | string                          a string
      | number                          a number
      | character                       a character
      | identifier                      a symbol
      | (qp_1 ... qp_n)                 list of n elements
      | (qp_1 ... qp_n . qp_{n+1})      list of n or more
      | (qp_1 ... qp_n qp_n+1 ooo)      list of n or more, each element
                                        of remainder must match qp_n+1
      | #(qp_1 ... qp_n)                vector of n elements
      | #(qp_1 ... qp_n qp_n+1 ooo)     vector of n or more, each element
                                        of remainder must match qp_n+1
      | ,pat                            a pattern
      | ,@pat                           a pattern

The names (quote, quasiquote, unquote, unquote-splicing, ?, _, $, and, or, not, set, get, ..., ___) cannot be used as pattern variables.

identifier

(excluding the reserved names ?, $, _, and, or, not, set, get, ..., and (.. k ) for non-negative integers k): matches anything, and binds a variable of this name to the matching value in the body.

_

matches anything, without binding any variables.

(), t, string, number, character, ​’s-expression

These constant patterns match themselves, ie., the corresponding value must be equal? to the pattern.

( pat1 … patn )

matches a proper list of n elements that match pat1 through patn.

( pat1 … patn . patn+1 )

matches a (possibly improper) list of at least n elements that ends in something matching patn+1.

( pat1 … patn patn+1 )

matches a proper list of n or more elements, where each element of the tail matches patn+1. Each pattern variable in patn+1 is bound to a list of the matching values. For example, the expression:

(match '(let ((x 1)(y 2)) z)
  (('let ((binding values) ...)  exp) body))

binds binding to the list ​'(x y), values to the list ​'(1 2), and exp to ‘z in the body of the match- expression. For the special case where patn+1 is a pattern variable, the list bound to that variable may share with the matched value.

( pat1 … patn patn+1 (.. k ))

This pattern is similar to the previous pattern, but the tail must be at least k elements long. The pattern keywords (.. 0) and =... are equivalent.

#( pat1 … patn )

matches a vector of length n, whose elements match pat1 through patn.

($ class pat1 … patn )

matches a class declared with defclass.

(and pat1 … patn )

matches if all of the sub-patterns match. This pattern is often used as (and x pat ) to bind x to the entire value that matches pat (cf. “as-patterns” in ML or Haskell).

(or pat1 … patn )

matches if any of the sub-patterns match. At least one subpattern must be present. All sub-patterns must bind the same set of pattern variables.

(not pat1 … patn )

matches if none of the sub-patterns match. The sub-patterns may not bind any pattern variables.

(? predicate pat1 … patn )

In this pattern, predicate must be an expression evaluating to a single argument function. This pattern matches if predicate applied to the corresponding value is true, and the sub-patterns pat1 … patn all match. The predicate should not have side effects, as the code generated by the pattern matcher may invoke predicates repeatedly in any order. The predicate expression is bound in the same scope as the match expression, i.e., free variables in predicate are not bound by pattern variables.

(set identifier )

matches anything, and binds identifier to a procedure of one argument that mutates the corresponding field of the matching value. This pattern must be nested within a pair, vector or class pattern. For example, the expression:

(define x (list 1 (list 2 3)))
(match x ((_ (_ (set setit))) (setit 4)))

mutates the cadadr of x to 4, so that x is ​'(1 (2 4)).

(get identifier )

matches anything, and binds identifier to a procedure of zero arguments that accesses the corresponding field of the matching value. This pattern is the complement to set. As with set, this pattern must be nested within a pair, vector, or class pattern.

Quasipatterns

Quasiquote introduces a quasipattern, in which identifiers are considered to be symbolic constants. Like Scheme’s quasiquote for data, unquote (=,=) and unquote-splicing (=,@=) escape back to normal patterns.

Match Failure

  • Complete support of classes
  • Complete set of tests

Installation

  • Run ‘make’ in directory Modules/Smatch.
  • Run ‘make test’ in directory Modules/Smatch.
Something went wrong with that request. Please try again.