Can't properly recurse anonymous functions and closures...

[GordonBGood]

V language doesn't allow uninitialized variables as does the Go language, and currently the compiler inserts a call to the already initialized value of an anonymous function or closure rather than the value being defined when called recursively, meaning that we can't do what can be done in Go by this means. An alternative method of achieving recursive closures is to use a combinator (although that is considerably more complex), but while this works, it does more huge allocations on every recursive level than expected so that memory-access crashes for very many levels of recursion and it is much much slower than it should be even when it works (say as compared to a Go version or any other language where recursion works).

V version: V 0.3.2 407bb66 OS: linux, Linux version 5.19.13-200.fc36.x86_64 (mockbuild@bkernel02.iad2.fedoraproject.org) (gcc (GCC) 12.2.1 20220819 (Red Hat 12.2.1-2), GNU ld version 2.37-36.fc36) #1 SMP PREEMPT_DYNAMIC Tue Oct 4 15:42:43 UTC 2022

What did you do?` In trying to what can be done in the Go language in implementing the basic Legendre prime counting function:

// trivial example to show problems with closure recursion...
// Legendre phi function is extremely recursive where:
//   phi(x, a) = phi(x, a - 1) - phi(x / p[a - 1], a - 1), where
//     `p` is an array of primes and `a` is the zero-based index to that array;
// called with phi(n, pisqrt)
//   where `pisqrt` is number of primes to square root of n
// then the count of primes to n is phi(n, pisqrt) + pisqrt - 1...

import math { sqrt }

// since closures/anonymous functions can't call themselves:
// z combinator for closure recursion...
// for simplicity, generics aren't used
type PhiF = fn (int, int) int
type PhiFF = fn (PhiF) PhiF
struct RecFunc { recfn (fn (RecFunc) PhiF) }
fn zcomb(f PhiFF) PhiF {
  g := fn [f] (x RecFunc) PhiF {
    return f(fn [x] (m int, a int) int {
      rf := x.recfn(x)
      return rf(m, a) }) }
  return g(RecFunc{ recfn: g }) }

// count using recursion...
fn count_primes_to(n int) int {
  if n <= 3 { if n < 2 { return 0 }
              else { if n < 3 { return 1 } else { return 2 } } }
  // need array of primes to square root of n; not particularly fast...
  sz0 := int(math.sqrt(f64(n))) - 1 // don't include 0 and 1!
  mut prms := []u32 { cap: sz0, len: sz0, init: u32(it + 2) }
  for i := 0; i < sz0; i++ {
    p := prms[i]
    if p == 0 { continue } // if already culled, not prime
    for c := p * p - 2; c < sz0; c += p { prms[c] = 0 } // cull multiples
  }
  prms = prms.filter(it != 0) // remove culled values

/*
  // attempt to directly recurse closure as per Go;
  // calls previously defined value -> incorrect result...
  mut phi := fn (q int, a int) int { return q }
  phi = fn [prms, phi] (q int, a int) int {
          if a <= 0 { return q }
          na := a - 1
          p := int(prms[na])
          if q <= p { return 1 }
          return phi(q, na) - phi(q / p, na)
        }
*/

  // make recursive closure function using combinator...
  prmsp := unsafe { &prms[0] }
  phi := zcomb(fn [prmsp] (f PhiF) PhiF {
    return fn [prmsp, f] (q int, a int) int {
      if a <= 0 { return q }
      na := a - 1
      p := unsafe { int(prmsp[na]) }
      if q <= p { return 1 }
      return f(q, na) - f(q / p, na)
    }
  })

  return phi(n, prms.len) + prms.len - 1
}

compiled with --prod --no-debug

What did you expect to see?

The correct answer of 50847534, which is the number of prime up to a billion (1e9) should only take about a half of a second to complete with this algorithm.

What did you see instead?

When counting primes to 100_000_000 it takes about 2.5 seconds rather than just a few ten's of milliseconds, although with the correct result of 5761455.

When counting primes to 1_000_000_000 as per the above code, it crashes with the following error after about four and a half seconds: 7fb45c6b9000 : at ???: RUNTIME ERROR: invalid memory access /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2682: by anon_fn_8ea50ba4ea1cc847_int_intint_2022 /tmp/v_1000/Recursion.18096845170213720548.tmp.c:2647: by anon_fn_8ea50ba4ea1cc847_int_intint_784

As can be seen from the above stack trace, the stack is only about 12 levels deep as expected by the "short-cutting" optimization which makes this algorithm work without memoization, which seems to indicate that some huge allocations are being made on each level of recursion.

[Delta456]

The issue still persists with the latest version of V.