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