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.
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 ./2system 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./2./2
./2The 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 len173as 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.
Dicts currently define the following reserved functions:
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
./2
?- 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}}.
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,_).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.
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).
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.
?- 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}.
?- 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}}.
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, _).
?- 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.
member(Dict, List),
Dict >:< point{x:0, y:Y}.
See also :</2 and select_dict/3.
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}.
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.
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(record)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(assoc)library(option)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(pairs)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:
point(1,2).
library(record),
which generates access predicates for a term using positional arguments
from a description.
Name=Value, Name-Value,
Name:Value or Name(Value).
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.
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.