Lichen

Changeset

862:0c3887bb6ff8
2019-01-17 Paul Boddie raw files shortlog changelog graph Expanded various sections and formatted the text in various places.
docs/wiki/Deduction (file)
     1.1 --- a/docs/wiki/Deduction	Fri Aug 17 11:41:28 2018 +0200
     1.2 +++ b/docs/wiki/Deduction	Thu Jan 17 14:11:37 2019 +0100
     1.3 @@ -9,13 +9,13 @@
     1.4  
     1.5  == The Deduction Process ==
     1.6  
     1.7 -The deduction process takes observations made during the
     1.8 -[[../Inspection|inspection process]] and attempts to form deductions about the
     1.9 -behaviour of the program primarily in terms of the nature of the attribute
    1.10 -'''accesses''', with their corresponding '''accessors''', featuring in the
    1.11 -program. Where attributes are used in conjunction with names, accessors are
    1.12 -name versions; where attributes are used in conjunction with other
    1.13 -expressions, accessors are '''anonymous'''.
    1.14 +The deduction process takes observations made during the [[../Inspection|
    1.15 +inspection process]] and attempts to form deductions about the behaviour of
    1.16 +the program primarily in terms of the nature of the attribute '''accesses''',
    1.17 +with their corresponding '''accessors''', featuring in the program. Where
    1.18 +attributes are used in conjunction with names, accessors are name versions;
    1.19 +where attributes are used in conjunction with other expressions, accessors are
    1.20 +'''anonymous'''.
    1.21  
    1.22  === Indexes ===
    1.23  
    1.24 @@ -23,28 +23,58 @@
    1.25  following things:
    1.26  
    1.27  {{{#!table
    1.28 -'''Indexes''' || '''Details'''
    1.29 +'''Indexes''' || '''From''' || '''To''' || '''Purpose'''
    1.30 +==
    1.31 +`access_index`
    1.32 +|| access operation
    1.33 +|| accessor (name version)
    1.34 +|| defining types at access locations
    1.35  ==
    1.36 -`access_index` || Which accessors (name versions) are involved with access
    1.37 -               .. operations
    1.38 +`access_index_rev`
    1.39 +|| accessor (name version)
    1.40 +|| access operations
    1.41 +|| determining whether names are used for accesses; establishing alias
    1.42 +.. information
    1.43  ==
    1.44 -`location_index` || Which attribute usage patterns are supported by accessors
    1.45 -                 .. (name versions)
    1.46 +`location_index`
    1.47 +|| accessor (name version)
    1.48 +|| attribute usage patterns
    1.49 +|| deducing types for names
    1.50  ==
    1.51  `attr_class_types`<<BR>>`attr_instance_types`<<BR>>`attr_module_types`
    1.52 -|| Which types support which attribute names
    1.53 +|| attribute name and assignment state
    1.54 +|| class, instance, module types
    1.55 +|| determining types supporting name accesses and assignments
    1.56  ==
    1.57  `assigned_attrs`
    1.58 -|| Which usage patterns involve attribute assignment
    1.59 +|| attribute usage pattern
    1.60 +|| attribute assignment locations
    1.61 +|| determining possibly mutated attributes on types
    1.62 +==
    1.63 +`alias_index`
    1.64 +|| alias (name version)
    1.65 +|| accesses
    1.66 +|| determining the identities of aliases (name versions) from initialising
    1.67 +.. name or attribute accesses
    1.68 +==
    1.69 +`alias_index_rev`
    1.70 +|| access
    1.71 +|| aliases (name versions)
    1.72 +|| propagating updated information from accesses to aliases
    1.73 +}}}
    1.74 +
    1.75 +Various collections are also maintained:
    1.76 +
    1.77 +{{{#!table
    1.78 +'''Collections''' || '''Details''' || '''Purpose'''
    1.79  ==
    1.80  `reference_assignments`
    1.81 -|| Which accesses involve assignments
    1.82 +|| accesses involving assignments
    1.83 +|| constraining accessor types; adjusting access plans
    1.84  ==
    1.85  `reference_invocations`
    1.86 -|| Which accesses involve invocations
    1.87 -==
    1.88 -`alias_index`
    1.89 -|| Which names are aliases for other names, accesses or invocations
    1.90 +|| accesses involving invocations
    1.91 +|| converting access types to instantiation or invocation results
    1.92  }}}
    1.93  
    1.94  The objective of deduction is to combine these indexes to establish new
    1.95 @@ -312,8 +342,10 @@
    1.96  
    1.97   * Any name whose initialisation could be determined during inspection can be
    1.98     associated with its initialised type
    1.99 +
   1.100   * Any name referring to a constant object can be associated with the type of
   1.101     that object
   1.102 +
   1.103   * Usage of `self` in methods can result in only compatible class and instance
   1.104     types being retained from the types obtained from usage deductions
   1.105  
   1.106 @@ -325,8 +357,11 @@
   1.107  accessors and access situations exist:
   1.108  
   1.109   * Name-based accesses involving attribute usage
   1.110 +
   1.111   * Aliases to names, possibly accompanied by accesses
   1.112 +
   1.113   * Anonymous accesses involving individual attributes
   1.114 +
   1.115   * Constant or previously-identified names, possibly accompanied by accesses
   1.116  
   1.117  === Aliases ===
   1.118 @@ -367,14 +402,18 @@
   1.119  
   1.120   * Provider types, indicating which types may provide the attributes used by
   1.121     the accessor
   1.122 +
   1.123   * Accessor types, indicating which types will actually appear as the accessor
   1.124  
   1.125 -This information can be processed in a number of ways to produce the following:
   1.126 +This information can be processed in a number of ways to produce the
   1.127 +following:
   1.128  
   1.129   * All types (from all kinds of type) of providers able to provide attributes
   1.130     via the accessor
   1.131 +
   1.132   * All types (from all kinds of type) of accessors compatible with the
   1.133     accessor
   1.134 +
   1.135   * The most general types of accessors compatible with the accessor
   1.136  
   1.137  Where many types may be associated with an accessor, identifying the most
   1.138 @@ -403,19 +442,25 @@
   1.139  following:
   1.140  
   1.141   * The accessors potentially involved in each access
   1.142 +
   1.143   * The types of accessors and the types providing attributes via those
   1.144     accessors
   1.145 +
   1.146   * Any guards applying to the accessors
   1.147 +
   1.148   * Whether an access is constrained by certain program characteristics and is
   1.149     thus guaranteed to be as deduced
   1.150 +
   1.151   * The possible attributes referenced by the access
   1.152  
   1.153  This information can be processed in a number of ways to produce the
   1.154  following:
   1.155  
   1.156   * The types of accessors, both general and specific, applying to each access
   1.157 +
   1.158   * The attributes that can be provided by each access, consolidating existing
   1.159     referenced attribute details
   1.160 +
   1.161   * The general types providing the attributes
   1.162  
   1.163  Since more than one accessor may be involved, information from all accessors
   1.164 @@ -456,8 +501,8 @@
   1.165   * Details of any test required on the initial accessor
   1.166   * Details of any type employed by the test
   1.167   * Any identified static accessor (to be used as the initial accessor)
   1.168 - * Attributes needing to be traversed from the accessor that yield unambiguous
   1.169 -   objects
   1.170 + * Attributes needing to be traversed from the accessor that yield
   1.171 +   unambiguous objects
   1.172   * Access modes for each of the unambiguously-traversed attributes
   1.173   * Remaining attributes needing to be tested and traversed (after having
   1.174     traversed the above attributes)
   1.175 @@ -475,6 +520,7 @@
   1.176  
   1.177   * Whether the initial accessor is static, originating from a constant access
   1.178     or involving an identifiable static object
   1.179 +
   1.180   * Whether the initial accessor is dynamic but has a known, deduced identity
   1.181  
   1.182  Some useful information about the accessor and about the actual provider of
   1.183 @@ -489,6 +535,7 @@
   1.184  
   1.185   * Object-relative accesses occur with class accessors or module accessors or
   1.186     when attributes are provided by instances
   1.187 +
   1.188   * Class-relative accesses occur with instance accessors when attributes are
   1.189     provided by classes
   1.190  
   1.191 @@ -531,21 +578,63 @@
   1.192  
   1.193  === Identifying Context Information ===
   1.194  
   1.195 -Final attribute accesses involving callables need to yield context information
   1.196 -that can subsequently be used to invoke those callables. Where the nature of
   1.197 -an accessed attribute is not known, a simplistic attempt can be made to look
   1.198 -up all attributes stored using the attribute name in the program.
   1.199 +Final attribute accesses involving callables need to incorporate context
   1.200 +information that can subsequently be used to invoke those callables. Where the
   1.201 +nature of an accessed attribute is not known, a simplistic attempt can be made
   1.202 +to look up all attributes stored using the attribute name in the program.
   1.203 +Otherwise, with knowledge of the attribute, its details can be inspected to
   1.204 +determine if context information plays a role in the access.
   1.205 +
   1.206 +==== Context Testing ====
   1.207  
   1.208  Of particular interest are the following situations:
   1.209  
   1.210   * Where class attributes are being accessed via instances, whether the
   1.211 -   attributes are all methods that can be bound upon access
   1.212 - * Where class attributes may be accessed via instances, whether any
   1.213 -   attributes could be methods
   1.214 +   attributes are all methods that are bound to the instances
   1.215 +
   1.216 + * Where class attributes ''may'' be accessed via instances, whether any
   1.217 +   attributes ''could be'' methods
   1.218  
   1.219  Such considerations dictate whether the context information originates from
   1.220  the attribute or from the accessor and whether any run-time test is required
   1.221 -to determine this.
   1.222 +to determine this. Thus, for attributes in general:
   1.223 +
   1.224 +{{{#!table
   1.225 +'''Accessor''' || '''Provider''' || '''Attributes'''
   1.226 +|| '''Effect on Context''' || '''Remark'''
   1.227 +==
   1.228 +Always instances || Always classes || Always methods
   1.229 +|| Replacement
   1.230 +|| Permit method calling using the instance as context
   1.231 +==
   1.232 +Always instances || Always classes || Sometimes methods
   1.233 +|| Test at run-time
   1.234 +|| Preserve original context for non-methods
   1.235 +==
   1.236 +Sometimes instances || Sometimes classes || Sometimes methods
   1.237 +|| Test at run-time
   1.238 +|| Preserve original context for non-methods, non-instance accessors
   1.239 +}}}
   1.240 +
   1.241 +In all other situations, the available context is ignored, with the attribute
   1.242 +itself providing any stored context information.
   1.243 +
   1.244 +==== Context Identity ====
   1.245 +
   1.246 +Where the context is ignored, no effort will be made to obtain or retain it in
   1.247 +the program for the access operation: it will be unset. Otherwise, the context
   1.248 +will be defined as one of the following:
   1.249 +
   1.250 + * The "base" or static accessor where this is also the accessor for the final
   1.251 +   access
   1.252 +
   1.253 + * The original (or initial) accessor where this is also the accessor for the
   1.254 +   final access
   1.255 +
   1.256 + * The final accessor, having been identified through attribute traversal
   1.257 +
   1.258 +Note that non-static accessors may be computed dynamically and thus need to be
   1.259 +stored temporarily for subsequent use. 
   1.260  
   1.261  == Preparing Instruction Plans ==
   1.262  
   1.263 @@ -563,12 +652,24 @@
   1.264  subsequent mentions of the accessor can potentially be replaced with such
   1.265  references or names used as expressions.
   1.266  
   1.267 -|| '''Access Plan Information''' || '''Original Accessor''' ||
   1.268 -|| Static accessor identified || Identified accessor ||
   1.269 -|| Named accessor access, not invocation || Indicated name ||
   1.270 -|| Named accessor invocation, accessor known to provide the attribute || Indicated name ||
   1.271 -|| Named accessor invocation, accessor not known to provide the attribute || Accessor expression ||
   1.272 -|| Other accessors || Accessor expression ||
   1.273 +{{{#!table
   1.274 +'''Access Plan Information''' || '''Original Accessor'''
   1.275 +==
   1.276 +Static accessor identified
   1.277 +|| Identified accessor
   1.278 +==
   1.279 +Named accessor access, not invocation
   1.280 +|| Indicated name
   1.281 +==
   1.282 +Named accessor invocation, accessor known to provide the attribute
   1.283 +|| Indicated name
   1.284 +==
   1.285 +Named accessor invocation, accessor not known to provide the attribute
   1.286 +|| Accessor expression
   1.287 +==
   1.288 +Other accessors
   1.289 +|| Accessor expression
   1.290 +}}}
   1.291  
   1.292  By using names or static references, the need to store the result of
   1.293  evaluating an accessor expression is eliminated because such labels can be
   1.294 @@ -584,8 +685,10 @@
   1.295  
   1.296   * Final method is an access (meaning that an attribute cannot be directly
   1.297     obtained)
   1.298 +
   1.299   * Final method is an assignment (requiring the object whose attribute will be
   1.300     updated)
   1.301 +
   1.302   * Attributes (identified or otherwise) need traversing
   1.303  
   1.304  === Accessor Nature ===
   1.305 @@ -610,13 +713,176 @@
   1.306  
   1.307  === Context Testing ===
   1.308  
   1.309 +=== Instruction Details ===
   1.310 +
   1.311 +The emitted instructions are as follows.
   1.312 +
   1.313 +==== Direct Load ====
   1.314 +
   1.315 +These instructions employ the attribute position for the supplied attribute
   1.316 +name.
   1.317 +
   1.318 +{{{#!table
   1.319 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.320 +==
   1.321 +`__load_via_class` || object, attribute name
   1.322 +|| Obtain class from object; load attribute from class at position
   1.323 +==
   1.324 +`__load_via_object` || object, attribute name
   1.325 +|| Load attribute from object at position
   1.326 +==
   1.327 +`__get_class_and_load` || object, attribute name
   1.328 +|| Obtain class from object if instance; load attribute from result at
   1.329 +.. position
   1.330 +}}}
   1.331 +
   1.332 +==== Direct Store ====
   1.333 +
   1.334 +These instructions employ the attribute position for the supplied attribute
   1.335 +name, storing an attribute value.
   1.336 +
   1.337 +{{{#!table
   1.338 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.339 +==
   1.340 +`__store_via_class` || object, attribute name, value
   1.341 +|| Obtain class from object; store attribute in class at position
   1.342 +==
   1.343 +`__store_via_object` || object, attribute name, value
   1.344 +|| Store attribute in object at position
   1.345 +}}}
   1.346 +
   1.347 +==== Checked Load ====
   1.348 +
   1.349 +These instructions employ the attribute position and code for the supplied
   1.350 +attribute name.
   1.351 +
   1.352 +{{{#!table
   1.353 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.354 +==
   1.355 +`__check_and_load_via_class` || object, attribute name
   1.356 +|| Obtain class from object; test for attribute and load or raise type error
   1.357 +==
   1.358 +`__check_and_load_via_object` || object, attribute name
   1.359 +|| Test for attribute and load or raise type error
   1.360 +==
   1.361 +`__check_and_load_via_any` || object, attribute name
   1.362 +|| Test for attribute and load or obtain class; test for attribute and load or
   1.363 +.. raise type error
   1.364 +}}}
   1.365 +
   1.366 +==== Checked Store ====
   1.367 +
   1.368 +These instructions employ the attribute position and code for the supplied
   1.369 +attribute name, storing an attribute value.
   1.370 +
   1.371 +{{{#!table
   1.372 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.373 +==
   1.374 +`__check_and_store_via_class` || object, attribute name, value
   1.375 +|| Raise type error
   1.376 +==
   1.377 +`__check_and_store_via_object` || object, attribute name, value
   1.378 +|| Test for attribute and store value or raise type error
   1.379 +==
   1.380 +`__check_and_store_via_any` || object, attribute name, value
   1.381 +|| Test for attribute and store value or raise type error
   1.382 +}}}
   1.383 +
   1.384 +==== Testing ====
   1.385 +
   1.386 +These instructions employ the special attribute position and code for the
   1.387 +supplied type name.
   1.388 +
   1.389 +{{{#!table
   1.390 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.391 +==
   1.392 +`__test_common_instance` || object, type
   1.393 +|| Obtain class from object; test conformance to type
   1.394 +==
   1.395 +`__test_common_object` || object, type
   1.396 +|| Test conformance to type or obtain class from object and test conformance
   1.397 +.. to type
   1.398 +==
   1.399 +`__test_common_type` || object, type
   1.400 +|| Test conformance to type
   1.401 +==
   1.402 +`__test_specific_instance` || object, type
   1.403 +|| Obtain class from object; test equivalence to type
   1.404 +==
   1.405 +`__test_specific_object` || object, type
   1.406 +|| Test equivalence to type or obtain class from object and test equivalence
   1.407 +.. to type
   1.408 +==
   1.409 +`__test_specific_type` || object, type
   1.410 +|| Test equivalence to type
   1.411 +}}}
   1.412 +
   1.413 +==== Static Load ====
   1.414 +
   1.415 +These instructions obtain references to static objects, in some cases
   1.416 +employing a supplied context.
   1.417 +
   1.418 +{{{#!table
   1.419 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.420 +==
   1.421 +`__load_static_ignore` || object
   1.422 +|| Load attribute populated with object, leaving the context unset
   1.423 +==
   1.424 +`__load_static_replace` || context, object
   1.425 +|| Load attribute populated with the context and object
   1.426 +==
   1.427 +`__load_static_test` || context, object
   1.428 +|| Load attribute populated with object; test context compatibility and set
   1.429 +.. the context
   1.430 +}}}
   1.431 +
   1.432 +==== Temporary Access ====
   1.433 +
   1.434 +These instructions access temporary values retained to perform the attribute
   1.435 +access. The temporary storage index is generated during program translation.
   1.436 +
   1.437 +{{{#!table
   1.438 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.439 +==
   1.440 +`__get_context` || (temporary)
   1.441 +|| Load the context stored in the temporary storage
   1.442 +==
   1.443 +`__set_accessor` || accessor
   1.444 +|| Store the accessor temporarily
   1.445 +==
   1.446 +`__set_context` || (temporary), context
   1.447 +|| Store the context in the temporary storage
   1.448 +==
   1.449 +`__set_private_context` || context
   1.450 +|| Store the context temporarily
   1.451 +==
   1.452 +`__set_target_accessor` || accessor
   1.453 +|| Store the assignment accessor temporarily
   1.454 +}}}
   1.455 +
   1.456 +==== Context Test ====
   1.457 +
   1.458 +These instructions perform tests on the available context object. The
   1.459 +temporary storage index is generated during program translation.
   1.460 +
   1.461 +{{{#!table
   1.462 +'''Instruction''' || '''Arguments''' || '''Operations'''
   1.463 +==
   1.464 +`__test_context_revert` || (temporary), context, attribute
   1.465 +|| Test compatibility of context; revert temporary to attribute context if
   1.466 +.. incompatible
   1.467 +==
   1.468 +`__test_context_static` || (temporary), context, value
   1.469 +|| Test compatibility of context; set temporary to specified context if
   1.470 +.. compatible
   1.471 +}}}
   1.472 +
   1.473  == Deduction Products ==
   1.474  
   1.475  The deduction process should produce a complete catalogue of accessor and
   1.476 -access references that may then be consulted by the
   1.477 -[[../Translation|translation]] process needing to know the nature of any
   1.478 -operation within the program. Central to the translation process's
   1.479 -understanding of references is the '''attribute access plan''' for each
   1.480 -reference which characterises each access and provides the basis for the
   1.481 -formulation of the '''instruction plan''' used to replicate it in the final
   1.482 -program.
   1.483 +access references that may then be consulted by the [[../Translation|
   1.484 +translation]] process needing to know the nature of any operation within the
   1.485 +program. Central to the translation process's understanding of references is
   1.486 +the '''attribute access plan''' for each reference which characterises each
   1.487 +access and provides the basis for the formulation of the '''instruction
   1.488 +plan''' used to replicate it in the final program.