<p>How do I implement strings, lists and dicts in bytecode?</p>
<p>For example, disassembling the bytecode might look like this:</p>
<pre><code>LOAD str &quot;hello, world&quot;
</code></pre>
<p>But how does it work in real bytecode?</p>
<pre><code>0x01 0x5 ???
</code></pre>
<p>PS: <code>0x01</code> is <code>LOAD</code> command, and <code>0x05</code> is str type.</p>

<implementation><bytecode>
How are strings, lists and dicts implemented in bytecode?
<p>Value &quot;literals&quot; in source code can be divided into four groups:</p>
<ol>
<li>Simple literals. This includes immutable &quot;simple&quot; values like numeric literals, and strings (if strings are immutable).</li>
<li>Constant value expressions. This includes immutable &quot;simple&quot; values like numeric literals, and strings (if strings are immutable), but also immutable containers like in Python's <code>tuple</code> as long as all their elements are constant value expressions. <code>(1, 2, 3)</code> would be a constant value expression but <code>(1, 2, three())</code> would not be. Something like <code>(1, 2, 7 - 4)</code> might be a constant value expression depending on if your parser implements constant folding.</li>
<li>Mutable constant value expressions. There may be a better word for this, as it looks like a contradiction, but these are CVEs except the constraint of immutability is relaxed. Examples are string literals (if strings are mutable) and expressions of mutable containers only containing MCVEs. Using Python lists as examples, <code>[1, 2, 3]</code> would be an MCVE, but <code>[1, 2, three()]</code> would not. And <code>[1, 2, 7 - 4]</code> counting as MCVE would depend on constant folding.</li>
<li>Arbitrary value displays. This includes <code>(1, 2, three())</code> and <code>[1, 2, three()]</code>.</li>
</ol>
<p>To implement AVDs, you really need to consider these as expressions, like how <code>one() + two()</code> is implemented. In a stack-based bytecode language, that may compile to something like:</p>
<pre><code>PUSH_FUNCTION one
CALL_FUNCTION
PUSH_FUNCTION two
CALL_FUNCTION
ADD
</code></pre>
<p>Whereas <code>[one(), two()]</code> may be:</p>
<pre><code>PUSH_MARKER
PUSH_FUNCTION one
CALL_FUNCTION
PUSH_FUNCTION two
CALL_FUNCTION
GATHER_UP_TO_MARKER_AS_LIST
</code></pre>
<p>or</p>
<pre><code>PUSH_FUNCTION one
CALL_FUNCTION
PUSH_FUNCTION two
CALL_FUNCTION
MAKE_LIST 2
</code></pre>
<p>For simple literals, there are two basic ways of dealing with them (as shown in the answers by abel1502 and RubenVerg): inline and indexing a specialised section of the bytecode.</p>
<p>I consider the indexing approach superior, because it allows you to collect all instances of a particular literal into a single occurrence in the bytecode. This can save memory and also CPU time, because you only have to construct the values at runtime once, even if the literal is evaluated many times. It can also help decoding instructions to be faster if there isn't an arbitrary offset between one instruction and the next (which is a consequence of inlining literals).</p>
<p>You can also combine both approaches, for example by inlining all fixed-size integers that fit into the argument part of the instruction and indexing for all other simple literals.</p>
<p>CVEs and MCVEs can be implemented the same as AVDs, but you can take advantage of their contents being known at compile time by treating them as simple literals, at the cost of making the literals section a bit more complex. And for MCVEs you need to take care that a copy is made when their expression is evaluated, either by emitting a <code>DEEPCOPY</code> instruction or by having the copying behaviour built into the instruction that retrieves the stored value.</p>

CC BY-SA 4.0
2023-05-30T12:21:43.513Z
2023-05-30T12:21:43.513Z
Jasmijn
<p>Stuq (no public code available yet, sorry) simply inlines the string bytes.</p>
<p><code>&quot;HELLO&quot;</code> compiles to</p>
<pre><code>0x17 ; PUSH_STR_SHORT (length between 5 and 261 bytes)
0x00 ; 5 bytes long
0x67 ; 'H'
0x64 ; 'E'
0x6b ; 'L'
0x6b ; 'L'
0x71 ; 'O'
</code></pre>
<p>List literals don't exist in the traditional sense, but for completeness they look like this:</p>
<p><code>⟨ 1 2 3 ⟩</code> compiles to</p>
<pre><code>0x3a ; PUSH_LIST_START_MARKER
0x20 ; PUSH_NUMBER_SHORT (1-byte)
0x01
0x20 0x02
0x20 0x03
0x3f ; CALL_LIST_END (collects all elements up to marker and pushes a list containing them)
</code></pre>

CC BY-SA 4.0
2023-05-30T09:53:52.567Z
2023-05-30T09:53:52.567Z
RubenVerg
<p>Python's bytecode handles this by placing all constants in a container separate from the bytecode (<code>co_consts</code>), and then having instructions utilize indices into it. For lists and dicts an alternative mechanism is also used, where their literals are expanded into pushing the contained items onto the stack and then invoking a special instuction for building a literal with the specified number of items from the stack (<code>BUILD_LIST</code>, <code>BUILD_MAP</code> &amp; some more).</p>

CC BY-SA 4.0
2023-05-30T08:43:16.437Z
2023-05-30T08:43:16.437Z
abel1502
CC BY-SA 4.0
2023-05-30T10:19:24.683Z
Worth adding that the reason Python caches string constants in `co_consts` but not lists or dicts, is because the latter are mutable. Tuples do get cached if their elements are also constants, and lists and sets can be compiled to constant tuples or frozensets if they are used in expressions which can't leak references to them (e.g. `x in {1, 2, 3}` gets compiled to use a frozenset).
kaya3
CC BY-SA 4.0
2023-05-30T12:42:25.537Z
Java does this as well, although too not for lists, arrays, or maps.
Seggan
# How are strings, lists and dicts implemented in bytecode?
Posted by: username_0 on 2023-05-30
How do I implement strings, lists and dicts in bytecode?
For example, disassembling the bytecode might look like this:
LOAD str "hello, world"

But how does it work in real bytecode?
0x01 0x5 ???

PS: 0x01 is LOAD command, and 0x05 is str type.
**Tags:** implementation bytecode
---
## 3 answers
### Answer by username_3 on 2023-05-30. Score: 7 | Accepted answer
Python's bytecode handles this by placing all constants in a container separate from the bytecode (`co_consts`), and then having instructions utilize indices into it. For lists and dicts an alternative mechanism is also used, where their literals are expanded into pushing the contained items onto the stack and then invoking a special instuction for building a literal with the specified number of items from the stack (`BUILD_LIST`, `BUILD_MAP` & some more).
> **Comments:**
> **username_4** (2023-05-30): Worth adding that the reason Python caches string constants in `co_consts` but not lists or dicts, is because the latter are mutable. Tuples do get cached if their elements are also constants, and lists and sets can be compiled to constant tuples or frozensets if they are used in expressions which can't leak references to them (e.g. `x in {1, 2, 3}` gets compiled to use a frozenset).  
> **username_5** (2023-05-30): Java does this as well, although too not for lists, arrays, or maps.  
---
### Answer by username_1 on 2023-05-30. Score: 4
Value "literals" in source code can be divided into four groups:

Simple literals. This includes immutable "simple" values like numeric literals, and strings (if strings are immutable).
Constant value expressions. This includes immutable "simple" values like numeric literals, and strings (if strings are immutable), but also immutable containers like in Python's tuple as long as all their elements are constant value expressions. (1, 2, 3) would be a constant value expression but (1, 2, three()) would not be. Something like (1, 2, 7 - 4) might be a constant value expression depending on if your parser implements constant folding.
Mutable constant value expressions. There may be a better word for this, as it looks like a contradiction, but these are CVEs except the constraint of immutability is relaxed. Examples are string literals (if strings are mutable) and expressions of mutable containers only containing MCVEs. Using Python lists as examples, [1, 2, 3] would be an MCVE, but [1, 2, three()] would not. And [1, 2, 7 - 4] counting as MCVE would depend on constant folding.
Arbitrary value displays. This includes (1, 2, three()) and [1, 2, three()].

To implement AVDs, you really need to consider these as expressions, like how one() + two() is implemented. In a stack-based bytecode language, that may compile to something like:
PUSH_FUNCTION one
CALL_FUNCTION
PUSH_FUNCTION two
CALL_FUNCTION
ADD

Whereas [one(), two()] may be:
PUSH_MARKER
PUSH_FUNCTION one
CALL_FUNCTION
PUSH_FUNCTION two
CALL_FUNCTION
GATHER_UP_TO_MARKER_AS_LIST

or
PUSH_FUNCTION one
CALL_FUNCTION
PUSH_FUNCTION two
CALL_FUNCTION
MAKE_LIST 2

For simple literals, there are two basic ways of dealing with them (as shown in the answers by abel1502 and RubenVerg): inline and indexing a specialised section of the bytecode.
I consider the indexing approach superior, because it allows you to collect all instances of a particular literal into a single occurrence in the bytecode. This can save memory and also CPU time, because you only have to construct the values at runtime once, even if the literal is evaluated many times. It can also help decoding instructions to be faster if there isn't an arbitrary offset between one instruction and the next (which is a consequence of inlining literals).
You can also combine both approaches, for example by inlining all fixed-size integers that fit into the argument part of the instruction and indexing for all other simple literals.
CVEs and MCVEs can be implemented the same as AVDs, but you can take advantage of their contents being known at compile time by treating them as simple literals, at the cost of making the literals section a bit more complex. And for MCVEs you need to take care that a copy is made when their expression is evaluated, either by emitting a DEEPCOPY instruction or by having the copying behaviour built into the instruction that retrieves the stored value.
---
### Answer by username_2 on 2023-05-30. Score: 2
Stuq (no public code available yet, sorry) simply inlines the string bytes.
"HELLO" compiles to
0x17 ; PUSH_STR_SHORT (length between 5 and 261 bytes)
0x00 ; 5 bytes long
0x67 ; 'H'
0x64 ; 'E'
0x6b ; 'L'
0x6b ; 'L'
0x71 ; 'O'

List literals don't exist in the traditional sense, but for completeness they look like this:
⟨ 1 2 3 ⟩ compiles to
0x3a ; PUSH_LIST_START_MARKER
0x20 ; PUSH_NUMBER_SHORT (1-byte)
0x01
0x20 0x02
0x20 0x03
0x3f ; CALL_LIST_END (collects all elements up to marker and pushes a list containing them)
---
