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