ALM and DDLog

1README.md

I'm trying to convert ALM to DDLog. I've come up with a contrived example that still models a lot of ALM's features.

The domain is this: we have rectangle objects on some Cartesian plane. Users can move the rectangles around the plane. Some rectangles are "magic rectangles". Normally, each magic rectangle is blue. However, when the user moves a magic rectangle to a particular area of the plane, the rectangle turns red.

Below is:

• A small intro to ALM
• The full ALM program
• A "best guess" on how to translate to DDLog (TODO - this is a work in progress atm)

2Tutorial.md

ALM is a logic language in the tradition of Prolog, Datalog, and ASP.

ALM is all about objects and actions (which are themselves types of objects). Every object has a "sort". Sorts are organized into a directed acyclic graph such that sorts can have one or more subsorts.

ALM has the following built in sorts:built in sorts for booleans and integers.

• booleans
• integers
• universe, which is the root sort for everything
• action, which is the root sort for all action objects, and is itself a subsort of universe

Additionally, users can define their own sorts with the "specialization" operator ("::"). "a :: b" reads "a is a subsort of b"

Objects can have attributes, which are properties intrinsic to the object and which never change. Semantically, attributes are just functions from an object to another value.

Some sorts are small and known ahead of time. These can be represented as set literals like "some_sort :: {a, b, c}". I think this is just typedef some_sort = A | B | C in DDLog.

ALM has a number of built in functions. These mostly describe the sort hierarchy. The two most important built in functions are:

• instance : objects x sorts -> booleans, which tells you if an object is of a particular sort.
• is_a : object x sorts -> booleans, which tells if an object is a subsort of a particular sort.

In addition to objects and the built in functions, ALM has what are called "fluents", functions whose value changes over time as the system changes. There are two types: basic, which have inertia and don't change until changed by some action; and defined, which are derived purely from the values of other fluents, and don't have inertia. These almost exactly correspond to the distinction between input and output relations in DDLog, with one exception: rules can add to the values of basic fluents, while, by my experimentation, rules can't add to the values of input relations. I think this is easily overcome by representing each basic fluent as the combination of an input and output relation.

The last construct in ALM is axioms. Axioms have two forms:

• The first are called state constraints. They read "P if Q". These correspond exactly to normal rules in DDLog if you just replace "if" with :-.

• The second are called causal laws. They say "if action A occurs and P is true, then Q is true in the next state". While DDLog doesn't directly represent change over time, these relationships are still easily representable via normal Datalog rules. I think I'll have to write an interpretter that takes the output of causal laws and modifies the input relations accordingly.

3rectangles.alm

sorts
    rectangles :: universe
        attributes
            width : integers
            height : integers
    magic_rectangles :: rectangles
    axes :: { x, y }
    colors :: { red, blue }
    move :: action
        target : rectangles
        diff : coordinates -> integers
fluents
    basic
        total coordinates : rectangles x axes -> integers
    defined
        in_special_area : rectangles -> booleans
        rectangle_color : magic_rectangles -> colors
axioms
    rectangle_color(Rect) = red if
        instance(Rect, magic_rectangle),
        in_special_area(Rect).
    rectangle_color(Rect) = blue if
        instance(Rect, magic_rectangle),
        -in_special_area(Rect).

    in_special_area(Rect) if
        width(Rect) = W,
        height(Rect) = H,
        coorindates(Rect, x) = X,
        coorindates(Rect, y) = Y,
        X + W < 1000,
        Y + H < 1000.

    occurs(Action) causes coordinates(Target, Coord + Diff) if
        instance(Action, move),
        target(Action) = Target,
        diff(Action) = Diff.

4rectangles.dl

// Since capitalization rules differ between ALM and DDLog, I'll append
// everything with prefixes that make for valid syntax and easy transformations.
// C is for constructor, S is for sort, T is for term literal, F is for function

input relation Object(obj: string, sort: string)

typedef S_universe = C_universe{}
typedef S_actions = C_actions{}

// Set literals are just typedefs
typedef S_axes = T_x | T_y
typedef S_colors = T_red | T_blue

// Sorts with attributes become constructors with arguments
typedef S_rectangles = C_rectangles{width: bigint, height: bigint }

// One way to do inheritance is via product types.
// To say "A is a subsort of B" is to say "A has a B property"
typedef S_magic_rectangles = C_magic_rectangles {
    color : S_colors,
    // magic_rectangles inherit everything rectangles have
    rectangles : S_rectangles
}

typedef S_move = C_move {
    action : S_actions,
    target : S_rectangles,
    target_obj : Object
}

typedef Sort = S_universe
    | S_actions
    | S_axes
    | S_colors
    | S_rectangles
    | S_magic_rectangles
    | S_move

output relation F_is_a(obj: string, sort: Sort)
output relation F_instance(obj: string, sort: Sort)

// For each terminal, non-literal node in the sort hierarchy, we get a rule.
F_is_a(obj, S_rectangles) :- Object(obj, "rectangles").
F_is_a(obj, S_magic_rectangles) :- Object(obj, "magic_rectangles").
F_is_a(obj, S_move) :- Object(obj, "move").

// Now we start building the hierarchy.

// First, these two are independent of user-defined sorts.

// Every type of object is an instance of universe, the top of the tree.
F_instance(obj, S_universe) :- F_is_a(obj, _).
// Every type of object is an instance of its own sort. This forms the leaves of the tree.
F_instance(obj, sort) :- F_is_a(obj, sort).

// Next, the user-defined sorts.
F_instance(obj, S_rectangles) :- F_instance(obj, S_magic_rectangles).
F_instance(obj, S_actions) :- F_instance(obj, S_move).