fuzion icon indicating copy to clipboard operation
fuzion copied to clipboard

AoC Issue: `list.fold` needs tail recursion optimization in JVM backend

Open fridis opened this issue 2 years ago • 0 comments

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.

fridis avatar Dec 07 '23 16:12 fridis