* alist and assq
@ 2020-03-20 0:34 Freeman Gilmore
2020-03-20 6:33 ` Gábor Boskovits
0 siblings, 1 reply; 3+ messages in thread
From: Freeman Gilmore @ 2020-03-20 0:34 UTC (permalink / raw)
To: guile-devel
[-- Attachment #1: Type: text/plain, Size: 482 bytes --]
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.
Thank you, ƒg
[-- Attachment #2: Type: text/html, Size: 1558 bytes --]
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: alist and assq
2020-03-20 0:34 alist and assq Freeman Gilmore
@ 2020-03-20 6:33 ` Gábor Boskovits
2020-03-20 14:39 ` Freeman Gilmore
0 siblings, 1 reply; 3+ messages in thread
From: Gábor Boskovits @ 2020-03-20 6:33 UTC (permalink / raw)
To: Freeman Gilmore; +Cc: guile-devel
[-- Attachment #1: Type: text/plain, Size: 1978 bytes --]
Hello,
Freeman Gilmore <freeman.gilmore@gmail.com> 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.
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)
#f
(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,
g_bor
>
[-- Attachment #2: Type: text/html, Size: 4493 bytes --]
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: alist and assq
2020-03-20 6:33 ` Gábor Boskovits
@ 2020-03-20 14:39 ` Freeman Gilmore
0 siblings, 0 replies; 3+ messages in thread
From: Freeman Gilmore @ 2020-03-20 14:39 UTC (permalink / raw)
To: Gábor Boskovits; +Cc: guile-devel
On Fri, Mar 20, 2020 at 2:33 AM Gábor Boskovits <boskovits@gmail.com> wrote:
>
> Hello,
>
> Freeman Gilmore <freeman.gilmore@gmail.com> 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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-03-20 14:39 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-03-20 0:34 alist and assq Freeman Gilmore
2020-03-20 6:33 ` Gábor Boskovits
2020-03-20 14:39 ` Freeman Gilmore
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).