Scala example source code file (tailcalls.scala)

This example Scala source code file (tailcalls.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Scala tags/keywords

boolean, c, c, class, fancytailcalls, final, int, int, list, o, o, sealed, sealed, subclass

The Scala tailcalls.scala source code

//############################################################################
// Tail Calls
//############################################################################

//############################################################################
// Calibration

class Calibrator {
  def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
}

//############################################################################
// Tail calls in different contexts

class Class {
  def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
}

class SubClass extends Class {
  override def f(n: Int, v: Int): Int = v;
}

sealed class Sealed {
  def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
}

class SubSealed extends Sealed {
  override def f(n: Int, v: Int): Int = v;
}

final class Final {
  def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
}

object Object {
  def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
}

//############################################################################
// Tail calls in nested objects/classes

object O {
  final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
  object O {
    final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
    object O {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    class C {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    val c: C = new C;
  }
  class C {
    final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
    object O {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    class C {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    val c: C = new C;
  }
  val c: C = new C;
}

class C {
  final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
  object O {
    final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
    object O {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    class C {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    val c: C = new C;
  }
  class C {
    final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
    object O {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    class C {
      final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      object O {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      class C {
        final def f(n: Int, v: Int): Int = if (n == 0) v else f(n - 1, v - 1);
      }
      val c: C = new C;
    }
    val c: C = new C;
  }
  val c: C = new C;
}

//############################################################################
// Tail calls with different signatures

class TailCall[S](s: S) {
  def getS: S = s;

  final def f1(n: Int, v: Int): Int =
    if (n == 0) v else f1(n - 1, v - 1);
  final def f2[T](n: Int, v: Int): Int =
    if (n == 0) v else f2[T](n - 1, v - 1);
  final def f3[T](n: Int, v: Int, ls: List[T]): Int =
    if (n == 0) v else f3(n - 1, v - 1, ls);

  final def g1(x: Int, y: Int): Int = {
    def aux(n: Int, v: Int): Int =
      if (n == 0) v else aux(n - 1, v - 1);
    aux(x, y);
  }
  final def g2[T](x: Int, y: Int): Int = {
    def aux[U](n: Int, v: Int): Int =
      if (n == 0) v else aux[U](n - 1, v - 1);
    aux[T](x, y);
  }
  final def g3[T](x: Int, y: Int, zs: List[T]): Int = {
    def aux[U](n: Int, v: Int, ls: List[Pair[T,U]]): Int =
      if (n == 0) v else aux(n - 1, v - 1, ls);
    aux(x, y, Nil);
  }

  final def b1(x: Int): Boolean =
    (x == 1) || b1(x - 1)
  final def b2(x: Int): Boolean =
    (x > 0) && ((x == 1) || b1(x - 1))

  def h1(n: Int, v: Int): Int = hP(n, v);
  private def hP(n: Int, v: Int): Int = if (n == 0) v else hP(n - 1, v - 1);

  // !!! test return in non-tail-call position
  // !!! test non-same-instance calls
  // !!! test non-same-type calls

}

object FancyTailCalls {
  val f1 = new FancyTailCalls
  val f2 = new FancyTailCalls
}

object PolyObject extends App {
  def tramp[A](x: Int): Int = 
    if (x > 0)
      tramp[A](x - 1)
    else 
      0
}


class FancyTailCalls {

  def tcTryLocal(x: Int, v: Int): Int = {
    try {
      def loop(n: Int): Int = {
        if (n == 0) v else loop(n - 1)
      }
      loop(x)
    } finally {}
  }

  import FancyTailCalls._
  final def differentInstance(n: Int, v: Int): Int = {
    if (n == 0) v
    else if ((n % 2) == 0) f1.differentInstance(n - 1, v)
    else f2.differentInstance(n - 1, v)
  }
}

class NonTailCall {
  final def f1(n: Int): Int = try {
    if (n == 0) 0
    else f1(n - 1)
  } finally {
    Console.print(" " + n)
  }

  final def f2(n: Int): Int = synchronized {
    if (n == 0) 0
    else f2(n - 1)
  }
  
}

//############################################################################
// Test code

object Test {
  def check_success(name: String, closure: => Int, expected: Int) {
    print("test " + name)
    try {
      val actual: Int = closure
      if (actual == expected) {
        print(" was successful")
      } else {
        print(" failed: expected "+ expected +", found "+ actual)
      }
    } catch {
      case exception: Throwable => {
        print(" raised exception " + exception)
      }
    }
    println
  }

  def check_success_b(name: String, closure: => Boolean, expected: Boolean) {
    print("test " + name)
    try {
      val actual: Boolean = closure
      if (actual == expected) {
        print(" was successful")
      } else {
        print(" failed: expected "+ expected +", found "+ actual)
      }
    } catch {
      case exception: Throwable => {
        Console.print(" raised exception " + exception);
      }
    }
    println
  }
    
  def check_overflow(name: String, closure: => Int) {
    print("test " + name)
    try {
      val actual: Int = closure;
    } catch {
      case exception: compat.Platform.StackOverflowError =>
        println(" was successful")
      case exception: Throwable => {
        print(" raised exception " + exception)
      }
    }
    println
  }

  def calibrate: Int = {
    val calibrator = new Calibrator();
    var stop = false;
    var n = 1;
    while (!stop) {
      try {
        calibrator.f(n, n);
        if (n >= Math.MAX_INT / 2) error("calibration failure");
        n = 2 * n;
      } catch {
        case exception: compat.Platform.StackOverflowError => stop = true
      }
    }
    4 * n
  }

  def main(args: Array[String]) {
    // compute min and max iteration number
    val min = 16;
    val max = calibrate;

    // test tail calls in different contexts
    val Final     = new Final()
    val Class     = new Class()
    val SubClass  = new SubClass()
    val Sealed    = new Sealed()
    val SubSealed = new SubSealed()
    check_success("Object   .f", Object   .f(max, max), 0)
    check_success("Final    .f", Final    .f(max, max), 0)
    check_success("Class    .f", Class    .f(max, max), 0)
    check_success("SubClass .f", SubClass .f(max, max), max)
    check_success("Sealed   .f", Sealed   .f(max, max), 0)
    check_success("SubSealed.f", SubSealed.f(max, max), max)
    println

    // test tail calls in nested classes/objects
    val c: C = new C
    check_success("O      .f", O      .f(max, max), 0)
    check_success("c      .f", c      .f(max, max), 0)
    check_success("O.O    .f", O.O    .f(max, max), 0)
    check_success("O.c    .f", O.c    .f(max, max), 0)
    check_success("c.O    .f", c.O    .f(max, max), 0)
    check_success("c.c    .f", c.c    .f(max, max), 0)
    check_success("O.O.O  .f", O.O.O  .f(max, max), 0)
    check_success("O.O.c  .f", O.O.c  .f(max, max), 0)
    check_success("O.c.O  .f", O.c.O  .f(max, max), 0)
    check_success("O.c.c  .f", O.c.c  .f(max, max), 0)
    check_success("c.O.O  .f", c.O.O  .f(max, max), 0)
    check_success("c.O.c  .f", c.O.c  .f(max, max), 0)
    check_success("c.c.O  .f", c.c.O  .f(max, max), 0)
    check_success("c.c.c  .f", c.c.c  .f(max, max), 0)
    check_success("O.O.O.O.f", O.O.O.O.f(max, max), 0)
    check_success("O.O.O.c.f", O.O.O.c.f(max, max), 0)
    check_success("O.O.c.O.f", O.O.c.O.f(max, max), 0)
    check_success("O.O.c.c.f", O.O.c.c.f(max, max), 0)
    check_success("O.c.O.O.f", O.c.O.O.f(max, max), 0)
    check_success("O.c.O.c.f", O.c.O.c.f(max, max), 0)
    check_success("O.c.c.O.f", O.c.c.O.f(max, max), 0)
    check_success("O.c.c.c.f", O.c.c.c.f(max, max), 0)
    check_success("c.O.O.O.f", c.O.O.O.f(max, max), 0)
    check_success("c.O.O.c.f", c.O.O.c.f(max, max), 0)
    check_success("c.O.c.O.f", c.O.c.O.f(max, max), 0)
    check_success("c.O.c.c.f", c.O.c.c.f(max, max), 0)
    check_success("c.c.O.O.f", c.c.O.O.f(max, max), 0)
    check_success("c.c.O.c.f", c.c.O.c.f(max, max), 0)
    check_success("c.c.c.O.f", c.c.c.O.f(max, max), 0)
    check_success("c.c.c.c.f", c.c.c.c.f(max, max), 0)
    println

    // test tail calls with different signatures
    val TailCall = new TailCall("S")
    check_success("TailCall.f1", TailCall.f1(max, max     ), 0)
    check_success("TailCall.f2", TailCall.f2(max, max     ), 0)
    check_success("TailCall.f3", TailCall.f3(max, max, Nil), 0)
    check_success("TailCall.g1", TailCall.g1(max, max     ), 0)
    check_success("TailCall.g2", TailCall.g2(max, max     ), 0)
    check_success("TailCall.g3", TailCall.g3(max, max, Nil), 0)
    check_success("TailCall.h1", TailCall.h1(max, max     ), 0)
    println
    
    val NonTailCall = new NonTailCall
    check_success("NonTailCall.f1", NonTailCall.f1(2), 0)
    check_overflow("NonTailCall.f2", NonTailCall.f2(max))

    check_success_b("TailCall.b1", TailCall.b1(max), true)
    check_success_b("TailCall.b2", TailCall.b2(max), true)

    val FancyTailCalls = new FancyTailCalls;
    check_success("FancyTailCalls.tcTryLocal",   FancyTailCalls.tcTryLocal(max, max), max)
    check_success("FancyTailCalls.differentInstance",   FancyTailCalls.differentInstance(max, 42), 42)
    check_success("PolyObject.tramp", PolyObject.tramp[Int](max), 0)
  }

  // testing explicit tailcalls.
  
  import scala.util.control.TailCalls._

  def isEven(xs: List[Int]): TailRec[Boolean] =
    if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

  def isOdd(xs: List[Int]): TailRec[Boolean] =
    if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail)) 

  assert(isEven((1 to 100000).toList).result)
  
}

//############################################################################