The Set of Equations to Evaluate Objects
Larissa Ismailova

arXiv:cs/0106013v1 [cs.LO] 8 Jun 2001

Vorotnikovsky per, 7, bld. 4
Institute for Contemporary Education “JurInfoR-MSU”
Moscow, 103006, Russia
lyui@jmsuice.msk.ru

Abstract
The notion of an equational shell is studied to involve the objects and their environment. Appropriate methods are studied as valid embeddings
of refined objects. The refinement process determines the linkages between the variety of possible
representations giving rise to variants of computations. The case study is equipped with the adjusted equational systems that validate the initial
applicative framework.

1 Introduction
One of the aims of this extended abstract is to revisit the
known ideas how to evalute the expression using the applicative computational system. Computation is sure to become one of the dominant trend in computer research especially to carry out object derivation processes.
Objects. The remarks here can be taken as a suggestion
to group numerous aspects of ‘object’ to result in a general computational framework that gives a suitable scheme.
This scheme can be useful as a primitive frame to put important ideas of evaluation in a certain order.
Representation. Applications involve the excessively
complicated representations of objects that are equipped
with the methods. An idea of object generalizes the experimental or theoretical observations concerning the behaviour of the selfcontained couples of data. Among other
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial
advantage, the CSIT copyright notice and the title of the publication and
its date appear, and notice is given that copying is by permission of the
Institute for Contemporary Education JMSUICE. To copy otherwise, or to
republish, requires a fee and/or special permission from the JMSUICE.

Proceedings of the Workshop on Computer Science and Information Technologies CSIT’2001
Ufa, Yangantau, Russia, 2001

representations the ‘data’ is less of all understood. Attempts to capture the most important features of data lead
to various mathematical ideas that are distant from the selected model of computation and result in a spectrum of
far distant models. The proposals here are to fill the gaps
between them.
Combinatory logic. Combinators represent the basic
properties of functions, and combinatory logic represents a
theory of functions over arbitrary objects. The last notion
is significant to generate flexible data models. Even more:
combinatory logic is known as a sound amount of theoretical and applied knowledge related to the ground nature of
objects. It supports: (1) basic representation of arbitrary
objects, (2) computational ideas with the objects, (3) integrity of both syntax and semantic.
Thus combinatory logic involves those entities that combine both syntax and semantical properties at the same
time. This was known to computer science theoreticians,
but was not widely used in applications at almost any scale.
Valid mathematical objects could be embedded into
combinatory logic. As embedding of an object is the main
verification procedure within combinatory logic then it is
ready made for compiling an arbitrary object into ‘computational instructions’ that in turn are combinators.
Those observations enforce the researcher to establish
the regular scheme to reconstruct all the vital entities by
the objects with useful mathematical properties. In applications this is known as determining the method.
A brief outline of the refinement is observed as follows.
Imagine the fixed class of primary and derived objects that
is prescribed by the set of equations. The proposal is to
define the properties of the objects by adjusting the initial
set. The effect observed tends to capture more meaning by
the refined objects, and the process of refinement evolves
along distinct computational methods.
The outline of this extended abstract is as follows. The
first and second Sections contain a suitable formulation of
a (higher order) theory of functions. It is based on combinatory logic and the relative computation theories referred

Workshop on Computer Science and Information Technologies CSIT’2001, Ufa, Yangantau, Russia, 2001

1

as shell, or conceptual theory. The process of refinement
is covered mainly in the third Section. The connections of
applicative and imperative modes of computation are explicated. The refined objects are embedded into the shell.

2 Postulates
To carry on with computation shell the minimal set of equations has to be postulated. An easy start gives the triple of
primary objects I, K, S and the metaoperator of application. This triple is power to maintain an applicative computation system with the higher order functions.
2.1 Applicative system

It is also object generating operator but it ranges over variables and objects. After that the previous definition of an
object may be augmented by the additional step: (iii) If x
is a variable, a is an object then λx.a, or (λx.a) is the object.
For convenience the agreement is added – the left associated parentheses may be demote (or remote) if needed.
The recent abstraction operator would be avoided.
2.3 Basis
To avoid the excessive objects the basis of disassembling
is needed. The following metatheorem validates the triple
I, K, S to be the basis.

Let I, K, S to be the (mathematical) objects. Also an infinite set of the indeterminants is added to support the supply
of variables. All the variables are included into the class of
objects. The objects determine the set of generic objects,
or atoms. The definition of derived objects is as follows by
induction on the complexity.

Metatheorem 2.1 (Disassembling) Any object λx.M
may be disassembled by case studying (according to induction on complexity):

Definition 2.1 (Objects) (i) I, K, S and the variables are
the objects. (ii) If a, b are the objects so is (a b).

In fact, this metatheorem determines the primary basis.

The step of induction needs the intuitive understanding.
Thus, the binary application operator (· ·) is taken into
game:
(· ·) : object × object → object.
It is the object generating operator that ranges over the objects. A first object is viewed as the ‘function’ while the
second is the ‘argument’. Hence the application operator
enables function to be applied to an argument that results
in a generating of some new object, or result of applying
function to its argument, and without application there is
no chance to take a resulting value.
To compare objects with other objects some (binary) relation is to be defined. Usually this relation is referred as
the conversion and is determined by the postulates (CL):
(I) Ia = a, (K) Kab = a, (S) Sabc = ac(bc),
a = b, b = c
a=b
, (τ )
,
b=a
a=c
a=b
a=b
,
(ν)
,
(µ)
ca = cb
ac = bc
where a, b, c indicate the arbitrary objects and ‘=’ is the
conversion relation.
(σ) a = a, (ρ)

2.2 Alternative formulation
Note that the class of objects above has the unique metaoperator, namely application. For convenience the second
metaoperator of abstraction would be added:
(λ · .·) :

2

variable × object → object.

(i) λx.x = I;
(ii) λx.y = Ky, y 6= x;
(iii) λx.M ′ M ′′ = S(λx.M ′ )(λx.M ′′ ).

3 Creating a shell
To verify the useful properties of basis I, K, S consider an
example of embedding. To be more rigorous add to postulates (CL) above the following schemes:
(α)
(β)
(ξ)
(η)

λx.a = λy.[y/x]a, y∈a (congruency);
(λx.a)b = [b/x]a (substitution);
a=b
;
λx.a = λx.b
λx.bx = b, x∈b.

(Note that (η) determines b as a concept.) The extended set
of postulates will be referred as (CLηξ).
3.1 Restrictions
The (CLηξ) formulation is given equationally, i.e. the binary relation ‘=’ of conversion can be specified as a kind
of equality. The additional equations seem to capture more
features of practically helpful objects. Up to the current
stage the consideration was purely syntactical. Now an attempt to generate ‘the embedded applications’ that essentially contain semantics will be done.
For purely mathematical reasons the additional (and not
generic) combinators would simplify the notations. Here
some combinators are axiomatized by the following equations:
Ix = x, Cxyz = xzy, Bxyz = x(yz),
Kxy = x, Sxyz = xz(yz),
Dxy ≡ [x, y] ≡ λr.rxy, < f, g >≡ λt.[f t, gt],
Φxyzw = x(yw)(zw), Ψxyzw = x(yz)(yw),
B2 ≡ BBB, C2 xyzw = xwyz,
Curry ≡ λh.λxy.h[x, y], p[x, y] = x, q[x, y] = y.

The Set of Equations to Evaluate Objects

They will be used below to refine the properties of the initial shell.
3.2 Application
Consider the set (CLηξ) of postulates with the additional
equation:
B = Ψ(Φ I)

(·(·) =)

The resulting set will be referred as (CLηξ) + (·(·) =).
To study the expressive power of this conceptual equation
take the indeterminants V, M, N, ρ (possibly, variables,
or, at least, objects).
The left part application immediately gives:
(B)

BVM N ρ = V(M N )ρ ≡k M N k ρ
with the agreement V(·) ≡ k · k, that enables V as evaluation mapping. The right part derivation results in
Ψ(Φ I)VM N ρ

(Ψ)

=

(Φ)

=

(I)

=

Φ I(VM )(VN )ρ

is derived. Discovering the conceptual equations (·(·) =)
and ([·, ·] =), as may be shown below, refines the properties of the initial shell (CL) up to computational model of
general purpose.
For explicit studying of (CLηξ) and (CLηξ) + (·(·) =
) + ([·, ·] =) computational properties the refined (and
partially conversed) consideration would be helpful. The
concepts of main interest are constants that gives rise to
the object constructor.
3.4 Constant object
Often the formal systems involve the constants. The notion or idea of a constant is assumed to be intuitively clear.
When the constants are viewed as the relative entities with
respect to some presupposed objects this idea is not so selfevident. Let the valuation V and the environment ρ are selected to be the point of relativization.
Definition 3.1 (constant object) K is defined to be the
constant object relative to the valuation V and the environment ρ if and only if it is not dependent on the valuation
V and the environment ρ:

I(VM )ρ(VN ρ)
k K k ρ ≡ VKρ = K

kM kρ(kN kρ)

(K)

Thus the equation (K) captures some important aspects and
does enrich our intuitive idea of a constant. Moreover, provided V and ρ are as above and K is a constant object we
have to assume for arbitrary object x:

The direct observation gives the equation
kM N kρ = kM kρ(kN kρ)
that is implied by (·(·) =).

K(Vxρ)
3.3 Ordered pair
Consider the equation
CB2 D = Ψ(Φ D)

([·, ·] =)

in a context of (CLηξ), i.e. use the augmented shell
(CLηξ) + ([·, ·] =). The left part concept for V, M, N, ρ
generates the conversions as follows:
CB2 DVM N ρ

(C)

=

(B2 )

=

(D)

=

B2 VDM N ρ
V(DM N )ρ
k[M, N ]kρ,

and the right part gives:
Ψ(Φ D)VM N ρ

(Ψ)

=

(Φ)

=

(D)

=

ΦD(VM )(VN )ρ
D(VM ρ)(VN ρ)

= (VKρ)(Vxρ)
= V(Kx)ρ.

by (K)

The last equation reflects a very natural principle that ‘the
valuation of application is the application of valuations’.
Similarly, one concludes:
(Vxρ)K

= (Vxρ)(VKρ)
= V(xK)ρ.

by (K))

The observations being accumulated result is the following
working rule: the constant is extracted through the valuation within some environment. The importance of the equation (K) erases a special equational principle of constant
(K). Actually, it would be better to construe the equation
VKρ = CVρK for the combinator C, thus the principle (K)
would be reformulated as CVρK = K = IK.
Let K be constructed as a variable by means of (CLηξ).
Then the equation (K =) is derivable:
CVρ = I

(K =)

[kM kρ, kN kρ].

Thus the equation
k[M, N ]kρ = [kM kρ, kN kρ]

This equation is intended in the desirable property of being
a constant. On the other hand using the equations
VKρ = K = KKρ,

Workshop on Computer Science and Information Technologies CSIT’2001, Ufa, Yangantau, Russia, 2001

3

and solving the equation (K =) for the evaluation V one obtains V = K. The immediate consequence of this equation
gives
k K k ρ =′ Kρ,

4 Equational notation
Now let apply the computational principles to the combinators. Suppose V, M, N, ρ are the variables.
k MN k ρ

and hence k K k=′ K for ′ = K. The symbol ‘ ′ ’ is the
quotation function that is analogous to the function quote in
LISP . For this solution of the equation (K) the following
conclusion is valid:
the evaluation K gives the ‘constant’ computational system,
i.e. evaluation views all the objects as ordinary constants.

=
=
=
=

(k M k ρ)(k N k ρ)
V(M N )ρ = (VM ρ)(VN ρ)
BVM N ρ = ΦI(VM )(VN )ρ
Ψ(ΦI)VM N ρ.

From the equation BVM N ρ = Ψ(ΦI)VM N ρ given above
the characteristic equation (·(·) =) is derivable:
B = Ψ(ΦI)

3.5 Object constructor
3.5.1 Valuation of application
Let x, y be the objects evaluated as follows:
k xy k ρ =k (p[x, y])(q[x, y]) k ρ
=k Spq[x, y] k ρ
= Spq(k [x, y] k ρ)
= Spq[k x k ρ, k y k ρ]
= (p[k x k ρ, k y k ρ])(q[k x k ρ, k y k ρ])
= (k x k ρ)(k y k ρ)

(S)
(K)
([·, ·])
(S)
(p, q)

Here: S is a combinator, p and q are the first and second
projections respectively. The principles (K) and the ‘valuation of pair’ are used in this derivation. Therefore the
principle ‘valuation of application’ is derivable from the
principles (K) and ‘valuation of pair’.
3.5.2 Valuation of pair
Let to analyze separately the derivation of principle the
‘valuation of pair’. The steps are analogous to those from
the above:
k [x, y] k ρ

≡
=
=
=

k Dxy k ρ
k Dx k ρ(k y k ρ)
(·(·))
D(k x k ρ)(k y k ρ) (K)
[k x k ρ, k y k ρ]
(D)

Here: D is a pairing combinator. The principle ‘valuation
of pair’ is derived from the‘valuation of application’ and
(K). Hence the principle ‘valuation of pair’ is derivable
from the principles (K) and ‘valuation of application’.
3.5.3 Redundancy of computational principles
As was observed above the principles (K), ·(·) and [·, ·] are
mutually dependent. Thus some redundant entities would
be eliminated. The possible postulates are the principles as
follows:
(1) k K k ρ = K;
(2) either ‘valuation of application’ or ‘valuation of
pair’.

4

(·(·) =)

This equation is understood as the equational notation for
the principle ‘evaluation of application’ whereas V is the
valuation, M, N are the objects, and ρ is the environment
or assignment.
The same reasons are applied to the equational notation of
the ‘evaluation of pair’:
k [M, N ] k ρ

=
=
=
=
=

[k M k ρ, k N k ρ]
V[M, N ]ρ = [VM ρ, VN ρ]
Curry VM N ρ = D(VM ρ)(VN ρ)
ΦD(VM )(VN )ρ
Ψ(ΦD)VM N ρ

The immediate consequence is the equation ([·, ·] =):
Curry = Ψ(ΦD)

([·, ·] =)

The modified equation takes into account Curry = CB2 D.
Thus
CB2 D = Ψ(ΦD)

([·, ·] =)

4.1 Modified equation to evaluate the application
The following observation would be fruitful for further
derivations. The evaluation of k xy k ρ is likely to involve the definition of ε. From xy = ε[x, y] the following
equations are valid:
k xy k ρ

=
=
=
=

k ε[x, y] k ρ
ε(k [x, y] k ρ)
ε[k x k ρ, k y k ρ] (by [·, ·])
(k x k ρ)(k y k ρ) (by ε)

4.2 Currying, application and product
Let z be equal to the ordered pair i.e. z = [u, v]. Of course,
from the equations u = pz and v = qz we derive z =
[pz, qz] =< p, q > z. Having in mind the equation z = Iz
and ignoring the type considerations it is easy to show:
< p, q >= I

(× =)

Suppose h = ε in the definition h[x, y] = Curry h xy.
The immediate consequence is the following:
ε[x, y] = xy = Curry ε xy

The Set of Equations to Evaluate Objects

References

Adding the equation xy = I xy it is easy to show:
Curry ε = I
The equation above interconnects the currying Curry and
the explicit application ε. The following is derivable from
the equation (× =):
hz

=
=
=
=
=

h[pz, qz]
Curry h(pz)(qz)
(Curry h ◦ p)z(qz)
ε[(Curry h ◦ p)z, qz]
(ε◦ < Curry h ◦ p, q >)z,

(by (× =))
(by ◦)
(by ε)
(by < ·, · >)

For arbitrary variable z in the equations above one concludes:
h = ε◦ < Curry h ◦ p, q >

([·, ·])

The last equation gives characteristics of the computations
with the ordered pairs.
The modified derivation gives the following:
kxy

= ε[kx, y]
= (ε◦ < k ◦ p, q >)[x, y]
= Curry(ε◦ < k ◦ p, q >)xy

[1] S. Clue, C. Delobel, A general framework for the optimization of object-oriented queries, In Proc. SIGMOD,
San Diego, California, USA, June 1992, pp. 383-392
[2] G. Cousineau, P.-L. Curien, M. Mauny, The categorical abstract machine. LNCS, 201, Functional programming languages computer architecture, 1985, pp. 5064
[3] D.S. Scott, Lambda calculus: some models, some
philosophy, The Kleene Symposium, Barwise, J., et
al.(eds.), Studies in Logic 101, North– Holland, 1980,
pp.381-421
[4] V.E. Wolfengagen, Computational aspects of data objects, Proceedings of the workshop on advances in
database and information systems, ADBIS’93, May
11-14, Moscow, 1993, pp. 1-12
[5] V.E. Wolfengagen. Event driven objects. In V. Wolfengagen and Ch. Freytag, editors, Proceedings of the 1st International Workshop on Computer Science and
Information Technologies (CSIT’99), Moscow, Russia,
January, 18–22, 1999. JurInfoR-MSU Press, University Press of MEPhI.

The derivation above generates the equation (·(·)):
k = Curry(ε◦ < k ◦ p, q >)

(·(·))

that characterizes the computations with the applications.
Combinators and combinatory logics produce some additional entities e.g. product and coproduct.

Conclusions
Main results are briefly summarized as follows.
1. Varying with different researches the nature of ‘object’ from a computational point of view would be captured, represented and embedded into a kind of primitive
frame. This scheme operates within a theory of functions
concerning combinatory logic and generates a primary conceptual shell.
2. Combinators give a sound substrate to produce a data
object model. The objects in use inherit both syntax and
semantics of the initial idea of object. This leads to and
object-as-functor computations and generates a refinement
process to capture the methods for individual objects.
3. It could be shown that the concepts are embedded into
the shell and inherit the logical properties of the objects.
The higher order theory (with em the descriptions) is in
use.
4. The refinement process suits the equational conditions. The distinct methods are to be studied within an
equational framework.

Workshop on Computer Science and Information Technologies CSIT’2001, Ufa, Yangantau, Russia, 2001

5

