Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!jp
From: jp@unix.cis.pitt.edu (Jefferson Provost)
Newsgroups: comp.lang.lisp
Subject: Re: FALSE vs empty list
Message-ID: <35036@unix.cis.pitt.edu>
Date: 5 Sep 90 03:07:38 GMT
References: <24305@uflorida.cis.ufl.EDU> <119011@linus.mitre.org>
Reply-To: jp@unix.cis.pitt.edu (Jefferson Provost)
Distribution: usa
Organization: Society for Visual Lunacy
Lines: 47

In article <119011@linus.mitre.org> guttman@linus.mitre.org (Joshua D. Guttman) writes:
>
>Well here's an example of why it would be nice to have '() and #f (in scheme
> [...]
>Suppose you're doing syntactic matching or unification or some procedure like
>that which wants to return a substitution when it succeeds.  
>
>So ((x . 23) (y .  34)) means substitute 23 for x and 34 for y and you have a
>match.  Then it's natural for () to mean that you don't have to substitute
>anything, because the expressions already match.  
>
>However, what do you return when the expressions can't be made to match, e.g.
>(* x 3) and (+ x 3)?  Well, you would normally want to return #f to indicate
>failure, but if () = false you can't, because that indicates you have
>succeeded.  
>
>So you have to do a ghastly hack like return the symbol FAIL.  This is highly
>unpleasant when you want to write code like 
[some code deleted]

Or, you can have the matcher return a list containting the list of
bindings (substitutions, whatever).  Thus,

nil = no match
(nil) = match, with no substitutions.

Of course, now you have to look one level deeper in the returned list to
actually find the bindings, but I don't think that's such a big deal.
In addition, with this set up, the matcher is more easily extendable to
being able to handle situations with multiple possible binding sets,
should you so desire. (e.g. matching of non-ordered sets, or some sort
of set membership operator in the matcher)

I believe _Artificial_Intelligence_Programming_ by Charniak, et al,
handles it this way.

Another possible scheme is to return a dotted pair, in which the first
value is t or nil, depending on the success of the match, and the
second value is the list of sustitutions.

This is the way that _Common_LISPcraft_ by Robert Wilensky does it.


There are probably other ways, as well,

latre,
Jeff