Previously I've accepted the conventional wisdom that ANSI
Common Lisp does NOT have pattern matching. It doesn't
strike me as an important question; there are pattern
matching macros out there if I need them.
Recently I have noticed that combining typecase and
destructing-bind does much the same thing as pattern
matching. An aside in another thread suggested that CL is at
a disadvantage compared to languages with pattern matching
for algebraic manipulations such as differentiation and
simplification. This goaded me into trying to write such
code using the typecase/duct-tape/destructuring-bind technique
Here is a differentiator (restricted to binary multiplication)
(defun diff (form variable)
(typecase form
(symbol (if (eql form variable)
1
0))
(number 0)
((cons (eql +) *)
(cons '+ (mapcar (lambda(subform)
(diff subform variable))
(rest form))))
((cons (eql *)
(cons *
(cons * null)))
(destructuring-bind (prod left right) form
`(+ (* ,(diff left variable) ,right)
(* ,(diff right variable) ,left))))
((cons (eql *)
(cons *
(cons * *)))
(error "Sorry ~A makes the example too complicated." form))
Trying it out on a cubic I've prepared earlier
CL-USER> *cubic*
(+ (* 3 (* X (* X X))) (* 5 (* X X)) (* 7 X) 11)
produces the usual sorry mess
CL-USER> (diff *cubic* 'x)
(+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
(+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
(+ (* 0 X) (* 1 7))
0)
so I started hacking together a simplifier. I realise that
matching patterns in a hacky way doesn't have a future, one
needs cannonical forms and stuff for a real algebra
system. Nevertheless my goal was to see how well
typecase/duct-tape/destruction-bind works as a pattern
matching technique.
I found that hacking in extra patterns to make the
simplification work was really rather addictive and I kept
going until my test form could be fully simplified by
several applications of simplify
(defun simplify (form)
(typecase form
((cons (eql *)
(cons (eql 0)
(cons * null)))
;; (* 0 x) => 0
0)
((cons (eql *)
(cons *
(cons (eql 0) null)))
;; (* x 0) => 0
0)
((cons (eql *)
(cons (eql 1) *))
;; (* 1 x) => x
(simplify (third form)))
((cons (eql *)
(cons *
(cons (eql 1) null)))
;; (* x 1) => x
(simplify (second form)))
((cons (eql *)
(cons number
(cons number null)))
;; (* n1 n2) => n3
(* (second form) (third form)))
((cons (eql *)
(cons number
(cons (cons (eql *)
(cons number
(cons * nul)))
null)))
;; (* n1 (* n2 x)) => (* n3 x)
(destructuring-bind (op1 n (op2 m x)) form
(list '* (* n m) (simplify x))))
((cons (eql *)
(cons (cons (eql *)
(cons number
(cons * null)))
(cons number null)))
(destructuring-bind (op1 (op2 n x) m) form
(list '* (* n m) (simplify x))))
((cons (eql *)
(cons (cons (eql *)
(cons number
(cons * null)))
(cons * null)))
;; (* (* n x) y) => (* n (* x y))
(destructuring-bind (op1 (op2 n x) y) form
`(* ,n (* ,(simplify x) ,(simplify y)))))
((cons (eql *) *)
(destructuring-bind (op left right) form
(list op
(simplify left)
(simplify right))))
((cons (eql +)
(cons (eql 0)
(cons * null)))
;; (+ 0 x) => x
(third form))
((cons (eql +)
(cons *
(cons (eql 0) null)))
;; (+ x 0) => x
(second form))
((cons (eql +)
(cons *
(cons (cons (eql *)
(cons number
(cons * null)))
null)))
;; (+ x (* n x)) => (* n+1 x)
;; (+ x (* n y)) => (+ x (* n y))
(destructuring-bind (*1 x (*2 n y)) form
(let ((x (simplify x))
(y (simplify y)))
(if (equal x y)
(list '* (+ n 1) x)
`(+ ,x (* ,n ,y))))))
((cons (eql +)
(cons *
(cons * null)))
;; (+ x x) => (* 2 x)
;; (+ x y) => (+ x y)
(destructuring-bind (x y)
(mapcar #'simplify (rest form))
(if (equal x y)
`(* 2 ,x)
(list '+ x y))))
((cons (eql +)
(cons (eql 0)
(cons * (cons * null))))
(destructuring-bind (op x y z) form
(list op (simplify y) (simplify z))))
((cons (eql +)
(cons *
(cons (eql 0)
(cons * null))))
;; (+ x 0 y) => (+ x y)
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify z))))
((cons (eql +)
(cons *
(cons *
(cons (eql 0) null))))
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify y))))
((cons (eql +)
(cons number
(cons number
(cons * null))))
(destructuring-bind (op x y z) form
(list op (+ x y) (simplify z))))
((cons (eql +)
(cons *
(cons *
(cons number
(cons number null)))))
(destructuring-bind (op x y n m) form
(list op (simplify x) (simplify y)(+ n m))))
((cons (eql +) *)
(cons '+ (mapcar #'simplify (rest form))))
(t form)))
Invoking it repeatedly
CL-USER> (diff *cubic* 'x)
(+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
(+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
(+ (* 0 X) (* 1 7))
0)
CL-USER> (simplify *)
(+ (+ 0 (* (+ (* X X) (* (* 2 X) X)) 3)) (+ 0 (* (* 2 X) 5)) (+ 0 (* 1 7)) 0)
CL-USER> (simplify *)
(+ (* (+ (* X X) (* (* 2 X) X)) 3) (* (* 2 X) 5) (* 1 7) 0)
CL-USER> (simplify *)
(+ (* (+ (* X X) (* 2 (* X X))) 3) (* 10 X) 7 0)
CL-USER> (simplify *)
(+ (* (* 3 (* X X)) 3) (* 10 X) 7)
CL-USER> (simplify *)
(+ (* 9 (* X X)) (* 10 X) 7)
3 2 2
3x + 5x + 7x + 11 => 9x + 10x + 7
so that is a success of sorts.
I'm not sure what to make of this. The
typecase/duct-tape/destruction-bind technique clearly sucks,
and yet it is good enough to be addictive and fun :-) If a
program that I intended to distribute needed to do a modest
amount of pattern matching I would be very tempted to make
do with it and save myself a dependency on an external
package
There is a reason that typecase cannot bind variables. The
type (cons symbol number) cannot do
(let ((symbol (car x))
(number (cdr x)))
...
because it is already doing
(and (typep (car x) 'symbol)
(typep (cdr x) 'number))
The names are names of types. Since deftype lets symbols
name types, typecase cannot know that a symbol is supposed
to be a variable name and not a name for a type.
In my code I make use of this type matching. It is useful
and wins something back from the clunkiness of cons and eql.
The language design issue is that you cannot just write a
pattern
(a b c)
perhaps a is a literal, b a type and c a variable and I
would render it as
(typecase form
((cons (eql a) (cons b (cons * null)))
(destructuring-bind (x1 x2 c) form
(declare (ignore x1 x2))
...
So a fair summary could be that ANSI Common Lisp does have
built in pattern matching, but never fixed on a slick
notation to distinguish between literals, types, and
variables, leaving the programmer to make that choice and
define some macros to implement it.
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> So a fair summary could be that ANSI Common Lisp does have
> built in pattern matching, but never fixed on a slick
> notation to distinguish between literals, types, and
> variables, leaving the programmer to make that choice and
> define some macros to implement it.
Yes. I think decent pattern matching would be a welcome addition to the next
Lisp standard.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 4, 3:14 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> Alan Crowe wrote:
> > So a fair summary could be that ANSI Common Lisp does have
> > built in pattern matching, but never fixed on a slick
> > notation to distinguish between literals, types, and
> > variables, leaving the programmer to make that choice and
> > define some macros to implement it.
>
> Yes. I think decent pattern matching would be a welcome addition to the next
> Lisp standard.
Actually, Crowe (and Joswig) explained why pattern matching should not
be part of the language. Summary: There isn't a single definition
that handles all the relevant cases.
For those who want hand-cuffs, other languages happily provide them.
Andy Freeman wrote:
> Actually, Crowe (and Joswig) explained why pattern matching should not
> be part of the language.
Nonsense. Alan gave an excellent example of when pattern matching is useful.
There are many more.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 5, 1:24 am, Jon Harrop <····@ffconsultancy.com> wrote:
>
> Nonsense. Alan gave an excellent example of when pattern matching is useful.
> There are many more.
And all different.
Tim Bradshaw wrote:
> On May 5, 1:24 am, Jon Harrop <····@ffconsultancy.com> wrote:
>> Nonsense. Alan gave an excellent example of when pattern matching is
>> useful. There are many more.
>
> And all different.
And all benefit from a useful core pattern matcher.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 5, 11:16 am, Jon Harrop <····@ffconsultancy.com> wrote:
> Tim Bradshaw wrote:
> > On May 5, 1:24 am, Jon Harrop <····@ffconsultancy.com> wrote:
> >> Nonsense. Alan gave an excellent example of when pattern matching is
> >> useful. There are many more.
>
> > And all different.
>
> And all benefit from a useful core pattern matcher.
Is that core re or what? What happens if that core is more powerful
(read expensive) than what I need? If it is less powerful, then
what? What if its token syntax doesn't match my needs? Oops - that
"core pattern matcher" just became a constraint.
Lisp actually has lots of pattern matchers. And, unlike other
languages, rolling your own is painless enough that not using one
isn't a huge problem.
Things are different for languages that make library-based pattern
matching inconvenient.
However, the basic fact remains - Harrop doesn't like Lisp. Good for
him. Why doesn't he take his dislike somewhere else? (Are all OCaml/
F# advocates so rude?)
On May 7, 8:08 am, Andy Freeman <······@earthlink.net> wrote:
> However, the basic fact remains - Harrop doesn't like Lisp. Good
for
> him. Why doesn't he take his dislike somewhere else? (Are all OCaml/
> F# advocates so rude?)
He's probably using Usenet as free advertising rather than for its
intended purpose as a discussion forum...
mfh
Andy Freeman wrote:
> On May 5, 11:16 am, Jon Harrop <····@ffconsultancy.com> wrote:
>> And all benefit from a useful core pattern matcher.
>
> What happens if that core is more powerful (read expensive) than what I
> need?
You don't use all of its features.
> If it is less powerful, then what?
You must combine pattern matching with other approaches (which is exactly
what you already do) or extend the matcher using macros (OCaml) or active
patterns (F#).
> What if its token syntax doesn't match my needs?
Change the syntax to whatever you want.
> Oops - that "core pattern matcher" just became a constraint.
How so?
> Lisp actually has lots of pattern matchers.
None are as common as any of the other FPLs with pattern matching built in.
> And, unlike other languages, rolling your own is painless enough that not
> using one isn't a huge problem.
Greenspun. The pattern matchers in Haskell, OCaml, F# and Mathematica
compilers are thousands of lines of code each. Pattern matching algorithms
remain an active area of research.
> However, the basic fact remains - Harrop doesn't like Lisp.
What if Common Lisp lacked mapcar? Would you say, "hey, no problem. Everyone
can implement their own and introduce unnecessary quirks and
incompatibilities."? Would you say, "there are thousands of mapcar
implementations out there, which is much better than having a single
widely-adopted standard."?
The fact is, pattern matching is more common that mapcar. It is ubiquitous
in languages that support it. I think that warrants putting a standard
pattern matcher in the next version of Lisp.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 7, 9:12 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> Greenspun. The pattern matchers in Haskell, OCaml, F# and Mathematica
> compilers are thousands of lines of code each. Pattern matching algorithms
> remain an active area of research.
Of course, that's an argument *against* standardizing it just yet.
----
Dan Muller
DanM wrote:
> On May 7, 9:12 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>> Greenspun. The pattern matchers in Haskell, OCaml, F# and Mathematica
>> compilers are thousands of lines of code each. Pattern matching
>> algorithms remain an active area of research.
>
> Of course, that's an argument *against* standardizing it just yet.
You could say the same of garbage collection so I'm not sure that is a very
good reason to provide no pattern matching whatsoever.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On 2007-05-08 00:29:15 -0400, Jon Harrop <···@ffconsultancy.com> said:
> You could say the same of garbage collection so I'm not sure that is a very
> good reason to provide no pattern matching whatsoever.
Clearly usenet has no garbage collection or you'd have been marked and
swept from c.l.l long ago.
Please sell your Microsoft F# kool-aid somewhere else.
Jon Harrop <···@ffconsultancy.com> writes:
> DanM wrote:
>> On May 7, 9:12 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>>> Greenspun. The pattern matchers in Haskell, OCaml, F# and Mathematica
>>> compilers are thousands of lines of code each. Pattern matching
>>> algorithms remain an active area of research.
>>
>> Of course, that's an argument *against* standardizing it just yet.
>
> You could say the same of garbage collection so I'm not sure that is
> a very good reason to provide no pattern matching whatsoever.
Right, but it's a very good reason not to /standardize/ such a
facility, but to leave implementors and users room to experiment.
This is exactly the situation with garbage collection in Common Lisp:
memory management is not addressed by the Common Lisp standard, and so
implementors are not bound to any particular memory management
approach.
--
RmK
On May 8, 2:12 am, Jon Harrop <····@ffconsultancy.com> wrote:
>
> None are as common as any of the other FPLs with pattern matching built in.
Um, when did CL become a functional programming language again?
On May 7, 6:12 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> Andy Freeman wrote:
> > On May 5, 11:16 am, Jon Harrop <····@ffconsultancy.com> wrote:
> >> And all benefit from a useful core pattern matcher.
>
> > What happens if that core is more powerful (read expensive) than what I
> > need?
>
> You don't use all of its features.
Wrong answer - I don't use it because it's more expensive.
> > If it is less powerful, then what?
>
> You must combine pattern matching with other approaches
In other words, I end up writing a pattern matcher. And, outside of
the tokenizer, very little of the less powerful, albeit standard,
"pattern matcher" is likely to be useful.
In practice, languages with standard pattern matchers "encourage"
people to bend their problem to the pattern matcher. In other words,
it becomes a constraint.
> > What if its token syntax doesn't match my needs?
>
> Change the syntax to whatever you want.
Which is almost always painful.
> > Lisp actually has lots of pattern matchers.
>
> None are as common as any of the other FPLs with pattern matching built in.
The relevant question is whether they are common enough for their
usage.
> > And, unlike other languages, rolling your own is painless enough that not
> > using one isn't a huge problem.
>
> Greenspun. The pattern matchers in Haskell, OCaml, F# and Mathematica
> compilers are thousands of lines of code each.
Large implementations are actually a negative.
> Pattern matching algorithms remain an active area of research.
Which means that standardization is premature.
I note that python seems to do a lot of pattern matching without any
language support. (Yes, there are libraries.)
If Harrop is to be believed, F# hasn't (can't?) managed that simple
trick, but Lisp could.
> > However, the basic fact remains - Harrop doesn't like Lisp.
Note that Harrop doesn't tell us why he keeps flogging F# and OCaml in
cll.
Maybe he'll answer a different question - why should anyone care what
he thinks about what should be in lisp, a language that he doesn't
like, won't use, etc?
Andy Freeman wrote:
> On May 7, 6:12 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>> Andy Freeman wrote:
>> > On May 5, 11:16 am, Jon Harrop <····@ffconsultancy.com> wrote:
>> >> And all benefit from a useful core pattern matcher.
>>
>> > What happens if that core is more powerful (read expensive) than what I
>> > need?
>>
>> You don't use all of its features.
>
> Wrong answer - I don't use it because it's more expensive.
For what definition of "expensive"?
>> > If it is less powerful, then what?
>>
>> You must combine pattern matching with other approaches
>
> In other words, I end up writing a pattern matcher.
Which is much easier in the presence of a simpler pattern matcher.
> In practice, languages with standard pattern matchers "encourage"
> people to bend their problem to the pattern matcher. In other words,
> it becomes a constraint.
Not in the presence of macros or active patterns.
>> > What if its token syntax doesn't match my needs?
>>
>> Change the syntax to whatever you want.
>
> Which is almost always painful.
But it is better than what you're currently doing.
>> > And, unlike other languages, rolling your own is painless enough that
>> > not using one isn't a huge problem.
>>
>> Greenspun. The pattern matchers in Haskell, OCaml, F# and Mathematica
>> compilers are thousands of lines of code each.
>
> Large implementations are actually a negative.
Even if they are well-defined, fast and correct?
>> Pattern matching algorithms remain an active area of research.
>
> Which means that standardization is premature.
I don't have a problem with using the state-of-the-art.
>> > However, the basic fact remains - Harrop doesn't like Lisp.
>
> Note that Harrop doesn't tell us why he keeps flogging F# and OCaml in
> cll.
Because lots of people here like to see what they're missing.
> Maybe he'll answer a different question - why should anyone care what
> he thinks about what should be in lisp, a language that he doesn't
> like, won't use, etc?
To me, the Lisp approach to destructuring data structures is so primitive
and tedious that I feel I might as well be writing assembler. Rather than
reinvent the wheel, I asked for advice on libraries that supplement Lisp
with a more modern approach to destructuring, only to find that most of
them suck and all are inherently slow because this functionality is missing
from the language.
Now, if I want to write Lisp I start by asking an OCaml compiler to output
its intermediate Lisp representation.
I know I'm not a "real Lisper" and that's why I get shunned here. But Alan
Crowe is and look at his Lisp implementation of a ten line OCaml function:
;; much improved
(defun simplify (form)
(typecase form
((tuple '* 0 *) 0)
((tuple '* * 0) 0)
((tuple '* 1 *) (simplify (third form)))
((tuple '* * 1) (simplify (second form)))
((tuple '* number number) (* (second form) (third form)))
((tuple '* number (tuple '* number *)
(destructuring-bind (op1 n (op2 m x)) form
(list '* (* n m) (simplify x)))))
((tuple '* (tuple '* number *) number)
(destructuring-bind (op1 (op2 n x) m) form
(list '* (* n m) (simplify x))))
((tuple '* (tuple '* number *) *)
;; raise buried number
(destructuring-bind (op1 (op2 n x) y) form
`(* ,n (* ,(simplify x) ,(simplify y)))))
((tuple '* * *)
(destructuring-bind (op left right) form
(list op
(simplify left)
(simplify right))))
((tuple '* etc)(error "~a not binary" form))
((tuple '+ 0 *) (simplify (third form)))
((tuple '+ * 0) (simplify (second form)))
((tuple '+ * (tuple '* number *))
;; (+ x (* n x)) => (* n+1 x)
;; (+ x (* n y)) => (+ x (* n y))
(destructuring-bind (*1 x (*2 n y)) form
(let ((x (simplify x))
(y (simplify y)))
(if (equal x y)
(list '* (+ n 1) x)
`(+ ,x (* ,n ,y))))))
((tuple '+ * *)
;; (+ x x) => (* 2 x)
;; (+ x y) => (+ x y)
(destructuring-bind (x y)
(mapcar #'simplify (rest form))
(if (equal x y)
`(* 2 ,x)
(list '+ x y))))
((tuple '+ 0 * *)
(destructuring-bind (op x y z) form
(list op (simplify y) (simplify z))))
((tuple '+ * 0 *)
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify z))))
((tuple '+ * * 0)
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify y))))
((tuple '+ number number *)
(destructuring-bind (op x y z) form
(list op (+ x y) (simplify z))))
((tuple '+ * * number number)
(destructuring-bind (op x y n m) form
(list op (simplify x) (simplify y)(+ n m))))
((tuple '+ etc)
(cons '+ (mapcar #'simplify (rest form))))
(t form)))
and before you say "oh, but he's an especially stupid Lisper". Look at Andre
Thieme's Lisp:
(defun simplify (xexpr)
(declare (optimize (speed 3)))
(if (atom xexpr)
xexpr
(labels ((make-expr (op f g)
(list op f g))
(optimize-plus (f g)
(cond
((eql f 0) g)
((eql g 0) f)
((and (numberp f) (numberp g)) (+ f g))
(t (optimize-associatively '+ #'optimize-plus f
g))))
(optimize-multiply (f g)
(cond
((or (eql f 0) (eql g 0)) 0)
((eql f 1) g)
((eql g 1) f)
((and (numberp f) (numberp g)) (* f g))
(t (optimize-associatively '* #'optimize-multiply f
g))))
(optimize-associatively (op opt-func f g)
(cond
((and (listp g) (eq op (first g)))
(let ((a (funcall opt-func f (second g))))
(funcall opt-func a (third g))))
(t (make-expr op f g)))))
(declare (inline make-expr optimize-associatively))
(let* ((op (first xexpr))
(f (simplify (second xexpr)))
(g (simplify (third xexpr))))
(cond
((eq op '+) (optimize-plus f g))
((eq op '*) (optimize-multiply f g)))))))
Look at Nathan Froyd's implementation:
(defun simplify-common-funcs (xexpr)
(declare (optimize (speed 3)))
(if (atom xexpr)
xexpr
(labels ((make-expr (op f g)
(list op f g))
(optimize-plus (f g)
(cond
((eql f 0) g)
((eql g 0) f)
((and (numberp f) (numberp g)) (+ f g))
(t (optimize-associatively '+ #'optimize-plus f g))))
(optimize-multiply (f g)
(cond
((or (eql f 0) (eql g 0)) 0)
((eql f 1) g)
((eql g 1) f)
((and (numberp f) (numberp g)) (* f g))
(t (optimize-associatively '* #'optimize-multiply f g))))
(optimize-associatively (op opt-func f g)
(cond
((and (listp g) (eq op (first g)))
(let ((a (funcall opt-func f (second g))))
(funcall opt-func a (third g))))
(t (make-expr op f g)))))
(declare (inline make-expr optimize-associatively))
(let* ((op (first xexpr))
(f (simplify-common-funcs (second xexpr)))
(g (simplify-common-funcs (third xexpr))))
(cond
((eq op '+) (optimize-plus f g))
((eq op '*) (optimize-multiply f g)))))))
I think these solutions speak for themselves.
The Lisper's rebuttal will be "pattern matching is only good for symbolic
simplification which is widely admitted to be a real weak-point of Lisp".
But pattern matching is equally useful for RB trees in data structures,
scene graphs in computer graphics, huffman trees in data compression,
suffix encoders in bioinformatics and pretty much everything else.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 8, 10:52 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> Andy Freeman wrote:
> > Wrong answer - I don't use it because it's more expensive.
>
> For what definition of "expensive"?
The "costs more" definition.
> > In practice, languages with standard pattern matchers "encourage"
> > people to bend their problem to the pattern matcher. In other words,
> > it becomes a constraint.
>
> Not in the presence of macros or active patterns.
Coulda, woulda, shoulda, but doesn't happen often enough to count.
> > Maybe he'll answer a different question - why should anyone care what
> > he thinks about what should be in lisp, a language that he doesn't
> > like, won't use, etc?
>
> To me, the Lisp approach to destructuring data structures is so primitive
> and tedious that I feel I might as well be writing assembler.
Harrop "forgets" that he doesn't write Lisp, he writes F#, OCaml,
etc. There's no reason for him to write Lisp, and he doesn't. Given
that, why does he care?
After all, if he's correct, his choice gives him an advantage over the
heathens.
Note that Fortran folks also believe that Lisp is inferior. You don't
see them wandering through here. Instead, they sit back and let the
bucks roll in.
> I think these solutions speak for themselves.
Not really, but it would be an improvement if we only heard from the
solutions.
It's interesting that Harrop confuses "pattern matching can be used
for" with "pattern matching is the right approach to".
On 2007-05-09 12:01:04 -0400, Andy Freeman <······@earthlink.net> said:
>
>> I think these solutions speak for themselves.
>
> Not really, but it would be an improvement if we only heard from the
> solutions.
>
> It's interesting that Harrop confuses "pattern matching can be used
> for" with "pattern matching is the right approach to".
He also coveniently ignores the existence of several pattern matching
libraries for those who want pattern matching, while putting forth
examples from usenet posts which explicitly say "how far could we go if
we limited ourselves to ..." as if these were the only possibilities
for pattern matching in Common Lisp.
Perl compatible regular expressions are not part of common lisp either.
But I don't care, and neither does any lisper with a lick of sense
because all I have to do to get perl compatible regular expressions is:
(asdf :cl-ppcre)
and Edi Weitz's cl-ppcre is loaded and ready to use.
Similarly, if I needed pattern matching I'd just load one of the
existing pattern matching libraries and use it.
http://common-lisp.net/project/cl-unification/
http://www.cliki.net/fare-matcher
http://common-lisp.net/project/bese/arnesi.html
http://lisa.sourceforge.net/
Note also that these provide a *variety* of solutions using different
algorithms since, as even Harrop admits, "pattern matching" is not one
well defined, stable, cut and dried thing. Different projects want
different types of pattern matching. Common Lisp has a number of
libraries.
F# has what's built in so you're encouraged to conform your thinking
about the problem to the tool that F# gives you. The lisp approach is
just the opposite - you're encouraged to conform the language to the
way you think about the problem. Numerous useful libraries facilitate
this process.
Big picture:
- Common Lisp has plenty of libraries for things which are not in the
base langauge such as pattern matching.
- Harrop is just stirring up a tempest in a teapot here in order to
troll for business for his flying frog consultancy.
Finally to anticipate Harrop's usual comback (for nubz, we've been on
this merry-go-round with Harrop before), when you ask us to implement
your current favorite OCaml/F# toy example using an existing Common
Lisp pattern matching library realize that a thread just a week or two
ago already gave examples using these libraries:
<http://groups.google.com/group/comp.lang.lisp/msg/6675afefffaa14d1?hl=en&>
I suggest you try to implement your toy example du jour using one of
these libraries *yourself* and post your versions here for suggestions
and corrections. You might actually <gasp!> post something that is *on
topic* for comp.lang.lisp.
You may have the ignorant fooled, but people who actually use common
lisp know that not having pattern matching built into the language is a
non-issue. Your rants here are little different than a Perl programmer
showing up claiming that perl is better than Common Lisp because Perl
has regexes built in. No one who actually knows Common Lisp cares,
because we know we can always reach for an existing library for this
when we need it.
Now either go away and shill Microsoft junk on
comp.lang.basic.visual.misc where they're predisposed to like this
stuff, or code up one of your F# examples using one or more of the
above Common Lisp libraries and post something on topic. But stop
hawking F# on a newsgroup specifically devoted to Common Lisp.
On May 8, 10:52 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>
> I know I'm not a "real Lisper" and that's why I get shunned here.
That is not the reason.
On May 8, 10:52 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>
> The Lisper's rebuttal will be "pattern matching is only good for symbolic
> simplification which is widely admitted to be a real weak-point of Lisp".
Um, yeah. That's the first thing that came to *my* mind...
Pattern matching is not a single, monolithic paradigm, but a
description that encompasses a number of data-driven programming
techniques from simple type dispatch to unification to frame-based
knowledge representation and more. As it happens, the first
programming language to have tree-based pattern matching was Lisp
(Fred McBride's thesis). Pattern matching, especially type-related
pattern matching, is a broad and rich area of research.
Because of this, there is no one-size-fits-all pattern matcher in
Common Lisp. There are, however, many pattern matching libraries.
I'm sorry you find that `most of them suck', but perhaps you could
enumerate the ones that you tried and we can see if anyone in the
group has an idea for one that is more appropriate for your uses.
Jon Harrop wrote:
> The fact is, pattern matching is more common that mapcar. It is ubiquitous
> in languages that support it. I think that warrants putting a standard
> pattern matcher in the next version of Lisp.
A pattern matcher is essentially a glorified if statement. The
disadvantage with if statements is that they are not extensible - and
the same applies to pattern matchers.
So if you want to add new subtypes / subclasses to your existing
abstract data types / classes, you have to manually go through all the
if statements / pattern matchers and add new branches to handle the new
types.
That's what dynamic dispatch / OOP is there for to solve this particular
problem. With OOP, whenever you add a subclass, you can also add the
respective new methods that are necessary to glue the subclass with the
rest of the program.
However in most OOP approaches, now the problem is turned to the side:
It is now hard to add new functionality, because for each new function
you have to manually go trough all the classes and add the necessary
methods to define the specific behavior for those functions.
This situation, that you can either extend the data types or the
functionality conveniently is also called the expression problem. There
is no general solution for it that applies without exceptions because
for each function or for each datatype, you have exceptions wrt what
respective specific behaviors should be.
However, in CLOS the situation is not that pressing: Since in CLOS you
define methods outside of classes, you can actually easily do both, add
new classes and group the necessary methods with them, or add new
generic functions and again group the necessary methods with them. All
you need is some way of determining which methods are necessary - but
this is also solved well due to the introspective interface to the
object system which allows you to query the system for existing classes
and their subclasses and existing generic functions and their methods.
As soon as you have dynamic dispatch and dynamic types, the need for
pattern matchers is greatly reduced. Pattern matchers are indeed more
useful for languages with static type systems where at runtime you
cannot refer to the type of a value anymore.
What is missing in CLOS is a generalization of method dispatch.
Currently, CLOS provides two kinds of specializers: class specializers
and eql specializers which dispatch on the class or on the object
identity of a parameter respectively. It would be nice if we could also
dispatch on more complex predicates, like the contents of a parameter
(for example, if it is a collection), or some other properties (like in
predicate dispatch). This is not a brand new idea, but there are some
difficult problems involved especially if you want to integrate such
generalized dispatch with a dynamic language. Several people are
currently working on ideas how to integrate this with CLOS, and there
are some good chances that this can be done with only minor
modifications to the overall design and implementation of CLOS.
I find this a much more interesting development than the integration of
pattern matcher, which is a non-extensible old hat. You would basically
get pattern matchers for free, but in a much nicer dynamically
extensible setting.
Of course, if you don't care about dynamic extensibility, you can as
well google for "predicate dispatch" to find out about some existing
approaches which already provide such features (including at least one
for CLOS).
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On May 8, 11:30 am, Pascal Costanza <····@p-cos.net> wrote:
> Jon Harrop wrote:
> > The fact is, pattern matching is more common that mapcar. It is ubiquitous
> > in languages that support it. I think that warrants putting a standard
> > pattern matcher in the next version of Lisp.
>
> A pattern matcher is essentially a glorified if statement. The
> disadvantage with if statements is that they are not extensible - and
> the same applies to pattern matchers.
>
> So if you want to add new subtypes / subclasses to your existing
> abstract data types / classes, you have to manually go through all the
> if statements / pattern matchers and add new branches to handle the new
> types.
>
> That's what dynamic dispatch / OOP is there for to solve this particular
> problem. With OOP, whenever you add a subclass, you can also add the
> respective new methods that are necessary to glue the subclass with the
> rest of the program.
>
> However in most OOP approaches, now the problem is turned to the side:
> It is now hard to add new functionality, because for each new function
> you have to manually go trough all the classes and add the necessary
> methods to define the specific behavior for those functions.
>
> This situation, that you can either extend the data types or the
> functionality conveniently is also called the expression problem. There
> is no general solution for it that applies without exceptions because
> for each function or for each datatype, you have exceptions wrt what
> respective specific behaviors should be.
>
> However, in CLOS the situation is not that pressing: Since in CLOS you
> define methods outside of classes, you can actually easily do both, add
> new classes and group the necessary methods with them, or add new
> generic functions and again group the necessary methods with them. All
> you need is some way of determining which methods are necessary - but
> this is also solved well due to the introspective interface to the
> object system which allows you to query the system for existing classes
> and their subclasses and existing generic functions and their methods.
>
> As soon as you have dynamic dispatch and dynamic types, the need for
> pattern matchers is greatly reduced. Pattern matchers are indeed more
> useful for languages with static type systems where at runtime you
> cannot refer to the type of a value anymore.
Yes. It is also interesting of your data can be described by patterns
and your operations by applying patterns. Computer Algebra
is such a domain. There are others. You find lots of them
in applications which are using deduction or rule-based systems.
Many uses have been very dynamic in nature. Users can
add, edit or remove rules at runtime. This has been always
very important for knowledge-based systems.
As a tool for programming in certain domains I find it useful.
But then the power of the tool is determined by the domain.
> What is missing in CLOS is a generalization of method dispatch.
Is it theoretically missing or practically missing? Is there any
developer of a
software system who says, he I miss this feature?
> Currently, CLOS provides two kinds of specializers: class specializers
> and eql specializers which dispatch on the class or on the object
> identity of a parameter respectively. It would be nice if we could also
> dispatch on more complex predicates, like the contents of a parameter
> (for example, if it is a collection), or some other properties (like in
> predicate dispatch). This is not a brand new idea, but there are some
> difficult problems involved especially if you want to integrate such
> generalized dispatch with a dynamic language. Several people are
> currently working on ideas how to integrate this with CLOS, and there
> are some good chances that this can be done with only minor
> modifications to the overall design and implementation of CLOS.
This already has been explored in the past and I doubt that newer
attempts
will produce something useful. I see there a trend to explore
mechanisms
without having a problem. Later you have a solution but not problem.
I see lots of work on theoretical improvements, but little work based
on
practical needs. There just seems to be little software that is
significant,
where architectural alternatives are explored and the usefulness of
those then can be evaluated.
CLOS breaks done the generic functions into methods. With specific
method
combinations you can get also new ways to specify the purpose of a
particular
method in a generic function.
I'm not sure that exposing too much specifics of the object into the
parameter list is a good idea. An attempt can be seen in presentations
and presentation methods in CLIM. There is lots of complicated
machinery there.
>
> I find this a much more interesting development than the integration of
> pattern matcher, which is a non-extensible old hat. You would basically
> get pattern matchers for free, but in a much nicer dynamically
> extensible setting.
>
> Of course, if you don't care about dynamic extensibility, you can as
> well google for "predicate dispatch" to find out about some existing
> approaches which already provide such features (including at least one
> for CLOS).
>
> Pascal
>
> --
> My website:http://p-cos.net
> Common Lisp Document Repository:http://cdr.eurolisp.org
> Closer to MOP & ContextL:http://common-lisp.net/project/closer/
From: Edi Weitz
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <uhcqn38wq.fsf@agharta.de>
On 8 May 2007 03:03:26 -0700, ·······@corporate-world.lisp.de" <······@corporate-world.lisp.de> wrote:
> I see there a trend to explore mechanisms without having a
> problem. Later you have a solution but not problem.
Pascal is an academic... :)
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz wrote:
> On 8 May 2007 03:03:26 -0700, ·······@corporate-world.lisp.de" <······@corporate-world.lisp.de> wrote:
>
>> I see there a trend to explore mechanisms without having a
>> problem. Later you have a solution but not problem.
>
> Pascal is an academic... :)
That too... ;)
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
······@corporate-world.lisp.de wrote:
> On May 8, 11:30 am, Pascal Costanza <····@p-cos.net> wrote:
>> What is missing in CLOS is a generalization of method dispatch.
>
> Is it theoretically missing or practically missing?
It's a practical inconvenience that I have encountered myself, and I am
aware of other examples.
Of course, "missing" is a big word. In a Turing-complete language,
nothing is really "missing." ;)
> Is there any developer of a software system who says, he I miss this feature?
Yes. There is a good chance that there will be some interesting report
in this regard at this year's European Lisp Workshop.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> Jon Harrop wrote:
>> The fact is, pattern matching is more common that mapcar. It is
>> ubiquitous in languages that support it. I think that warrants putting a
>> standard pattern matcher in the next version of Lisp.
>
> A pattern matcher is essentially a glorified if statement.
No, because "if" statements do not deconstruct. Pattern matching replaces
if/cond/car/cdr/destructuring-bind with a single unified construct that
encourages high-level programming, making for simpler and faster code.
> The
> disadvantage with if statements is that they are not extensible - and
> the same applies to pattern matchers.
For SML/Haskell pattern matching, yes. In OCaml, you can extend the pattern
matcher using macros. In F#, you can extend the pattern matcher using
active patterns (views).
> So if you want to add new subtypes / subclasses to your existing
> abstract data types / classes, you have to manually go through all the
> if statements / pattern matchers and add new branches to handle the new
> types.
Sometimes, yes.
> That's what dynamic dispatch / OOP is there for to solve this particular
> problem.
Except they don't really solve it, they just alter it to make it worse as
you explain here:
> However in most OOP approaches, now the problem is turned to the side:
> It is now hard to add new functionality, because for each new function
> you have to manually go trough all the classes and add the necessary
> methods to define the specific behavior for those functions.
Exactly.
> As soon as you have dynamic dispatch and dynamic types, the need for
> pattern matchers is greatly reduced.
Lisp has those yet it cannot express the symbolic simplifier as elegantly or
efficiently as SML, Haskell, OCaml, F# and many other modern FPLs.
> Pattern matchers are indeed more
> useful for languages with static type systems where at runtime you
> cannot refer to the type of a value anymore.
Scheme and F# are obvious counter examples. F# provides run-time type
information yet pattern matching remains ubiquituous, precisely because it
is so useful and cannot be represented using dynamic dispatch and types.
> What is missing in CLOS is a generalization of method dispatch.
> Currently, CLOS provides two kinds of specializers: class specializers
> and eql specializers which dispatch on the class or on the object
> identity of a parameter respectively. It would be nice if we could also
> dispatch on more complex predicates, like the contents of a parameter
> (for example, if it is a collection), or some other properties (like in
> predicate dispatch).
That is probably a definition of pattern matching. The main difference is
that it is dynamic whereas the pattern matchers that I am used to
statically reflect the structure of the data.
I have no experience from CLOS but, from what I have heard, it is extremely
slow. Given that one advantage of pattern matching is performance, perhaps
a CLOS-based implementation is not the way to go?
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
From: Kent M Pitman
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <uzm4e1osx.fsf@nhplace.com>
I'm just joining randomly intot his conversation; I've only been
spot-checking occasional posts, so forgive me if this has been
covered, but...
Jon Harrop <···@ffconsultancy.com> writes:
> No, because "if" statements do not deconstruct. Pattern matching replaces
> if/cond/car/cdr/destructuring-bind with a single unified construct that
> encourages high-level programming, making for simpler and faster code.
Be careful here. In static languages, pattern matching encourages and
exploits abstraction, while in Lisp and other dynamic languages, it can
bypass intentional type and dispatch on representational type, which is
not always what is wanted.
I sometimes refer to such traps as "structured data abstraction violations".
They look like they're being helpful, and they trick you into using them
because they seem so well-packaged. But the packaging is tricking you into
bypassing abstraction instead of using it, at least in cases where the
static/intentional types are not one-to-one with dynamic/representational
types.
This is related in turn to the equality issue, which is less severe in
static languages.
Kent M Pitman wrote:
> Be careful here. In static languages, pattern matching encourages and
> exploits abstraction, while in Lisp and other dynamic languages, it can
> bypass intentional type and dispatch on representational type, which is
> not always what is wanted.
Can you elaborate on this? Do you mean that pattern matching encourages you
to be less dynamic?
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
From: Kent M Pitman
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <utzumt5s9.fsf@nhplace.com>
Jon Harrop <···@ffconsultancy.com> writes:
> Kent M Pitman wrote:
> > Be careful here. In static languages, pattern matching encourages and
> > exploits abstraction, while in Lisp and other dynamic languages, it can
> > bypass intentional type and dispatch on representational type, which is
> > not always what is wanted.
>
> Can you elaborate on this? Do you mean that pattern matching encourages you
> to be less dynamic?
No, I wouldn't say that. But you must at least understand whether you
are dispatching on declared type or representational type. Lisp,
which does not use so-called "strong typing", doesn't know the
declared type of the data it receives; it knows the dynamically
accessible representational type. That's different and sometime may
have different effects.
If you're just dealing with data structures as pure shapes, it's fine.
But people have been known to create overlapping shapes. And if you
assume your pattern matcher will naturally sort that out, you're asking
for trouble. I'm not saying you have to not be a deep thinker to want
pattern matcher, but pattern matchers will attract those who are not
deep thinkers because they seem to involve less direct programming.
Assume these are three independent abstractions:
(defun make-simple-frob () 'frob)
(defun make-foo (x) (list 'foo x))
(defun make-frob (x) (list 'frob (list 'foo x)))
Now assume I do:
(pattern-case v
((frob (foo $x)) ...action...))
in some language where (frob $x) is the pattern with frob being a
constant term and $x being a pattern variable.
Then if I give v as the result of (list (make-simple-frob) (make-foo 3)),
should it match? If I give v as (make-frob 3) should it match? Are
you sure that (list (make-simple-frob) (make-foo 3)) and (make-frob 3)
are intended to be semantically the same?
It's hard to make a direct comparison to strongly typed languages, since
strongly typed languages often don't give you the ability to examine
representational tokens, and so the extra tokens like the 'foo and 'frob
in the examples above would not be there to confuse things. That makes
this comparison tricky. But the feature of such languages is that many
such languages can't confuse:
(pattern-case v
(frob($x) ...))
or
(pattern-case v
([bar, foo($x)] ...))
because the function wouldn't type-reconcile without knowing this.
Note well: You might assume punning is just bad and has no place in
programming, so you might say that such languages give you a leg up
and are automatically superior. I don't agree. While this particular
instance punning has some problems, there are cases where punning and
dynamic inspect gives you very sophisticated effects that are hard to
simulate in static languages.
Language choices are not about Good vs Bad, they are about design
trade-offs: you trade away the things you don't plan to do in favor of
the things you do plan to do. The hard part is getting that planning
right so you aren't pinned into a corner down the line. Since Lisp
supports changing one's mind later, I tend to like that, but it comes
at some occasional costs, and I think there's a minor but manageable
cost on the issue of clarity of intent on certain intentional type
issues. It's not a cost that troubles me because it buys other things
I care about. Static typing feels like a stranglehold to me. But
it's worth acknowledging that there are people who will be troubled by
these design trade-offs because they value things differently.
For other related issues, see my http://www.nhplace.com/kent/PS/EQUAL.html
On May 8, 10:43 pm, Jon Harrop <····@ffconsultancy.com> wrote:
here:
> F# provides run-time type
> information yet pattern matching remains ubiquituous, precisely because it
> is so useful and cannot be represented using dynamic dispatch and types.
If pattern matching is the preferred mechanism in F#, it's because PM
is the easiest way to do things that one wants to do in F#. That's a
statement about F#.
> I have no experience
That's different then - you're clearly an expert. You're wasting your
time here.
Jon Harrop wrote:
> Pascal Costanza wrote:
>> Jon Harrop wrote:
>>> The fact is, pattern matching is more common that mapcar. It is
>>> ubiquitous in languages that support it. I think that warrants putting a
>>> standard pattern matcher in the next version of Lisp.
>> A pattern matcher is essentially a glorified if statement.
>
> No, because "if" statements do not deconstruct. Pattern matching replaces
> if/cond/car/cdr/destructuring-bind with a single unified construct that
> encourages high-level programming, making for simpler and faster code.
What part of "glorified" is it that you didn't understand?
>> Pattern matchers are indeed more
>> useful for languages with static type systems where at runtime you
>> cannot refer to the type of a value anymore.
>
> Scheme and F# are obvious counter examples. F# provides run-time type
> information yet pattern matching remains ubiquituous, precisely because it
> is so useful and cannot be represented using dynamic dispatch and types.
How do you know that anything in F# is ubiquitous? It only exists for
three years now...
> I have no experience from CLOS but, from what I have heard, it is extremely
> slow.
Maybe you should check your hearing, then.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> Jon Harrop wrote:
>> Pascal Costanza wrote:
>>> Jon Harrop wrote:
>>>> The fact is, pattern matching is more common that mapcar. It is
>>>> ubiquitous in languages that support it. I think that warrants putting
>>>> a standard pattern matcher in the next version of Lisp.
>>> A pattern matcher is essentially a glorified if statement.
>>
>> No, because "if" statements do not deconstruct. Pattern matching replaces
>> if/cond/car/cdr/destructuring-bind with a single unified construct that
>> encourages high-level programming, making for simpler and faster code.
>
> What part of "glorified" is it that you didn't understand?
So by "glorified" you mean "nothing to do with".
>> I have no experience from CLOS but, from what I have heard, it is
>> extremely slow.
>
> Maybe you should check your hearing, then.
This article:
http://www.franz.com/about/press_room/clos.article.pdf
states that saying CLOS is not slow because computers are now faster than
they were. Well, if only I'd known that before...
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
Jon Harrop <···@ffconsultancy.com> writes:
> Pascal Costanza wrote:
>> Jon Harrop wrote:
>>> I have no experience from CLOS but, from what I have heard, it is
>>> extremely slow.
>>
>> Maybe you should check your hearing, then.
>
> This article:
>
> http://www.franz.com/about/press_room/clos.article.pdf
>
> states that saying CLOS is not slow because computers are now faster than
> they were. Well, if only I'd known that before...
Perhaps not only your hearing, but your English reading skills as well
:-)
The portion of the article in question says (in a section that is
responding to common myths, speicifically: "CL/CLOS is slow"):
"Since 1985, PC have become 100 times faster. Much slower languages,
such as Java and Visual Basic, have become popular. Today, CL/CLOS can
run effectively on any standard PC and its implementations are faster."
1. This is not just about CLOS alone. It is true that the article is
about CLOS, but CLOS did not exist in 1985, and the myth about CLOS
being slow is the same as the myth about CL being slow. This is why
the author consistently wrote about CL/CLOS, rather than CLOS alone.
2. There is no "because" (or "therefore") stated or implied in this
statement. The conjunction is "and", directly attributing CL/CLOS's
speedups to both machine speedups (which have benefitted all
languages, of course), as well as inherently faster implementations,
both of CL and of CLOS.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Jon Harrop <···@ffconsultancy.com> wrote:
> I have no experience from CLOS but, from what I have heard, it is
> extremely slow.
Gosh. Now, even Lispers themselves contribute to propagate
legends about Lisp slowness :-( We're in biiiig trouble I telya.
Seriously, this kind of comment is not only annoying, but completely
meaningless. What part of CLOS are you talking about ? For what kind of
application ? Slow compared to what ?
For instance, I've heard people claiming that CLOS *must* be slow, given
all the things it does dynamically (like computing the list of
applicable methods for each generic function call). But these people
forget (or just don't know) about memoization.
Then there are the clowns that pretend that dynamic dispatch is
"inherently slow" because you have to go through a vtable like in C++,
or a hashtable in some CLOS implementation. OK, but slow compared to
what ? If your generic dispatch is for finding a short function (e.g.
pixel access in an image), then performance might be an issue. But if
your method is going to take 10 seconds to execute, why would you care
about the dispatch time ?
So, okay, I grant you the right to say that CLOS is extremely slow
compared to, say, nop ;-)
--
Read the Jazz Blog !! http://jazzblog.didierverna.com
Didier Verna, ······@lrde.epita.fr, http://www.lrde.epita.fr/~didier
EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (1) 44 08 01 85
94276 Le Kremlin-Bic�tre, France Fax.+33 (1) 53 14 59 22 ······@xemacs.org
From: Edi Weitz
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <ulkfy5su2.fsf@agharta.de>
On Wed, 09 May 2007 09:53:08 +0200, Didier Verna <······@lrde.epita.fr> wrote:
> Jon Harrop <···@ffconsultancy.com> wrote:
>
>> I have no experience from CLOS but, from what I have heard, it is
>> extremely slow.
>
> Gosh. Now, even Lispers themselves contribute to propagate
> legends about Lisp slowness :-( We're in biiiig trouble I telya.
He's not a Lisper, in fact he knows next to nothing about Lisp. He's
a known spammer who tries to generate revenue for his business here.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Kent M Pitman
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <uy7jyt7ir.fsf@nhplace.com>
Didier Verna <······@lrde.epita.fr> writes:
> For instance, I've heard people claiming that CLOS *must* be slow, given
> all the things it does dynamically (like computing the list of
> applicable methods for each generic function call). But these people
> forget (or just don't know) about memoization.
I generally agree with your statement of pain about the way people suggest
slowness where it dosen't exist or exaggerate it heavily where it does.
Rather than comment on those remarks, which I think stand fine as you've
written them, let me point out where the personal point of pain is for me:
Dynamic inheritance is semantically different than static inheritance
(and, in my opinion, more correct). It doesn't implement the same
semantics. So, of course, it has different performance
characteristics.
There is a philosophical issue that's overlooked when one says things like
"C is faster at addition than Lisp" because C isn't doing Lisp addition
quickly nor is Lisp doing C's addition slowly. The two associate different
operations with the symbol +. I happen to like the definition of plus that
says when you give it a number, x, and 1, you get something bigger than x.
The feature of that, to me, is it's more like the math I do. C says the
operation is really to do what the machine does, and that I should use some
other secret operation if I want the math thing, or make sure all my numbers
are small, but that the most important thing is speed.
Likewise, CLOS does inheritance correctly. It can't be done truly correctly
with static analysis, because when you have an abstract class, you end
up dispatching only on the statically known methods for that type. When you
do oher calls to other methods, and they dispatch, and so on, it's not just
fast vs slow, it's what methods are actually gonig to get called. If calling
a method on a parent class means you are giving up the right to have child
class methods be called, then that's not just speed but correctness... Of
course, this choice point in the design space is just "defined" to be right,
and program errors are tolerated as "the programmer knew this was the semantics
and wrote the wrong program". But I don't think that's the only possible
analysis. By that analysis, we could rename + to be - and vice versa in CL,
and say "that's how we define the semantics and all program errors that result
from our choice of naming are due to the programmer".
The static/dynamic thing was not done as a way of saying, as a community,
"we're too lazy to do things up front where they belong". Rather, we as a
community have said "we want to first choose what we want to say, and when
the right time is to say it, and only after that is done will we see about
making that maximally efficient". That leads to different consequences,
which we have optimized well. If there are better optimizations possible for
those semantics, let's see an apples-to-apples comparison. But if we're
only going to talk apples-to-oranges, then the fight isn't fair from the
outset.
Didier Verna wrote:
> Jon Harrop <···@ffconsultancy.com> wrote:
>> I have no experience from CLOS but, from what I have heard, it is
>> extremely slow.
>
> Gosh. Now, even Lispers themselves contribute to propagate
> legends about Lisp slowness :-( We're in biiiig trouble I telya.
Well, if Lispers say something is slow then it must be really, really
slow. ;-)
> Seriously, this kind of comment is not only annoying, but completely
> meaningless. What part of CLOS are you talking about ? For what kind of
> application ? Slow compared to what ?
The impression I got from Lispers is that CLOS is very slow for pretty much
anything non-trivial.
> For instance, I've heard people claiming that CLOS *must* be slow, given
> all the things it does dynamically (like computing the list of
> applicable methods for each generic function call). But these people
> forget (or just don't know) about memoization.
I've heard a lot about it being extremely "flexible", which presumably means
in incurs an unusually large amount of run-time checking and dispatch.
> Then there are the clowns that pretend that dynamic dispatch is
> "inherently slow" because you have to go through a vtable like in C++,
> or a hashtable in some CLOS implementation. OK, but slow compared to
> what ?
The most common form of dispatch in other FPLs is pattern matching. Perhaps
it would be good to compare the performance of CLOS-based programs with
some pattern matching equivalents?
> If your generic dispatch is for finding a short function (e.g.
> pixel access in an image), then performance might be an issue. But if
> your method is going to take 10 seconds to execute, why would you care
> about the dispatch time?
Of course.
> So, okay, I grant you the right to say that CLOS is extremely slow
> compared to, say, nop ;-)
Presumably the symbolic simplifier example could be written using CLOS. If
anyone here is interested in quantitative evidence, maybe they could write
a CLOS implementation and benchmark it against the others?
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 8, 10:43 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>
> I have no experience from CLOS but, from what I have heard, it is extremely
> slow.
May I suggest that you either research something or gain experience in
it before making assertions?
@article{ queinnec97fast,
author = "Christian Queinnec",
title = "Fast and Compact Dispatching for Dynamic Object-Oriented
Languages",
journal = "Information Processing Letters",
volume = "64",
number = "6",
pages = "315-321",
year = "1997",
url = "citeseer.ist.psu.edu/queinnec97fast.html" }
@article{ dujardin98fast,
author = "Eric Dujardin and Eric Amiel and Eric Simon",
title = "Fast Algorithms for Compressed Multimethod Dispatch Table
Generation",
journal = "ACM Transactions on Programming Languages and Systems",
volume = "20",
number = "1",
month = "January",
publisher = "ACM Press",
pages = "116--165",
year = "1998",
url = "citeseer.ist.psu.edu/article/dujardin96fast.html" }
These will get you started. Optimization multi-method dispatch has
been a topic of research for many, many years, and there is much
published literature on it. An informed opinion is much more valuable
than hearsay.
On May 9, 6:43 am, Jon Harrop <····@ffconsultancy.com> wrote:
> I have no experience from CLOS but, from what I have heard, it is extremely
> slow.
Gosh. Well, I do have experience of CLOS, including more than one
largish (O(10^4) lines) application written making extensive use of
it, and I can tell you based on significant benchmarks of these things
(we were worried about the impact of things like user-defined method
combinations, and using fully-fledged CLOS instances where we could
have got away with structures) that what you've heard is wrong. Sorry
to let the facts get in the way.
Tim Bradshaw wrote:
> Gosh. Well, I do have experience of CLOS, including more than one
> largish (O(10^4) lines) application written making extensive use of
> it, and I can tell you based on significant benchmarks of these things
> (we were worried about the impact of things like user-defined method
> combinations, and using fully-fledged CLOS instances where we could
> have got away with structures) that what you've heard is wrong. Sorry
> to let the facts get in the way.
Well, it certainly seems that a lot of people are now saying that CLOS is
not slow.
Do you have any freely available code and benchmark results that I can
peruse?
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 11, 1:17 am, Jon Harrop <····@ffconsultancy.com> wrote:
> Well, it certainly seems that a lot of people are now saying that CLOS is
> not slow.
Exactly. It was slow in the late 80s but people have done a lot of
work on it since then.
>
> Do you have any freely available code and benchmark results that I can
> peruse?
No. Well, I have stuff on my website, but nothing that would be
meaningful as a benchmark of CLOS performance. The programs I was
talking about were commercial applications whose source isn't
available (and even if it was a lot of work would be required to do a
meaningful benchmark).
In fact, of course, meaningful benchmarks are pretty hard to do full
stop. Anyone can cook up something which spends all its time in a
tight inner loop with 99.993% L1 hit rate and demonstrate that x is
faster than y, but most real applications tend to have significantly
more complex characteristics.
Tim Bradshaw wrote:
> On May 11, 1:17 am, Jon Harrop <····@ffconsultancy.com> wrote:
>> Well, it certainly seems that a lot of people are now saying that CLOS is
>> not slow.
>
> Exactly. It was slow in the late 80s but people have done a lot of
> work on it since then.
Ok. I didn't realise the stuff I'd read was so out of date...
> In fact, of course, meaningful benchmarks are pretty hard to do full
> stop. Anyone can cook up something which spends all its time in a
> tight inner loop with 99.993% L1 hit rate and demonstrate that x is
> faster than y, but most real applications tend to have significantly
> more complex characteristics.
Sure.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On 2007-05-10 20:17:36 -0400, Jon Harrop <···@ffconsultancy.com> said:
> Do you have any freely available code and benchmark results that I can
> peruse?
some common lisp benchmarking code. the clos benchmarks are obviously
the relevant ones:
<http://www.chez.com/emarsden/downloads/cl-bench.tar.gz>
some graphed results:
<http://sbcl.boinkor.net/bench/>
A paper on cl-bench results in sbcl:
<http://www.doc.gold.ac.uk/~mas01cr/papers/benchmarks.ps>
Andy Freeman <······@earthlink.net> writes:
> On May 4, 3:14 pm, Jon Harrop <····@ffconsultancy.com> wrote:
> > Alan Crowe wrote:
> > > So a fair summary could be that ANSI Common Lisp does have
> > > built in pattern matching, but never fixed on a slick
> > > notation to distinguish between literals, types, and
> > > variables, leaving the programmer to make that choice and
> > > define some macros to implement it.
> >
> > Yes. I think decent pattern matching would be a welcome addition to the next
> > Lisp standard.
>
> Actually, Crowe (and Joswig) explained why pattern matching should not
> be part of the language. Summary: There isn't a single definition
> that handles all the relevant cases.
>
> For those who want hand-cuffs, other languages happily provide them.
It is easy to write a pattern matching function that takes a
pattern description and data structure and walks them in
synchrony to see if them match, building a table of bindings
as it goes.
It is easy to wrap this with macro: heh presto, a pattern
matching macro! So it is natural to leave pattern matching
to the application programmer, who can tune the details of
the pattern description and the matching process to be a
snug fit to his particular application.
The draw back that I'm aware of is that ones code is no
longer fully compiled. Even though the pattern matching
function is compiled, it is interpretting the pattern at run
time. Writing a pattern matching macro that actually
compiles the pattern matches to good quality code is a
different challenge that has so daunted me that I have not
attempted it.
I have three reasons for not attempting it.
1)Cowardice
2)It is not obvious what the right definition of pattern
matching is. Indeed it is hard to see how there could be a
right definition. I feel that a pattern matcher needs to
be parameterisable, which makes the challenge of compiling
the matches much harder.
3)Futamura projections: If you define the pattern matcher in
a limited subset of CL for which you have a partial
evaluator, you can compile the pattern matches by
partially evaluating the pattern matcher at compile time
with the known pattern and unkown data.
This looks like the right way to write a fully compiled,
parameterisable, pattern matching macro. If you
realise that the definition of pattern matching needs
modification for your particular application it is not a
disaster. One doesn't have to modify a dark and dangerous
pattern compiler. One merely tweaks the pattern
interpreter and lets the miracle of partial evaluation
turn it into compiled code.
But I don't understand partial evaluation, so I'm not
ready to attempt this.
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> But I don't understand partial evaluation, so I'm not
> ready to attempt this.
And you are with the vast majority of Lisp programmers who shun all such
tools in favour of compiling their pattern matches by hand every time.
Pattern matching is only widely adopted when it is provided with the
language. It is clearly very useful => it should be provided with the
language.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
On May 5, 7:16 pm, Jon Harrop <····@ffconsultancy.com> wrote:
>
> And you are with the vast majority of Lisp programmers who shun all such
> tools in favour of compiling their pattern matches by hand every time.
> Pattern matching is only widely adopted when it is provided with the
> language. It is clearly very useful => it should be provided with the
> language.
This is, of course, why so many mainstream languages have it built
in. Er, no, I mean, um.
In article <··············@cawtech.freeserve.co.uk>,
Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
...
> So a fair summary could be that ANSI Common Lisp does have
> built in pattern matching, but never fixed on a slick
> notation to distinguish between literals, types, and
> variables, leaving the programmer to make that choice and
> define some macros to implement it.
There is more than that. Some patterns might need backtracking,
for example - if you can match sequences.
Nice hack.
But if we are talking about mathematical simplification:
* what is the domain we are talking about?
what type of mathematics do we want to cover?
* how do we represent the mathematical expressions?
* what kind of simplification do we want to do?
* what kind of pattern language is needed in our chosen domain?
how expressive/powerful should our patterns and
the corresponding pattern matcher be?
* what is the complexity of our pattern matcher based
on the various pattern types and various input data?
* what kind of notation do we want to have for our patterns?
* how much flexibility do we want to have in respect to
changes of the domain (do we want the patterns
changeable at runtime?) use?
If we want to design a pattern language and a pattern
matcher, then we have to look at the domain: mathematics.
Otherwise we fall in the trap, that we just take what
the programming language offers and use that - without
knowing the limitations it has representing the domain.
That's a nice exercise, but it does not scale very
far.
That's the reason that computer algebra systems are
quite complex and using facilities that are designed
for representing and processing mathematical knowledge.
>
> Alan Crowe
> Edinburgh
> Scotland
--
http://lispm.dyndns.org
Rainer Joswig wrote:
> Otherwise we fall in the trap, that we just take what
> the programming language offers and use that - without
> knowing the limitations it has representing the domain.
> That's a nice exercise, but it does not scale very
> far.
It isn't perfect, but it is much better than car/cdr.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
Hi Alan,
You can do this in Qi as you probably know, with rather less space and
more clarity. Almost a direct transcription of your comments actually!
(define simplify
[* 0 X] -> 0
[* X 0] -> X
[* 1 X] -> X
[* X 1] -> X
[* X Y] -> (* X Y) where (and (number? X) (number? Y))
............. etc.
Qi also supports an internal S-expression syntax for metaprogramming
so you can also write this which is closer to your style ....
(define simplify
(cons * (cons 0 (cons X ( )))) -> 0
.................... etc
or even
(define simplify
(list * 0 X) -> 0
.............. etc.
You can get the resulting Lisp off very easiy using the dump command.
The program you've got in mind should port very easily without much Qi
open source so you are not dependent on the Qi package to run it.
If you want to see how to typecheck this sort of stuff see 'How To
Build A Reliable Algebra Program' (originally a thread on
comp.lang.lisp) now living at http://www.lambdassociates.org/studies/study07.htm.
best
Mark
On 4 May, 22:55, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
> Previously I've accepted the conventional wisdom that ANSI
> Common Lisp does NOT have pattern matching. It doesn't
> strike me as an important question; there are pattern
> matching macros out there if I need them.
>
> Recently I have noticed that combining typecase and
> destructing-bind does much the same thing as pattern
> matching. An aside in another thread suggested that CL is at
> a disadvantage compared to languages with pattern matching
> for algebraic manipulations such as differentiation and
> simplification. This goaded me into trying to write such
> code using the typecase/duct-tape/destructuring-bind technique
>
> Here is a differentiator (restricted to binary multiplication)
>
> (defun diff (form variable)
> (typecase form
> (symbol (if (eql form variable)
> 1
> 0))
> (number 0)
> ((cons (eql +) *)
> (cons '+ (mapcar (lambda(subform)
> (diff subform variable))
> (rest form))))
> ((cons (eql *)
> (cons *
> (cons * null)))
> (destructuring-bind (prod left right) form
> `(+ (* ,(diff left variable) ,right)
> (* ,(diff right variable) ,left))))
> ((cons (eql *)
> (cons *
> (cons * *)))
> (error "Sorry ~A makes the example too complicated." form))
>
> Trying it out on a cubic I've prepared earlier
>
> CL-USER> *cubic*
> (+ (* 3 (* X (* X X))) (* 5 (* X X)) (* 7 X) 11)
>
> produces the usual sorry mess
>
> CL-USER> (diff *cubic* 'x)
> (+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
> (+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
> (+ (* 0 X) (* 1 7))
> 0)
>
> so I started hacking together a simplifier. I realise that
> matching patterns in a hacky way doesn't have a future, one
> needs cannonical forms and stuff for a real algebra
> system. Nevertheless my goal was to see how well
> typecase/duct-tape/destruction-bind works as a pattern
> matching technique.
>
> I found that hacking in extra patterns to make the
> simplification work was really rather addictive and I kept
> going until my test form could be fully simplified by
> several applications of simplify
>
> (defun simplify (form)
> (typecase form
> ((cons (eql *)
> (cons (eql 0)
> (cons * null)))
> ;; (* 0 x) => 0
> 0)
> ((cons (eql *)
> (cons *
> (cons (eql 0) null)))
> ;; (* x 0) => 0
> 0)
> ((cons (eql *)
> (cons (eql 1) *))
> ;; (* 1 x) => x
> (simplify (third form)))
> ((cons (eql *)
> (cons *
> (cons (eql 1) null)))
> ;; (* x 1) => x
> (simplify (second form)))
> ((cons (eql *)
> (cons number
> (cons number null)))
> ;; (* n1 n2) => n3
> (* (second form) (third form)))
> ((cons (eql *)
> (cons number
> (cons (cons (eql *)
> (cons number
> (cons * nul)))
> null)))
> ;; (* n1 (* n2 x)) => (* n3 x)
> (destructuring-bind (op1 n (op2 m x)) form
> (list '* (* n m) (simplify x))))
> ((cons (eql *)
> (cons (cons (eql *)
> (cons number
> (cons * null)))
> (cons number null)))
> (destructuring-bind (op1 (op2 n x) m) form
> (list '* (* n m) (simplify x))))
> ((cons (eql *)
> (cons (cons (eql *)
> (cons number
> (cons * null)))
> (cons * null)))
> ;; (* (* n x) y) => (* n (* x y))
> (destructuring-bind (op1 (op2 n x) y) form
> `(* ,n (* ,(simplify x) ,(simplify y)))))
> ((cons (eql *) *)
> (destructuring-bind (op left right) form
> (list op
> (simplify left)
> (simplify right))))
> ((cons (eql +)
> (cons (eql 0)
> (cons * null)))
> ;; (+ 0 x) => x
> (third form))
> ((cons (eql +)
> (cons *
> (cons (eql 0) null)))
> ;; (+ x 0) => x
> (second form))
> ((cons (eql +)
> (cons *
> (cons (cons (eql *)
> (cons number
> (cons * null)))
> null)))
> ;; (+ x (* n x)) => (* n+1 x)
> ;; (+ x (* n y)) => (+ x (* n y))
> (destructuring-bind (*1 x (*2 n y)) form
> (let ((x (simplify x))
> (y (simplify y)))
> (if (equal x y)
> (list '* (+ n 1) x)
> `(+ ,x (* ,n ,y))))))
> ((cons (eql +)
> (cons *
> (cons * null)))
> ;; (+ x x) => (* 2 x)
> ;; (+ x y) => (+ x y)
> (destructuring-bind (x y)
> (mapcar #'simplify (rest form))
> (if (equal x y)
> `(* 2 ,x)
> (list '+ x y))))
> ((cons (eql +)
> (cons (eql 0)
> (cons * (cons * null))))
> (destructuring-bind (op x y z) form
> (list op (simplify y) (simplify z))))
> ((cons (eql +)
> (cons *
> (cons (eql 0)
> (cons * null))))
> ;; (+ x 0 y) => (+ x y)
> (destructuring-bind (op x y z) form
> (list op (simplify x) (simplify z))))
> ((cons (eql +)
> (cons *
> (cons *
> (cons (eql 0) null))))
> (destructuring-bind (op x y z) form
> (list op (simplify x) (simplify y))))
> ((cons (eql +)
> (cons number
> (cons number
> (cons * null))))
> (destructuring-bind (op x y z) form
> (list op (+ x y) (simplify z))))
> ((cons (eql +)
> (cons *
> (cons *
> (cons number
> (cons number null)))))
> (destructuring-bind (op x y n m) form
> (list op (simplify x) (simplify y)(+ n m))))
> ((cons (eql +) *)
> (cons '+ (mapcar #'simplify (rest form))))
> (t form)))
>
> Invoking it repeatedly
>
> CL-USER> (diff *cubic* 'x)
> (+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
> (+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
> (+ (* 0 X) (* 1 7))
> 0)
>
> CL-USER> (simplify *)
> (+ (+ 0 (* (+ (* X X) (* (* 2 X) X)) 3)) (+ 0 (* (* 2 X) 5)) (+ 0 (* 1 7)) 0)
>
> CL-USER> (simplify *)
> (+ (* (+ (* X X) (* (* 2 X) X)) 3) (* (* 2 X) 5) (* 1 7) 0)
>
> CL-USER> (simplify *)
> (+ (* (+ (* X X) (* 2 (* X X))) 3) (* 10 X) 7 0)
>
> CL-USER> (simplify *)
> (+ (* (* 3 (* X X)) 3) (* 10 X) 7)
>
> CL-USER> (simplify *)
> (+ (* 9 (* X X)) (* 10 X) 7)
>
> 3 2 2
> 3x + 5x + 7x + 11 => 9x + 10x + 7
>
> so that is a success of sorts.
>
> I'm not sure what to make of this. The
> typecase/duct-tape/destruction-bind technique clearly sucks,
> and yet it is good enough to be addictive and fun :-) If a
> program that I intended to distribute needed to do a modest
> amount of pattern matching I would be very tempted to make
> do with it and save myself a dependency on an external
> package
>
> There is a reason that typecase cannot bind variables. The
> type (cons symbol number) cannot do
>
> (let ((symbol (car x))
> (number (cdr x)))
> ...
>
> because it is already doing
>
> (and (typep (car x) 'symbol)
> (typep (cdr x) 'number))
>
> The names are names of types. Since deftype lets symbols
> name types, typecase cannot know that a symbol is supposed
> to be a variable name and not a name for a type.
>
> In my code I make use of this type matching. It is useful
> and wins something back from the clunkiness of cons and eql.
>
> The language design issue is that you cannot just write a
> pattern
>
> (a b c)
>
> perhaps a is a literal, b a type and c a variable and I
> would render it as
>
> (typecase form
> ((cons (eql a) (cons b (cons * null)))
> (destructuring-bind (x1 x2 c) form
> (declare (ignore x1 x2))
> ...
>
> So a fair summary could be that ANSI Common Lisp does have
> built in pattern matching, but never fixed on a slick
> notation to distinguish between literals, types, and
> variables, leaving the programmer to make that choice and
> define some macros to implement it.
>
> Alan Crowe
> Edinburgh
> Scotland
Oops - second line should be
[* X 0] -> 0
Never post before breakfast!
Mark
On 5 May, 09:28, Mark Tarver <··········@ukonline.co.uk> wrote:
> Hi Alan,
>
> You can do this in Qi as you probably know, with rather less space and
> more clarity. Almost a direct transcription of your comments actually!
>
> (define simplify
> [* 0 X] -> 0
> [* X 0] -> X
> [* 1 X] -> X
> [* X 1] -> X
> [* X Y] -> (* X Y) where (and (number? X) (number? Y))
> ............. etc.
>
> Qi also supports an internal S-expression syntax for metaprogramming
> so you can also write this which is closer to your style ....
>
> (define simplify
> (cons * (cons 0 (cons X ( )))) -> 0
> .................... etc
>
> or even
>
> (define simplify
> (list * 0 X) -> 0
> .............. etc.
>
> You can get the resulting Lisp off very easiy using the dump command.
> The program you've got in mind should port very easily without much Qi
> open source so you are not dependent on the Qi package to run it.
>
> If you want to see how to typecheck this sort of stuff see 'How To
> Build A Reliable Algebra Program' (originally a thread on
> comp.lang.lisp) now living athttp://www.lambdassociates.org/studies/study07.htm.
>
> best
>
> Mark
>
> On 4 May, 22:55, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
>
>
>
> > Previously I've accepted the conventional wisdom that ANSI
> > Common Lisp does NOT have pattern matching. It doesn't
> > strike me as an important question; there are pattern
> > matching macros out there if I need them.
>
> > Recently I have noticed that combining typecase and
> > destructing-bind does much the same thing as pattern
> > matching. An aside in another thread suggested that CL is at
> > a disadvantage compared to languages with pattern matching
> > for algebraic manipulations such as differentiation and
> > simplification. This goaded me into trying to write such
> > code using the typecase/duct-tape/destructuring-bind technique
>
> > Here is a differentiator (restricted to binary multiplication)
>
> > (defun diff (form variable)
> > (typecase form
> > (symbol (if (eql form variable)
> > 1
> > 0))
> > (number 0)
> > ((cons (eql +) *)
> > (cons '+ (mapcar (lambda(subform)
> > (diff subform variable))
> > (rest form))))
> > ((cons (eql *)
> > (cons *
> > (cons * null)))
> > (destructuring-bind (prod left right) form
> > `(+ (* ,(diff left variable) ,right)
> > (* ,(diff right variable) ,left))))
> > ((cons (eql *)
> > (cons *
> > (cons * *)))
> > (error "Sorry ~A makes the example too complicated." form))
>
> > Trying it out on a cubic I've prepared earlier
>
> > CL-USER> *cubic*
> > (+ (* 3 (* X (* X X))) (* 5 (* X X)) (* 7 X) 11)
>
> > produces the usual sorry mess
>
> > CL-USER> (diff *cubic* 'x)
> > (+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
> > (+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
> > (+ (* 0 X) (* 1 7))
> > 0)
>
> > so I started hacking together a simplifier. I realise that
> > matching patterns in a hacky way doesn't have a future, one
> > needs cannonical forms and stuff for a real algebra
> > system. Nevertheless my goal was to see how well
> > typecase/duct-tape/destruction-bind works as a pattern
> > matching technique.
>
> > I found that hacking in extra patterns to make the
> > simplification work was really rather addictive and I kept
> > going until my test form could be fully simplified by
> > several applications of simplify
>
> > (defun simplify (form)
> > (typecase form
> > ((cons (eql *)
> > (cons (eql 0)
> > (cons * null)))
> > ;; (* 0 x) => 0
> > 0)
> > ((cons (eql *)
> > (cons *
> > (cons (eql 0) null)))
> > ;; (* x 0) => 0
> > 0)
> > ((cons (eql *)
> > (cons (eql 1) *))
> > ;; (* 1 x) => x
> > (simplify (third form)))
> > ((cons (eql *)
> > (cons *
> > (cons (eql 1) null)))
> > ;; (* x 1) => x
> > (simplify (second form)))
> > ((cons (eql *)
> > (cons number
> > (cons number null)))
> > ;; (* n1 n2) => n3
> > (* (second form) (third form)))
> > ((cons (eql *)
> > (cons number
> > (cons (cons (eql *)
> > (cons number
> > (cons * nul)))
> > null)))
> > ;; (* n1 (* n2 x)) => (* n3 x)
> > (destructuring-bind (op1 n (op2 m x)) form
> > (list '* (* n m) (simplify x))))
> > ((cons (eql *)
> > (cons (cons (eql *)
> > (cons number
> > (cons * null)))
> > (cons number null)))
> > (destructuring-bind (op1 (op2 n x) m) form
> > (list '* (* n m) (simplify x))))
> > ((cons (eql *)
> > (cons (cons (eql *)
> > (cons number
> > (cons * null)))
> > (cons * null)))
> > ;; (* (* n x) y) => (* n (* x y))
> > (destructuring-bind (op1 (op2 n x) y) form
> > `(* ,n (* ,(simplify x) ,(simplify y)))))
> > ((cons (eql *) *)
> > (destructuring-bind (op left right) form
> > (list op
> > (simplify left)
> > (simplify right))))
> > ((cons (eql +)
> > (cons (eql 0)
> > (cons * null)))
> > ;; (+ 0 x) => x
> > (third form))
> > ((cons (eql +)
> > (cons *
> > (cons (eql 0) null)))
> > ;; (+ x 0) => x
> > (second form))
> > ((cons (eql +)
> > (cons *
> > (cons (cons (eql *)
> > (cons number
> > (cons * null)))
> > null)))
> > ;; (+ x (* n x)) => (* n+1 x)
> > ;; (+ x (* n y)) => (+ x (* n y))
> > (destructuring-bind (*1 x (*2 n y)) form
> > (let ((x (simplify x))
> > (y (simplify y)))
> > (if (equal x y)
> > (list '* (+ n 1) x)
> > `(+ ,x (* ,n ,y))))))
> > ((cons (eql +)
> > (cons *
> > (cons * null)))
> > ;; (+ x x) => (* 2 x)
> > ;; (+ x y) => (+ x y)
> > (destructuring-bind (x y)
> > (mapcar #'simplify (rest form))
> > (if (equal x y)
> > `(* 2 ,x)
> > (list '+ x y))))
> > ((cons (eql +)
> > (cons (eql 0)
> > (cons * (cons * null))))
> > (destructuring-bind (op x y z) form
> > (list op (simplify y) (simplify z))))
> > ((cons (eql +)
> > (cons *
> > (cons (eql 0)
> > (cons * null))))
> > ;; (+ x 0 y) => (+ x y)
> > (destructuring-bind (op x y z) form
> > (list op (simplify x) (simplify z))))
> > ((cons (eql +)
> > (cons *
> > (cons *
> > (cons (eql 0) null))))
> > (destructuring-bind (op x y z) form
> > (list op (simplify x) (simplify y))))
> > ((cons (eql +)
> > (cons number
> > (cons number
> > (cons * null))))
> > (destructuring-bind (op x y z) form
> > (list op (+ x y) (simplify z))))
> > ((cons (eql +)
> > (cons *
> > (cons *
> > (cons number
> > (cons number null)))))
> > (destructuring-bind (op x y n m) form
> > (list op (simplify x) (simplify y)(+ n m))))
> > ((cons (eql +) *)
> > (cons '+ (mapcar #'simplify (rest form))))
> > (t form)))
>
> > Invoking it repeatedly
>
> > CL-USER> (diff *cubic* 'x)
> > (+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
> > (+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
> > (+ (* 0 X) (* 1 7))
> > 0)
>
> > CL-USER> (simplify *)
> > (+ (+ 0 (* (+ (* X X) (* (* 2 X) X)) 3)) (+ 0 (* (* 2 X) 5)) (+ 0 (* 1 7)) 0)
>
> > CL-USER> (simplify *)
> > (+ (* (+ (* X X) (* (* 2 X) X)) 3) (* (* 2 X) 5) (* 1 7) 0)
>
> > CL-USER> (simplify *)
> > (+ (* (+ (* X X) (* 2 (* X X))) 3) (* 10 X) 7 0)
>
> > CL-USER> (simplify *)
> > (+ (* (* 3 (* X X)) 3) (* 10 X) 7)
>
> > CL-USER> (simplify *)
> > (+ (* 9 (* X X)) (* 10 X) 7)
>
> > 3 2 2
> > 3x + 5x + 7x + 11 => 9x + 10x + 7
>
> > so that is a success of sorts.
>
> > I'm not sure what to make of this. The
> > typecase/duct-tape/destruction-bind technique clearly sucks,
> > and yet it is good enough to be addictive and fun :-) If a
> > program that I intended to distribute needed to do a modest
> > amount of pattern matching I would be very tempted to make
> > do with it and save myself a dependency on an external
> > package
>
> > There is a reason that typecase cannot bind variables. The
> > type (cons symbol number) cannot do
>
> > (let ((symbol (car x))
> > (number (cdr x)))
> > ...
>
> > because it is already doing
>
> > (and (typep (car x) 'symbol)
> > (typep (cdr x) 'number))
>
> > The names are names of types. Since deftype lets symbols
> > name types, typecase cannot know that a symbol is supposed
> > to be a variable name and not a name for a type.
>
> > In my code I make use of this type matching. It is useful
> > and wins something back from the clunkiness of cons and eql.
>
> > The language design issue is that you cannot just write a
> > pattern
>
> > (a b c)
>
> > perhaps a is a literal, b a type and c a variable and I
> > would render it as
>
> > (typecase form
> > ((cons (eql a) (cons b (cons * null)))
> > (destructuring-bind (x1 x2 c) form
> > (declare (ignore x1 x2))
> > ...
>
> > So a fair summary could be that ANSI Common Lisp does have
> > built in pattern matching, but never fixed on a slick
> > notation to distinguish between literals, types, and
> > variables, leaving the programmer to make that choice and
> > define some macros to implement it.
>
> > Alan Crowe
> > Edinburgh
> > Scotland- Hide quoted text -
>
> - Show quoted text -
Mark Tarver wrote:
> You can do this in Qi as you probably know, with rather less space and
> more clarity. Almost a direct transcription of your comments actually!
>
> (define simplify
> [* 0 X] -> 0
> [* X 0] -> X
> [* 1 X] -> X
> [* X 1] -> X
> [* X Y] -> (* X Y) where (and (number? X) (number? Y))
> ............. etc.
This is exactly what a language should provide, IMHO.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
From: Lars Brinkhoff
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <85zm4jvgjw.fsf@junk.nocrew.org>
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> (defun diff (form variable)
> (typecase form
...
> ((cons (eql *)
> (cons *
> (cons * null)))
...
For these usage patterns, I would usually like to define something like
(deftype list-of (&rest args)
(if (null args)
'null
`(cons ,(first args) (list-of ,@(rest args)))))
Lars Brinkhoff <·········@nocrew.org> writes:
> Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> > (defun diff (form variable)
> > (typecase form
> ...
> > ((cons (eql *)
> > (cons *
> > (cons * null)))
> ...
>
> For these usage patterns, I would usually like to define something like
>
> (deftype list-of (&rest args)
> (if (null args)
> 'null
> `(cons ,(first args) (list-of ,@(rest args)))))
Thank you for posting that, I had completely forgotten about
deftype but it makes a huge difference here.
Your observation shows that my code is wrong.
The code was supposed to be answering the question "how
pattern-matchey is ANSI Common Lisp?". deftype is in the
standard and the code fails to make appropriate use of it,
so the code understates how pattern-matchey CL is.
I've tried redoing the code using list-of. I soon noticed
1)Literal numbers 0 and 1 are common in the patterns. They
should be recognised and wrapped for example 561 => (eql 561)
2)The patterns contain symbols both as literals and names of
types. It would be helpful to rewrite (quote foo) as (eql
foo) so that a literal symbol could be typed in using the
built-in quote read-macro 'foo => (eql foo)
3)Some patterns end (cons type null) others end
(cons type *) depending on whether the pattern fixes the
length of the list or allows it to continue. It would be
nice to enter a list exactly three long as (tuple a b c)
and one three or longer as (tuple a b c etc)
So I came up with
(deftype tuple (&rest types)
(if (endp types)
'null
(typecase (first types)
(number
`(cons (eql ,(first types))
(tuple ,@(rest types))))
( ;; ('quote literal)
(cons (eql quote) (cons * null))
`(cons (eql ,(second (first types)))
(tuple ,@(rest types))))
((eql etc) 'list)
(t `(cons ,(first types) (tuple ,@(rest types)))))))
;; as before
(defparameter *cubic*
'(+ (* 3 (* x (* x x)))
(* 5 (* x x))
(* 7 x)
11))
;; tidy
(defun diff (form variable)
(typecase form
(symbol (if (eql form variable)
1
0))
(number 0)
((tuple '+ etc)
(cons '+ (mapcar (lambda(subform)
(diff subform variable))
(rest form))))
((tuple '* * *)
(destructuring-bind (prod left right) form
`(+ (* ,(diff left variable) ,right)
(* ,(diff right variable) ,left))))
((tuple '* * * etc)
(error "Sorry ~A makes the example too complicated." form))
(t (error "Differentiating ~A is not implemented yet." form))))
;; much improved
(defun simplify (form)
(typecase form
((tuple '* 0 *) 0)
((tuple '* * 0) 0)
((tuple '* 1 *) (simplify (third form)))
((tuple '* * 1) (simplify (second form)))
((tuple '* number number) (* (second form) (third form)))
((tuple '* number (tuple '* number *)
(destructuring-bind (op1 n (op2 m x)) form
(list '* (* n m) (simplify x)))))
((tuple '* (tuple '* number *) number)
(destructuring-bind (op1 (op2 n x) m) form
(list '* (* n m) (simplify x))))
((tuple '* (tuple '* number *) *)
;; raise buried number
(destructuring-bind (op1 (op2 n x) y) form
`(* ,n (* ,(simplify x) ,(simplify y)))))
((tuple '* * *)
(destructuring-bind (op left right) form
(list op
(simplify left)
(simplify right))))
((tuple '* etc)(error "~a not binary" form))
((tuple '+ 0 *) (simplify (third form)))
((tuple '+ * 0) (simplify (second form)))
((tuple '+ * (tuple '* number *))
;; (+ x (* n x)) => (* n+1 x)
;; (+ x (* n y)) => (+ x (* n y))
(destructuring-bind (*1 x (*2 n y)) form
(let ((x (simplify x))
(y (simplify y)))
(if (equal x y)
(list '* (+ n 1) x)
`(+ ,x (* ,n ,y))))))
((tuple '+ * *)
;; (+ x x) => (* 2 x)
;; (+ x y) => (+ x y)
(destructuring-bind (x y)
(mapcar #'simplify (rest form))
(if (equal x y)
`(* 2 ,x)
(list '+ x y))))
((tuple '+ 0 * *)
(destructuring-bind (op x y z) form
(list op (simplify y) (simplify z))))
((tuple '+ * 0 *)
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify z))))
((tuple '+ * * 0)
(destructuring-bind (op x y z) form
(list op (simplify x) (simplify y))))
((tuple '+ number number *)
(destructuring-bind (op x y z) form
(list op (+ x y) (simplify z))))
((tuple '+ * * number number)
(destructuring-bind (op x y n m) form
(list op (simplify x) (simplify y)(+ n m))))
((tuple '+ etc)
(cons '+ (mapcar #'simplify (rest form))))
(t form)))
CL-USER> (let ((form (diff *cubic* 'x)))
(dotimes (i 4 form)
(print form)
(setf form (simplify form))))
(+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
(+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
(+ (* 0 X) (* 1 7))
0)
(+ (+ 0 (* (+ (* X X) (* (* 2 X) X)) 3)) (+ 0 (* (* 2 X) 5)) (+ 0 (* 1 7)) 0)
(+ (* (+ (* X X) (* 2 (* X X))) 3) (* 10 X) 7 0)
(+ (* (* 3 (* X X)) 3) (* 10 X) 7)
(+ (* 9 (* X X)) (* 10 X) 7)
The simplifier is now quite readable. Which is embarrassing
because you can see how it works which exposes the flaws in
the design. Now I understand why it is so important to
obfuscate ones code :-) The code is far from complete and
with the approach taken completing it will make it bloat
horribly.
One seems to get useful basic pattern matching out of
deftype/typecase/destructuring-bind and I'm grateful to Lars
for pointing out deftype.
Alan Crowe
Edinburgh
Scotland
On May 6, 11:22 am, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
> The simplifier is now quite readable. Which is embarrassing
> because you can see how it works which exposes the flaws in
> the design. Now I understand why it is so important to
> obfuscate ones code :-) The code is far from complete and
> with the approach taken completing it will make it bloat
> horribly.
It's ok, the example does convey how to do pattern matching -- writing
a full algebraic simplifier is a Hard Problem. (Seems like in order
to keep the code bloat down, you'll want something more like a theorem
prover...)
mfh
From: Lars Brinkhoff
Subject: Re: Does ANSI Common Lisp have pattern matching?
Date:
Message-ID: <85tzuotsuw.fsf@junk.nocrew.org>
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> Thank you for posting that, I had completely forgotten about deftype
> but it makes a huge difference here.
Good. I didn't know if I just pointed out something obvious or irrelevant.
> (deftype tuple (&rest types)
> (if (endp types)
> 'null
> (typecase (first types)
> (number
> `(cons (eql ,(first types))
> (tuple ,@(rest types))))
> ( ;; ('quote literal)
> (cons (eql quote) (cons * null))
> `(cons (eql ,(second (first types)))
> (tuple ,@(rest types))))
> ((eql etc) 'list)
> (t `(cons ,(first types) (tuple ,@(rest types)))))))
That's very handy for your pattern matching example. I went in
another direction and came up with something to allow saying things
like
(list-of (eql defun) (or symbol (list-of (eql setf) symbol)) list . list)
[which would benefit from your quote notation] or
(list-of :element-type number :length 3)
Hello
I have been absent from here for a while :) but the occasion for a
shameless plug is too tasty...
One candidate for your pattern matching needs could be
http://common-lisp.net/project/cl-unification
It may be buggy and a little weird, but, to the best of my knowledge,
it's still the only unifier (not only pattern matching!) that can
unify two arrays of CLOS instances. It also has a bit of syntactic
quirkiness (probably the buggiest part) which may go in the direction
of designing a pattern language extension for Commn Lisp.
Ciao
Marco
On May 4, 11:55 pm, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
> Previously I've accepted the conventional wisdom that ANSI
> Common Lisp does NOT have pattern matching. It doesn't
> strike me as an important question; there are pattern
> matching macros out there if I need them.
>
> Recently I have noticed that combining typecase and
> destructing-bind does much the same thing as pattern
> matching. An aside in another thread suggested that CL is at
> a disadvantage compared to languages with pattern matching
> for algebraic manipulations such as differentiation and
> simplification. This goaded me into trying to write such
> code using the typecase/duct-tape/destructuring-bind technique
>
> Here is a differentiator (restricted to binary multiplication)
>
> (defun diff (form variable)
> (typecase form
> (symbol (if (eql form variable)
> 1
> 0))
> (number 0)
> ((cons (eql +) *)
> (cons '+ (mapcar (lambda(subform)
> (diff subform variable))
> (rest form))))
> ((cons (eql *)
> (cons *
> (cons * null)))
> (destructuring-bind (prod left right) form
> `(+ (* ,(diff left variable) ,right)
> (* ,(diff right variable) ,left))))
> ((cons (eql *)
> (cons *
> (cons * *)))
> (error "Sorry ~A makes the example too complicated." form))
>
> Trying it out on a cubic I've prepared earlier
>
> CL-USER> *cubic*
> (+ (* 3 (* X (* X X))) (* 5 (* X X)) (* 7 X) 11)
>
> produces the usual sorry mess
>
> CL-USER> (diff *cubic* 'x)
> (+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
> (+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
> (+ (* 0 X) (* 1 7))
> 0)
>
> so I started hacking together a simplifier. I realise that
> matching patterns in a hacky way doesn't have a future, one
> needs cannonical forms and stuff for a real algebra
> system. Nevertheless my goal was to see how well
> typecase/duct-tape/destruction-bind works as a pattern
> matching technique.
>
> I found that hacking in extra patterns to make the
> simplification work was really rather addictive and I kept
> going until my test form could be fully simplified by
> several applications of simplify
>
> (defun simplify (form)
> (typecase form
> ((cons (eql *)
> (cons (eql 0)
> (cons * null)))
> ;; (* 0 x) => 0
> 0)
> ((cons (eql *)
> (cons *
> (cons (eql 0) null)))
> ;; (* x 0) => 0
> 0)
> ((cons (eql *)
> (cons (eql 1) *))
> ;; (* 1 x) => x
> (simplify (third form)))
> ((cons (eql *)
> (cons *
> (cons (eql 1) null)))
> ;; (* x 1) => x
> (simplify (second form)))
> ((cons (eql *)
> (cons number
> (cons number null)))
> ;; (* n1 n2) => n3
> (* (second form) (third form)))
> ((cons (eql *)
> (cons number
> (cons (cons (eql *)
> (cons number
> (cons * nul)))
> null)))
> ;; (* n1 (* n2 x)) => (* n3 x)
> (destructuring-bind (op1 n (op2 m x)) form
> (list '* (* n m) (simplify x))))
> ((cons (eql *)
> (cons (cons (eql *)
> (cons number
> (cons * null)))
> (cons number null)))
> (destructuring-bind (op1 (op2 n x) m) form
> (list '* (* n m) (simplify x))))
> ((cons (eql *)
> (cons (cons (eql *)
> (cons number
> (cons * null)))
> (cons * null)))
> ;; (* (* n x) y) => (* n (* x y))
> (destructuring-bind (op1 (op2 n x) y) form
> `(* ,n (* ,(simplify x) ,(simplify y)))))
> ((cons (eql *) *)
> (destructuring-bind (op left right) form
> (list op
> (simplify left)
> (simplify right))))
> ((cons (eql +)
> (cons (eql 0)
> (cons * null)))
> ;; (+ 0 x) => x
> (third form))
> ((cons (eql +)
> (cons *
> (cons (eql 0) null)))
> ;; (+ x 0) => x
> (second form))
> ((cons (eql +)
> (cons *
> (cons (cons (eql *)
> (cons number
> (cons * null)))
> null)))
> ;; (+ x (* n x)) => (* n+1 x)
> ;; (+ x (* n y)) => (+ x (* n y))
> (destructuring-bind (*1 x (*2 n y)) form
> (let ((x (simplify x))
> (y (simplify y)))
> (if (equal x y)
> (list '* (+ n 1) x)
> `(+ ,x (* ,n ,y))))))
> ((cons (eql +)
> (cons *
> (cons * null)))
> ;; (+ x x) => (* 2 x)
> ;; (+ x y) => (+ x y)
> (destructuring-bind (x y)
> (mapcar #'simplify (rest form))
> (if (equal x y)
> `(* 2 ,x)
> (list '+ x y))))
> ((cons (eql +)
> (cons (eql 0)
> (cons * (cons * null))))
> (destructuring-bind (op x y z) form
> (list op (simplify y) (simplify z))))
> ((cons (eql +)
> (cons *
> (cons (eql 0)
> (cons * null))))
> ;; (+ x 0 y) => (+ x y)
> (destructuring-bind (op x y z) form
> (list op (simplify x) (simplify z))))
> ((cons (eql +)
> (cons *
> (cons *
> (cons (eql 0) null))))
> (destructuring-bind (op x y z) form
> (list op (simplify x) (simplify y))))
> ((cons (eql +)
> (cons number
> (cons number
> (cons * null))))
> (destructuring-bind (op x y z) form
> (list op (+ x y) (simplify z))))
> ((cons (eql +)
> (cons *
> (cons *
> (cons number
> (cons number null)))))
> (destructuring-bind (op x y n m) form
> (list op (simplify x) (simplify y)(+ n m))))
> ((cons (eql +) *)
> (cons '+ (mapcar #'simplify (rest form))))
> (t form)))
>
> Invoking it repeatedly
>
> CL-USER> (diff *cubic* 'x)
> (+ (+ (* 0 (* X (* X X))) (* (+ (* 1 (* X X)) (* (+ (* 1 X) (* 1 X)) X)) 3))
> (+ (* 0 (* X X)) (* (+ (* 1 X) (* 1 X)) 5))
> (+ (* 0 X) (* 1 7))
> 0)
>
> CL-USER> (simplify *)
> (+ (+ 0 (* (+ (* X X) (* (* 2 X) X)) 3)) (+ 0 (* (* 2 X) 5)) (+ 0 (* 1 7)) 0)
>
> CL-USER> (simplify *)
> (+ (* (+ (* X X) (* (* 2 X) X)) 3) (* (* 2 X) 5) (* 1 7) 0)
>
> CL-USER> (simplify *)
> (+ (* (+ (* X X) (* 2 (* X X))) 3) (* 10 X) 7 0)
>
> CL-USER> (simplify *)
> (+ (* (* 3 (* X X)) 3) (* 10 X) 7)
>
> CL-USER> (simplify *)
> (+ (* 9 (* X X)) (* 10 X) 7)
>
> 3 2 2
> 3x + 5x + 7x + 11 => 9x + 10x + 7
>
> so that is a success of sorts.
>
> I'm not sure what to make of this. The
> typecase/duct-tape/destruction-bind technique clearly sucks,
> and yet it is good enough to be addictive and fun :-) If a
> program that I intended to distribute needed to do a modest
> amount of pattern matching I would be very tempted to make
> do with it and save myself a dependency on an external
> package
>
> There is a reason that typecase cannot bind variables. The
> type (cons symbol number) cannot do
>
> (let ((symbol (car x))
> (number (cdr x)))
> ...
>
> because it is already doing
>
> (and (typep (car x) 'symbol)
> (typep (cdr x) 'number))
>
> The names are names of types. Since deftype lets symbols
> name types, typecase cannot know that a symbol is supposed
> to be a variable name and not a name for a type.
>
> In my code I make use of this type matching. It is useful
> and wins something back from the clunkiness of cons and eql.
>
> The language design issue is that you cannot just write a
> pattern
>
> (a b c)
>
> perhaps a is a literal, b a type and c a variable and I
> would render it as
>
> (typecase form
> ((cons (eql a) (cons b (cons * null)))
> (destructuring-bind (x1 x2 c) form
> (declare (ignore x1 x2))
> ...
>
> So a fair summary could be that ANSI Common Lisp does have
> built in pattern matching, but never fixed on a slick
> notation to distinguish between literals, types, and
> variables, leaving the programmer to make that choice and
> define some macros to implement it.
>
> Alan Crowe
> Edinburgh
> Scotland
Marco Antoniotti wrote:
> http://common-lisp.net/project/cl-unification
>
> It may be buggy and a little weird, but, to the best of my knowledge,
> it's still the only unifier (not only pattern matching!) that can
> unify two arrays of CLOS instances. It also has a bit of syntactic
> quirkiness (probably the buggiest part) which may go in the direction
> of designing a pattern language extension for Commn Lisp.
Indeed, this was by far the best of the Lisp pattern matchers that I've
played with.
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet