From: Pramode C.E
Subject: Problem with self referential lists
Date: 
Message-ID: <ba4638f8.0205121954.4982631d@posting.google.com>
Hello,

I started learning LISP a few days back-
I use CLISP on Linux. I have a file called
`a.lsp' which contains the following code:

(setf p '(a))
(setf (cdr p) p)
(print p)

When I run it, the interpreter is eating up
all available memory. I understand that the
cdr pointer of the cons cell `p' is pointing
to itself - but what I don't understand is
why the interpreter is consuming memory.
Can anybody help? 

Thanks and Regards,
Pramode C.E
-------------------

From: Gabe Garza
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <3cwwy8ki.fsf@anubis.kynopolis.org>
··········@yahoo.co.in (Pramode C.E) writes:

> Hello,
> 
> I started learning LISP a few days back-
> I use CLISP on Linux. I have a file called
> `a.lsp' which contains the following code:
> 
> (setf p '(a))
> (setf (cdr p) p)
> (print p)
> 
> When I run it, the interpreter is eating up
> all available memory. I understand that the
> cdr pointer of the cons cell `p' is pointing
> to itself - but what I don't understand is
> why the interpreter is consuming memory.
> Can anybody help? 

Yes.

The interpreter is consuming memory because it's trying to
print a circular list as if it's non-circular.  This is a bad
thing, because it means that it will try and print it forever.

Set *PRINT-CIRCLE* to T to let the interpreter know that it's
likely to have to print circular data structures and you'll
get more graceful behaviour:

[1]> (setf *print-circle* t)
T
[2]> (setf p '(a))
(A)
[3]> (setf (cdr p) p)
#1=(A . #1#)
[4]> (print p)

#1=(A . #1#) 
#1=(A . #1#)

Gabe Garza
From: ·······@andrew.cmu.edu
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <20020513031302.I18482@emu>
BTW, you are modifying an immutable list there and that can produce
undefined results.  Use (defvar p (list 'a)) then (setf (cdr p) p) is okay.

-- 
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Kaz Kylheku
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <%dRD8.12308$a04.56421@tor-nn1.netcom.ca>
On 12 May 2002 20:54:56 -0700, Pramode C.E <··········@yahoo.co.in> wrote:
>Hello,
>
>I started learning LISP a few days back-
>I use CLISP on Linux. I have a file called
>`a.lsp' which contains the following code:
>
>(setf p '(a))
>(setf (cdr p) p)

Unfortunately, this invokes undefined behavior, because you are modifying
a literal constant. This is a problem found in some other languages;
for example in C:

  char *p = "a";
  p[0] = 'b'; /* oops */

Instead, try:

  (defvar *p* (list 'a))
  (setf (cdr *p*) *p*)

>(print p)
>
>When I run it, the interpreter is eating up
>all available memory. 

That's simply because it's trying to print the entire object,
which appears to be an infinitely long list.

Try doing this:

  (setf *print-circle* t)
  (defvar *p* (list 'a))
  (setf (cdr *p*) *p*)

Now your Lisp system will recognize the circular reference
in the list and spit out the appropriate printed representation.
From: Andy
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <3CDFFC4B.7593F679@smi.de>
Kaz Kylheku wrote:
> 
> On 12 May 2002 20:54:56 -0700, Pramode C.E <··········@yahoo.co.in> wrote:
> >Hello,
> >
> >I started learning LISP a few days back-
> >I use CLISP on Linux. I have a file called
> >`a.lsp' which contains the following code:
> >
> >(setf p '(a))
> >(setf (cdr p) p)
> 
> Unfortunately, this invokes undefined behavior, because you are modifying
> a literal constant. This is a problem found in some other languages;
> for example in C:
> 
>   char *p = "a";
>   p[0] = 'b'; /* oops */
> 
This is, in Lisp and in C, not a problem. You can image the lisp command
line
as (loop (print (eval (read))) (As a simple model).
The simple trick is that the print command per default tries to print
the hole expression. Since the CDR of p is p itself it runs forever. And
since the printer doesn't now
that it was the last part of all it keeps all intermediate results in
memory.
From that the memory usage increases.
> 
> Try doing this:
> 
>   (setf *print-circle* t)
>   (defvar *p* (list 'a))
>   (setf (cdr *p*) *p*)
> 
Just the first one is needed to work properly (at least in CLisp).
It tells print to lock for cyclic lists and the Clisp results with 
  >(setf (cdr p) p)
  #1=(A . #1#)
indicating that #1# is the structure itself.

Best regards
AHz
From: Dave Pearson
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <slrnae23p8.1kq.davep.news@hagbard.davep.org>
* Andy <···@smi.de>:

> Kaz Kylheku wrote:
>
> > Unfortunately, this invokes undefined behavior, because you are modifying
> > a literal constant. This is a problem found in some other languages;
> > for example in C:
> > 
> >   char *p = "a";
> >   p[0] = 'b'; /* oops */
>
> This is, in Lisp and in C, not a problem. [SNIP]

It is a problem in C:

,----
| ·····@hagbard:~/temp$ cat foo.c
| int main( void )
| {
|     char *p = "a";
| 
|     p[ 0 ] = 'b';
| 
|     return( 0 );
| }
| 
| ·····@hagbard:~/temp$ ./foo 
| Segmentation fault (core dumped)
`----

-- 
Dave Pearson:                   |     lbdb.el - LBDB interface.
http://www.davep.org/           |  sawfish.el - Sawfish mode.
Emacs:                          |  uptimes.el - Record emacs uptimes.
http://www.davep.org/emacs/     | quickurl.el - Recall lists of URLs.
From: Andy
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <3CE39C4B.A9AFF52A@smi.de>
Dave Pearson wrote:
> 
> It is a problem in C:
> 
> ,----
> | ·····@hagbard:~/temp$ cat foo.c
> | int main( void )
> | {
> |     char *p = "a";
> |
> |     p[ 0 ] = 'b';
> |
> |     return( 0 );
> | }
> |
> | ·····@hagbard:~/temp$ ./foo
> | Segmentation fault (core dumped)
> `----
> 
Mhh, cute (and new to me). Since the declaration of p creates a 
field with two chars length and p[0] == *p it should (IMHO) work.
Let me think about that.
Best
AHz
From: Dave Pearson
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <slrnae77sj.1ij.davep.news@hagbard.davep.org>
[If you must CC: posts, please mark them as such]

* Andy <···@smi.de>:

> Dave Pearson wrote:
> > 
> > It is a problem in C:
> > 
> > ,----
> > | ·····@hagbard:~/temp$ cat foo.c
> > | int main( void )
> > | {
> > |     char *p = "a";
> > |
> > |     p[ 0 ] = 'b';
> > |
> > |     return( 0 );
> > | }
> > |
> > | ·····@hagbard:~/temp$ ./foo
> > | Segmentation fault (core dumped)
> > `----
>
> Mhh, cute (and new to me). Since the declaration of p creates a field with
> two chars length and p[0] == *p it should (IMHO) work. 

The above code is attempting to modify a string literal. IIRC, the outcome
of such an attempt is "undefined". Dumping core is one possible, and
correct, outcome.

>                                                        Let me think about
> that.

<URL:http://www.eskimo.com/~scs/cclass/krnotes/sx8e.html> might be worth a
quick read before you do.

-- 
Dave Pearson:                   |     lbdb.el - LBDB interface.
http://www.davep.org/           |  sawfish.el - Sawfish mode.
Emacs:                          |  uptimes.el - Record emacs uptimes.
http://www.davep.org/emacs/     | quickurl.el - Recall lists of URLs.
From: Joe Marshall
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <bJNE8.5892$Bn5.2392421@typhoon.ne.ipsvc.net>
"Dave Pearson" <··········@davep.org> wrote in message ······························@hagbard.davep.org...
>
> The above code is attempting to modify a string literal. IIRC, the outcome
> of such an attempt is "undefined". Dumping core is one possible, and
> correct, outcome.
>

Making monkeys fly out of your butt is another possible, and correct,
outcome.  Far less likely, though.

`Undefined' covers a lot of ground.
From: Raymond Wiker
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <86ptzw5mlj.fsf@raw.grenland.fast.no>
Andy <···@smi.de> writes:

> Dave Pearson wrote:
> > 
> > It is a problem in C:
> > 
> > ,----
> > | ·····@hagbard:~/temp$ cat foo.c
> > | int main( void )
> > | {
> > |     char *p = "a";
> > |
> > |     p[ 0 ] = 'b';
> > |
> > |     return( 0 );
> > | }
> > |
> > | ·····@hagbard:~/temp$ ./foo
> > | Segmentation fault (core dumped)
> > `----
> > 
> Mhh, cute (and new to me). Since the declaration of p creates a 
> field with two chars length and p[0] == *p it should (IMHO) work.
> Let me think about that.
> Best
> AHz

        The declaration of p creates a _pointer_, intialised to a
string that happens to be one character long, plus a null character
for termination. The string pointed to is commonly placed in a
read-only segment of memory (in Unix-speak, the "text" segment.)

-- 
Raymond Wiker                        Mail:  ·············@fast.no
Senior Software Engineer             Web:   http://www.fast.no/
Fast Search & Transfer ASA           Phone: +47 23 01 11 60
P.O. Box 1677 Vika                   Fax:   +47 35 54 87 99
NO-0120 Oslo, NORWAY                 Mob:   +47 48 01 11 60

Try FAST Search: http://alltheweb.com/
From: Fred Gilham
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <u7offf8vt9.fsf@snapdragon.csl.sri.com>
> int main( void )
> {
>      char *p = "a";
> 
>      p[ 0 ] = 'b';
> 
>      return( 0 );
> }


It used to be allowable in C to write into string literals.

So gcc even has a backwards-compatibility flag for this:

snapdragon:~ > cat write-me.c
int main( void )
 {
     char *p = "a";

     p[ 0 ] = 'b';

     return( 0 );
 }

snapdragon:~ > gcc -fwritable-strings -o write-me write-me.c
snapdragon:~ > ./write-me
snapdragon:~ > gcc -o write-me write-me.c
snapdragon:~ > ./write-me
Bus error (core dumped)
snapdragon:~ > 

-- 
Fred Gilham                                    ······@csl.sri.com
Do remember you're there to fuddle him.  From the way some of you
young fiends talk, anyone would suppose it was our job to teach!
                          -- The Screwtape Letters, C. S. Lewis
From: Nils Goesche
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <lk7km2oqpn.fsf@pc022.bln.elmeg.de>
Fred Gilham <······@snapdragon.csl.sri.com> writes:

> > int main( void )
> > {
> >      char *p = "a";
> > 
> >      p[ 0 ] = 'b';
> > 
> >      return( 0 );
> > }
> 
> 
> It used to be allowable in C to write into string literals.

No.  The behavior was and still is undefined, so any compiler is free
to do whatever it likes.  gcc changed its default behavior, that's all.

Regards,
-- 
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x42B32FC9
From: Kaz Kylheku
Subject: Re: Problem with self referential lists
Date: 
Message-ID: <slrnae8195.hku.kaz@localhost.localdomain>
On Thu, 16 May 2002 13:47:23 +0200, Andy <···@smi.de> wrote:
>Dave Pearson wrote:
>> 
>> It is a problem in C:
>> 
>> ,----
>> | ·····@hagbard:~/temp$ cat foo.c
>> | int main( void )
>> | {
>> |     char *p = "a";
>> |
>> |     p[ 0 ] = 'b';
>> |
>> |     return( 0 );
>> | }
>> |
>> | ·····@hagbard:~/temp$ ./foo
>> | Segmentation fault (core dumped)
>> `----
>> 
>Mhh, cute (and new to me). Since the declaration of p creates a 
>field with two chars length and p[0] == *p it should (IMHO) work.
>Let me think about that.

The point is that the declaration creates a *literal constant* object.  Yes, it
is an array of two char; it occupies at least two bytes of storage which a
pointer can reference.  But the behavior is not defined if you try to modify
that storage.

Lisp is the same way. Modify a quoted list and you are doing something
undefined and nonportable.

One implication of these rules is that language implementations are free to
place constant objects into read-only storage, such as virtual memory pages
that have read-only permissions. Or into actual ROM, like if you are generating
an image for an embedded system.

Some C compilers on Unix systems intersperse string literals among the
executable code. The code gets loaded into write-protected pages, protecting
the literals with it. This is the likely cause for the crash reproduced
by Dave Pearson's program above.

The second implication of these rules is that multiple occurences equivalent
constant objects can be folded into fewer instances, or perhaps into one
program-wide instance. Since the programmer has agreed to write the program
such that it does not modify the data, the program cannot be affected by this
folding, insofar as it does not rely on pointer comparisons in C, or EQ in
Lisp.

Constant data which is optimized into a compiled program's or function's image
can be a big efficiency improvement. Consider that '(1 2) does not have to cons
anything; whenever evaluated, it can just retrieve a pointer to the
same pre-computed list object.