Re: AtomList infinite or cyclic in all models

On Feb 16, 2007, at 3:02 PM, Drew McDermott wrote:

>> [Bijan Parsia]
>> [...]
>> I guess I don't have strong prior intuitions about the nature of
>> empty lists. Well, I guess I do, but then they don't involve pair/
>> cons structures *at all*.
>
> On reflection, we're both wrong, but I believe you are righter than
> I.

I was humbler too :)

>>> and if it were then
>>> testing whether a list was empty would be a nightmare.
>
> I think I was a bit too hasty here.  A list is empty if it's equal to
> nil, period.

Yep.

> Allowing the empty list to have elements is misleading
> and perhaps humorous, but strictly speaking not a problem.

I like the humor.

>> Er if the first and rest of a list is #nil, then the list is #nil.
>
> But you're wrong about this.  There must be a list with exactly one
> element, nil, and it must be distinct from nil.  Otherwise you get all
> kinds of anomalies.  (For instance, the list (nil nil) = nil,
> because rest[(nil nil)] = (nil) = nil, so (nil nil) = (nil) = nil.)

I've already acknowledged these. From my post:

"""I tried to get a problem out of list membership vs. list  
termination, e.g., '(#nil . (a . #nil)) but i don't see it. Yes, the  
car is #nil, but the cdr isn't, so the list isn't #nil. Hrm. You  
couldn't have a list of nothing but #nils, e.g., '(#nil . (#nil .  
#nil) that was distinct from #nil. Somehow, I'm not too worked up  
over that, though I guess I can imagine circumstances where it'd be  
annoying."""

Are these anomalies? I'm not so sure. It makes nil a bit more like  
the empty set. One might find that anomalous on some readings of  
lists, but not on others.

> In other words, it can be true that
>
>   If the list is #nil then its first and rest are #nil
>
> but not vice versa.

Oops, I did want to write the vice versa.

I don't see that  the collapse of all #niled lists into #nil is  
*necessarily* a problem. It's a choice and it's a choice that might  
be annoying to some and under some circumstances. If this is the  
behavior of #nil then I would strong suggests *never* using #nil as a  
placeholder in lists (like a relational NULL).  But that seems fine  
to me. And in this case it seems especially innocuous. AtomLists are  
supposed to represent syntactic structures where the empty AtomList  
isn't inherently significant. I.e., (nil nil nil) and (nil) have the  
same effect. As do (nil nil nil A) and (A).

Cheers,
Bijan.

Received on Friday, 16 February 2007 15:20:39 UTC