A Tail of TwoTails

Mutual Tail Recursion?

General Recursion

object MaxNode{ 
  def find(tree: Tree): Int = tree match{
    case Leaf(v)           => v
    case Node(left, right) => Math.max(find(left), find(right))
  }
}
						

Tail Recursion

import scala.annotation.tailrec

final class Contains[A](value: A){
  @tailrec def contains(rem: List[A]): Boolean = rem match{
    case Nil          => false
    case `value` :: t => true
    case _ :: t       => contains(t)
  }
}
						

Mutual Tail Recursion

final class PingPong(value: Int){
  def ping(x: Int): Int = if(x < value) x else pong(x - 1)
  def pong(x: Int): Int = if(x < value) x else ping(x - 1)
}
						

First Act Recap

Start Here

final class Foo{
  def methodA(x: Int): Int = //code, depends on methodB...
  def methodB(x: Int): Int = //code, depends on methodA...
  //more...
}
						

End Here

import twotails.mutualrec

final class Foo{
  @mutualrec def methodA(x: Int): Int = //code, depends on methodB...
  @mutualrec def methodB(x: Int): Int = //code, depends on methodA...
  //more...
}
						

First Scheme

final class Foo{
  @tailrec private def mutual_fn$0(indx: Int, x: Int): Int = indx match{
    case 0 => //code for methodA...
    case 1 => //code for methodB...
  }
  def methodA(x: Int): Int = mutual_fn$0(0, x)
  def methodB(x: Int): Int = mutual_fn$0(1, x)
  //more...
}
						

Fn Body Transformation

  def methodA[X](x: X): X = if(pred(x)) f(x) else methodB(x)
						

Substitutions Required

X(methodA)

X(mutual_fn$0)

x(methodA)

x(mutual_fn$0)

methodB(...) 

mutual_fn$0(1, ...)  

Success!

version 0.3.1

But...

final class BlowUpTooLarge{
  @mutualrec def one(a1: Any, a2: Any, a3: Any) = (a1, a2, a3) match{
    case (_, _, List(Option(1))) => //code
    //lots more code
  }

  //lots more large but not too large methods...
}
						

there's a problem

[error] Could not write class example/BlowUpTooLarge because it exceeds 
        JVM code size limits. Method mutual_fn$0's code too large!
						

The Second Act

Start Here

final class Foo{
  def methodA(x: Int): Int = //code, depends on methodB...
  def methodB(x: Int): Int = //code, depends on methodA...
  //more...
}
						

End Here

import twotails.mutualrec

final class Foo{
  @mutualrec def methodA(x: Int): Int = //code, depends on methodB...
  @mutualrec def methodB(x: Int): Int = //code, depends on methodA...
  //more...
}
						

Same Shape, sorta

final class Foo{
  private def mutual_fn$0(indx: Int, x: Int): Int = //but...

  def methodA(x: Int): Int = mutual_fn$0(0, x)
  def methodB(x: Int): Int = mutual_fn$0(1, x)
  //more...
}
						

More Complicated

  private def mutual_fn$0(indx: Int, x: Int): Int = {
    var indx$: Int = indx
    var x$: Int = x
    var cont$ = true
    var result$: Int = 0
    def methodA$(): Unit = //code for methodA
    def methodB$(): Unit = //code for methodB
    while(cont$){
      indx$ match{
        case 0 => methodA$()
        case 1 => methodB$()
      }
    }
    result$
  }
						

Fn Body Transformation

  def methodA[X](x: X): X = if(pred(x)) f(x) else methodB(x)
						

Substitutions Required

X(methodA)

X(mutual_fn$0)

x(methodA)

x$(mutual_fn$0)

methodB(y) 

indx$ = 1
x$ = y

f(x)

result$ = f(x$)
cont$ = false    

Happy

Recurse Like Me

Include

libraryDependencies ++= Seq(
  compilerPlugin("com.github.wheaties" %% "twotails" % "0.3.1" cross CrossVersion.full),
  "com.github.wheaties" %% "twotails-annotations" % "0.3.1" cross CrossVersion.full
)
						

or

libraryDependencies ++= Seq(
  compilerPlugin("com.github.wheaties" %% "twotails" % "0.4.0-SNAPSHOT" cross CrossVersion.full),
  "com.github.wheaties" %% "twotails-annotations" % "0.4.0-SNAPSHOT" cross CrossVersion.full
)
						

Plugin Options

scalacOptions += "-Ptwotails:size" //equivalent to no options
						

or

scalacOptions += "-Ptwotails:memory" //optimize for method allocations
						

Bug Reports

www.github.com/Wheaties/TwoTails

Thanks

@OweinReese