Previous Home Contents Next

Chapter 10: Post facto extensions

10.1 Extending types

10.2 Extending functions

10.3 Extending the base Aldor library

10.4 Extending the AXIOM library

One of the real problems in reusing code is how to use programs from independently developed libraries at the same time.

Every library has assumptions about the basic behaviour of the values it uses. To use values created by functions of one library as input to functions of a second library, it is usually necessary to convert the values to types derived from the second library.

As the number of libraries used by an application increases, the conversion problem becomes more significant. For example, say a library defines a concept of "FancyOutput", of which the basic Integer type could be an instance, if only it supported a few extra operations. The way this would be handled in other languages would be to derive a new type from Integer, say "FancyOutputInteger", and to use fancy integers in the program.

Now suppose we wish to use a library for differential operators, which defines a concept of "DifferentialRing". Now the integers would be a suitable instance, if only they provided a differentiation operator. It is a trivial matter to supply a differentiation operator for the set of integers: it would just return 0. At this point we end up with the new type "DifferentiableFancyOutputInteger" which may now be used in place of "Integer" when using the differential operator library at the same time as fancy output.

Aside from being ugly, this leads to a second problem: Each library may refer to the original type Integer, or its own derived version of it, in particular situations, and the DifferentiableFancyIntegers will need to be converted to FancyIntegers or Integers and vice versa.

This problem is acute when both libraries use the same base type, String or Window for instance, with different sets of operations.

This problem is particularly acute in certain applications. In mathematics, for example, certain basic sets are simple instances of very many abstract concepts. It is impossible for the Aldor library to anticipate all the mathematical contexts in which the type Integer may be expected to perform.

The way Aldor solves the problem just described is to allow programs to supply enhancements to already existing types via post facto extensions.



10.1 : Extending types

If T is a type-valued constant, then its meaning may be extended with a definition of the form:

Here C is a new category to which T will now belong and D is a package providing implementations for the newly required exports. The new operations cannot see the internal representation of T.

Taking the earlier example, the type Integer can made to satisfy the new categories FancyOutput and DifferentialRing by providing appropriate extensions:

then these extensions may be used, independently or together,

Extensions are made visible in the same manner as other definitions: by importing the package which provides them. This allows programs using extensions to be statically checked and more heavily optimized.

Extensions may be private to a particular application, or be exported by a library. In the case where a library provides an extension, the clients of the library see the extension applied to the type.

Within a given context, a type-valued constant has as its type the Join of the categories of the original value all the extensions. Its value is obtained by add-ing the extensions to the original value.

If two extensions have intersecting categories, then they may not be imported in the same scope. The extensions might, however, be combined explicitly. The current implementation does not check for this error.



10.2 : Extending functions

In typical Aldor applications many of the types are provided by functions, so an effective extension mechanism must provide some way to extend these types as well.

One might imagine a solution which took a particular function result, say List(Integer) and modified it. The problem with this is that while that one list type would be extended, the other list types would not be. It is really the meaning of List which should be extended.

To extend the meaning of a function-valued constant in Aldor one writes:

where ``fdef'' has the from of a definition of the function being extended. For example:

Any form of function definition is allowed, e.g.:

Function extensions are meaningful when the argument and result types of the extension are compatible with the argument and result types of the original meaning.

For this first implementation of the language, the extension argument types are compatible if they are the same as the argument types of the orginal function. (Ultimately, the compatibility of argument types is intended to be that they have a shared supertype.)

Corresponding result types are compatible if they are the same or both are subtypes of the same type. Additionally, the (base) type must have an appropriate method to combine values. At present only functions and types provide a combination method.

In practice this means that types, or functions producing types, or functions producing functions producing types, etc. may be extended.

Type values are combined by add and their types are combined with Join. Function values are combined by producing a new function which runs all of them and combines the result (recursively, if necessary).



10.3 : Extending the base Aldor library

The base Aldor library builds many of its types in layers, using extend. For instance, it extends Boolean, Generator(S) and Tuple(S), which are language-defined, and creates Integer and TextWriter in stages. These examples may be found in the "libaldor" subdirectory of the Aldor "samples" directory. (Please consult your systems administrator to determine the location of this directory.)

An application which introduces a new concept can provide a file to extend an existing library to support the new concept.

Suppose, for instance, that an application needed to determine how much dynamically allocated memory was used by data structures. Then it could extend the Aldor library with a file which began with code resembling that in figure 10.1

With this, it would now be possible to ask about the sizes of values belonging to the types "Integer", "List(Integer)", and so on.



10.4 : Extending the AXIOM library

The AXIOM library bindings provided with Aldor also make significant use of extensions. The types, as provided by the AXIOM library, do not provide the operations necessary to participate gracefully in Aldor programs.

For example, the Integer type does not have an operation "integer" so it could not use integer-style literals; the List constructor does not provide a generator function, so iteration over lists would be impossible.

So, in order to allow Aldor to be a suitable vehicle to extend the AXIOM library, we have provided a set of post facto extensions as part of the AXIOM library interface. When a program uses #include "axiom" it sees the extended AXIOM types, dressed for use with Aldor.

These extensions also serve a second purpose: to allow the Aldor compiler to do better optimization for programs based on the AXIOM library. By providing redundant Aldor implementations for efficiency-critical functions, we make these operations available for inter-file optimization.

The part of the axextend.as file which provides the extension for the Vector constructor is shown in figure 10.2. We present this, not as the most beautiful program in the world, but rather as a real-life example of using extensions to solve a problem.



Figure 10.1: Post facto extensions of the Base Aldor library.

#include "aldor"

+++ ''ByteSize'' provides a meaure of dynamically allocated storage.
define ByteSize: Category == with {
        bytesize: % -> SingleInteger;
}

extend Boolean: ByteSize with { } == add {
        bytesize(a: %): SingleInteger == 0;
}

extend Integer: ByteSize with { } == add {
        bytesize(n: %): SingleInteger ==
                if single? n then 0 else (length n) quo 8 + 12;
}

extend List(S: Type): with {
        if S has ByteSize then ByteSize;
}

== add {
        import from S;

	if S has ByteSize then {
                bytesize(l: %): SingleInteger == {
                        sz := 0;
			for s in l repeat sz := sz + bytesize s + 8;
			sz
                }
        }
}




Figure 10.2: Exerpt of "axextend.as" for Vector

  1  import from axiomLib;
  2  inline from AxiomLib;
  3  
  4  macro {
  5          SI      == SingleInteger;
  6          BVal    == BuiltinValue;
  7          BArr    == BuiltinArray;
  8  }
 10  -- The Axiom library uses the formal parameter name "#1".
 11  S ==> _#1;
 12
 13  extend Vector(S: Type): with {
 14          if S has SetCategory then SetCategory;
 15          if S has OrderedSet then Orderedset;
 16
 17          -- These provide new required operations:
 18          generator:     % -> Generator S;
 19          bracket:       Generator S -> %;
 20          bracket:       Tuple S     -> %;
 21
 22          -- These are for optimization:
 23          new:           (SI, S) -> %;
 24          #:             % -> SI;
 25	     apply:	    (%, SI) -> S;
 26	     set!:	    (%, SI, S) -> ();
 27  }
 28  == add {
 29          Rep ==> BArr;
 30	     import from Rep, SI, S;
 31          
 32	     if S has SetCategory then {
 33	            (X: %) = (y: %) : Boolean == {
 34		            (#x ~= #y)$SI => false;
 35			    for xx in x for yy in y repeat
 36			            xx ~= yy => return false;
 37			    true;
 38		    }
 39
 40                 coerce(l1: %) : OutputForm == l1 pretend OutputForm;
 41          }
 42	     if S has OrderSet then {
 43	            (a: %) < (b: %) : Boolean == {
 44                         for aa in a for bb in b repeat
 45                                 aa ~= bb => return aa < bb;
 46                         (#a < #b)$SI;
 47                 }
 48          }
 49
 50          [g: Generator S]: % == {
 51                 import from List S;
 52                 l := empty()@List(S);
 53                 n := zero();
 54                 for e in g repeat {
 55                         l := cons(e, l);
 56	                    n := inc n;
 57                 }
 58		    v := per new n;
 59		    while l repeat {
 60		            v.n := first l;
 61			    l := rest l;
 62			    n := dec n;
 63                 }
 64                 v
 65          }
 66
 67          [t: Tuple S]: % == {
 68	            n := length t;
 69                 v := per new n;
 70		    while leq(one(), n) repeat {
 71		            v.n := element(t, n);
 72			    n := dec n;
 73                 }
 74		    v
 75          }
 76
 77          new(n: SI, x: S): % == {
 78	            v := per new n;
 79		    while leq(one(), n) repeat {
 80		            v.n := x;
 81			    n := dec n;
 82                 }
 83		    v
 84          }
 85
 86          generator(v: %): Generator S == {
 87                 n := (#v)@SI;
 88                 i := one();
 89                 generate while leq(i, n) repeat {
 90                         yield v.i;
 91			    i := inc i;
 92                 }
 93          }
 94
 95          #(v: %): SI ==
 96                 # rep v;
 97
 98          apply(x: %, i: SI): S ==
 99	            (rep x).(dec i) pretend S;
100
101          set!(x: %, n: SI, v: S): () ==
102                 (rep x).(dec n) := v pretend BVal;
103  }

Previous Home Contents Next