'$A Polymorphic Calculus for
Views and Object Sharing&Atsushi Ohori

Keishi Tajima

Kyoto University

University of Tokyo&Kyoto University%

'$Backgrounds (1/2)
IS-A Relation in Current OODBs
IS-A relation in current OODBs has two roles.
e.g. Employee IS-A P erson:• method inheritance — a method on P erson is also applicable toEmployee objects, and• extent inclusion — an instance of Employee is also included in aextent of P erson.
These two seem to be ad-hoc approximations to more
fundamental mechanisms of method and object sharing!

&1%

'$

Backgrounds (2/2)
Method Sharing by Polymorphic Type Inference
Polymorphic type inference for records can infer the most generalapplicability of the method.
e.g. in Machiavelli[SIGMOD89]:
fun wealthy S = select x·Name from x ∈ S where x·Salary > 100: {’a::[Name:’b, Salary:int]} →{’b}This provides us a more precise
framework for method sharing.

&2%

'$

Motivation
Object Sharing by General Predicate
Simple partial ordering is inadequate. e.g.:“define a new class F oreigner from Student and Employee”
A more direct and natural approach is:
to allow the programmer to specify desired object
sharing predicates between arbitrary classes.

&3%

'$

The Goal of This WorkWe develop a framework for• object sharing by general sharing predicate,• objects with views,— to be shared by multiple classes, an object should havemultiple views —and• integrate them into a polymorphic type inference system formethod sharing.

&4%

'$

Features of Our Language
1. Classes with Object Sharing• Class definitions include sharing specifications.
class S include Student as f1 where age > 20
include Employee as fn where age > 20 end• Recursive class can be defined.
Sharing relation can be cyclic.
2. Objects with Views• Views are defined by mapping functions
joe = [Name = “joe”, Sex = “male”, BirthY = 1968]
joe as [Name = x·Name, Age = 1994 − x·BirthY]• Uniform treatment for objects and views
&5%

'$

Our Strategy (1/2)
An “object” is internally an association of• a raw object — a record that has an identity,• a viewing function – to map the raw object to its view.

A “class” is internally an association of• an immediate extent — a set of immediate instances,• a sharing predicate — a function evaluated dynamically.

&6%

'$

Our Strategy (2/2)
To integrate “objects” with views and “classes” with object sharing
into a polymorphic type system, we
1. define the polymorphic core calculus similar to that ofMachiavelli,
2. extend the core to “objects”, and then to “classes”,
3. define the semantics of the extended language by giving atranslation to the core, and4. show the translation preserves typing.

&7%

'$

The Core Calculus
e ::= cτ | () | x | eq(e, e) | λx.e | (e e) | ﬁx x.e | let x = e in e end |[f, . . . , f ] | e·l | extract(e, l) | update(e, l, e) |{e, . . . , e} | union(e, e) | hom(e, e, e, e)l := e : for mutable fields• f in [f, . . . , f ] is one of:l = e : for immutable fields• a record has an identity.
• extract(r, l) extracts the L-value of a mutable l field.
The type system can infer principal type. e.g.
fun wealthy S = select x·Name from x ∈ S where x·Salary > 100: ∀a::U .∀b::[Name:a, Salary:int].{b}→{a}
&8%

'$

Extension for Objects with Views (1/3)
Expressions, Types, and Typing Rules
e ::= · · · | IDView(e) | (e as e) | query(e, e)| fuse(e, e) | relobj(l1 = e1, . . . , ln = en)τ ::= · · · | obj(τ )(object creation)

K, A  e : τ K ` τ :: [ ]K, A  IDView(e) : obj(τ )(view composition)

K, A  e1 : obj(τ1) K, A  e2 : τ1→τ2K, A  (e1 as e2) : obj(τ2)

K, A  e1 : τ1→τ2 K, A  e2 : obj(τ1)(query through view)
K, A  query(e1, e2) : τ2
&9%

'$

Extension for Objects with Views (2/3)
Examples of Views
Attribute renaming, hiding, derivation and access control
val joe = IDView([Name = ”Doe”,BirthY = 1955,Salary:= 2000,Bonus := 5000]): obj([Name = str, BirthY = int, Salary := int, Bonus := int])
val joeview = (joe as λx.[Name = x·Name,
Age = ThisYear - x·BirthY,
Income = x·Salary,Bonus := extract(x, Bonus)]): obj([Name = str, Age = int, Income = int, Bonus := int])
&10%

'$

Extension for Objects with Views (3/3)
Examples of Views (cont.)
Query on “objects” with views:
fun annual income p = (p·Income) ∗ 12 + p·Bonus: ∀a::[[Income = int, Bonus = int]].a→int
query(annual income, joeview): int
View update:
fun adjust bonus p = update(p, Bonus, p·Income ∗ 3)
: ∀a::[[Income = int, Bonus := int]].a→()query(adjust bonus, joeview): unit&11%

'$Classes and Object Sharing (1/2)
Expressions, Types, and Typing Rules
me ::= · · · | class S include C11, . . . , C1 1 as e1 where p1 · · ·include Cn1 , . . . , Cnmn as en where pn end| c-query(e, e) | insert(e, e) | delete(e, e)τ ::= · · · | class(τ )K, A  e : {obj(τ1)}→τ2 K, A  C : class(τ1)(cquery)
K, A  c-query(e, C) : τ2&12%

'$Classes and Object Sharing (2/2)
Examples of Classes
Staﬀ : class([Name = str, Sex = str, Salary := int])
Student : class([Name = str, Sex = str, Degree := int])
let FemaleMember = class {}include Staﬀ
as λs.[Name = s·Name, Category = ”staﬀ”]
where λs.(s·Sex = ”female”)
include Student
as λs.[Name = s·Name, Category = ”student”]
where λs.(s·Sex = ”female”) end: class([Name = str, Category = str])
&

13%

'$

Extension for Recursive Definition
We introduce a new construct for recursive definition.
let Staﬀ = class {} include FemaleMember as · · ·where · · · (select only staﬀs)
and Student = class {} include FemaleMember as · · ·where · · · (select only students)
and FemaleMember = class {}includes Staﬀ as · · ·where · · · (select only females)
include Student as · · ·where · · · (select only females)

&

14%

'$

Semantics of Recursive Classes

The semantics of recursive definitions can be defined as minimal
solution satisfying constraints.
This can be computed by simple searching with cycle avoidance.
Intuitively, the points are• cycle of definition occur only in from clauses.
• include clause never produces new identity.
• elements of sets of objects are collapsed using fuse(o1,o2)

&15%

'$

Semantics of the Extended Language
We define the precise semantics by giving a systematic translation:tr(IDView(e)) = (e, λx.x)
tr((e1 as e2)) = (tr(e1)·1, λx.(e2 (tr(e1)·2 x)))tr(query(e1, e2)) = (e1 (tr(e2)·2 tr(e2)·1))mtr(class S include C11, . . . , C1 1 as e1 where p1 include · · · end)
= [OwnExt:=S, Ext=λ().union(S, union(select · · ·))]
tr(c-query(e, C)) = (tr(e) (tr(C)·Ext ()))
..

&16%

'$

Properties of the Extended Language
The translation preserves typing. By this,
Proposition 1 The type system of the extended language is soundwith respect to the semantics given by the translation.
Furthermore,
Proposition 2 The type system of the extended language can stillinfer the principal type for any type consistent expression.

&17%

'$

Conclusions
We have• developed a framework for object with views and class with object
sharing• given a precise semantics for them• integrated those framework with a polymorphic type system
Some further investigations:• integrate the language with parametric classes with multiple
inheritance for object oriented programming• abstract characterization of views and classes.

&18%