5.4 Dicts: structures with named arguments

SWI-Prolog version 7 introduces dicts as an abstract object with a concrete modern syntax and functional notation for accessing members and as well as access functions defined by the user. The syntax for a dict is illustrated below. Tag is either a variable or an atom. As with compound terms, there is no space between the tag and the opening brace. The keys are either atoms or small integers (up to max_tagged_integer). The values are arbitrary Prolog terms which are parsed using the same rules as used for arguments in compound terms.

Tag{Key1:Value1, Key2:Value2, ...}

A dict can not hold duplicate keys. The dict is transformed into an opaque internal representation that does not respect the order in which the key-value pairs appear in the input text. If a dict is written, the keys are written according to the standard order of terms (see section 4.6.1). Here are some examples, where the second example illustrates that the order is not maintained and the third illustrates an anonymous dict.

?- A = point{x:1, y:2}.
A = point{x:1, y:2}.

?- A = point{y:2, x:1}.
A = point{x:1, y:2}.

?- A = _{first_name:"Mel", last_name:"Smith"}.
A = _G1476{first_name:"Mel", last_name:"Smith"}.

Dicts can be unified following the standard symmetric Prolog unification rules. As dicts use an internal canonical form, the order in which the named keys are represented is not relevant. This behaviour is illustrated by the following example.

?- point{x:1, y:2} = Tag{y:2, x:X}.
Tag = point,
X = 1.

Note In the current implementation, two dicts unify only if they have the same set of keys and the tags and values associated with the keys unify. In future versions, the notion of unification between dicts could be modified such that two dicts unify if their tags and the values associated with common keys unify, turning both dicts into a new dict that has the union of the keys of the two original dicts.

5.4.1 Functions on dicts

The infix operator dot (op(100, yfx, .) is used to extract values and evaluate functions on dicts. Functions are recognised if they appear in the argument of a goal in the source text, possibly nested in a term. The keys act as field selector, which is illustrated in this example.

?- X = point{x:1,y:2}.x.
X = 1.

?- Pt = point{x:1,y:2}, write(Pt.y).
2
Pt = point{x:1,y:2}.

?- X = point{x:1,y:2}.C.
X = 1,
C = x ;
X = 2,
C = y.

The compiler translates a goal that contains ./2 terms in its arguments into a conjunction of calls to ./3 defined in the system module. Terms functor.2 that appears in the head are replaced with a variable and calls to ./3 are inserted at the start of the body. Below are two examples, where the first extracts the x key from a dict and the second extends a dict containing an address with the postal code, given a find_postal_code/4 predicate.

dict_x(X, X.x).

add_postal_code(Dict, Dict.put(postal_code, Code)) :-
        find_postal_code(Dict.city,
                         Dict.street,
                         Dict.house_number,
                         Code).

Note that expansion of ./2 terms implies that such terms cannot be created by writing them explicitly in your source code. Such terms can still be created with functor/3, =../2, compound_name_arity/3 and compound_name_arguments/3.^{176Traditional code is unlikely to use ./2 terms because they were practically reserved for usage in lists. We do not provide a quoting mechanism as found in functional languages because it would only be needed to quote ./2 terms, such terms are rare and term manipulation provides an escape route.}

.(+Dict, +Function, -Result)

This predicate is called to evaluate ./2 terms found in the arguments of a goal. This predicate evaluates the field extraction described above, raising an exception if Function is an atom (key) and Dict does not contain the requested key. If Function is a compound term, it checks for the predefined functions on dicts described in section 5.4.1.2 or executes a user defined function as described in section 5.4.1.1.

5.4.1.1 User defined functions on dicts

The tag of a dict associates the dict to a module. If the dot notation uses a compound term, this calls the goal below.

<module>:<name>(Arg1, ..., +Dict, -Value)

Functions are normal Prolog predicates. The dict infrastructure provides a more convenient syntax for representing the head of such predicates without worrying about the argument calling conventions. The code below defines a function multiply(Times) on a point that creates a new point by multiplying both coordinates. and len^{177as length would result in a predicate length/2, this name cannot be used. This might change in future versions.} to compute the length from the origin. The . and := operators are used to abstract the location of the predicate arguments. It is allowed to define multiple a function with multiple clauses, providing overloading and non-determinism.

:- module(point, []).

M.multiply(F) := point{x:X, y:Y} :-
        X is M.x*F,
        Y is M.y*F.

M.len() := Len :-
        Len is sqrt(M.x**2 + M.y**2).

After these definitions, we can evaluate the following functions:

?- X = point{x:1, y:2}.multiply(2).
X = point{x:2, y:4}.

?- X = point{x:1, y:2}.multiply(2).len().
X = 4.47213595499958.

5.4.1.2 Predefined functions on dicts

Dicts currently define the following reserved functions:

get(?KeyPath)

Return the value associates with KeyPath. KeyPath is either a single key or a term Key1/Key2/.... Each key is either an atom, small integer or a variable. While Dict.Key throws an existence error, this function fails silently if a key does not exist in the target dict. See also :</2, which can be used to test for existence and unify multiple key values from a dict. For example:

?- write(t{a:x}.get(a)).
x
?- write(t{a:x}.get(b)).
false.
?- write(t{a:t{b:x}}.get(a/b)).
x

put(+New)

Evaluates to a new dict where the key-values in New replace or extend the key-values in the original dict. See put_dict/3.

get(?KeyPath, +Default)

Same as get/1 , but if no match is found the function evaluates to Default. If KeyPath contains variables possible choice points are respected and the function only evaluates to Default if the pattern has no matches.

put(+KeyPath, +Value)

Evaluates to a new dict where the KeyPath-Value replaces or extends the key-values in the original dict. KeyPath is either a key or a term KeyPath/Key,^{178Note that we do not use the’.' functor here, because the ./2 would evaluate.} replacing the value associated with Key in a sub-dict of the dict on which the function operates. See put_dict/4. Below are some examples:

?- A = _{}.put(a, 1).
A = _G7359{a:1}.

?- A = _{a:1}.put(a, 2).
A = _G7377{a:2}.

?- A = _{a:1}.put(b/c, 2).
A = _G1395{a:1, b:_G1584{c:2}}.

?- A = _{a:_{b:1}}.put(a/b, 2).
A = _G1429{a:_G1425{b:2}}.

?- A = _{a:1}.put(a/b, 2).
A = _G1395{a:_G1578{b:2}}.

5.4.2 Predicates for managing dicts

This section documents the predicates that are defined on dicts. We use the naming and argument conventions of the traditional library(assoc).

is_dict(@Term)

True if Term is a dict. This is the same as is_dict(Term,_).

is_dict(@Term, -Tag)

True if Term is a dict of Tag.

get_dict(?Key, +Dict, -Value)

Unify the value associated with Key in dict with Value. If Key is unbound, all associations in Dict are returned on backtracking. The order in which the associations are returned is undefined. This predicate is normally accessed using the functional notation Dict.Key. See section 5.4.1.

Fails silently if Key does not appear in Dict. This is different from the behavior of the functional‘.`-notation, which throws an existence error in that case.

[semidet]get_dict(+Key, +Dict, -Value, -NewDict, +NewValue)

Create a new dict after updating the value for Key. Fails if Value does not unify with the current value associated with Key. Dict is either a dict or a list the can be converted into a dict.

Has the behavior as if defined in the following way:

get_dict(Key, Dict, Value, NewDict, NewValue) :-
        get_dict(Key, Dict, Value),
        put_dict(Key, Dict, NewValue, NewDict).

dict_create(-Dict, +Tag, +Data)

Create a dict in Tag from Data. Data is a list of attribute-value pairs using the syntax Key:Value, Key=Value, Key-Value or Key(Value). An exception is raised if Data is not a proper list, one of the elements is not of the shape above, a key is neither an atom nor a small integer or there is a duplicate key.

dict_pairs(?Dict, ?Tag, ?Pairs)

Bi-directional mapping between a dict and an ordered list of pairs (see section A.32).

put_dict(+New, +DictIn, -DictOut)

DictOut is a new dict created by replacing or adding key-value pairs from New to Dict. New is either a dict or a valid input for dict_create/3. This predicate is normally accessed using the functional notation. Below are some examples:

?- A = point{x:1, y:2}.put(_{x:3}).
A = point{x:3, y:2}.

?- A = point{x:1, y:2}.put([x=3]).
A = point{x:3, y:2}.

?- A = point{x:1, y:2}.put([x=3,z=0]).
A = point{x:3, y:2, z:0}.

put_dict(+Key, +DictIn, +Value, -DictOut)

DictOut is a new dict created by replacing or adding Key-Value to DictIn. For example:

?- A = point{x:1, y:2}.put(x, 3).
A = point{x:3, y:2}.

This predicate can also be accessed by using the functional notation, in which case Key can also be a *path* of keys. For example:

?- Dict = _{}.put(a/b, c).
Dict = _6096{a:_6200{b:c}}.

del_dict(+Key, +DictIn, ?Value, -DictOut)

True when Key-Value is in DictIn and DictOut contains all associations of DictIn except for Key.

[semidet]+Select :< +From

True when Select is a‘sub dict' of From: the tags must unify and all keys in Select must appear with unifying values in From. From may contain keys that are not in Select. This operation is frequently used to match a dict and at the same time extract relevant values from it. For example:

plot(Dict, On) :-
        _{x:X, y:Y, z:Z} :< Dict, !,
        plot_xyz(X, Y, Z, On).
plot(Dict, On) :-
        _{x:X, y:Y} :< Dict, !,
        plot_xy(X, Y, On).

The goal Select :< From is equivalent to select_dict(Select, From, _).

[semidet]select_dict(+Select, +From, -Rest)

True when the tags of Select and From have been unified, all keys in Select appear in From and the corresponding values have been unified. The key-value pairs of From that do not appear in Select are used to form an anonymous dict, which us unified with Rest. For example:

?- select_dict(P{x:0, y:Y}, point{x:0, y:1, z:2}, R).
P = point,
Y = 1,
R = _G1705{z:2}.

See also :</2 to ignore Rest and >:</2 for a symmetric partial unification of two dicts.

+Dict1 >:< +Dict2

This operator specifies a partial unification between Dict1 and Dict2. It is true when the tags and the values associated with all common keys have been unified. The values associated to keys that do not appear in the other dict are ignored. Partial unification is symmetric. For example, given a list of dicts, find dicts that represent a point with X equal to zero:

    member(Dict, List),
    Dict >:< point{x:0, y:Y}.

See also :</2 and select_dict/3.

5.4.2.1 Destructive assignment in dicts

This section describes the destructive update operations defined on dicts. These actions can only update keys and not add or remove keys. If the requested key does not exist the predicate raises existence_error(key, Key, Dict). Note the additional argument.

Destructive assignment is a non-logical operation and should be used with care because the system may copy or share identical Prolog terms at any time. Some of this behaviour can be avoided by adding an additional unbound value to the dict. This prevents unwanted sharing and ensures that copy_term/2 actually copies the dict. This pitfall is demonstrated in the example below:

?- A = a{a:1}, copy_term(A,B), b_set_dict(a, A, 2).
A = B, B = a{a:2}.

?- A = a{a:1,dummy:_}, copy_term(A,B), b_set_dict(a, A, 2).
A = a{a:2, dummy:_G3195},
B = a{a:1, dummy:_G3391}.

[det]b_set_dict(+Key, !Dict, +Value)

Destructively update the value associated with Key in Dict to Value. The update is trailed and undone on backtracking. This predicate raises an existence error if Key does not appear in Dict. The update semantics are equivalent to setarg/3 and b_setval/2.

[det]nb_set_dict(+Key, !Dict, +Value)

Destructively update the value associated with Key in Dict to a copy of Value. The update is not undone on backtracking. This predicate raises an existence error if Key does not appear in Dict. The update semantics are equivalent to nb_setarg/3 and nb_setval/2.

[det]nb_link_dict(+Key, !Dict, +Value)

Destructively update the value associated with Key in Dict to Value. The update is not undone on backtracking. This predicate raises an existence error if Key does not appear in Dict. The update semantics are equivalent to nb_linkarg/3 and nb_linkval/2. Use with extreme care and consult the documentation of nb_linkval/2 before use.

5.4.3 When to use dicts?

Dicts are a new type in the Prolog world. They compete with several other types and libraries. In the list below we have a closer look at these relations. We will see that dicts are first of all a good replacement for compound terms with a high or not clearly fixed arity, library library(record) and option processing.

Compound terms

Compound terms with positional arguments form the traditional way to package data in Prolog. This representation is well understood, fast and compound terms are stored efficiently. Compound terms are still the representation of choice, provided that the number of arguments is low and fixed or compactness or performance are of utmost importance.

A good example of a compound term is the representation of RDF triples using the term rdf(Subject, Predicate, Object) because RDF triples are defined to have precisely these three arguments and they are always referred to in this order. An application processing information about persons should probably use dicts because the information that is related to a person is not so fixed. Typically we see first and last name. But there may also be title, middle name, gender, date of birth, etc. The number of arguments becomes unmanageable when using a compound term, while adding or removing an argument leads to many changes in the program.

Library library(record)

Using library library(record) relieves the maintenance issues associated with using compound terms significantly. The library generates access and modification predicates for each field in a compound term from a declaration. The library provides sound access to compound terms with many arguments. One of its problems is the verbose syntax needed to access or modify fields which results from long names for the generated predicates and the restriction that each field needs to be extracted with a separate goal. Consider the example below, where the first uses library library(record) and the second uses dicts.

    ...,
    person_first_name(P, FirstName),
    person_last_name(P, LastName),
    format('Dear ~w ~w,~n~n', [FirstName, LastName]).

    ...,
    format('Dear ~w ~w,~n~n', [Dict.first_name, Dict.last_name]).

Records have a fixed number of arguments and (non-)existence of an argument must be represented using a value that is outside the normal domain. This lead to unnatural code. For example, suppose our person also has a title. If we know the first name we use this and else we use the title. The code samples below illustrate this.

salutation(P) :-
    person_first_name(P, FirstName), nonvar(FirstName), !,
    person_last_name(P, LastName),
    format('Dear ~w ~w,~n~n', [FirstName, LastName]).
salutation(P) :-
    person_title(P, Title), nonvar(Title), !,
    person_last_name(P, LastName),
    format('Dear ~w ~w,~n~n', [Title, LastName]).

salutation(P) :-
    _{first_name:FirstName, last_name:LastName} :< P, !,
    format('Dear ~w ~w,~n~n', [FirstName, LastName]).
salutation(P) :-
    _{title:Title, last_name:LastName} :< P, !,
    format('Dear ~w ~w,~n~n', [Title, LastName]).

Library library(assoc)

This library implements a balanced binary tree. Dicts can replace the use of this library if the association is fairly static (i.e., there are few update operations), all keys are atoms or (small) integers and the code does not rely on ordered operations.

Library library(option)

Option lists are introduced by ISO Prolog, for example for read_term/3, open/4, etc. The library(option) library provides operations to extract options, merge options lists, etc. Dicts are well suited to replace option lists because they are cheaper, can be processed faster and have a more natural syntax.

Library library(pairs)

This library is commonly used to process large name-value associations. In many cases this concerns short-lived data structures that result from findall/3, maplist/3 and similar list processing predicates. Dicts may play a role if frequent random key lookups are needed on the resulting association. For example, the skeleton‘create a pairs list',‘use list_to_assoc/2 to create an assoc', followed by frequent usage of get_assoc/3 to extract key values can be replaced using dict_pairs/3 and the dict access functions. Using dicts in this scenario is more efficient and provides a more pleasant access syntax.

5.4.4 A motivation for dicts as primary citizens

Dicts, or key-value associations, are a common data structure. A good old example are property lists as found in Lisp, while a good recent example is formed by JavaScript objects. Traditional Prolog does not offer native property lists. As a result, people are using a wide range of data structures for key-value associations:

• Using compound terms and positional arguments, e.g., point(1,2).
• Using compound terms with library library(record), which generates access predicates for a term using positional arguments from a description.
• Using lists of terms Name=Value, Name-Value, Name:Value or Name(Value).
• Using library library(assoc) which represents the associations as a balanced binary tree.

This situation is unfortunate. Each of these have their advantages and disadvantages. E.g., compound terms are compact and fast, but inflexible and using positional arguments quickly breaks down. Library library(record) fixes this, but the syntax is considered hard to use. Lists are flexible, but expensive and the alternative key-value representations that are used complicate the matter even more. Library library(assoc) allows for efficient manipulation of changing associations, but the syntactical representation of an assoc is complex, which makes them unsuitable for e.g., options lists as seen in predicates such as open/4.

5.4.5 Implementation notes about dicts

Although dicts are designed as an abstract data type and we deliberately reserve the possibility to change the representation and even use multiple representations, this section describes the current implementation.

Dicts are currently represented as a compound term using the functor `dict`. The first argument is the tag. The remaining arguments create an array of sorted key-value pairs. This representation is compact and guarantees good locality. Lookup is order log( N ), while adding values, deleting values and merging with other dicts has order N. The main disadvantage is that changing values in large dicts is costly, both in terms of memory and time.

Future versions may share keys in a separate structure or use a binary trees to allow for cheaper updates. One of the issues is that the representation must either be kept canonical or unification must be extended to compensate for alternate representations.