From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1.migadu.com ([2001:41d0:1008:1e59::1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms1.migadu.com with LMTPS id MDsDD5lHXWayEAEAA41jLg (envelope-from ) for ; Mon, 03 Jun 2024 06:33:29 +0200 Received: from aspmx1.migadu.com ([2001:41d0:403:4876::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1.migadu.com with LMTPS id oGjQCJlHXWbH+QAA62LTzQ (envelope-from ) for ; Mon, 03 Jun 2024 06:33:29 +0200 X-Envelope-To: larch@yhetil.org Authentication-Results: aspmx1.migadu.com; dkim=pass header.d=incana.org header.s=key1 header.b=EBoqBi4D; spf=pass (aspmx1.migadu.com: domain of "guix-devel-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-devel-bounces+larch=yhetil.org@gnu.org"; dmarc=pass (policy=quarantine) header.from=incana.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1717389209; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:list-id:list-help:list-unsubscribe: list-subscribe:list-post:dkim-signature; bh=I6PHu/SLAj8ioiBY8dklhJIsAzP9YVMWp+E234Gwb7c=; b=aWGSCQaVL2PNK9+KM8tc1mag3Sx9k7xhP+P4xVuOzoUFupp6kevyr8zFgk6XcIctFjaC+8 OuP0nrFg9OnlF3boxi7/4CJsuUn1B9dWdLCE7uWDZtfokj/CZPgu6dm0cze/eGnznLcq0t ce80N2U49dzni/B2PTJVv9QzoF3Ruzf0fFiOhm4128ZZiwiwC59OXkNR2RhHPOGlHql35g /uY+9hMZYI3vypbysdAtt2j+VTmO2TDRcHWO7qf0USiaFDg+9AW6Kyur0ZZ2Fke5wROGo0 UVpq6+T9ETSWM5veU3yV8bo8HAeRz28egt0W9oeyUCEMe055GwMp1H2dwuWoPA== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=incana.org header.s=key1 header.b=EBoqBi4D; spf=pass (aspmx1.migadu.com: domain of "guix-devel-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-devel-bounces+larch=yhetil.org@gnu.org"; dmarc=pass (policy=quarantine) header.from=incana.org ARC-Seal: i=1; s=key1; d=yhetil.org; t=1717389209; a=rsa-sha256; cv=none; b=ZMXpkG7Of9FLiLAPvWT29EwQ3AgugLiIHtuqYicvRyIQgl7Ojtf2jaVxKhbzTvnmtu8hht 2uOHUXfd3OINykdKCAYPQLwG3ntWBOxCzPiPlsoUE5yLpaweDgId1dSjywiP2CAAZUHpoU QoDBEcyDLLM79Ph5uxjaf6f7+U18nf6z9b7XtjceZPXXPI0s7o7KniNmMhvf5deZSLsLMd WPnDlzh60RfhL/EPMooFB5JLppU5cvuLWSIuhryQydFXDQ2955w7BDLDXlLw1l8CWewxi7 G1ijJuEhp5FfUd27Uq67kagFdRBuqGbslSt5D/ZGgdf7YhJc51Bs4z9UGY4fdA== 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 8685CCBE8 for ; Mon, 3 Jun 2024 06:33:28 +0200 (CEST) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sDxt3-0001ln-GD; Sun, 02 Jun 2024 22:57:29 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sDxt1-0000sk-4K for guix-devel@gnu.org; Sun, 02 Jun 2024 22:57:27 -0400 Received: from out-170.mta1.migadu.com ([2001:41d0:203:375::aa]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sDtQ7-0004TI-00 for guix-devel@gnu.org; Sun, 02 Jun 2024 18:11:21 -0400 X-Envelope-To: sergio.pastorperez@outlook.es DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=incana.org; s=key1; t=1717366273; h=from:from:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type; bh=I6PHu/SLAj8ioiBY8dklhJIsAzP9YVMWp+E234Gwb7c=; b=EBoqBi4DlpoDDuSDWPGgwb2FakTZkwfoQDLG4M3yiU2ZOxekfotC7IOmChkj+ePa6hL6MF 9Q24nfRk1DE83QavD/TiEnh4/NlviP6Wi6A5XVad7NVOlkC/SslGSF65mwTWbCeffp7wQw PAfUtXwy11gOzso+arhPSQvb3sruQqCOMMYrYdLH3i9HAXrUOB5tl0pPpbawLPBcE+707Y LUPnDvrzbbo2Ds13mMrgLAzdZIMMLUpKhRfdDqCK5chRzlEuNDLovPlYNZ7PZzm9qPoQq9 yBE3iRnl/c1ltU4f1pQ1qLxoYUoY6lYcUk8gUEYz3GVOtBmPZb0VGoLL12K+4A== X-Envelope-To: michal_atlas+gnu@posteo.net X-Envelope-To: guix-devel@gnu.org Date: Sun, 02 Jun 2024 18:10:58 -0400 X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. From: Juliana Sims Subject: Re: System deployment commands hoarding all RAM To: sergio.pastorperez@outlook.es Cc: michal_atlas+gnu@posteo.net, guix-devel@gnu.org Message-Id: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Received-SPF: pass client-ip=2001:41d0:203:375::aa; envelope-from=juli@incana.org; helo=out-170.mta1.migadu.com X-Spam_score_int: 20 X-Spam_score: 2.0 X-Spam_bar: ++ X-Spam_report: (2.0 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, GB_FAKE_RF_SHORT=1.999, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_SBL_A=0.1, URI_DOTEDU=1.999 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: guix-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: AS8P251MB0337E3439FE24C98DA02D6BBF3F72@AS8P251MB0337.EURP251.PROD.OUTLOOK.COM Errors-To: guix-devel-bounces+larch=yhetil.org@gnu.org Sender: guix-devel-bounces+larch=yhetil.org@gnu.org X-Migadu-Country: US X-Migadu-Flow: FLOW_IN X-Spam-Score: -6.54 X-Migadu-Queue-Id: 8685CCBE8 X-Migadu-Scanner: mx10.migadu.com X-Migadu-Spam-Score: -6.54 X-TUID: 76uMmgDiomni Hi Sergio, Continuing on from our out-of-band conversation about this topic, the most likely cause of your RAM issue is that you use recursion extensively, but not in tail position. This means that Guile cannot optimize this recursion to re-use stack frames and thus your memory usage is unbounded. I'll try to explain a bit more what that means in this email in the hopes that you'll be able to resolve it. Forgive me if I repeat things you already know; I want to make sure you have all the information you need to solve your problem. You know what recursion is: calling a function from inside itself (or one of the functions it calls). You mentioned you've also heard of tail calls. I'll go ahead and describe tail calls a couple ways just in case these different descriptions help something click for you. I know I needed to hear several different explanations before I really understood them. The common definition is that a tail call is a call made as the last thing a function does. I think of it as calling a function when there's no more work to do in the current function. Functions called in this way are said to be "in tail position." Tail recursion is simply making a recursive call in tail position. Here's a silly example defined first without tail recursion, then with: ``` (define (add-x n x) "Add @var{x} to @var{n} one at a time." (if (= x 0) n (+ 1 (add-x n (- x 1))))) (define (add-x-tail n x) (if (= x 0) n (add-x-tail (+ n 1) (- x 1)))) ``` An important note: while the recursive call is the last line of text in the tail-recursive function definition, this isn't necessarily required. That idea threw me off for quite some time. The following function is also tail recursive and produces the same output as the other two definitions: ``` (define (add-x-tail-2 n x) (if (not (= x 0)) (add-x-tail-2 (+ n 1) (- x 1)) n)) ``` Let's return to the first definition for now. You may notice that the recursive call happens inside of a call to `+`. Because arguments have to be fully evaluated to values in order to be passed to functions, the `+` call cannot be fully evaluated without the result of the recursive call. We therefore have to keep around the outer `add-x` call so that we can fully evaluate `+` and return its value from `add-x`. Let's walk through expanding a quick example, skipping some intermediary evaluation to save space and using ellipses to replace parts of the function we don't care about anymore but have to keep around anyway: ``` (add-x 3 2) -> ;; replace add-x with its body, replacing variable names with values (if (= 2 0) 3 (+ 1 (add-x 3 1))) -> ;; repeat the above steps, replacing the inner call to add-x with its body and its variable names with their values (... (+ 1 (if (= 1 0) 3 (+ 1 (add-x 3 0))))) -> ;; and again (... (+ 1 (... (+ 1 (if (= 0 0) 3))))) ;; we skip writing the second arm because we don't evaluate it -> ;; now that everything is fully expanded, we can begin evaluating in ernest (... (+ 1 (... (+ 1 3)))) -> (... (+ 1 4)) -> 5 ``` Compare that to the second function definition. In this definition, the `+` and `-` calls both happen inside the call to `add-x-tail`. These are operating on known values and can be fully evaluated before the call to `add-x-tail`. That is, there is no information in the first `add-x-tail` call that is required to use the result of the second (or third, fourth, etc) call to `add-x-tail`. This reveals another way to think of tail calls. Tail calls are calls for which all arguments are known and whose result is immediately returned by the calling function. Here's where we introduce a new term: recursive tail call optimization. Tail calls and tail recursion just describe situations you find in code. In and of themselves, they only talk about what code does on a theoretical level. Tail call optimization is a way to take advantage of the theoretical aspects I've been discussing. I've been framing tail calls as calls which do not need any information from the function that calls them. Recursive tail call optimization allows the compiler to replace the arguments of the calling function with the new argument values and then simply re-evaluate that function in-place. If you're familiar with how computers operate at the level of machine code and the stack, recursive tail call optimization is usually implemented by moving the new arguments into the same argument registers as were used for the first call to a function, then jumping back to the beginning of the function's stack frame. Guile (and all Scheme implementations compliant with R5RS or later standards) does something very similar. We'll step through evaluation of our tail recursive definition with this understanding in mind, as well as previous rules for making the steps shorter: ``` (add-x-tail 3 2) -> ;; replace add-x-tail with its body and replace variable names with their values (if (= 2 0) 3 (add-x-tail 4 1)) -> ;; we only need to replace variables this time (if (= 1 0) 4 (add-x-tail 5 0)) -> ;; and now we can finish evaluation (if (= 0 0) 5) -> 5 ``` As you can see, we just replaced the arguments in-line and evaluated the function over. When deciding if you're using a recursive tail call, ask yourself: if I replace the arguments to the current call with the arguments to the next call and evaluate the function again with no other changes, will I get the result I want? If the answer is yes, then congratulations! That's a recursive tail call! Now, that's all just to help you understand recursive tail calls, why they're useful, and how to recognize them. That doesn't actually help you write them. And even when you understand recursive tail calls well enough to write them reliably, it's often non-trivial to represent a particular computational task using only recursive tail calls. Still, hopefully this helps. Here are some other explanations of tail calls and tail recursion which may also help: * a brief description and demonstration from Computerphile on YouTube (I recommend a free software frontend): https://youtu.be/_JtPhF8MshA * a more thorough treatment of the topic from "An Introduction to Scheme and Its Implementation": https://www.cs.utexas.edu/ftp/garbage/cs345/schintro-v14/schintro_127.html * the entire sixth part of "How to Design Programs" talks about recursive tail calls and how to define functions using them (note that this section builds on the rest of the book so it may not be immediately obvious what it's saying without other context): https://htdp.org/2023-8-14/Book/part_six.html I'm sure other seasoned Schemers on this list can help refine this explanation or point you to other resources, and they may even be able to point you towards tail-recursive solutions to your problem. I don't have the time to try my hand at it at the moment, unfortunately, but I wish you good luck and happy hacking! -Juli PS If you've never spent time with "How to Design Programs" (HtDP), I highly recommend it. It can be slow going if you're not new to programming, but the design recipe and the program design discipline it teaches are the most valuable education I've ever gotten in, well, designing programs (and the functions that compose them). HtDP is an incredibly good replacement for the program design parts of the legendary "Structure and Interpretation of Computer Programs" (SICP) because it is able to build upon and refine the lessons of SICP with further experience from decades more of teaching. Plus, its laser-focus on one specific subset of the many topics SICP covers allows it to progress more gently and explore concepts in more depth from more angles.