From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.ciao.gmane.io!not-for-mail From: Freeman Gilmore Newsgroups: gmane.lisp.guile.devel Subject: Re: alist and assq Date: Fri, 20 Mar 2020 10:39:03 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="ciao.gmane.io:159.69.161.202"; logging-data="81235"; mail-complaints-to="usenet@ciao.gmane.io" Cc: guile-devel@gnu.org To: =?UTF-8?Q?G=C3=A1bor_Boskovits?= Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Fri Mar 20 15:39:30 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 1jFIo6-000Kzc-8j for guile-devel@m.gmane-mx.org; Fri, 20 Mar 2020 15:39:30 +0100 Original-Received: from localhost ([::1]:53676 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jFIo5-0006mR-AL for guile-devel@m.gmane-mx.org; Fri, 20 Mar 2020 10:39:29 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:50491) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jFInt-0006mK-9J for guile-devel@gnu.org; Fri, 20 Mar 2020 10:39:18 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1jFIns-0002e1-4L for guile-devel@gnu.org; Fri, 20 Mar 2020 10:39:17 -0400 Original-Received: from mail-wr1-x42f.google.com ([2a00:1450:4864:20::42f]:40810) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1jFInr-0002c0-Uf for guile-devel@gnu.org; Fri, 20 Mar 2020 10:39:16 -0400 Original-Received: by mail-wr1-x42f.google.com with SMTP id f3so7762995wrw.7 for ; Fri, 20 Mar 2020 07:39:15 -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:content-transfer-encoding; bh=dzlSwnR+zyyk7PK6xCigSF9Qxt0qIgqnG6EDKQDsf0w=; b=GamtO9AYk30phETIf6KOh9G/V0r1QQMhzkVUHnTZW8OqWeBrCXk18Z1sxSrGaI6Bv2 XRXzAUMYU33iFwUeFBGHIhfkfm9VD9wRVY0/LzFMjXI6nqCNdoQ8JO6vcOxPBZ36Y3lN h7So1iu1LgXc0kiXLF7rMkb+s37FagbHgodZXP4q4R0lqHecedWxkF0lqM65hsrKT5jq x2q7m75EhmxMDtQuhUD75Kc08kZXpeLW7mpY+2d/YeEEtzkBMj+qffWBW2/59xit3cg+ id2nPpq2M5FzYVRS81s2kTOJR5Wzn1UNORQ7+OARz/rmA6E62HOaieKFOm7Y+G3wNp9c m8Qg== 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:content-transfer-encoding; bh=dzlSwnR+zyyk7PK6xCigSF9Qxt0qIgqnG6EDKQDsf0w=; b=dXlLT7VHDJQbDtL/MiKAZ2xv9hSumTgwkFPeYbHCxbKMIgAdA9STACqFQE6vf9ds3r y8upUOCG0S9pxF5xAKF3HLbe1Ll69K0O1Qv8eYzltvByf9QangvQ1uAKeHmelBNX6rrD 3e3gRZ7wm//PXUvaJLCYKpBshVBGbFiiu3TegjOFBhsEzgbAWhnWNOCbuws9oY673FPy /iFB7WyIJZDGoYKLU/vmbAktC2buhuITORE5bqLQDdmrS1WOFNIyrabA0jxL3Bu2X12W wJWfOEta9duXtEzXbcZ8zF2t9SoJ7IzVxA4d+Jab+/Oh5R2gSuTnUot0+BkkuHqpL59/ 6LLw== X-Gm-Message-State: ANhLgQ2Y1G+FmKSDJNV7/yY+FQPfUW0OGiz85KFxWLK4ZfiLA8TMm74R aBXWLP2F+0LjxWGPOmDRGpaVCZuGAOKD4vh+HxM= X-Google-Smtp-Source: ADFU+vvU44VmS2aHWgUi8Rsr297ou/E7Y/kts0lEfMEimCglzML76NxB2IbkCddO21dohWCultXyUnwycfB7WdMUL7A= X-Received: by 2002:adf:8341:: with SMTP id 59mr11443707wrd.314.1584715154431; Fri, 20 Mar 2020 07:39:14 -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::42f 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:20452 Archived-At: On Fri, Mar 20, 2020 at 2:33 AM G=C3=A1bor Boskovits = wrote: > > Hello, > > Freeman Gilmore ezt =C3=ADrta (id=C5=91pont: = 2020. m=C3=A1rc. 20., P=C3=A9n 1:45): >> >> Hi: >> >> I am not a programmer. Have some understanding of scheme. I have a qu= estion 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 ass= q and assq-ref work, what is past to the alist at the same level. Also, t= he source code would be good. > > Storing an atomic value is implementation dependent, but usually implemen= ted 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 t= here. The accessors return the buffer buffer+sizeof(atomic) respectively.) > > For lists there is a special value, the empty list. (This can be implemen= ted 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 c= ar assq). I know (assq X (alist)) but it takes more code to do (assq X my-alist), my-alist =3D (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 =3D #=E2=80=99((K1 . V1) (K2 . V2) (K3 . V2))) #(assp =E2=80=98K2 my-lis) =3D> (K2 . V2), At the source code level starting at assq. Do not care how the K=E2=80=99= s and V=E2=80=99s were place in memory or how K2 was input. The source cod= e would help but I would probably need some help stepping through it unless it is well documented. Thank you, =C6=92g > > > This is just a conceptual level, usually a modern implementation has a lo= t of optimalizations on top of that. > > An alist is a list of pairs. >> >> Thank you, =C6=92g > > Best regards, > g_bor