pattern-matching in LISP?

10 views
Skip to first unread message

Chris Schumacher

unread,
Apr 28, 2007, 6:15:56 PM4/28/07
to
I noticed that in the functional language ML there is a way to break a
function's input into various forms in the function header.
For instance:
split(a::b::c) (where :: is ML's equivalent of cons)
This also allows an interesting kind of function overloading where you can
contain several function definitions in a single declaration, each keyed by
the format of the input.
I attempted to do something similar in LISP, using:
defun ( split (cons A B) )

But it didn't appear to work. Does LISP have pattern-matching capabilities
as well?
I'd be sad if it didn't, because I like LISP a lot more than ML. :)


-==Kensu==-

Pascal Costanza

unread,
Apr 28, 2007, 9:08:49 PM4/28/07
to
Chris Schumacher wrote:
> I noticed that in the functional language ML there is a way to break a
> function's input into various forms in the function header.
> For instance:
> split(a::b::c) (where :: is ML's equivalent of cons)
> This also allows an interesting kind of function overloading where you can
> contain several function definitions in a single declaration, each keyed by
> the format of the input.
> I attempted to do something similar in LISP, using:
> defun ( split (cons A B) )
>
> But it didn't appear to work.

Your code isn't even close to the s-expression syntax of Lisp, so it's
no wonder that it doesn't work. That's not related to pattern matching.

There are pattern matching libraries for Lisp. (That's the nice thing of
a programmable programming language - you can just extend it without the
need to mess with the internals of an implementation.)

Neither Common Lisp nor Scheme, the two major Lisp dialects, have
anything built in in that regard.

Common Lisp has a low-level destructuring-bind form, but that's used
when you already know what the structure of your data is. There have
been suggestions for building a destructuring-case on top of it, but
that's probably not the best way to do it.

In Common Lisp, you would probably try to arrange your code differently
and take advantage of generic functions. That also gives you the
advantage of better potential to dynamically evolve your code without
sacrificing efficiency.

Some Scheme implementations come with pattern matching provided as
built-in libraries. For example, Bigloo seems to have a nice case-match
/ case-lambda facility.

It all depends on what you actually want to do (and unfortunately, you
don't give enough details in that regard).


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/

Vagif Verdi

unread,
Apr 28, 2007, 11:08:07 PM4/28/07
to
There's a language, based on lisp: http://www.lambdassociates.org/
It runs on Clisp and CMUCL.
You can freely mix lisp code with qi code.
And qi has many ML features, including pattern matching, currying,
partial applications.


Kent M Pitman

unread,
Apr 28, 2007, 11:42:57 PM4/28/07
to
Chris Schumacher <ken...@hotmail.com> writes:

> I noticed that in the functional language ML there is a way to break a
> function's input into various forms in the function header.
> For instance:
> split(a::b::c) (where :: is ML's equivalent of cons)
> This also allows an interesting kind of function overloading where you can
> contain several function definitions in a single declaration, each keyed by
> the format of the input.
> I attempted to do something similar in LISP, using:
> defun ( split (cons A B) )
>
> But it didn't appear to work. Does LISP have pattern-matching capabilities
> as well?

It's not built in per se, with some modest exceptions.

The reasons are subtle and varied, by the way. I don't recall this issue
coming up for a per se vote in any design forum I participated in, but I
suspect because people knew there were opinions all over the map on this,
and it would be better to leave to users to have competing packages. Here
are some issues that relate to that:

* Lisp allows for dynamic redefinition. Programs can construct and evaluate
and run new code dynamically at runtime, including redefining themselves.
If you have a definition that is in parts, there are issues of what part
gets redefined and what does not, etc.
(This issue comes up for DEFMETHOD, too, so the issue is not insurmountable.
But it's non-trivial and requires a lot of work to get the detailing right.
The CL standard was mostly constructed of things where people had already
done and long-tested such detailing and there as a well accepted result.
This is not such a case, so is not standardized.)

* Some of the issues are to do with the difference between static types
and dynamic types. You'd have to understand that these are different
in Lisp than in a static language, and that there are consequent
differences in what constitutes a match.

See my article http://www.nhplace.com/kent/PS/EQUAL.html for some
thoughts on this issue.

> I'd be sad if it didn't, because I like LISP a lot more than ML. :)

Don't be too sad. Language extension in Lisp is not like building
your own kernel in Unix. Rather, it's a routine operation that is
done compatibly with other programs and routinely by ordinary users.

Incidentally, I bet it's easier to write as an extension to Lisp than
it would be to extend ML to accommodate many of the things Lisp has
that ML doesn't.

Give it a shot. I'm sure a lot of people here will help with ideas and
advice.

Matthias Benkard

unread,
Apr 29, 2007, 4:33:06 AM4/29/07
to
Hi,

> But it didn't appear to work. Does LISP have pattern-matching capabilities
> as well?

I certainly don't want to keep you from having some fun implementing
your own pattern matcher in Common Lisp, but there are some libraries
readily available that you might be interested in.

First, there is CL-Unification: http://common-lisp.net/project/cl-unification/

CL-USER> (unify:match-case ('(1 2 3 4))
((?x ?y . ?z) (values 'yes (+ x y) z))
(?x (values 'no x)))
YES
3
(3 4)
CL-USER> (unify:match-case ('(1))
((?x ?y . ?z) (values 'yes (+ x y) z))
(?x (values 'no x)))
NO
(1)

Second, Faré Ridaeu's matching library, fare-matcher: http://www.cliki.net/fare-matcher

CL-USER> (fare-matcher:match '(1 2 3 4)
((list* x y z) (values 'yes (+ x y) z))
(x (values 'no x)))
YES
3
(3 4)
CL-USER> (fare-matcher:match '(1)
((list* x y z) (values 'yes (+ x y) z))
(x (values 'no x)))
NO
(1)

Third, the pattern matcher included in the ARNESI library:
http://common-lisp.net/project/bese/arnesi.html

CL-USER> (arnesi:match-case '(1 2 3 4)
((:list* x y z) (values 'yes (+ x y) z))
(x (values 'no x)))
YES
3
(3 4)
CL-USER> (arnesi:match-case '(1)
((:list* x y z) (values 'yes (+ x y) z))
(x (values 'no x)))
NO
(1)

Finally, I just stumbled upon MCPat, but I don't really know what
exactly it's supposed to be and how to use it: http://www.sfmishras.com/smishra/mcpat/

As I haven't actually used any of these libraries, I can't make a
recommendation. Just choose the one which looks the nicest to you or
whatever. :)

Bye-bye,
Matthias

Alan Crowe

unread,
Apr 29, 2007, 4:08:21 PM4/29/07
to
Chris Schumacher <ken...@hotmail.com> writes:

> But it didn't appear to work. Does LISP have pattern-matching capabilities
> as well?

destructing-bind doesn't do quite what you need. The catch
is that

Exceptional Situations:

If the result of evaluating the expression does not
match the destructuring pattern, an error of type error
should be signaled.

Checking the error terminology page to see what this means

1.4.2 Error Terminology

An error is signaled

This means that an error is signaled in both safe and
unsafe code. Conforming code may rely on the fact that
the error is signaled in both safe and unsafe code.

An error should be signaled

This means that an error is signaled in safe code, and
an error might be signaled in unsafe code.

Damn, the designers went for "should be" instead of
"is". Clearly they thought of the match checking code as a
debugging aid that might go away when you optimize for
speed.

All is not lost. The Common Lisp has a fairly powerful type
system. For example (cons * (cons * null)) names the type of
a list of two items. You can replace * by something more
specific.

So you can duct tape typecase and destructuring-bind
together like this:

CL-USER> (defun flex (x)
(typecase x
(atom x)
((cons integer (cons integer null))
(destructuring-bind (a b) x
(+ a b)))
((cons float (cons float null))
(destructuring-bind (a b) x
(* a b)))
((cons * *)
(destructuring-bind (a . b) x
(expt a b)))))

CL-USER> (dolist (x '(1
(5 7)
(5.0 7.0)
(2 . 3)))
(format t "~&~A ~A" x (flex x)))
1 1
(5 7) 12
(5.0 7.0) 35.0
(2 . 3) 8

Alan Crowe
Edinburgh
Scotland

Jon Harrop

unread,
May 12, 2007, 1:24:56 PM5/12/07
to
Chris Schumacher wrote:
> I noticed that in the functional language ML there is a way to break a
> function's input into various forms in the function header.
> For instance:
> split(a::b::c) (where :: is ML's equivalent of cons)

Yes. Pattern matching is ubiquitous in MLs (OCaml, SML, Haskell, F# etc.).
It even appears in function declarations:

# let f(a, (b, c)) = ((a, b), c);;
val f : 'a * ('b * 'c) -> ('a * 'b) * 'c = <fun>

the pattern (a, (b, c)) destructured the statically-checked type. The Lisp
equivalent is:

* (defun f (v) (cons (cons (car v) (cadr v)) (cddr v)))

> This also allows an interesting kind of function overloading where you can
> contain several function definitions in a single declaration, each keyed
> by the format of the input.

ML's pattern matching is not a form of overloading but, rather, it is a form
of dynamic dispatch.

> I attempted to do something similar in LISP, using:
> defun ( split (cons A B) )
>
> But it didn't appear to work. Does LISP have pattern-matching capabilities
> as well?

No. Lisp predates ML by a long way and lacks most of its features, including
pattern matching. You can try reimplementing parts of ML in Lisp but you'll
just end up at Greenspun. Indeed, the first MLs were implemented in Lisp.

> I'd be sad if it didn't, because I like LISP a lot more than ML. :)

This was discussed here again recently. The conclusion is essentially that
pattern matching's utility in ML is a consequence of ML's static type
system, i.e. you can't do it well enough in Lisp to make it worthwhile, or
without ending up with ML.

Lisp programmers typically compile their pattern matches by hand, like this:

http://groups.google.co.uk/group/comp.lang.lisp/msg/2603f471e85490e8?hl=en&

This gets very tedious very quickly.

It is probably also worth noting that ML pattern matching is extremely fast.
Something else that Lisp is bad at...

--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet

Jon Harrop

unread,
May 12, 2007, 1:32:39 PM5/12/07
to
Pascal Costanza wrote:
> There are pattern matching libraries for Lisp. (That's the nice thing of
> a programmable programming language - you can just extend it without the
> need to mess with the internals of an implementation.)

Greenspun.

> Neither Common Lisp nor Scheme, the two major Lisp dialects, have
> anything built in in that regard.

Scheme is much better than Lisp in this regard. Google for the thread about
symbolic simplification in OCaml, Lisp and Scheme if you're interested.

> In Common Lisp, you would probably try to arrange your code differently
> and take advantage of generic functions. That also gives you the
> advantage of better potential to dynamically evolve your code without
> sacrificing efficiency.

You can't get the effects of a pattern matching compiler by "rearranging
your code".

neptun...@gmail.com

unread,
May 12, 2007, 3:02:56 PM5/12/07
to
> http://groups.google.co.uk/group/comp.lang.lisp/msg/2603f471e85490e8?...

>
> This gets very tedious very quickly.
>
> It is probably also worth noting that ML pattern matching is extremely fast.
> Something else that Lisp is bad at...
>
> --
> Dr Jon D Harrop, Flying Frog Consultancy
> The F#.NET Journalhttp://www.ffconsultancy.com/products/fsharp_journal/?usenet

Ahh, here you are: http://www-amorphous.ch.cam.ac.uk/photo/jonharrop_thumb.jpg

I had to check whether you are some kind of retarded or what, but you
just look
like David Hasselhoff little gay brother...

Frog, seriously, are you running on some drugs or what?
Would you mind stop being a flying frog and land here on earth?
I know that you need to feed your ego and bank account doing some
advertisement
here, but your "intelligent" post are just sad example how a man with
next to zero
knowledge of Lisp live in a illusion that he actually knows something
and should
share his "knowledge" with others...

Don't be sad, not anybody can understand what is Lisp about (actually
most
people can, but you just have some problem... lack of neurons?)


Rainer Joswig

unread,
May 12, 2007, 4:06:21 PM5/12/07
to
In article <4645f9ac$0$8751$ed26...@ptn-nntp-reader02.plus.net>,
Jon Harrop <j...@ffconsultancy.com> wrote:

> No. Lisp predates ML by a long way and lacks most of its features, including
> pattern matching. You can try reimplementing parts of ML in Lisp but you'll
> just end up at Greenspun.

You don't need ML to do pattern matching. If one would want ML,
one would know where to find it. This newsgroup is about
a very different family of programming languages. Hint:
it is not ML.

> Indeed, the first MLs were implemented in Lisp.

But what is your point? At some point in history Ada,
Fortran, C, Pascal, Scheme, Dylan, Logo, Prolog, Haskell
and lots of other programming languages have been implemented in Lisp.

It just says Lisp is fine for implementing and/or prototyping
other programming languages. But we knew that before.

> > I'd be sad if it didn't, because I like LISP a lot more than ML. :)
>
> This was discussed here again recently. The conclusion is essentially that
> pattern matching's utility in ML is a consequence of ML's static type
> system, i.e. you can't do it well enough in Lisp to make it worthwhile, or
> without ending up with ML.

Pattern matching is completely independent of ML. There are
lots of very different pattern matching facilites for Lisp.

>
> Lisp programmers typically compile their pattern matches by hand, like this:
>
> http://groups.google.co.uk/group/comp.lang.lisp/msg/2603f471e85490e8?hl=en&

You can use a library.

>
> This gets very tedious very quickly.
>
> It is probably also worth noting that ML pattern matching is extremely fast.
> Something else that Lisp is bad at...


Okay, Bullshit bingo:

ML, check.
SML, check.
Pattern matching, check.
OCAML, check.
F#, check.
Haskell, check.
statically checked, check.
overloading, check.
dynamic dispatch, check.
Greenspun, check.
ML implemented in Lisp, check.
Lisp lacks most ML features, check.
static type system, check.
ML pattern matching extremely fast, check.
Lisp is bad, check.


Bingo!

--
http://lispm.dyndns.org

Matthias Benkard

unread,
May 12, 2007, 5:42:26 PM5/12/07
to
> * (defun f (v) (cons (cons (car v) (cadr v)) (cddr v)))

Ohh! One can write artificially ugly code in Lisp! Who'd have
thought?

Jon Harrop

unread,
May 13, 2007, 12:29:42 AM5/13/07
to
Rainer Joswig wrote:
> In article <4645f9ac$0$8751$ed26...@ptn-nntp-reader02.plus.net>,
> Jon Harrop <j...@ffconsultancy.com> wrote:
>> This was discussed here again recently. The conclusion is essentially
>> that pattern matching's utility in ML is a consequence of ML's static
>> type system, i.e. you can't do it well enough in Lisp to make it
>> worthwhile, or without ending up with ML.
>
> Pattern matching is completely independent of ML.

The OP specifically referred to ML's pattern matching.

Pascal Costanza

unread,
May 13, 2007, 6:00:52 AM5/13/07
to
Jon Harrop wrote:
> Pascal Costanza wrote:
>> There are pattern matching libraries for Lisp. (That's the nice thing of
>> a programmable programming language - you can just extend it without the
>> need to mess with the internals of an implementation.)
>
> Greenspun.
>
>> Neither Common Lisp nor Scheme, the two major Lisp dialects, have
>> anything built in in that regard.
>
> Scheme is much better than Lisp in this regard. Google for the thread about
> symbolic simplification in OCaml, Lisp and Scheme if you're interested.
>
>> In Common Lisp, you would probably try to arrange your code differently
>> and take advantage of generic functions. That also gives you the
>> advantage of better potential to dynamically evolve your code without
>> sacrificing efficiency.
>
> You can't get the effects of a pattern matching compiler by "rearranging
> your code".

So it's good that that's not what I said, isn't it?

Andy Freeman

unread,
Jun 13, 2007, 2:59:10 PM6/13/07
to
On May 12, 10:24 am, Jon Harrop <j...@ffconsultancy.com> wrote:
> Yes. Pattern matching is ubiquitous in MLs (OCaml, SML, Haskell, F# etc.).
> It even appears in function declarations:
>
> # let f(a, (b, c)) = ((a, b), c);;
> val f : 'a * ('b * 'c) -> ('a * 'b) * 'c = <fun>
>
> the pattern (a, (b, c)) destructured the statically-checked type. The Lisp
> equivalent is:
>
> * (defun f (v) (cons (cons (car v) (cadr v)) (cddr v)))

http://www.lisp.org/HyperSpec/Body/mac_destructuring-bind.html

> No. Lisp predates ML by a long way and lacks most of its features, including
> pattern matching.

Wrong.

Folks who want to work the ML way are free to do so. One wonders why
some folks haven't figured that out.

Thanks for playing.

Jon Harrop

unread,
Jun 21, 2007, 6:16:04 PM6/21/07
to
Andy Freeman wrote:
> On May 12, 10:24 am, Jon Harrop <j...@ffconsultancy.com> wrote:
>> let f(a, (b, c)) = ((a, b), c);;
>>
>> (defun f (v) (cons (cons (car v) (cadr v)) (cddr v)))
>
> http://www.lisp.org/HyperSpec/Body/mac_destructuring-bind.html

That would be even longer and just as unnecessarily obfuscated.

>> No. Lisp predates ML by a long way and lacks most of its features,
>> including pattern matching.
>
> Wrong.

As you can see, you won't get a useful response if you ask Lispers about any
of the language features that they don't use. Best case, you'll get an
ad-hoc, informally-specified and bug-ridden implementation of half of an ML
pattern matcher.

Anyone wanting to learn about ML-style pattern matching would be much better
off asking in a group related to any language that integrates a decent
pattern matcher (Standard ML, F#, OCaml, Haskell etc.) and not Lisp, or by
reading introductory material:

http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html?cll
http://www.ffconsultancy.com/products/ocaml_journal/free/introduction.html?cll
http://www.ffconsultancy.com/ocaml/benefits/pattern_matching.html?cll
http://www.ffconsultancy.com/ocaml/benefits/parsing.html?cll
http://www.ffconsultancy.com/ocaml/benefits/symbolic.html?cll
http://www.ffconsultancy.com/ocaml/benefits/interpreter.html?cll

> Folks who want to work the ML way are free to do so.

By using ML, yes.

To make an informed choice of language, you need to know the differences
between the languages. RB-tree rebalancing and symbolic rewriting are two
examples where languages with integrated pattern matching excel compared to
Lisp, both in terms of clarity and performance.

If you want to show Lisp in a good light, do not mention pattern matching.

--
Dr Jon D Harrop, Flying Frog Consultancy

The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?usenet

Rainer Joswig

unread,
Jun 21, 2007, 6:26:45 PM6/21/07
to
In article <467afa07$0$8728$ed26...@ptn-nntp-reader02.plus.net>,
Jon Harrop <j...@ffconsultancy.com> wrote:

___________________________
/| /| | |
||__|| | Please don't |
/ O O\__ feed |
/ \ the trolls |
/ \ \ |
/ _ \ \ ----------------------
/ |\____\ \ ||
/ | | | |\____/ ||
/ \|_|_|/ | __||
/ / \ |____| ||
/ | | /| | --|
| | |// |____ --|
* _ | |_|_|_| | \-/
*-- _--\ _ \ // |
/ _ \\ _ // | /
* / \_ /- | - | |
* ___ c_c_c_C/ \C_c_c_c____________

--
http://lispm.dyndns.org

Reply all
Reply to author
Forward
0 new messages