Arc Forumnew | comments | leaders | submitlogin
A pattern-matching library (at Lathe)
1 point by rocketnia 3461 days ago | discuss
Yesterday fallintothis mentioned[1] it would be nice to have a pattern-matching library that did something like this:

  ; returns var.1.1 if var is of the form (global 'inner-var)
  (when-match (global (quote ?inner-var)) var
    ?inner-var)
There's already almkglor's p-m macro[2], but I suffer from not-invented-here syndrome, and I wanted this to be capable of supporting backtracking (like regexes do) and extensions (so that I could theoretically add regex syntax as a library :-p ).

In the past I've built a Groovy library that does regexes something like this, and it wasn't hard to do it again. So in Lathe[3] is a pattern-matching library[4] that's used like so:

  arc> (use-rels-as pm (+ lathe-dir* "patmac.arc"))
  #(tagged mac #<procedure: nspace-indirect>)
  arc>
    (pm:when-match `(global ',inner-var) '(global 'foo)
      inner-var)
  foo
It's based on a pattern DSL that compiles down to a pattern (a generator that takes the pattern's subject and yields tables with the matched bindings) and a list of variables to be bound.

A non-nil, non-ssyntax symbol compiles to a pattern that binds just that symbol (and always succeeds with a single match):

  arc> (pm.patcompile 'inner-var)
  ((inner-var) (fn (_) (gs2328-iterify (list:obj inner-var _))))
A (quasiquote ...) form compiles to something quite a bit more complicated:

  arc> (pm.patcompile '`(global ',inner-var))
  ((inner-var) [snip: a long expression implementing the destructuring])
Unrecognized forms, including all ssyntax, compile to themselves, so that if you have a pattern function handy you can use it:

  arc> (pm.patcompile 'do.foo)
  (nil do.foo)
  arc> (pm.patcompile '(not-special a b c))
  (nil (not-special a b c))
Note that those patterns won't bind any variables for the purposes of things like 'when-match. You can override that with a (binding ...) form:

  arc> (pm.patcompile '(binding do.foo bar baz))
  ((bar baz) do.foo)
For the moment, literals compile to themselves too, which probably isn't useful at all since they're not functions:

  arc> (pm.patcompile 1)
  (nil 1)
For now, you can make do with putting literals into a (quote ...) form, which matches things based on 'iso so that it works with lists:

  arc> (pm.patcompile ''1)
  (nil (fn (_) (gs2328-iterify (when (iso _ (quote 1)) (list:table)))))
  arc> (pm.patcompile ''(1 2 3))
  (nil (fn (_) (gs2328-iterify (when (iso _ (quote (1 2 3))) (list:table
  )))))
None of these forms use backtracking. Just to explore that potential, patmac.arc defines two other pattern forms:

- (or ...), which tries each of its inner patterns in sequence

- (atomic ...), which performs the inner pattern but without any backtracking, like a regex atomic group

Defining a new pattern form can be very similar to defining a macro; the pattern compiler recognizes any globally defined functions tagged with 'patmac. Lathe globally defines (mc ...) and (=mc ...) shortcuts for creating macros, and patmac.arc defines similar forms (patmc ...) and (=patmc ...) for patmacs:

  arc> (use-rels-as ir (+ lathe-dir* "iter.arc"))
  #(tagged mac #<procedure: nspace-indirect>)
  arc>
    (pm:=patmc match123 ()
      (list '(x) `[,ir!iterify (map [obj x _] '(1 2 3))]))
  #(tagged patmac #<procedure: match123>)
  arc>
    (pm:each-match (match123) 'this-is-ignored
      prn.x)
  1
  2
  3
  nil
However, many of the nicest names for patterns are already taken. If you redefine 'quote and 'quasiquote on Jarc, you're in trouble. So there's a global table, 'patmacs, which maps convenient names to full global names, and there's a definition form, 'named-patmac, which adds to 'patmacs at the same time:

  arc> pm.patmacs*
  #hash((binding . gs2009-binding-patmac) (or . gs2009-or-patmac) (quote
   . gs2009-quote-patmac) (quasiquote . gs2009-qq-patmac) (atomic . gs20
  09-atomic-patmac))
  arc>
    (pm:named-patmac match123 m123 ()
      (list '(x) `[,ir!iterify (map [obj x _] '(1 2 3))]))
  #(tagged patmac #<procedure: match123>)
  arc>
    (pm:each-match (m123) 'this-is-ignored
      prn.x)
  1
  2
  3
  nil
  arc> bound!m123
  nil
So... yep. Just letting you know, I guess. ^_^

-

[1]: http://arclanguage.org/item?id=11950

[2]: http://arclanguage.org/item?id=2556

[3]: http://github.com/rocketnia/lathe/

[4]: http://github.com/rocketnia/lathe/blob/5338d9/arc/patmac.arc (for the version current as of this post)