In this paper, we give an overview of our current work on introducing context as first-class objects in Lucid. It allows us to write programs in Lucx (Lucid enriched with context) in a high level of abstraction which is closer to the problem domain. We include a discussion on context theory, representation of context aggregations, and the syntax and semantic rules of Lucx. The implementation of Lucx in GIPSY, a platform under development for compiling Lucid family of languages, is also discussed.
Context is a rich concept and is hard to define. The meaning of "context" is tacitly understood and used by researchers in diverse disciplines. In modelling human-computer interaction [5], context includes the physical place of the user, the time constraints, and the system's assumption about users interests. In Ubiquitous computing [3], context is understood as both situated and environmental. In natural language processing, contexts arise as situations for interpreting natural language constructs. In imperative programming languages, context introduces index, constants, and pointers. In functional languages, static context introduces definitions and constraints, and dynamic context processes the executable information for evaluating expressions. In Artificial Intelligence(AI), the notion of context was introduced by McCarthy and later used by Guha [4] as a means of expressing assumptions made by natural language expressions. Hence, a formula, which is an expression combining a sentence in AI with contexts, can express the exact meaning of the natural language expression. Intensional logic [7] is a branch of mathematical logic which is used to describe precisely context-dependent entities. In Intensional Programming(IP) paradigm, which has its foundations in Intensional Logic, the real meaning of an expression, called intension, is a function from contexts to values, and the value of the intension at any particular context, called the extension, is obtained by applying context operators to the intension. Although the notion of context was implicit in Lucid, an Intensional Programming Language, context cannot be explicitly declared and manipulated in Lucid. By introducing context as a first class object in Lucid, we remove this limitation. The language, thus extended, is called Lucx(Lucid extended with contexts).
The goal of this paper is to illustrate how context is formally defined and introduced as first class objects in Lucx and as a result, how Lucx can be used for programming diverse application domains. The context theory that we are developing provides a semantic basis for context manipulation in Lucx. The paper is organized as follows: In Section 2 we review briefly contexts in Intensional Programming Paradigm. Section 3 discusses the context theory applied in Lucx. In Section 4 we discuss the syntax and semantics of Lucx. An example of Lucx programming and implementing Lucx are also illustrated. We conclude our work in Section 5.
Intensional Logic, a family of mathematical formal systems that permits expressions whose value depends on hidden context, came into being from research in natural language understanding. Basically, intensional logics add dimensions to logical expressions, and non-intensional logics can be viewed as constant in all possible dimensions, i.e. their valuation does not vary according to their context of utterance. Intensional operators are defined to navigate in the context space. In order to navigate, some dimension tags (or indexes) are required to provide place holders along dimensions. These dimension tags, along with the dimension names they belong to, are used to define the context for evaluating intensional expressions. For example, we can have an expression: E: the average temperature this month here is greater than 0
This expression is intensional because the truth value of this expression depends on the context in which it is evaluated. The two intensional natural language operators in this expression are this month and here, which refer respectively to the time and space dimension. If we evaluate the expression in different cities in Canada and in the months of a particular year, the extension of the expression varies. Hence, we have the following valuation for the expression:
The intension of the expression is the above whole table; and the extension of the expression in the time point Ap and in the space point Ottowa is T.
Intensional programming paradigm has its foundations on intensional logic. It retains two aspects from intensional logic: first, at the syntactic level, are context-switching operators, called intensional operators; second, at the semantic level, is the use of possible worlds semantics [7].
Lucid was a data-flow language and evolved into a Multidimensional Intensional Programming Language [1]. In extending Lucid with contexts we preserve the intensionality in Lucx. Moreover, contexts exist independent of any objects in the system. That is, one context may be used to evaluate different expressions, at the same time expressions can also be evaluated at different contexts. This feature distinguishes the language Lucx from other imperative languages or functional languages, where index (for imperative languages) or evaluation environment(for functional language) are always bound to statements or expressions. Because of the separation of the definition of expressions from contexts, Lucx has provided more power of representing problems in different application domains and given more flexibility of programming.
Context theory provides a semantic basis for Lucx programs. A context in the theory need not be finite. However, context in Lucx has a finite number of dimensions and along each dimension is associated a tag set, which is enumerable. This is in contrast to Guha's notion, wherein contexts are infinite, rich, and generalized objects. We are motivated by Guha's work. However not all contexts studied by Guha can be dealt within our language. On the other hand, every context that we can define in Lucx is indeed a context in Guha's sense, but restricted to well-formed Lucx expressions.
In Intensional Programming context is a reference to the representation of the "possible worlds" relevant to the current discussion. The "possible world" is a multidimensional space enclosing all possible information pertaining to the discussion. Motivated by this, we formalize contexts as a subset of a finite union of relations. The relations are defined over dimension and tag sets. Let DIM = {d 1 , d 2 , . . . , d n } denote a finite set of dimension names. We associate with each d i ∈ DIM a unique enumerable tag set X i . Let TAG = {X 1 , . . . , X r } denote the set of tag sets. There exists functions f dimtotag : DIM → TAG, such that the function f dimtotag associates with every d i ∈ DIM exactly one tag X j in TAG.
As an example consider a system in which computations involve pressure, volume, and time, where pressure is observed by different sensors, volume is measured by different devices, and the sampling frequencies are different. The three distinguished dimensions are: (1).Sampling Time ST with index N; (2). Pressure P with index set {s 1 , . . . , s k }, where s 1 , . . . , s k are named sensory devices; and (3). Volume V with index set {m 1 , . . . , m q }, where m 1 , . . . , m q are named measuring devices. A context c = [ST : 1, P : s 2 , V : m 3 ] for one stream σ may be interpreted as a reference to the tuple t 1 , p 2 , v 3 , where at the first sampling time t 1 the value of volume measured by m 3 is v 3 and the value of pressure observed by the sensor s 2 is p 2 . Supposing t 1 , p 2 , v 3 ∈ R, the domain for the entities in the stream σ is R × R × R. The same context may also be used as a reference to another possible world containing the expression σ = p v t . Such a reference will produce the result p2 v3 t1 , which is the result of evaluating the expression σ with the substitution [t → t 1 ; p → p 2 ; v → v 3 ]. In this case, the domain for the entities in the stream σ is R.
Several functions on contexts are predefined in [2]. The basic functions dim and tag are to extract the set of dimensions and their associate tag values from a set of contexts. Since we are still developing the Lucx language, the set of predefined functions is not exhaustive. Functions on contexts using functions already defined in Lucx can be introduced.
In [9], we have formally defined the following context operators: the override ⊕ is similar to function override; difference , comparison =, conjunction , and disjunction are similar to set operators; projection ↓ and hiding ↑ are selection operators; constructor [ : ] is used to construct an atomic context; substitution / is used to substitute values for selected tags in a context; choice | accepts a finite number of contexts and nondeterministically returns one of them; undirected range and directed range produce a set of contexts.
Example 2 illustrates an overall example for some of those operators.
In order to provide a precise meaning for a context expression, we have defined the precedence rules for all the operators in Figure 1[a] (right column) (from the highest precedence to the lowest) and described a set of evaluation rules for context expressions in [9]. Parentheses will be used to override this precedence when needed. Operators having the same precedence will be applied from left to right. The formal syntax of context expressions is shown in Figure 1[a](left column).
A context which is not a micro context or a simple context is called a non-simple context. For example, context c 4 = [X : 3, X : 4, Y : 3, Y : 2, U : blue] is a non-simple context. In general, a non-simple context is equivalent to a set of simple contexts [2]. In several applications we deal with contexts that have the same dimension set ∆ ⊆ DIM and the tags satisfy a predicate formula p. The short hand notation for such a set is
The context operators projection (↓), hiding (↑), choice (|), and substitution (/) introduced in Section 3.2 can be naturally lifted to sets of contexts, in particular for Boxes. As an example : ↑ and ↓ can be lifted for Box B:
However not all context operators have natural extensions. Instead, the following three operations (join), (intersection), and (union) are defined [2] for sets of contexts introduced by Box.
We define these three operators ( , , and ) have equal precedence and have semantics analogous to relational algebra operators. Let B be a box expression and D be a dimension set. A formal syntax for box expression B is defined in Figure 1[b] (left column) and the precedence rules for box operators are defined in Figure 1[b] right column.
Context Regions A context region is a finite subset of a multidimensional space generated by a set of dimensions. Boxes can be used to represent different context regions. For example, Figure 2[a] shows two different context regions, which can be represented as follows:
defines a cone, and Box B 2 defines the upper half of hemisphere with the radius 3. If we restrict to integer indices, then the set of contexts defined by Box B 1 consists of all the points with integer coordinates within the cone, and the set of contexts defined by Box B 2 consists of all the points with integer coordinates within the hemisphere.
) refers to the region α 1 . The tag sets for clocks are reals. For discrete time modelled by multiple clocks the tag sets are integers, and regions become lattice points, vertices of convex regions.
Nested Contexts Nested contexts define the meta relation between different contexts. This is similar to Guha's definition of nested context [4]. In his definitions, nested context enables to nest ist(f , c) formulas, which define that formula f is true in context c, and ist(c i ist(c j , α)), ist(c k ist(c l . . . ist(c j α) . . .)) are all valid. In the former example ist(c i ist(c j , α)), context c i is outer or meta to context c j . Guha also provides entering and exiting actions to migrate the interpretation of formulas from contexts. Similarly, we provide @ * operator to navigate the evaluation of expressions between nested contexts.
of the predicate formula q(x, y, z) and write p(x, y) =↓ z q(x, y, z). Conversely, we say q(x, y, z) is a simple extension of p(x, y) and write p(x, y) z → q(x, y, z). In general, a predicate formula extended with s > 1 arguments can be inductively defined as follows:
and p 2 is an extension of the logic expression p 1 . It is easy to see that is an irreflexive partial order on B. We define a partially order chain b 1 b 2 . . . b k to be nested, and refer to the boxes in the chain as nested contexts.
We want to study the relationship between nested contexts and sets of expressions obtained by evaluating a given expression E at the boxes in the nested chain.
and E be an expression. Define the relation £ on the set {E@ * b 1 , E@ * b 2 , . . .} as follows:
It is easy to verify that c 1j and c 2j satisfy
. . b k is a chain of nested contexts, we get a corresponding chain of cascading expressions:
This rule gives the base for the reasoning and reducing rules for constraint programming solver mentioned in [9].
Contexts can be passed as parameters to functions.
define the context regions in the space generated by the dimensions ∆ 1 ∪ ∆ 2 . The context-dependent expression E is defined differently in different regions:
An application of Definition 6 is to use contexts as parameters in a function definition. Let f : X × Y × Z × C → W, where C is a set of contexts; and f (x, y, z, c), x ∈ X, y ∈ Y, z ∈ Z, c ∈ C, be defined such that for different context values, the function's definitions are different. For example, function f (x, y, z, c) is defined according to different context regions shown in Figure 2
The evaluation of functions f varies depending on the actual context value given as input when f is called.
Given contexts as input, context-dependent functions can be used to produce a new context as a result to achieve adaptation in context-aware system [9].
We define context dependency analogous to the functional dependency in relational data models.
Let ∆ = {X 1 , . . . , X k } be a dimension set. If there exists a function φ ij : f dimtotag (X i ) → f dimtotag (X j ), we say φ ij is a functional dependency in the set ∆. In general, a functional dependency exists in ∆, if A ⊂ ∆, B ⊂ ∆, A ∩ B = ∅, and there exists a function :
For a given functional dependency φ ij in ∆, we define dependent contexts as the set of contexts:
This definition is easy to generalize for the general functional dependency φ AB .
Dependent context effectively reduces the possible worlds that are relevant to evaluate expressions. As an example, let a function φ: V → ST be defined as follows:
Hence context of this form [P : s 1 , V : m 3 , ST : 1] need not be considered for evaluating expressions in the example.
Moreover, dependent contexts also help to represent context sets compactly. In [9], we proved the following: starting with a set S ∆ of contexts, whose dimensions are subsets of ∆ and a finite set of functional dependencies on ∆, we can represent S ∆ as an expression S ∆ = S ∆ k S ∆ k , where there is no dependency in S ∆ k and S ∆ k = b 1 b 2 . . . b k , each b i is a Box representing one dependency. Since a box has a compact representation, the representation for S ∆ given above is a compact way to manage the contexts in this S ∆ . The substitutions for tags in b 1 , . . . , b k are subject to dependencies. However, those tags corresponding to dimension in S ∆ k can be done freely. This is analogous to substitution principle in functional languages.
Lucx is a conservative extension of Lucid, with context becoming a first-class object in the language. This way, contexts can be manipulated, assigned values and passed as parameters dynamically.
The syntax of Lucx is shown below.
The difference between Lucx and original Lucid is highlighted in bold in the above syntax rules. The symbols @ and # are context navigation and query operators. The non-terminals E and Q respectively refer to expressions and definitions. The abstract semantics of evaluation in Lucx is D, P E : v, which means that in the definition environment D, and in the evaluation context P , expression E evaluates to v. The definition environment D retains the definitions of all of the identifiers that appear in a Lucid program. Formally, D is a partial function D : Id → IdEntry, where Id is the set of all possible identifiers and IdEntry has five possible kinds of value such as: Dimensions, Constants, Data Operators, Variables, and Functions [7]. The evaluation context P , is the result of P †c, where P is the initial evaluating context, c is the defined context expression, and the symbol †denotes the overriding function.
A complete operational semantics for Lucid is defined in [7]. The new semantic rules for Lucx are given below.
The evaluation rule for the navigation operator, E atc , which corresponds to the syntactic expression E @ E , evaluates E in context E , where E is a context defined in Section 3.1. The evaluation rule for the set navigation operator E ats , which corresponds to the syntactic expression E @ * S, evaluates E in a set of contexts S. Hence, the evaluation result should be a collection of results of evaluating E at each element of S. Semantically speaking, the symbol # is a nullary operator, which evaluates to the current evaluation context P. And the symbol . is a binary operator, whose left operand is an expression and the right operand is a single dimension. The semantic rule E tupid evaluates a tuple as a finite stream whose dimension is explicitly indicated as E in the corresponding syntax rule E 1 , . . . , E n E. Accordingly, the semantic rule E select picks up one element indexed by E from the tuple E . The semantic rule E box evaluates a Box to a set of contexts according to the definition in Section 3.3. f p (tag(P i ) i=1..m ) is a boolean function. The rule E set evaluates {E 1 , . . . , E m } to a set of contexts.
We give two examples.
1. The example models the problem of heat transfer in a solid. There is a metal rod which initially has temperature 0 and whose left-hand end touches a heat source with temperature 100. As the heat is transfered, the temperature at the various points of the rod changes. That is, the temperature depends on the time point and the spatial position on the rod. The following equations illustrate the temperature of the rod as a function of time and space (where k is a small constant related to the physical properties of the rod):
Temp t,0 = 100 Temp 0,s+1 = 0 The Lucx program that models the above equations and queries the temperature at the space 10 at time 10 is the following:
Temp @ [Time : 10, Space : 10] where Temp @ [Time : t + 1, Space : s
Temp@[Time : t, Space : 0] = 100 Temp@[Time : 0, Space : s + 1] = 0 end 2. Consider the problem of finding the solution in positive integers that satisfy the following constraints:
x 3 + y 3 + z 3 + u 3 = 100 x < u x + y = z The Lucx program is given below:
Eval.B1, B2, B3 (x , y , z , u ) = N where N = merge ( merge( merge(x, y), z), u) @ B 1 B 2 B 3 ; where merge(x, y) = if (x <= y) then x else y;
Implementing Lucx in GIPSY The GIPSY is an Intensional Programming investigation platform under development which allows the automated generation of compiler components for the different variants of the Lucid family of languages [6]. Currently, the compiler for Indexical Lucid, a variant of Lucid, has been implemented successfully in the GIPSY. Lucx is a conservative extension of Lucid. We will provide the Lucx parser and Lucx AST(Abstract Syntax Tree) translator as a Lucx front end to GIPSY. Lucx parser can be automatically generated using the JavaCC tool as the Indexical Lucid parser being obtained. In [9], we provide the translation rules for translating Lucx operators into Indexical Lucid operators. Combined with the translation rules for Indexical Lucid operators provided in [7], we achieve a two-pass Lucx AST translator. Once these two models are integrated into GIPSY, the programs written in Lucx will be compiled and run in GIPSY.
The notion of context is the cornerstone of the intensional programming paradigm. The previous versions of Lucid were merely using the notion of context of evaluation. They provided a single operator for the navigation in the context of evaluation, but did not provide a mechanism to represent and manipulate contexts as first class values.
The use of contexts as first class values increases the expressive power of the language by an order of magnitude. It allows the definition of aggregate contexts, which are a key feature to achieve efficiency of evaluation through granularization of the manipulated data. It also allows us to use the paradigm for agent communication by allowing the sharing and manipulation of multidimensional contextual information among agents [2]. In addition, the use of the paradigm for real-time reactive programming is shown in [8]. We are developing larger application programs that arise in constraint programming and in context-aware systems [9].
This work is supported by grants from the Natural Sciences and Engineering Research Council of Canada.