Stack overflow during grading occurs sooner in the browser than in batch mode

[fpottier]

The title says it all: I have written a grader which works in batch mode (when executed via learn-ocaml grade) but fails in the browser (Firefox) with a Stack_overflow exception. This happens when grading the solution of my exercise nondet_monad_cont, which currently is sitting in a pull request in learn-ocaml-corpus. The second half of Question 4 (laziness) is where the grader fails.

Is it possible that the compilation to JavaScript does not do tail call optimization?

Is it possible to somehow ensure that the stack limit is the same under both environments (batch mode and in-browser mode)?

Is it possible for each exercise to indicate what stack size it needs?

[ejgallego]

Is it possible that the compilation to JavaScript does not do tail call optimization?

Indeed tail call is limited in js_of_ocaml; see the docs.

We use a workaround for Coq https://github.com/ejgallego/jscoq/blob/v8.10/etc/patches/trampoline.patch

[fpottier]

Thanks Emilio.

Interesting workaround, which I don't fully understand: doesn't the fact that trampoline itself is tail-recursive still create a problem? -- Oh, I see, this pattern is recognized by js_of_ocaml.

Besides, I suppose that this workaound is applicable to code that is already written in monadic style, but this does not really solve the problem with "normal" code.

[ejgallego]

Oh, I see, this pattern is recognized by js_of_ocaml.

Indeed, what the workaround does is to help JSOO realize about the tail-rec; for teaching this is a problem indeed.

[fpottier]

Does anyone have a suggestion to fix this problem? It's now exposed on the public site.

[erikmd]

Hi @fpottier, that's an annoying problem indeed.

FWIW, I recently identified another Stack_overflow problem after I merged learn-ocaml master in the learn-ocaml-editor branch (deployed at https://pfitaxel.github.io/pfitaxel-demo/):

• the source of the issue was painful to identify (as there is no backtrace or so) but I pushed a workaround in https://github.com/pfitaxel/learn-ocaml/commit/d337cccf2b276ba51c37784d4d9f69de7f0321bd;
• still, this won't be helpful for you as it is orthogonal to your issue: to sum up, mine was directly trigerred by a call to the function descrs_from_string on a large string…
• I didn't bisect manually but the first commit that certainly introduced that issue (which didn't occur with the first versions of learn-ocaml/learn-ocaml-editor) is https://github.com/ocaml-sf/learn-ocaml/commit/163b0d12ce6032ceddb40f80a898903fb9d31f49
• And unfortunately I don't have a good solution to fix it for the time being, the commit d337ccc being just a raw workaround (replacing the large string with an error message) :-/

Other ideas/suggestions are welcome as well...

[hferee]

Hi everyone,

I recently stumbled upon some stack overflows too on the platform, which surprised me a lot since the solutions were not recursive at all! I'm not certain that my issues have the same cause as @fpottier, but I'll share my (raw) findings anyway.

First, the size of the stack depends on the browser. For example, the current version of Firefox has a stack size of about 26k, while Chrome only has 13k. This looks plenty for non-recursive exercises, but let's see some benchmarks.

Example : a trivial test of the identity function, with the unit -> unit type, where no tests are actually performed: test_function_1_against_solution [%ty : unit -> unit] ~gen:0 "test" []

Firefox gives a stack overflow with less than 50 of those tests, resp. 30 for Chrome.

At first, this suggests that one call of the test function is compiled into something of the order of 500 (~ 26k / 50) actual javascript function calls. Let's see what happens with functions with bigger arguments.

The same example over int triplets instead of unit: test_function_1_against_solution [%ty : (int * int * int) -> (int * int * int)] ~gen:0 "test" []

Firefox gives a stack overflow with less than 18 of those tests, resp. 8 for Chrome, which shows that this issue can appear with quite small exercises.

This is about three times smaller than for the first example. This suggests that the number of javascript function calls is not to blame, but rather the size that arguments use on the stack. For example, Chrome cannot handle a single test for a function over 40-tuples of int (yes, that would be a silly function).

For me, this raises two questions:

• Is it true that one (OCaml) int argument is equivalent to several hundread javascript stack calls ? And if so, what can we do about it ?
• These tests would sort of make sense if we were testing the functions at least once, but here we have an empty list of test inputs and ~gen:0. Is this due to some ppx magic?