object | { attr1 | value } | { attr2 | value } | ...",shape=record]; + + attrB [label="attribute | { intvalue | 12345 }",shape=record]; + + attrA:value -> obj1:main; +} +}}} + +Although a value indicates a specific object of interest for an attribute, if the object is callable then additional '''context''' information may be required to call the object. Such context information is not stored in an attribute record but is instead obtained from the object itself, if appropriate. + +=== Integer Representation === + +The `intvalue` member of the attribute structure is employed instead of the `value` member to store integer values. Since `value` normally holds a pointer, and since pointers are often aligned to certain address boundaries on many modern platforms (usually four-byte boundaries on 32-bit platforms, eight-byte boundaries on 64-bit platforms, two-byte boundaries on platforms with 16-bit addressing), the lowest significant bit (bit 0) will typically be zero for a valid pointer. Consequently, by setting bit 0 to 1, other data can be stored in the remaining bits and be distinguished from pointer information. Obviously, operations on attributes first need to test whether the `value` member or the `intvalue` member is in use by testing bit 0. + +Thus, integers are transformed and stored directly within attributes, and they are therefore passed around by value. When an attribute of an integer needs to be accessed, the operation usually providing the `value` member, thus obtaining an instance under normal circumstances, instead provides the address of a common integer instance. This instance may then provide instance attributes, whose values will be the same for all integers, or class attributes through a reference to the integer (`int`) class. + +Each method provided by `int`, when called, will be given the original attribute for which the method was obtained as its context. In such methods, operations on the context via `self` will either involve the propagation of the attribute to other functions or methods or attribute accesses on `self`, yielding common instance attributes or class attributes as already described. Only native functions will attempt to interpret the attribute in a different way, decoding the representation, performing arithmetic or logical operations, and encoding the result in a new attribute. + +== Contexts and Wrappers == + +The context of an object is of significance if that object is callable. For example, an instance may permit access to a method via an attribute. Since the method will be callable, and since the method is accessed via the instance, the context of that method will be the instance. In order to retain both context and value information, a '''wrapper''' may be created. + +{{{#!graphviz +//format=svg +//transform=notugly +digraph wrappers { + node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Wrappers"]; + edge [fontsize="13.0",fontname="Helvetica",tooltip="Wrappers"]; + rankdir=TB; + + inst [label="

instance | { attr1 | reference to method } | { attr2 | value } | ...",shape=record]; + method [label="

method | ...",shape=record]; + wrapper [label="

wrapper | { __context__ | reference to instance } | { __value__ | reference to method } | ...",shape=record]; + + inst:attr1 -> method:main; + wrapper:context -> inst:main; + wrapper:value -> method:main; +} +}}} + +The context is not always the accessor of the object - in this case, the instance - because the object may already be a wrapper with its own context. + +== Objects == + +Classes, instances and modules are objects, and all of these kinds of objects provide metadata describing the type of each object, together with a collection of attributes forming the contents of such objects. + +{{{#!graphviz +//format=svg +//transform=notugly +digraph objects { + node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Objects"]; + edge [fontsize="13.0",fontname="Helvetica",tooltip="Objects"]; + rankdir=TB; + + instC [label="

instance of C | { 0 | reference to\ninstance table } | { __class__ | reference\nto C } | { a | value } | { b | value } | ...",shape=record]; + clsC [label="

class C | { class identifier | reference to\nclass table } | { __class__ | reference\nto type } | { __fn__ | instantiator\nreference } | { __args__ | reference to\nparameter table } | { f | reference\nto f } | { g | value } | ...",shape=record]; + methodF [label="

function f | { 0 | reference to\ninstance table } | { __class__ | reference\nto function } | { __fn__ | method\nreference } | { __args__ | reference to\nparameter table } | ...",shape=record]; + function [label="

class function | { class identifier | reference to\nclass table } | { __class__ | reference\nto type } | ...",shape=record]; + type [label="

class type | { class identifier | reference to\nclass table } | { __class__ | reference\nto type } | ...",shape=record]; + + instC:cls -> clsC:main; + clsC:cls -> type:main; + clsC:f -> methodF:main; + methodF:cls -> function:main; +} +}}} + +Classes are represented by structures whose members reference class attributes and class metadata (the class table), as well as incorporating invocation metadata (the `__args__` and `__fn__` special attributes). + +Instances are represented by structures whose members reference instance attributes (including `__class__` which indicates the class instantiated by a given instance) and instance metadata (the instance table), as well as incorporating invocation metadata (the `__args__` and `__fn__` special attributes). + +Functions are instances of a general function type that does not permit additional, general instance attributes. However, function instance structures may have extra members corresponding to default parameter values. Access to such extra members is performed using the minimum and maximum values provided via `__args__` and with knowledge of the number of declared instance attributes indicated by the instance table for the function type. + +Modules are represented by structures whose members reference module attributes and module metadata (the module table). + +== Special Members == + +All object representations support the following special members describing the invocation properties of each object: + +{{{#!table +`__args__` || the minimum number of arguments supported in an invocation and a reference to the parameter table for the object +== +`__fn__` || a reference to a native function containing the actual code run when calling the object +}}} + +Classes are invoked in order to create instances of each class ('''instantiation'''). Instances may support invocation by providing a `__call__` method. Functions are supported by instances of a general function class. Modules are generally not callable and will not actually provide these special members in practice. + +All object representations support information about their type: + +{{{#!table +`__class__` +|| the class of the object: instances refer to their classes, classes refer to the `type` class, functions are instances that refer to the `function` class, modules refer to the `module` class +}}} + +Certain kinds of object support other descriptive attributes: + +{{{#!table +`__name__` || the name of a class or a function +== +`__parent__` || the parent scope of a class or a function +}}} + +Objects supported by native, system-level functionality require a means of retaining information in special attributes: + +{{{#!table +`__data__` || private data manipulated at the native level +}}} + +Strings support special annotation attributes that permit their use in dynamically resolving attributes: + +{{{#!table +`__key__` || the code and position of the attribute whose name is represented by the string +}}} + +Such "key" attributes provide information that can be used to inspect an object table and to test for the presence of an attribute. With such information, the `getattr` and `hasattr` functions can be supported. + +== Attribute Tables == + +In order to provide information about the attributes supported by each object, the structure of each object will reference a table containing entries describing these supported attributes. The size of this table is declared within the table structure, and for each position in the table an entry corresponding to the same position within an actual object structure describes the nature of the attribute at that position. + +== Parameter Tables == + +In order to support argument validation and keyword arguments in invocations, a structure is referenced by `__args__` that indicates... + + * The minimum number of parameters supported by a callable + * The maximum number of parameters supported by a callable + * The size of the table describing the parameters + * A table of entries with each entry indicating the nature of a parameter (in effect, which name it uses, albeit as a generated code instead of a string) and the position of the parameter in any argument list prepared for an invocation + +Parameter tables only need to be consulted at run-time if the nature of a callable is undetermined. By supporting a uniform interface, the arguments used in an invocation can be tested against the description provided by `__args__` and the table. diff -r 0c893b6761a7 -r e08d8986f0e1 docs/wiki/Restarted --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/wiki/Restarted Tue Apr 11 21:41:22 2017 +0200 @@ -0,0 +1,282 @@ += Lichen Restarted = + +Originally, lots of work was being put in to support various Python features that are arguably superfluous. The realisation was had that a lot of effort was being made for little practical benefit by trying to support things that are, [[../Design|in the larger picture]], not that important. Consequently, Lichen was refocused on a smaller set of more useful Python features. + +This document is of historical interest only, with the [[../Design|design]] and other documents attempting to communicate the results of this restarting effort. Some obsolete information is therefore preserved below. For example, attributes hold context information in the diagrams, but context information is now held in wrappers or is maintained separately within programs. + +Objectives: + + * Individual module inspection + * No importing triggered during module inspection + * All unresolved external references are set to `` + * Hierarchical module namespaces are not exposed in programs + * Modules are independent: package hierarchies are not traversed when importing + * Nested scopes will be dropped + * If expressions and comprehensions will be dropped + * `self` is a reserved name and is optional in method parameter lists + * Unbound methods must be bound using a special function taking an instance + * Functions assigned to classes do not become unbound methods + +== Names == + +Names are locals, globals or built-ins. (Special names exist internally to support certain operations.) + +Locals inside functions are dynamic; locals outside functions are static, as are module globals. Built-ins are defined statically in the `__builtins__` package. + +== Imports == + +Imports provide access to external references. The "leaf" module in a module path is the module returned by the statement. + +Indicate that module "compiler" is accessed via compiler... +{{{#!python numbers=disable +import compiler +}}} + +Indicate that module "compiler" is accessed via comp... +{{{#!python numbers=disable +import compiler as comp +}}} + +Indicate that module "compiler.ast" is accessed via ast; module "compiler.transformer" is accessed via tr... +{{{#!python numbers=disable +import compiler.ast as ast, compiler.transformer as tr +}}} + +Import compiler.ast, access Function... +{{{#!python numbers=disable +from compiler.ast import Function +}}} + +Import compiler.ast, access Function as F... +{{{#!python numbers=disable +from compiler.ast import Function as F +}}} + +This causes some semantic differences with Python, with the most significant one being the following: + +{{{{#!table +'''Python''' || '''Lichen''' +== + + +Import compiler, import compiler.ast, set ast on compiler... +{{{#!python numbers=disable +import compiler.ast +}}} +...returning compiler + +|| + + +Import compiler.ast... +{{{#!python numbers=disable +import compiler.ast +}}} +...returning compiler.ast as ast + +}}}} + +Some statements can be rewritten to achieve the same effect: + +{{{{#!table +'''Python''' || '''Lichen''' +== + + +Import compiler, access ast as submodule... +{{{#!python numbers=disable +from compiler import ast +}}} + +|| + + +Import compiler.ast... +{{{#!python numbers=disable +import compiler.ast +}}} +...returning compiler.ast as ast + +}}}} + +Other kinds of import are not directly possible with Lichen. For example: + +Import all names from compiler.ast... +{{{#!python numbers=disable +from compiler.ast import * +}}} + +Some notes: + + * Names not defined in a module and not declared in import statements are unresolved + * Modules are identified during inspection but are not loaded + * Instead, modules are added to a list and are imported later + * Names imported from modules are set to `` (since the contents of modules will not generally be known) + * Names are resolved in a later activity + +== Self == + +In Python: + + * The `self` name provides access to the instance associated with a method + * The instance is supplied by a "context", initialised when a method is obtained from an instance (or through other attribute accesses) + * Upon invocation, any instance context must be assigned to the `self` parameter, provided the callable is a method + * Meanwhile, any non-instance context is not assigned to the `self` parameter, which should be provided explicitly for class-accessed methods + * Plain functions never expose `self` or have `self` initialised, even if they have been assigned to an instance + +Apart from tests for the nature of the context and the callable, the argument list is effectively variable. + +With `self` as a ubiquitous, hidden parameter: + + * The `self` name still provides access to the instance associated with a method + * The instance is still supplied by a "context", initialised when a method is obtained from an instance (or through other attribute accesses) + * Upon invocation, `self` is included in the argument list regardless of the nature of the callable + * Class-accessed methods would have their class as context, following from the above, but `self` may not refer to a class: it must be an instance + * To combine class-accessed methods with instance contexts, a special function is employed + +The argument list for each callable thus remains static, at a cost of allocating an extra argument that may not be used. (Various calling conventions for certain processor architectures employ potentially unused registers, anyway.) Note that a callable may support defaults, however, and thus any argument list may need extending to include default values for parameters without corresponding arguments. + +{{{{#!table +'''Python''' || '''Without self''' +== + + +{{{#!python numbers=disable +inst.method(x, y, z) +# -> inst.method(inst, x, y, z) + +def method(self, a, b, c): + # self = inst; a = x; b = y; c = z +}}} + +|| + + +{{{#!python numbers=disable +inst.method(x, y, z) +# -> inst.method(inst, x, y, z) + +def method(a, b, c): + # self = inst; a = x; b = y; c = z +}}} + +== + + +{{{#!python numbers=disable +cls.method(self, x, y, z) + +def method(self, a, b, c): + # parameters = arguments +}}} + +|| + + +{{{#!python numbers=disable +f = get_using(cls.method, self) +# context of f = self; value of f = cls.method +f(x, y, z) +# -> f(context of f, x, y, z) + +def method(a, b, c): + # self = context of f = self; a = x; b = y; c = z +}}} + +}}}} + +To avoid usage of `self` in undefined ways, only methods are able to use `self` and are not allowed to redefine it. Consequently, when invoking a callable, the context is set (where the callable is unknown until run-time; it is not set if compile-time knowledge indicates that it is not needed), and in situations where `self` is not permitted, the context is therefore safely ignored. Meanwhile, methods are always supplied with a context compatible with `self`. + +|| '''Callable''' || '''self''' || '''Remarks''' || +|| Class || context || context discarded and replaced by allocated instance || +|| Function || null || `self` not permitted, context ignored || +|| Function (stored on class) || class as context || `self` not permitted, context ignored || +|| Function (stored on instance) || instance as context || `self` not permitted, context ignored || +|| Instance || instance as context || `self` set to instance || +|| Method (via class) || class as context || method not called (see "unbound methods") || +|| Method (via instance) || instance as context || `self` set to instance || + +Note that the treatment of functions stored on classes differs from Python. In Python, such functions would become unbound methods (see below) and would employ their first parameter as an effective `self` parameter (regardless of name). + +== Unbound Methods == + +Since methods acquired directly from classes ("unbound methods" in Python) are meant to be combined with an instance as context (using the `get_using` function), they must be uncallable until combined with the appropriate context, yet the same methods when acquired via instances ("bound methods" in Python) must be immediately callable. + +To support the two different states of methods, the principal structure of a class has attributes referencing uncallable versions of its methods. Meanwhile, such uncallable methods reference callable versions and when instances are employed to access the class attributes, it is these callable versions that are retrieved. For example: + +{{{#!graphviz +//format=svg +//transform=notugly +digraph structures { + node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Instance and class structures"]; + edge [fontsize="13.0",fontname="Helvetica",tooltip="Instance and class structures"]; + rankdir=TB; + + instanceC [label="

instance of C |{ context of a | value of a }|{context of b | value of b }",shape=record]; + classC [label="

class C |{ context of m | value of m }|{ context of n | value of n}",shape=record]; + callables [label=" m\ncallable | n\ncallable",shape=record]; + uncallables [label=" m\nuncallable | n\nuncallable",shape=record]; + + instanceC:main -> classC:main; + classC:m -> uncallables:m [label="C.m",style=dashed]; + classC:n -> uncallables:n [label="C.n",style=dashed]; + uncallables:m -> callables:m [label="get_using(C.m, instance)",style=dashed]; + uncallables:n -> callables:n [label="get_using(C.n, instance)",style=dashed]; +} +}}} + +The precise structure usage is as follows: + +{{{#!graphviz +//format=svg +//transform=notugly +digraph methods { + node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Method structures"]; + edge [fontsize="13.0",fontname="Helvetica",tooltip="Method structures"]; + rankdir=TB; + + classC [label="

class C | { context of m | uncallable for m } | ...",shape=record]; + uncallableattr [label="attr | { C | uncallable for m }",shape=record]; + callableattr [label="attr | { instance | callable for m }",shape=record]; + uncallable [label="

uncallable for m |{ __fn__ | bound method reference | unbound method routine }|{ __args__ | minimum #parameters | parameter table reference }",shape=record]; + callable [label="
callable for m |{ __fn__ | 0 | bound method routine }|{ __args__ | minimum #parameters | parameter table reference }",shape=record]; + ptable [label="
parameter table for m | ...",shape=record]; + + classC:mvalue -> uncallableattr [label="C.m",style=dashed]; + classC:mvalue -> uncallable:main; + uncallableattr:value -> uncallable:main; + uncallableattr -> callableattr [label="get_using(C.m, instance)",style=dashed]; + uncallable:b -> callable:main; + callableattr:value -> callable:main; + uncallable:ptable -> ptable:main; + callable:ptable -> ptable:main; +} +}}} + +Callable methods provide a reference to a callable routine in its special callable member, just as functions and classes do. Uncallable methods populate the callable member with a reference to an error routine. Thus, any attempt to call an uncallable method would cause the error routine to be invoked. In addition, uncallable methods reference the corresponding callable methods so that the callable methods can be found and referenced. + +|| '''Accessor''' || '''Provider''' || '''Attribute''' || '''Context''' || '''Summary''' || +||<|4> Instance ||<|4> Instance || Function || ''not used'' ||<|6> Preserve context || +|| Bound method || Original instance || +|| Unbound method || Providing class || +|| Other || Same as value || +||<|4> Instance ||<|4> Class || Function || ''not used'' || +|| Bound method || Original instance || +|| Unbound method || Accessing instance, if compatible || Test and replace context || +|| Other || Same as value ||<|5> Preserve context || +||<|4> Class ||<|4> Class || Function || ''not used'' || +|| Bound method || Original instance || +|| Unbound method || Providing class || +|| Other || Same as value || + +When obtaining an unbound method from an instance attribute, the context of the method attribute is provided. Indeed, the context is always preserved when accessing instance attributes. + +When obtaining an unbound method from a class attribute via an instance, the context of the method attribute is tested against the accessing instance. If compatible, an attribute is copied containing the instance as context and a callable method reference as value. + +When obtaining an unbound method from a class attribute, the context of the method attribute is provided. Indeed, the context is always preserved when accessing class attributes directly. + +When combining an unbound method obtained from a class with an instance using `get_using`, the context of the method attribute is tested against the supplied instance. If compatible, an attribute is copied containing the instance as context and a callable method reference as value. + +=== Functions as Unbound Methods === + +Functions not defined within classes could be treated as unbound methods if they were to employ `self` (thus indicating that they are intended as methods). Such functions would then be recorded as uncallable in the module namespace, needing to be explicitly bound to a class using a special function. However, there appears to be limited utility in defining functions in this way, instead of defining them directly as methods, or instead of merely using such generic functions from existing methods. diff -r 0c893b6761a7 -r e08d8986f0e1 docs/wiki/Structure --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/wiki/Structure Tue Apr 11 21:41:22 2017 +0200 @@ -0,0 +1,135 @@ += Program Structure = + +A program consists of a number of '''modules''' with each module providing its own namespace. Modules can be organised within '''packages''' which define a hierarchical relationship between them. However, the relationship between modules is not automatically exposed within the program: it is more appropriate to consider modules as independent entities that have a particular naming scheme. + +Within each module a hierarchy of namespaces is provided by '''classes''', with each class potentially containing other classes, and so on. Also appearing within modules and classes are '''functions''', with those appearing within classes being regarded as '''methods'''. + +Function namespaces are considered separately from module and class namespaces and are not considered part of the general namespace hierarchy, instead merely appearing as objects at the edges of that hierarchy. Functions may also be defined within functions, and such inner functions will be referenced within their parent functions, but no hierarchical relationship will exist between their namespaces. + +Thus, a program provides a static namespace hierarchy consisting of modules containing classes (containing other classes, and so on) plus functions. Objects residing within namespaces are accessed via '''attributes''' of those namespaces. + +{{{{#!table +{{{#!graphviz +//format=svg +//transform=notugly +digraph program { + node [shape=box,fontsize="13.0",fontname="Helvetica",tooltip="Program structure"]; + edge [tooltip="Program structure"]; + rankdir=LR; + + program [label="program",shape=folder,style=filled,fillcolor=cyan]; + + subgraph { + rank=same; + moduleM [label="module M",style=filled,fillcolor=gold]; + moduleN [label="module N\n(package)",style=filled,fillcolor=gold]; + } + + subgraph { + rank=same; + classA [label="class A"]; + moduleNP [label="module N.P",style=filled,fillcolor=gold]; + } + + subgraph { + rank=same; + functionF [label="function f",shape=ellipse]; + functionG [label="function g",shape=ellipse]; + classB [label="class B"]; + classC [label="class C"]; + } + + subgraph { + rank=same; + functionJ [label="function j",shape=ellipse]; + functionH [label="function h",shape=ellipse]; + functionK [label="function k",shape=ellipse]; + } + + program -> moduleM; + program -> moduleN; + + moduleM -> classA; + moduleN -> moduleNP; + moduleNP -> classC; + + classA -> functionF; + classA -> functionG; + classA -> classB; + classB -> functionH; + classC -> functionK; + + functionG -> functionJ [style=dashed]; +} +}}} +|| +{{{#!python numbers=disable +# module M + +class A: + def f(...): pass + + def g(...): + def j(...): pass + + class B: + def h(...): pass + +# module N + +... + +# module N.P + +class C: + def k(...): pass +}}} +}}}} + +== Referencing the Structure == + +Each part of the structure is catalogued using an '''object path''', indicating its location in the structure hierarchy, and a reference indicating its nature and origin. For example: + +|| '''Object Path''' || '''Reference''' || '''Explanation''' || +|| `M.A` || `:M.A` || The definition of class `A` in module `M` || +|| `O.A` || `:M.A` || A reference to `M.A`, a class || +|| `N.P.C.k` || `:N.P.C.k` || The definition of method `k` in class `C` of module `N.P` || +|| `O.k` || `:N.P.C.k` || A reference to `N.P.C.k`, a function || +|| `O.values` || `:__builtins__.list.list` || An object identified as an instance of class `__builtins__.list.list` || +|| `__main__.M` || `:M` || A reference to module `M` || +|| `__main__.counter` || `` || An undetermined object called `counter` in the `__main__` module || + +The reference therefore expresses the '''kind''' of object (class, function, instance, module or undetermined variable), possibly accompanied by an object type, and also possibly accompanied by an alias indicating where the reference was obtained. + +== Classes == + +Classes are regarded as statically-defined objects, meaning that they are only evaluated once and must not be defined within conditional sections or within functions. Base classes must be expressed using readily-identifiable class names, since any potential ambiguity or uncertainty with the identity of base classes could result in a class inheritance hierarchy that is effectively dynamic. + +When '''instantiated''', classes provide '''instances''' that provide the attributes of each class's namespace plus any '''inherited''' attributes from base classes that would not be provided by the class itself. In addition, instances provide their own instance attributes. + +== Functions == + +Functions are regarded as statically-defined objects, but they may be defined either with names within other named functions or as '''lambdas''' (functions without names) within named functions or other lambdas. Thus, unlike classes, functions may be defined once but replicated many times, each time with different accompanying state information. Such state information needs to be provided via default parameters: it is not detected and propagated automatically. Closures are not supported: any state from enclosing scopes must be supplied at the point of definition of a function; it is not acquired from outer functions by name. + +{{{#!python numbers=disable +def outer(a): + b = 2 + def inner(c, a=a, b=b): + # a initialised using default from outer scope + # b also initialised using default from outer scope + return a, b, c + b = 4 + +outer(1)(3) # returns (1, 2, 3) not (1, 4, 3) +}}} + +=== Lambdas === + +Lambdas are given special names for the purposes of identification within the program structure, being named relative to the scope in which they are defined. For example, the first lambda appearing within module `N` would have an object path of `N.$l0`, and a subsequent lambda within the same scope would have an object path of `N.$l1`. Lambdas may appear within classes and functions, including lambdas themselves. For example: + +{{{#!python numbers=disable +def f(x): + return lambda y, x=x: lambda z, x=x, y=y: (x, y, z) +}}} + +Here, within a module `M`, the outer lambda would have the object path `M.f.$l0` whereas the inner lambda would have the object path `M.f.$l0.$l0`. diff -r 0c893b6761a7 -r e08d8986f0e1 docs/wiki/ToDo --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/wiki/ToDo Tue Apr 11 21:41:22 2017 +0200 @@ -0,0 +1,57 @@ += To Do = + +As always with software, there are still many things that need to be done. Here is a list of a few of them. + +<> + +== Finish the Core Standard Library == + +Lichen provides its own core standard library featuring the [[../Builtins|built-ins]] and other essential modules, with only a small amount of native code supporting implementations written in the Lichen language. + +=== Numeric Types === + +Support all the numeric types. Currently, only `int` is supported, but `float` merely requires some native code handling operations and testing for exception conditions. A representation for `long` needs to be determined, and `complex` probably just needs some methods implementing. + +Support promotion between some of the numeric types. Currently, `int` values that overflow raise `OverflowError`, as was done in Python before automatic promotion to `long`. + +=== String Types === + +The remaining methods need defining for byte and Unicode strings. Some methods are more complicated than others, particularly where some interpretation of the content is required: identification of case, whitespace, punctuation, and so on. + +Some Unicode operations could be implemented in the Lichen language, not in C. + +=== Sequence and Mapping Types === + +Various methods still need defining in the dictionary, list, tuple and set classes to provide parity with Python. + +=== Hashing === + +Unlike Python, the hashing approaches currently employed are not well-tuned. One important difference between Lichen and Python is that the former does not use hashtables as a general structure for objects, meaning that certain desirable criteria for Python hashtables (randomising certain aspects of their behaviour to prevent the exploitation of poorly performing cases) are less important for Lichen. + +== Provide Peripheral Library Support == + +The Python standard library offers support for things like networking which require a degree of system-level integration. The Lichen libraries could be expanded to offer coverage of many of the same APIs. + +=== Versatile Native Libraries === + +Currently, the native functionality already exposes things like file descriptors, and a relatively simple versatile interface might be sufficient for many future libraries. + +== Incremental Compilation == + +To some extent, the toolchain supports the caching of inspection results with selective regeneration upon changes to source files. However, deduction and subsequent activities are performed in their entirety every time. + +=== Preserving Structures === + +Where source files have changed, it may be possible that the structure details remain the same. Consequently, it is unnecessary to regenerate structures, and it is only necessary to determine the nature of modified program operations. + +Where structures have changed, certain existing operations may need to be updated because such operations may no longer support certain types of object or may support additional types. Meanwhile, changes to structures may be compatible with existing structure layouts and not require such layouts to be recomputed. + +== Exploit Deductions Further == + +So far, deductions have been used to inform the translation of certain operations and to identify situations where suitable operations cannot be generated. However, no attempt has been made to broaden the application of such information. + +=== Parameter Type Checking === + +Elementary knowledge about function parameters is currently available when inspecting a program, but the deducer does not attempt to propagate such information to likely callers of such functions. Such propagation in its simplest form would merely use the list of potential targets for each invocation, obtain the parameter types from each target, compare these types to any readily-comparable argument (such as a name), and then determine which targets may still be invoked successfully, potentially imposing restrictions on the suitable targets as a result. + +Such propagation activities can be time-consuming because they can lead to iterative whole-program propagation occurring. Consider the restriction of an invocation target: this may indicate a restriction on a name that provides such a target, thus affecting the function parameter providing the name; such a restriction could then be propagated to callers of that function, initiating further refinement of other invocations, and so on. diff -r 0c893b6761a7 -r e08d8986f0e1 docs/wiki/Toolchain --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/wiki/Toolchain Tue Apr 11 21:41:22 2017 +0200 @@ -0,0 +1,53 @@ += Toolchain = + +The toolchain implements the process of analysing Lichen source files, compiling information about the structures and routines expressed in each program, and generating output for further processing that can produce an executable program. + +<> + +== Compiling Programs == + +The principal interface to the toolchain is the `lplc` command, run on source files as in the following example: + +{{{ +lplc tests/unicode.py +}}} + +There is no need to specify all the files that might be required by the complete program. Instead, the toolchain identifies files in the program by searching its module search path. This can be configured using the `LICHENPATH` environment variable and the `-E` option. + +Various [[../Prerequisites|prerequisites]] are needed for the toolchain to work properly. By specifying the `-c` option, the specified program will be translated to a C programming language representation but not built, avoiding the need for some development tools to be installed if this is desirable. + +The default output file from a successful compilation is a file called `_main`, but this can be overridden using the `-o` option. For example: + +{{{ +lplc -o unicode tests/unicode.py +}}} + +The complete set of options can be viewed by specifying the `--help` option, and a manual page is also provided in the `docs` directory of the source distribution: + +{{{ +man -l docs/lplc.1 +}}} + +This page may already be installed if the software was provided as a package as part of an operating system distribution: + +{{{ +man lplc +}}} + +== Toolchain Implementation == + +The toolchain itself is currently written in Python, but it is envisaged that it will eventually be written in the Lichen language, hopefully needing only minor modifications so that it may be able to accept its own source files as input and ultimately produce a representation of itself as an executable program. Since the Lichen language is based on Python, it is convenient to use existing Python implementations to access libraries that support the parsing of Python source files into useful representations. + +The Python standard library provides two particularly useful modules or packages of relevance: the `compiler` package and the `parser` module; `parser` is employed by `compiler` to decode source text, whereas `compiler` takes the concrete syntax tree representation from `parser` and produces an abstract syntax tree (AST) which is particularly helpful to software of the nature described here. (Contrary to impressions that [[http://eli.thegreenplace.net/2009/11/28/python-internals-working-with-python-asts/|some articles]] might give, the `ast` module available in Python 2.5 and later was not the first module to offer AST representations of Python programs in Python, nor was it even the first such module in the standard library.) + +However, it is not desirable to have a dependency on a Python implementation, which the `parser` module effectively is (as would the `ast` module also be if it were used here), with it typically being implemented as an extension module in a non-Python language (in C for CPython, in Java for Jython, and so on). Fortunately, the !PyPy project implemented their own parsing module, `pyparser`, that is intended to be used within the !PyPy environment together with their own `ast` equivalent, but it has been possible to rework `pyparser` to produce representations that are compatible with the `compiler` package, itself being modified in various ways to achieve compatibility (and also to provide various other conveniences). + +== Program Analysis == + +With the means of inspecting source files available through a `compiler` package producing a usable representation of each file, it becomes possible to identify the different elements in each file and to collect information that may be put to use later. But before any files are inspected, it must be determined ''which'' files are to be inspected, these comprising the complete program to be analysed. + +Both Lichen and Python support the notion of a main source file (sometimes called the "script" file or the main module or `__main__`) and of imported modules and packages. The complete set of modules employed in a program is defined as those imported by the main module, then those imported by those modules, and so on. Thus, the complete set is not known without inspecting part of the program, and this set must be built incrementally until no new modules are encountered. + +Where Lichen and Python differ is in the handling of [[../Imports|imports]] themselves. Python [[https://docs.python.org/3/reference/import.html|employs]] an intricate mechanism that searches for modules and packages, loading modules encountered when descending into packages to retrieve specific modules. In contrast, Lichen only imports the modules that are explicitly mentioned in programs. Thus, a Lichen program will not accumulate potentially large numbers of superfluous modules. + +With a given module identified as being part of a program, the module will then be [[../Inspection|inspected]] for the purposes of gathering useful information. Since the primary objectives are to characterise the structure of the objects in a program and to determine how such objects are used, certain kinds of program constructs will be inspected more closely than others. Note that this initial inspection activity is not concerned with the translation of program operations to other forms: such [[../Translation|translation]] will occur later; this initial inspection is purely concerned with obtaining enough information to inform such later activities, with the original program being revisited to provide the necessary detail required to translate it. diff -r 0c893b6761a7 -r e08d8986f0e1 docs/wiki/Translation --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/wiki/Translation Tue Apr 11 21:41:22 2017 +0200 @@ -0,0 +1,164 @@ += Translating Programs = + +The Lichen toolchain currently targets the C programming language, generating programs that are then compiled using existing C compilers. The process of translation involves the optimisation and generation of program structures, and the translation of Lichen language constructs into equivalent C language constructs. + +<> + +== Attribute Access Plans == + +During [[../Inspection|inspection]], each attribute access is associated with a unique location and its details stored. During [[../Deduction|deduction]], such accesses are resolved and characterised. During [[../Optimisation|optimisation]], such accesses are encoded as '''instruction plans''' indicating the operations or instructions required to achieve the access. During translation, these instruction plans are generated as part of the final program. + +== Structure Optimisation == + +All object structures need to support the attributes defined for them, and although it may be possible to determine the identity of attributes in advance of a program being run, there generally remains a need to provide mechanisms to determine the nature of an object at run-time and to access its attributes dynamically. To achieve this, an [[../Optimisation|optimisation]] process catalogues the presence of each attribute name on all program objects, then deciding upon a position for the structure member corresponding to that attribute name in all objects. + +== Structure Generation == + +Each program consists of a number of structures providing the program's objects and defining classes, functions, modules and any predefined instances. + +=== Attribute Representation === + +Attributes most typically provide references to objects within a certain optional context. Since attributes are employed to encode various other kinds of information, the data structure may be interpreted in other ways within suitably controlled environments. For example, the `__data__` attribute found on instances of certain built-in classes will encode references to other kinds of information that are used within native functions. + +=== Object Representation === + +Objects provide collections of attributes, and the object representation is meant to support efficient computed access to attributes whilst also allowing a reasonably efficient means of testing and accessing attributes at run-time. + +=== Structure Constants === + +For clarity, several classes of symbolic constant are defined in the translated program to help define structures or to refer to structure members. + +|| '''Constant Class''' || '''Purpose''' || '''Example''' || '''Application''' || +|| `csize` || Indicates the number of attributes in a class || `__csize___builtins___list_list` ||<|3> Structure definition || +|| `isize` || Indicates the number of attributes in an instance || `__isize___builtins___list_list` || +|| `msize` || Indicates the number of attributes in a module || `__msize___builtins___list` || +|| `pminsize` || Indicates the minimum number of parameters expected by a callable || `__pminsize___builtins___list_list_append` ||<|2> Invocation || +|| `pmaxsize` || Indicates the maximum number of parameters expected by a callable || `__pmaxsize___builtins___list_list_append` || +|| `pcode` || Assigns a code to a particular parameter name || `__pcode_value` ||<|2> Keyword argument positioning || +|| `ppos` || Indicates the table position used by a particular parameter name || `__ppos_value` || +|| `code` || Assigns a code to a particular attribute name || `__code_value` ||<|2> Attribute access || +|| `pos` || Indicates the table position used by a particular attribute name || `__pos_value` || + +Such constants are encoded using helper functions, producing names resembling those above that are intended to be distinct and not to conflict with other defined names in the final program. + +=== Instance Structures === + +Like all program objects, instances are defined in C according to a generic structure, meaning that all instances have the same generic members from the perspective of a C program. However, specific structures are defined for each class in order to conveniently describe the dimensions of instances of that class. For example, for the built-in list class, a declaration resembling the following is issued: + +{{{ +typedef struct { + const __table * table; + unsigned int pos; + __attr attrs[__isize___builtins___list_list___init__]; +} __obj___builtins___list_list___init__; +}}} + +== Program Translation == + +=== Useful C Language Features === + +The translated code relies on the availability of certain useful features of C, some of them supported only in modern compilers: + + * Array and structure literals: these are used to define values within expressions that would otherwise require separate definition; invocation arguments are defined using inline expressions and the `__ARGS` macro (for unknown invocation targets and for keyword arguments) + * [[https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html#Variadic-Macros|Variadic macros]]: such macros permit variable numbers of arguments, thus making the `__ARGS` macro possible + * [[WikiPedia:Comma operator]] sequences: these are used to construct instruction sequences within expressions, providing a mechanism for formulating attribute accesses + +=== Function Naming === + +A naming scheme is applied to functions defined in the final C program to support different kinds of callables present in the original program. + +|| '''Name Class''' || '''Purpose''' || '''Example''' || +|| `fn` || Indicates a plain function || `__fn___builtins___str_str` || +|| `main` || Indicates a module main program || `__main_sys` || +|| `new` || Indicates a class instantiator || `__new___builtins___list_list` || +|| `newliteral` || Provides an instantiator for literals mentioned in programs || `__newliteral___builtins___list_list` || + +=== Generic Program Functionality === + +Given the representation of the fundamental program objects, a suite of generic operations is provided to support the activities necessary to inspect and update program data. Such operations are largely concerned with generic object and attribute representations and are practically identical from program to program. + +For example, an attribute provided by an object can be accessed in several different ways depending on the information known about the object when the program is translated. Consequently, a suite of attribute access operations is provided to support each different scenario: + +||<-2|2> ||<-2> '''Attribute provider''' || +|| '''Class''' || '''Instance''' || +||<|3> '''Accessor''' || '''Class''' || `load_via_object` || || +|| '''Instance''' || `load_via_class` || `load_via_object` || +|| '''Class or instance''' || `get_class_and_load` || `check_and_load_via_any` || + +=== Specific Program Functionality === + +Since objects at the program level have their layouts [[../Optimisation|optimised]], and since these layouts may differ from program to program, a suite of specific operations is provided to support a range of activities within programs, such operations being configured with program-specific information in order to do the right thing within a given program. + +|| '''Function''' || '''Purpose''' || +|| `__invoke` || A generic invocation function that populates the argument array and obtains the appropriate target || +|| `__new` || Creates a new object, setting the `__class__` attribute to the indicated class identity || +|| `__BOOL` || Tests the identity of an attribute value against the `True` constant's address || +|| `__GETDEFAULT` || Obtains a function default from additional members of a function instance beyond the core members || +|| `__SETDEFAULT` || Updates a function default from additional members of a function instance beyond the core members || + +=== Module Files === + +Each program module is defined in its own file in the translated program. Since C has no notion of general module-level code, a special main function is generated for each module to perform the operations defined at the module level in the original program. These main functions are called in turn by the principal `main` function of the final C program, and the order of invocation is defined by the module initialisation ordering established when resolving inter-module dependencies. + +=== Statement Translation === + +Statements in the original program are generally translated to statements in the final C program. During inspection and translation, certain constructs are transformed to produce the operations necessary to implement such constructs. For instance, operators need to be rewritten as function invocations, and thus the form of the original program changes before it is translated to C. + +When translating certain operations that may appear within a statement, a sequence of instructions is generated, and such instructions must be performed in turn. Fortunately, C supports a wide variety of operations - such as assignments - within expressions, and it also provides the comma operator which permits sequences of operations to be performed in order and to yield a result that can then be used in the context of an expression. Such sequences of operations are employed extensively to realise attribute access instruction plans. + +=== Name References === + +Names can be translated in different ways for the final C program. Function locals and parameters correspond directly to locals in C functions. Module-level globals and class-level locals are translated to structure accesses. However, temporary names that are used in sequence assignment are translated to C function locals, either in functions corresponding to their equivalents in the original program, or in module initialisation functions corresponding to the module scope in the original program. + +Certain special names that are formulated during [[../Inspection|inspection]] are converted to constant or static references. + +=== Attribute Accesses === + +Each attribute access is associated with a particular access location, corresponding to an operation occurring in the original program identified during inspection. This location can be used as a key to access a [[#Attribute_Access_Plans|plan]] that describes how the access may be realised in the final program. Since most of the work computing the nature of the access is done during the preceding deduction and optimisation activities, what remains is mostly the emission of the plan into the generated program text with some substitutions performed. + +=== Invocations === + +Each invocation involves an object whose identity may or may not be known at compile-time, plus a collection of arguments. The translation process is concerned with obtaining a target to be invoked in the generated program, populating an argument array appropriately for the target, and providing the means of invocation. + +Where the identity of the object is not known at all, the information provided is effectively passed on to the special `__invoke` function which is then required to do all the work at run-time. However, one of the goals of analysing and compiling the program is to avoid doing such work at run-time and to take advantage of those cases where the identity of the object can be determined. + +Thus, where the identity of the called object is known, details of the object's signature - its parameters and their positions - are used to populate the argument array and to determine whether this can be done successfully. Some callables require a context to be provided, and knowledge about the callable can be used to obtain or omit such a context from the arguments. + +Finally, the invocation target must be obtained. Where some knowledge of the identity of the object is available, it may be sufficient to access the special `__fn__` member directly (potentially testing for its presence if this is not certain) and to call the appropriate function with the assembled argument array. Where a definite identity is available, the actual function itself may be named and thus called with the arguments. Such operations are mere fragments of the total work performed by the `__invoke` function in the least optimal case. + +=== Assignments === + +Assignments of objects to names occur for the following kinds of statements: assignments, definition statements (`class` and `def`), import statements (`from` and `import`). + +=== Guards === + +Guards are identified during [[../Deduction|deduction]] as being necessary to uphold deductions about the nature of objects referenced via names that may be undermined at run-time by potentially erroneous program behaviour. + +=== Exceptions === + +The C programming language does not support exceptions in a form supported by more modern programming languages. Consequently, lower-level mechanisms need to be employed to reproduce the semantics of the `try` statement, its `except` and `finally` clauses, and the `raise` statement, as well as considering the effect of exceptions on the `return` statement. + +Fortunately, some consideration has been given to this topic before. The [[http://www.nicemice.net/cexcept/|cexcept]] library - really a collection of convenience macros - provides a way of expressing exception constructs in a natural way in C while translating those constructs to usage of the `setjmp` and `longjmp` functions. Although direct usage of such functions could be generated during program translation, for convenience and to focus on other implementation concerns, it was decided to employ the cexcept macros and to build any additional functionality in terms of their usage. + +A structure is defined to hold exception-related information: + +{{{ +typedef struct +{ + __attr arg; + int raising; + int raising_else; + int completing; +} __exc; +}}} + +Here, the `arg` member holds a raised exception object reference. Meanwhile, the remaining members interact with language constructs as follows: + +|| '''Member''' || '''Description''' || '''Output Program Operation''' || +|| `raising` || Indicates an exception that has been raised and not yet handled || `__Raise` || +|| `raising_else` || Indicates an exception that must be re-raised because it occurred in an `else` clause || `__RaiseElse` || +|| `completing` || Indicates the completion of, or return from, a `try` clause requiring entry into a `finally` clause || `__Complete` and `__Return` || + +=== Memory Allocation and Garbage Collection === + +To avoid having to write a garbage collector, the [[http://www.hboehm.info/gc/|Boehm-Demers-Weiser garbage collector]] is employed by programs to allocate and free memory needed for its objects.