I am wondering about the cons cell representation of NIL.
For example, with '(1 2) , is the representation like this:

+---.---+ +---.---+ +---.---+
| 1 | .---->| 2 | .---->| | |
+---.---+ +---.---+ +---.---+
?

Notice on the representation of NIL. Is this always an empty cons cell?
Is it safe to say that all proper lists end with an empty cons cell?

Daniel Cerqueira <dan.list@brilhante.top> writes:
>Notice on the representation of NIL. Is this always an empty cons cell?

NIL is a special value that is /not/ the same as `(NIL . NIL),
which is a dotted pair ("cell") with its CAR and CDR being NIL.

The notation `() for NIL does /not/ mean that NIL is represented
by an empty cons cell.

`(1 2) is `( 1 . ( 2 . NIL )).

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>Notice on the representation of NIL. Is this always an empty cons cell?
>
> NIL is a special value that is /not/ the same as `(NIL . NIL),
> which is a dotted pair ("cell") with its CAR and CDR being NIL.

You are defining NIL with NIL, which is a poor, and confusing teaching.

> The notation `() for NIL does /not/ mean that NIL is represented
> by an empty cons cell.
>
> `(1 2) is `( 1 . ( 2 . NIL )).

Then, if NIL is not represented by an empty cons cell, how is NIL
represented?

Daniel Cerqueira wrote:
> Then, if NIL is not represented by an empty cons cell, how is NIL
> represented?

NIL is a symbol (and also an (empty) list). Its internal representation
is not specified by the standard.

Daniel Cerqueira <dan.list@brilhante.top> writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>
>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>>Notice on the representation of NIL. Is this always an empty cons cell?
>>
>> NIL is a special value that is /not/ the same as `(NIL . NIL),
>> which is a dotted pair ("cell") with its CAR and CDR being NIL.
>
> You are defining NIL with NIL, which is a poor, and confusing teaching.
>
>> The notation `() for NIL does /not/ mean that NIL is represented
>> by an empty cons cell.
>>
>> `(1 2) is `( 1 . ( 2 . NIL )).
>
> Then, if NIL is not represented by an empty cons cell, how is NIL
> represented?

nil is a predefined symbol which has itself as its value. The same goes
for t, as well as any symbol in the keyword package.

So,

(eq nil 'nil) => t
(eq t 't) => t

(eq (cons nil nil) nil) => nil

Note also:
(eq (cons nil nil) (cons nil nil)) => nil

So, in general, a cons cell with nil as car and cdr is not identical to
any other cons cell with car=cdr=nil.

A possibly useful comparison might be with NULL or null in lesser
programming languages, and None in even lesserer languages.

Lars Brinkhoff <lars.spam@nocrew.org> writes:
>NIL is a symbol (and also an (empty) list). Its internal representation
>is not specified by the standard.

A symbol is an entity of the source-code model.

A list is an entity of the runtime model.

So, NIL "is" a symbol and a list (and also an atom), but on two
different layers: In the source code it's a symbol, and the value of
that symbol when it is being evaluated at runtime is the empty list.

Models always contain entities which are not defined by
being a kind of a more fundamental entity, because it is
not possible to define every entity in that manner. But such
entities are defined by their relations to other entities.

Not defining the representation of entities gives Lisp the
flexibility to be implemented in various ways on various machines.
But it takes some time to get used to this kind of abstract thinking
where abstract models replace specific internal representations.

ram@zedat.fu-berlin.de (Stefan Ram) writes:
>A symbol is an entity of the source-code model.

Well, the /name/ of the symbol is the actual entity of the
source-code model.

On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
> I am wondering about the cons cell representation of NIL.

Nil isn't formally a cons cell.

> For example, with '(1 2) , is the representation like this:
>
> +---.---+ +---.---+ +---.---+
> | 1 | .---->| 2 | .---->| | |
> +---.---+ +---.---+ +---.---+

A CL implementation can represent nil in any way it wants as long as it
is consistent with the language. It is possible for nil to *internally*
be a cons cell object (provided it's only one global object).

> Notice on the representation of NIL. Is this always an empty cons cell?

In some impelmentations, it's not a heap allocated object at all, but
a special unboxed value.

Formally, nil is of symbol type. (symbolp nil) has to yield true,
and everything has to work: (symbol-name nil), (symbol-package nil).

In a system where nil is a special bit pattern, and not a pointer
to a symbol object, all those functions have to check for nil as
a special case.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>
>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>>Notice on the representation of NIL. Is this always an empty cons cell?
>>
>> NIL is a special value that is /not/ the same as `(NIL . NIL),
>> which is a dotted pair ("cell") with its CAR and CDR being NIL.
>
> You are defining NIL with NIL, which is a poor, and confusing teaching.

Nonetheless, it *could* work that way. NIL could be internally
represented as a cons cell, whose CAR and CDR are NIL (i.e. that
cell it points to itself).

If it is done correctly, the application cannot tell.

I've not heard of that implementation strategy.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Am 2024-01-27 um 13:39 schrieb Daniel Cerqueira:
> Notice on the representation of NIL. Is this always an empty cons cell?

no.

because, you have a Chain, in LISP, it is a LIST.
You can push Integer Numbers like you want on the "given" LIST.

Firstly, you have to understand, that what you do in LISP have
a left Hand side, and a right Hand side.

( 1 2 ) is a List
(+ 1 2 ) is a Operation - addition, because the Operator at the
second character is a Function.
This Function add the Term aka RPN (reverse polish notation).
The rpn is built stright forward:
1. push first number on the stack, here: 2
2. push second number on the stack, here: 1
3. push operator on the stack, here: +
As Result, the value is 3.

Internaly, you have this representation of ( 1 2 )

1. The value: 1 - is the Chain Part, beginning with Index: 0
2. A internal Pointer to the next Chain Part (the nex one is: 2) will
be "point" to the Memory Data in the Computer System, by LISÜ self.
So the first form has the following pseudo: ( 1 ptr-to )

3. The new LIST have: ( ptr-from 2 )

4. When you push a new value to the LIST, you have the Form:
( 1 ptr-to )
-->
( ptr-from 2 )
-->
( ptr-from 3 )

5. The User/Programmers-View is: ( 1 2 3 )
There, you have a set of the power of three Elements.
But you may be can use the Informations that I have give you (above),
to thinking on, that's are sixx Elements (the Pointers).

--
Diese E-Mail wurde von Avast-Antivirussoftware auf Viren geprüft.
www.avast.com

On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
> I am wondering about the cons cell representation of NIL.
> For example, with '(1 2) , is the representation like this:
>
> +---.---+ +---.---+ +---.---+
> | 1 | .---->| 2 | .---->| | |
> +---.---+ +---.---+ +---.---+
> ?
>
> Notice on the representation of NIL. Is this always an empty cons cell?
> Is it safe to say that all proper lists end with an empty cons cell?

It is safe to say that all proper lists have an empty proper list
as their suffix! That empty list is nil.

What is the suffix of (a)? It is () / NIL, which you can obtain
using (cdr '(a)) or (rest '(a)).

An empty list isn't a cons cell in Common Lisp and similar
dialects; it is the symbol NIL.

Note that (consp nil) is required to be false; i.e. it must
return nil. Even if the implementation of NIL is a cons cell
internally, that object must not report as a cons cell.

(typeof nil) -> NULL

(consp nil) -> NIL

(atom nil) -> T

(symbolp nil) -> T

(symbol-package nil) -> #<package COMMON-LISP>

(The #<package COMMON-LISP> will look different in your implementation;
The #< characters introduce an implementation-specific notation
that is not machine-readable.)

NIL is defined by properties. Whatever kind of object it is, it
has to satisfy the properties.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

* Kaz Kylheku <20240127090616.827@kylheku.com> :
Wrote on Sat, 27 Jan 2024 17:09:26 -0000 (UTC):

> On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
>> I am wondering about the cons cell representation of NIL.
>
> Nil isn't formally a cons cell.
>
>> For example, with '(1 2) , is the representation like this:
>>
>> +---.---+ +---.---+ +---.---+
>> | 1 | .---->| 2 | .---->| | |
>> +---.---+ +---.---+ +---.---+
>
> A CL implementation can represent nil in any way it wants as long as it
> is consistent with the language. It is possible for nil to *internally*
> be a cons cell object (provided it's only one global object).

(consp nil) has to be true. NIL cannot be of type CONS.

It makes no sense to say NIL can be implemented using a "cons cell object"

>> Notice on the representation of NIL. Is this always an empty cons cell?

No NIL is not a cons cell.

> In some impelmentations, it's not a heap allocated object at all, but
> a special unboxed value.
>
> Formally, nil is of symbol type. (symbolp nil) has to yield true,
> and everything has to work: (symbol-name nil), (symbol-package nil).
>
> In a system where nil is a special bit pattern, and not a pointer
> to a symbol object, all those functions have to check for nil as
> a special case.

Madhu <enometh@meer.net> writes:

> * Kaz Kylheku <20240127090616.827@kylheku.com> :
> Wrote on Sat, 27 Jan 2024 17:09:26 -0000 (UTC):
>
>> On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
>>> I am wondering about the cons cell representation of NIL.
>>
>> Nil isn't formally a cons cell.
>>
>>> For example, with '(1 2) , is the representation like this:
>>>
>>> +---.---+ +---.---+ +---.---+
>>> | 1 | .---->| 2 | .---->| | |
>>> +---.---+ +---.---+ +---.---+
>>
>> A CL implementation can represent nil in any way it wants as long as it
>> is consistent with the language. It is possible for nil to *internally*
>> be a cons cell object (provided it's only one global object).
>
>
> (consp nil) has to be true. NIL cannot be of type CONS.
>
> It makes no sense to say NIL can be implemented using a "cons cell object"

Thanks Madhu. That simple explanation makes perfect sense. Didn't
thought of that. ;-)

Daniel Cerqueira <dan.list@brilhante.top> writes:

> Madhu <enometh@meer.net> writes:
>
>> * Kaz Kylheku <20240127090616.827@kylheku.com> :
>> Wrote on Sat, 27 Jan 2024 17:09:26 -0000 (UTC):
>>
>>> On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
>>>> I am wondering about the cons cell representation of NIL.
>>>
>>> Nil isn't formally a cons cell.
>>>
>>>> For example, with '(1 2) , is the representation like this:
>>>>
>>>> +---.---+ +---.---+ +---.---+
>>>> | 1 | .---->| 2 | .---->| | |
>>>> +---.---+ +---.---+ +---.---+
>>>
>>> A CL implementation can represent nil in any way it wants as long as it
>>> is consistent with the language. It is possible for nil to *internally*
>>> be a cons cell object (provided it's only one global object).
>>
>>
>> (consp nil) has to be true. NIL cannot be of type CONS.

I think you meant to write "NIL" (or maybe "not true").

>> It makes no sense to say NIL can be implemented using a "cons cell object"
>
> Thanks Madhu. That simple explanation makes perfect sense. Didn't
> thought of that. ;-)

Simple but not entirely accurate! Kaz said that the implementation can
use any representation it wants *internally* provided it is consistent
with the language. Since the implementation also defines consp (and
atom, etc.), it can return NIL when passed that internal representation
which can indeed be a cons cell.

I've seen it done, though not in a Common Lisp implementation.

--
Ben.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Daniel Cerqueira <dan.list@brilhante.top> writes:
>
>> Madhu <enometh@meer.net> writes:
>>
>>> * Kaz Kylheku <20240127090616.827@kylheku.com> :
>>> Wrote on Sat, 27 Jan 2024 17:09:26 -0000 (UTC):
>>>
>>>> On 2024-01-27, Daniel Cerqueira <dan.list@brilhante.top> wrote:
>>>>> I am wondering about the cons cell representation of NIL.
>>>>
>>>> Nil isn't formally a cons cell.
>>>>
>>>>> For example, with '(1 2) , is the representation like this:
>>>>>
>>>>> +---.---+ +---.---+ +---.---+
>>>>> | 1 | .---->| 2 | .---->| | |
>>>>> +---.---+ +---.---+ +---.---+
>>>>
>>>> A CL implementation can represent nil in any way it wants as long as it
>>>> is consistent with the language. It is possible for nil to *internally*
>>>> be a cons cell object (provided it's only one global object).
>>>
>>>
>>> (consp nil) has to be true. NIL cannot be of type CONS.
>
> I think you meant to write "NIL" (or maybe "not true").
>
>>> It makes no sense to say NIL can be implemented using a "cons cell object"
>>
>> Thanks Madhu. That simple explanation makes perfect sense. Didn't
>> thought of that. ;-)
>
> Simple but not entirely accurate! Kaz said that the implementation can
> use any representation it wants *internally* provided it is consistent
> with the language. Since the implementation also defines consp (and
> atom, etc.), it can return NIL when passed that internal representation
> which can indeed be a cons cell.
>
> I've seen it done, though not in a Common Lisp implementation.

Ok, thanks Ben.