---
title: "Tail Call Optimization"
output: arl::arl_html_vignette
pkgdown:
  as_is: true
vignette: >
  %\VignetteIndexEntry{Tail Call Optimization}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include = FALSE}
knitr::opts_chunk$set(collapse = TRUE, comment = "#>")
arl::register_knitr_engine()
```

R does not optimize tail calls. A recursive function that works fine in
Scheme or Clojure will overflow R's call stack after a few thousand
iterations. Arl's compiler fixes this for the most common case:
**self-recursion**.

## How It Works

When the compiler sees `(define name (lambda ...))` or
`(set! name (lambda ...))` and the lambda body contains calls to `name`
in tail position, it rewrites the entire function as a `while(TRUE)` loop.
Each self-call becomes a set of parameter reassignments followed by `next`,
so no new stack frames are allocated.

Because `letrec` expands into `set!`, this means `letrec`-bound lambdas
that self-recurse are automatically optimized too.

```{arl}
;; The compiler optimizes this automatically
(define factorial
  (lambda (n acc)
    (if (< n 2)
      acc
      (factorial (- n 1) (* acc n)))))

;; No stack overflow (but 100000! is too large
;; to be representable and overflows to Inf)
(factorial 100000 1)
```

```{arl, include=FALSE}
(assert-equal 120 (factorial 5 1))
```

The compiled R code looks roughly like:

```r
function(n, acc) {
  while (TRUE) {
    if (n < 2) {
      return(acc)
    } else {
      .__tco_n <- n - 1
      .__tco_acc <- acc * n
      n <- .__tco_n
      acc <- .__tco_acc
      next
    }
  }
}
```

Temporary variables (`.__tco_n`, `.__tco_acc`) ensure all new argument values
are computed before any parameter is reassigned — just like a
simultaneous `let`.

Unlike in Scheme, more advanced types of tail recursion are **not** optimized:
- **Mutual recursion** (`f` calls `g` in tail position, `g` calls `f`).
- **`apply`-based tail calls** or indirect calls through higher-order functions.
- **Anonymous lambdas** which tail-recurse by use of a fixed-point combinator
  (no name for the compiler to detect self-calls against).

## What Counts as Tail Position

The compiler recognizes self-calls in tail position through these special
forms:

- **`if`** — both the consequent and alternative branches
- **`begin`** — the last expression

This covers many other expressions (`cond`, `let`, `let*`, `letrec`, etc.)
which are implemented as macros in terms of `if` and `begin`.

```{arl}
;; All three self-calls below are in tail position
(define sum-positive
  (lambda (lst acc)
    (if (null? lst)
      acc
      (let ((x (car lst)))
        (if (> x 0)
          (sum-positive (cdr lst) (+ acc x))   ; tail: let -> if -> consequent
          (sum-positive (cdr lst) acc))))))     ; tail: let -> if -> alternative
```

```{arl, include=FALSE}
(assert-equal 6 (sum-positive (list 1 -2 2 -3 3) 0))
```

A call that is **not** in tail position — for example, wrapped in another
function call — will not be optimized:

```{arl, eval=FALSE}
;; NOT tail-recursive: the + wraps the recursive call
(define bad-sum
  (lambda (n)
    (if (< n 1)
      0
      (+ n (bad-sum (- n 1))))))   ; not in tail position
```

```{arl, include=FALSE}
;; Verify the non-tail-recursive version works for small n
(define __bad-sum
  (lambda (n)
    (if (< n 1) 0 (+ n (__bad-sum (- n 1))))))
(assert-equal 15 (__bad-sum 5))
```

## Advanced Features

Self-TCO works with all of Arl's parameter features:

- **Destructuring parameters** — pattern bindings are re-evaluated each
  iteration inside the loop
- **Rest parameters** — `(lambda (x . rest) ...)` works correctly
- **Keyword arguments** — named arguments in the self-call are matched
  to the right parameters

## Disabling TCO for Debugging

Since self-calls become loop iterations, recursive call frames do **not**
appear in stack traces on error. Only the outermost call is visible. To
preserve natural call stacks for debugging, you can disable self-TCO
using the `disable_tco` option.

There are three ways to disable it, in order of precedence:

**Engine initialization parameter** (highest priority):

```r
engine <- arl::Engine$new(disable_tco = TRUE)
```

**R option**:

```r
options(arl.disable_tco = TRUE)
```

**Environment variable** (lowest priority):

```bash
export ARL_DISABLE_TCO=1
```

With TCO disabled, self-recursive functions compile to normal recursive
calls. This means deep recursion will hit R's stack limit, but error
stack traces will show the full chain of recursive calls, making it
easier to identify where things went wrong.

## loop/recur

For mutual recursion or explicit looping patterns where self-TCO is not
applicable, the `looping` module provides Clojure-style `loop`/`recur`.
Since `looping` is not a prelude module, you need to import it explicitly:

```{arl}
(import looping :refer :all)

(define factorial
  (lambda (n)
    (loop ((i n) (acc 1))
      (if (< i 2)
        acc
        (recur (- i 1) (* acc i))))))
```

```{arl, include=FALSE}
(assert-equal 120 (factorial 5))
```

`loop` establishes named bindings and `recur` jumps back to the top of
the loop with new values. This is implemented as a macro that expands to
a `while` loop, so it has the same performance characteristics as
self-TCO.

## Summary

| Feature | Self-TCO | loop/recur |
|---------|----------|------------|
| Activation | Automatic | Explicit `(import looping)` required |
| Pattern | `(define name (lambda ...))` or `(set! name (lambda ...))` | `(loop ((var init) ...) body)` |
| Scope | Self-recursion only | Any loop pattern |
| Stack growth | None | None |
| Stack traces | Outermost frame only | Outermost frame only |