From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Newsgroups: gmane.emacs.devel Subject: Re: recursion to iteration macro Date: Sat, 23 Mar 2024 14:25:02 +0100 Message-ID: References: <871q813mgg.fsf@dataswamp.org> <87le69e812.fsf@posteo.net> <87h6gx1cdb.fsf@dataswamp.org> <87edc11baw.fsf@dataswamp.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="dPPfuEbEdwO3/acS" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="791"; mail-complaints-to="usenet@ciao.gmane.io" To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Mar 23 14:26:09 2024 Return-path: Envelope-to: ged-emacs-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 1ro1Nx-000AWY-0I for ged-emacs-devel@m.gmane-mx.org; Sat, 23 Mar 2024 14:26:09 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ro1N3-00061R-9l; Sat, 23 Mar 2024 09:25:13 -0400 Original-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 1ro1Mz-000614-Sw for emacs-devel@gnu.org; Sat, 23 Mar 2024 09:25:10 -0400 Original-Received: from mail.tuxteam.de ([5.199.139.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ro1Mv-0007Ba-UW for emacs-devel@gnu.org; Sat, 23 Mar 2024 09:25:09 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tuxteam.de; s=mail; h=From:In-Reply-To:Content-Type:MIME-Version:References:Message-ID: Subject:To:Date:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=alxvMIj7j1y41Y42JCQ9ymH2+QO9r/c5eiIQmkEf858=; b=BxKSrDM7lrHlBkUd6pnA4L3ELW 8RmGirhmnd1QY20utPXrgfhnZkfCT2RfnmJMoMVqy+ZRVKOfJzNJcLMbGJOwH8KvzphJ+6m3x0Z43 pjkYPnY/EmKJtmHCUTOlJO3ip1AFcQ+QCkhPwXrZ8TkrBoE7tOZaOSSpKXxM4PKXzuhRq49aMdP10 iZ+R3Q6ppn1bw+2psb37QgU0DetnjojSb6DGQLOnp8Sti45gTDj1oRG11IQ5vrTe8G5LfN90AIEnZ e8K7x5Gg6iN0BV98t3R9QYrcBrQ1b6jU2igbZZ0dGl91jZxsoeIYAFPfUlEfRAuleuTfFo7UbDBgj p78wHRPg==; Original-Received: from tomas by mail.tuxteam.de with local (Exim 4.94.2) (envelope-from ) id 1ro1Ms-0002e9-Rw for emacs-devel@gnu.org; Sat, 23 Mar 2024 14:25:02 +0100 Content-Disposition: inline In-Reply-To: <87edc11baw.fsf@dataswamp.org> Received-SPF: pass client-ip=5.199.139.25; envelope-from=tomas@tuxteam.de; helo=mail.tuxteam.de X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 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, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:317251 Archived-At: --dPPfuEbEdwO3/acS Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Mar 23, 2024 at 11:40:07AM +0100, Emanuel Berg wrote: > tomas wrote: >=20 > >>> At least for tail-call recursion, named-let will turn > >>> recursive code into iterative code. > >>> > >>> But generally speaking, if you need to accumulate data on > >>> the stack, then it becomes a lot more difficult. > >>=20 > >> Why is that so difficult, isn't a stack just a list with > >> `push' and `pop'? > > > > Only usually *much* more efficient. >=20 > How do you propose the virtual stack be implemented? >=20 > The goal is to have recursion syntax but iteration execution > transparently and seamlessly, other than that we will just > make it as efficient as possible. This is something the Schemes of the world have been doing since mid to late 1970ies, with an ever increasing grade of optimization. So much so that Scheme doesn't have (doesn't need) iterative constructs. As for the stack... best is to use the machine stack, of course. When you've help from the hardware, better use it. A locally contiguous stack plays into the hands of current CPU architecture, where your CPU has to wait roghly for 100 cycles to get something out of RAM "out there" (here is an old comparison of those times [0] -- I'd expect things to have become even more extreme these days). Chasing pointers along a list will kill your CPU cache and clog your RAM interface (you're pulling in eight bytes for each pointer) compared to a contiguous storage, where the "next value" will most probably be in cache when you need it. Yes, modern architectures have learnt to (speculatively) follow things which look like pointers. This has given us Spectre [2] and other niceties. If you want to see how such things are done in practice, Andy Wingo's blog is a trove. Here[1]'s an older post where he discusses Guile's (then) new register VM and how the stack is handled for it. So, in a nutshell, we already have roughly 50 years of efficient recursion. Cheers [0] http://norvig.com/21-days.html#answers [1] https://wingolog.org/archives/2013/11/26/a-register-vm-for-guile [2] https://en.wikipedia.org/wiki/Spectre_(security_vulnerability) --=20 t --dPPfuEbEdwO3/acS Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABECAB0WIQRp53liolZD6iXhAoIFyCz1etHaRgUCZf7YKAAKCRAFyCz1etHa RmvWAJ0Q05aDVTqDxFO+o8CoFWSO6cbXJwCeJ6Ti0tLAz346U3gcju2WtriGfjY= =AWft -----END PGP SIGNATURE----- --dPPfuEbEdwO3/acS--