54 Objects

Physical representation qualifier

The keyword object may prefix a type expression:

object T

object T establishes a heap-allocation boundary. Rather than embedding the representation of a T value directly in a containing value, the implementation allocates it separately.

For data in volatile memory, the containing representation may hold a hidden pointer to the separate heap allocation. A database can be regarded, at this level, as a persistent heap. In persisted data, the corresponding physical link is a hidden persistent object identifier. Loading the value resolves that identifier to an in-memory location.

object specifies a representation boundary, not whether a value is persistent. Like any other type, a type containing object T may be used for a variable that exists only in memory. The qualifier does not introduce a new logical domain, change the predicates of T, or give the value a new application-level identity. Logically, object T is simply T: expressions observe a value of type T, not a pointer, reference, address, or persistent identifier. All such links belong to the physical representation and are hidden from Predica expressions.

Accessing an object T within persisted data may require its separately stored representation to be loaded. An implementation may cache that representation in memory.

For persisted values, an object boundary permits a value to be loaded independently of its container. Construction, ownership, sharing, deletion, and transaction behaviour require explicit rules for separately stored objects.

The object qualifier is orthogonal to the distinction between value and entity types. Either kind of type may require a separate persistent representation. The qualifier says how a value is stored; value and entity continue to say what kind of thing it represents.

JPEG image

The following types model a JPEG encoding and its decoded RGB image:

// Encoding of an image using JPEG format
type JpegBytes = Vector<Byte>;

value RGB
{
    Uint8 r;
    Uint8 g;
    Uint8 b;
}

value Image<Type T>
{
    Vector<T> values;
    Int32 width;
    Int32 height;
}

value Point<Type T>
{
    T x;
    T y;
}

func Point<T> componentWiseProduct<Type T>(Point<T> a, Point<T> b) =
    Point<T> { x = a.x * b.x, y = a.y * b.y };

// Pure function that decodes JPEG into an RGB image in memory
extern "C++:predica"
{
    Image<RGB> decodeJpeg(JpegBytes jpeg);
}

// Single image with synchronous decoding
value Jpeg
{
    JpegBytes bytes;
    → Image<RGB> image = decodeJpeg(bytes);
}

Jpeg.bytes is the encoded representation. The derived attribute image denotes the decoded RGB image and is defined by the pure external function decodeJpeg. As written, accessing image is synchronous. An implementation may materialise the derived value as a cache, provided it remains consistent with bytes.

Tiled image

A tiled image may contain millions of tiles, each perhaps containing 256 × 256 pixels. Each tile can be stored as a separate object in the database. Predica allows these tile objects to be loaded on demand, so accessing part of the image does not require every tile to be loaded.

value TiledImage
{
    const Point<Int32> numTiles;
    const Point<Int32> tilePixelSize;

    constraints
    {
        isPowerOfTwo(numTiles.x);
        isPowerOfTwo(numTiles.y);
    }

    → Int64 countTiles =
        Int64(numTiles.x) * Int64(numTiles.y);

    → imageSize =
        componentWiseProduct(numTiles, tilePixelSize);

    MortonArray<object Jpeg?, numTiles.x, numTiles.y> tiles;
}

The object-qualified element

The key declaration in TiledImage is:

MortonArray<object Jpeg?, numTiles.x, numTiles.y> tiles;

Here object qualifies the Jpeg element type. It instructs the compiler to represent each present Jpeg as a separate database object. It does not qualify the MortonArray itself: the array belongs to the containing TiledImage, while its populated elements are stored independently.

A large TiledImage may contain millions of tiles. Such an image cannot be written in a single transaction, so there is an inherent requirement for its tiles to be added over time, across many transactions. Declaring the elements as object Jpeg? allows each optional tile object to be populated independently.

Logically, the declaration remains a two-dimensional array of zero-or-one Jpeg values. The object qualifier does not introduce reference semantics into the logical model. In particular, it is not logically an array of storage identifiers, pointers, or references. Such representations would expose storage mechanics to ordinary expressions. With object Jpeg?, Predica expressions continue to observe optional Jpeg values, while the compiler manages their independent storage.

Morton-ordered storage

MortonArray<T,X,Y> is a two-dimensional array whose extents are X and Y. Its elements are arranged in Morton order, also called Z-order, so nearby spatial coordinates tend to remain nearby in the one-dimensional representation.

The following image illustrates Morton order with one level of nesting (4 × 4):

The next image illustrates Morton order with two levels of nesting (8 × 8):

In TiledImage, numTiles.x and numTiles.y give the fixed extents of tiles. Each cell has cardinality zero or one because its element declaration is object Jpeg?. The array therefore describes a fixed spatial grid in which tiles may be populated independently.

Object identity from spatial position

The following implementation scheme uses hidden database object identifiers, called OIDs here. An OID is not a Predica type and cannot be inspected or compared by Predica expressions. It is an implementation artefact used to locate a separately stored object.

When a TiledImage is constructed, its const attributes numTiles and tilePixelSize must be supplied to the constructor. The dimensions of tiles are therefore known when construction completes and cannot subsequently change. This allows the implementation to preallocate the Morton array's object-identity space.

Preallocation does not require the array or its elements to be materialised. Because the elements are database objects, the implementation can reserve a contiguous range of OIDs and record only its base OID in the TiledImage. The OID for a tile at (x,y) is:

tileOid(x,y) = tilesBaseOid + morton2D(x,y)

morton2D(x,y) =
    Σᵢ ((((x >> i) & 1) << (2i))
      + (((y >> i) & 1) << (2i + 1)))

Thus the bits of x occupy the even-numbered bits of the Morton index and the bits of y occupy the odd-numbered bits. For example, (0,0), (1,0), (0,1), and (1,1) have Morton indices 0, 1, 2, and 3 respectively. There is no need to store either an array of OIDs or a separate index from coordinates to OIDs.

The calculated OID can then be used to fetch the corresponding Jpeg, if it exists. An empty cell has no logical Jpeg value and need not have any stored object. A populated cell has a Jpeg stored under the OID derived from its position.

Incremental population and on-demand loading

Tiles may be populated over multiple transactions. Because every present tile is a separate database object, Predica can resolve and load an individual tile on demand without loading the other tiles in the image.

Logical absence must be distinguished from physical residency. An empty cell has cardinality zero. A populated cell has cardinality one whether its object is already cached in memory or must be loaded from the database.

Each tile object participates independently in snapshot evaluation. Its derived attributes, including the decoded image, may be materialised and cached independently. Updating a tile's encoded bytes invalidates the affected derived cache without requiring unrelated tiles to be decoded or invalidated.

Indexing and navigation

For x in 0..numTiles.x-1 and y in 0..numTiles.y-1, a tile can be reached by ordinary array indexing:

tiles[x,y]          // Jpeg, cardinality 0..1
tiles[x,y].image    // Image<RGB>, cardinality 0..1

If the cell is empty, both expressions have empty extensions. If the cell is populated, navigation to image resolves the tile object when necessary and then evaluates or retrieves its derived decoded image.

Indexing and filtering syntax

There is no ambiguity between array indexing and a path filter when parsing a path. Indexing uses brackets directly after the array expression, whereas a filter is introduced by .[:

tiles[x,y]

s.supplier.[city = "London"].shipment.part.[color = Color.red]