stephen@estragon.uchicago.edu (Stephen P Spackman) (09/04/90)
In article <24305@uflorida.cis.ufl.EDU> drc@beach.cis.ufl.edu (David Cabana) writes:
I have heard critics of lisp object to the identification of
the empty list and the boolean value FALSE. I am afraid I
fail to see point of this objection. Can anyone explain this,
or suggest references in the literature? Thanks.
I think that to take this view you need to think either
(1) of Lisp NOT as providing (which I think it does) its own little
computational logic under the classical model that god gave us
equality and man invented types (in which vase it's an annoyance not
to be able to use NIL as UNSPECIFIED as distinct from TRUE and FALSE)
or
(2) that Lisp is crypto-typed and each type should get a distinct set
of members thank you very much (which I *think* is a purely aesthetic
argument, but it might have its uses in some analytic techniques; did
boyer&moore need to distinguish them for formal purposes? I think they
did)
Myself I think of it this way: all the world is typed. Every type
contains a "no, forget it" value. IF is polymorphic; it tests for this
distinguished value of ANY type. Finally, Lisp doesn't mention types
(Lisp types aren't my types because I they aren't prior) so it
collapses all functionally identical atoms into single objects -
effectively using "pre-casting", if you think about the arrows. That
way I can fit most programming languages into the same model.
Myself, I find polymorphism in IF and OR (and AND if it works on
lvalues! - in C syntax if not semantics <<(a && b) = c>>)
stupendously useful and entirely formalisable, though I like, as I
say, prior typing (the whole idea of equality without type hurts my
mind. I mean how do you compare two THINGS for equality when for all
you know one is a yak and the other is a superintelligent shade of the
colour blue? I mean, you can't even pick them up until you know their
types! No flames, this is just a personal failing. :-).
Is anyone any clearer on this?
stephen p spackman stephen@estragon.uchicago.edu 312.702.3982
guttman@linus.mitre.org (Joshua D. Guttman) (09/05/90)
Well here's an example of why it would be nice to have '() and #f (in scheme notation) be distinct. (Note: I believe that in the new Scheme standard (R4RS) they will be required to be distinct, with the null list counting as non-false in conditional tests. Just imagine!) 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 (any (lambda (exp) (match exp fixed-exp)) some-list) since you have to rewrite it as an iteration with a test for non-FAILing return value. Even (any (lambda (exp) (let ((subst (match exp fixed-exp))) (and (succeed? subst) subst))) some-list) is wrong. Josh
cowan@marob.masa.com (John Cowan) (09/05/90)
In article <STEPHEN.90Sep3192954@estragon.uchicago.edu>, stephen@estragon.uchicago.edu (Stephen P Spackman) writes: >Myself I think of it this way: all the world is typed. Every type >contains a "no, forget it" value. IF is polymorphic; it tests for this >distinguished value of ANY type. Finally, Lisp doesn't mention types >(Lisp types aren't my types because I they aren't prior) so it >collapses all functionally identical atoms into single objects - >effectively using "pre-casting", if you think about the arrows. That >way I can fit most programming languages into the same model. Smalltalk models 'nil' as the sole object of the type UndefinedObject. 'True' and 'false' are likewise the sole objects of types True and False. Nil is not false is not an empty collection. >Myself, I find polymorphism in IF and OR (and AND if it works on >lvalues! - in C syntax if not semantics <<(a && b) = c>>) >stupendously useful and entirely formalisable, though I like, as I >say, prior typing (the whole idea of equality without type hurts my >mind. I mean how do you compare two THINGS for equality when for all >you know one is a yak and the other is a superintelligent shade of the >colour blue? I mean, you can't even pick them up until you know their >types! No flames, this is just a personal failing. :-). You pick either object and ask it, "Are you equal to the other object?" It can answer yes, no, or search-me. If it answers search-me, a meta-protocol for equality asks the opposite question of the other object. If it, too, answers search-me, the meta-protocol replies false. >Is anyone any clearer on this? > >stephen p spackman stephen@estragon.uchicago.edu 312.702.3982 -- cowan@marob.masa.com (aka ...!hombre!marob!cowan) e'osai ko sarji la lojban
jp@unix.cis.pitt.edu (Jefferson Provost) (09/05/90)
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
krulwich@ils.nwu.edu (Bruce Krulwich) (09/06/90)
stephen@estragon (Stephen P Spackman) writes: >Suppose, just as plausibly, that I'm doing theorem-proving. Each >strategy takes a proposition as an argument and needs to return one of >TRUE, FALSE and FAIL. Now, isn't it natural to represent failure with >#f, so ANY will behave? But wait! #f is ALREADY falsity! Conflict of >interests again. > >Amusingly enough, BOTH of these happened to me in real life (I once ... >The second difficulty was dealt with by having "truth" and "falsity" >bound to gensyms to represent object-model truthvalues, with nil being >the _absence_ of truthness. The best answer that I've found to all of these problems is to have the function take continuation parameters for all of the end-cases that it has to handle. This obviates the need to have the return value signal the result, because different pieces of code can be called instead. The following could be how a database retrieval system could be called. The first arg is the proposition, the second is the continuation to call in the success case, and the third is the continuation to call in the failure case. (query '(on a b) #'(lambda (bindings) (format t "A is ~S" (cdr (assoc 'a bindings)))) #'(lambda () (format t "I failed..."))) (query prop #'(lambda (bindings) (if bindings (format t "Match.") (format t "Exact match."))) #'(lambda () (format t "No match."))) This has the overhead of CONSing the continuations (unless you've got a compiler that handled downward-funargs well), but I've found that if you want to do backtracking in a matcher (when handling more complex expressions), continuation CONSing is no more expensive than other schemes. Bruce Krulwich Institute for the Learning Sciences
sfk@otter.hpl.hp.com (Steve Knight) (09/06/90)
Ahhh, the old arguments are the best arguments .... The type-distinctness of empty-list and false in a Lisp or Lisp-like language is an aesthetic consideration. Many folks, and I'd include myself, believe that making them distinct is more convenient and makes programs more readable. Ultimately, our arguments must boil down to "I don't think of an empty list and false in the same way. I don't think that applying boolean operators to lists makes good programming practice." and so on. These are preferences that cannot be grounded logically. You might argue that making them distinct or the same confers some special advantage. Review of debates shows that any advantages or disadvantages are less than uniformly persuasive. A lot of folks go away unconvinced that enough benefit/penalty has been shown to change their views. If you are happy applying boolean operators to lists and list operators to booleans, then you will have little inclination to change. You may even enjoy the conciseness of idioms such as (car (or (member x L1) (member x L2) '(()))) which exploit the conflation of lists and booleans. On the other hand, you may be inclined to wonder why only lists and booleans should enjoy the benefits of conflation. For example, we could map 0 and NIL onto one another & perhaps 1 onto TRUE. No, they are kept distinct because it is generally felt to be more comfortable that way. Distinct concepts are typically given distinct, non-overlapping data-types. It's not a big deal. It's just one of those many features that makes Lisp feel a bit dated. Steve
lgm@cbnewsc.att.com (lawrence.g.mayka) (09/07/90)
> 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. Common Lisp functions often return two values in this situation: the result (if any), and an indication of success or failure. SUBTYPEP is a typical example. Lawrence G. Mayka AT&T Bell Laboratories lgm@iexist.att.com Standard disclaimer.
cowan@marob.masa.com (John Cowan) (09/07/90)
In article <1350029@otter.hpl.hp.com>, sfk@otter.hpl.hp.com (Steve Knight) writes: >The type-distinctness of empty-list and false in a Lisp or Lisp-like >language is an aesthetic consideration. Many folks, and I'd include myself, >believe that making them distinct is more convenient and makes programs >more readable. Ultimately, our arguments must boil down to "I don't think >of an empty list and false in the same way. I don't think that applying >boolean operators to lists makes good programming practice." and so on. Something that Lispers never seem to address, but is the case in Smalltalk, is the distinctness of the empty list and the undefined datum. In Smalltalk, nil, false, and () are completely different: they have different types. I find this to be extremely useful. For example, this neatly solves the problem of representing the difference between knowledge of nothing and ignorance. () represents knowing that something has no elements, whereas nil represents ignorance. This solves the problem of returning a list of bindings vs. returning failure. Is there any dialect of Lisp in which such a distinction is made? I know that Scheme optionally distinguishes between #f (false) and '() (the empty list), but does anyone distinguish between #f, '(), and #nil, or the like? -- cowan@marob.masa.com (aka ...!hombre!marob!cowan) e'osai ko sarji la lojban
klapper@oravax.UUCP (Carl Klapper) (09/07/90)
In article <1350029@otter.hpl.hp.com>, sfk@otter.hpl.hp.com (Steve Knight) writes: > If you are happy applying boolean operators to lists and list operators to > booleans, then you will have little inclination to change. You may even > enjoy the conciseness of idioms such as > (car (or (member x L1) (member x L2) '(()))) > which exploit the conflation of lists and booleans. or even ... (defvar list-where-found nil) (defun member-note-list (x l) (let ((member-list (member x l))) (when member-list (setq list-where-found l) member-list))) (setf (car (or (member-note-list x L1) (member-note-list x L2) '(()))) list-where-found) (and (member-note-list x L3) (member-not-list x list-where-found)) which exploit the execution sequences of OR and AND. Clearly, lisp booleans and boolean operators diverge from mathematical booleans and boolean operators. BTW, my preferences for TRUE and FALSE are : TRUE #s(AND :ARGS NIL) FALSE #s(OR :ARGS NIL) +-----------------------------+--------------------------------------------+ | Real urbanites don't buy | Carl Klapper | | things. They buy service. | Odyssey Research Associates, Inc. | | | 301A Harris B. Dates Drive | | A kitchen's place is | Ithaca, NY 14850 | | in the restaurant. | (607) 277-2020 | | | klapper%oravax.uucp@cu-arpa.cs.cornell.edu | +-----------------------------+--------------------------------------------+
masinter@parc.xerox.com (Larry Masinter) (09/08/90)
> In article <1350029@otter.hpl.hp.com>, > sfk@otter.hpl.hp.com (Steve Knight) writes: >The type-distinctness of empty-list and false in a Lisp or Lisp-like >language is an aesthetic consideration. Many folks, and I'd include myself, >believe that making them distinct is more convenient and makes programs >more readable. Ultimately, our arguments must boil down to "I don't think >of an empty list and false in the same way. I don't think that applying >boolean operators to lists makes good programming practice." and so on. I think it was David Moon that characterized this (in 79?) as something that some people consider to be a wart on the face of Lisp, but others think of it as a beauty mark. Personally, I always found the pun of NIL and false and () to be much more of a convenience than a hinderance, but styles and preferences in programming languages do vary. That 0 and false and end-of-string are the same in C sometimes annoys me. >In article <26E7C356.5DE7@marob.masa.com> cowan@marob.masa.com (John Cowan) writes: > Something that Lispers never seem to address, but is the case in Smalltalk, > is the distinctness of the empty list and the undefined datum. In Smalltalk, > nil, false, and () are completely different: they have different types. > I find this to be extremely useful. > For example, this neatly solves the problem of representing the difference > between knowledge of nothing and ignorance. () represents knowing that > something has no elements, whereas nil represents ignorance. This solves > the problem of returning a list of bindings vs. returning failure. > Is there any dialect of Lisp in which such a distinction is made? I know > that Scheme optionally distinguishes between #f (false) and '() (the empty > list), but does anyone distinguish between #f, '(), and #nil, or the like? Something like this was proposed for Common Lisp: the idea that there would be a distinct value "undefined". The discussion got tied into knots about what it would mean to store "undefined" in a variable, how could you say in a program that a value *should be* undefined without getting errors because you were trying to use an undefined value, etc., to the point where there was nothing we thought we could add to the language that would reasonably automatically detect uses of undefined values. Besides, in many situations there are multiple degrees of uncertainty ("undefined, but I know it is a number > 0", "undefined symbol"). -- Larry Masinter (masinter@parc.xerox.com) Xerox Palo Alto Research Center (PARC) 3333 Coyote Hill Road; Palo Alto, CA USA 94304 Fax: (415) 494-4333
jeff@aiai.ed.ac.uk (Jeff Dalton) (09/13/90)
In article <1350029@otter.hpl.hp.com> sfk@otter.hpl.hp.com (Steve Knight) writes: >The type-distinctness of empty-list and false in a Lisp or Lisp-like >language is an aesthetic consideration. Many folks, and I'd include myself, >believe that making them distinct is more convenient and makes programs >more readable. Ultimately, our arguments must boil down to "I don't think >of an empty list and false in the same way. I don't think that applying >boolean operators to lists makes good programming practice." and so on. It is important to distinguish two different, but related, issues. 1. Should false and the empty list (and the symbol NIL) be distinct? 2. Should arbitrary objects other than the false value count as true, or should only one value count as true. I am happy to go either way on the first, though if pressed I'd probably prefer that the values be distinct. But on the second I feel very strongly that all non-false values should count as true. >If you are happy applying boolean operators to lists and list operators to >booleans, then you will have little inclination to change. You may even >enjoy the conciseness of idioms such as > (car (or (member x L1) (member x L2) '(()))) >which exploit the conflation of lists and booleans. This is issue number 2, but an example designed to make the "punning" look suspect. Moreover, it does not exploit the conflation of lists and booleans; it exploits the fact that any non-false value counts as true. (The key thing to notice is that MEMBER returns <false> when the item is not found. This is made clear in Scheme but not in Common Lisp, where <false> and the empty list are always the same.) >On the other hand, you may be inclined to wonder why only lists and booleans >should enjoy the benefits of conflation. For example, we could map 0 and >NIL onto one another & perhaps 1 onto TRUE. And this is issue number 1. Your article doesn't explicitly distinguish them, but I hope you would agree that that *can* be decided separately (even if you happen to think they shouldn't be). That said, let me make the following point. Arguments about issue number 1 don't necessarily apply to issue number 2. In particular, the argument that NIL, false, and the empty list ought to be distinct, and the argument that it's inconsistent (or something) to have only lists and booleans enjoy the benefits of conflation, are *not* arguments that there should be only a single value that counts as true. -- Jeff