In Kornshell I wrote a recursive function that (in practice) requires a maximum recursion depth of about 3000. There's obviously a fixed limit defined that lies around 1024 (zsh, for example, has a limit of 1000,
it seems); a test program and the error message:
#!/usr/bin/ksh
typeset l=0
function f { print $((++l)) ; f ;}
f
...
1023
1024
1025
...: f[3]: f: line 3: f: recursion too deep
Any good ideas how to handle/circumvent/extend that limit (in ksh)?
[ ksh function call recursion depth limit of 1024 ]
Any good ideas how to handle/circumvent/extend that limit (in ksh)?
In Kornshell I wrote a recursive function that (in practice) requires a maximum recursion depth of about 3000. There's obviously a fixed limit defined that lies around 1024 (zsh, for example, has a limit of 1000,
it seems); a test program and the error message:
#!/usr/bin/ksh
typeset l=0
function f { print $((++l)) ; f ;}
f
...
1023
1024
1025
...: f[3]: f: line 3: f: recursion too deep
Any good ideas how to handle/circumvent/extend that limit (in ksh)?
N.B.: Rewriting the (8-branch-cascading) algorithm is not an option.
On 2022-10-08, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
In Kornshell I wrote a recursive function that (in practice) requires a
maximum recursion depth of about 3000. There's obviously a fixed limit
defined that lies around 1024 (zsh, for example, has a limit of 1000,
it seems); a test program and the error message:
#!/usr/bin/ksh
typeset l=0
function f { print $((++l)) ; f ;}
f
...
1023
1024
1025
...: f[3]: f: line 3: f: recursion too deep
Is this diagnostic literally accurate?
What would happen if we wrote a
script that contains over 1000 differently named functions that call
each other in a chain?
That's not recursion!
Any good ideas how to handle/circumvent/extend that limit (in ksh)?
N.B.: Rewriting the (8-branch-cascading) algorithm is not an option.
Is there a particular branch that generates the depth; and is
it a tail call? Or could it be turned into one?
Without changing an algorithm, we may be able to manually convert some
key tail call in it into iteration, while keeping the others recursive.
I think I spoke too soon previously about "[not] rewriting the
algorithm"; if it's a hard coded shell limit then there's no other way
[in shell], I suppose.
In article <thubhv$g0bh$1@dont-email.me>,
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
...
I think I spoke too soon previously about "[not] rewriting the
algorithm"; if it's a hard coded shell limit then there's no other way
[in shell], I suppose.
Is recompiling the shell binary an option?
(I don't know if it is as simple as changing a parameter and recompiling. Have you asked on any other forums - perhaps one more about ksh internals - i.e., at the C level - rather than just being about shell programming in general)
(I don't know if it is as simple as changing a parameter and recompiling.
Have you asked on any other forums - perhaps one more about ksh internals - >> i.e., at the C level - rather than just being about shell programming in
general)
Not yet.
To be honest, I'd rather like to focus on the algorithmic side, not
dive too deep into the tool details.
From the times (last century) when I programmed more than I do today
I recall compiler to allow setting parameters for memory consumption,
stack depth, and the like. Now I have to admit that shell was likely
just not the right tool for my prototyping approach.
In article <thueo6$g8i3$1@dont-email.me>,
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
...
To be honest, I'd rather like to focus on the algorithmic side, not
dive too deep into the tool details.
Yes, definitely. It's just that in your OP, you stated that changing the algorithm was not an option.
You have since softened your position on that front.
From the times (last century) when I programmed more than I do today
I recall compiler to allow setting parameters for memory consumption,
stack depth, and the like. Now I have to admit that shell was likely
just not the right tool for my prototyping approach.
Yes, I'm sure that thought was on most people's minds when reading this thread. I think that's why you see a lot of those "Don't program in shell" screeds - from people who started something in shell and it just grew and grew until it became unmanageable (generally, by hitting some hard limit or bug/flaw in the shell implementation) and then wished they'd done it differently (i.e., in a different language) from the start. But of course, it is too late to change now...
I think I spoke too soon previously about "[not] rewriting the
algorithm"; if it's a hard coded shell limit then there's no other way
[in shell], I suppose.
On 2022-10-09, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
I think I spoke too soon previously about "[not] rewriting the
algorithm"; if it's a hard coded shell limit then there's no other way
[in shell], I suppose.
Why do you keep repeating "if"? How about checking the source?
I don't know what "ksh" you use, but a brief look at ksh93 1.0.3
shows that...
* It is indeed a fixed limit. https://github.com/ksh93/ksh/blob/v1.0.3/src/cmd/ksh93/sh/xec.c#L3081
* That limit is defined to 1024. https://github.com/ksh93/ksh/blob/v1.0.3/src/cmd/ksh93/include/path.h#L44
I don't even know how the ksh93 code base is organized, I just
grepped for the error message and followed the trail.
On 09.10.2022 07:29, Kaz Kylheku wrote:
On 2022-10-08, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
In Kornshell I wrote a recursive function that (in practice) requires a
maximum recursion depth of about 3000. There's obviously a fixed limit
defined that lies around 1024 (zsh, for example, has a limit of 1000,
it seems); a test program and the error message:
#!/usr/bin/ksh
typeset l=0
function f { print $((++l)) ; f ;}
f
...
1023
1024
1025
...: f[3]: f: line 3: f: recursion too deep
Is this diagnostic literally accurate?
I omitted the data lines 1..1022 (that contain the respective values)
where I wrote "..." and also the script name where the second "..."
is, and I manually added the the #! line for informational purposes
(where the script had a blank line; I always feed scripts explicitly
to the interpreter, like 'ksh testscript', in case of tests).
What would happen if we wrote a
script that contains over 1000 differently named functions that call
each other in a chain?
I haven't tried. (My guess is it would trigger.) - ...quick test with
function f { print f=$((++ff)) ; g ;}
function g { print g=$((++gg)) ; f ;}
f
...
g=511
f=512
g=512
f=513
rec[4]: f[2]: g: line 3: g: recursion too deep
That's not recursion!
No direct recursion, but an indirect one. - I think the naming is okay
but we can also call it a call stack limit.
Any good ideas how to handle/circumvent/extend that limit (in ksh)?
N.B.: Rewriting the (8-branch-cascading) algorithm is not an option.
Is there a particular branch that generates the depth; and is
it a tail call? Or could it be turned into one?
It's a cascading recursion with eight possible call branches like
function f { c1 && f ; c2 && f ; ... ; c8 && f ;} # c1..c8: conditions
so it's no tail recursion special case and there's no preferred branch.
Frankly, I cannot say whether it could be transformed - I mean without explicitly organizing the call stack. I've done that with special cases
of a (simple, 2-branch) cascading function (fib; see comp.lang,awk the
post "Yet another obfuscated Awk code", Jan. 2022), but here I am lost.
On 09.10.2022 07:29, Kaz Kylheku wrote:
On 2022-10-08, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
In Kornshell I wrote a recursive function that (in practice) requires a
maximum recursion depth of about 3000. There's obviously a fixed limit
defined that lies around 1024 (zsh, for example, has a limit of 1000,
it seems); a test program and the error message:
#!/usr/bin/ksh
typeset l=0
function f { print $((++l)) ; f ;}
f
...
1023
1024
1025
...: f[3]: f: line 3: f: recursion too deep
Is this diagnostic literally accurate?
I omitted the data lines 1..1022 (that contain the respective values)
where I wrote "..." and also the script name where the second "..."
is, and I manually added the the #! line for informational purposes
(where the script had a blank line; I always feed scripts explicitly
to the interpreter, like 'ksh testscript', in case of tests).
What would happen if we wrote a
script that contains over 1000 differently named functions that call
each other in a chain?
I haven't tried. (My guess is it would trigger.) - ...quick test with
function f { print f=$((++ff)) ; g ;}
function g { print g=$((++gg)) ; f ;}
f
...
g=511
f=512
g=512
f=513
rec[4]: f[2]: g: line 3: g: recursion too deep
That's not recursion!
No direct recursion, but an indirect one. - I think the naming is okay
but we can also call it a call stack limit.
Any good ideas how to handle/circumvent/extend that limit (in ksh)?
N.B.: Rewriting the (8-branch-cascading) algorithm is not an option.
Is there a particular branch that generates the depth; and is
it a tail call? Or could it be turned into one?
It's a cascading recursion with eight possible call branches like
function f { c1 && f ; c2 && f ; ... ; c8 && f ;} # c1..c8: conditions
so it's no tail recursion special case and there's no preferred branch.
Frankly, I cannot say whether it could be transformed - I mean without explicitly organizing the call stack. I've done that with special cases
of a (simple, 2-branch) cascading function (fib; see comp.lang,awk the
post "Yet another obfuscated Awk code", Jan. 2022), but here I am lost.
Without changing an algorithm, we may be able to manually convert some
key tail call in it into iteration, while keeping the others recursive.
I think I spoke too soon previously about "[not] rewriting the
algorithm"; if it's a hard coded shell limit then there's no other way
[in shell], I suppose.
[...]
Before thinking about things like tail recursion and whatever crap
I've been talking about, one thing that can be done is to reduce
the number of function calls by a factor.
This is done simply by manually inlining the recursive cases
to whatever depth is required.
If you need a call of around 3000, and the language artificially
restricts to 1000 well before the stack is exhausted, you can
fool it by manually inlining three levels of recursion.
[...]
On 09.10.2022 14:59, Kenny McCormack wrote:
Yes, I'm sure that thought was on most people's minds when reading this
thread. I think that's why you see a lot of those "Don't program in shell" >> screeds - from people who started something in shell and it just grew and
grew until it became unmanageable (generally, by hitting some hard limit or >> bug/flaw in the shell implementation) and then wished they'd done it
differently (i.e., in a different language) from the start. But of course, >> it is too late to change now...
I'm not sure it's too late. After all I'm using the shell just for the
"rapid prototyping"; now it's just "prototyping" (no "rapid" any more).
Kornshell is a bit treacherous; it supports so many advanced features
(type system, FP arithmetic, etc.) that you can reach quite far using
it for algorithmic solutions. But then there's a hard stop at places
where one wouldn't expect it.
Janis
On 09.10.2022 15:32, Janis Papanagnou wrote:
On 09.10.2022 14:59, Kenny McCormack wrote:
Yes, I'm sure that thought was on most people's minds when reading this
thread. I think that's why you see a lot of those "Don't program in shell" >>> screeds - from people who started something in shell and it just grew and >>> grew until it became unmanageable (generally, by hitting some hard limit or >>> bug/flaw in the shell implementation) and then wished they'd done it
differently (i.e., in a different language) from the start. But of course, >>> it is too late to change now...
I'm not sure it's too late. After all I'm using the shell just for the
"rapid prototyping"; now it's just "prototyping" (no "rapid" any more).
Since the algorithm was already existing in ksh, a re-implementation
in Awk was done fast. The Awk code is terse and much better readable.
It is running a magnitude faster than shell. No recursion depth limit
or other obstacles appeared. ("+1" for GNU Awk with multi-dimensional
arrays support which contributed here as well.)
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 307 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 100:21:41 |
| Calls: | 6,850 |
| Calls today: | 1 |
| Files: | 12,354 |
| Messages: | 5,415,286 |