From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.user Subject: Re: Weird Guile Scheme Behaviour Date: Wed, 16 Oct 2019 02:52:15 -0400 Message-ID: <87sgntqj0l.fsf@netris.org> References: <87pnk4v8et.fsf@bulbul> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="15727"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) Cc: guile-user@gnu.org To: philip@warpmail.net (Philip K.) Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Wed Oct 16 08:53:44 2019 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1iKdBo-0003y5-Ox for guile-user@m.gmane.org; Wed, 16 Oct 2019 08:53:44 +0200 Original-Received: from localhost ([::1]:37828 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iKdBm-0005eR-Vk for guile-user@m.gmane.org; Wed, 16 Oct 2019 02:53:42 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:60073) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iKdBK-0005eF-K9 for guile-user@gnu.org; Wed, 16 Oct 2019 02:53:15 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iKdBI-0004ci-Up for guile-user@gnu.org; Wed, 16 Oct 2019 02:53:14 -0400 Original-Received: from world.peace.net ([64.112.178.59]:60590) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1iKdBI-0004bz-10 for guile-user@gnu.org; Wed, 16 Oct 2019 02:53:12 -0400 Original-Received: from mhw by world.peace.net with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1iKdBE-0002j4-R5; Wed, 16 Oct 2019 02:53:09 -0400 In-Reply-To: <87pnk4v8et.fsf@bulbul> (Philip K.'s message of "Fri, 13 Sep 2019 11:43:06 +0200") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 64.112.178.59 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.org gmane.lisp.guile.user:15740 Archived-At: Hi Philip, philip@warpmail.net (Philip K.) writes: > I was reading a thread on an imageboard[0] the other day, then I came > across a most peculiar "bug", if it even is one. Since the original > example was a bit dense (it tried to solve a problem someone else had > posted, that's not relevant here), I tried to construct a minimal > working example to discuss here. > > Compare > > (define (reverse-iota-1 max) > (let ((numbers '(start))) > (let loop ((val 0)) > (append! numbers > (if (< max val) > '() > (begin > (loop (1+ val)) > (list val))))) > numbers)) > > and > > (define (reverse-iota-2 max) > (let ((numbers '(start))) > (let loop ((val 0)) > (append! numbers > (if (< max val) > '() > (begin > (loop (1+ val)) > (list val))))) > (cdr numbers))) > > (I know, the style is horrible, but that's not the point. Also, both > have an internal state, so you have to re-eval the function every time > before starting the function itself.) > > The only difference is in the last line. The first function returns the > entire list (with the start symbol), and the second tries to chop it > off. > > But what happens is that (reverse-iota-1 4) evals to '(start 3 2 1 0) > while (reverse-iota-2 4) just returns '()! The problem here is that '(start) is a *literal* list, and it's an error to modify literals in Scheme. In other words, modifying a literal results in undefined behavior. Like C string literals, Scheme literals are actually part of the program text itself. To fix this problem, instead of initializing 'numbers' to point to a literal list, you must construct a fresh mutable list. One way is by replacing '(start) with (list 'start). What's happening here is this: Since it's an error to modify a literal list, and since the 'numbers' variable is never 'set!' within its lexical scope (the only scope where a variable can possibly be set! in Scheme), Guile's compiler is allowed to assume that 'numbers' will always point to the literal '(start), and therefore that (cdr numbers) can be optimized to '(). The other problem, as Neil and Vladimir correctly pointed out, is that 'append!' is permitted, but not required, to modify the original list. Therefore, you must always do (set! numbers (append! numbers ...)) to avoid relying on unspecified behavior. Note that it's impossible in Scheme to implement an 'append!' procedure that always modifies the original list. Specifically, an empty list cannot be destructively modified. It can't be done for the same reason that you cannot implement a C function with the following specification: struct pair { void *item; struct pair *next; }; void appendx (struct pair *list_to_modify, struct pair *list_to_add); This C function can only be implemented in the case where 'list_to_modify' has at least one element. In that case, the 'next' field of the last pair can be modified. If 'list_to_modify' is NULL, it can't be done, because 'appendx' doesn't have access to the variable that contained NULL. In Scheme, the same issues apply. If there's at least one element in the first list passed to 'append!', it can use 'set-cdr!' to modify the last pair of the list. If the first argument is '(), it can't be done. In practice, that's the reason why 'append!' is specified the way it is. However, I would advise against assuming that 'append!' will always modify the original list if it's nonempty, because that fact, although true of the current implementation, is not actually specified. Regards, Mark