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.

Janis

On Sat, 08 Oct 2022 19:07:47 -0400, 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
>
> Any good ideas how to handle/circumvent/extend that limit (in ksh)?

It may be something set in /etc/security/limits.conf

Regards, Dave Hodgins

On 09.10.2022 01:07, Janis Papanagnou wrote:
> [ ksh function call recursion depth limit of 1024 ]
>
> Any good ideas how to handle/circumvent/extend that limit (in ksh)?

I fear it's hard-coded, and that there's no way out. :-/

Janis

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.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

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.

Janis

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)

--
After Using Gender Slur Against AOC, GOP Rep. Yoyo Won't Apologize 'For Loving God'.

That's so sweet...

On 09.10.2022 13:43, Kenny McCormack wrote:
> 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 thought about it when I realized that it's a hard coded limit. But,
without going into the details, on the legacy system I am preferred
working on it may be an issue. The (AT&T) ksh build process is also
non-standard (not the usual configure/make/install incantation), and
though the build worked smoothly when I did that on a contemporary
system many years ago, I'd rather not want to try here (failed with
missing libs and the like). When I looked into the code it's also
not that clear to me whether I can just change a constant; I found
at least two that sound like it and I cannot tell whether it's safe
to change any of them without subtle side effects; it would certainly
need some time to check that. And then I would have an isolated shell
clone. - These were about my thoughts when pondering about it.

>
> (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.

Janis

In article <thueo6$g8i3$1@dont-email.me>,
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
....
>> (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.

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...

--
Faced with the choice between changing one's mind and proving that there is
no need to do so, almost everyone gets busy on the proof.

- John Kenneth Galbraith -

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.

--
Christian "naddy" Weisgerber naddy@mips.inka.de

On 09.10.2022 14:59, Kenny McCormack wrote:
> 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.

That was my first impulse. Given the options, I was wrong.

>
> You have since softened your position on that front.

The Gory Reality hit me quite effective.

>
>>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'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:22, Christian Weisgerber wrote:
> 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 did. - And I am still unsure (as written elsethread).

> I don't know what "ksh" you use, but a brief look at ksh93 1.0.3
> shows that...

I'm using the standard AT&T ksh 93u+ (2012-08-01).

I cannot tell about any clones you are referring to. (I've never heard
of "1.0.3" nor do I use it.)

Janis

>
> * 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 2022-10-09, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> 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.

Well, the c8 && f is definitely a tail call. However, that may not
be where the depth is.

The c1 && f isn't a tail call because the function continues
after it returns, and the conditions aren't mutually exlusive.

An example of this kind of function is an N-ary tree traversal.
Say a tree with up to 8-way branching:

function f (node) {
if (node.children > 0)
f(node.child[0])
if (node.children > 1)
f(node.child[0])
...
if (node.children > 7)
f(node.child[7])
}

E.g. in lisp we have binary nodes, conses with car and cdr.
Most lists grow in the cdr direction, so tail calling on the cdr
case keeps the stack shallow.

This is an issue for garbage collectors, which have to traverse whatever
is reachable, however the application has chosen to shape it.

The application can create cruft in the heap using non-recursive
techniques which then choke a recursive garbage collector.

There are stackless techniques for garbage collection via
"pointer reversal". When the garbage collector follows some link
into an object, it picks one of the pointers in *that* object
and stashes the incoming pointer. Before doing that, it removes
that child pointer, and recurses on that child, passing it
its own address as the next pointer.

Basically, the backwards pointers for returning are stored
into the object graph itself, the originals bein restored
when the reverse path is taken.

It goes something like this:

// stacklessly traverse "3-node": node with 3 child pointers
function visit_3_node(node, escape_pointer)
{
switch (node.traversal_state) {
case UNTRAVERSED:
{
traverse_next = node.child[0]
node.child[0] = escape_pointer
node.state = TRAVERSED_0

// tail call!!!
// child[0] is traversed next, and *its* escape_pointer
// is just node, so it will return here.
return top_level_visit_fn(traverse_next, node)
}
case TRAVERSED_0:
{
orig_escape_pointer = node.child[0]
traverse_next = node.child[1]
node.child[0] = escape_pointer // restore child[0]
node.child[1] = orig_escape_pointer // move to child[1]

node.state = TRAVERSED_1
// child[1] traversed next, again with pointer back to here
return top_level_visit_fn(traverse_next, node)
}
case TRAVERSED_1:
{
// One child left to traverse: different handling.
orig_escape_pointer = node.child[1] // recover orig ptr

node.child[1] = escape_pointer // restore child[1]

// We don't stash the orig_escape_pointer any more.
// Just go to child[2] and pass the original escape
// pointer as the next object to go to (i.e. our caller's).

node.state = TRAVERSED_2; // traversed 0, 1, 2: all done.
return top_level_visit_fn(node.child[2], orig_escape_pointer)
}
}

Basically it is just like continuation passing style (CPS), where the
continuation we are passing down isn't a function, but just pointer to
the object in the graph where to continue. Because the continuation
isn't a function, we simulate one with a state machine; the state
we switch on gives us a kidn of instruction pointer to move through
the traversal cases of the function.

> 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.

Language expressiveness is an issue. E.g. how nicely/easily can we code
a pointer-reversal state machine (if such as thing is necessary) in
shell?

:)

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

On 2022-10-09, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> 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.

The function blows up in size and complexity, to be sure, but
in a regular way which you can document as being manually
expanded recursion. (E.g. provide the simple version in a block
comment, with a brief explanation.)

E.g. here is a two-level expansion of your simplified function schema:

function f()
{
if (cond1) {
cond1 && f # I eval cond1 twice; it may have side effects
cond2 && f
...
cond8 && f
}
if (cond2) {
cond1 && f
cond2 && f
...
cond8 && f
}

...
if (cond8) {
cond1 && f
cond2 && f
...
cond8 && f
}
}

A macro preprocessor would help here, clearly.

If this were Awk, we could use cppawk, which gives you the C
preprocessor in front of Awk.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

On 09.10.2022 20:25, Kaz Kylheku wrote:
>> [...]
>
> 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.

A good idea. - Thanks!

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.)

>
> 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
>

In article <ti53cd$17cgm$1@dont-email.me>,
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>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.)

I think you did the right thing.

--
A Catholic woman tells her husband to buy Viagra.

A Jewish woman tells her husband to buy Pfizer.