Hacker News new | ask | show | jobs
by kazinator 1850 days ago
TXR Lisp:

  1> (defun rewrite (fun list)
      (build
        (while* list
          (let ((nlist [fun list]))
            (if (eq list nlist)
              (if list (add (pop list)))
              (set list nlist))))))
  rewrite
  2> (defmacro rewrite-case (sym list . cases)
      ^(rewrite (lambda (,sym)
                  (match-case ,sym
                    ,*cases))
                ,list))
  rewrite-case
  3> (rewrite-case x '(foo bar * select * fox select * bravo)
       ((select * . @rest) ^(select _ . ,rest))
       (@else else))
   (foo bar * select _ fox select _ bravo)
rewrite-case and rewrite appear in the TXR Lisp internals; they are used in the compiler for scanning instruction sequences for patterns and rewriting them.

E.g. a function early-peephole looks for one particular four instruction pattern (six items, when the labels are included). Rewriting it to a different form helps it disappear later on.

  (defun early-peephole (code)
    (rewrite-case insns code
      (((mov (t @t1) (d @d1))
        (jmp @lab2)
        @(symbolp @lab1)
        (mov (t @t1) (t 0))
        @lab2
        (ifq (t @t1) (t 0) @lab3)
        . @rest)
      ^((mov (t ,t1) (d ,d1))
        (jmp ,lab3)
        ,lab1
        (mov (t ,t1) (t 0))
        ,lab2
        ,*rest))
      (@else else)))
This is much more general and powerful than a hack which just looks at successive pairs for an ad-hoc match. rewrite-case can have multiple clauses, of different lengths, and arbitrary matching complexity.
1 comments
kazinator 1850 days ago
The original requirements should be addressed. The thing being matched is not just select, but actually any one of a set of symbols that appear in K.

We can stick that data into the pattern matching syntax using the or operator:

  3> (rewrite-case x '(foo bar * select * fox where * bravo)
       ((@(or select distinct partition from where
              group having order limit) * . @rest) ^(,(car x) _ . ,rest))
       (@else else))
  (foo bar * select _ fox where _ bravo)
Or put it into a variable:

  4> (defvarl K '(select distinct partition from where group having order limit))
  K
  5> (rewrite-case x '(foo bar * select * fox where * bravo)
       ((@(member @sym K) * . @rest) ^(,sym _ . ,rest))
       (@else else))
  (foo bar * select _ fox where _ bravo)
"If an object sym which is a member of K is followed by * and some remaining material, replace that by sym, underscore and that remaining material."

Hash table:

  6> (set K (hash-list '(select distinct partition from where group having order limit)))
  #H(() (select select) (where where) (limit limit) (order order)
     (having having) (distinct distinct) (partition partition) (group group)
     (from from))
  7> (rewrite-case x '(foo bar * select * fox where * bravo)
       ((@[K @sym] * . @rest) ^(,sym _ . ,rest))
       (@else else))
  (foo bar * select _ fox where _ bravo)
This code golfs moderately well: https://news.ycombinator.com/item?id=27227276
link