Re: alist and assq

[Freeman Gilmore]

On Fri, Mar 20, 2020 at 2:33 AM Gábor Boskovits <address@hidden> wrote:
>
> Hello,
>
> Freeman Gilmore <address@hidden> ezt írta (időpont: 2020. márc. 20., Pén 
> 1:45):
>>
>> Hi:
>>
>> 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.

I know that in a pair the is a key that points to a value ant the pair
points to the next pair in the alist.

>
>
> 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).

I know (assq X (alist))  but it takes more code to do (assq X my-alist),
  my-alist = (alist)

>
>
> What find does is that it recurses on the list. It is something like:
> (define (find pred list)
>  (if (empty list)
>       #f
>       (if (pred (car list))
>            (car list)
>            (find pred (cdr list)))))
>
> I hope it helps.

What I am looking for is a step by step through the complete procedure,

my-alist = #’((K1 . V1) (K2 . V2) (K3 . V2)))
#(assp ‘K2 my-lis) => (K2 . V2),

At the source code level starting at assq.   Do not care how the K’s
and V’s were place in memory or how K2 was input.    The source code
would help but I would probably need some help stepping through it
unless it is well documented.

Thank you, ƒg

>
>
> 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,
> g_bor