From root Thu Jun 18 13:20:53 1992 Received: from vmd.cso.uiuc.edu by p300.cpl.uiuc.edu with SMTP id AA05514 (5.65c/IDA-1.3.4 for foote); Thu, 18 Jun 1992 13:20:51 -0500 Received: from Ulbvm.fnrs-nfwo.ac.be by vmd.cso.uiuc.edu (IBM VM SMTP V2R2) with BSMTP id 7556; Thu, 18 Jun 92 13:21:26 CDT Received: from BBRBFU60 (BSMTP) by Ulbvm.fnrs-nfwo.ac.be (Mailer R2.08) with BSMTP id 1408; Thu, 18 Jun 92 20:19:33 +0200 Received: from prog1.vub.ac.be by rc1.vub.ac.be (4.1/RC1-920604) id AA00929; Thu, 18 Jun 92 20:21:09 +0200 Return-Path: Received: by prog1.vub.ac.be (4.0/4.7) id AA28699; Thu, 18 Jun 92 20:07:25 +0200 Date: Thu, 18 Jun 92 20:07:25 +0200 From: prsteyae@prog1.vub.ac.be (Patrick R. Steyaert) Message-Id: <9206181807.AA28699@prog1.vub.ac.be> To: foote@p300.cpl.uiuc.edu Subject: ASCII version Status: R Here comes the ASCII version ! patrick. Towards a Calculus for Objects and its Reflective Variant Patrick Steyaert Free University Brussels, PROG - WE Pleinlaan 2, B1050 Brussels - Belgium prsteyae@vnet3.vub.ac.be abstract First, a calculus is constructed that models, in a direct way, the crucial features of object-oriented programming. Then, we propose an extention with behavioural and structural reflection. Behavioural and structural reflection are added independently of each other, but, support each other. The semantics of both the calculus and its extension are made clear by means of examples. Behavioural reflection is achieved by absorption and reification of the evaluation method typical for expressions (respectively by a quoting and its inverse, unquoting, operation). Evaluation is done in an explicitly given context (as well for reified as for absorbed evaluation methods), paying attention to make a distinction between object-level context and meta-level context. This leads in a natural way to the idea of having a stack of contexts (object-level meta1- level meta2-level ... ). Structural reflection is achieved by absorption and reification of the send method typical for objects. Special care is taken that one does not have to breach the encapsulation, that is inherent in the non-reflective calculus, in order to make use of structural reflection, an aspect that is ignored in most other work. a calculus for objects The intention is to lay out a calculus (a short overview of the reduction rules can be found in the appendix) that deals directly with two important aspects of object- oriented(based?) programming i.e. encapsulation or the binding of a public part to a private (encapsulated) part, and message passing. The calculus is inspired by the modelling of objects in lambda-calculus extended with records [Cardelli84][Wand89]. In view of adding reflection later on, we want a more 'direct' model of objects. The key feature of the calculus is that both the public part and the encapsulated part of an object are objects in their own right; unbound variables in public methods are seen as a form of private method invocation. The public part of an object can contain instance variables (public instance variables); the encapsulated part can contain methods (private methods). Message passing is restricted to unary message passing (no arguments). All argument passing to methods is done by adding extra instance variables, as will be shown later (blurring, somewhat, the difference between arguments and instance variables). This helps us to keep things simple. The objects used in the calculus are state less. It is not the intention of the calculus to model objects with state and object-identity, a priori. Records (simple objects) and record selection (message passing) have the following form: object message expressions result [] ([])x normal form x.1 (x.1)x -> 1 (x.1)y normal form [x.1; y.2; z.3] ([x.1; y.2; z.3])y -> 2 [x.a; y.b] ([x.a; y.b])y -> b Simple objects of this kind are constructed entirely of 'instance variable associations'. Free variables are bound via lexical scoping (as is hinted at in the last example). In order to model an object we introduce two extra concepts: 'method associations' and 'compound objects'. A compound object is the composition of a public part (mostly a simple object with method associations) and an encapsulated part (mostly a simple object with instance variable associations); we use the following notation: . Method associations (x#e) differ from instance variable associations (x.e) in their scoping: the free variables of a method association in the public part of a compound object, are bound via the encapsulated part of that compound object. Some examples: <[x#a; y#b], [a.3]> (<[x#a; y#b], [a.3]>)x evaluation of the body of method x in the encapsulated part -> (a.3)a -> 3 (<[x#a; y#b], [a.3]>)y evaluation of the body of method y in the encapsulated part -> (a.3)b ()x -> [k.([a.3; b.4])a; j.([a.3; b.4])b] -> [k.3; j.4] , [a.3; b.4]> (, [a.3; b.4]>)x -> -> The last two examples show how objects can be returned as a result of 'method invocation', and the effect on the binding of free variables. We can also pass objects to methods; as an example of this we show the construction of boolean values. The method 'foo' expects as input a condition: if#true true object if#false false object foo#()if object with 1 method:foo ()if,condition.if#true>)foo -> ()if -> 3 The most important advantage of the calculus, to model objects, over lamda-calculus with records is that both parts of a compound object can be, again, compound objects. This is essential on the one hand to model private methods, and on the other hand to have some form of curried binding of instance variables. The key insight is that an unbound variable in a selected method is seen as a message with an implicit receiver: the encapsulated part of the compound object of which the method was part of. The interaction between the encapsulated part and the public part of a compound object, is that a selected method from the public part sends its unbound variables to the encapsulated part and conversely that the encapsulated part is an object that contains methods for the unbound variables in a selected method from the public part. This is apparent in the reduction rule for message passing in its most general form: (<[x1.e1 ... xi#ei ... xn.en],d>)xi -> {d}ei Where {d}ei stands for the evaluation of an expression ei in a context d (we refer to the appendix for the exact definition). Note that the context, in which an expression is evaluated, can be an arbitrary object. The following example shows an object with method x#y having another object as encapsulated part. The other example shows an object with public part: and encapsulated part: c.3. The object responds only to the message x. As the first step in the example shows, the encapsulated part (c.3) has effect on the encapsulated part ([a.3; b#c]) of the public part only. > (>)x -> {}y == ()y -> {b.3}b == (b.3)b -> 3 <, c.3> (<, c.3>)x -> (>)x -> {<[a.3; b#c], c.3>}[k.a; j.b] == [k.(<[a.3; b#c], c.3>>)a; j.(<[a.3; b#c], c.3>>)b] -> [k.3; j.(c.3)c] -> [k.3; j.3] To give an example of the curried binding of instance variables the foo method from the boolean example above can also be written down as: )if, condition#condition> making more clear what the expected instance variables (or arguments) are. recursive structures Recursive structures are, similarly to recursion in lambda calculus, defined via self-application. The following is an object that returns an object totally equivalent to itself, on invocation of the method 'z'. The object z# is an object that expects an instance variable self that contains the object itself. , self.z#> (, self.z#>)z -> {self.z# == , self.z#> This construction accounts for the more classical forms of recursion found in object-oriented languages. It allows an object to send messages to itself via the self instance variable. In the presence of private methods we need another form of recursion. Recall that private methods are invoked without mentioning an explicit receiver. To model recursive private methods we need an object that has itself as encapsulated part. We define the operator Omega as Omega(V) -> . This results in objects of the form >>. The operator Omega can be written down as: Omega == ()x>, [V.V, O.x#)x>]>)x For an example of the use of the Omega operator we refer to the example of endless reflection later on. adding reflection In this section we extend the calculus with behavioural and structural reflection. Behavioural reflection is introduced by means of a quoting and an unquoting operation. It adheres to the sort of reflection resulting from the use of reifying functions, in the sense that it allows to extend the basic 'language' with new expression types without phenomena such as reflective overlap. The quoting operator (form: `e') allows one to get hold on expressions as first-class objects in, what is usually called, a meta-program. A quoted expression is an object that can be sent an eval message, given a context as argument. The following meta-program (the bold faced part forms the actual meta-program) evaluates the object-level program ()x in an, initially, empty context: (<`()x', c.[]>)eval -> 3 This is a typical example of meta-programming: allowing to manipulate programs as first-class objects, but, on the other hand, absorbing (leaving implicit) the evaluator for these programs. Due to the fact that the evaluation is done in an explicitly given context, care must be taken not to mix the object-level context (initially empty, later on containing z.3) and the meta-level context (the context in which the meta-program is evaluated). Nesting of quoted expressions will give rise to meta meta ... -level contexts. Unquoting (form: /e\) is exactly the reverse of quoting. Its purpose is to make expressions in which the evaluator is reified (made explicit). The expression being unquoted must evaluate to an object that acts as an expression, i.e. it has to have an 'eval' method. The unquoted expression is part of the meta-program, i.e. it is evaluated in the same context as the meta-program. We must keep track of both the object- level context and the meta context. This sort of 'layered' contexts are notated as: {c{d{...}}} where c is the object-level context, and d upto ... are the meta and metan contexts. Meta contexts play a role similar to the metacontinuations found in [Wand&Friedman88]. In the following example we construct an new expression-kind e that behaves as identifier z i.e. upon evaluation it looks up the identifier z in the given context. ()x', c.[]>)eval,e.>)foo -> {e.}(<`()x', c.[]>)eval -> {[] {e.}}()x -> {[z.3] {e.}}/e\ -> {e.}()eval -> (<, c.[z.3]>)eval -> 3 This leads us to a concept very similar to tower-architectures [Smith84]. We have layers of meta-programs, each with its associated context. Quoting adds an extra layer; unquoting pops back into a previous layer. {d{...}}(<`e',c.c>)eval -> {c{d{...}}}e {c{d{...}}}/e\ -> {d{...}}()eval To show that the level of reflection that can be achieved is not statically determined, we combine the above with recursion to get arbitrarily deep reflective programs. The expression Omega(e#(<`eval#/e\',c.[])eval) results in an new expression, when sent the message e, that reflects endlessly to compute its result. It is equivalent to an expression of the form: eval#/eval#/eval#/eval#/...\\\\ Structural reflection is achieved in analogy with behavioural reflection: the operator (?e) transforms an object into an object that can serve as its meta-object, i.e. an object that responds to the message 'send' with a pattern argument the same way the original object would respond to this pattern, and the reverse operator (^e) indicates that the object, the result of evaluating e, and understanding the send message, will act as meta-object for the object ^e. Notice that, in contrast with other object meta-object approaches, an object does not contain a reference to its meta-object but, rather, that object and meta-object are different views of communicating with an object. For example the following object responds to all possible messages with the result 3: ^ (^)x -> 3 Similar to quoting the following holds ($x transforms a pattern x into a string): (^e)x -> ()send (<^e, d>)x -> ()send ()send -> ()x To conclude with an example, we show the reflective implementation of the built-in message-expression. Notice that both behavioural and structural reflection are necessary for this example to work. The example shows the use of this new expression type by mimicking the expression (x#(z)y, z.y.3)x. Especially notice that the result of evaluating the receiver expression is an object-level object. It's meta-object is needed in order to be able to 'send' it the pattern instance variable. Both structural and behavioural reflection are needed in this simple example! )eval, p.pattern>)send, c#c>, [receiverExp#receiverExp; pattern#pattern]> (\,z.y.3>)x',c.[]>)eval, , [receiverExp#receiver; pattern#pattern] >)foo -> 3 conclusion We are convinced that the presented calculus provides a very expressive notation for exploring reflection in object- oriented programming. Further formalisation and exploration of possibilities awaits. references [Cardelli84] L. Cardelli : A semantics of multiple inheritance, Semantics of Data Types, volume 173 of Lecture Notes in Computer Science, pp. 51-688, Springer-Verlag. (1984) [Smith84] Brian Cantwell Smith : Reflection and Semantics in Lisp, Conf. Rec 11th ACM Symp on Principles of Programming Languages (Salt Lake City, January 1984, pp23-35. (1984) [Wand89] M. Wand : Type Inference for Record Concatenation and Multiple Inheritance, Proc. of the fourth IEEE Symposium on Logic in Computer Science, pp 92-97. (1989) [Wand&Friedman88] Mitchell Wand and Daniel P. Friedman : The Mystery of the Tower Revealed: A Non-Reflective Description of the Reflective Tower, Meta-Level Architectures and Reflection, P. Maes and D. Nardi (eds.) Elsevier Publishers B.V. (North-Holland). (1988) appendix concrete grammar: NonTerminal labels = { Expression Application Abstraction SimpleObject CompoundObject Association MethodAssociation VariableAssociation } Terminal labels = { Name } Start label = Expression Expression -> Application | Abstraction | Name Application -> "(" Expression ")" Name Abstraction -> SimpleObject | CompoundObject CompoundObject -> "<" Expression "," Expression ">" SimpleObject -> "[" [ Association {";" Association}] "]" Association -> MethodAssociation | VariableAssociation VariableAssociation -> Name "." Expression MethodAssociation -> Name "#" Expression reduction rules: x, xi : meta variable of sort Name e, f, g, c, ei : meta variable of sort Expression ai : meta variable of sort Association reduction rules for application (message sending) ([x1.e1 ... xi.ei ... xn.en])xi -> ei ([x1.e1 ... xi#ei ... xn.en])xi -> {[]}ei (<[x1.e1 ... xi.ei ... xn.en],d>)xi -> ei (<[x1.e1 ... xi#ei ... xn.en],d>)xi -> {d}ei <,g> -> > inductive definition of evaluating an expression e in a context c: {c}e {c}x == (c)x {c}[a1 ... an] == [{c}a1 ... {c}an] {c}x.e == x.{c}e {c}x#e == x#e {c} == <{c}e, {c}f> {c}(e)x == ({c}e)x