Case Study: the Matcher

The paper’s §3 develops a small regular-expression matcher and stages it. lib/matcher.naj is the port, close to verbatim. It is the first program in this book written for stage polymorphism: one source that is a matcher when interpreted and a matcher generator when compiled.

The source

A regex here is a list of symbols: literals match themselves, _ matches anything, * (postfix) repeats the preceding element, and done ends both regexes and input strings. The matcher is three functions — star_loop, match_here, match — with a free variable maybe-lift wrapped around every created value, in the same positions the Pink evaluator’s handlers use it. The last of the three:

(let match (lambda match r
  (if (eq? 'done (car r))
      (maybe-lift (lambda _ s (maybe-lift 'yes)))
      (maybe-lift (match_here r))))
match)

maybe-lift is free in the source, so matcher-src is not a closed program. The library closes it by splicing text, not by passing a value — matcher takes the source of a maybe-lift and builds a new program around the matcher source:

(define matcher (lambda _ ml `(let maybe-lift ,ml ,matcher-src)))

Interpreting it

With identity as maybe-lift, the closed program is an ordinary matcher. The stages of use: matcher picks the reading, interpret evaluates the program, the result takes a regex, and that takes a string.

(load lib/matcher.naj)
(define m ((interpret (matcher '(lambda _ e e))) nil-env))
((m '(_ * a _ * done)) '(b a done))
;=> 'yes
((m '(_ * a _ * done)) '(b b done))
;=> 'no

The regex (_ * a _ * done) — anything, then an a, then anything — matches (b a done) and rejects (b b done). One m serves every regex; each call to (m r) walks the regex and the string together, interpreting r as it goes.

Compiling it

With (lambda _ e (lift e)) as maybe-lift, applying the matcher to a regex generates a program: the regex walk happens at generation time, and what residualizes is a matcher specialized to that one regex, with the regex constants folded in and no regex left to consult. Per the last chapter’s discipline, the specialization runs inside the run scope (the boot preamble is the one from the Stage Polymorphism chapter):

(let pink-poly-src (car (read-file 'lib/pink-forms.naj))
(let pink-tie-src `(let pink-poly ,pink-poly-src
                     (lambda eval l (lambda _ e (((pink-poly eval) l) e))))
(let pink-tie (evalms nil (trans pink-tie-src nil))
(let pink-eval (pink-tie (cons (lambda _ e e) 0))
(let msrc (cadr (caddr (car (read-file 'lib/matcher.naj))))
(let prog `(let maybe-lift (lambda _ e (lift e)) ,msrc)
(let nil-env (lambda _ y 0)
  (((pink-eval prog) nil-env) '(_ * a _ * done)))))))))
;=> #<code 101 nodes>

A hundred and one nodes for a six-element regex: the two starred elements each became their own residual loop — star_loop unrolled once per star — and the literal comparisons specialized to their symbols. The compiled matcher accepts and rejects the same strings:

(let pink-poly-src (car (read-file 'lib/pink-forms.naj))
(let pink-tie-src `(let pink-poly ,pink-poly-src
                     (lambda eval l (lambda _ e (((pink-poly eval) l) e))))
(let pink-tie (evalms nil (trans pink-tie-src nil))
(let pink-eval (pink-tie (cons (lambda _ e e) 0))
(let msrc (cadr (caddr (car (read-file 'lib/matcher.naj))))
(let prog `(let maybe-lift (lambda _ e (lift e)) ,msrc)
(let nil-env (lambda _ y 0)
(let cm (run 0 (((pink-eval prog) nil-env) '(_ * a _ * done)))
  (cons (cm '(b a done)) (cm '(b b done)))))))))))
;=> ('yes . 'no)

(The two applications share one floor form because floor forms are closed; the pair packages both answers.)

What the case study shows

The evaluator of the previous chapters needed no changes to compile the matcher, and the matcher needed no compiler — only the maybe-lift calls, placed where values are created. That placement is the entire “staging annotation” burden, and it is inherited unchanged from the paper’s matcher.scm. The reference implementation goes one step further and builds a tracing matcher by running the same source under a delta-eval extension (the mechanism from the metacircular chapter) — instrumentation as an interpreter modification, orthogonal to both the matcher and the staging.