🎓 A1Learner
🔍
0 of 45 lessons completed

Trampolines

Trampolines are loops that run small steps one at a time. Each step returns either a finished value or the next step.

A TailRec chain returns a small sum

The function adds 10 down to 1. Each call returns the next step until zero is reached.

import scala.util.control.TailCalls._

def sumTo(n: Long, acc: Long): TailRec[Long] =
  if n <= 0 then done(acc)
  else tailcall(sumTo(n - 1, acc + n))

@main def main(): Unit =
  println(sumTo(10, 0).result)

A deep chain finishes without overflow

The same shape of function runs for 100000. The trampoline loop handles every step in turn.

import scala.util.control.TailCalls._

def sumTo(n: Long, acc: Long): TailRec[Long] =
  if n <= 0 then done(acc)
  else tailcall(sumTo(n - 1, acc + n))

@main def main(): Unit =
  println(sumTo(100000, 0).result)

A deep countdown still finishes

A countdown needs many steps and no large sum. Two hundred thousand steps finish through the same loop.

import scala.util.control.TailCalls._

def steps(n: Long, acc: Long): TailRec[Long] =
  if n <= 0 then done(acc)
  else tailcall(steps(n - 1, acc + 1))

@main def main(): Unit =
  println(steps(200000, 0).result)

Example

import scala.util.control.TailCalls._

def sumTo(n: Long, acc: Long): TailRec[Long] =
  if n <= 0 then done(acc)
  else tailcall(sumTo(n - 1, acc + n))

@main def main(): Unit =
  println(sumTo(50000, 0).result)

Key points

  • Recursion: a function that calls itself to solve a smaller part of a problem.
  • Stack: the memory that holds calls that have not finished yet.
  • Overflow: a failure caused by too many unfinished calls on the stack.
  • TailRec: a value that holds either a finished result or the next step.
  • Use tailcall to return the next step without growing the stack.
  • Use done to wrap a finished result.
  • Use result to run the whole chain and get the final value.

In this example, sumTo adds 50000 down to 1. Each call returns the next step through tailcall. The call to result runs the steps and prints the total.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

Exercise

What does sumTo(4, 0).result give when sumTo adds n down to 1?