fuzion
fuzion copied to clipboard
AoC Issue: `list.fold` needs tail recursion optimization in JVM backend
This small test
fold_test is
n := (0..100000).fold i32.type.sum
say n
results in a stack overflow
> $FUZION/bin/fz fold_test.fz 2>&1 | head -n 20
error 1: java.lang.StackOverflowError
at fzC_2lteq_i32.fzRoutine(Unknown Source)
at fzC_2infix_gt_i32.fzRoutine(Unknown Source)
at fzC_1i32__1overflow_on_add.fzRoutine(Unknown Source)
at fzC_1i32__1infix_plus.fzPrecondition(Unknown Source)
at fzC_1i32__1infix_plus.fzPreconditionAndRoutine(Unknown Source)
at fzC_i32_INTERN_type_i32__sum__2infix__U2219_.fzRoutine(Unknown Source)
at fzC_i32_INTERN_type_i32__sum__2op.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
at fzC_list_i32__2fold.fzRoutine(Unknown Source)
The problem is that the recursive call in fold is not recognized as a tail recursion, probably because the result is first assigned to an expression result field before that is copied to the feature results field that is returned.