<p><a href="https://langdev.stackexchange.com/q/2664/89">Another question</a> refers to the terms &quot;interior iteration&quot; and &quot;exterior iteration&quot;, and the comments under an answer suggest some disagreement or confusion about the meanings of these terms. The terms &quot;internal iteration&quot; and &quot;external iteration&quot; are also used there, though it's not clear if they are (respectively) synonyms.</p>
<p>What do these terms mean? And do they together describe all iteration, or are there other kinds than these two?</p>

<iterators><terminology>
What are "interior iteration" and "exterior iteration"?
CC BY-SA 4.0
2023-08-06T15:28:39.707Z
The best explanation I know of is Bob Nystrom's https://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/
Eldritch Conundrum
<p>&quot;Interior&quot; and &quot;exterior&quot; iteration seem to be simply a local shibboleth of the Rust community referring to what are usually called &quot;internal&quot; and &quot;external&quot; iteration. This may stem from an overloaded use of &quot;internal&quot; or &quot;external&quot; with another meaning that led these to be given a near-synonym, or a mistake at some point that's been propagated onwards. It's also possible it was for deliberate distancing from the object-oriented usage of the common terms, but I didn't find any evidence of that. The linked question uses the more standard terms everywhere except the direct quote.</p>
<p>Search results for either term in this meaning appear all to be connected to Rust on Google, Bing, or DuckDuckGo, and almost all other uses of &quot;interior iteration&quot; are discussing periods of nested loops; people also often use &quot;internal&quot; and &quot;external&quot; in reference to Rust. These terms do not have general currency and are only used as synonyms to the usual terms, and principally within that one language community; &quot;exterior&quot; has very little use at all.</p>
<hr />
<p><strong>Internal iterators</strong>, as in Smalltalk or Ruby, are higher-order functions provided on iterable values that accept another function or some sort of runnable value, and evaluate that function for each contained or produced value in the iterable using the privileged internal access the aggregate value has to itself. It's a <strong>push-based model where control rests with the iterable</strong>. This is what <a href="https://graydon2.dreamwidth.org/307291.html" rel="noreferrer">the Graydon Hoare post</a> quoted in that question was referring to as &quot;interior&quot;; Rust's old iteration model used a similar form to Ruby.</p>
<p><strong>External iterators</strong>, as in Java, modern Rust and the GoF <em>Design Patterns</em> book, <strong>reify the iteration state</strong> into a value which provides operations to advance the iteration and to return its current value. The iterator value often has privileged access to the internal state of the aggregate, but not necessarily, and code that uses it will invoke those operations repeatedly to access each item in the iterable. These generally provide further flexibility to do things like interleave iterations of multiple aggregates, and it's simple to create an internal-like iteration operation on top of them; they also tend to have worse cache locality and allocation costs, but these prices are often found worthwhile.</p>
<p>In the 2012-ish Rust model, internal iteration was supported at the language level using non-first-class coroutines with yielding and no reentrancy. It's <em>conceivable</em> to decide to refer to this specific approach as &quot;interior&quot; as a contrast with object-oriented internal iterators using first-class function objects, but it's fundamentally parallel to Ruby's internal iteration, and it doesn't appear that most contemporary mentions of &quot;interior iteration&quot; do refer to that specific model. The <a href="https://doc.rust-lang.org/std/iter/trait.Iterator.html" rel="noreferrer">modern &quot;exterior&quot; iterators</a> are exactly standard external iterators, however, and the <a href="https://doc.rust-lang.org/std/iter/index.html" rel="noreferrer">headline documentation refers to them as such</a>.</p>
<p>Some history of the process to that point is set out in <a href="https://mastodon.social/@graydon@types.pl/109995318212060698" rel="noreferrer">this social media post by Graydon Hoare</a>, where an intermediate stage of exactly an OO-style internal approach also appears; it's possible that the &quot;interior&quot; distinction arose there, but &quot;exterior&quot; does not have similar support or any use from other sources.</p>
<hr />
<p>Some languages &amp; their libraries provide one or the other of these iteration models, and some provide both. There are trade-offs that favour each of them in both design and implementation. For example, JavaScript includes both a <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach" rel="noreferrer">forEach method</a> (internal iteration) and an <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols#the_iterable_protocol" rel="noreferrer">iterator protocol</a> (external iteration); the latter is what is wrapped up by the built-in <code>for ... of</code> foreach syntax.</p>
<p>Ruby is able to lift its internal iterators into external iterators through coroutines that evaluate the internal iterator until a value is yielded (blocking until it does), and then return it to the caller through an external iteration protocol; when the iterator is asked for the next value, it does the same thing again. This use of coroutines isn't directly related to the use given in the Hoare post, which was about not-quite-first-class resumable code blocks used for the loop itself. In principle, any language could allow this sort of lifting, but it is quite rare in practice.</p>
<hr />
<p>There are many kinds of iteration more generally, through loops, recursion, and jumps. These named &quot;iterator&quot; types are for iteration over notional collections of values, and don't encompass all of those forms — a <code>while</code> loop is not generally either of these, and a cyclic <code>goto</code> couldn't be represented in either of these models at all. Both &quot;internal iterator&quot; and &quot;external iterator&quot; are terms most commonly, though not exclusively, found in object-oriented language communities, especially those influenced by the <em>Design Patterns: Elements of Reusable Object-Oriented Software</em> book that uses the name &quot;Iterator&quot; for one of its patterns that describes an external iterator.</p>

CC BY-SA 4.0
2023-08-07T08:37:40.137Z
2023-08-07T08:47:26.490Z
2023-08-07T08:47:26.490Z
Michael Homer
CC BY-SA 4.0
2023-08-07T11:26:01.390Z
Am I correct that `yield` keyword in python and some other languages effectively provide both the advantages of internal and external iterators while avoiding most of the downsides?
mousetail 'he-him'
CC BY-SA 4.0
2023-08-07T18:27:24.517Z
`yield` mitigates the downsides of external iteration by automating the reification of the iteration state. Similarly, coroutines mitigate the downsides of internal iteration. I suppose this is where I post the link to Bob Nystrom's second post, that mentions both yield and coroutines: https://journal.stuffwithstuff.com/2013/02/24/iteration-inside-and-out-part-2/
Eldritch Conundrum
CC BY-SA 4.0
2023-08-08T09:46:35.770Z
@moustetail Python generators (with `yield`) produce external (pull-based) iterators that look a bit like internal ones while you're writing them; I don't know that they avoid any particular downsides other than that, and it's not usually the authoring ergonomics that are the concern. They are also limited coroutines that can have values injected back into them, but that's not really related to either kind.
Michael Homer
# What are "interior iteration" and "exterior iteration"?
Posted by: username_0 on 2023-08-06
[Another question](https://langdev.stackexchange.com/q/2664/89) refers to the terms "interior iteration" and "exterior iteration", and the comments under an answer suggest some disagreement or confusion about the meanings of these terms. The terms "internal iteration" and "external iteration" are also used there, though it's not clear if they are (respectively) synonyms.

What do these terms mean? And do they together describe all iteration, or are there other kinds than these two?
**Tags:** iterators terminology
> **Comments:**
> **username_1**: The best explanation I know of is Bob Nystrom's https://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/  
---
## 1 answers
### Answer by username_2 on 2023-08-07. Score: 12 | Accepted answer
"Interior" and "exterior" iteration seem to be simply a local shibboleth of the Rust community referring to what are usually called "internal" and "external" iteration. This may stem from an overloaded use of "internal" or "external" with another meaning that led these to be given a near-synonym, or a mistake at some point that's been propagated onwards. It's also possible it was for deliberate distancing from the object-oriented usage of the common terms, but I didn't find any evidence of that. The linked question uses the more standard terms everywhere except the direct quote.

Search results for either term in this meaning appear all to be connected to Rust on Google, Bing, or DuckDuckGo, and almost all other uses of "interior iteration" are discussing periods of nested loops; people also often use "internal" and "external" in reference to Rust. These terms do not have general currency and are only used as synonyms to the usual terms, and principally within that one language community; "exterior" has very little use at all.

---

**Internal iterators**, as in Smalltalk or Ruby, are higher-order functions provided on iterable values that accept another function or some sort of runnable value, and evaluate that function for each contained or produced value in the iterable using the privileged internal access the aggregate value has to itself. It's a **push-based model where control rests with the iterable**. This is what [the Graydon Hoare post](https://graydon2.dreamwidth.org/307291.html) quoted in that question was referring to as "interior"; Rust's old iteration model used a similar form to Ruby.

**External iterators**, as in Java, modern Rust and the GoF *Design Patterns* book, **reify the iteration state** into a value which provides operations to advance the iteration and to return its current value. The iterator value often has privileged access to the internal state of the aggregate, but not necessarily, and code that uses it will invoke those operations repeatedly to access each item in the iterable. These generally provide further flexibility to do things like interleave iterations of multiple aggregates, and it's simple to create an internal-like iteration operation on top of them; they also tend to have worse cache locality and allocation costs, but these prices are often found worthwhile.

In the 2012-ish Rust model, internal iteration was supported at the language level using non-first-class coroutines with yielding and no reentrancy. It's *conceivable* to decide to refer to this specific approach as "interior" as a contrast with object-oriented internal iterators using first-class function objects, but it's fundamentally parallel to Ruby's internal iteration, and it doesn't appear that most contemporary mentions of "interior iteration" do refer to that specific model. The [modern "exterior" iterators](https://doc.rust-lang.org/std/iter/trait.Iterator.html) are exactly standard external iterators, however, and the [headline documentation refers to them as such](https://doc.rust-lang.org/std/iter/index.html).

Some history of the process to that point is set out in [this social media post by Graydon Hoare](https://mastodon.social/@graydon@types.pl/109995318212060698), where an intermediate stage of exactly an OO-style internal approach also appears; it's possible that the "interior" distinction arose there, but "exterior" does not have similar support or any use from other sources.

---

Some languages & their libraries provide one or the other of these iteration models, and some provide both. There are trade-offs that favour each of them in both design and implementation. For example, JavaScript includes both a [forEach method](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach) (internal iteration) and an [iterator protocol](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols#the_iterable_protocol) (external iteration); the latter is what is wrapped up by the built-in `for ... of` foreach syntax.

Ruby is able to lift its internal iterators into external iterators through coroutines that evaluate the internal iterator until a value is yielded (blocking until it does), and then return it to the caller through an external iteration protocol; when the iterator is asked for the next value, it does the same thing again. This use of coroutines isn't directly related to the use given in the Hoare post, which was about not-quite-first-class resumable code blocks used for the loop itself. In principle, any language could allow this sort of lifting, but it is quite rare in practice.

---

There are many kinds of iteration more generally, through loops, recursion, and jumps. These named "iterator" types are for iteration over notional collections of values, and don't encompass all of those forms — a `while` loop is not generally either of these, and a cyclic `goto` couldn't be represented in either of these models at all. Both "internal iterator" and "external iterator" are terms most commonly, though not exclusively, found in object-oriented language communities, especially those influenced by the *Design Patterns: Elements of Reusable Object-Oriented Software* book that uses the name "Iterator" for one of its patterns that describes an external iterator.
> **Comments:**
> **username_3** (2023-08-07): Am I correct that `yield` keyword in python and some other languages effectively provide both the advantages of internal and external iterators while avoiding most of the downsides?  
> **username_1** (2023-08-07): `yield` mitigates the downsides of external iteration by automating the reification of the iteration state. Similarly, coroutines mitigate the downsides of internal iteration. I suppose this is where I post the link to Bob Nystrom's second post, that mentions both yield and coroutines: https://journal.stuffwithstuff.com/2013/02/24/iteration-inside-and-out-part-2/  
> **username_2** (2023-08-08): @moustetail Python generators (with `yield`) produce external (pull-based) iterators that look a bit like internal ones while you're writing them; I don't know that they avoid any particular downsides other than that, and it's not usually the authoring ergonomics that are the concern. They are also limited coroutines that can have values injected back into them, but that's not really related to either kind.  
---
