CODEWITHSUNDEEP
haskellrecursionoptimization
Alex Aparin
Alex Aparin

Reputation: 4522

Can haskell optimise not tail recursive function?

I have following program:

my_sum 0 = 54321
my_sum i = i + (my_sum (i - 1))

main = do
    print $ my_sum 12345

I want to find out whether generated my_sum function is recursive. In other words, will haskell transform this one to not recursive kind.

I am tried to see native c-- code (asm almost the same). But it is too difficult for me. It is code of my_sum:

my_sum_s24N_entry() //  [R1]
     { info_tbl: [(c25x,
                   label: block_c25x_info
                   rep:StackRep [False, False]),
                  (c267,
                   label: my_sum_s24N_info
                   rep:HeapRep 1 nonptrs { Fun {arity: 1 fun_type: ArgSpec 5} })]
       stack_info: arg_space: 8 updfr_space: Just 4
     }
 {offset
   c267:
       _s24N::P32 = R1;
       _s24O::P32 = P32[Sp];
       if ((Sp + 8) - 32 < SpLim) goto c268; else goto c269;
   c269:
       Hp = Hp + 8;
       if (Hp > HpLim) goto c26b; else goto c26a;
   c26b:
       HpAlloc = 8;
       goto c268;
   c268:
       R1 = _s24N::P32;
       call (stg_gc_fun)(R1) args: 8, res: 0, upd: 4;
   c26a:
       I32[Hp - 4] = sat_s24V_info;
       _c25n::P32 = Hp - 4;
       I32[Sp - 8] = c25x;
       P32[Sp - 24] = GHC.Integer.Type.$fEqInteger_closure;
       I32[Sp - 20] = stg_ap_pp_info;
       P32[Sp - 16] = _s24O::P32;
       P32[Sp - 12] = _c25n::P32;
       P32[Sp - 4] = _s24N::P32;
       Sp = Sp - 24;
       call GHC.Classes.==_info() returns to c25x, args: 20, res: 4, upd: 4;
   c25x:
       _s24N::P32 = P32[Sp + 4];
       _s24O::P32 = P32[Sp + 8];
       _s24W::P32 = R1;
       _c266::P32 = _s24W::P32 & 3;
       if (_c266::P32 != 1) goto c265; else goto c264;
   c265:
       Hp = Hp + 8;
       if (Hp > HpLim) goto c26j; else goto c26i;
   c26j:
       HpAlloc = 8;
       R1 = _s24W::P32;
       call stg_gc_unpt_r1(R1) returns to c25x, args: 4, res: 4, upd: 4;
   c26i:
       I32[Hp - 4] = GHC.Integer.Type.S#_con_info;
       I32[Hp] = 54321;
       _c26k::P32 = Hp - 3;
       P32[Sp] = GHC.Num.$fNumInteger_closure;
       I32[Sp + 4] = stg_ap_p_info;
       P32[Sp + 8] = _c26k::P32;
       call GHC.Num.fromInteger_info() args: 16, res: 0, upd: 4;
   c264:
       Hp = Hp + 16;
       if (Hp > HpLim) goto c26e; else goto c26d;
   c26e:
       HpAlloc = 16;
       R1 = _s24W::P32;
       call stg_gc_unpt_r1(R1) returns to c25x, args: 4, res: 4, upd: 4;
   c26d:
       I32[Hp - 12] = sat_s250_info;
       P32[Hp - 4] = _s24N::P32;
       P32[Hp] = _s24O::P32;
       _c25B::P32 = Hp - 12;
       P32[Sp - 4] = GHC.Num.$fNumInteger_closure;
       I32[Sp] = stg_ap_pp_info;
       P32[Sp + 4] = _s24O::P32;
       P32[Sp + 8] = _c25B::P32;
       Sp = Sp - 4;
       call GHC.Num.+_info() args: 20, res: 0, upd: 4;
 }
 }

Upvotes: 0

Views: 166

Answers (1)

user2407038
user2407038

Reputation: 14598

The answer is no, GHC will not optimize this to a tail recursive function. As a commenter suggests, to see this, you should look at the GHC core^:

Rec {
my_sum :: Integer -> Integer
my_sum =
  \ (ds :: Integer) ->
    case eqInteger# ds my_sum'2 of wild { __DEFAULT ->
    case tagToEnum# wild of _ {
      False -> plusInteger ds (my_sum (minusInteger ds lvl));
      True -> my_sum'1
    }
    }
end Rec }

This function is clearly not tail-recursive - the outermost call is to plusInteger. The GHC core is the code after all optimizations are performed - this code is what is actually translated to machine code. So you know if your function is not tail-recursive in core, it really isn't tail recursive. It is also essentially just Haskell, aside from some funny names, so reading it should not be a problem.

If you want a tail recursive function, just use foldl': 

import Data.List (foldl')

my_sum' :: Integer -> Integer 
my_sum' i0 = foldl' (+) 54321 [0..i0]

Which gives the following core: 

my_sum' :: Integer -> Integer
my_sum' =
  \ (i0 :: Integer) ->
    letrec {
      go :: Integer -> Integer -> Integer
      go =
        \ (x :: Integer) (eta :: Integer) ->
          case gtInteger# x i0 of wild { __DEFAULT ->
          case tagToEnum# wild of _ {
            False -> go (plusInteger x $fEnumInteger1) (plusInteger eta x);
            True -> eta
          }
          }; } in
    go my_sum'2 my_sum'1

Here my_sum'2, my_sum'1 and lvl are the constants in the program: 

my_sum'2 :: Integer
my_sum'2 = 0
my_sum'1 :: Integer
my_sum'1 = 54321
lvl :: Integer
lvl = 1

^ Generated with the options -ddump-simpl -dsuppress-idinfo -dsuppress-coercions -dsuppress-type-applications -dsuppress-uniques -dsuppress-module-prefixes --make

Upvotes: 3

Related Questions