Efficient Function Nesting
2025-10-23
The early language called “Forth” used an intriguing optimization to call two kinds of functions
built-ins
recipes.
Built-ins are parameterless functions. Recipes are compact arrays of pointers to other parameterless recipes and/or to other parameterless built-ins.
In both cases, parameters flow in and out via an explicit common data stack instead of on the call stack, as is done with many popular programming languages.
Both, built-ins and recipes are called “words” in Forth. Forth contains a flag, called the “codeword”, that differentiates between built-ins and compact recipes.
A clever optimization is used to avoid branching code based on codewords.
Codewords are used as indirect pointers to routines. For builtins, codewords point to a first-class function. For recipes, codewords point to a shared function that iterates through an array containing first-class functions and/or references to other recipes.
Instead of testing the codeword flag, Forth simply invokes the routine pointed to by codewords. Testing a flag is expensive because it involves branching code. Branching code is essentially a gotcha - hardware must use complicated branch prediction algorithms and might perform pipeline drains. The codeword optimization used by Forth replaces all of this complication by a simple indirect jump (or call, if that’s all you’ve got).
In both cases, codewords point to routines (”functions”). Codewords are set up to point to appropriate routines.
In the case of builtins, codewords point to function code.
In the case of recipe words, codewords point to a single function that sequentially calls each function in the array associated the word. The recipe iterator is a very short function because it doesn’t need to worry about parameter passing. In Forth, all parameters use a common data stack.
In assembler, the recipe iterator consists of only one or a few instructions, depending on available addressing modes. In higher level languages, a recipe array can be implemented as an array of pointers to anonymous functions and the recipe iterator becomes a simple for loop.
Aside: this kind of iteration is one of the techniques used in Container parts in the implementation of Parts Based Programming (PBP (0D)).
More
Further discussion can be had on the Forth-ish discord or on the programming simplicity discord.
See Also
Email: ptcomputingsimplicity@gmail.com
Substack: paultarvydas.substack.com
Videos: https://www.youtube.com/@programmingsimplicity2980
Discord: https://discord.gg/65YZUh6Jpq
Leanpub: [WIP] https://leanpub.com/u/paul-tarvydas
Twitter: @paul_tarvydas
Bluesky: @paultarvydas.bsky.social
Mastodon: @paultarvydas
(earlier) Blog: guitarvydas.github.io
References: https://guitarvydas.github.io/2024/01/06/References.html