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