Framing Frames

If you've been doing some reading, you may have come across the notion of frames as a data structure, but little available information on what they are and how they work. Implementations of frames are even rarer. In this post we'll examine what they are and consider alternative representations and implementations.

What are Frames?

We sometimes hear mutterings of Frames as a forerunner to OWL or perhaps, incorrectly, Object-Oriented programming. Their place in the evolution of things is from a stage where subsumption and instantiation were being used, in Frames and Semantic Networks, but Object-Oriented achieved dominance and Description Logics were named.

A Frame, at it's simplest, consists of an identifying label and slot-value pairs. They do get more complicated though, including "values" that are procedures or daemons, as described by AMZI!, so we shan't repeat that here. If you want the full power of objects in Prolog, then check out Logtalk.

We'll stick to the typical Frame conventions: ako is the subsumption relation (a kind of) and isa is the instantiation relationship (is a):

CAR: comment-"Vehicle used for transport"

LANCER: ako-CAR, manufacturer-MITSUBISHI, top_speed-127, mpg-17

SIERRA: ako-CAR, manufacturer-FORD, top_speed-118, mpg-23

VIN_JM1BK313141132051: isa-SIERRA, mot: invalid, colour-silver

From this small knowledge base we can assume the thing identified by VIN_JM1BK313141132051 is a "Vehicle used for transport", has a top speed of 118 and will do 23 miles-per-gallon, if it had a valid MOT.

The question is, how do we represent this in Prolog and how do we query it?

Predicate-Based Representations

We've got an identity label and slot-value pairs to represent in a structure that we'd like to be convenient to query. We could stick to a regular predicate logic representation:


Sure, all the data is there, but it's not really true to the "identity label" and "slot-value" pairs representation that is a Frame. Plus, Prolog'll want your predicates grouped in the file by default, whereas for reading Frames it would be nice to have them grouped by their identity label. Maintaining a decent sized knowledge base with this format would be somewhat annoying and error prone, although discontinuous/1 will go a long way to alleviating that.

In this representation, we can't have the slot as the variable in the query, without some jiggery-pokery. However, trying to find out how a subject is related to a value is a rare query so this may not appear to cause any bother for your application, but finding all the slot-value pairs for a given subject can be a useful!


For readability and to reify the slot you'll see the representation rejigged like so:


OK, a little easier reading. Still not quite true to the single "identity label", but we can at least identify the slots and the values. As before, there's one query we can't do with this representation, this one is even more likely to cause some bother. We can't query with a variable for the subject:


In both cases, querying required us to use the call/3 operator to compose our queries. This is the cause of the failure of queries with variables in the "wrong" places. One solution, triples, presents itself when declaring slots that are transitive, reflexive, or symmetric, such as ako (which is reflexive and transitive). But let's get away from repeating the identity label.

Dicts and Pairs Representations

Pair lists are a common data-structure in Prolog, so you'll often find your implementation has some handy predicates for dealing with them. Dicts are somewhat of a newcomer and although they may be trendy and more efficient for look-ups with many slots, they don't work forwards and backwards in the same way that pairs do. Dicts seem like a a good idea, until they turn-round and bite you with an "arguments insufficiently instantiated" error right when you don't want it. Feel free to try dicts, perhaps you can do a better job at it than my past attempts.

This pair representation is simplified from the more complex AMZI! one previously mentioned:


Maybe I'm biased, but those frames are beautiful reading! This is a frame representation that stays true to what a frame is. It's not all wins though by using this representation, our queries are likely to be less efficient, particularly when the identity label is the variable of your query, (?-query(Car, mpg, 17).) but we can have variables anywhere in the query.


Well there's three different ways to represent a "frame" here in your Prolog code, plus the triples style in Reflexive, Symmetric and Transitive Relations in Prolog. Perhaps this great flexibility with the trade-offs in efficiency and readability are one reason why there's no "standard Prolog frame".

At the end of the day, it's a way to write your data and query it, with subsumption and instantiation. The additional features required, such as reified relationships, daemon procedures or non-functional relationships, as well as the typical queries you're expecting, will determine how you'll write your frames. Hopefully this little jaunt will have provided enough ideas for you to spin your own frames next time you're finding yourself in need.