[Chicken-users] Re: General newbie query about tspl execise

[Pascal J. Bourguignon]

Enwin Thun <address@hidden> writes:

> Please redirect me if this is inappropriate for this forum.
>
> The following code appears in the tspl book.
> <http://www.scheme.com/tspl3/start.html#./start:s185>
>
> It is an "implementation of a queue use[ing] a tconc structure".
>
> To put new elements into the end of the list, it is required that the
> 2 'ignored atoms are really the same.
>
> This makes me curious about how atoms and lists are stored.  I am
> looking for a link that explains this in terms of memory addresses,
> pointers, etc.  


LiSP explains how to implement a lisp (presenting mostly scheme
interpreters and compilers).


LiSP   = "Lisp in Small Pieces"  
         http://pagesperso-systeme.lip6.fr/Christian.Queinnec/WWW/LiSP.html
         
http://pagesperso-systeme.lip6.fr/Christian.Queinnec/Books/LiSP-2ndEdition-2006Dec11.tgz
         This book covers Lisp, Scheme and other related dialects,
         their interpretation, semantics and compilation. To sum it up
         in a few figures: 500 pages, 11 chapters, 11 interpreters and
         2 compilers.


> A link for general discussion about memory management
> in scheme would also be nice.

Anything about garbage collection / garbage collectors.

You will find a lot here:  http://www.schemers.org/Documents/



> (define make-queue
>   (lambda ()
>     (let ((end (cons 'ignored '())))
>       (cons end end))))
>
> (define putq!
>   (lambda (q v)
>     (let ((end (cons 'ignored '())))
>       (set-car! (cdr q) v)
>       (set-cdr! (cdr q) end)
>       (set-cdr! q end))))
>
> (define getq
>   (lambda (q)
>     (car (car q))))
>
> (define delq!
>   (lambda (q)
>     (set-car! q (cdr (car q)))))

Perhaps a little diagram will help:

scheme> (let ((q (make-queue)))
          (map (lambda (e) (putq! q e)) '(1 two "Three" 4))
          (com.informatimago.common-lisp.picture.cons-to-ascii:draw-list
               q :title "queue of (1 two \"Three\" 4)"))

+-------------------------------------------------------------+
| queue of (1 two "Three" 4)                                  |
|                                                             |
| +---+---+   +---+---+                                       |
| | * | * |-->| * |NIL|                                       |
| +---+---+   +---+---+                                       |
|   |           |                                             |
|   |           v                                             |
|   |         +---------+                                     |
|   |         | ignored |                                     |
|   |         +---------+                                     |
|   v                                                         |
| +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   |
| | * | * |-->| * | * |-->| * | * |-->| * | * |-->| * |NIL|   |
| +---+---+   +---+---+   +---+---+   +---+---+   +---+---+   |
|   |           |           |           |           |         |
|   v           v           v           v           v         |
| +---+       +-----+     +---------+ +---+       +---------+ |
| | 1 |       | two |     | "Three" | | 4 |       | ignored | |
| +---+       +-----+     +---------+ +---+       +---------+ |
+-------------------------------------------------------------+


Cons cells are represented by little boxes with two pointers.
Notice however that NIL is not represented by a pointer to a symbol NIL,
but directly inside the cons cell.

Also, there are pointers to boxes representing the small numbers 1 and
4.  Most probably, integers smaller than a pointer will be represented
in-line and actually stored in the cons cell.

Also, the box for the symbol ignored is duplicated, but it is more
probable that there is a single box with the two arrows pointing to it.
But not necessarily.

The point is that there is not mandatory way to implement the memory of
a lisp or scheme, as long as the external properties are respected.
Implementations can use pointers or keep copies of _immutable_ values.  

Some implementations of lisp used vectors to store lists ("cdr coding"),
so even the little cons cell boxes may not really be implemented by
discrete structures.


So there is no definitive answer to your question in general.


Since you're asking it on the chicken mail-list, what you can do is
download the sources of chicken, and see by yourself how it's
implemented. http://code.call-cc.org/


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.