Extensible Macros and define-library

Extensible Macros and define-library

[J. Vincent Toups]

I'm seeking ideas on how to implement an extensible pattern matcher.

You can see the code as it currently is here:

https://github.com/VincentToups/kawa-lib/blob/main/lib/shadchen.scm

Usage look like this

(define (example arg)
 (match arg
  ((string? x) x)
  ((number? x) x)
  ((list a b c) (list c b a))
  (anything-else (error "Fail"))))

(example 10) -> 10
(example '(1 2 3)) -> (3 2 1)

When matching against a pattern which is a list, the matcher uses the
head of the list to determine what behavior to implement. The list
head is interpreted as being in its own namespace (the pattern
namespace, if you'd like). If you examine the source code you can see
that we dispatch presently on the symbolic value of the head rather
than its syntax. The "pattern namespace" is totally static and flat.

I'm trying to figure out how to let users extend this pattern matcher.
A user defined pattern is naturally thought of as a special kind of
syntax-transformer. It takes some syntax in and returns a new pattern
using primitive patterns as an implementation language.

eg:

(define-pattern list-of-two
 (lambda (expr)
  (syntax-case expr ()
   ((_ a b) #'(list a b)))))

How can I set this system up so that

1. patterns can be exported/imported/etc using define-library
2. they are neither regular functions nor syntax-transformers
    a. they don't have run time values
    b. they also aren't interpreted as regular syntax-transformers?

I'm not sure such a thing can be defined in pure R7RS/R6RS scheme?

I _think_ the essence of this question is whether there is any clever
way to set up a separate namespace that I can interact with at
syntax-transformation time. I think I could hack something together if
there was a way to do a macro-expand-once but in that case I think I'd
still have to define patterns as regular syntax-transformations. And
it doesn't seem like there is such a thing as "expand-once" in
R(6,7)RS or in Kawa.

A cute use of such a thing would be to implement something like
scala's "unapply" idiom where a specific static method of a class
describes how to perform a pattern match for instances.

Any advice would be appreciated!

Re: Extensible Macros and define-library

[Per Bothner]

Sorry for the late response - I missed your message.

On 4/17/21 3:32 AM, J. Vincent Toups via Kawa wrote:
> I'm seeking ideas on how to implement an extensible pattern matcher.

If you want to define your own pattern-matching library, you can of course do what.
Likewise, if you're trying to implement a library following some other existing API.
However, if you want pattern-matching to be part of Kawa itself and available
as part of the Kawa "standard library" then note that Kawa has its own pattern
"language" and "vision".  If you're not already familar with it, check out
http://www.gnu.org/software/kawa/Variables-and-Patterns.html
Understand that the (let ...) family and lambda formal parameters have been extended to
take patterns: http://www.gnu.org/software/kawa/Extended-formals.html
Note the (! patterm value) syntax is an extension of plain define.
Note how if-expressions and cond have been extended to be pattern-aware,
using the (? pattern value) form: www.gnu.org/software/kawa/Conditionals.html .

Now the Kawa pattern "syntax" is rather limited.  My goal was to integrate
patterns into the language, so I stuck to pattern forms that wouldn't constrain
extending the pattern language.  Unfortunately, syntax-rules is based on
pattern-match using an elegant but limited syntax - which is incompatible
with most other designs: In syntax-rules the pattern (list x y z) matches
a *four*-element list, binding the name 'list to the first element of the list.
I.e. the first element of a list in a syntax-rules pattern is not a
pattern operator, but instead matches just like the remaining elements.

Now if we *do* want to allow "pattern operators", breaking with syntax-rules compatibility
(and I think we do) then it would be desirable to allow for some kind of extensibility,
as you're talking about.

If you want to extend or hook into the Kawa pattern framework, the place where
lists are handled is starting near line 143 in kawa/lang/BindDecls.java.
Specifically, search for the error message "unrecognized pattern operator "
and erplace that to search for a defined pattern operator.
Unfortunately, the code is rather convoluted.

The hard part is defining a Scheme API that can hook into the BindDecls class.
Specifically, what kind of transformer is it: What are the inputs (patterns,
presumably) and what are the outputs (declarations/bindings, initialized from
the match form) in a clean way that can be mapped to Kawa internals.

How to deal with namespaces and hygiene can probably best be done with
compound names: www.gnu.org/software/kawa/Symbols-and-namespaces.html
For example when the compiler sees a pattern (OP arg1 arg2 args3)
it could look for a transfomer with the name $PATTERN-BIND$:OP
- i.e. the symbol 'OP in the '$PATTERN-BIND$ namespace.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/