Re: recursion to iteration macro

[tomas]

On Sat, Mar 23, 2024 at 11:40:07AM +0100, Emanuel Berg wrote:
> tomas wrote:
> 
> >>> 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.
> >> 
> >> Why is that so difficult, isn't a stack just a list with
> >> `push' and `pop'?
> >
> > Only usually *much* more efficient.
> 
> How do you propose the virtual stack be implemented?
> 
> 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)

-- 
t

signature.asc
Description: PGP signature