[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: alist and assq

From: Gábor Boskovits
Subject: Re: alist and assq
Date: Fri, 20 Mar 2020 07:33:15 +0100


Freeman Gilmore <address@hidden> ezt írta (időpont: 2020. márc. 20., Pén 1:45):

I am not a programmer.  Have some understanding of scheme.   I have a question that I cannot find the answer to on the net.    I joined this group to ask if someone would help me find the answer.   

I am looking for a manual or whatever that will explain in detail how an alist is stored in memory and how it works at this level.    Also, how assq and assq-ref work, what is past to the alist at the same level.   Also, the source code would be good.

Storing an atomic value is implementation dependent, but usually implemented by a type tagged structure.
(You can think about this as a tuple of a type, buffer, where buffer is a length,pointer there are several optimizations, but this is a possibility).

A pair is a structure holding two atomics with accessors to them.
(Possible implementation:
Type:pair, buffer is twice as long as an atomic, two atomics are stored there. The accessors return the buffer buffer+sizeof(atomic) respectively.)

For lists there is a special value, the empty list. (This can be implemented by setting the pointer to null)

A list is stored as a pair where the first member is a value, the current first element, and the second is a list, the current tail.

An alist is a list of pairs.

Assq and assq-ref is just a find with a predicate on the first element of the pair eq to the value passed in as key. Actually assq-ref is (compose car assq).

What find does is that it recurses on the list. It is something like:
(define (find pred list)
 (if (empty list)
      (if (pred (car list))
           (car list)
           (find pred (cdr list)))))

I hope it helps.

This is just a conceptual level, usually a modern implementation has a lot of optimalizations on top of that.

An alist is a list of pairs.

Thank you, ƒg  

Best regards,

reply via email to

[Prev in Thread] Current Thread [Next in Thread]