Recursive call overrides earlier data

[hoosierEE]

I'm trying to parse an expression tree like f(g(), h()) using recursive descent, but instead of getting a tree like this:

   f
 /   \
g     h

I get something more like this:

   h
 / 
h

This is the full source code:

tokens: ((`id;"F")
(`oparen;"(")
(`id;"G")
(`oparen;"(")
(`cparen;")")
(`comma;",")
(`id;"H")
(`oparen;"(")
(`cparen;")")
(`cparen;")"))

peek: {x~tokens[;0][0]}
eat: {
  t: *tokens
  tokens :: 1 _ tokens
  if[~x~t[0]; \echo "no match for ",$x; : 0]
  t}

parse_call: {
  name:eat[`id]@1
  ae: parse_arg_exprs()
  .((`name;name);(`arg_exprs;ae))}

parse_arg_exprs: {
  arg_exprs:()
  eat[`oparen]
  if[~peek[`cparen]
    arg_exprs:,parse_call()
    while[peek[`comma]
      eat[`comma]
      arg_exprs,:,parse_call()]]
  eat[`cparen]
  arg_exprs}

parse_call()

And this is the result:

.((`name;"H";)
  (`arg_exprs
   ,.((`name;"H";)
      (`arg_exprs;();))
   ))

To me, it seems that the deeper nested call to parse_arg_exprs overwrites the "parent". Also, it either skips the last node or drops an earlier node, because the resulting tree is missing a leaf. Am I misunderstanding Kona scoping rules or is this a bug?

[edit] For completeness, here is what I expected to see as a correct result:

.((`name;"F";)
  (`arg_exprs
   .((`name;"G";)
      (`arg_exprs;();))
   .((`name;"H";)
      (`arg_exprs;();))
   ))

[bakul]

On Wed, 16 May 2018 11:01:28 -0700 Alex Shroyer ***@***.***> wrote: I'm trying to parse an expression tree like `f(g(), g())` using recursive des cent, but instead of getting a tree like this: ``` f / \ g h ``` I get something more like this: ``` h / h ``` This is the full source code: ```/ F(G(),H()) tokens: ((`id;"F") (`oparen;"(") (`id;"G") (`oparen;"(") (`cparen;")") (`comma;",") (`id;"H") (`oparen;"(") (`cparen;")") (`cparen;")")) peek: {x~tokens[;0][0]} eat: { t: *tokens tokens :: 1 _ tokens if[~x~t[0]; \echo "no match for ",$x; : 0] t} parse_call: { ***@***.*** ae: parse_arg_exprs() .((`name;name);(`arg_exprs;ae))} parse_arg_exprs: { arg_exprs:() eat[`oparen] if[~peek[`cparen] arg_exprs:,parse_call() while[peek[`comma] eat[`comma] arg_exprs,:,parse_call()]] eat[`cparen] arg_exprs} parse_call() ``` And this is the result: Here's the full result: ``` .((`name;"H";) (`arg_exprs ,.((`name;"H";) (`arg_exprs;();)) )) ``` To me, it seems that the deeper nested call to `parse_arg_exprs` overwrites t he "parent". Am I misunderstanding Kona scoping rules or is this a bug?

This is a bug.

[hoosierEE]

For what it's worth, this reminded me of a quirk (not a bug) of Python's scoping rules: https://stackoverflow.com/a/233835/2037637 . I wondered if a similar thing is going on in Kona.

[bakul]

On Wed, 16 May 2018 19:27:42 -0700 Alex Shroyer ***@***.***> wrote: For what it's worth, this reminded me of a quirk (not a bug) of Python's scop ing rules [link](https://stackoverflow.com/a/233835/2037637). I wondered if a similar thing is going on in Kona.

k3 (and kona by extension) variables have only global scope or local (function level) scope. Your code works as expected in k3.

[tavmem]

2 simple cases:
This one fails:

$ cat tst1.k
sub:{a:2}
foo:{a:1; sub(); a}
foo()

$ rlwrap -n ./k tst1
kona      \ for help. \\ to exit.

This one works:

$ cat tst2.k
foo:{a:1; {a:2}; a}
foo()

$ rlwrap -n ./k tst2
kona      \ for help. \\ to exit.

1

[hoosierEE]

Kona console:

  {a:1;{a:3}();a}()
  {a:1;{b:3}();a}()
  {a:1;{b:3;}();a}()
1
  {a:1;{a:3;}();a}()
1

It seems like the inner function doesn't return anything (not even nil) and breaks the outer function.

[hoosierEE]

There are several oddities with assignment inside a void function:

  {a:2; {a:3}(); a}() / no output
  {a:2; {a:3;}(); a}() / returns 2
2
  f:{a:2; {a:3}(); a}() / no output, however f gets 2
  f
2
  g:{a:2; {a:3;}(); a}() / added semicolon
2
  g
2

@tavmem do you think this is the root cause of the bug I saw with the recursive functions?

[tavmem]

It could be. Hard to say for sure.
It's probably best to try & fix the simple oddity cases and see if your recursive case becomes resolved.

[tavmem]

In a k2.8 console

$ rlwrap -n ./k
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
Evaluation. Not for commercial use. 
\ for help. \\ to exit.

  {a:2; {a:3}(); a}()
2
  {a:2; {a:3;}(); a}()
2
  f:{a:2; {a:3}(); a}()
  f
2
  g:{a:2; {a:3;}(); a}()
  g
2

[tavmem]

The first "oddity"

{a:2; {a:3}(); a}()     / no output

is a regression.

It first shows up in commit 0e63515 made on Aug 10, 2017 titled "suppress display on amend".

[tavmem]

First "oddity" is fixed.

The following cases are still problematic:

$ rlwrap -n ./k
kona      \ for help. \\ to exit.

$ rlwrap -n ./k
kona      \ for help. \\ to exit.

  f:{a:2; {a:3}(); a}()
2
  f
2
  g:{a:2; {a:3;}(); a}()
2
  g
2

[tavmem]

All 3 "oddities" are fixed. Your recursive case is not resolved.

$ rlwrap -n ./k
kona      \ for help. \\ to exit.

  {a:2; {a:3}(); a}()
2
  f:{a:2; {a:3}(); a}()
  f
2
  g:{a:2; {a:3;}(); a}()
  g
2

[tavmem]

Here's the next attempt at a relevant "simplistic" case:
In k2.8

  foo:{a:x; sub(a); a}
  sub:{:[x=0; a:x; foo(0)]}
  foo(2)
2

In kona:

  foo:{a:x; sub(a); a}
  sub:{:[x=0; a:x; foo(0)]}
  foo(2)
0

[tavmem]

This issue is not a regression. I went back to the code as of commit 611fdca titled "Fix backslash commands with a leading space" made on June 23, 2011 and got similar results:

  foo:{a:x; sub(a); a}
{a:x; sub(a); a}
  sub:{:[x=0; a:x; foo(0)]}
{:[x=0; a:x; foo(0)]}
  foo(2)
0

[bakul]

I suspect the issue may be that the symbol table associated with the function definition is being modified, rather than each function instantiation getting its own copy of the symbol table. For each instantiation (when a function is called), a fresh dictionary needs to be created and pushed on the stack. When the function is exited, it is popped from the stack and destroyed.

[tavmem]

If the subroutine is redefined as a void function, the problem persists
In k2.8:

  foo:{a:x; {:[x=0; a:x; foo(0)]}a; a}
  foo 2
2

In kona:

  foo:{a:x; {:[x=0; a:x; foo(0)]}a; a}
  foo 2
0

[tavmem]

@bakul:
I agree with your diagnosis.

[tavmem]

However, if you make everything a void function, the problem disappears:
in k2.8:

  {a:x; {:[x=0; a:x; _f(0)]}a; a}2
2

in kona:

  {a:x; {:[x=0; a:x; _f(0)]}a; a}2
2

[tavmem]

Just to document all variations:
Using a hybrid approach (define foo, but use a void function at the top level), also works fine.
in k2.8:

  foo:{a:x; {:[x=0; a:x; foo(0)]}a; a}
  {a:x; {:[x=0; a:x; foo(0)]}a; a}2
2

in kona:

  foo:{a:x; {:[x=0; a:x; foo(0)]}a; a}
  {a:x; {:[x=0; a:x; foo(0)]}a; a}2
2

[tavmem]

That begs the following question:
Does the hybrid approach work on the original recursive case?

$ cat hybrid.k
tokens: ((`id;"F")
(`oparen;"(")
(`id;"G")
(`oparen;"(")
(`cparen;")")
(`comma;",")
(`id;"H")
(`oparen;"(")
(`cparen;")")
(`cparen;")"))

peek: {x~tokens[;0][0]}

eat: {
  t: *tokens
  tokens :: 1 _ tokens
  if[~x~t[0]; \echo "no match for ",$x; : 0]
  t}

parse_call: {
  name:eat[`id]@1
  ae: parse_arg_exprs()
  .((`name;name);(`arg_exprs;ae))}

parse_arg_exprs: {
  arg_exprs:()
  eat[`oparen]
  if[~peek[`cparen]
    arg_exprs:,parse_call()
    while[peek[`comma]
      eat[`comma]
      arg_exprs,:,parse_call()]]
  eat[`cparen]
  arg_exprs}

{name:eat[`id]@1; ae:parse_arg_exprs(); .((`name;name);(`arg_exprs;ae))}()

Yes ... in k2.8:

$ rlwrap -n ./k ~/k2.8/hybrid
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
Evaluation. Not for commercial use. 
\ for help. \\ to exit.

.((`name;"F";)
  (`arg_exprs
   (.((`name;"G";)
      (`arg_exprs;();))
    .((`name;"H";)
      (`arg_exprs;();)))
   ))

No ... in kona:

$ rlwrap -n ./k ~/k2.8/hybrid
kona      \ for help. \\ to exit.

type error

> 

[tavmem]

A better listing of simple cases that "Don't work" and that "Do work".
(All the cases do work in k2.8)

Don't work:

  foo:{a:x; {:[x=0; a:x; foo(0)]}a; a}; foo(2)
0
  foo:{a:x; sub(a); a};  sub:{:[x=0; a:x; foo(0)]};  foo(2)
0

Do work:

  {a:x; {:[x=0; a:x; _f(0)]}a; a}2
2
  foo:{a:x; sub(a); a};  sub:{:[x=0; a:x; _f(0)]}; foo(2)
2
  foo:{a:x; {:[x=0; a:x; _f(0)]}a; a}; foo(2)
2

[tavmem]

It was interesting that this works in Kona: foo:{a:x; {:[x=0; a:x; _f(0)]}a; a}; foo(2)
while this fails: foo:{a:x; {:[x=0; a:x; foo(0)]}a; a}; foo(2)

The reason is not what I expected.
Kona seems to be interpreting _f(0) as a command to execute {:[x=0; a:x; _f(0)]}0
which is quite different than to execute {a:x; {:[x=0; a:x; _f(0)]}a; a}0

[bakul]

I think the real issue is early binding. The following snippet will behave differently in k3 and kona:

  f:{:[x>0;2*f[x-1];1]}
  g:f
  f:{0}
  g 4

In processing lambda expression on RHS, kona replaces the inner f with self reference. This changes the definition of g to a recursive one so redefining f later has no effect on g and g 4 yields 16. Not so in k3, where g 4 will yield 0. I alluded to this early binding issue in an old bug report (don’t recall which one now). To see the difference, compare the contents of .k for both interpreters after each definition. Do the same for mutually recursive functions.

[tavmem]

I agree that the "early binding" you describe is a problem that needs to be fixed
(and probably should be added as a separate issue -- so we don't lose it yet again).

However, I think that the incorrect result in the simplified example that we have been discussing is somewhat different (but could also be described as a "binding" problem):

 f:{a:x; {:[x=0; a:x; f(0)]}a; a}
 .k
.,(`f;{a:x; {:[x=0; a:x; f(0)]}a; a};)

 f 2
0

Here, kona did not replace the inner f with self reference.

Consider the following (that gives the correct result):

 f:{a:x; {:[x=0; a:x; a:5]}a; a}
 f 2
2

The assignments to "a" in the lambda of the second example have no effect on the correct value of "a" reported by the outer "f".

In the first example, the two executions of "f" (inner & outer) should be completely independent.
However, the value assigned to "a" by the inner f (in the lambda) gets "bound" to the value of "a" incorrectly reported by the outer "f".

[tavmem]

A diagnosis of the problem:

The function "f" is stored as a type 7.
enum TYPE_SEVEN_MEMBERS {CONTEXT,DEPTH,CODE,LOCALS,PARAMS,CONJ,CACHE_WD,CACHE_TREE,TYPE_SEVEN_SIZE};
The initial occurrence looks like this, with the CACHE_TREE (a7) empty:

4 7 3   {a:x; {:[x=0; a:x; f(0)]}a; a}
        a0:        .k
        a1:        (nil)
        a2:        0x7fdb7b1ec898            1 -3 28   "a:x; {:[x=0; a:x; f(0)]}a; a"
        a3:        0x7fdb7b1ec818            1 5 1
   .,(`a;;)
        0x7fdb7b1ecc58            1 0 3
   (`a;;)
        0x7fdb7b1ec058            11 6 0
        0x7fdb7b1ec058            11 6 0
        0x7fdb7b1ecb58 0xc5d4c0  1 4 1   `a
        a4:        0x7fdb7b1ec858            1 5 1
   .,(`x;;)
        0x7fdb7b1ec998            1 0 3
   (`x;;)
        0x7fdb7b1ec058            11 6 0
        0x7fdb7b1ec058            11 6 0
        0x7fdb7b1ecdd8 0xc5a2b0  1 4 1   `x
        a5:
        a6:
        a7:

Without getting overly verbose, the CACHE_TREE goes through the following transitions:
First, while processing the outer "f"

        a7:        0x7fdb7b1ec658            1 5 2
   .((`x;2;)
     (`a;;))

        a7:        0x7fdb7b1ec658            1 5 2
   .((`x;2;)
     (`a;2;))

Then, when processing the inner "f"

        a7:        0x7fdb7b1ec658            1 5 2
   .((`x;0;)
     (`a;2;))

        a7:        0x7fdb7b1ec658            1 5 2
   .((`x;0;)
     (`a;0;))

When getting back to the outer "f", the CACHE_TREE still contains the values from the inner "f".

[bakul]

Re: binding. Sorry for the confusion. Looks like you are on the right track in spite of that :-)

I modified the program to print before and after values and see interesting results!

Kona:

  foo:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; `0:"x=",($x),", a=",($a),"\n"; a}; foo(3)
x=3
x=2
x=1
x=0
x=0, a=0
type error
foo:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; `0:"x=",($x),", a=",($a),"\n"; a}; foo(3)
at execution instance 12 of "0:"

k3:

  foo:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; `0:"x=",($x),", a=",($a),"\n"; a}; foo(3)
x=3
x=2
x=1
x=0
x=0, a=0
x=1, a=1
x=2, a=2
x=3, a=3
3

[tavmem]

Yes ... thanks ... quite interesting.
I wondered whether your example blew up on the "x=1" or on the "a=1".
It's the "x=1".

k2.8

  f:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; f(x-1)]}a; `0:("x=",$x),"\n"; `0:("a=",$a),"\n"; a}
  f 3
x=3
x=2
x=1
x=0
x=0
a=0
x=1
a=1
x=2
a=2
x=3
a=3
3

kona

  f:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; f(x-1)]}a; `0:("x=",$x),"\n"; `0:("a=",$a),"\n"; a}
  f 3
x=3
x=2
x=1
x=0
x=0
a=0
type error

[tavmem]

Also interesting ... kona:

  f:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; f(x-1)]}a; `0:("a=",$a),"\n"; a}
  f 3
x=3
x=2
x=1
x=0
a=0
a=0
a=0
a=0
0

[tavmem]

Simply in the interest of documentation, in kona:

  f:{a:x; {:[x=0; a:x; f(x-1)]}a; `0:("x=",$x),"\n"; a}
  f 1
x=0
type error

The type error occurs in the function vf_ex contained in file ~/kona/src/kx.c

  if(2==k && a && b){ fnc=DT[(L)q].text;
    if(fnci<127){fncp[fnci]=q; fnci++;}
    if(cls && a->t==6) z=((K(*)(K,K))DT[(L)q].func)(cls,b);
    else z=((K(*)(K,K))DT[(L)q].func)(a,b);                 // WHEN EXECUTING THIS LINE
    GC; }
  //? (+).1 -> err ; {[a;b]a+b} 1 -> err
  if(2==k && !a){VE; GC;} //Reachable? Projection?

[tavmem]

But ... (just saying) ... this does seem to reinforce the "need for two paths":
Given a recursive descent parser with inputs: string, dictionary, and function,
sometimes the dictionary is a pointer to a global dictionary (K* dict)
sometimes the dictionary is an actual local dictionary (K dict)

[tavmem]

Maybe ... resolved by a cover function.

[bakul]

As I noted earlier, there is a solution where you don’t need a local dictionary or a dictionary stack but that’ll require very simple compilation, where ref to a variable becomes an index into local frame. Though this may be hard to implement in kona at present. But even with this scheme you’d need the global dictionary (.k). In k3

a:1
f:{a:2; .[`a;();:;222]}
a

You can see that this form of amend changes the global a, not the local a. This shows you need .k but you can compile away local variable and parameter references into stack indices.

[tavmem]

Very interesting. Thanks!
This also gets around the limitation (in parenthesis) documented on page 143 of the K reference manual:

If b is a global variable and the expression b::y appears in a function expression, the effect to assign the contents of y to the global variable b in the same directory as where the function is defined. (However, if the definition also contains an ordinary assignment b: z then b will be local).

[tavmem]

Implementing either solution in kona is difficult.

I set up a counter to track the number of times that the recursive parser
K wd_(S s, int n, K*dict, K func)
is called, and to report the count each time an execution K ex(K a) completes.

The results for this issue (as defined) is:

$ rlwrap -n ./k rcr
kona      \ for help. \\ to exit.

12 13 20 27 28 41 42 65 66 77 91 94 103 117 120 123 123 123 126 129 138 
152 155 158 158 158 161 164 164 164 164  
.((`name;"H";)
  (`arg_exprs
   ,.((`name;"H";)
      (`arg_exprs;();))
   ))

The parser is called 164 times, during 31 completed executions.
(Where the count stays constant, is probably where recursive executions are completing.)
Figuring out which of the 164 recursions need the global vs a local dictionary is daunting.
My trials so far have resulted in different (also incorrect) results.

I think my next step is to formulate a very simple example that causes a similar problem.

[tavmem]

Here are a couple of possible simplifications:

First, reduce the token definition from 10 lines down to 6 (to cut down the number of recursions):

tokens: ((`id;"F")
(`oparen;"(")
(`id;"G")
(`oparen;"(")
(`cparen;")")
(`cparen;")"))

Second, as an initial step to localizing dictionaries where needed,
examine (track) the variable "name" as defined in the function "parse_call"

parse_call: {
  name:eat[`id]@1
  ae: parse_arg_exprs()
  .((`name;name);(`arg_exprs;ae))}

The value in "name" must always be "local" to the recursion level, and must change back to "F" as the recursions complete.

[tavmem]

A much simpler script that also fails:

$ cat tst.k
tokens: ((`id;"F")
(`id;"G")
(`id;"H"))

call:{
  name: (*tokens)[1]
  tokens :: 1 _ tokens
  if[name~"H";  : ""] 
  ` 0: name,"\n"
  call()
  ` 0: name,"\n" }

call()

$ rlwrap -n ./k tst
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
\ for help. \\ to exit.

F
G
G
F

$ rlwrap -n ./k tst
kona      \ for help. \\ to exit.

  F
G
H
H

[tavmem]

An even simpler script, that fails with fewer parse/execute cycles:

$ cat tst.k
tokens: ((`id;"F")
(`id;"G"))

call:{
  name: (*tokens)[1]
  tokens :: 1 _ tokens
  if[name~"G";  : ""] 
  ` 0: name,"\n"
  call()
  ` 0: name,"\n" }

call()

$ rlwrap -n ./k tst
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems 
\ for help. \\ to exit.

F
F

$ nano tst.k
$ rlwrap -n ./k tst
kona      \ for help. \\ to exit.

  F
G

[tavmem]

Simpler ... fewer calls to "parser" and to "execute":

tk:("F";"G")
call:{ nm:*tk; tk::1 _ tk; if[nm~"G"; :0]; call(); nm }
call()

$ rlwrap -n ./k tst
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
\ for help. \\ to exit.

"F"

$ rlwrap -n ./k tst
kona      \ for help. \\ to exit.

  "G"

Using this simple script in Kona:
3 lines read
17 calls to "parser"
5 calls to "execute"

[tavmem]

Making a change to a single line of code gives the correct result:

$ git diff
diff --git a/src/kx.c b/src/kx.c
index 4eed6fa..2038f9a 100644
--- a/src/kx.c
+++ b/src/kx.c
@@ -638,7 +638,7 @@ K vf_ex(V q, K g)
         if(t) cd(kV(f)[CACHE_WD]);
         K fc = kclone(f); //clone the function to pass for _f
         cd(kV(fc)[CONJ]); kV(fc)[CONJ]=0;
-        kV(fc)[DEPTH]++; fw=wd_(kC(o),o->n,&tree,fc); kV(f)[CACHE_WD]=fw; cd(fc); }
+        kV(fc)[DEPTH]++; K tc=kclone(tree); fw=wd_(kC(o),o->n,&tc,fc); kV(f)[CACHE_WD]=fw; cd(fc); }

rcr.k (short for recursion.k) is the name I gave to the original problematic script listed at the beginning of this issue.

$ rlwrap -n ./k rcr
kona      \ for help. \\ to exit.

  .((`name;"F";)
  (`arg_exprs
   (.((`name;"G";)
      (`arg_exprs;();))
    .((`name;"H";)
      (`arg_exprs;();)))
   ))

However, running k_test (with the change) results in memory leaks for 215 tests:

./k_test
...
Test pass rate: 0.7987, Total: 1100, Passed: 853, Skipped: 32, Failed: 215, Time: 0.316603s
fail

It seems that;

• this change should be implemented as a branch used only in case of a recursive call,
• when it is used, appropriate "clean-up" will be necessary (to eliminate memory leaks).

But ... is there any way to determine that a recursive call is executing?

[bakul]

Don't you need a cd(tc);?

[tavmem]

i am dropping the idea of a "separate branch" as as I don't see an easy way to identify a recursive call.

Declaring tc at the start of K vf_ex(V q, K g) and cd(tc); at the end reduces the fails from 215 to 36. Only 2 of the "fails" are memory leaks, 34 are "real" fails.

$ git diff
diff --git a/src/kx.c b/src/kx.c
index 4eed6fa..ee9b963 100644
--- a/src/kx.c
+++ b/src/kx.c
@@ -473,6 +473,7 @@ K dv_ex(K a, V *p, K b)
 K vf_ex(V q, K g)
 {
+  K tc=0;
   if (interrupted) {interrupted=0; R BE;}
 
   //V w=(*(V*)q);
@@ -638,7 +639,7 @@ K vf_ex(V q, K g)
         if(t) cd(kV(f)[CACHE_WD]);
         K fc = kclone(f); //clone the function to pass for _f
         cd(kV(fc)[CONJ]); kV(fc)[CONJ]=0;
-        kV(fc)[DEPTH]++; fw=wd_(kC(o),o->n,&tree,fc); kV(f)[CACHE_WD]=fw; cd(fc); }
+        kV(fc)[DEPTH]++; tc=kclone(tree); fw=wd_(kC(o),o->n,&tc,fc); kV(f)[CACHE_WD]=fw; cd(fc); }
 
@@ -684,7 +685,7 @@ K vf_ex(V q, K g)
 
 cleanup:
-  cd(g);
+  cd(g); cd(tc);
   R z;
 }

./k_test
...
Test pass rate: 0.9663, Total: 1100, Passed: 1032, Skipped: 32, Failed: 36, Time: 0.260224s
fail

All 34 of the "real" fails involve "subfunctions".
eg:

Failed. These are not equal:
1 2 , {a:x; {a,x}.,2}1
********************************
1 2
--------------------------------
(;2)

Some (or all) of the code that did handle subfunctions previously may need to be removed!

[tavmem]

Of the 2 memory leak fails:

One also had a subfunction:

Failed: Memory Leak - 15 20 25, f:{a:x; 1 2 3{a+x*y}\:5} ;f 10

The second should not have been in the test list at all

TC(a:{a[x]}; a 5, )

Both k2.8 and kona report "stack error" when this test is run from the console

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

  a:{a[x]}; a 5
stack error
{a[x]}
 ^
>

$ rlwrap -n ./k
kona      \ for help. \\ to exit.

  a:{a[x]}; a 5
stack error
a:{_f[x]}; a 5
 ^
>

[tavmem]

Pursuing the "separate branch" option again.
It's difficult to identify recursion, esp. if the recursive call is embedded in another function.
Much easier to tell if a function contains a subfunction.

But, then again, what about a function with a subfunction that is called recursively?

[tavmem]

With these changes:

$ git diff
diff --git a/src/kx.c b/src/kx.c
@@ -473,6 +473,7 @@ K dv_ex(K a, V *p, K b)
 K vf_ex(V q, K g)
 {
+  K tc=0;
   if (interrupted) {interrupted=0; R BE;}
 
   //V w=(*(V*)q);
@@ -638,7 +639,11 @@ K vf_ex(V q, K g)
         cd(kV(fc)[CONJ]); kV(fc)[CONJ]=0;
-        kV(fc)[DEPTH]++; fw=wd_(kC(o),o->n,&tree,fc); kV(f)[CACHE_WD]=fw; cd(fc); }
+        kV(fc)[DEPTH]++;
+        I tt=0; DO(o->n, if(kC(o)[i]=='{')tt=1;)
+        if(tt) fw=wd_(kC(o),o->n,&tree,fc);
+        else { tc=kclone(tree); fw=wd_(kC(o),o->n,&tc,fc); }
+        kV(f)[CACHE_WD]=fw; cd(fc); }
 
       #ifdef DEBUG
       if(stk1>5) {cd(g); kerr("stack"); R _n();}
@@ -684,7 +689,7 @@ K vf_ex(V q, K g)
 cleanup:
-  cd(g);
+  cd(g); cd(tc);
   R z;
 }
 
diff --git a/src/tests.c b/src/tests.c
@@ -657,7 +657,7 @@ Z I tests02()
   TC(skip, 5 6, a 5 6)             // value error
-  TC(a:{a[x]}; a 5, )
+  TC(skip, a:{a[x]}; a 5, )        // stack error

we are down to 2 fails:

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

Failed. These are not equal:
(2 0;2 1) , for:{[n;f]f'!n}; {[i]for[i]{[j]i,j}}2
********************************
(2 0
 2 1)
--------------------------------
((;0)
 (;1))


Failed. These are not equal:
(();,1 0;(2 0;2 1)) , for:{[n;f]f'!n}; for[3]{[i]for[i]{[j]i,j}}
********************************
(()
 ,1 0
 (2 0
  2 1))
--------------------------------
(()
 ,(;0)
 ((;0)
  (;1)))

t:700
t:750
t:800
t:850
t:900
t:950
t:1000
t:1050
Test pass rate: 0.9981, Total: 1100, Passed: 1065, Skipped: 33, Failed: 2, Time: 0.305472s
fail
kona      \ for help. \\ to exit.

[tavmem]

The 2 remaining fails demonstrate that the "separate branch" option does not work when there is a combination of recursion and subfunction. Documenting which branch is taken on each iteration (and the target string) gives the following results:

-        kV(fc)[DEPTH]++; fw=wd_(kC(o),o->n,&tree,fc); kV(f)[CACHE_WD]=fw; cd(fc); }
+        kV(fc)[DEPTH]++;
+        I tt=0; DO(o->n, if(kC(o)[i]=='{')tt=1;)
+        O("tt: %lld   kC(o): %s\n",tt,kC(o));
+        if(tt) fw=wd_(kC(o),o->n,&tree,fc);
+        else { tc=kclone(tree); fw=wd_(kC(o),o->n,&tc,fc); }

$ rlwrap -n ./k
kona      \ for help. \\ to exit.

  for:{[n;f]f'!n}; {[i]for[i]{[j]i,j}}2
tt: 1   kC(o): [i]for[i]{[j]i,j}
tt: 0   kC(o): [n;f]f'!n
tt: 0   kC(o): [j]i,j
tt: 0   kC(o): [j]i,j
((;0)
 (;1))
  
  
  for:{[n;f]f'!n}; for[3]{[i]for[i]{[j]i,j}}
tt: 0   kC(o): [n;f]f'!n
tt: 1   kC(o): [i]for[i]{[j]i,j}
tt: 0   kC(o): [n;f]f'!n
tt: 1   kC(o): [i]for[i]{[j]i,j}
tt: 0   kC(o): [n;f]f'!n
tt: 0   kC(o): [j]i,j
tt: 1   kC(o): [i]for[i]{[j]i,j}
tt: 0   kC(o): [n;f]f'!n
tt: 0   kC(o): [j]i,j
tt: 0   kC(o): [j]i,j
(()
 ,(;0)
 ((;0)
  (;1)))

I am turning attention back to subfunction processing.
Hopefully, subfunctions can be made to work when using the same path required for recursion, i.e.:

else { tc=kclone(tree); fw=wd_(kC(o),o->n,&tc,fc); }

[hoosierEE]

@tavmem and @bakul I just want to say thank you for working on this bug. It's been a good learning experience just to watch the process, and personally I really appreciate that there are people like you investing your time and effort into projects like this that benefit so many people.

Anyway, I appreciate your work. 👍

[tavmem]

Thanks for the feedback! You are very welcome. It’s been quite a learning experience for me too! Best, Tom

…

On Fri, Nov 1, 2019 at 8:25 AM Alex Shroyer ***@***.***> wrote: @tavmem <https://github.com/tavmem> and @bakul <https://github.com/bakul> I just want to say thank you for working on this bug. It's been a good learning experience just to watch the process, and personally I really appreciate that there are people like you investing your time and effort into projects like this that benefit so many people. Anyway, I appreciate your work. 👍 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#521?email_source=notifications&email_token=AALEJJ4SDHL2TW7ICX2EPSDQRQN3BA5CNFSM4FAHDBNKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEC2ZCCA#issuecomment-548770056>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AALEJJYUVKLDI7N24JFUZLTQRQN3BANCNFSM4FAHDBNA> .

[bakul]

@hoosierEE , You're welcome but note that Tom did all the hard work!

Tom, this one still fails even with the latest sources (see #521 (comment)):

foo:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; `0:"x=",($x),", a=",($a),"\n"; a}; foo(3)`

[tavmem]

Thanks @bakul .... :-)

[tavmem]

Hey @bakul --
I have tried your example 2 ways in k2.8 (with and without the final backtick).
Neither one worked.
Maybe there is a typo?

$ rlwrap -n ./k
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
\ for help. \\ to exit.

  foo:{a:x; 0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; 0:"x=",($x),", a=",($a),"\n"; a}; foo(3)`
rank error
foo:{a:x; 0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; 0:"x=",($x),", a=",($a),"\n"; a}; foo(3)`
                                                                                           ^
>  \\

$ rlwrap -n ./k
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
\ for help. \\ to exit.

  foo:{a:x; 0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; 0:"x=",($x),", a=",($a),"\n"; a}; foo(3)
x=3
: No such file or directory
{a:x; 0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; 0:"x=",($x),", a=",($a),"\n"; a}
      ^
>  

[bakul]

I don't know where that last backtick came from. See the original comment #521 (comment) up in the thread. But my guess is most likely you didn't type in the whole expression as one line.

rlwrap k-2.8
K 2.8 2000-10-10 Copyright (C) 1993-2000 Kx Systems
Evaluation. Not for commercial use.
\ for help. \\ to exit.

  foo:{a:x; `0:("x=",$x),"\n"; {:[x=0; a:x; foo(x-1)]}a; `0:"x=",($x),", a=",($a),"\n"; a}; foo(3)
x=3
x=2
x=1
x=0
x=0, a=0
x=1, a=1
x=2, a=2
x=3, a=3
3

[tavmem]

Thanks !!
Will add this as issue #556.