Is there a systematic upper bound to evaluation in Frege?

Question

Just out of curiosity, I tried this code in Frege:

println (mydrop 30000000 [1..30000001])

It goes without saying that a sequence of 30 million entries is kind of silly and I would have been ok with an OOME. I wanted to see whether lazy evaluation makes a difference here. The result was though that all my 8 cores were exhausted at 100% and stayed there until I hard-killed the process.

Have I hit a systematic upper bound?

---

I should have mentioned that I used the mydrop from the real-world Haskell exercise:

mydrop n xs = if n <= 0 || null xs
              then xs
              else mydrop (n-1) (tail xs)

Answer 1

There is no upper limit I am aware of. A short test in the REPL (try.frege-lang.org) shows that I can go up to

drop 16_000_000 [1..16_000_000]

which finishes after a few seconds only. Since this program is O(n) I'd estimate a maximum execution time of maybe 30 seconds for 30 million, but with 32_000_000 I get "Service unavailable" after some seconds, which usually hints at exhaustion of some limit of the free web service.

Also, the memory usage of the program above should be constant, irrespective of the number. If it didn't I would consider it a bug.

--- EDIT ---

Tried it on a 2 core 2.9GHz office PC: works like a charm and takes 5.7s. 64 million take 10.5s

Answer 2

The issue has now being tracked down, but it turns out that it can't be avoided in all cases, due to lack of proper tail calls in the JVM. See here for an explanation: https://github.com/Frege/frege/issues/65

Interestingly, the following "equivalent" groovy program (my first one!) exhibits an interesting behaviour:

println (new IntRange(0,30_000_000).drop(29).take(3))

this takes substantial longer than

println (new IntRange(0,30_000_000).drop(29_999_990).take(3))

The Frege program always needs n+m steps, where n is the number of dropped items and m the number of items taken, so the first one is almost immediate, but the second one takes 2 to 3s. The grrovy program OTOH seems to actually realize the list that remains after drop, before continuing with take. Thus the first version is slower.