• #### Re: recursion is silly

From Paul Rubin@21:1/5 to albert@cherry. on Wed Dec 27 10:03:48 2023
XPost: comp.lang.forth

albert@cherry.(none) (albert) writes:
This is a kind of reversed dynamic programming.

That is usually called memoization.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From minforth@21:1/5 to none on Wed Dec 27 18:43:55 2023
XPost: comp.lang.forth

none wrote:

Recursion is silly (if you can avoid it).

I recently draw attention to a toy lisp in Forth.
The example program was a scheme program that counts
how many changes in coins are possible for e.g. 100 dollarcent.
The lisp had to improved to be able to compile the program.
The improved version can hardly manage an input of 100 and takes
a noticable time, 200 and following fails.

IOW educated brute force can beat elegant recursion.

You are right in a brutish

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Julieta Shem@21:1/5 to LIT on Wed Dec 27 17:13:02 2023
zbigniew2011@gmail.com (LIT) writes:

What do you mean iterative?

An iterative function is one that loops to
repeat some part of the code, and a recursive
function is one that calls itself again to
repeat the code

Such calling itself again is a form of going back to work on a similar
problem, which seems to fall under your definition of that which loops.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Joerg Mertens@21:1/5 to Julieta Shem on Wed Dec 27 21:47:52 2023
Julieta Shem <jshem@yaxenu.org> writes:

What do you mean iterative? For instance, Gerald Sussman and Harold
Abelson classify as `iterative' the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.

Are you sure? IIRC they differentiate between programs and processes.
So your function would be a recursive program but it doesn't create a
recursive process (assumed the implementation is tail call optimized).

I admit that it is a long time since I read the book.

Regards

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From mhx@21:1/5 to All on Wed Dec 27 22:29:43 2023
XPost: comp.lang.forth

1000000 | 1333983445341383545001 | 15.24 | 580696

That is quite different from the result none showed.
| time coinsusa 1,000,000
| 666793341266850001
| real 0m0.353s

I guess you are computing something different?
The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Paul Rubin@21:1/5 to mhx on Wed Dec 27 14:37:58 2023
XPost: comp.lang.forth

mhx@iae.nl (mhx) writes:
I guess you are computing something different?
The time for 1,000,000 is also quite large, 15.24s vs 10ms (with iForth).

Interesting, what values do you get for 100, 200, etc.? It could be
that my method is wrong. I just did it off the top of my head and may
have done something dumb.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Julieta Shem@21:1/5 to Joerg Mertens on Wed Dec 27 23:12:38 2023
Joerg Mertens <joerg-mertens@t-online.de> writes:

Julieta Shem <jshem@yaxenu.org> writes:

What do you mean iterative? For instance, Gerald Sussman and Harold
Abelson classify as `iterative' the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.

Are you sure? IIRC they differentiate between programs and processes.

They do --- between ``procedures'' and processes.

So your function would be a recursive program but it doesn't create a recursive process (assumed the implementation is tail call optimized).

On section 1.2.1, Figure 1.4 is roughly

--8<---------------cut here---------------start------------->8---
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

Figure 1.4: A linear iterative process for computing 6!.
--8<---------------cut here---------------end--------------->8---

You're right that they don't call it an iterative /procedure/, but they
do call it an iterative /process/. So maybe I can fix my post with

--8<---------------cut here---------------start------------->8---
[They] classify as `iterative' the process generated by the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.
--8<---------------cut here---------------end--------------->8---

Here's their words directly:

--8<---------------cut here---------------start------------->8---
Consider the [linearly recursive naive factorial procedure]. The
substitution model reveals a shape of expansion followed by contraction, indicated by the arrow in figure 1.3. The expansion occurs as the
process builds up a chain of deferred operations (in this case, a chain
of multiplications). The contraction occurs as the operations are
actually performed. This type of process, characterized by a chain of
deferred operations, is called a recursive process. Carrying out this
process requires that the interpreter keep track of the operations to be performed later on. In the computation of n!, the length of the chain of deferred multiplications, and hence the amount of information needed to
keep track of it, grows linearly with n (is proportional to n), just
like the number of steps. Such a process is called a linear recursive
process.

By contrast, the second process [the fact-iter procedure of Figure 1.4]
does not grow and shrink. At each step, all we need to keep track of,
for any n, are the current values of the variables product, counter, and max-count. We call this an /iterative process/. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state
variables should be updated as the process moves from state to state and
an (optional) end test that specifies conditions under which the process
should terminate. In computing n!, the number of steps required grows
linearly with n. Such a process is called a linear iterative process. --8<---------------cut here---------------end--------------->8---

They constrast the two notions:

--8<---------------cut here---------------start------------->8---
In contrasting iteration and recursion, we must be careful not to
confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring
to the syntactic fact that the procedure definition refers (either
directly or indirectly) to the procedure itself. But when we describe a
process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a
procedure is written. It may seem disturbing that we refer to a
recursive procedure such as fact-iter as generating an iterative
process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep
track of only three variables in order to execute the process. --8<---------------cut here---------------end--------------->8---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From none) (albert@21:1/5 to no.email@nospam.invalid on Thu Dec 28 11:20:36 2023
XPost: comp.lang.forth

In article <87plyq9419.fsf@nightsong.com>,
Paul Rubin <no.email@nospam.invalid> wrote:
albert@cherry.(none) (albert) writes:
You must be kidding. The memoization using standard tools impressed me.
Compared to the result below it is only one order of magnitude.

I see, so the algorithms are basically similar. I haven't examined your
code closely yet. But I see you are using a much more efficient memo
table than I am. Yours is indexed on the offset into the coin list,
while mine uses the entire list. I might try adapting mine, maybe to
use arrays instead of a hash table.

It is similar in the sense that at the end intermediate results
are calculated in the same partial sums. There is a great difference
that it is reversed. Memoization asks for the intermediate results e.g. 100,5 to be calculated. I start from the bottom and just guess that all
This depend on analysing the problem.
You will get nowhere by this method if you apply at eulerproject
problem 502 (counting castles).

I noticed I got an 8x speedup and 5x memory reduction by simply
reversing the order of the coin list, i.e. using (100 50 25 10 5 1)
instead of (1 5 10 25 50 100).

In reality, 50 cent coins and dollar coins are rarely used in the US.
50 cent coins are large enough to be cumbersome, and dollar coins never >became popular because they are too easily confused with quarters (they
are just slightly larger).

Canada has all the coins that the US has, plus a 2 dollar coin, and they >actually use them. France before the Euro had even more, I believe.

France used denominations 10 centimes up till 10 Franc .
The 10 Franc piece and 2 euro piece and the Can 2 dollar piece
have comparable purchasing power. A the time the Netherlands
had a 2.5 guilder coins, also comparable.
Formally the Euro has a regular 1 2 5 10 20 50 100 200 series
but the 1 and 2 cent pieces are no more used in the Netherlands.
So 5 or 6 coins in actual use.

Groetjes Albert

--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Lawrence D'Oliveiro@21:1/5 to All on Fri Dec 29 02:51:22 2023
Somebody who doesn’t like recursion, I wonder what they’re likely to think of continuations ...

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Julieta Shem@21:1/5 to Lawrence D'Oliveiro on Fri Dec 29 00:14:01 2023
Lawrence D'Oliveiro <ldo@nz.invalid> writes:

Somebody who doesn’t like recursion, I wonder what they’re likely to think
of continuations ...

They could like continuations because they might like goto statements. :-)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Lawrence D'Oliveiro@21:1/5 to Julieta Shem on Fri Dec 29 04:18:29 2023
On Fri, 29 Dec 2023 00:14:01 -0300, Julieta Shem wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

Somebody who doesn’t like recursion, I wonder what they’re likely to
think of continuations ...

They could like continuations because they might like goto statements.
:-)

Interestingly, gotos are the one thing that cannot (easily, in general) be expressed as continuations ...

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Paul Rubin@21:1/5 to Julieta Shem on Thu Dec 28 22:46:08 2023
Julieta Shem <jshem@yaxenu.org> writes:
They could like continuations because they might like goto statements. :-)

Continuations are more like comefrom statements. ;-).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Julieta Shem@21:1/5 to Lawrence D'Oliveiro on Fri Dec 29 13:35:47 2023
Lawrence D'Oliveiro <ldo@nz.invalid> writes:

On Fri, 29 Dec 2023 00:14:01 -0300, Julieta Shem wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

Somebody who doesn’t like recursion, I wonder what they’re likely to >>> think of continuations ...

They could like continuations because they might like goto statements.
:-)

Interestingly, gotos are the one thing that cannot (easily, in general) be expressed as continuations ...

You're right:

--8<---------------cut here---------------start------------->8---
``[a] goto can move anywhere in the program because the possible
destinations are known at compile time. A continuation, by contrast,
needs the current evaluation context, which is only known at run
time. In that sense, a continuation is less flexible: it can only
represent a location in the program that’s already been visited.''

Source:
https://beautifulracket.com/explainer/continuations.html
--8<---------------cut here---------------end--------------->8---

But what we mean is:

--8<---------------cut here---------------start------------->8---
``[...] Like [goto statements], continuations can be abused in all sorts
of bizarre manners; virtually every argument that [Dijkstra] makes in
[Goto Considered Harmful] can be applied to continuations.''

Source:
https://kidneybone.com/c2/wiki/ContinuationsAreGotos
--8<---------------cut here---------------end--------------->8---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Lawrence D'Oliveiro@21:1/5 to Julieta Shem on Fri Dec 29 22:35:32 2023
On Fri, 29 Dec 2023 13:35:47 -0300, Julieta Shem wrote:

``[...] Like [goto statements], continuations can be abused in all sorts
of bizarre manners; virtually every argument that [Dijkstra] makes in
[Goto Considered Harmful] can be applied to continuations.''

But consider the following list:

Loop constructs:
-- useful/desirable? Yes.
-- can be practicably implemented with continuations? Yes.
Exceptions:
-- useful/desirable? Yes.
-- can be practicably implemented with continuations? Yes.
Coroutines:
-- useful/desirable? Yes.
-- can be practicably implemented with continuations? Yes.
Arbitrary gotos:
-- useful/desirable? Not so.
-- can be practicably implemented with continuations? Not really.

See the pattern?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Julieta Shem@21:1/5 to Lawrence D'Oliveiro on Fri Dec 29 23:22:53 2023
Lawrence D'Oliveiro <ldo@nz.invalid> writes:

On Fri, 29 Dec 2023 13:35:47 -0300, Julieta Shem wrote:

``[...] Like [goto statements], continuations can be abused in all sorts
of bizarre manners; virtually every argument that [Dijkstra] makes in
[Goto Considered Harmful] can be applied to continuations.''

But consider the following list:

Loop constructs:
-- useful/desirable? Yes.
-- can be practicably implemented with continuations? Yes.
Exceptions:
-- useful/desirable? Yes.
-- can be practicably implemented with continuations? Yes.
Coroutines:
-- useful/desirable? Yes.
-- can be practicably implemented with continuations? Yes.
Arbitrary gotos:
-- useful/desirable? Not so.

Very useful, very desirable.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Lawrence D'Oliveiro@21:1/5 to Julieta Shem on Sat Dec 30 05:48:56 2023
On Fri, 29 Dec 2023 23:22:53 -0300, Julieta Shem wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

Arbitrary gotos:
-- useful/desirable? Not so.

Very useful, very desirable.

Come on ... you don’t mean you code that way, do you?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Julieta Shem@21:1/5 to Lawrence D'Oliveiro on Sat Dec 30 17:17:07 2023
Lawrence D'Oliveiro <ldo@nz.invalid> writes:

On Fri, 29 Dec 2023 23:22:53 -0300, Julieta Shem wrote:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

Arbitrary gotos:
-- useful/desirable? Not so.

Very useful, very desirable.

Come on ... you don’t mean you code that way, do you?

I do and, of course, I'm not the only one.

Knuth, Donald E. ``Structured programming with /go-to/ statements.''
ACM Computing Surveys (CSUR) 6.4 (1974): 261-301.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From none) (albert@21:1/5 to Anton Ertl on Sun Dec 31 11:56:35 2023
XPost: comp.lang.forth

In article <2023Dec30.084142@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:

\ SORTM (best-performing)
: sort2 ( al ah -- )
begin
over cell+ over u< while
partition recurse
repeat
2drop ;

I hate it if one uses U< in comparing numbers that hapenns
to be positive.
Are you really expecting the index straddles the boundary e.g 9223372036854775807 and 9223372036854775809

<SNIP>
- anton
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From none) (albert@21:1/5 to jshem@yaxenu.org on Mon Jan 1 15:40:13 2024
In article <87a5pveeit.fsf@yaxenu.org>, Julieta Shem <jshem@yaxenu.org> wrote: >zbigniew2011@gmail.com (LIT) writes:

Recursion is silly (if you can avoid it).

Not really.

Recursion is elegant — but actually isn't any
more efficient than iteration, and of course
it requires stack space.

And yes, most of the time (or always?) there
does exist iterative counterpart solution

What do you mean iterative? For instance, Gerald Sussman and Harold
Abelson classify as `iterative' the procedure

(def (f n [acc 1])
(if (= n 1)
1
(f (dec n) (* acc n)))),

which is self-referential.

That is pretty insane. It is however the prerogative of a math book,
that you are allowed to define whatever terms as soon as you include
the definitions. The reader should be aware that the term may
not be in universal use.

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Lawrence D'Oliveiro@21:1/5 to Paul Rubin on Wed Jan 3 19:08:07 2024
On Wed, 03 Jan 2024 10:17:43 -0800, Paul Rubin wrote:

The Python equivalent (untested) is:

Fixed missing definition of “memo” variable:

def memoize(f) :

memo = {}

def m(*args) :
if args not in memo :
memo[args] = f(*args)
#end if
return memo[args]
#end m

#begin memoize
return m
#end memoize

Of course this still doesn’t work with keyword args ...

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From mhx@21:1/5 to All on Thu Jan 4 11:58:58 2024
XPost: comp.lang.forth

Can the memoization "see" that once cc(N-5,5) is known,
cc(N-4,5) = cc(N-5,5), up till (cc(N-1,5) (which are zero till now
[..]

I never used naive memoization much because the table size becomes
impractical for real-world problems. If it is known how to compress
N-dim tables (in hopefully a simple way), I'd be very interested
to know how it is done (even when N=1).

-marcel

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Paul Rubin@21:1/5 to mhx on Thu Jan 4 10:56:40 2024
XPost: comp.lang.forth

mhx@iae.nl (mhx) writes:
If it is known how to compress N-dim tables (in hopefully a simple
way), I'd be very interested to know how it is done (even when N=1).

In the Scheme code I posted, the "coordinate list" is used as a hash key.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Lawrence D'Oliveiro@21:1/5 to Kaz Kylheku on Fri Jan 5 21:54:49 2024
On Fri, 5 Jan 2024 21:24:00 -0000 (UTC), Kaz Kylheku wrote:

The ratio of successive values of the Fibonacci numbers approaches the
golden ratio.

The golden ratio is also obtained by just about the simplest of all
continued fractions:

1
1 + -------------
1
1 + ---------
1
1 + -----
...

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Kaz Kylheku@21:1/5 to Kaz Kylheku on Fri Jan 5 22:38:46 2024
On 2024-01-05, Kaz Kylheku <433-929-6894@kylheku.com> wrote:
Puzzle:

Could we use this information somehow to neatly build an amplifier whose closed-loop gain is the Golden Ratio, using only resistors that have integer-valued resistances in Ohms?

I might post this to the Electronics Stack Exchange.

Someone beat me to it, seven years ago:

"How can i make a circuit such that output voltage is reduced by golden
ratio, using feedback"

https://electronics.stackexchange.com/questions/261616/how-can-i-make-a-circuit-such-that-output-voltage-is-reduced-by-golden-ratio-us

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Kaz Kylheku@21:1/5 to Lawrence D'Oliveiro on Fri Jan 5 22:36:04 2024
On 2024-01-05, Lawrence D'Oliveiro <ldo@nz.invalid> wrote:
On Fri, 5 Jan 2024 21:24:00 -0000 (UTC), Kaz Kylheku wrote:

The ratio of successive values of the Fibonacci numbers approaches the
golden ratio.

The golden ratio is also obtained by just about the simplest of all
continued fractions:

1
1 + -------------
1
1 + ---------
1
1 + -----
...

That's recursive, like a Droste image, and so we can rewrite it self-referentially:

R = 1 + 1/R

R^2 = R + 1

R^2 - R - 1 = 0

Then solve for R using the quadratic formula:

1 +/- sqrt(5)
R = -------------
2

One of the solutions is negative, which we can reject. A continued
fraction with only positive constants and addition cannot have
a limit that is negatively valued.

---

Puzzle:

Could we use this information somehow to neatly build an amplifier whose closed-loop gain is the Golden Ratio, using only resistors that have integer-valued resistances in Ohms?

I might post this to the Electronics Stack Exchange.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)