From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.ciao.gmane.io!not-for-mail From: =?UTF-8?Q?G=C3=A1bor_Boskovits?= Newsgroups: gmane.lisp.guile.devel Subject: Re: alist and assq Date: Fri, 20 Mar 2020 07:33:15 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="00000000000099f20105a1437682" Injection-Info: ciao.gmane.io; posting-host="ciao.gmane.io:159.69.161.202"; logging-data="84654"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-devel@gnu.org To: Freeman Gilmore Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Fri Mar 20 07:33:50 2020 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1jFBE5-000LuT-K9 for guile-devel@m.gmane-mx.org; Fri, 20 Mar 2020 07:33:49 +0100 Original-Received: from localhost ([::1]:46480 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jFBE4-0005oj-5d for guile-devel@m.gmane-mx.org; Fri, 20 Mar 2020 02:33:48 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:47092) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jFBDo-0005oZ-AR for guile-devel@gnu.org; Fri, 20 Mar 2020 02:33:33 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1jFBDn-0007Un-2p for guile-devel@gnu.org; Fri, 20 Mar 2020 02:33:32 -0400 Original-Received: from mail-wm1-x334.google.com ([2a00:1450:4864:20::334]:33061) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1jFBDm-0007P3-S2 for guile-devel@gnu.org; Fri, 20 Mar 2020 02:33:31 -0400 Original-Received: by mail-wm1-x334.google.com with SMTP id r7so6458430wmg.0 for ; Thu, 19 Mar 2020 23:33:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=/gCxDdqEr/N2EJTcHKTDC3Qh6C6BgFQFiO+3TuaJzkM=; b=qYNzeSSBpfpycRvpYHukuj4I1+TGCIPP6WPhSB2RERgX4SV4WiQ/Kf8vqoM7+wSEBx qNnfqIysGUsrSA103JQTB9oeFmCB0hsz52LyVp3OVCEJeHXLiMSCaqqyyQgQJwH1JBkI 6HnTSMbiXROR/N6zNrrgpEql+PHkEk+IM/3dT2ns3gaZtaUl5wwZVgJ2rSTpVrWJmno7 2xDp7cB+zTPyFKEgx3P8sF3akioMGDK/89+YxxVdsBGDqynfgG0uNc7no7qzDurW/uwZ EXM3thFSoHiFyXnLkDT1beRUOgwIQa6PfzC/FJTtCkct/tizQcPFte9bBmRYtmBtAw0D wcmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=/gCxDdqEr/N2EJTcHKTDC3Qh6C6BgFQFiO+3TuaJzkM=; b=h58xzvI+UPXhLil2fDAZYN7/hkzUz7JtxAXblMHwrQtgy/iiuQjN11DIOsB0So1D0w Eb9A7sN5SWBOdKkJdlH55tJrWWPWEstmpJq/yNFn4A0f6X0DSVW6q44AJoHfwNCpX6zH T4WC2g2lWA+cWKVSIXDIANDZq084GnLJCJtPJwLkD6PZNBo5GgPKwRBTNEv2nN+wL+1J Y5Lg54PV+/kBeffdyqFiSsJk0mEnbi+2FQz3DUbA2R0XSUslDqtP0OYTcIrKw9Y0BgGl wSKXhBClkYQKQIbJJeQhoSKvmF5Y1ukepUarw1gMrAyJuEbUutYmaecPckJK5tgza0xl 4KTg== X-Gm-Message-State: ANhLgQ0wyaa43oD27ohoZBhsJ/MKY4M9aCUkyHvm8PPJfn5JIo8nhkXq BMgpbIBDDS5s3gxCKbduFwyMLs0vhsTpyr7cgw== X-Google-Smtp-Source: ADFU+vvbwcrRnQ9p8K+SK0yfnTjtdrSQWATrdcVoe/w1uQHnxN2nQrh+FjhXzfb1K8SSrG5QP9lMBgLf4jKis8hSRaU= X-Received: by 2002:a1c:750f:: with SMTP id o15mr8426691wmc.145.1584686008233; Thu, 19 Mar 2020 23:33:28 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::334 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:20451 Archived-At: --00000000000099f20105a1437682 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hello, Freeman Gilmore ezt =C3=ADrta (id=C5=91pont: 20= 20. m=C3=A1rc. 20., P=C3=A9n 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 as= sq > 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, =C6=92g > Best regards, g_bor > --00000000000099f20105a1437682 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello,

Freeman Gilmore <freeman.gilmore@gmail.com> ezt =C3=ADrta (id=C5=91p= ont: 2020. m=C3=A1rc. 20., P=C3=A9n 1:45):
Hi:

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

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

Storing an atomic value = is implementation dependent, but usually implemented by a type tagged struc= ture.
(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:pa= ir, 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 valu= e, the empty list. (This can be implemented by setting the pointer to null)=

A list is stored as a p= air where the first member is a value, the current first element, and the s= econd 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 fi= rst 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)
=C2=A0(if= (empty list)
=C2=A0 =C2=A0 =C2=A0 #f
=C2=A0 =C2=A0 =C2=A0 (if (pred (car list))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(car list)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(find pred (cdr list)))))

I hope it helps.

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

An alist is a list of pair= s.

Thank you, =C6=92g =C2=A0

Best regards,
g_bor
--00000000000099f20105a1437682--