AL Design Doc: Where Does a Value Live? Storage as Configuration in Developing AL Towards a Temporal Semantics
Summary
This article goes over the recent set of changes to AL since . I describe the new constraint store, the SoA/AoS split, bitemporality features in development, as well as the current resolution caches.
Constraints
In the last design doc, I explained that SLD Resolution as Metaobject Protocol was the first vital step in the grand vision of AL’s design, and that constraint processing over finite domains was the natural next step in the evolution of its semantics, necessary for certain kinds of bidirectional queries and optimisation of others.
Here is why: SLD resolution is only capable of enumerating, eagerly, choicepoints in queries of known facts. However, constraint processing replaces this enumeration with propagation: constraints are posted and reasoned about monotonically, prior to ‘labelling’ (enumeration of choicepoints). A constraint such as 1 < X < 100 can exist in its own right without needing a stack of choicepoints. This means much work does not need to be repeated, and the constraint can be composed with other constraints as they are learned.
Unlike mathematical resolution under SLD, Z = X * Y also no longer needs any grounding to be a valid computable statement. Upon binding, a var knows the constraints to which it applies, and can determine whether it is valid or not.
This also allows us to post a kind of constraint that is generally problematic within PROLOG: not. Or to be more specific, dif. In PROLOG and AL, not is a logical not, rather than an expression of difference. That is to say, checking not means: ‘Forall possible bindings in , it does not apply’- there is no such X. However, sometimes one only wants to express difference- dif(X, Y) acts as a constraint which ensures that X and Y are, well, different. This is an important feature of constraint propagation.
Constraints must also interact. This means there must be a dedicated constraint solving engine. Narrowing the domain of a variable may precipitate into other narrowings. I believe that Sussman describes the basic operation of propagators best in ‘Art of the Propagator’.
The implementation of CLP(FD) in AL is largely conventional, with known modern optimisations such as bounds consistency, arc consistency, and other specialised algorithms such as Regin’s Algorithm. However, what distinguishes AL’s constraint layer is that it can also reason about objects qua object. CLP(Z) is a special case of CLP(Object ID), and this means one can reason about such statements like ‘the class of O is C’, ‘O inherits from S’ as constraints.
This means that AL can perform what I call ‘smart generation’. When sending to an object, an unground receiver must be determined by either generating a value object, or by looking up applicable durable objects via the inheritance chain. Now with constraints, we can take a slightly more optimised approach. Receivers still enumerate eagerly, since execution may have side effects (although it may be that a compiler can optimise things differently), but constraints apply at the point of send, which is to say sends perform an implicit labelling. Only the valid interpretations of a send will apply, reducing the amount of work that AL needs to do. This ends up working quite well for ‘ephemeral’ objects, which only exist for the duration of a transaction, since their properties can be unbounded yet constrained. Meaning that one can perform some more interesting queries.
This also required changing the classical design of AL’s runtime as a WAM into something that understands its active binding store as a constraint store natively. Instead of variables being either bound or unbound, variables now associate with their relevant constraints, with hooks that fire on unification which check said constraints.
The basic body of CLP(FD) work is now completed, although testing and robustness improvements are still ongoing. It’s worth noting that at least for now, constraints do not persist into the database, so there is no such notion of adding an unbound yet constrained var into the database. Sorry!
Redefinition
Redefinition has been built out in order to help with the liveness and ergonomics of AL. The brief explanation is that when a class is redefined with a special flag, any existing instances are walked, with newly declared ivars added or enforced as required, and retracted ivars removed.
Importantly, this logic can be overwritten with an MOP hook, class_redefined, much like CLOS. This could be done in the case that the user wanted to, say, simply invalidate existing instances, or do more bespoke logic. reconcile_redefined_instance determines the overwrite logic for an instance, and backfill_ivar also provides a similar hook for determining how missing ivars are backfilled.
Bitemporality
A feature that has been discussed as essential to AL for some time is bitemporality, the work for which has now begun. For those not in the know, here is a basic explanation of how bitemporality works according to databases like XTDB & SQL 2011.
Firstly, there is a concept of system_time: Each document in a database has with it an associated marking of the times during which the document came to exist, and when it ceased to exist, in the database.
Secondly, there is a concept of valid_time: Each document in a database has with it an associated marking of the times during which the document is considered to be ‘active’ in the sense of a practical domain.
The separation of these two timelines is enabled by the structure of event sourcing, and allows users to separate notions of ‘when something existed’ and ‘when my system actually learned that the thing existed’. In short, it allows one to reason separately about change and correctness, and to reflexively model the database’s evolving knowledge. This is why AL is driven by a ‘command log’ architecture, where-in the object views are derived from an append-only, write-ahead log of all transacted operations.
AL now has one of these axes. Each durable relation now follows a ‘soft-close’ pattern, where-in a row such as class(o1, c1) is not deleted when retracted, but rather, the :open temporal marker for said row is closed by stamping the transaction under which the row was closed. This, along with constraint propagation, allows the user to reason temporally over objects, making queries such as give me all of the values throughout the database's history for this slot.
What AL does not yet have is the valid_time axis, the writes for which is something the user can fully determine.
Storage Overhaul
The question of valid_time yielded an important piece of theoretical knowledge: Shared slots rows mean that temporal markers apply to the entire set of slots, rather than to singular slots. Modern databases take a more bespoke approach, where-in the ‘struct of arrays’ representation and the ‘array of structs’ representation can both exist simultaneously. The former is ideal for looking for many objects with the same slot (for example, searching for an object), whereas the latter is ideal for looking for many slots on the same object. We can take advantage of this in AL, where having both approaches in different situations would be ideal.
AL now allows ivar definition level configuration of their relational storage mechanism. This means that the user can optimise their code by deciding on a different storage mechanism.
Moreover, the existing relations have all been given default storage mechanism. One finds that for multi-valued rows, the SoA representation is ideal, and this is also true for reasoning about time. However, AoS might still be appropriate if it is the ‘whole object level’ so to speak at which these temporal dynamics apply. Moreover, this can be overridden on a subclass by simply redefining the ivar.
Resolution Caches
Finally, we can avoid having to ask ‘where do I lookup this thing’ by maintaining an ivar specs cache which invalidates on write (typical for coarse IVM, and in keeping with Smalltalk). This secondary information will provide quick lookups despite the differing storage mechanisms between different slots, without having to walk the inheritance chain. This resolution cache exists in addition to the existing caches that exist for optimising the VM.