THE ACTIVATION RECORD a function call is a frame; a tail call reuses it
Every function call gets an activation record (a stack frame): a fixed block holding the return address, the caller’s saved frame pointer, saved registers, the locals and the outgoing arguments — each at a known offset from the frame pointer, so a local is just [fp + k]. A normal call pushes a new frame; a tail call, having nothing left to do, can reuse the current one — the exact reuse tail-call optimisation (dart 155) needs.
THE TECHNIQUE offsets from fp; reuse on tail calls
Locals sit at fixed offsets above the saved frame pointer and return address. A normal call pushes a fresh frame at fp + frame_size; a tail call reuses the current fp and never grows the stack. Toggle the call kind and compute the frame pointer: live demo
HISTORY & CREDIT Dijkstra 1960: recursion + display (the stack is older)
“Local variables live at fixed memory addresses.” — no, not for a re-entrant or recursive function: each call has its own frame on the stack, and a local is addressed relative to the frame pointer, not absolutely — which is exactly what lets a function call itself. cited
1960 · Edsger Dijkstra — “Recursive Programming” (Numer. Math. 2, 312–318): applies the run-time stack to activation records for recursion and introduces the display for nested-scope access. The stack itself is older — Turing’s 1945 “bury / unbury”, Samelson & Bauer’s Kellerprinzip (1955–57); Dijkstra’s advance is recursion + the display. 1964 · Randell & Russell — the ALGOL 60 implementation that realises the stack/display in a real compiler. ongoing · the calling convention / ABI fixes the exact layout (who saves which register, arg order) — the frame’s contract between caller and callee.
The frame pointer is the pivot: locals above it, the saved fp and return address below, and the caller’s frame one link further down — a linked list of frames that is the call stack. A tail call overwrites its own link instead of adding one. Dijkstra, 1960
RECOMMEND FOR I-13 offsets computed; the tail-call reuse
The frame layout — local offsets, and a tail call reusing the frame pointer — runs on the canonical compiler:
$ i13 run frame.i13 # local i at fp+2+i; tail call reuses fp, normal call pushes
loc0 = 1002 loc2 = 1004 -- locals at fixed offsets above fp=1000
normal_call_fp = 1005 -- a normal call pushes a new frame (fp + size)
tailcall_fp = 1000 -- a TAIL call REUSES the frame: same fp, no growth
Recommend: the activation record is LIT and the missing piece behind dart 155 — the canonical compiler computes locals at fixed offsets above fp (loc0=1002, loc2=1004) and, crucially, that a tail call reuses fp=1000 where a normal call would push to 1005. That reuse is tail-call optimisation: I-13’s measured 4096-frame wall (dart 155) is a wall of activation records, and eliminating a tail call means overwriting the current record instead of stacking a new one. A real I-13 back-end would lay locals at frame offsets and add exactly this reuse to make accumulator recursion run flat. Closes the back-end (batch 26) by naming the object every call and every optimisation acts on.