Got a "Memory fault" when trying to sum up to 1.000.000 using a recursive impl. of Gauss' algorithm

[takusuman]

G'Night, KornShell 93 development team.

Recently --- to be specific, on 22th September ---, I was testing a tree-walker type interpreter that I wrote for a challenge called "Rinha de Compiladores", that is occurring between Brazilian programmers, with a recursive form of the Gauss' algorithm. So I decided to modify the code provided to count up to 1.000.000 instead of 5, just to see how fast it was, and ended up getting a "Memory fault" when n was equal to 999766:

For the folks that can't read an algorithm before a mathematical explanation of it, here it goes: The Gauss' sum algorithm works as the following, it sums the 1st number with the last number, the 2nd with the penultimate and it goes on, which can be rendered into:

$S\left(n\right)=\left(1 + \left(n - \left(1 - 1 \right)\right)\right) + \left(2 + \left(n -\left(2 - 1 \right)\right)\right) + \cdots + \left(n + \left(n - \left(n - 1 \right)\right)\right)$

Of which we can generalize as:

$S\left(n\right)=\left(2n - \left(n - 1\right)\right) \times \frac n 2$

We know that, if we plug 1 as $n$, it will "return" us just 1, as it follows: $S\left(1\right)=\left(2\times1 - \left(1 - 1\right) \right) \times \frac 1 2$ $S\left(1\right)=\left(2\times1 - \left(\enclose{horizontalstrike}{1 - 1}\right) \right) \times \frac 1 2$ $S\left(1\right)=\left(2\times1\right) \times \frac 1 2=\frac{\left(2\times1\right)}{2}$ $S\left(1\right)=\frac{\left(\enclose{horizontalstrike}{2}\times1\right)}{\enclose{horizontalstrike}{2}}=1$

Putting that in a programming language --- in case, a small subset of ECMAScript created only for the aforementioned challenge ---, we got this:

```js let sum = fn (n) => { if (n == 1) { n } else { n + sum(n - 1) } }; ```

From files/sum.rinha, at aripiprazole/rinha-de-compiler

I.e until $n$ is equal to 1, we will keep adding $n$ to $(n - 1)$, which is similar to the demonstration that I did before --- but, instead of dividing per two after subtracting $(n - 1)$ from $2n$, we are doing a direct addition of $n$ with $n - 1$ until it reaches 1.

Anyway, after being extremely prolix, I must say how I made this code run on top of KornShell 93, which lead me to write this bug report in the first place.

As I said before, my program is written as a Tree-Walking type interpreter, so it takes a tree data structure, in the case, an Abstract syntax tree, and "walks" over it via recursion, interpreting the values on it and, at the end, returning them. The A.S.T. is read from a vulgar JSON file, and then it's transformed into a compound variable:

eval ast=$(echo "$ast_json" | \
    sed -e 's/\{/\(/g; s/\}/\)/g; s/\[/\(/g; s/\]/\)/g; s/"\([^"]*\)":[^ ]*./\1=/g; s/,//g')

After that, the main node of the A.S.T. (ast.expression) is given as input to a function called evaluate, which evaluates the A.S.T. checking every possible kind of structure that may be present on it using a switch-case until it's finished. For instance, the first line of the sum algorithm code would be interpreted like that:

Type	Code
Pseudo-code	```js let sum = fn (n) => { ```
JSON A.S.T.	```json { "name": "files/sum.rinha", "expression": { "kind": "Let", "name": { "text": "sum", "location": { "start": 4, "end": 7, "filename": "files/sum.rinha" } }, "value": { "kind": "Function", "parameters": [ { "text": "n", "location": { "start": 14, "end": 15, "filename": "files/sum.rinha" } } ], ```
KornShell interpreter	```bash function evaluate { [[ $verbose ]] && set -x node=$1 kind="$(eval_per_token $node kind)" case "$kind" in # [...] "Let") identifier=$(eval_per_token $node name.text) content=$(eval_per_token $node value.kind) next=$(eval_per_token $node next) printlog INFOF "Let: $identifier with kind $content." if [[ $content == "Function" ]]; then printlog INFOF "Dealing with $content, recording it in case of a call." record_function "$identifier" "$node.value" printlog INFOF "records: ${records[@]}" else r=$(evaluate "$node.value") eval $(printf '%s=%s' "$identifier" "$r") printlog INFOF "Let $identifier=$r" unset r fi unset content identifier [[ -n $next ]] \ && unset next \ && printlog INFOF "$node.next is not empty, evaluating it." \ && evaluate "$node.next" ;; # [...] esac ```

... And that goes for the rest of the file.

When I tried to run it with 1.000.000 as the input for sum, I got that "ksh: : Memory fault" error, but I went further and enabled tracing on my script to see exactly what happened: It breaks when $n$ is equal to 999766, as you can see. At first, I thought that maybe my interpreter is overloading KornShell, so, for conscience's sake, I implemented the exact same algorithm in pure KornShell:

function sum {
  n=$1
  if (( n == 1 )); then
    echo $n
  else
    echo $(( n + $(sum $(( n - 1 ))) ))
  fi
}

First, I ran it with 15 as $n$. It printed 15, just as expected, then I tested it again with 1.000.000 and got another "Memory fault", with my shell getting killed and falling back to the first instance.

So I decided that it would be reasonable to know if it also stops when $n$ is 999766 or not, so I enabled tracing this time:

It went a little bit further but, like before, it also broke.

I'm using version 93u+m/1.0.6 from June 13th 2023, but this also happens on older versions of KornShell such as 93u+m/1.0.0-beta.2 from December 17th 2021. This can be seen when running both the A.S.T. and the native function over Copacabana Linux, which uses the said version of KornShell: From this, you can take the conclusion that this, let's say, bug wasn't caused by anyone recently, it was always there.

After all of this, I have two questions: how much of this is my fault as a programmer --- not as the tester 😅 --- and what could this actually be? My bet, before anyone figures it out, is that KornShell doesn't have something such as a "long int" or "BigInt" implementation --- and, in my humble opinion, it actually doesn't need to have such thing since it's a Shell that works thoroughly well for programming, not a mathematics-oriented programming language; what calls for another question: is it worth fixing or it's just me (ab)using KornShell 93 capabilities as a programming language?

Some references that may help when debugging further: My interpreter (herbiec) File containing tracing of herbiec (herbiec_sum_1000000.txt) The sum A.S.T. (sum.json.txt)

Merci for the attention in advance.

[phidebian]

Ksh functions recursion stack deep level is 1024 meaning you gotta remove your tail recursion if you plan to go beyond this point.

May be something along this lines.

$ function sum
{ integer s i n
  n=$1
  for((s=i=0;i<=n;i++))
  { ((s+=i))
  }
  echo $s
}

$ sum 5
15

$ sum 1000000
500000500000

ksh93 do have the integer type, implemented internally as double, so the the INT_MAX is 0x7fffffffffffffff and INT_MIN is 0x800000000000

$ integer x=0x7fffffffffffffff
$ printf "%d\n" $x
9223372036854775807

$ x=0x8000000000000000        
$ printf "%d\n" $x    
-9223372036854775808

[takusuman]

Ksh functions recursion stack deep level is 1024 meaning you gotta remove your tail recursion if you plan to go beyond this point.

Nice to know the stack deep level. Well, I haven't a lot of places to go to do not use recursion because, as I showed, I'm not programming the executed code by myself, just the interpreter.

ksh93 do have the integer type, implemented internally as double, so the the INT_MAX is 0x7fffffffffffffff and INT_MIN is 0x800000000000

$ integer x=0x7fffffffffffffff
$ printf "%d\n" $x
9223372036854775807

$ x=0x8000000000000000        
$ printf "%d\n" $x    
-9223372036854775808

Well, I knew about types on ksh93, but I thought the problem was the integer type. This proves that the problem isn't the internal integer size on KornShell, but the stack deepness. Merci!