From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp11.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id oHfhJP8P2WGmlQAAgWs5BA (envelope-from ) for ; Sat, 08 Jan 2022 05:15:59 +0100 Received: from aspmx1.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp11.migadu.com with LMTPS id IJs2Iv8P2WEYFgAA9RJhRA (envelope-from ) for ; Sat, 08 Jan 2022 05:15:59 +0100 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id C3ED02F707 for ; Sat, 8 Jan 2022 05:15:58 +0100 (CET) Received: from localhost ([::1]:35774 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1n6393-0008Sr-Ui for larch@yhetil.org; Fri, 07 Jan 2022 23:15:57 -0500 Received: from eggs.gnu.org ([209.51.188.92]:42566) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1n638A-0008SJ-W1 for guix-patches@gnu.org; Fri, 07 Jan 2022 23:15:04 -0500 Received: from debbugs.gnu.org ([209.51.188.43]:53293) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1n638A-0003HN-Lh for guix-patches@gnu.org; Fri, 07 Jan 2022 23:15:02 -0500 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1n638A-0001VC-EX for guix-patches@gnu.org; Fri, 07 Jan 2022 23:15:02 -0500 X-Loop: help-debbugs@gnu.org Subject: [bug#51838] [PATCH v6 03/41] guix: node-build-system: Add JSON utilities. Resent-From: Philip McGrath Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Sat, 08 Jan 2022 04:15:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 51838 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: Liliana Marie Prikler , 51838@debbugs.gnu.org Cc: Timothy Sample , Pierre Langlois , Jelle Licht , Leo Famulari Received: via spool by 51838-submit@debbugs.gnu.org id=B51838.16416152455649 (code B ref 51838); Sat, 08 Jan 2022 04:15:02 +0000 Received: (at 51838) by debbugs.gnu.org; 8 Jan 2022 04:14:05 +0000 Received: from localhost ([127.0.0.1]:46190 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n637E-0001T3-PM for submit@debbugs.gnu.org; Fri, 07 Jan 2022 23:14:05 -0500 Received: from mail-ua1-f50.google.com ([209.85.222.50]:33287) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n637B-0001SH-0p for 51838@debbugs.gnu.org; Fri, 07 Jan 2022 23:14:04 -0500 Received: by mail-ua1-f50.google.com with SMTP id u6so13878394uaq.0 for <51838@debbugs.gnu.org>; Fri, 07 Jan 2022 20:14:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=philipmcgrath.com; s=google; h=message-id:date:mime-version:user-agent:subject:content-language:to :cc:references:from:in-reply-to:content-transfer-encoding; bh=1jDfLbRj4g/OzOn8O30S74yo9i+PD4Cj2osyEyIAwHk=; b=cqSnMmEIC7pw2STrE2aH5EPZx8uR0QucYgztHUrF86k0gldSHyS17lz4XhgZRXzVHU SVwZ4cPR84nNUj8LNIUqvUFkIdiIewvbDQGHxChgFN+/jky9kGR+r40ueR1scBpC5lsZ 3sGM8Qo5FjVqhA88xDYQUUpxZmmMSzdFFrjauafMjV7KS2nAxfeq8cwbjj2LZO+3MiD4 npJCxU9k240UjKOUblQ2PDUc/94xpcTRDlGgPU/z3+6J7hE7g7FH99Sw4csJms7VBbg9 PcDWosfDVFM2V9MHPOuq9hLUO+80+XU0q+bTGNDBXg8sBjzCNzEnVBznG9Ow7gljE0pj s/9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:cc:references:from:in-reply-to :content-transfer-encoding; bh=1jDfLbRj4g/OzOn8O30S74yo9i+PD4Cj2osyEyIAwHk=; b=64jiCGrgsNFsAPRvfOWnuZSjTPiFA12eK8iKV5WWi5nVooP44p+UE5gM2SuaczUO2E ccxybvDUeK7EFMpry72YllJaF3QCEANuhNqw+SAuGDADG7PQ0h9zB9cs4JZ23AYGG/4c uZAMfK3dAqjf3WUKmoI/76BSKJ1XWS0FjoyRsebAsezOH6E0TUV60W8NJF2IAev6+BGx 7cklxiKNAsrywatooMeWaI3F769ckQEQeK1QYWsHAOpNdU741f/Ko7cRvo4R/OWT7kXD UbJBo4cXMKg87HKohEQt/a7/i4S/R2I393K1sN9XOCc95daRPoE2CUMsYI7nKsMOKzp2 h7mg== X-Gm-Message-State: AOAM533VhNX7ETpVciF71kzAXdrCcCfZraCZeZOt5gxE+wAuTcCAvhOu 4huN4ZKKVRC9uPJdTn3R1BtWCA== X-Google-Smtp-Source: ABdhPJwXrnBQa1YuoL8Evs5bCx2OVvpcVU/0ooxS2kMfYiwwvbg8mzCaO6az592rdB2TI0n6FhRR4g== X-Received: by 2002:ab0:6813:: with SMTP id z19mr22410695uar.28.1641615235501; Fri, 07 Jan 2022 20:13:55 -0800 (PST) Received: from [192.168.45.37] (c-73-125-89-242.hsd1.fl.comcast.net. [73.125.89.242]) by smtp.gmail.com with ESMTPSA id k135sm345428vke.53.2022.01.07.20.13.54 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 07 Jan 2022 20:13:55 -0800 (PST) Message-ID: <70c1a8ec-c2fb-74b3-1061-2178dfb21ca8@philipmcgrath.com> Date: Fri, 7 Jan 2022 23:13:54 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.3.1 Content-Language: en-US References: <082a81964a43ae5f735ad2ca433d0dfe00859c35.camel@gmail.com> <20211230073919.30327-1-philip@philipmcgrath.com> <20211230073919.30327-4-philip@philipmcgrath.com> <6fde49a1b469be7f14524e902fc91cd3eb4f3d41.camel@gmail.com> From: Philip McGrath In-Reply-To: <6fde49a1b469be7f14524e902fc91cd3eb4f3d41.camel@gmail.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: "Guix-patches" X-Migadu-Flow: FLOW_IN X-Migadu-Country: US ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1641615359; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:resent-cc: resent-from:resent-sender:resent-message-id:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post:dkim-signature; bh=1jDfLbRj4g/OzOn8O30S74yo9i+PD4Cj2osyEyIAwHk=; b=iXIIUzOpyQPCuXCGKxwREvDOhePOpSP33GgIBFcS968JVdl4uR6WvCBbY97S+r1iXCSURL NhD/wPRU74kgFM3hy3Ch+9CJ94VOjGYwhXTWaZsA0J+oKa82v1EsnKKfNp78QtEr33J8px DpvflyD42ixi91YSz8HbBygrJZKjYldYEQNsItzGIa1BRUC0c+GRUUyR7qLSe56DOHKFUB xh28qbvToBxp/AAb2PatwR6ziDtPPaket30UyRVScY27HE3Tk5M7yO8fJyPzQ91YdsvnEB 9lD7MGuPXvDEM4BWXyuXf1kZQXviDMPKqXwIQPi6opvFv8ZT+UvV2Q2Ndo+V4g== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1641615359; a=rsa-sha256; cv=none; b=ccT0z5v5cARrVimU0mPwxfz8zePNS5TBGLHnE6Hicg7s+oTYFY6RcoKBSV3ImHIcJeT4wY qJNiVm3Kzc4C02EF9VEZN+Ke4Q5u9FLXpopjUFDqOQbK2uBBhSIF+D/c2W1j+h73yR23DS g//dX9LmN9VRz2lAQL2YdyBIqnKyVOAUp12qCENuU+47FP1rG52d6f/Hgz0ue6a5wOOUNv tcFPjLyjDkWS4lDheSkOD8wHC3pJU04KbDIMMFm46wK4WyzUq9ZFL2b86iXs7lNEig+6ew XgPpVsR9q56i0ti9/9op/BcE2rtHOwk0DaPUSySpJMoz43wCetDDrJjWmrb2kQ== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=philipmcgrath.com header.s=google header.b=cqSnMmEI; dmarc=none; spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org" X-Migadu-Spam-Score: -1.60 Authentication-Results: aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=philipmcgrath.com header.s=google header.b=cqSnMmEI; dmarc=none; spf=pass (aspmx1.migadu.com: domain of "guix-patches-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-patches-bounces+larch=yhetil.org@gnu.org" X-Migadu-Queue-Id: C3ED02F707 X-Spam-Score: -1.60 X-Migadu-Scanner: scn0.migadu.com X-TUID: +22Zh3bPjwiH Hi, On 12/31/21 05:18, Liliana Marie Prikler wrote: > Am Freitag, dem 31.12.2021 um 00:22 -0500 schrieb Philip McGrath: >>>> +(define (alist-pop alist key) >>>> +  "Return two values: the first pair in ALIST with the given KEY >>>> in its >>>> +'car' (or #f, if no such pair exists) and an assosciation list >>>> like (and >>>> +potentially sharing storage with) ALIST, but with no entry for >>>> KEY." >>>> +  (match (assoc key alist) >>>> +    ;; If key isn't present, we don't need to do any allocation >>>> +    (#f >>>> +     (values #f alist)) >>>> +    (found >>>> +     (values found >>>> +             ;; Because we have `found`, we can find it more >>>> +             ;; efficiently this time with `eq?`. We avoid using >>>> +             ;; `delq` because it would copy pairs in a shared >>>> +             ;; tail. We assume a sufficiently smart compiler to >>>> +             ;; handle "tail recursion modulo cons" (vid. e.g. >>>> Indiana >>>> +             ;; University Technical Report No. 19, Friedman & >>>> Wise >>>> +             ;; 1975) at least as efficiently as a hand-written >>>> +             ;; tail-recursive implementation with an >>>> accumulator. >>>> +             (let loop ((alist alist)) >>>> +               (match alist >>>> +                 ;; We know that `found` is present, >>>> +                 ;; so no need to check for '() >>>> +                 ((this . alist) >>>> +                  (if (eq? this found) >>>> +                      alist >>>> +                      (cons this (loop alist)))))))))) >>> I think this can be more efficiently be done in a "single" loop. >>> >>>    (let loop ((rest alist) >>>               (previous '())) >>>      (match rest >>>        (() (values #f alist)) >>>        ((first . rest) >>>         (if (eq? (car first) key) >>>             (values first (reverse! previous rest)) >>>             (loop rest (cons first previous)))))) >>> >> >> I'll admit to a Racket bias, but, having just eliminated the use of >> 'assoc-set!', I'm loathe to start mutating pairs (even correctly). To >> quote a bit from the SRFI-1 spec for 'append-reverse!', "note that >> this pattern of iterative computation followed by a reverse can >> frequently be rewritten as a recursion, dispensing with the reverse >> and append-reverse steps, and shifting temporary, intermediate >> storage from the heap to the stack, which is typically a win for >> reasons of cache locality and eager storage reclamation." (See how >> 'set-cdr!' can crash safe Chez Scheme! >> ) >> >> IIUC, using SRFI-1's 'span' would lead to the same situation. > For the record, we can use the non-destructive append and reverse here > at the expense of more copying. If done in terms of SRFI-1 span, we > would not need reverse as far as I understand. > >>> Also, I don't think your version is tail-recursive.  (loop alist) >>> is not in tail position from what I can tell. >> >> Yes, "tail recursion modulo cons" refers to a compiler optimization >> for functions which are _not_ tail recursive. For full details, see >> the Friedman & Wise 1975 tech report I cited at >> (or various >> other articles), but, as briefly as I can: The optimization rests on >> the observation that many recursive functions, like the classic >> definition of 'map': >> >>      (define (map f lst) >>        (match lst >>          (() >>           '()) >>          ((this . lst) >>           (cons (f this) >>                 (map f lst))))) >> >> are nearly tail-recursive, and the only real work remaining to be >> done in the continuation of the recursive call is to fill in the cdr >> of the pair. Thus, a compiler can safely transform this code into a >> truly tail-recursive implementation: >> >>      (define (map f lst) >>        (match lst >>          (() >>           '()) >>          ((this . lst) >>           (define ret (list (f this))) >>           (let loop ((dest ret) >>                      (lst lst)) >>             (match lst >>               ((this . lst) >>                (define new (list (f this))) >>                (set-cdr! dest new) >>                (loop new lst)) >>               (() >>                ret)))))) >> >> Unlike the Proper Implementation of Tail Calls (so-called "tail-call >> optimization"), handling "tail recursion modulo cons" truly is an >> optimization: it does not change the space complexity of the >> function. But it can allow the compiler to generate whatever code it >> thinks will work best with its collector/allocator and >> continuation/"call stack" implementation. >> >> (The optimizations applies to constructors in general, not just >> 'cons', and a compiler can safely apply it to values that are >> immutable from the perspective of the source language.) > I'm not aware to which extent Guile implements tail recursion modulo > cons and I'd argue neither are you until you dig down into disassembly. > I think it's better here to avoid patterns from Racket that would feel > foreign to Guilers, particularly if you have to explain them with > reference to a paper (we already get hate for referring to Wingo's fold > for XML handling). In a sense, "tail recursion modulo cons" was a red herring here. The essential requirement for implementing 'alist-pop' or 'map' as I did is that the language implementation be "safe for space", i.e. not have "stack overflow"s: Guile meets that requirement. [1] In a safe-for-space language, the naturally recursive implementations and the implementations with explicit, non-destructive accumulators both allocate O(n) temporary storage. The difference is that the explicit accumulator versions allocate temporary pairs on the heap, while the naturally recursive version allocates its temporary space on the "stack" (i.e. additional frames of the (non-reified) continuation), which is generally, and specifically for Guile per [1], much better (though a sufficiently smart generational garbage collector with bump-pointer allocation in the nursery could mitigate the difference somewhat). All of that relies just on the guarantees of Guile as a safe-for-space language. The optimization in "tail recursion modulo cons" is that a compiler could, if it chose to expend its effort this way, make the naturally recursive implementations work without the O(n) temporary "stack" storage by transforming transforming the non-tail recursion into tail recursion. In essence, it could achieve a similar effect to an explicit accumulator plus 'reverse!' without the many downsides (some of which [1] discusses). But the naturally recursive implementation is preferable even if the optimization does not apply. > > In principle, what you're supposing is that a sufficiently smart > compiler could rewrite > > (let ((before after (span PRED mylist))) (append before after)) > > to (list-copy mylist), which as far as I'm aware Guile currently > doesn't. It could be argued that it would start doing so once I cast > some magic incantations, but I wouldn't count on it without reading the > disassembly. In some sense that's true, but your example would require a lot of interprocedural analysis, not just a directly visible pattern with well-known primitives using analysis that has been well known since the '70s. But, again, the optimization isn't really relevant. >>> Is order relevant here? Because we could just as well reimplement >>> our alist-delete* loop and cons the replacement onto the rest. >>> WDYT? >> >> Relying on order for JSON objects is non-interoperable, per RFC 8259 >> §4. I'm not intending for these alist procedures to be exported, so >> I'm not trying to handle any more general case than that, as I >> explain in the comments at the top of the file. >> >> I'm not sure what the advantage would be to reimplementing the >> 'alist-delete' loop here. > Fair enough, the question was however not so much what is required per > RFC, but rather if there is a natural feel of order to package.json > that we ought not disturb. Particularly, putting dependencies before > name and version could be confusing to whoever needs to debug a delete- > dependencies phase gone wrong. I haven't noticed a consistent convention in "package.json" files (which IIUC may not be entirely hand-written). For debugging, the biggest problem is that (guix build json) doesn't add any linebreaks or indentation. If I were changing it, I'd want it to write object keys in 'string