Term

From Dyna
Jump to: navigation, search

Contents

About Terms

The data objects in Dyna are called terms. Everything is a term, in the same way that (almost) everything in C is an object. Some examples of Dyna terms:

99
"foo"
nil
bar(99,"foo",nil)
s(np("John"), vp(v("loves"),np("Mary")))

Notice that terms can contain other terms, nested arbitrarily deeply. Hence, they are tree-like data structures. They are mainly written using the same syntax as in Prolog, but they may ground out in any Dyna primitive.

A note for Prolog programmers

Despite the resemblance, Dyna's terms are more restricted than Prolog's. Dyna's terms may not contain variables, so they are similar to ground terms in Prolog. (At least for now!)

While the patterns that appear in Dyna programs are like terms with variables, they are formally distinct from terms. Patterns only have to match against (ground) terms at runtime; they do not have to unify with other patterns. Dyna probably gains in efficiency by not having to deal with full unification, and by not taking the extra space and time to deal with the possibility of variable subterms. If you want full unification, you are of course free to create a new primitive type, prolog_term, that supports non-destructive unification as in the XSB project.

Terms and Types

Every term in Dyna has a type. Type names are atoms.

For example, "foo" has type string, nil has type nil, and bar(99,"foo",nil) has type bar.

Types are important for several reasons:

  • Many declarations refer to types. For example, one might declare that bar terms are real-valued and trainable.
  • Since pragma declarations refer to types, one might declare that bar terms are stored internally in a particular way. (If you want to store some bar terms one way, and some another way, then you have to split the type into two subtypes.)
  • Using strong typing will make your Dyna program more efficient. bar(99,"foo",nil) can be stored and processed more efficiently if you declared :- bar(int,string,list) than if you declared :- bar(term,term,term), although the latter will also work.
  • Using strong typing will also make your C driver program more efficient. It is cheaper and safer to store bar(99,"foo",nil) in a C variable of type bar than in one of type term, although the latter will also work. Strong typing can also make your C program prettier because you can avoid explicit cast operations.
  • What an expression means, if anything, depends on the value types of the items in the expression. For example, hello*world has a well-defined value if hello and world have numeric value types, but not if they have string value types.

Primitive terms

Primitive objects are terms. For example, "foo" is a term of type string, and 3.1415926536 is a term of type double.

Structures

Structures are central to Dyna. They are similar to structs in C. You can declare a new structure type foo as follows:

:- structure(foo(int i, string s)).
Should link the word structure to the page/section where that declaration is fully described.

You can now write terms of type foo:

foo(3,"three")
foo(4,"four")

In general, a structure term is written as a type name (any atom) with 0 or more terms listed as arguments between parentheses. The parentheses are omitted if there are 0 arguments. Thus,

:- structure(nil).

declares a structure type nil, and the only term of this type is the atom

nil

Now that we have declared foo and nil, we can also declare structures that contain them, such as

:- structure(bar(foo x, foo y, nil n)).

which lets you write terms of type bar:

bar(foo(3,"three"),foo(4,"four"),nil)
Alas, the module that parses the Dyna source file is currently broken (version 0.3.1): it rejects all types in structure declarations except for term and the primitive types . So at the moment you will have to replace foo with term in the example.

In practice, most type declarations can be omitted without loss of efficiency, because Dyna provides a form of declaration inference. So you can usually go around like a happy-go-lucky Prolog programmer, writing things like my(big(messy,"term")) without declaring anything. The compiler will try to figure out what you should have declared.

Union types

Like many languages, Dyna supports tagged union types. The tag is implicit, as in Algol.

Suppose you want to have numeric variables that can be either int or float. Declare a new type

:- union(numeric,[int,float]).

This lets you use numeric like any other type:

:- structure(foo(numeric val)).

Now foo(3) and foo(3.0) are legal but distinct terms of type foo. The memory representation of foo(3) must keep an internal tag indicating that its argument is an int rather than a float.

Another example comes from parsing. You might want to be able to write both word("John",3,4) and word(epsilon,3,3), where epsilon is an empty word of width 0. So you need a union type [string,epsilon]:

:- structure(epsilon).
:- union(symbol,[string,epsilon]).
:- structure(word(symbol w, int start, int end)).

Circular declarations using unions

Type declarations can depend circularly on one another. In particular, you can define a list of strings in the usual way:

:- union(list, [nil,cons]).                   % a list is either nil or cons(...)
:- structure(nil).
:- structure(cons(string first, list rest)).  % refers back to list

If you want a heterogeneous list whose elements can be of any types at all, simply replace string with term. That works because term itself is a union type. term is automatically declared to be the union of all other types in the Dyna program (including primitive types). Thus, it plays a role like that of the root class Object in object-oriented languages: every term in Dyna is an instance of term.

By combining :- structure(...) and :- union(...) declarations, you can define any algebraic data type by building up its declaration in "sum-product" form. An instance of a "product" type (structure) is a tuple containing an instance of each of its component types, while an instance of a "sum" type (union) is an instance of just one of its component types.

Special union types

Several standard union types (such as term) are automatically declared, for your convenience, during declaration inference.

Functor overloading

This feature is not yet supported in the implementation.

It is legal to declare several structures with the same functor foo:

:- structure(foo(int i)).
:- structure(foo(string s)).
:- structure(foo(int i, string s)).

This is translated internally into something like

:- structure(foo1(int i)).
:- structure(foo2(string s)).
:- structure(foo3(int i, string s)).
:- union(foo,[foo1,foo2,foo3]).

except that the three subtypes of foo are not really called foo1, foo2, foo3. In fact the subtypes are anonymous. You cannot refer to them by name, either in Dyna or in C .

Type splitting

You may want to rewrite a declaration like structure(foo(list)) ... or negative vs. positive arg ...

The compiler is free to rewrite declarations in this way. For example (in a future version of Dyna), it might choose to transform

:- structure(epsilon).
:- union(symbol,[string,epsilon]).
:- structure(word(symbol w, int start, int end)).

into

:- structure(epsilon).
:- structure(word1(string w, int start, int end)).
:- structure(word2(epsilon w, int start, int end)).
:- union(word, [word1,word2]).

and specialize the inference rules to deal appropriately, and differently, with word1 and word2.

Personal tools
Namespaces

Variants
Actions
Navigation
Tools