Hello, all.
I have been on this newsgroup only for a day or so, primarily because
I am looking at prototyping an application in Lisp, which has already
been developed in Caml. The reason I would like to use Lisp is that
the code needs to interface with a verification system implemented in
Allegro CL. The reason I prototyped the application in Caml first is
that I have very little Lisp development experience (though they used
Scheme in my first introduction to programming course in college), and
I was unsure whether or not it could do ML like pattern matching.
The application requires working with Hashtables (which I understand
Lisp has), and data structures with named constructors, and the
functions employ pattern matching on their arguments *heavily*. For
example, in Caml:
type searchresult =
Failed
| Witness of proof_tree
;;
where proof_tree is a type with 5 different constructors, each with a
varying list of arguments, some of which are other proof trees.
Several functions, such as proof checking, do pattern matching on the
structure of these datatypes.
My main question is whether there are facilities in the Lisp language
which make pattern matching roughly as easy to do as in ML variants.
This would help me make a decision on committing to porting this in
Lisp. Otherwise, I would try to interface with the verification
system in other ways, but building the exterior code in Lisp is
definitely preferable.
I have been reading several good things about Lisp over the last
couple of days, and it I might be a victim of disinformation about the
language efficiency and features. The question above reflects my
(hopefully lessening) ignorance about the language, so I would
appreciate it if folks would set me straight, and give me some
pointers.
Cheers.
On Wed, Apr 16, 2003 at 03:44:38PM -0700, Teirn wrote:
> My main question is whether there are facilities in the Lisp language
> which make pattern matching roughly as easy to do as in ML variants.
Well, first things first: pattern matching isn't necessary to do all
these things. But, I also find it a convenient feature of ML variants,
and so does Fare apparently since he implemented fairly general
pattern-matching macros for Common Lisp:
http://fare.tunes.org/cgi-bin/viewcvs.cgi/fare/lisp/matcher.lisp
OTOH, it's not something I miss terribly much when I program in Lisp,
it's more a matter of style. I tend to use a functional interface to
data-structures rather than deconstructing their internals. Also,
Lispers will tend to make use of ad-hoc polymorphism a bit more, and you
may find yourself doing things like (typecase var (failed ...) (witness
...)). Or doing similar things with generic-functions and methods.
> I have been reading several good things about Lisp over the last
> couple of days, and it I might be a victim of disinformation about the
> language efficiency and features. The question above reflects my
> (hopefully lessening) ignorance about the language, so I would
> appreciate it if folks would set me straight, and give me some
> pointers.
Here's a place for pointers: http://www.cliki.net/
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
···········@yahoo.com (Teirn) writes:
> I have been on this newsgroup only for a day or so, primarily because
> I am looking at prototyping an application in Lisp, which has already
> been developed in Caml. The reason I would like to use Lisp is that
> the code needs to interface with a verification system implemented in
> Allegro CL. The reason I prototyped the application in Caml first is
> that I have very little Lisp development experience (though they used
> Scheme in my first introduction to programming course in college), and
> I was unsure whether or not it could do ML like pattern matching.
One of the core features of Lisp is extensibility: If the language
lacks some feature you like, it is usually easy, but at least
possible, to integrate it.
See <http://www.cliki.net/fare-matcher> for a library that claims to
implement ML-style pattern matching integrated with CL. There may be
others.
> The application requires working with Hashtables (which I understand
> Lisp has), and data structures with named constructors, and the
> functions employ pattern matching on their arguments *heavily*. For
> example, in Caml:
>
> type searchresult =
> Failed
> | Witness of proof_tree
> ;;
>
> where proof_tree is a type with 5 different constructors, each with a
> varying list of arguments, some of which are other proof trees.
>
> Several functions, such as proof checking, do pattern matching on the
> structure of these datatypes.
>
> My main question is whether there are facilities in the Lisp language
> which make pattern matching roughly as easy to do as in ML variants.
Maybe a straightforward translation is possible with the library
mentioned above is possible, but it certainly is not the only way.
IMHO a better way would be using the standard facilities of Common
Lisp, like, say, structures and run-time type information. For
example, if you have in ML (I just know OCaml, not Standard ML, and
that not very well, so that may be syntactically rubbish):
type foo =
Type_1 of int
| Type_2 of string * string
| Type_3 of boolean
let type_num x =
match x with
Type_1 x -> 1
| Type_2 (_, _) -> 2
| Type_3 _ -> 3
type_num (Type_1 123)
- : int = 1
(Assuming the type would be a little more complex in the real world)
You could write in CL:
(defstruct type-1
int)
(defstruct type-2
string1 string2)
(defstruct type-3
bool)
(defun type-num (thing)
(etypecase thing
(type-1 1)
(type-2 2)
(type-3 3)))
(type-num (make-type-1 :int 123))
=> 1
If you want, you can also throw a `(deftype foo () '(or type-1 type-2 type-3))'
in somewhere if it makes you feel better ;-)
Other ways are possible - you can define arbitrary types (with
deftype), even based on your own predicates:
(defun thing-is-a-foo-p (thing)
#| figure out whether thing is a foo or not somehow |#)
(deftype foo () '(satisfies thing-is-a-foo-p))
Or you could, for example, represent your searchresult type as lists
in the form (:failed), (:witness proof-tree) ... and check for the CAR
in a CASE or COND form.
Yet another possibility is method dispatch with CLOS.
Perl is not the only TIMTOWDI language :)
Regards
Henrik
Henrik Motakef <··············@web.de> writes:
[lots of stuff]
Um, I just realized that you probably also want to do something with
the components of your searchresults etc. So I cound as well point you
to DESTRUCTURING-BIND.
Regards
Henrik
From: Joe Marshall
Subject: Re: ML style pattern matching: Is Lisp a good fit?
Date:
Message-ID: <znmpgqta.fsf@ccs.neu.edu>
···········@yahoo.com (Teirn) writes:
> The application requires working with Hashtables (which I understand
> Lisp has), and data structures with named constructors, and the
> functions employ pattern matching on their arguments *heavily*. For
> example, in Caml:
>
> type searchresult =
> Failed
> | Witness of proof_tree
> ;;
>
> where proof_tree is a type with 5 different constructors, each with a
> varying list of arguments, some of which are other proof trees.
>
> Several functions, such as proof checking, do pattern matching on the
> structure of these datatypes.
>
> My main question is whether there are facilities in the Lisp language
> which make pattern matching roughly as easy to do as in ML variants.
I'm surprised no one mentioned CLOS. Multimethod dispatch and
inheritance make type-based `pattern matching' easy. You could write
code something like this:
(defmethod process-result ((witness (eql :failed)))
(error "Search failed to find an answer"))
(defmethod process-result ((witness proof-tree))
....)
As you mention that a witness has five different variants, perhaps
you would set up your class inheritance something like this:
(defclass proof-tree () ())
(defclass axiom (proof-tree) ())
(defclass conjunction (proof-tree)
((left-clause)
(right-clause)))
(defclass disjunction (proof-tree)
((left-clause)
(right-clause)))
From: Francois-Rene Rideau
Subject: Re: ML style pattern matching: Is Lisp a good fit?
Date:
Message-ID: <87istd86oh.fsf@Samaris.tunes.org>
Joe Marshall <···@ccs.neu.edu> writes:
> I'm surprised no one mentioned CLOS. Multimethod dispatch and
> inheritance make type-based `pattern matching' easy.
OO works great for pattern-matching,
but only if your patterns only have one level of construction.
For deep patterns, you still need more than that.
Which reminds me that my pattern matcher doesn't try to factor
the matching of common initial subpatterns across clauses.
Optimizations are boring to write when you don't expect
the user-base to justify them.
[ Fran�ois-Ren� �VB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[ TUNES project for a Free Reflective Computing System | http://tunes.org ]
Opportunity is missed by most people because it comes dressed in overalls
and looks like work. -- T. A. Edison
From: Joe Marshall
Subject: Re: ML style pattern matching: Is Lisp a good fit?
Date:
Message-ID: <adep9ky5.fsf@ccs.neu.edu>
Francois-Rene Rideau <····@tunes.org> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
> > I'm surprised no one mentioned CLOS. Multimethod dispatch and
> > inheritance make type-based `pattern matching' easy.
> OO works great for pattern-matching,
> but only if your patterns only have one level of construction.
> For deep patterns, you still need more than that.
Yes. I was assuming the `flat' kind of matching.
In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu>
wrote:
>···········@yahoo.com (Teirn) writes:
>
>> My main question is whether there are facilities in the Lisp language
>> which make pattern matching roughly as easy to do as in ML variants.
>
>I'm surprised no one mentioned CLOS. Multimethod dispatch and
>inheritance make type-based `pattern matching' easy. You could write
>code something like this:
Hmm. I guess I'm delighted the following works:
===
? (defmethod fact ((n (eql 1))) ; base case.
1)
#<STANDARD-METHOD FACT ((EQL 1))>
? (defmethod fact ((n integer)) ; recursive step.
(* n (fact (- n 1))))
#<STANDARD-METHOD FACT (INTEGER)>
? (fact 1)
1
? (fact 2)
2
? (fact 3)
6
? (fact 70)
1197857166996989179607278372168909873645893814254642585755536286462800958
2789845319680000000000000000
?
===
A primitive sort of pattern matching, to be sure...
On Fri, Apr 18, 2003 at 12:47:14PM -0500, sv0f wrote:
> ? (defmethod fact ((n (eql 1))) ; base case.
> 1)
(defmethod fact ((n (eql 0))) ; base case
1)
(fact 0) => 1
:-)
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
···········@yahoo.com (Teirn) wrote in message news:<···························@posting.google.com>...
> My main question is whether there are facilities in the Lisp language
> which make pattern matching roughly as easy to do as in ML variants.
Never mind real Lisp, in which everything is a piece of cake, I
recently did this easily in C++ using some ad-hoc, inefficiently
implemented imitations of pieces of Lisp:
void analyze_it(const object_ref &it)
{
// static variables: C++'s lame answer to lazy,
// once-only evaluation! :)
static object_ref
pattern1 = parse(L"((or string symbol) (eql 3))"),
pattern2 = parse(L"(string string integer)"),
pattern3 = parse(L"(symbol (or null cons))");
if (matches(it, pattern1)) {
// for example ("foo" 3) or (bar 3)
object_ref foo = first(it);
object_ref three = second(it);
} else if (matches(it, pattern2)) {
// for example ("foo" "bar" 42)
} else if (matches(it, pattern3)) {
// (foo nil) or (foo (some list))
} else {
// no match
}
}
Beethoven's Ninth in the speakers, Greenspun's Tenth in the code! ;)
The matches() function supports a formalism which expresses a match in
terms of type names in a tree, or instances of the (or ...) or (eql
...) operator for some added flexibility for disjunction and matching
on numeric value or identity.