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 [
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. 2
Context in Intensional Programming Paradigm 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◦C.
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:
Ja Fe Mr Ap Ma Jn Jl Au Se Oc No De
Montreal F F F F T T T T T F F F E0 = Ottawa F F F T T T T T T F F F
Toronto F F T T T T T T T T F F
Vancouver F T T T T T T T T T T T
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 [
Lucid was a data-flow language and evolved into a Multidimensional Intensional
Programming Language [
Context Theory in Lucx 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. 3.1
Context Definition 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 = {d1, d2, . . . , dn} denote a finite set of dimension names. We associate with each di ∈ DIM a unique enumerable tag set Xi. Let TAG = {X1, . . . , Xr} denote the set of tag sets. There exists functions fdimtotag : DIM → TAG, such that the function fdimtotag associates with every di ∈ DIM exactly one tag Xj in TAG.
Definition 1 Consider the relations
Pi = {di} × fdimtotag(di) 1 ≤ i ≤ n A context C, given (DIM, fdimtotag), is a finite subset of Sn i=1 Pi. The degree of the context C is | Δ |, where Δ ⊂ DIM includes the dimensions that appear in C. A context is written using enumeration syntax, as [d1 : x1, . . . , dn : xn], where d1, . . . , dn are dimension names, and xi is the tag for dimension di. We say a context C is simple (s context), if (di, xi), (dj, xj) ∈ C ⇒ di 6= dj. A simple context C of degree 1 is called a micro (m context) context.
Example 1 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 {s1, . . . , sk}, where s1, . . . , sk are named sensory devices; and (3). Volume V with index set {m1, . . . , mq}, where m1, . . . , mq are named measuring devices. A context c = [ST : 1, P : s2, V : m3] for one stream σ may be interpreted as a reference to the tuple ht1, p2, v3i, where at the first sampling time t1 the value of volume measured by m3 is v3 and the value of pressure observed by the sensor s2 is p2. Supposing t1, p2, v3 ∈ 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 σ0 = p?tv . Such a reference will produce the result p2?v3 , which is the result of t1 evaluating the expression σ0 with the substitution [t 7→ t1; p 7→ p2; v 7→ v3]. In this case, the domain for the entities in the stream σ0 is R.
Several functions on contexts are predefined in [
Context Operators
In [
Example 2 illustrates an overall example for some of those operators.
Let c1 = [X : 2, X : 3, Y : 4],c2 = [X : 2, Y : 4, Z : 5], c3 = [Y : 2], D = {Y, Z}, Then c1 ⊕ c2 = [X : 2, Y : 4, Z : 5], c1 c2 = [X : 3], c1 ↓ D = [Y : 4], c1 u c2 = [X : 2, Y : 4], c1 t c2 = [X : 2, X : 3, Y : 4, Z : 5], c2 ↑ D = [X : 2], c2 c3 = {[X : 2, Y : 2, Z : 5], [X : 2, Y : 3, Z : 5], [X : 2, Y : 4, Z : 5]}, c3 * c2 = {[X : 2, Y : 2, Z : 5], [X : 2, Y : 3, Z : 5], [X : 2, Y : 4, Z : 5]}, c2/hY, 3i = [X : 2, Y : 3, Z : 5], c2 * c3 = ∅
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 [
Box and Box Operators
A context which is not a micro context or a simple context is called a non-simple
context. For example, context c4 = [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 [
syntax
precedence C ::= c | C = C | C ⊇ C | C ⊆ C | C | C | C/C | C ⊕ C | C C | C u C | C t C | C C | C * C | C ↓ D | C ↑ D 1. ↓, ↑, / 2. | 3. u, t 4. ⊕, 5. , * 6. =, ⊆, ⊇ (a) Rules for Context Expression syntax
precedence B ::= b | B | B | B B | B B | B B | B ↓ D | B ↑ D | B/hd, ti 1. ↓, ↑, / 2. | 3. , , (b) Rules for Box Expression Definition 2 Let Δ = {d1, . . . , dk}, where di ∈ DIM i = 1, . . . , k, and p is a predicate formula defined on the tuples of the relation Πd ∈Δ fdimtotag(d). The syntax
Box[Δ | p] = {s | s = [di1 : xi1 , . . . , dik : xik ]}, where the tuple (x1, . . . , xk), xi ∈ fdimtotag(di), i = 1, . . . k satisfy the predicate formula p, introduces a set S of contexts of degree k. For each context s ∈ S the values in tag(s) satisfy the predicate formula p.
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: B ↑ D = {c ↑ D | c ∈ B},
B ↓ D = {c ↓ D | c ∈ B}. However not all context operators have natural
extensions. Instead, the following three operations (join), (intersection), and (union)
are defined [
Let DIM = {X, Y , Z}, fdimtotag(X) = fdimtotag(Y ) = fdimtotag(Z) = N,
B1 = Box[X, Y | x, y ∈ N ∧ x + y = 5], B2 = Box[Y , Z | y, z ∈ N ∧ y = z2 ∧ z ≤ 3]. Then B1 = {[X : 1, Y : 4], [X : 2, Y : 3], [X : 3, Y : 2], [X : 4, Y : 1]}
B2 = {[Y : 1, Z : 1], [Y : 4, Z : 2], [Y : 9, Z : 3]}.
Hence B1 B2 = Box[X, Y , Z | x + y = 5 ∧ (y = z2 ∧ z ≤ 3)]
= {[X : 1, Y : 4, Z : 2], [X : 4, Y : 1, Z : 1]} B1 B2 = Box[Y | x + y = 5 ∧ (y = z2 ∧ z ≤ 3)] = {[Y : 1], [Y : 4]} B1 B2 = Box[X, Y , Z | x + y = 5 ∨ (y = z2 ∧ z ≤ 3)] = {[X : 1, Y : 4, Z : 1..3], [X : 2, Y : 3, Z : 1..3], [X : 3, Y : 2, Z : 1..3], [X : 4, Y : 1, Z : 1..3], [X : 1..3, Y : 1, Z : 1], [X : 2..4, Y : 4, Z : 2], [X : 1..4, Y : 9, Z : 3]} 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. 3.4
Context Category 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 represBe2nte=d aBsofxo[lXlo,wYs,:ZB1| x=2 +Byo2x+[Xz,2Y,≤Z 9 | ∧x2z +≥ z02]. ≤Box1B61 ∧dexfin=es a12 zco∧ne, zan≥d B0o]x, B2 defines the upper half of hemisphere with the radius 3. If we restrict to integer indices, then the set of contexts defined by Box B1 consists of all the points with integer coordinates within the cone, and the set of contexts defined by Box B2 consists of all the points with integer coordinates within the hemisphere.
B1
B2 (a) ent Regions
DifferContext
In timed systems having continuous time model, clock regions which are
equivalence classes of clock valuations arise when several clocks are used. These clock
regions are treated as context regions, and can be represented as boxes [
Definition 3 Let p(x, y) and q(x, y, z) be two predicate formulas. If ∀ a, b for which p(a, b) is true, and if ∃ c such that q(a, b, c) is true, then we call p(x, y) as a projection 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: x→r+s ps(x1, . . . , xr+s), where p0 ≡ p, ps ≡ q. 1. p(x1, . . . , xr) xr+1 q(x1, . . . , xr, xr+1)
→ 2. p(x1, . . . , xr) xr+1,...,xr+s q(x1, . . . , xr, . . . , xr+s)
−→ =Δ p0(x1, . . . , xr) x→r+1 p1(x1, . . . , xr, xr+1) x→r+2 p2(x1, . . . , xr+2) . . .
Definition 4 We define a relation @ on a set of boxes B as follows: for b1, b2 ∈ B, b1 = Box[Δ1 | p1], b2 = Box[Δ2 | p2], b1 @ b2 iff Δ1 ⊂ Δ2 and p2 is an extension of the logic expression p1. It is easy to see that @ is an irreflexive partial order on B. We define a partially order chain b1 @ b2 . . . @ bk 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. Definition 5 Let B = {b1, b2, . . .} be a finite set of boxes, bi = Box[Δi | pi], and E be an expression. Define the relation on the set {E@∗b1, E@∗b2, . . .} as follows:
This rule gives the base for the reasoning and reducing rules for constraint programming
solver mentioned in [
Context Dependent Expressions Contexts can be passed as parameters to functions. Definition 6 Let B1 = Box[Δ1 | p1], and B2 = Box[Δ2 | p2] define the context regions in the space generated by the dimensions Δ1 ∪ Δ2. The context-dependent expression E is defined differently in different regions: λ ·E = E1 in B1 B2
E2 in B2 B1 E3 in B1 u B2 μ ·E is defined to indicate corresponding context regions, namely, μ ·E = {B1 B2, B2 B1, B1 u B2}
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[a]. Hence μ ·f = {B1 B2, B2 B1, B1 u B2}, and λ ·f = {2x3 + y − 6, x + y2, z3 + y}. 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 [
Dependent Context We define context dependency analogous to the functional dependency in relational data models.
Definition 7 Let Δ = {X1, . . . , Xk} be a dimension set. If there exists a function φij : fdimtotag(Xi) → fdimtotag(Xj), 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 :
φAB : ΠXi∈Afdimtotag(Xi) → ΠXj∈Bfdimtotag(Xj).
For a given functional dependency φij in Δ, we define dependent contexts as the set of contexts:
SΔ = {c | dim(c) = Δ0 ∧ ({Xi, Xj} ⊆ Δ0 ⊆ Δ)} As an example, c = [Xi : a, Xj : φij(a)] ∈ SΔ, a ∈ fdimtotag(Xi). 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: φ(m1) = φ(m2) = 1; φ(m3) = φ(m4) = 2. Hence context of this form [P : s1, V : m3, ST : 1] need not be considered for evaluating expressions in the example.
Moreover, dependent contexts also help to represent context sets compactly. In [
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.
Syntax and Semantics of Lucx The syntax of Lucx is shown below.
E ::= id S ::= {E1, . . . , Em} | E(E1, . . . , En) | Box[E | E0] | if E then E0 else E00 Q ::= dimension id | # | id = E | E @ E0 | id(id1, . . . , idn) = E | [E1 : E01, . . . , En : E0n] | Q Q | hE1, . . . , EniE | select(E, E0) | E @∗ S | E where Q
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, P0 ` E : v, which means that in the definition
environment D, and in the evaluation context P0 , 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[
A complete operational semantics for Lucid is defined in [
Eat(c) : D, P ` E0 : P0 D, P0 ` E : v
D, P ` E @E0 : v E# :
D, P ` # : P E. : D, P ` E2 : id2 D(id2) = (dim)
D, P ` E1.E2 : tag(E1 ↓ {id2}) Etuple : D, P ` E : id D†[id 7→ (dim)] P †[id 7→ 0] D, P ` Ei : vi
D, P ` hE1, E2, . . . , EniE : v1 fby.id v2 fby.id . . . vn fby.id eod
D, P ` E : Δ Ebox : D(v0k:1..n) = (dim)
D, P ` Edj : idj Econtext : D, P ` Eij : vj
D(idj) = (dim)
P0 = P0 † [id1 7→ v1] † . . . † [idn 7→ vn]
D, P ` [Ed1 : Ei1 , Ed2 : Ei2 , . . . , Edn : Ein ] : P0
The evaluation rule for the navigation operator, Eatc , which corresponds to the syntactic expression E @ E0, evaluates E in context E0, where E0 is a context defined in Section 3.1. The evaluation rule for the set navigation operator Eats , 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 Etupid evaluates a tuple as a finite stream whose dimension is explicitly indicated as E in the corresponding syntax rule hE1, . . . , EniE. Accordingly, the semantic rule Eselect picks up one element indexed by E from the tuple E0. The semantic rule Ebox evaluates a Box to a set of contexts according to the definition in Section 3.3. fp(tag(Pi)i=1..m) is a boolean function. The rule Eset evaluates {E1, . . . , Em} to a set of contexts. Examples of Lucx Programs 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):
Tempt+1,s+1 = k × Tempt,s − (1 − 2 × k) × Tempt,s+1 + k × Tempt,s+2 Tempt,0 = 100
Temp0,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 + 1] = k × Temp @ [Time : t, Space : s] −(1 − 2 × k) × Temp @ [Time : t, Space : s + 1] +k × Temp @ [Time : t, Space : s + 2] Temp@[Time : t, Space : 0] = 100
Temp@[Time : 0, Space : s + 1] = 0
end
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 [
Conclusion 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 [