1 Concepts
2 ========
3
4 This document describes the underlying concepts employed in micropython.
5
6 * Namespaces and attribute definition
7 * Contexts and values
8 * Tables, attributes and lookups
9 * Objects and structures
10 * Parameters and lookups
11 * Instantiation
12 * Register usage
13
14 Namespaces and Attribute Definition
15 ===================================
16
17 Namespaces are any objects which can retain attributes.
18
19 * Module attributes are defined either at the module level or by global
20 statements.
21 * Class attributes are defined only within class statements.
22 * Instance attributes are defined only by assignments to attributes of self
23 within __init__ methods.
24
25 These restrictions apply because such attributes are thus explicitly declared,
26 permitting the use of tables (described below). Module and class attributes
27 can also be finalised in this way in order to permit certain optimisations.
28
29 See rejected.txt for complicating mechanisms which could be applied to
30 mitigate the effects of these restrictions on optimisations.
31
32 Contexts and Values
33 ===================
34
35 Values are used as the common reference representation in micropython: as
36 stored representations of attributes (of classes, instances, modules, and
37 other objects supporting attribute-like entities) as well as the stored values
38 associated with names in functions and methods.
39
40 Unlike other implementations, micropython does not create things like bound
41 method objects for individual instances. Instead, all objects are referenced
42 using a context, reference pair:
43
44 Value Layout
45 ------------
46
47 0 1
48 context object
49 reference reference
50
51 Specific implementations might reverse this ordering for optimisation
52 purposes.
53
54 Rationale
55 ---------
56
57 To reduce the number of created objects whilst retaining the ability to
58 support bound method invocations. The context indicates the context in which
59 an invocation is performed, typically the owner of the method.
60
61 Usage
62 -----
63
64 The context may be inserted as the first argument when a value is involved in
65 an invocation. This argument may then be omitted from the invocation if its
66 usage is not appropriate.
67
68 See invocation.txt for details.
69
70 Context Value Types
71 -------------------
72
73 The following types of context value exist:
74
75 Type Usage Transformations
76 ---- ----- ---------------
77
78 Replaceable With functions (not methods) May be replaced with an
79 instance or a class when a
80 value is stored on an
81 instance or class
82
83 Placeholder With classes May not be replaced
84
85 Instance With instances (and constants) May not be replaced
86 or functions as methods
87
88 Class With functions as methods May be replaced when a
89 value is loaded from a
90 class attribute via an
91 instance
92
93 Contexts in Acquired Values
94 ---------------------------
95
96 There are four classes of instructions which provide values:
97
98 Instruction Purpose Context Operations
99 ----------- ------- ------------------
100
101 1) LoadConst Load module, constant Use loaded object with itself
102 as context
103
104 2) LoadFunction Load function Combine replaceable context
105 with loaded object
106
107 3) LoadClass Load class Combine placeholder context
108 with loaded object
109
110 4) LoadAddress* Load attribute from Preserve or override stored
111 LoadAttr* class, module, context (as described in
112 instance assignment.txt)
113
114 In order to comply with traditional Python behaviour, contexts may or may not
115 represent the object from which an attribute has been acquired.
116
117 See assignment.txt for details.
118
119 Contexts in Stored Values
120 -------------------------
121
122 There are two classes of instruction for storing values:
123
124 Instruction Purpose Context Operations
125 ----------- ------- ------------------
126
127 1) StoreAddress Store attribute in a Preserve context; note that no
128 known object test for class attribute
129 assignment should be necessary
130 since this instruction should only
131 be generated for module globals
132
133 StoreAttr Store attribute in an Preserve context; note that no
134 instance test for class attribute
135 assignment should be necessary
136 since this instruction should only
137 be generated for self accesses
138
139 StoreAttrIndex Store attribute in an Preserve context; since the index
140 unknown object lookup could yield a class
141 attribute, a test of the nature of
142 the nature of the structure is
143 necessary in order to prevent
144 assignments to classes
145
146 2) StoreAddressContext Store attribute in a Override context if appropriate;
147 known object if the value has a replaceable
148 context, permit the target to
149 take ownership of the value
150
151 See assignment.txt for details.
152
153 Tables, Attributes and Lookups
154 ==============================
155
156 Attribute lookups, where the exact location of an object attribute is deduced,
157 are performed differently in micropython than in other implementations.
158 Instead of providing attribute dictionaries, in which attributes are found,
159 attributes are located at fixed places in object structures (described below)
160 and their locations are stored using a special representation known as a
161 table.
162
163 For a given program, a table can be considered as being like a matrix mapping
164 classes to attribute names. For example:
165
166 class A:
167 # instances have attributes x, y
168
169 class B(A):
170 # introduces attribute z for instances
171
172 class C:
173 # instances have attributes a, b, z
174
175 This would provide the following table, referred to as an object table in the
176 context of classes and instances:
177
178 Class/attr a b x y z
179
180 A 1 2
181 B 1 2 3
182 C 1 2 3
183
184 A limitation of this representation is that instance attributes may not shadow
185 class attributes: if an attribute with a given name is not defined on an
186 instance, an attribute with the same name cannot be provided by the class of
187 the instance or any superclass of the instance's class.
188
189 The table can be compacted using a representation known as a displacement
190 list (referred to as an object list in this context):
191
192 Classes with attribute offsets
193
194 classcode A
195 attrcode a b x y z
196
197 B
198 a b x y z
199
200 C
201 a b x y z
202
203 List . . 1 2 1 2 3 1 2 . . 3
204
205 Here, the classcode refers to the offset in the list at which a class's
206 attributes are defined, whereas the attrcode defines the offset within a
207 region of attributes corresponding to a single attribute of a given name.
208
209 Attribute Locations
210 -------------------
211
212 The locations stored in table/list elements are for instance attributes
213 relative to the location of the instance, whereas those for class attributes
214 and modules are absolute addresses (although these could also be changed to
215 object-relative locations). Thus, each occupied table cell has the following
216 structure:
217
218 attrcode, uses-absolute-address, address (or location)
219
220 Objects and Structures
221 ======================
222
223 As well as references, micropython needs to have actual objects to refer to.
224 Since classes, functions and instances are all objects, it is desirable that
225 certain common features and operations are supported in the same way for all
226 of these things. To permit this, a common data structure format is used.
227
228 Header.................................................... Attributes.................
229
230 Identifier Identifier Address Identifier Size Object Object ...
231
232 0 1 2 3 4 5 6 7
233 classcode attrcode/ invocation funccode size __class__ attribute ...
234 instance reference reference reference
235 status
236
237 Classcode
238 ---------
239
240 Used in attribute lookup.
241
242 Here, the classcode refers to the attribute lookup table for the object (as
243 described above). Classes and instances share the same classcode, and their
244 structures reflect this. Functions all belong to the same type and thus employ
245 the classcode for the function built-in type, whereas modules have distinct
246 types since they must support different sets of attributes.
247
248 Attrcode
249 --------
250
251 Used to test instances for membership of classes (or descendants of classes).
252
253 Since, in traditional Python, classes are only ever instances of some generic
254 built-in type, support for testing such a relationship directly has been
255 removed and the attrcode is not specified for classes: the presence of an
256 attrcode indicates that a given object is an instance. In addition, support
257 has also been removed for testing modules in the same way, meaning that the
258 attrcode is also not specified for modules.
259
260 See the "Testing Instance Compatibility with Classes (Attrcode)" section below
261 for details of attrcodes.
262
263 Invocation Reference
264 --------------------
265
266 Used when an object is called.
267
268 This is the address of the code to be executed when an invocation is performed
269 on the object.
270
271 Funccode
272 --------
273
274 Used to look up argument positions by name.
275
276 The strategy with keyword arguments in micropython is to attempt to position
277 such arguments in the invocation frame as it is being constructed.
278
279 See the "Parameters and Lookups" section for more information.
280
281 Size
282 ----
283
284 Used to indicate the size of an object including attributes.
285
286 Attributes
287 ----------
288
289 For classes, modules and instances, the attributes in the structure correspond
290 to the attributes of each kind of object. For functions, however, the
291 attributes in the structure correspond to the default arguments for each
292 function, if any.
293
294 Structure Types
295 ---------------
296
297 Class C:
298
299 0 1 2 3 4 5 6 7
300 classcode (unused) __new__ funccode size class type attribute ...
301 for C reference for reference reference
302 instantiator
303
304 Instance of C:
305
306 0 1 2 3 4 5 6 7
307 classcode attrcode C.__call__ funccode size class C attribute ...
308 for C for C reference for reference reference
309 (if exists) C.__call__
310
311 Function f:
312
313 0 1 2 3 4 5 6 7
314 classcode attrcode code funccode size class attribute ...
315 for for reference function (default)
316 function function reference reference
317
318 Module m:
319
320 0 1 2 3 4 5 6 7
321 classcode attrcode (unused) (unused) (unused) module type attribute ...
322 for m for m reference (global)
323 reference
324
325 The __class__ Attribute
326 -----------------------
327
328 All objects support the __class__ attribute and this is illustrated above with
329 the first attribute.
330
331 Class: refers to the type class (type.__class__ also refers to the type class)
332 Function: refers to the function class
333 Instance: refers to the class instantiated to make the object
334
335 Lists and Tuples
336 ----------------
337
338 The built-in list and tuple sequences employ variable length structures using
339 the attribute locations to store their elements, where each element is a
340 reference to a separately stored object.
341
342 Testing Instance Compatibility with Classes (Attrcode)
343 ------------------------------------------------------
344
345 Although it would be possible to have a data structure mapping classes to
346 compatible classes, such as a matrix indicating the subclasses (or
347 superclasses) of each class, the need to retain the key to such a data
348 structure for each class might introduce a noticeable overhead.
349
350 Instead of having a separate structure, descendant classes of each class are
351 inserted as special attributes into the object table. This requires an extra
352 key to be retained, since each class must provide its own attribute code such
353 that upon an instance/class compatibility test, the code may be obtained and
354 used in the object table.
355
356 Invocation and Code References
357 ------------------------------
358
359 Modules: there is no meaningful invocation reference since modules cannot be
360 explicitly called.
361
362 Functions: a simple code reference is employed pointing to code implementing
363 the function. Note that the function locals are completely distinct from this
364 structure and are not comparable to attributes. Instead, attributes are
365 reserved for default parameter values, although they do not appear in the
366 object table described above, appearing instead in a separate parameter table
367 described below.
368
369 Classes: given that classes must be invoked in order to create instances, a
370 reference must be provided in class structures. However, this reference does
371 not point directly at the __init__ method of the class. Instead, the
372 referenced code belongs to a special initialiser function, __new__, consisting
373 of the following instructions:
374
375 create instance for C
376 call C.__init__(instance, ...)
377 return instance
378
379 Instances: each instance employs a reference to any __call__ method defined in
380 the class hierarchy for the instance, thus maintaining its callable nature.
381
382 Both classes and modules may contain code in their definitions - the former in
383 the "body" of the class, potentially defining attributes, and the latter as
384 the "top-level" code in the module, potentially defining attributes/globals -
385 but this code is not associated with any invocation target. It is thus
386 generated in order of appearance and is not referenced externally.
387
388 Invocation Operation
389 --------------------
390
391 Consequently, regardless of the object an invocation is always done as
392 follows:
393
394 get invocation reference from the header
395 jump to reference
396
397 Additional preparation is necessary before the above code: positional
398 arguments must be saved in the invocation frame, and keyword arguments must be
399 resolved and saved to the appropriate position in the invocation frame.
400
401 See invocation.txt for details.
402
403 Parameters and Lookups
404 ======================
405
406 Since Python supports keyword arguments when making invocations, it becomes
407 necessary to record the parameter names associated with each function or
408 method. Just as object tables record attributes positions on classes and
409 instances, parameter tables record parameter positions in function or method
410 parameter lists.
411
412 For a given program, a parameter table can be considered as being like a
413 matrix mapping functions/methods to parameter names. For example:
414
415 def f(x, y, z):
416 pass
417
418 def g(a, b, c):
419 pass
420
421 def h(a, x):
422 pass
423
424 This would provide the following table, referred to as a parameter table in
425 the context of functions and methods:
426
427 Function/param a b c x y z
428
429 f 1 2 3
430 g 1 2 3
431 h 1 2
432
433 Confusion can occur when functions are adopted as methods, since the context
434 then occupies the first slot in the invocation frame:
435
436 def f(x, y, z):
437 pass
438
439 f(x=1, y=2, z=3) -> f(<context>, 1, 2, 3)
440 -> f(1, 2, 3)
441
442 class C:
443 f = f
444
445 def g(x, y, z):
446 pass
447
448 c = C()
449
450 c.f(y=2, z=3) -> f(<context>, 2, 3)
451 c.g(y=2, z=3) -> C.g(<context>, 2, 3)
452
453 Just as with parameter tables, a displacement list can be prepared from a
454 parameter table:
455
456 Functions with parameter (attribute) offsets
457
458 funccode f
459 attrcode a b c x y z
460
461 g
462 a b c x y z
463
464 h
465 a b c x y z
466
467 List . . . 1 2 3 1 2 3 1 . . 2 . .
468
469 Here, the funccode refers to the offset in the list at which a function's
470 parameters are defined, whereas the attrcode defines the offset within a
471 region of attributes corresponding to a single parameter of a given name.
472
473 Instantiation
474 =============
475
476 When instantiating classes, memory must be reserved for the header of the
477 resulting instance, along with locations for the attributes of the instance.
478 Since the instance header contains data common to all instances of a class, a
479 template header is copied to the start of the newly reserved memory region.
480
481 Register Usage
482 ==============
483
484 During code generation, much of the evaluation produces results which are
485 implicitly recorded in the "active value" register, and various instructions
486 will consume the active value. In addition, some instructions will consume a
487 separate "active source value" from a register, typically those which are
488 assigning the result of an expression to an assignment target.
489
490 Since values often need to be retained for later use, a set of temporary
491 storage locations are typically employed. However, optimisations may reduce
492 the need to use such temporary storage where instructions which provide the
493 "active value" can be re-executed and will produce the same result.