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

[Alan Post]

On Thu, Nov 04, 2010 at 10:39:19PM +0530, Enwin Thun wrote:
> 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.  A link for general discussion about memory management
> in scheme would also be nice.
> 
> Thanks.
> 

Typically, all objects in a scheme system are stored with a tag,
indicating the object type.  Basically, whether it is an atom or a
cons.

For an atom, the data is stored immediately after the tag.

For a cons cell (which is how lists are constructed) two pointers
are stored, the 'car' and 'cdr' pointers.  These point to other
tagged objects.

lists are composed of multiple cons cells.  In the simplest to
imagine case, a cons cell has a car pointer to an atom and a cdr
pointer to another cons.

Here is more information, including a diagram:

  http://en.wikipedia.org/wiki/Cons
  http://en.wikipedia.org/wiki/Car_and_cdr

This article is a good introduction to lisp, but not exactly what
you're asking for:

  http://www.paulgraham.com/rootsoflisp.html

I'd recommend this book for learning about Garbage Collection:

  
http://www.amazon.com/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484/ref=sr_1_1?ie=UTF8&qid=1288891672&sr=8-1

But you would probably enjoy reading Henry Baker's paper, which
inspired the garbage collector in Chicken Scheme.

I've implemented a small (but not the smallest!) lisp interpreter:

http://makeutil.cvs.sourceforge.net/viewvc/makeutil/makeutil/b00t.c?revision=1.2&view=markup

The garbage collector there is a copying garbage collector that is
in the same family of garbage collectors as Henry Baker's method.

The size of the code might be some help in understanding how parts
of the system are implemented.


> (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)))))
> 
> _______________________________________________
> Chicken-users mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/chicken-users

-- 
.i ko djuno fi le do sevzi