Seeking oMiser Accelerators

[orcmid]

Immutability provides a variety of ways in which it is easier to reason about oMiser computational interpretations. Immutability also allows the underlying implementation of an oMiser to expedite matters so long as the results are indistinguishable from the literal semantics given for applicative operations.

One key factor in exploiting the opportunities of immutability is that the primitive operations be able to operate rapidly and simply. The script-interpretation "inner loop" is to be as simple as possible. The ‹ob› structure primitive notions are contrived with the idea of facilitating such economy of operation.

1. The Immutable List-Structure Assumption

It is presumed that the natural implementation of Obs is via linked-list structures. That is,

c = ob.c(a,b)

is manifest with a storage-structure cell, pointed to by &c, that contains two pointers, &a and &b. All of the primitive notions involve cells of this nature. When &c == &b, the cell represents a singleton. When &c == &a, the cell represents an individual, using == to signify the equality of pointers in the oMiser implementation.

e = ob.e(a)

operates similarly, except the b-position of the cell holds &e.

2. Distinction of Definite Individuals

It is desirable that individuals be distinguished and comparable. For two individuals x and y, it is required that

x = y ⇔ &x == &y

Here, &x == &y is comparable to the eq[x, y] in the formulation of LISP.

2.1 Differentiation of Primitives

The primitives, ob.NIL, ob.A, ..., ob.E, ..., obap.EV, ob.PROC, ob.DEF, etc., are each implemented by distinct, unique cells. oFrugal is able to determine those cells by some look-up mechanism that recognizes the various spellings of .nil, .a, ..., .e, ..., .ev, .proc, .def, etc.

For practical reasons, oFrugal uses a hash table to find links to the storage cells that represent these primitives. It is possible to locate the hash-table entry from the cell of the primitive for this and other purposes.

Implementation Note: It is desirable in what follows that these hashes be based on (case-adjusted) names and not anything about implementations, so that the hashes can be used across implementations for accelerator purposes, including interchange of serialized representations of obs..

2.2 Differentiation of Lindies

Similar arrangements are for creating distinct and unique cells for individual lindies. A different hash table is likely to be used since it will need to be expandable and accommodate variable-length names in some compact encoding. In this manner, each lindy will have a unique individual cell and it can refer to the hash entry where the string holding the printable name is also found. (Primitives could have the same features for simplicity in reporting canonical forms.)

Implementation Note: It may be appropriate to accommodate deletions when any garbage elimination algorithm determines that the lindy cell is no longer referenced from any in-use cells. It will depend on how chaining and hash-collision overflows are handled to know how to close up gaps following deletions. It is assumed that the same hash algorithm can be used as for primitives even if there are different tables. This leads into the structural equality case, below.

2.3 Handling of Binding-Names

Binding-names apply entirely in oFrugal and do not have any presence in oMiser.

Hash-table search for Binding-names is appropriate, although there is no need to adapt the same hash algorithm as the one applied to lindies and primitives, since these exist in oFrugal but not oMiser.

Implementation Consideration: Although binding names are handled at a level outside the oMiser engine, it exists at the boundary with an implementation. Because assigning a binding happens at an oFrugal level, cycling more slowly than ap and eval, this is a good point to consider acceleration and maybe some sort of JITting (4, below).

2.4 Handling of proc Individuals

To ensure that new individuals created from other obs are unique and distinct, it is valuable to use a hash-table search to find any existing proc of the same definition and employ the same oMiser cell for it. In this case, the proc is similar to an enclosure (in 3, below) insofar as hash differentiation is useful to determine when a just-derived proc is not already available.

Implementation Consideration: A proc may be short-lived and that suggests that the work to match up with an existing proc might be excessive. This needs to be considered in conjunction with acceleration procedures applied to pairs and enclosures. The clear identity case for individuals based on the cell location alone is very important when comparisons are made. The problem has to do with ephemeral procs versus ones that will be reused. The binding name case (2.3) might be useful.

3. Distinction of Pairs and Enclosures

When obs are not individuals, the semantics of equality depends on the correspondence of ob composition down to where a difference is encountered or there is a complete match. The presumption is that this is a time-consuming overhead. If there are measures to have matching structures have the same location, comparisons are accelerated.

Implementation Consideration: Effort to expedite structural comparison is justified only if there is a measurable benefit in practice. Instrumentation becomes important. It also becomes important to determine whether preservation of expedited matching be conveyed in serialized persistent forms for interchange and re-use in something more efficient than replaying an oFrugal script. For oMiser and oFrugal so far, we have not addressed distributed operation and sharing of obs (cf. Issue #31).

3.1 Pure Structural Comparison

Implementation of the obaptheory function d(x,y) can be expressed with simple functional pseudo-code.

let d(x, y)
    = if &x == &y
      then .A
      else if is-individual x or is-individual y
           then .B
           else if is-singleton x and is-singleton y
                then d(.a x, .a y)
                else if is-pair x and is-pair y
                     then if d(.b x, .b y) = .A
                          then d(.a x, .a y)
                          else .B
                     else .B ;

There is potential advantage to increasing the cases where &x == &y for non-individuals that are extensionally identical. It is also useful to increase determination when &x != &y yet there is extensional identity.

Implementation Anticipation: Arranging to re-use constructions is an automatic means of improving the incidence of equality in a pure structural comparison. Even if that is irrelevant with regard to comparisons, it is useful in terms of reduced storage footprint, since the same construction is referenced repeatedly. There are also patterns of construction that can be designed to increase this kind of economy.

3.2 Hash-Accelerated Structural Differentiation

Paul McJones pointed out to me that hash functions had been considered in acceleration of comparisons in implementations of LISP. In the case of oMiser implementation, we are already proposing hash-table lookups and we could provide hash codes in all cells.

For hashed constructions, if the hash codes are different, we know the obs are extensionally different. Assuming that every ob instance has a hash code derived from invariant structural features (i.e., the canonical form), we can use

let d(x, y)
    = if &x == &y
      then .A
      else if hash(x) != hash(y)  
           then .B
           else if is-singleton x
                then if is-singleton y
                     then d(.a x, .a y)
                     else .B
                else if is-singleton y
                     then .B
                     else if  .b x = .b y
                          then d(.a x, .a y)
                          else .B ;

where matching hashes might be collisions so it is necessary to go further.

3.3 Opportunistic Consolidation of Structural Matches

Another means of accelerating matches is by exploitation of immutability. References to cells in different locations that happen to be for extensionally-matching structures could have the references adjusted to be to the same cell. Immutability assures that the cases are indistinguishable. The preference is consolidation on the cell that is the older of the two. The idea is that the storage of the younger one is then more likely to be garbage-collected sooner rather than later. Also, it preserves the implicit precedence relationship, ¶.

Implementation Considerations: The situation of concern is only when hashes happen to be the same and we want, when they are found to be structurally identical, a subsequent check to arrive at &x == &y instead. It is unclear that there will be a repeated check very often and that garbage collection will turn out just fine regardless. Instrumented operation will be valuable. Note that, with the formulation of d(x,y) here, it is the d(.a x, .a y) and .b x, = .b y) that must intercede and make their arguments be the same cells on returning .A. For this, we can introduce da(x, y) and dab(x, y) so that we know which fields at &x and &y need to be checked and then made the same when ob-equality is determined. There may be further streamlining also.

4. Revisiting proc, Accelerating Applicative Operation

Every ob has an applicative interpretation. There is opportunity for acceleration in that respect. In particular, there can be code-behind techniques by which an accelerated application can be achieved. That is, every ob can have a direct short-cut implementation of its application to an operand. The default on construction would be to a simple employment of a direct applicative interpretation.

There are also opportunities to produce accelerated (native) implementations that bypass much of the recursive descent that is part of obap.ap reduction to yielding of a result. There are questions with respect to timing -- when and where should such optimization be inserted?

There are potential opportunities when an ob is being applied. There are also opportunities for hidden adjustments in the creation of a binding and perhaps in the use of certain already-provided objects, such as for ^rec and ^lambda.

There are two important limitations.

First, the rewriting that occurs as part of applications that deliver derived scripts must still happen, because the semantics, and especially extensional identity, must be preserved. On-the-fly creation of intermediate closures is a big reach. Approaching that level should be by stages that improve low-hanging fruit first.

Secondly, translation at what is essentially between two machine languages is very limited. The best case is being able to reverse engineer to an abstraction that can then be re-interpreted in the other machine language. Programming systems with definable types and functional abstraction provide essential hints for lower-level simulation.

Low-hanging fruit may be workable first, and addressing that may provide valuable insights for going farther -- or not.

There are other cases that are taken as variations of optimized compiling in oMiser terms. For example, in-lining can be used to eliminate applications.

[to be continued]