johnson@csli.STANFORD.EDU (Mark Johnson) (03/23/89)
I was writing a couple of demo unification programs recently
and the situation arose where I wanted the unification function
to return either a value indicating failure (of unification) or
a variable substitution (i.e. a list of pairs).
The problem is that NIL could conceivably mean both failure of
unification (i.e. FALSE) and also the empty variable substitution.
I know how to get around this problem, but it struck me that
maybe the overloading of the symbol NIL as both logical falsity
and also the empty list as is common in Lisp might not be such a
good idea.
I know that texts like Winston and Horn tout this as an advantage,
but I'm not so sure. If () was distinct to NIL (= FALSE) then
my little unifier would be a lot clearer to read.
Of course, some list manipulation programs would be more complex.
For example, instead of writing
(defun my-member (elt list)
(and list
(or (equal elt (first list))
(my-member elt (rest list)))))
I would have to write
(defun my-member (elt list)
(and (non-null list) ; or better (consp list)
(or (equal elt (first list))
(my-member elt (rest list)))))
Of course the second version actually expresses more precisely what
I mean: list is not a logical value, so it really isn't an appropriate
argument to a boolean function.
Does anybody else have any comments on the matter? Do more advanced
functional languages (ML?) incorporated the same overloading of NIL?
Mark Johnson.mike@arizona.edu (Mike Coffin) (03/23/89)
From article <8247@csli.STANFORD.EDU> (Mark Johnson): [Speaking of the overloading of nil and the empty list in Lisp] > Does anybody else have any comments on the matter? Do more advanced > functional languages (ML?) incorporated the same overloading of NIL? Scheme has distinct values for false and the empty list: #F and '(), respectively. Any Scheme value can be used as a boolean value for the purpose of a conditional test. Any value except #F and the empty list count as "true"; #F and the empty list count as "false". This seems to be the best of both worlds to me... -mike -- Mike Coffin mike@arizona.edu Univ. of Ariz. Dept. of Comp. Sci. {allegra,cmcl2}!arizona!mike Tucson, AZ 85721 (602)621-2858
rar@ZOOKS.ADS.COM (Bob Riemenschneider) (03/23/89)
=> The problem is that NIL could conceivably mean both failure of => unification (i.e. FALSE) and also the empty variable substitution. => I know how to get around this problem, but it struck me that => maybe the overloading of the symbol NIL as both logical falsity => and also the empty list as is common in Lisp might not be such a => good idea. => => I know that texts like Winston and Horn tout this as an advantage, => but I'm not so sure. If () was distinct to NIL (= FALSE) then => my little unifier would be a lot clearer to read. => => Of course, some list manipulation programs would be more complex. ... Scheme avoids the complexity by counting () as false, in the same sense that Common Lisp treats everything other than () as true. (But R3RS allows #f and () to be identical, so not every dialect provides a solution to your original problem.) -- rar
dorai@titan.rice.edu (Dorai Sitaram) (03/23/89)
In article <9840@megaron.arizona.edu> mike@arizona.edu (Mike Coffin) writes:
$From article <8247@csli.STANFORD.EDU> (Mark Johnson):
$[Speaking of the overloading of nil and the empty list in Lisp]
$$ Does anybody else have any comments on the matter? Do more advanced
$$ functional languages (ML?) incorporated the same overloading of NIL?
$
$Scheme has distinct values for false and the empty list: #F and '(),
$respectively. Any Scheme value can be used as a boolean value for the
$purpose of a conditional test. Any value except #F and the empty list
$count as "true"; #F and the empty list count as "false". This seems
$to be the best of both worlds to me...
Which Scheme is this?
In all the Schemes I've come across, #f and '() are just two ways of
writing the same object. They are indistinguishable from each other,
i.e., (eq? #f '()) ==> true. A unification algorithm written in Scheme
that used '() as the empty substitution list and #f to indicate
failure would bomb because of the false/empty-list schizophrenia.
It is perhaps helpful not to think of the-empty-list as a given in
Lisp/Scheme. Consider that we're given the numbers, booleans t and
nil, characters and other basic constants of your choice. Added to
this, we now are given the ability to form dotted pairs (cons), with
which we can form data-types of our choice. _One_ of the user
data-types that we can create from the above givens is something
called a list, which is distinguished by its having a nil finally when
one traverses down its dotted-pair representation in a rightmost
fashion. This way, nil is just a user-representation for the user's
empty list concept, and _we_ are doing the overloading of nil, _not_
Lisp. Feel better? ;-)
As an aside, Lisp would be more accurately though less euphonically
described as Dottedpaip.
--doraimike@arizona.edu (Mike Coffin) (03/23/89)
From article <2906@kalliope.rice.edu>, by dorai@titan.rice.edu (Dorai Sitaram): > In all the Schemes I've come across, #f and '() are just two ways of > writing the same object. They are indistinguishable from each other, > i.e., (eq? #f '()) ==> true. Yes, I was wrong. They are not required to be the same, but it is allowed, so you can't rely on them being different if you want to write portable code. Sorry for the mistake. -mike -- Mike Coffin mike@arizona.edu Univ. of Ariz. Dept. of Comp. Sci. {allegra,cmcl2}!arizona!mike Tucson, AZ 85721 (602)621-2858
jbn@glacier.STANFORD.EDU (John B. Nagle) (03/23/89)
In article <37807@think.UUCP> barmar@brigit.think.com.UUCP (Barry Margolin) writes: >Common Lisp, a popular approach is to return two values -- the first >is the value, and the second indicates whether the first is a list or >boolean when it is NIL. Yes, although multiple-return-valued functions are decidedly an afterthought in CL. Mesa is one of the few languages to integrate this notion well. >I think most language theorists would now agree that Lisp's >overloading of NIL was a bad idea. I don't think any non-Lisp-like >languages copy this. C's notion that conditionals test for nonzero integer values follows this line of reasoning. The result in C is that programs are slightly shorter, somewhat more likely to be in error, and no more efficient because of it. In strongly typed languages, such as Pascal and its descendants, the notion that NIL is a component of all pointer types is sometimes troublesome. But the alternative, a NIL for every type, seems so nit-pickey. John Nagle
clamen@CLAMEN.CS.CMU.EDU (Stewart Clamen) (03/23/89)
In article <8247@csli.STANFORD.EDU> johnson@csli.STANFORD.EDU (Mark Johnson) writes:
The problem is that NIL could conceivably mean both failure of
unification (i.e. FALSE) and also the empty variable substitution.
I know how to get around this problem, but it struck me that
maybe the overloading of the symbol NIL as both logical falsity
and also the empty list as is common in Lisp might not be such a
good idea.
....
Of course the second version actually expresses more precisely what
I mean: list is not a logical value, so it really isn't an appropriate
argument to a boolean function.
Does anybody else have any comments on the matter? Do more advanced
functional languages (ML?) incorporated the same overloading of NIL?
The empty-list/false "feature" in LISP is more of a pun in my opinion
than anything else. In the Scheme world, we are slowly moving away
from it. The current Standard does not require that #f (the false
object) and () (the empty list) be synonymous, and at a recent
meeting, the issue of actually having the empty-list be non-false (ie.
returning #f from (NOT ()) !), was even raised.
--
------------------------------------------------------------------------------
Stewart M. Clamen
School of Computer Science, Carnegie Mellon University
Pittsburgh, PA 15213-3890
INTERNET: clamen@CS.CMU.EDU
USENET: ...!uunet!"clamen@cs.cmu.edu"
-- shebs@Apple.COM (Stanley Todd Shebs) (03/24/89)
In article <8247@csli.STANFORD.EDU> johnson@csc.brown.edu (Mark Johnson) writes: >[...] it struck me that >maybe the overloading of the symbol NIL as both logical falsity >and also the empty list as is common in Lisp might not be such a >good idea. There's an amusing song that somebody posted a while ago about translating something like (cdr (assoc ...)) from traditional Lisp into T. By the time it was done, the code was about five lines long... stan shebs shebs@apple.com
quale@puff.cs.wisc.edu (quale) (03/24/89)
In article <37807@think.UUCP> barmar@brigit.think.com.UUCP (Barry Margolin) writes: >I think most language theorists would now agree that Lisp's >overloading of NIL was a bad idea. I don't think any non-Lisp-like >languages copy this. > >Barry Margolin >Thinking Machines Corp. Although I think Scheme's overloading of NIL is its greatest misfeature, it could be worse -- C doesn't have a boolean type, and the wonderfully elegant decison to overload integers for this purpose sabotages compiler error checking. (And also causes confusion. There was even some discussion on the net about whether false is always 0 in C.) -- Doug Quale quale@uhura.cs.wisc.edu
biep@cs.vu.nl (J A Biep Durieux) (03/29/89)
>If () was distinct to NIL (= FALSE) > then my little unifier would be a lot clearer to read. But why does your empty list have to be NIL? let your bindings-list end in T, and the problem is gone: NIL --> unification failed T --> unification succeeded with empty set of bindings (--- . T) --> unification succeeded with given set of bindings If your programs test for end-of-list with (ATOM &) instead of with (NULL &), then everything should work OK. After all, ending lists with the symbol for FALSE is only a choice, not something imposed upon you by the language (except by the print- functions, maybe..) -- Biep. (biep@cs.vu.nl via mcvax) Who am I to doubt the existence of God? I am only a simple man, I already have trouble enough doubting the existence of my neighbour!