[plt-scheme] New Match Implementation

On Tue> (compile '(let () z)), 1 Apr 2008, Sam THfŸ=y=z at Pž$"W^Áž##" wrote:

> On Tue, Apr 1, 2008 at 3:34 AM, Dimitris Vyzovitis <vyzo at media.mit.edu> wrote:
> >  Did you break the optimizer?
>
> More accurate would be to say that I deleted the optimizer.  The
> algorithm is completely different, and there's no longer a pass over
> the generated code to optimize it.  Unfortunately, that optimizer was
> hopelessly broken.  Fortunately, MzScheme has a decent optimizer that
> should help limit the differences.
...
>
> >  It now (well, rev 9096) extracts useless elements from compounds for _
> >  patterns.
>
> If you time these two examples, I think you'll find no measurable
> difference in performance.  I assume that the useless bindings are
> optimized away.  On this topic, see Kent Dybvig's talk on the
> macro-writers bill of rights, which I believe MzScheme supports all
> of.

Not quite.
You are asking the optimizer to drop an application (in a strict language)
because you don't use the result. This is not something you can do in
general, unless the the application is provably pure (and the compiler is
sufficiently smart to prove it).

This may be possible with primitives like car/cdr (but it is *not*
done), but in general it is hopeless for things like structs where the
accessors are generated by make-struct-type or things that may come from
different modules.

See (using matthew's comp=?):
> (comp=?
 (compile '(let ((x (car y))) z))
 (compile '(let () z)))
#"#~\t3.99.0.21\1\0\0\0\1\0\0\0\0#\0\0\0\237$\24f\237\"\20\2\24\30=y\24\30=z\20\0\e\370\26 at P\236$\"W^\27\301\1P\236##"
#"#~\t3.99.0.21\1\0\0\0\1\0\0\0\0\22\0\0\0\237\"\24f\237\"\20\1\24\30=z\20\0P\236\"\""
#f

> (comp=?
 (compile '(lambda (o) (let ((x (car o))) o)))
 (compile '(lambda (o) o)))
#"#~\t3.99.0.21\2\0\0\0\1\0\0\v\0\0\0!\0\0\0\e\370\26@\302W^\27\301\1\301\237\"\24f\237\"\20\0\20\0
\0Y\242\b,#*\t\336!\1"
#"#~\t3.99.0.21\1\0\0\0\1\0\0\0\0\25\0\0\0\237\"\24f\237\"\20\0\20\0
\0Y\242\b,#(\t\336\300"
#f

> (let ()
  (define-struct test (x y))
  (comp=?
   (compile '(lambda (o) (let ((x (test-x o)) (y (test-y o))) o)))
   (compile '(lambda (o) o))))
#"#~\t3.99.0.21\2\0\0\0\1\0\0\31\0\0\0@\0\0\0\e\370P\236$\"\303W^\27\301\1\e\370P\236%#\304W^\27\301\1\303\237\"\24f\237\"\20\2\24\30Btest-x\24\30Btest-y\20\0Y\242\b,#,\t\337\0!\1"
#"#~\t3.99.0.21\1\0\0\0\1\0\0\0\0\25\0\0\0\237\"\24f\237\"\20\0\20\0
\0Y\242\b,#(\t\336\300"
#f

As for timing, if you only measure trivial 1 arm patterns of course you
won't see any difference. But it will be there in complicated patterns,
which was exactly what the old optimizer handled well.

>
> This is something that can, and hopefully will, be improved.  It's a
> fairly straightforward optimization, but not one that I've had time to
> implement yet.

If you get around doing that, can you generalize it for (app ...) patterns
and not just the built-in expanders?

-- vyzo