Don't translate all recursive definitions to LetRec

[zhiyuanshi]

In Desugar.hs

[bixuanzju]

LetRec is a generalisation of Fix, so in principle, translating all recursive definitions to LetRec is OK. I have finished a variation of LetRec to Java translation, which avoids the nasty nested inner classes problem. Patches are on the way.

[bixuanzju]

Say we have the following program:

let rec
even (n : Int) : Bool = if n == 0 then True  else odd  (n - 1) and
odd  (n : Int) : Bool = if n == 0 then False else even (n - 1)
;
let id (x : Int) = x;
even (id 42)

The old translation of LetRec would create a class (L1) that wraps the two Closure classes Even and Odd and later expression (Id class and the final expression). The consequence is that, if later expressions contain letrec, then we end up in multiple nested inner classes:

class L1 {
  Object temp;
  Closure x3;
  Closure x4;
  {
  class Even {...}
  x3 = ...;
  class Odd {...}
  x4 = ...;
  class Id {...}
  <some application statements using x3 and x4>
  temp = ...;
  }
}
L1 l1 = new L1();
return l1.temp;

The new translation basically lift later expression out of the wrapping class like this

class L1 {
  Closure x3;
  Closure x4;
  {
  class Even {...}
  x3 = ...;
  class Odd {...}
  x4 = ...;
  }
}
L1 l1 = new L1();
Closure x3 = l1.x3;
Closure x4 = l1.x4;
class Id {...}
<some application statements using x3 and x4>

Now if later expressions contain letrec, they are in the same level.

This change also removes the need of having a standalone Fix construct, since in principle, Fix can be represented by LecRec, and currently this is what we did in the frontend: we translate every recursive definition to LetRec (some time ago, in Desugar.hs, we transformed a self-recursive definition back to Fix). Now if we have a program like

let rec fact (n:Int) : Int = if n == 0 then 1 else n * fact (n-1);

let id (x : Int) = x;

fact (id 10)

It translates to

class L1 {
  Closure x2;
  {
  Closure Fact {...}
  x2 = ...;
  }
}
L1 x1 = new L1();
Closure x2 = x1.x2;
class Id {...}
<some application statements using x2>

Id class is not inside L1

[brunocdsoliveira]

One reason why we still had standalone fixpoints was performance. Translating a single-recursive function as a LetRec was not as efficient as translating a fixpoint.

[bixuanzju]

Are you referring to the performance of compiling a program or running the generated Jaca code?

[brunocdsoliveira]

Running the generated code.

[bixuanzju]

yes, the only performance penalty is coming from having one more object creation, illustrated as below:

• translated as LetRec

class L1 {
  Closure x2;
  {
  Closure Fact {...}
  x2 = ...;
  }
}
L1 x1 = new L1();  -- can be eliminated if fixpoint
Closure x2 = x1.x2;
<statements using x2>

• translated as Fix

 Closure Fact {...}
 Closure x2 = ...;
<statements using x2>

Anyway, i will leave Fix around.