Overview

This document provides a formal specification of the syntax and semantics of the ClassAd (Classified Advertisement) language. The name of the language derives from its origin in the Condor distributed computing system [7,8], where it is used for discovery and allocation of resources. Providers of computing resources submit advertisements describing their capabilities and declaring constraints and preferences for jobs they are willing to run. Consumers submit ads describing their jobs. Like the provider ads, these ads may impose constraints and express preferences regarding execution sites. A matchmaker process matches the producer and consumer ads. All policy considerations are contained in the ads themselves; the matchmaker merely supplies the mechanism for interpreting the policies expressed in the ClassAd language. The present document only defines the language. This introduction hints at how the language can be used to express a variety of scheduling policies, but a full discussion of this issue is beyond the scope of this document.

The ClassAd language is a functional language. The basic unit is the expression, and execution entails evaluation of expressions, replacing an expression with its normal form or value. There are no side-effects: Evaluation has no effect other than calculating the value of an expression. The language is carefully designed to allow efficient evaluation. In particular, an expression can be evaluated in time proportional to the size of the expression.¹

The most important type of expression is a record expression (sometimes called a ``classad''), which is a set of name/value pairs. The ``value'' in each pair may be an arbitrarily complex expression, including nested record expressions and lists of expressions. An example is

    [
        type = "gizmo";
        components = {
            [ type = "widget"; part_number = 12394 ],
            [ type = "widget"; part_number = 92348 ]
        };
        main_component = components[0];
        main_part = main_component.part_number;
    ]

ClassAd expressions are strongly but dynamically typed. Supported types include integer and floating-point numbers, Boolean values (true and false), character strings, timestamps, and time intervals. During the evaluation, invalid sub-expressions evaluate to the value error. For example, 1/0, 3 * "abc", {1, 2, 3}[5], and 27[5] all evaluate to error. Attribute references (occurrences of identifiers on the right-hand side of attribute definitions) are replaced by their definitions. Attribute names with no definition or circular definitions evaluate to undefined. Attribute lookup is ``block structured'': An attribute reference is resolved by searching all record expressions containing the reference, from innermost outward, for a matching definition (this matching is case-insensitive). For example, the expression

    [
        a = 1; b = c;
        d = [ f = g; i = a; j = c; k = l; a = 2; ]
        l = d.k; c = 3;
    ]

evaluates to

    [
        a = 1; b = 3;
        d = [ f = undefined; i = 2; j = 3; k = undefined; a = 2; ]
        l = undefined; c = 3
    ]

There are currently two implementations of the ClassAd language, one in C++ and one in Java. Both implementations should have identical external behavior conforming to this specification.² In both implementations, ClassAd expressions are tree-structured objects. Each implementation provides methods for constructing expressions, navigating through them, and evaluating them, as well as methods for translating between the internal data structures and character strings using either of two concrete syntaxes, the ``native representation'' used in the examples above and XML [4].

An important application of ClassAds is matchmaking. Matchmaking is applied to a pair A, B of record expressions, each of which is expected to have a ``top-level'' definition of the attribute Requirements. The Requirements attribute of A is evaluated in an environment in which the attribute reference other evaluates to B, and B.Requirements is evaluated in an environment in which other evaluates to A, If both Requirements attributes evaluate to the specific value true (not undefined, error, or a value of some non-Boolean type), the expressions A and B are said to match. In Condor, matchmaking is used to match job and machine ads. A machine ad describes the characteristics and current state of a machine. It also has a Requirements attribute to restrict the set of jobs it is willing to run and a Rank attribute to indicate how much it ``likes'' an individual job. Rank should evaluate to a non-negative integer, with higher values indicating preferred jobs. Similarly, a job ad has descriptive attributes, a Requirements attribute to constrain the set of acceptable machines, and a Rank attribute to express preferences. The Condor matchmaker uses these attributes to match jobs with machines.

Footnotes

... expression.¹

Actually, this statement is only true if each function call completes within a time bound proportional to the length of its arguments. All ``built-in'' functions have this property.

... specification.²

Of course, this is an idealized goal. As of this writing, there are several ways in which the two implementations differ from each other and from this specification. An effort is underway to improve conformance.