Ackerman's function

[tavmem]

This issue was identified by @bakul while exploring issue #537

I tried running Ackerman's function to see if there are any leaks 
(and to see function call overhead without very deep nesting)...

  c:0
  ack:{c+:1;:[x;:[y;_f[x-1;_f[x;y-1]];_f[x-1;1]];y+1]}
  ack[3;5]

This is significantly slower than k3 and uses much more memory. 
The ps command reveals RSS of 2240KB & 77ms for k3 and 
37348KB & 25281ms for kona on FreeBSD-x86. 

For ack[3;6] k3 RS is 2336KB and 314 ms, but kona ran out of stack. 
Note that stack depth is only 510 frames for ack[3;6] as can be measured by the 
following code under k3. 

Note that even on an amd64 machine kona runs out of stack 
(on amd64 machine \w shows max used of 206MB).

  c:0;d:0
  ack:{:[d<z;d+:1];c+:1;:[x;:[y;_f[x-1;_f[x;y-1;z+1];z+1];_f[x-1;1;z+1]];y+1]}
  \t ack[3;6;0]

Looks like the stack error may be a separate issue but there is either a memory leak 
or the function call overhead (in time as well as space) is quite high.

[tavmem]

Documenting my trial with ack[3;5]

K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
\ for help. \\ to exit.

  c:0
  ack:{c+:1;:[x;:[y;_f[x-1;_f[x;y-1]];_f[x-1;1]];y+1]}
  \t ack[3;5]
65
  \w
61520 1048576 0

kona      \ for help. \\ to exit.

  c:0
  ack:{c+:1;:[x;:[y;_f[x-1;_f[x;y-1]];_f[x-1;1]];y+1]}
  \t ack[3;5]
3991
  \w
used now : 3136 (36495360 0)
max used : 36475264
symbols  : k .k (nil) ack _f c x localhost.localdomain t y z 
count    : 11

$ ps -aux
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
tom       2681  0.0  0.0 222184  2728 pts/2    S+   15:13   0:00 rlwrap -n ./k
tom       2682  0.0  0.0   5876   904 pts/0    Ss+  15:13   0:00 ./k
tom       2803  0.0  0.0 222184  2724 pts/1    S+   15:14   0:00 rlwrap -n ./k
tom       2804  6.3  0.4  48356 38400 pts/4    Ssl+ 15:14   0:04 ./k

Comment; I think that the problem is the current design of the parser. My "guesses" are that:

• kona (pretty much) parses the same function from scratch on each iteration of a recursion, and stores the full parse results redundantly at each level of recursive depth for ultimate execution.
• k3 probably parses a function to some intermediate form, and then recursions use that intermediate form, and that k3 probably does not redundantly save the same parse results separately for each level of recursive depth.

This gets back to a comment you made earlier on a separate issue: The parser really should be re-written.

[tavmem]

To test for memory leaks, I added Ackerman's function to the test suite.

  TC( 7, c:0; f:{c+:1;:[x;:[y;f[x-1;f[x;y-1]];f[x-1;1]];y+1]}; f[2;2] )    // Ackerman's function

results:

$ ./k_test
t:0
t:50
t:100
t:150
t:200
t:250
t:300
t:350
t:400
t:450
t:500
t:550
t:600
t:650
t:700
t:750
t:800
t:850
t:900
t:950
t:1000
t:1050
t:1100
Test pass rate: 1.0000, Total: 1116, Passed: 1083, Skipped: 33, Failed: 0, Time: 0.334735s
OK
kona      \ for help. \\ to exit.

[tavmem]

Here is the outline of a plan to improve the performance of the kona parser.

This would take considerable work, and might require a rewrite of the kona execution modules since they expect the current parser output. This is not currently a priority for me. There are currently 2 "crash" issues and 6 "bug" issues open in kona. I would like to close all "crash" and "bug" issues first.

There is a famously efficient implementation of A+ that is open source. This implementation was also written by Arthur Whitney (and made available by Morgan Stanley). You can find a successful build of A+ on Fedora-26 with XEmcacs 21-4.34 (for the APL characters) at https://github.com/tavmem/aplus

Plan:

• test the performance of Ackerman's function on A+, to verify that it outperforms kona similarly to how k2.8 outperforms kona.
• study the code to see how Arthur achieves this performance.
• rewrite sections of kona using similar techniques