recursion to iteration macro

recursion to iteration macro

[Emanuel Berg]

Did anyone try to write a macro or by using some other method
to translate arbitrary use of recursion into functionally
equivalent code that is iteration only?

I read [1] this is theoretically possible and that seems
reasonable as well, as with loops, local functions etc you
have everything you need to implement it.

You can even have an expanding data structure, e.g. a list, to
implement a virtual stack, still all within the one function,
if you are fond of it.

With execution all advantages should be with iteration but
sometimes recursion makes for compact, elegant code that can
also be more intuitive, more fun to write.

Recursion is not so common, in part for this exact reason, but
if we had this, maybe we would see a little recursion
renaissance and proliferation?

The best of both worlds anyone? You _will_ be assimilated!

[1] https://en.wikipedia.org/wiki/Recursion_(computer_science)
    https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

-- 
underground experts united
https://dataswamp.org/~incal

Re: recursion to iteration macro

[Philip Kaludercic]

Emanuel Berg <incal@dataswamp.org> writes:

> Did anyone try to write a macro or by using some other method
> to translate arbitrary use of recursion into functionally
> equivalent code that is iteration only?
>
> I read [1] this is theoretically possible and that seems
> reasonable as well, as with loops, local functions etc you
> have everything you need to implement it.

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.

> You can even have an expanding data structure, e.g. a list, to
> implement a virtual stack, still all within the one function,
> if you are fond of it.
>
> With execution all advantages should be with iteration but
> sometimes recursion makes for compact, elegant code that can
> also be more intuitive, more fun to write.
>
> Recursion is not so common, in part for this exact reason, but
> if we had this, maybe we would see a little recursion
> renaissance and proliferation?
>
> The best of both worlds anyone? You _will_ be assimilated!
>
> [1] https://en.wikipedia.org/wiki/Recursion_(computer_science)
>     https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

-- 
	Philip Kaludercic on peregrine

Re: recursion to iteration macro

[Emanuel Berg]

Philip Kaludercic 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'?

-- 
underground experts united
https://dataswamp.org/~incal

Re: recursion to iteration macro

[tomas]

[-- Attachment #1: Type: text/plain, Size: 459 bytes --]

On Sat, Mar 23, 2024 at 11:17:04AM +0100, Emanuel Berg wrote:
> Philip Kaludercic 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.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: recursion to iteration macro

[Emanuel Berg]

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.

-- 
underground experts united
https://dataswamp.org/~incal

Re: recursion to iteration macro

[tomas]

[-- Attachment #1: Type: text/plain, Size: 2185 bytes --]

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: recursion to iteration macro

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

Tail -recursion without deepening the stack is a convenience,
and it may seem conceptually trivial, but in implementation
it will ba a substantial redesign.  I think it would use up
a lot of developers time, and we are better off spending that
time on things that will helkp Emacs _users_ rather tan
only programmers.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: recursion to iteration macro

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1202 bytes --]

On Mon, Mar 25, 2024 at 07:38:25PM -0400, Richard Stallman wrote:
> [[[ To any NSA and FBI agents reading my email: please consider    ]]]
> [[[ whether defending the US Constitution against all enemies,     ]]]
> [[[ foreign or domestic, requires you to follow Snowden's example. ]]]
> 
> Tail -recursion without deepening the stack is a convenience,
> and it may seem conceptually trivial, but in implementation
> it will ba a substantial redesign.  I think it would use up
> a lot of developers time, and we are better off spending that
> time on things that will helkp Emacs _users_ rather tan
> only programmers.

I wasn't proposing to change Emacs Lisp in this direction.

I do agree with you that there are far more interesting
targets for Emacs lisp than full tail recursion. Every
language has a place, and this is not only the language
architecture itself, but the uses it is being put to and,
most importantly, the group of people who use it.

My intention was rather to inform the discussion. The OP
was asking about full tail recursion, and my answer was
that, yes, it has been done, and pointers to learn how
it works and what properties it has.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: recursion to iteration macro

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > I wasn't proposing to change Emacs Lisp in this direction.

Thanks for setting me straight.

I couldn't tell, from the messages I happened to see, that such a
change was not the issue at hand.  Those messages did not explicitly
say that -- they expected readers to know that from earlier messages
in the thread.  I suppose most readers did know, since they aren't so
far behind on mail.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: recursion to iteration macro

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1043 bytes --]

On Thu, Mar 28, 2024 at 06:05:43PM -0400, Richard Stallman wrote:
> [[[ To any NSA and FBI agents reading my email: please consider    ]]]
> [[[ whether defending the US Constitution against all enemies,     ]]]
> [[[ foreign or domestic, requires you to follow Snowden's example. ]]]
> 
>   > I wasn't proposing to change Emacs Lisp in this direction.
> 
> Thanks for setting me straight.

I didn't perceive my answer as "setting straight". On the contrary,
your reply gave me the chance to contextualize what I intended to
say,

> I couldn't tell, from the messages I happened to see, that such a
> change was not the issue at hand.  Those messages did not explicitly
> say that -- they expected readers to know that from earlier messages
> in the thread.  I suppose most readers did know, since they aren't so
> far behind on mail.

I think things are more nuanced. My intention wasn't, but I can't
vouch for others in that thread (and that is a Good Thing, diversity
is, after all part of the fun).

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: recursion to iteration macro

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > > Thanks for setting me straight.

  > I didn't perceive my answer as "setting straight". On the contrary,
  > your reply gave me the chance to contextualize what I intended to
  > say,

I'm glad to have been of help.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)