Welcome to the new Behind the Schemes series. Behind the Schemes discuss items in Schemer that are not readily visible to  users (i.e. behind the scenes). The inaugural post is about tail calls. Here is the definition of a tail call from wikipedia: 

"In computer science, a tail call is a subroutine call performed as the final action of a procedure."

It's perfectly fine if that didn't make any sense to you because I have a very simple example that should help explain it better, but first a bit of background. Scheme has a special form called begin which evaluates each expression that is passed to it (in left to right order) and returns the result of the last expression that it evaluates. The tail call within  the begin special form is the last expression...simple right? In the below example, (print 2) is the tail call:

(begin (print 1) (print 2))

Tail calls and tail call optimization are important because they allows you to reduce your call stack usage within an application. Put simply, the call stack within an application is similar to having a stack of plates on a table. To illustrate this, we'll use the begin example above:

When begin  is called, a single plate is added to an empty table. Next, (print 1) is called so a plate is added on top of the plate that begin added. When (print 1) finishes executing, its plate will be removed from the stack on the table and (print 2) will then be added on top of the plate that begin added. When (print 2) finishes executing, its plate will be removed from the stack and since there is nothing next to execute, the begin plate will be removed as well;  leaving the table empty.

With tail call optimization, we would recognize that (print 2) is the tail call, and so when (print 1) finishes executing, its plate will be removed from the stack on the table and the plate that was previously being used for begin would be re-purposed to be used for (print 2).

At first glance, tail call optimization may seem trivial and unnecessary, but applications have a specific amount of memory that is allocated for their call stack and when they exceed that memory (often referred to as a stack overflow), an exception is thrown and the application is forced to terminate. Many languages (including Scheme) allow for procedures to be recursive; that is, a procedure will continually call itself with different parameters until a base condition is met (at which point it will stop calling itself). Using recursion has the potential to significantly grow the call stack and ultimately cause a stack overflow; however, if the procedure is tail-recursive (i.e. the call to itself is the tail call), then each recursive call will use the "plate" that was used by the previous recursive call (avoiding the stack overflow).

Scheme implementations are required to perform tail call optimization because recursion is  one of the main ways to accomplish iteration (i.e. the process of evaluating a set of expressions a certain number of times). Schemer implements tail calls for the following special forms:

if, cond, logical or, logical and, begin, let, let*, letrec, let (named), do (loop), lambda.

That concludes the first Behind the Schemes devblog. I hope you found it interesting and learned something new. Till next time.