picopass: let's break nanopass down
In the excellent library nanopass, we can define a language via
define-language and make pattern matching on it by using
nanopass-case, the most important thing nanopass given here is the
generated code for these syntaxes. This is extremely useful because
usually, a compiler will have many uninterested paths, especially in
multi-passes solutions, we have to write tons of code to handle them.
However, Do I only get these from nanopass, a framework that cannot
I break the problem into two parts
- a mark to help
- add missing cases that might occur in the domain
2.1. Mark recursion target
First, let's look at the usage
(struct add (l r)) (define (eval-+ e) (record eval-+) (match e [(add (R l) (R r)) (+ l r)] [(? number? v) v])) (eval-+ (add 1 2))
recordrecords the recursion function
Rwill let the pattern be re-applied with the recursion function
This means if we have a pattern
x, it will bind to
The following is the implementation, quite simple actually.
(define-for-syntax recur-on? #f) (define-syntax (record stx) (syntax-parse stx [(_ x:id) (set! recur-on? #'x) #'(void x)])) (define-match-expander R (λ (stx) (syntax-parse stx [(_ v:id) #`(app #,recur-on? v)])))
recordputs it's target id into *phase 1*(compile time)
Rpattern relies on
2.2. Generate missing cases
Here, we need to define what's the domain. For me, it's a set of structures I care about in the current pass. That's why I write the below code.
(define-for-syntax (struct->clause id-stx) (syntax-parse id-stx [s:id (define fields (reverse (struct-field-info-list (syntax-local-value id-stx)))) #`[(s #,@(map (λ (x) `(R ,x)) fields)) (s #,@fields)]])) (define-syntax-parser rmatch [(_ target:expr #:recur on:id #:complete (s:id ...) c* ...) #`(begin (record on) (match target #,@(stx-map struct->clause #'(s ...)) c* ...))])
rmatch redo all we just done, and generates cases from the
structure identifier list given by
#:complete. What we care about here
struct->clause, this function extracts fields from the structure
R pattern for them, then preserves the structure. The
following is how will you use it.
(struct add (l r)) (struct mul (l r)) (define (eval-+ e) (rmatch e #:recur eval-+ #:complete (mul) [(add (R l) (R r)) (+ l r)] [(? number? v) v])) (define (eval-* e) (rmatch e #:recur eval-* #:complete (add) [(mul (R l) (R r)) (* l r)] [(? number? v) v])) ((compose eval-* eval-+) (mul (add 1 2) 3))
This example has trouble of course since it's an evaluate function, breaking it into two functions will make invoke order that must correspond to the given AST structure. However, this also shows how the idea works.
You now get a workable macro
rmatch, which can
- recur on any pass function you like to do so
- handle any structures you don't care yet
What can you do to get more?
(? number? v)pattern should also be generated, extend
#:completepart to get more possible input.
#:completetakes a mark of collection/language. For example,
#:complete λ0generates all possible patterns for language
matching on multiple targets, and still cover all cases (should be a cartesian product now). In type checker, such use cases are quite usual, with this one can write
(rmatch (tm ty) #:recur tyck #:complete (...) [((? number? v) Number) 'ok] ...)
typed/racketto get help from the type checker
- generated pattern should only recur on the interested type, here we
didn't hit the problem, since our target is
eval-+is a function with domain
More ideas? Welcome to show your thought here, have a nice day.