%%Page: 1 1
1 0 bop 8519 12841 a Fs(Demeter:)778 b(A)577 b(CASE)h(Study)h(of)f
(Soft)-50 b(w)g(are)580 b(Gro)-50 b(wth)13946 15276 y(Through)579
b(P)-50 b(arameterized)580 b(Classes)16477 18486 y Fr(Karl)435
b(J.)f(Lieb)36 b(erherr,)432 b(Arth)-36 b(ur)433 b(J.)h(Riel)10743
20036 y(Northeastern)f(Univ)-36 b(ersit)g(y)-108 b(,)434
b(College)i(of)e(Computer)f(Science)13791 21586 y(360)i(Hun)-36
b(tington)432 b(Av)-36 b(en)g(ue,)434 b(Boston)f(MA)h(02115)20695
24191 y(Decem)-36 b(b)36 b(er)433 b(14,)i(2004)17844
28287 y Fq(Cop)-31 b(yrigh)g(t)23351 28254 y(c)23043
28287 y Fp(\015)p Fq(1988)371 b(Karl)f(Lieb)31 b(erherr)23814
30611 y Fo(Abstract)11277 32346 y Fn(The)331 b Fm(D)28
b(emeter)17434 31923 y Fl(T)108 b(M)19257 32346 y Fn(system)332
b(is)f(a)f(CASE)g(\(Computer-Aided)h(Soft)-28 b(w)g(are)329
b(Engi-)9741 33564 y(neering\))265 b(to)28 b(ol)265 b(designed)f(for)f
(the)i(dev)-28 b(elopmen)g(t)265 b(of)f(large)g(soft)-28
b(w)g(are)262 b(pro)57 b(jects)264 b(using)9741 34782
y(a)307 b(new)g(soft)-28 b(w)g(are)305 b(design)j(metho)28
b(dology)308 b(whic)-28 b(h)307 b(fo)28 b(cuses)307 b(on)g(gro)-28
b(wing)305 b(rather)i(than)9741 35999 y(building)382
b(soft)-28 b(w)g(are.)574 b(W)-85 b(e)382 b(describ)28
b(e)382 b(the)g(soft)-28 b(w)g(are)379 b(dev)-28 b(elopmen)g(t)383
b(pro)28 b(cess)381 b(as)g(one)9741 37217 y(of)430 b(gro)-28
b(wth)429 b(and)h(ev)-28 b(olution)432 b(as)e(opp)28
b(osed)430 b(to)h(building)g(and)f(rebuilding)h(b)28
b(ecause)9741 38435 y(most)422 b(complex)g(ob)57 b(jects)422
b(in)f(the)h(real)f(w)-28 b(orld)420 b(are)i(gro)-28
b(wn)419 b(and)i(not)g(built.)696 b(Since)9741 39652
y(soft)-28 b(w)g(are)302 b(design)i(is)g(ob)-28 b(viously)304
b(a)g(complex)h(pro)28 b(cess)303 b(this)h(new)g(paradigm)f(ma)-28
b(y)304 b(b)28 b(e)9741 40870 y(helpful)390 b(in)f(unra)-28
b(v)g(eling)388 b(some)i(of)f(the)g(problems)g(asso)28
b(ciated)390 b(with)f(curren)-28 b(t)387 b(soft-)9741
42088 y(w)-28 b(are)308 b(design)h(practices.)445 b(Demeter)311
b(b)28 b(egins)309 b(b)-28 b(y)309 b(pro)-28 b(viding)309
b(an)f(ideal)i(en)-28 b(vironmen)g(t)9741 43305 y(for)428
b(the)i(sprouting)e(and)h(n)-28 b(uturing)428 b(of)g(a)h(seed)h
(\(class)f(dictionary\))h(in)-28 b(to)429 b(a)g(plan)-28
b(t)9741 44523 y(\(large)497 b(scale)f(soft)-28 b(w)g(are)494
b(pro)57 b(ject\).)919 b(In)496 b(addition,)535 b(through)495
b(the)h(com)-28 b(bined)496 b(use)9741 45741 y(of)c(ob)57
b(ject-orien)-28 b(ted)492 b(programming)f(tec)-28 b(hnology)-85
b(,)530 b(and)491 b(parameterized)i(classes,)9741 46958
y(Demeter)323 b(pro)-28 b(vides)321 b(a)h(facilit)-28
b(y)322 b(for)f(the)h(reuse)f(of)g(soft)-28 b(w)g(are)320
b(whic)-28 b(h)321 b(w)-28 b(as)320 b(dev)-28 b(elop)28
b(ed)9741 48176 y(in)342 b(previous)f(soft)-28 b(w)g(are)340
b(pro)57 b(jects.)6974 50168 y Fq(A)369 b(short)g(form)h(of)g(this)f
(pap)31 b(er)369 b(w)-31 b(as)370 b(published)f(in)h([LR88)q(].)8634
52604 y Fp(\017)554 b Fq(T)-92 b(o)324 b(app)31 b(ear)324
b(in)g Fk(Journal)354 b(of)g(OBJECT-ORIENTED)f(PR)-28
b(OGRAMMING)p Fq(,)324 b(V)-92 b(ol.1,)9741 53932 y(No.3,)371
b(1988.)25792 68632 y(1)p eop
%%Page: 2 2
2 1 bop 6974 4317 a Fj(1)1107 b(INTR)-31 b(ODUCTION)26937
b Fq(2)6974 8192 y Fi(1)1793 b(In)-50 b(tro)50 b(duction)6974
10616 y Fq(The)487 b(primary)g(purp)31 b(ose)486 b(of)i(the)f
Fh(D)31 b(emeter)25778 10214 y Fg(T)119 b(M)27890 10616
y Fq(system)488 b(is)e(to)i(pro)-31 b(vide)488 b(a)f(medium)h(for)6974
11944 y(e\016cien)-31 b(t)536 b(gro)-31 b(wth)537 b(and)e(ev)-31
b(olution)538 b(of)d(large)h(scale)f(soft)-31 b(w)g(are)537
b(pro)61 b(jects.)990 b(W)-92 b(e)535 b(describ)31 b(e)6974
13273 y(the)466 b(soft)-31 b(w)g(are)467 b(dev)-31 b(elopmen)g(t)468
b(pro)31 b(cess)464 b(as)i(one)g(of)g(gro)-31 b(wth)467
b(and)f(ev)-31 b(olution)468 b(as)e(opp)31 b(osed)6974
14601 y(to)481 b(building)h(and)f(rebuilding)h(b)31 b(ecause)480
b(most)h(complex)h(ob)61 b(jects)482 b(with)f(few)g(rep)31
b(etitiv)-31 b(e)6974 15929 y(building)371 b(blo)31 b(c)-31
b(ks)369 b(are)g(gro)-31 b(wn)371 b(and)e(not)h(built)g([Mil71)s(])f
([Bro87)r(].)493 b(Examples)370 b(of)g(these)f(are)6974
17258 y(plan)-31 b(t)410 b(and)e(animal)i(life.)611 b(Soft)-31
b(w)g(are,)420 b(b)31 b(eing)409 b(a)g(v)-31 b(ery)408
b(complex)i(creature,)418 b(should)408 b(not)h(b)31 b(e)6974
18586 y(built)306 b(from)f(bits)h(and)f(pieces)f(of)i(inanimate)h(co)31
b(de)305 b(whic)-31 b(h)306 b(is)f(sewn)f(together)i(and)f(sho)31
b(c)-31 b(k)g(ed)6974 19915 y(in)g(to)456 b(life)g(with)g(a)f(marathon)
i(session)d(of)i(debugging.)751 b(A)455 b(creature)g(created)g(in)g
(suc)-31 b(h)454 b(a)6974 21243 y(fashion)513 b(is)e(assured)g(of)h
(sharing)g(the)g(same)g(fatal)i(\015a)-31 b(ws)512 b(as)f(other)h
(creatures)g(created)6974 22571 y(in)464 b(this)g(fashion)h(\(e.g.)778
b(the)464 b(F)-92 b(rank)-31 b(enstein)25538 22170 y
Ff(1)26498 22571 y Fq(monster\).)778 b(Instead,)488 b(the)464
b(soft)-31 b(w)g(are)465 b(plan)-31 b(t)6974 23900 y(should)486
b(b)31 b(e)485 b(gro)-31 b(wn)487 b(from)f(a)g(small)h(but)e(animate)j
(sprout.)842 b(A)-31 b(t)487 b(eac)-31 b(h)486 b(stage)g(of)g(gro)-31
b(wth)6974 25228 y(the)424 b(creature)g(will)i(b)31 b(ecome)425
b(more)f(complex)i(but)f(will)h(alw)-31 b(a)g(ys)426
b(exhibit)g(c)-31 b(haracteristics)6974 26556 y(appropriate)370
b(for)g(that)g(stage)g(of)g(dev)-31 b(elopmen)g(t.)8634
27885 y(Demeter,)370 b(appropriately)h(named)e(for)h(the)f(Greek)f(go)
31 b(ddess)369 b(of)g(the)h(earth,)f(pro)-31 b(vides)6974
29213 y(an)351 b(ideal)h(en)-31 b(vironmen)g(t)352 b(for)f(the)g(plan)
-31 b(ting)353 b(of)f(a)f(small)h(protot)-31 b(yp)31
b(e)352 b(system)f(\(sprout\))h(and)6974 30541 y(its)361
b(n)-31 b(urturing)361 b(in)-31 b(to)362 b(a)f(fully)h(dev)-31
b(elop)31 b(ed)362 b(soft)-31 b(w)g(are)362 b(system.)490
b(In)360 b(addition,)365 b(Demeter)c(pro-)6974 31870
y(vides)384 b(the)h(necessary)e(facilities)k(for)d(grafting)j(whole)e
(or)f(part)h(of)g(previously)g(dev)-31 b(elop)31 b(ed)6974
33198 y(soft)-31 b(w)g(are)305 b(systems)d(to)i(the)g(new)f(system)g
(or)g(ev)-31 b(en)303 b(grafting)j(the)d(new)g(system)g(on)-31
b(to)305 b(a)e(suit-)6974 34526 y(ably)330 b(dev)-31
b(elop)31 b(ed)330 b(ro)31 b(ot)329 b(sto)31 b(c)-31
b(k)330 b(\(a)g(parameterized)g(class\).)480 b(The)329
b(Demeter)g(system)g(creates)6974 35855 y(suc)-31 b(h)299
b(an)i(en)-31 b(vironmen)g(t)302 b(b)-31 b(y)300 b(marrying)h(ob)61
b(ject-orien)-31 b(ted)303 b(programming)f(tec)-31 b(hniques)301
b(with)6974 37183 y(a)431 b(common)i(data)f(structure)e(description)i
(language)h(and)f(the)f(concept)g(of)h(parameter-)6974
38511 y(ized)445 b(class.)721 b(Through)446 b(the)g(use)e(of)i(this)g
(en)-31 b(vironmen)g(t,)466 b(large)446 b(soft)-31 b(w)g(are)447
b(en)-31 b(vironmen)g(ts)6974 39840 y(can)353 b(b)31
b(e)352 b(gro)-31 b(wn)354 b(from)f(h)-31 b(um)g(ble)354
b(b)31 b(eginnings,)357 b(b)31 b(orro)-31 b(wing)354
b(at)g(eac)-31 b(h)353 b(stage)g(of)g(dev)-31 b(elopmen)g(t)6974
41168 y(the)369 b(exp)31 b(erience)369 b(\(co)31 b(de\))370
b(gained)h(in)e(an)-31 b(y)370 b(previously)g(gro)-31
b(wn)370 b(pro)61 b(jects.)8634 42496 y(The)381 b(Demeter)f(system)h
(mak)-31 b(es)381 b(extensiv)-31 b(e)381 b(use)f(of)h(parameterized)h
(classes.)525 b(P)-31 b(aram-)6974 43825 y(eterized)434
b(classes)f(are)h(b)31 b(est)433 b(though)-31 b(t)436
b(of)e(as)g(generic)g(soft)-31 b(w)g(are)435 b(mo)31
b(dules)435 b(whic)-31 b(h)434 b(can)g(b)31 b(e)6974
45153 y(used)469 b(and)h(reused)f(b)-31 b(y)470 b(a)g(large)h
(assortmen)-31 b(t)471 b(of)f(pro)61 b(jects)471 b(so)e(long)i(as)f
(they)h(are)e(of)i(the)6974 46482 y(same)403 b(sp)31
b(ecies.)592 b(W)-92 b(e)402 b(consider)h(the)g(relationship)i(b)31
b(et)-31 b(w)g(een)403 b(parameterized)h(classes)f(and)6974
47810 y(soft)-31 b(w)g(are)338 b(pro)61 b(jects)337 b(to)g(b)31
b(e)336 b(similar)i(to)f(the)g(relationship)h(b)31 b(et)-31
b(w)g(een)337 b(ro)31 b(ot)337 b(sto)31 b(c)-31 b(ks)337
b(and)f(fruit)6974 49138 y(trees.)589 b(A)401 b(ro)31
b(ot)402 b(sto)31 b(c)-31 b(k)402 b(is)g(a)g(tree)f(gro)-31
b(wn)402 b(solely)h(for)e(its)h(ro)31 b(ots.)590 b(The)402
b(v)-61 b(ariet)-31 b(y)402 b(of)g(the)g(tree)6974 50467
y(is)477 b(t)-31 b(ypically)480 b(win)-31 b(ter)478 b(hardy)f(and)h
(disease)f(resistan)-31 b(t)478 b(but)f(otherwise)h(unin)-31
b(teresting)479 b(in)6974 51795 y(fruiting)452 b(habit.)739
b(This)451 b(ro)31 b(ot)451 b(sto)31 b(c)-31 b(k)452
b(is)e(used)g(as)h(a)g(strong)g(generic)g(ro)31 b(oting)453
b(system)e(for)6974 53123 y(trees)441 b(of)i(the)f(same)g(sp)31
b(ecies)441 b(whic)-31 b(h)443 b(ha)-31 b(v)g(e)443 b(sp)31
b(ectacular)443 b(fruiting)g(habits)g(but)f(p)31 b(o)g(or)442
b(im-)6974 54452 y(m)-31 b(unit)g(y)455 b(to)e(cold)h(and)f(disease.)
743 b(W)-92 b(e)452 b(graft)i(the)f(desired)g(v)-61 b(ariet)-31
b(y)453 b(on)-31 b(to)455 b(the)e(ro)31 b(ot)453 b(sto)31
b(c)-31 b(k)6974 55780 y(and)383 b(get)h(a)f(sup)31 b(erior)382
b(tree.)534 b(W)-92 b(e)382 b(could)i(ha)-31 b(v)g(e)383
b(pro)31 b(duced)383 b(suc)-31 b(h)382 b(a)i(tree)e(b)-31
b(y)384 b(y)-31 b(ears)382 b(of)i(selec-)6974 57108 y(tiv)-31
b(e)398 b(breeding)f(within)h(the)f(desired)g(v)-61 b(ariet)-31
b(y)-92 b(,)405 b(but)397 b(b)-31 b(y)397 b(using)g(the)g(ro)31
b(ot)397 b(sto)31 b(c)-31 b(k)398 b(w)-31 b(e)397 b(sa)-31
b(v)g(e)397 b(a)6974 58437 y(signi\014can)-31 b(t)439
b(amoun)-31 b(t)438 b(of)g(time.)697 b(The)437 b(parameterized)h
(classes)e(of)i(Demeter)e(ha)-31 b(v)g(e)438 b(m)-31
b(uc)g(h)6974 59765 y(in)416 b(common)h(with)g(ro)31
b(ot)416 b(sto)31 b(c)-31 b(ks.)631 b(They)416 b(pro)-31
b(vide)417 b(a)f(base)f(of)h(soft)-31 b(w)g(are)417 b(with)g(some)f(v)
-31 b(ery)6974 61093 y(desirable)435 b(prop)31 b(erties.)690
b(W)-92 b(e)434 b(presen)-31 b(t)435 b(sev)-31 b(eral)436
b(clear)f(examples)h(of)g(these)e(constructs)h(in)6974
62422 y(the)369 b(appropriate)i(section)f(b)31 b(elo)-31
b(w.)p 6974 63130 15276 45 v 8206 63846 a Fe(1)8668 64159
y Fd(The)284 b(American)h(Heritage)h(Dictionary)g(de\014nes)e(a)h(F)-78
b(rank)-26 b(enstein)284 b(as)h(\\An)g(agency)g(or)g(creation)h(that)
6974 65210 y(slips)314 b(from)g(the)f(con)-26 b(trol)314
b(of)g(and)g(ultimately)g(destro)-26 b(ys)314 b(its)g(creator".)p
eop
%%Page: 3 3
3 2 bop 6974 4317 a Fj(2)1107 b(DEMETER)370 b(CLASS)f(DICTIONARIES)h
(\(THE)g(SEEDS\))10040 b Fq(3)6974 8280 y Fi(2)1793 b(Demeter)600
b(Class)e(Dictionaries)i(\(The)f(Seeds\))6974 10705 y
Fq(All)478 b(large)g(soft)-31 b(w)g(are)479 b(pro)61
b(jects)478 b(should)g(b)31 b(egin)478 b(with)g(a)g(description)g(of)g
(the)g(underlying)6974 12033 y(data)325 b(structure.)477
b(It)323 b(is)h(the)f(underlying)i(data)g(structure)e(whic)-31
b(h)324 b(is)g(the)f(bac)-31 b(kb)31 b(one)325 b(of)f(an)-31
b(y)6974 13361 y(soft)g(w)g(are)365 b(system.)490 b(A)364
b(p)31 b(o)g(or)363 b(design)g(at)h(this)f(lev)-31 b(el)365
b(is)e(the)g(shortest)g(road)h(to)g(disaster.)490 b(In)6974
14690 y(Demeter,)379 b(the)e(\014rst)f(step)h(in)g(designing)h(a)f
(soft)-31 b(w)g(are)379 b(en)-31 b(vironmen)g(t)379 b(is)d(the)h
(construction)6974 16018 y(of)366 b(a)f(class)g(dictionary)-92
b(.)493 b(The)366 b(class)f(dictionary)i(is)e(a)h(natural)g
(description)g(of)g(the)f(ob)61 b(ject)6974 17346 y(hierarc)-31
b(hies)343 b(whic)-31 b(h)344 b(mak)-31 b(e)345 b(up)e(the)g
(underlying)h(data)g(structure.)484 b(Demeter)343 b(class)g(dictio-)
6974 18675 y(naries)450 b(are)g(de\014ned)h(b)-31 b(y)450
b(an)h(LL\(1\))g(language)i(whose)e(description)g(app)31
b(ears)450 b(in)h(a)f(form)6974 20003 y(similar)338 b(to)g(EBNF.)g(An)
-31 b(y)338 b(actions)g(whic)-31 b(h)338 b(are)f(to)h(b)31
b(e)336 b(carried)h(out)h(in)g(the)f(\\program")i(are)6974
21331 y(reduced)421 b(to)h(manipulations)i(of)e(the)g(ob)61
b(ject)423 b(hierarc)-31 b(h)g(y)-92 b(.)650 b(The)421
b(mac)-31 b(hine)423 b(readable)g(data)6974 22660 y(structure)365
b(is)g(automatically)370 b(generated,)e(along)f(with)f(an)g(abundance)g
(of)g(supp)31 b(ort)365 b(soft-)6974 23988 y(w)-31 b(are,)381
b(b)-31 b(y)378 b(the)g(Demeter)g(system.)519 b(When)377
b(a)h(user)f(describ)31 b(es)377 b(his)g(or)h(her)f(data)i(structure)
6974 25316 y(abstractly)-92 b(,)326 b(he)313 b(or)g(she)g(gains)h(the)f
(adv)-61 b(an)-31 b(tage)316 b(of)d(ha)-31 b(ving)315
b(a)f(common)h(data)f(structure)f(for)6974 26645 y(all)427
b(soft)-31 b(w)g(are)427 b(pro)61 b(jects.)662 b(This)426
b(allo)-31 b(ws)428 b(for)d(the)h(building)i(of)e(a)f(facilit)-31
b(y)429 b(for)d(reusing)f(an)-31 b(y)6974 27973 y(soft)g(w)g(are)428
b(previously)g(written)g(in)f(the)g(Demeter)g(system)g(regardless)f(of)
h(the)g(nature)g(of)6974 29302 y(the)369 b(old)h(soft)-31
b(w)g(are)371 b(pro)61 b(ject.)8634 30630 y(The)285 b(Demeter)f(system)
h(is)g(curren)-31 b(tly)284 b(implemen)-31 b(ted)287
b(in)e(F)-92 b(ranz)284 b(Lisp/Fla)-31 b(v)g(ors.)465
b(In)284 b(this)6974 31958 y(implemen)-31 b(tation)395
b(an)390 b(ob)61 b(ject)392 b(hierarc)-31 b(h)g(y)391
b(is)f(built)i(out)f(of)g(Fla)-31 b(v)g(or)392 b(instances)f(and)f(ob)
61 b(ject)6974 33287 y(manipulations)471 b(are)c(written)i(as)e(metho)
31 b(d)469 b(de\014nitions.)789 b(The)468 b(Demeter)f(system)h(could)
6974 34615 y(b)31 b(e)421 b(p)31 b(orted)422 b(to)h(an)-31
b(y)423 b(language)h(whic)-31 b(h)423 b(has)f(facilities)i(for)e
(de\014ning)h(ob)61 b(jects)423 b(and)f(classes)6974
35943 y(of)450 b(ob)61 b(jects,)472 b(instance)451 b(v)-61
b(ariables)450 b(attac)-31 b(hable)453 b(to)d(an)h(ob)61
b(ject)451 b(or)f(class,)470 b(and)450 b(a)g(m)-31 b(ultiple)6974
37272 y(inheritance)477 b(mec)-31 b(hanism.)814 b(The)476
b(p)31 b(orting)477 b(of)f(the)g(Demeter)g(system)g(to)g(the)g(follo)
-31 b(wing)6974 38600 y(languages)347 b(is)e(no)-31 b(w)346
b(under)e(review:)481 b(Ob)61 b(jectiv)-31 b(e-C,)348
b(C++,)j(Common)c(Lisp)e(\(CLOS\),)h(PC)6974 39928 y(Sc)-31
b(heme)369 b(with)i(Sco)31 b(ops)369 b(and)h(Prolog)g(with)h(an)e(ob)61
b(ject-orien)-31 b(ted)372 b(extension.)8634 41257 y(Man)-31
b(y)448 b(complex)g(class)f(dictionaries)h(ha)-31 b(v)g(e)448
b(b)31 b(een)447 b(written,)468 b(tested,)f(and)447 b(dev)-31
b(elop)31 b(ed)6974 42585 y(in)-31 b(to)385 b(full)g(\015edged)g(soft)
-31 b(w)g(are)385 b(systems.)538 b(W)-92 b(e)383 b(b)31
b(egin)385 b(b)-31 b(y)384 b(constructing)h(a)g(class)f(dictionary)6974
43913 y(whic)-31 b(h)425 b(represen)-31 b(ts)423 b(a)i(real)f(w)-31
b(orld)426 b(system,)439 b(namely)-92 b(,)439 b(a)425
b(meal.)659 b(W)-92 b(e)424 b(\014rst)g(construct)g(this)6974
45242 y(class)366 b(dictionary)i(in)e(English)i(and)e(then)g(transcrib)
31 b(e)366 b(it)h(in)-31 b(to)368 b(the)e(language)i(of)f(Demeter)6974
46570 y(in)i(order)g(to)h(illustrate)h(the)e(naturalness)h(of)g(the)f
(system.)8634 47898 y(A)-31 b(t)287 b(some)f(p)31 b(oin)-31
b(t)287 b(in)g(de\014ning)f(a)g(class)g(dictionary)i(w)-31
b(e)287 b(m)-31 b(ust)286 b(decide)g(what)h(w)-31 b(e)287
b(consider)6974 49227 y(to)314 b(b)31 b(e)313 b(atomic)j(ob)61
b(jects.)475 b(In)313 b(a)g(meal)i(a)f(steak)g(migh)-31
b(t)315 b(b)31 b(e)313 b(considered)g(atomic)j(since)d(w)-31
b(e)314 b(are)6974 50555 y(not)298 b(in)-31 b(terested)298
b(in)g(breaking)h(the)f(meat)g(do)-31 b(wn)299 b(in)-31
b(to)299 b(its)f(molecular)h(structure.)468 b(A)298 b(shrimp)6974
51884 y(co)31 b(c)-31 b(ktail)376 b(migh)-31 b(t)375
b(b)31 b(e)373 b(considered)g(b)-31 b(y)373 b(some)h(to)g(b)31
b(e)373 b(atomic,)k(but)c(for)h(the)f(purp)31 b(ose)373
b(of)g(this)6974 53212 y(example)353 b(w)-31 b(e)352
b(assume)g(that)h(w)-31 b(e)353 b(are)e(ignoran)-31 b(t)354
b(of)e(the)h(notion)g(of)f(a)h(shrimp)e(co)31 b(c)-31
b(ktail)355 b(and)6974 54540 y(need)272 b(to)i(break)e(it)i(do)-31
b(wn)273 b(further.)460 b(A)-31 b(tomic)275 b(ob)61 b(jects)274
b(are)e(presen)-31 b(ted)272 b(as)h(terminal)h(sym)-31
b(b)31 b(ols)6974 55869 y(in)369 b(our)g(grammar)i(\(t)-31
b(ypically)372 b(strings\).)494 b(W)-92 b(e)368 b(de\014ne)h(our)g
(meal)h(as)f(follo)-31 b(ws:)8327 58082 y(1.)554 b(A)372
b(meal)i(is)e(an)g(app)31 b(etizer,)374 b(an)f(en)-31
b(tree,)373 b(and)f(a)h(dessert.)501 b(While)372 b(a)h(dessert)e(ma)-31
b(y)373 b(b)31 b(e)9741 59411 y(considered)357 b(optional)j(in)d(man)
-31 b(y)358 b(households,)i(w)-31 b(e)358 b(consider)f(it)g(a)g
(required)g(part)g(of)9741 60739 y(a)370 b(meal.)8327
62953 y(2.)554 b(An)369 b(app)31 b(etizer)370 b(is)f(a)h(melon)g(or)f
(a)h(shrimp)f(co)31 b(c)-31 b(ktail.)8327 65167 y(3.)554
b(A)465 b(shrimp)f(co)31 b(c)-31 b(ktail)467 b(is)d(lettuce,)490
b(one)464 b(or)h(more)f(shrimp,)489 b(and)464 b(p)31
b(ossibly)465 b(co)31 b(c)-31 b(ktail)p eop
%%Page: 4 4
4 3 bop 6974 4317 a Fj(2)1107 b(DEMETER)370 b(CLASS)f(DICTIONARIES)h
(\(THE)g(SEEDS\))10040 b Fq(4)9741 8192 y(sauce.)8327
10342 y(4.)554 b(Co)31 b(c)-31 b(ktail)372 b(sauce)d(is)h(k)-31
b(etc)g(h)g(up)370 b(and)f(horseradish.)8327 12493 y(5.)554
b(An)369 b(en)-31 b(tree)370 b(is)f(a)g(steak)h(platter)g(or)g(a)f(bak)
-31 b(ed)370 b(stu\013ed)f(shrimp)g(platter.)8327 14644
y(6.)554 b(A)369 b(steak)h(platter)h(is)e(a)g(steak)h(and)g(the)f
(trimmings.)8327 16795 y(7.)554 b(A)369 b(bak)-31 b(ed)370
b(stu\013ed)f(shrimp)g(platter)i(is)e(a)g(stu\013ed)g(shrimp)g(and)h
(the)f(trimmings.)8327 18945 y(8.)554 b(The)370 b(trimmings)h(are)e(a)g
(p)31 b(otato)371 b(and)f(t)-31 b(w)g(o)371 b(v)-31 b(eggies.)8327
21096 y(9.)554 b(A)369 b(v)-31 b(eggie)371 b(is)e(carrots,)h(p)31
b(eas,)369 b(or)g(corn.)7773 23247 y(10.)555 b(A)369
b(dessert)g(is)g(pie,)h(cak)-31 b(e,)370 b(or)f(jello.)7773
25398 y(11.)555 b(W)-92 b(e)436 b(assume)g(that)h(the)f(follo)-31
b(wing)440 b(items)d(are)f(atomic)i(and)e(need)g(no)g(further)g(de-)
9741 26726 y(scription:)820 b(melon,)575 b(shrimp,)e(lettuce,)i(k)-31
b(etc)g(h)g(up,)575 b(horseradish,)e(steak,)h(stu\013ed-)9741
28054 y(shrimp,)370 b(p)31 b(otato,)371 b(carrots,)f(p)31
b(eas,)369 b(corn,)h(pie,)g(cak)-31 b(e,)370 b(and)g(jello.)6974
30142 y(The)413 b(decision)g(as)g(to)g(whether)g(an)g(ob)61
b(ject)414 b(is)f(atomic)i(or)d(built)i(up)f(from)g(other)g(ob)61
b(jects)6974 31470 y(is)390 b(not)g(only)h(domain)g(sp)31
b(eci\014c)390 b(but)g(also)g(sp)31 b(eci\014c)390 b(to)g(the)g(p)31
b(erson)389 b(p)31 b(erforming)391 b(the)f(data)6974
32799 y(abstraction.)8634 34127 y(Eac)-31 b(h)380 b(of)g(the)g(elev)-31
b(en)380 b(descriptiv)-31 b(e)380 b(phrases)e(falls)j(in)-31
b(to)380 b(one)g(of)g(three)f(categories.)524 b(Ei-)6974
35455 y(ther)493 b(w)-31 b(e)495 b(are)e(constructing)i(an)f(ob)61
b(ject)495 b(in)f(terms)g(of)g(other)g(ob)61 b(jects)495
b(\(a)f(construction)6974 36784 y(pro)31 b(duction\),)364
b(or)c(w)-31 b(e)360 b(are)g(de\014ning)h(an)f(ob)61
b(ject)362 b(as)d(b)31 b(eing)361 b(an)f(ordered)g(collection)i(of)f
(zero)6974 38112 y(\(one\))403 b(or)f(more)h(of)f(another)h(ob)61
b(ject)404 b(\(a)f(rep)31 b(etition)403 b(pro)31 b(duction\),)413
b(or)402 b(w)-31 b(e)402 b(state)h(that)h(an)6974 39440
y(ob)61 b(ject)376 b(is)e(one)g(of)h(sev)-31 b(eral)375
b(p)31 b(ossible)374 b(ob)61 b(jects)376 b(\(an)f(alternation)i(pro)31
b(duction\).)509 b(Examples)6974 40769 y(of)370 b(these)f(three)g(ob)61
b(ject)370 b(descriptions)g(are)f(sho)-31 b(wn)370 b(in)f(Demeter)g
(notation)j(b)31 b(elo)-31 b(w.)6974 43046 y Fc(Construction)555
b Fq(An)457 b(elemen)-31 b(t)458 b(of)f(class)g Fb(A)g
Fq(has)f(a)h(\014rst)g(part)g(whic)-31 b(h)457 b(is)g(an)g(elemen)-31
b(t)458 b(of)9741 44375 y(class)384 b Fb(B)f Fq(follo)-31
b(w)g(ed)386 b(b)-31 b(y)383 b(an)h(elemen)-31 b(t)384
b(of)g(class)f Fb(C)p Fq(,)h(p)31 b(ossibly)384 b(an)f(elemen)-31
b(t)385 b(of)f(class)f Fb(D)p Fq(,)9741 45703 y(and)370
b(an)f(elemen)-31 b(t)371 b(of)e(class)h Fb(E)p Fq(.)10904
48202 y Fa(A)581 b(=)g(B)g(C)h([D])f(E.)9741 50701 y
Fq(A)535 b(construction)h(class)f(ma)-31 b(y)537 b(inherit)e(from)h
(another)f(construction)i(class.)990 b(An)9741 52029
y(elemen)-31 b(t)359 b(of)g(class)e(X)h(has)g(a)g(\014rst)f(part)h
(whic)-31 b(h)358 b(is)g(an)g(elemen)-31 b(t)359 b(of)f(class)g(X)g
(follo)-31 b(w)g(ed)9741 53357 y(b)g(y)443 b(a)g(second)f(part)h(whic)
-31 b(h)444 b(is)e(an)h(elemen)-31 b(t)444 b(of)f(class)g(Z)g(follo)-31
b(w)g(ed)445 b(b)-31 b(y)443 b(all)h(parts)e(of)9741
54686 y(class)369 b(A.)10904 57374 y Fa(X)581 b(=)g(Y)g(Z)h(*inherit*)g
(A.)6974 60063 y Fc(Rep)35 b(etition)555 b Fq(An)302
b(elemen)-31 b(t)304 b(of)f(class)g Fb(A)f Fq(is)h(a)g(collection)i(of)
e(zero)g(\(one\))g(or)g(more)g(elemen)-31 b(ts)9741 61391
y(of)370 b Fb(B)p Fq(.)10904 63890 y Fa(A)581 b(~)g({)g(B)h(}.)10904
65218 y(A)f(~)g(B)g({)h(B)f(}.)p eop
%%Page: 5 5
5 4 bop 6974 4317 a Fj(2)1107 b(DEMETER)370 b(CLASS)f(DICTIONARIES)h
(\(THE)g(SEEDS\))10040 b Fq(5)6974 8192 y Fc(Alternation)555
b Fq(An)347 b(elemen)-31 b(t)348 b(of)f(class)g Fb(A)g
Fq(is)g(either)g(an)g(elemen)-31 b(t)349 b(of)e(classes)g
Fb(B)f Fq(or)h Fb(C)g Fq(or)g Fb(D)p Fq(.)10904 10848
y Fa(A)581 b(:)g(B)g(|)h(C)f(|)g(D.)9741 13505 y Fq(If)429
b(the)h(alternativ)-31 b(es)431 b(ha)-31 b(v)g(e)430
b(common)h(prop)31 b(erties,)444 b(w)-31 b(e)430 b(use)f(alternation)j
(with)e(im-)9741 14833 y(plied)350 b(inheritance.)487
b(An)349 b(elemen)-31 b(t)350 b(of)g(class)e(A)h(is)g(either)g(an)h
(elemen)-31 b(t)350 b(of)f(class)g(B)g(or)9741 16162
y(C)399 b(and)g(b)31 b(oth)399 b(B)f(and)h(C)g(ha)-31
b(v)g(e)399 b(t)-31 b(w)g(o)400 b(parts,)407 b(the)398
b(\014rst)g(b)31 b(eing)399 b(an)g(ob)61 b(ject)400 b(of)f(class)g(X)
9741 17490 y(and)354 b(the)g(second)f(an)h(ob)61 b(ject)355
b(of)f(class)f(Y.)h(\(X)g(and)g(Y)f(are)g(the)h(last)g(t)-31
b(w)g(o)356 b(parts)d(of)h(B)9741 18818 y(and)370 b(C.\))10904
21475 y Fa(A)581 b(:)g(B)g(|)h(C)f(*common*)h(X)g(Y.)6974
24132 y Fq(Man)-31 b(y)444 b(times)g(w)-31 b(e)443 b(w)-31
b(an)g(t)445 b(to)f(add)g(k)-31 b(eyw)g(ords)444 b(to)g(our)f(ob)61
b(ject)444 b(descriptions.)715 b(These)444 b(ma)-31 b(y)6974
25460 y(b)31 b(e)343 b(necessary)f(to)i(satisfy)g(the)g(LL\(1\))g
(restriction)g(on)g(the)f(grammar)i(or)e(ma)-31 b(y)345
b(b)31 b(e)342 b(used)h(to)6974 26788 y(\\sw)-31 b(eeten")377
b(the)e(syn)-31 b(tax)376 b(of)g(a)f(class)g(dictionary)-92
b(.)513 b(In)374 b(an)-31 b(y)376 b(ev)-31 b(en)g(t)376
b(they)g(ha)-31 b(v)g(e)376 b(no)f(e\013ect)h(on)6974
28117 y(the)339 b(ob)61 b(ject)340 b(hierarc)-31 b(h)g(y)339
b(descriptions.)483 b(The)338 b(Demeter)h(system)g(guaran)-31
b(tees)339 b(that)h(all)g(user)6974 29445 y(pro)31 b(duced)460
b(co)31 b(de)461 b(is)f(completely)j(shielded)e(from)g(the)g(concrete)g
(syn)-31 b(tax.)768 b(This)461 b(implies)6974 30773 y(that)409
b(the)g(input)g(language)h(for)e(an)h(ob)61 b(ject)409
b(hierarc)-31 b(h)g(y)409 b(can)g(b)31 b(e)407 b(mo)31
b(di\014ed)409 b(to)g(the)g(whims)6974 32102 y(of)396
b(the)g(user)e(with)j(no)f(risk)f(to)h(the)g(reliabilit)-31
b(y)399 b(of)d(the)f(system.)572 b(This)396 b(mo)31 b(di\014cation)399
b(can)6974 33430 y(b)31 b(e)424 b(done)h(at)g(an)-31
b(y)425 b(p)31 b(oin)-31 b(t)426 b(in)f(the)g(system)f(dev)-31
b(elopmen)g(t.)661 b(The)425 b(only)h(restriction)f(is)g(that)6974
34759 y(the)372 b(structure)g(of)g(the)g(underlying)h(ob)61
b(ject)374 b(hierarc)-31 b(h)g(y)372 b(m)-31 b(ust)373
b(remain)g(static.)502 b(Belo)-31 b(w)374 b(are)6974
36087 y(examples)392 b(of)g(construction)g(and)f(rep)31
b(etition)393 b(pro)31 b(ductions)392 b(whic)-31 b(h)392
b(demonstrate)g(where)6974 37415 y(concrete)369 b(syn)-31
b(tax)371 b(can)e(b)31 b(e)369 b(inserted)g(in)-31 b(to)370
b(the)g(ob)61 b(ject)370 b(descriptions.)6974 39851 y
Fc(Construction)426 b(Pro)35 b(duction)556 b Fq(.)10904
42729 y Fa(A)581 b(=)g("a")h(B)f("followed")i("by")e("a")h(C)13228
44057 y("inherits-from-Q")14390 45385 y(*inherit*)h(Q)13228
46714 y("end-inherit")13228 48042 y(["maybe")f(D)g("!!"])13228
49370 y("followed)h(by")e(E.)6974 52249 y Fc(Rep)35 b(etition)425
b(Pro)35 b(duction)556 b Fq(.)10904 55127 y Fa(A)581
b(~)g("first")h(B)13228 56455 y({"prefix")h("String")f(B)f("suffix"})
13228 57783 y("terminating".)6974 60661 y Fc(Alternation)425
b(Pro)35 b(duction)556 b Fq(.)10904 63540 y Fa(Fruit)581
b(:)h(Orange)g(|)f(Apple)12066 64868 y(*common*)h("weight")h(<weight>)f
(Number)g("terminating".)p eop
%%Page: 6 6
6 5 bop 6974 4317 a Fj(2)1107 b(DEMETER)370 b(CLASS)f(DICTIONARIES)h
(\(THE)g(SEEDS\))10040 b Fq(6)8634 8192 y(Man)-31 b(y)398
b(class)g(dictionaries)h(mak)-31 b(e)399 b(use)e(of)h(descriptiv)-31
b(e)398 b(lab)31 b(els)398 b(in)g(their)f(construction)6974
9520 y(pro)31 b(ductions.)467 b(A)292 b(descriptiv)-31
b(e)293 b(lab)31 b(el)294 b(is)e(an)g(iden)-31 b(ti\014er)293
b(whic)-31 b(h)293 b(is)f(enclosed)h(in)f(angle)i(brac)-31
b(k-)6974 10848 y(ets)383 b(and)g(preceeds)e(a)i(giv)-31
b(en)384 b(non)-31 b(terminal.)536 b(The)383 b(sole)h(purp)31
b(ose)381 b(of)j(descriptiv)-31 b(e)383 b(lab)31 b(els)384
b(is)6974 12177 y(to)344 b(rename)f(a)g(sub-ob)61 b(ject)344
b(in)f(the)h(class)f(dictionary)-92 b(.)485 b(This)344
b(renaming)g(is)f(required)g(if)g(t)-31 b(w)g(o)6974
13505 y(\(or)475 b(more\))h(of)f(the)g(same)g(non)-31
b(terminal)477 b(are)e(iden)-31 b(ti\014ed)476 b(on)f(the)h(righ)-31
b(t)475 b(hand)g(side)g(of)g(a)6974 14833 y(construction)408
b(pro)31 b(duction.)605 b(The)407 b(follo)-31 b(wing)410
b(is)d(an)g(example)h(of)f(suc)-31 b(h)406 b(a)h(pro)31
b(duction,)417 b(it)6974 16162 y(de\014nes)368 b(an)i(ob)61
b(ject)370 b(A)g(whic)-31 b(h)370 b(is)f(comprised)g(of)h(t)-31
b(w)g(o)371 b(B's.)8136 18376 y Fa(A)581 b(=)h(<first>)g(B)f(<second>)i
(B.)6974 20589 y Fq(The)320 b(other)f(case)h(in)g(whic)-31
b(h)320 b(descriptiv)-31 b(e)320 b(lab)31 b(els)320 b(are)g(often)g
(used)f(is)h(with)g(class)g(terminals.)6974 21918 y(When)294
b(a)h(class)f(terminal)i(is)f(used)f(without)j(a)d(lab)31
b(el)296 b(it)f(is)g(not)g(descriptiv)-31 b(e.)468 b(W)-92
b(e)294 b(use)g(lab)31 b(els)6974 23246 y(to)339 b(mak)-31
b(e)339 b(the)f(ob)61 b(jects)339 b(more)f(self)g(describing.)483
b(The)338 b(follo)-31 b(wing)342 b(example)d(illustrates)g(this)6974
24575 y(p)31 b(oin)-31 b(t.)8136 26788 y Fa(GradeReport)583
b(=)e(Ident)h(Number.)6974 29002 y Fq(is)442 b(not)g(self)g
(describing.)711 b(The)442 b(follo)-31 b(wing)445 b(is)d(seman)-31
b(tically)445 b(equiv)-61 b(alen)-31 b(t)444 b(but)e(mak)-31
b(es)443 b(the)6974 30331 y(class)369 b(dictionary)-92
b(,)371 b(and)f(an)-31 b(y)370 b(metho)31 b(ds)370 b(written)g(for)f
(it,)i(easier)e(to)h(read.)8136 32545 y Fa(GradeReport)583
b(=)9298 33873 y(<studentName>)h(Ident)9298 35201 y(<testScore>)f
(Number.)8634 37415 y Fq(It)381 b(is)f(imp)31 b(ortan)-31
b(t)382 b(to)f(note)g(that)h(the)f(ob)61 b(ject)381 b(stored)f(at)i(a)e
(sym)-31 b(b)31 b(ol)381 b(p)31 b(osition)382 b(remains)6974
38744 y(the)397 b(same)h(whether)f(or)g(not)h(it)f(is)g(lab)31
b(eled.)578 b(The)397 b(lab)31 b(els)397 b(are)g(used)g(only)h(for)f
(descriptiv)-31 b(e)6974 40072 y(purp)31 b(oses)287 b(and)i(are)f
(analogous)j(to)e(the)f(renaming)i(of)f(v)-61 b(ariables.)466
b(Lab)31 b(els)289 b(are)f(also)h(used)f(to)6974 41400
y(o)-31 b(v)g(erride)397 b(instance)g(v)-61 b(ariable)397
b(t)-31 b(yp)31 b(es)396 b(in)g(connection)i(with)g(inheritance)f(in)f
(construction)6974 42729 y(or)369 b(alternation)j(pro)31
b(ductions.)493 b(\(W)-92 b(e)369 b(use)g(class)g(and)g(t)-31
b(yp)31 b(e)370 b(as)f(synon)-31 b(yms.\))6974 45164
y Fa(A)581 b(=)g(B)h(<label>)g(K.)6974 46492 y(X)f(=)g(D)h(*inherit*)g
(A)g(*override*)g(<label>)g(L.)6974 47821 y(M)f(:)g(P)h(|)f(Q)g
(*common*)i(*inherit*)f(A)f(*override*)i(<label>)f(L.)8634
50256 y Fq(An)445 b(elemen)-31 b(t)446 b(of)f(class)g
Fb(X)f Fq(is)h(an)g(elemen)-31 b(t)446 b(of)f(class)f
Fb(D)h Fq(follo)-31 b(w)g(ed)448 b(b)-31 b(y)445 b(all)h(elemen)-31
b(ts)445 b(of)6974 51584 y(class)303 b Fb(A)p Fq(.)g(The)g(t)-31
b(yp)31 b(e)303 b(of)h(the)f(instance)h(v)-61 b(ariable)304
b(called)g Fb(lab)31 b(el)303 b Fq(is)g Fb(L)f Fq(and)h(not)h
Fb(K)p Fq(.)e(An)h(elemen)-31 b(t)6974 52913 y(of)385
b(class)f Fb(M)f Fq(is)i(either)f(an)h(elemen)-31 b(t)385
b(of)g(class)f Fb(P)g Fq(or)g Fb(Q)p Fq(.)h(Both)g Fb(P)f
Fq(and)h Fb(Q)e Fq(ha)-31 b(v)g(e)386 b(in)e(common)6974
54241 y(all)378 b(the)e(instance)i(v)-61 b(ariables)377
b(of)g Fb(A)p Fq(,)g(with)g(the)g(t)-31 b(yp)31 b(e)377
b(of)g(instance)h(v)-61 b(ariable)377 b Fb(lab)31 b(el)377
b Fq(c)-31 b(hanged)6974 55569 y(to)370 b Fb(L)p Fq(.)8634
56898 y(Certain)457 b(instance)f(v)-61 b(ariables)457
b(are)e(inherited)h(b)-31 b(y)456 b(all)h(ob)61 b(jects.)753
b(The)455 b(instance)i(v)-61 b(ari-)6974 58226 y(ables)493
b Fk(attribute)g Fq(and)g Fk(father)f Fq(are)h(inherited)h(b)-31
b(y)493 b(all)h(Demeter)f(de\014ned)g(ob)61 b(jects.)865
b(The)6974 59554 y(instance)373 b(v)-61 b(ariable)373
b Fk(attribute)f Fq(is)g(an)g(application)j(sp)31 b(eci\014c)372
b(v)-61 b(ariable)373 b(whic)-31 b(h)373 b(can)g(b)31
b(e)371 b(used)6974 60883 y(to)409 b(\\decorate")h(the)f(ob)61
b(jects.)611 b(The)409 b(latter)h(instance)f(v)-61 b(ariable)410
b(is)e(used)g(in)g(constructing)6974 62211 y(bac)-31
b(kw)g(ard)279 b(p)31 b(oin)-31 b(ters)278 b(in)g(an)h(ob)61
b(ject)279 b(hierarc)-31 b(h)g(y)-92 b(.)462 b(There)278
b(are)g(also)g(some)g(instance)h(v)-61 b(ariables)6974
63540 y(whic)-31 b(h)400 b(are)e(inherited)i(b)-31 b(y)399
b(certain)g(classes)g(of)g(ob)61 b(jects.)582 b(All)400
b(rep)31 b(etition)400 b(ob)61 b(jects)400 b(inherit)6974
64868 y(the)310 b(instance)g(v)-61 b(ariable)311 b Fk(child)p
Fq(.)473 b(This)310 b(instance)h(v)-61 b(ariable)310
b(con)-31 b(tains)312 b(a)e(list)g(of)h(the)f(rep)31
b(eated)p eop
%%Page: 7 7
7 6 bop 6974 4317 a Fj(2)1107 b(DEMETER)370 b(CLASS)f(DICTIONARIES)h
(\(THE)g(SEEDS\))10040 b Fq(7)19178 8868 y Fa(universal)16272
10196 y([father,)583 b(attribute])20921 11525 y(|)20921
12853 y(|)11042 14181 y(|----------------|---------------|)11042
15510 y(|)9298 b(|)8718 b(|)11042 16838 y(|)9298 b(|)8718
b(|)8717 18166 y(construction)3489 b(repetition)f(terminal)11042
19495 y(|)7555 b([child])5231 b([val])11042 20823 y(|)9298
b(|)8718 b(|)11042 22152 y(|)9298 b(|)8718 b(|-----|-------|)11042
23480 y(|)9298 b(|)8718 b(|)2906 b(|)4068 b(|)8717 24808
y(construction)3489 b(repetition)4070 b(Ident)581 b(Number)h(String)
8717 26137 y(classes)6394 b(classes)16793 29679 y Fq(Figure)370
b(1:)493 b(Class)369 b(hierarc)-31 b(h)g(y)370 b(organization)6974
33215 y(ob)61 b(jects)472 b(used)f(to)h(de\014ne)f(the)g(rep)31
b(etition)473 b(ob)61 b(ject.)801 b(In)470 b(addition,)500
b(eac)-31 b(h)472 b(class)f(terminal)6974 34543 y(\(i.e.,)j(Iden)-31
b(t,)473 b(Num)-31 b(b)31 b(er,)473 b(String\))453 b(inherits)f(the)g
(instance)h(v)-61 b(ariable)452 b Fk(val)g Fq(whic)-31
b(h)452 b(con)-31 b(tains)6974 35872 y(the)369 b(v)-61
b(alue)370 b(of)g(the)f(iden)-31 b(ti\014er,)371 b(n)-31
b(um)g(b)31 b(er,)369 b(or)g(string)h(\(resp)31 b(ectiv)-31
b(ely\).)8634 37200 y(The)311 b(instance)f(v)-61 b(ariables)311
b(father,)323 b(attribute,)h(c)-31 b(hild)311 b(and)f(v)-61
b(al)311 b(are)e(attac)-31 b(hed)312 b(to)f(classes)6974
38528 y(as)435 b(sho)-31 b(wn)437 b(in)f(Fig.)693 b(\\Class)436
b(hierarc)-31 b(h)g(y)437 b(organization".)695 b(Eac)-31
b(h)437 b(rep)31 b(etition)437 b(class)f(inher-)6974
39857 y(its)357 b(from)f(class)h(rep)31 b(etition)357
b(and)g(eac)-31 b(h)357 b(construction)g(class)f(inherits)h(from)g
(construction.)6974 41185 y(Class)469 b(terminals)h(\(e.g.)792
b(Iden)-31 b(t\))470 b(inherit)f(from)h(terminal)g(and)f(all)h(three)e
(classes:)692 b(con-)6974 42513 y(struction,)370 b(rep)31
b(etition)371 b(and)e(terminal)i(inherit)f(from)g(univ)-31
b(ersal.)6974 43842 y(The)369 b(description)h(of)g(our)f(meal)h(in)g
(Demeter)f(notation)j(is)d(as)g(follo)-31 b(ws:)8136
46056 y Fa(Meal)582 b(=)9298 47384 y("Appetizer:")h(Appetizer)9298
48712 y("Entree:")g(Entree)9298 50041 y("Dessert:")g(Dessert.)8136
51369 y(Appetizer)g(:)e(Melon)h(|)f(ShrimpCocktail.)8136
52697 y(ShrimpCocktail)i(=)f(Shrimps)g(Lettuce)9298 54026
y([CocktailSauce].)8136 55354 y(CocktailSauce)h(=)f(Ketchup)g
(HorseRadish.)8136 56683 y(Entree)g(:)f(SteakPlatter)i(|)f
(BakedStuffedShrimp.)8136 58011 y(SteakPlatter)h(=)e(Steak)h
(Trimmings.)8136 59339 y(BakedStuffedShrimp)i(=)d(StuffedShrimp)9298
60668 y(Trimmings.)8136 61996 y(Trimmings)i(=)e(Potato)9298
63324 y(<veggie1>)i(Veggie)f(<veggie2>)g(Veggie.)8136
64653 y(Veggie)g(:)f(Carrots)i(|)e(Peas)h(|)f(Corn.)p
eop
%%Page: 8 8
8 7 bop 6974 4317 a Fj(3)1107 b(SPR)-31 b(OUTING)370
b(AND)f(FER)-92 b(TILIZER)19256 b Fq(8)8136 8192 y Fa(Dessert)582
b(:)g(Pie)f(|)h(Cake)f(|)h(Jello.)8136 9520 y(Shrimps)g(~)g(Shrimp)g
({Shrimp}.)8136 10848 y(Shrimp)g(=)f("shrimp".)1164 b(Melon)582
b(=)f("melon".)1164 b(etc.)6974 12951 y Fq(W)-92 b(e)288
b(can)g(no)-31 b(w)290 b(input)f(this)g(class)f(dictionary)j(to)e
(Demeter)f(and)h(generate)g(an)g(en)-31 b(vironmen)g(t)6974
14280 y(sk)g(eleton.)459 b(W)-92 b(e)263 b(can)i(then)f(create)h(ob)61
b(ject)266 b(hierarc)-31 b(hies)264 b(represen)-31 b(ting)264
b(meals,)287 b(e.g.)459 b(an)264 b(input)6974 15608 y(of)370
b(the)f(form)6974 17711 y Fa(Appetizer:)582 b(melon)6974
19039 y(Entree:)g(steak)g(potato)g(carrots)g(peas)6974
20368 y(Dessert:)g(cake)6974 22471 y Fq(de\014nes)397
b(a)i(meal.)580 b(This)399 b(example)h(demonstrates)f(the)f(straigh)-31
b(t)400 b(forw)-31 b(ard)399 b(translation)h(of)6974
23799 y(our)437 b(conceptual)i(understanding)f(of)g(a)f(meal)i(to)f
(the)g(Demeter)f(notation.)699 b(The)438 b(repre-)6974
25128 y(sen)-31 b(tation)459 b(of)f(a)g(system)g(b)-31
b(y)457 b(a)h(hierarc)-31 b(h)g(y)458 b(of)g(ob)61 b(ject)459
b(descriptions)f(is)f(v)-31 b(ery)457 b(natural)i(to)6974
26456 y(p)31 b(eople.)6974 30397 y Fi(3)1793 b(Sprouting)599
b(and)f(F)-149 b(ertilizer)6974 32822 y Fq(Once)390 b(the)i(seed)e(of)h
(a)h(pro)61 b(ject)392 b(has)e(b)31 b(een)391 b(established)h(w)-31
b(e)391 b(need)g(to)g(pro)31 b(duce)391 b(a)g(w)-31 b(orking)6974
34150 y(system)416 b(from)h(it.)636 b(In)415 b(addition)k(to)e(pro)31
b(ducing)417 b(this)g(small)h(w)-31 b(orking)418 b(system)e(w)-31
b(e)417 b(w)-31 b(ould)6974 35478 y(lik)g(e)285 b(to)f(pro)-31
b(vide)285 b(a)f(large)g(quan)-31 b(tit)g(y)286 b(of)f(supp)31
b(ort)283 b(co)31 b(de)283 b(to)i(aid)f(the)g(early)g(system)g(in)g
(its)g(\014rst)6974 36807 y(stages)435 b(of)f(gro)-31
b(wth.)689 b(It)435 b(is)f(kno)-31 b(wn)435 b(that)g(eac)-31
b(h)435 b(plan)-31 b(t)436 b(in)e(the)g(agricultural)j(w)-31
b(orld)435 b(gro)-31 b(ws)6974 38135 y(b)31 b(est)456
b(when)g(an)g(applied)i(fertilizer)f(w)-31 b(as)457 b(dev)-31
b(elop)31 b(ed)457 b(sp)31 b(eci\014cally)457 b(for)f(the)g(giv)-31
b(en)458 b(plan)-31 b(t.)6974 39463 y(Similarly)-92 b(,)504
b(eac)-31 b(h)475 b(system)g(resp)31 b(onds)474 b(b)31
b(est)474 b(to)i(a)f(set)g(of)g(utilities)i(built)g(sp)31
b(eci\014cally)476 b(for)6974 40792 y(the)352 b(class)h(dictionary)-92
b(.)489 b(This)352 b(set)h(of)f(utilities)j(\(fertilizer\))g(is)d(pro)
31 b(duced)352 b(b)-31 b(y)352 b(the)h(Demeter)6974 42120
y(system)281 b(through)h(a)g(series)e(of)i(soft)-31 b(w)g(are)283
b(generation)g(steps.)463 b(In)281 b(these)g(steps)g(the)g(follo)-31
b(wing)6974 43448 y(utilities)298 b(are)e(generated)h(or)e(pro)-31
b(vided)297 b(generically)h(from)e(the)h(information)h(stored)e(in)h
(the)6974 44777 y(class)369 b(dictionary)-92 b(.)8634
46880 y Fp(\017)554 b Fq(The)392 b(class)g(de\014nitions)h(for)f(eac)
-31 b(h)393 b(ob)61 b(ject)393 b(de\014ned)f(in)g(the)g(class)g
(dictionary)-92 b(.)562 b(This)9741 48208 y(frees)327
b(the)g(user)f(from)i(learning)g(the)g(syn)-31 b(tax)328
b(of)g(de\014ning)f(classes)g(and)h(frees)e(Deme-)9741
49537 y(ter)369 b(from)h(b)31 b(eing)370 b(totally)i(dep)31
b(enden)-31 b(t)369 b(on)h(its)f(underlying)h(implemen)-31
b(tation.)8634 51695 y Fp(\017)554 b Fq(A)275 b(set)h(of)g(metho)31
b(ds)275 b(for)h(prett)-31 b(y-prin)g(ting)278 b(a)d(hierarc)-31
b(h)g(y)276 b(of)g(ob)61 b(jects.)462 b(It)276 b(is)f(considered)9741
53024 y(adv)-61 b(an)-31 b(tageous)378 b(to)e(ha)-31
b(v)g(e)377 b(data)f(whic)-31 b(h)377 b(is)e(self-describing.)512
b(In)375 b(Demeter,)j(the)d(t)-31 b(yp)31 b(e)9741 54352
y(de\014nitions)371 b(sp)31 b(ecify)369 b(the)g(external)i(represen)-31
b(tation)370 b(of)g(the)f(ob)61 b(jects.)8634 56510 y
Fp(\017)554 b Fq(A)315 b(set)f(of)h(metho)31 b(ds)315
b(for)f(\\dra)-31 b(wing")317 b(a)e(hierarc)-31 b(h)g(y)315
b(of)g(ob)61 b(jects.)475 b(The)315 b(curren)-31 b(t)314
b(imple-)9741 57839 y(men)-31 b(tation)398 b(is)e(a)f(simple)h(hierarc)
-31 b(hical)397 b(sk)-31 b(etc)g(h)396 b(of)g(the)g(ob)61
b(ject)396 b(hierarc)-31 b(hies.)572 b(Later)9741 59167
y(implemen)-31 b(tations)373 b(will)e(include)f(graphics)g(to)g(giv)-31
b(e)370 b(a)g(more)f(aesthetic)i(image.)8634 61326 y
Fp(\017)554 b Fq(A)431 b(scanner/parser)g(for)g(the)g(LL\(1\))i
(description)f(of)f(the)h(class)f(dictionary)-92 b(.)680
b(This)9741 62654 y(soft)-31 b(w)g(are)290 b(allo)-31
b(ws)290 b(the)e(user)f(to)i(ha)-31 b(v)g(e)289 b(a)g(hierarc)-31
b(h)g(y)288 b(of)h(ob)61 b(jects)289 b(built)g(from)g(an)f(ASCI)31
b(I)9741 63982 y(input)445 b(\014le)e(whic)-31 b(h)445
b(con)-31 b(tains)445 b(the)f(description)g(of)g(the)g(ob)61
b(ject)445 b(hierarc)-31 b(h)g(y)445 b(written)9741 65311
y(in)370 b(the)f(LL\(1\))h(language.)p eop
%%Page: 9 9
9 8 bop 6974 4317 a Fj(4)1107 b(THE)370 b(GR)-31 b(O)g(WTH)370
b(AND)f(EV)-31 b(OLUTION)370 b(OF)f(A)g(SYSTEM)g(\(NUR)-92
b(TURING\))1600 b Fq(9)8634 8192 y Fp(\017)554 b Fq(A)413
b(structure-directed)g(editor)h(whic)-31 b(h)414 b(allo)-31
b(ws)415 b(the)f(user)e(to)h(build)h(a)g(hierarc)-31
b(h)g(y)413 b(of)9741 9520 y(ob)61 b(jects)313 b(b)-31
b(y)313 b(answ)-31 b(ering)313 b(questions)f(ab)31 b(out)313
b(the)g(hierarc)-31 b(h)g(y)-92 b(.)473 b(This)313 b(ob)61
b(ject)313 b(hierarc)-31 b(h)g(y)9741 10848 y(could)415
b(then)g(b)31 b(e)414 b(prin)-31 b(ted)414 b(to)h(an)g(ASCI)31
b(I)414 b(\014le,)426 b(via)415 b(the)g(prett)-31 b(y-prin)g(ting)417
b(metho)31 b(ds,)9741 12177 y(for)320 b(later)g(reloading)h(b)-31
b(y)320 b(the)g(scanner/parser.)475 b(This)320 b(editor)g(do)31
b(es)319 b(not)h(require)g(the)9741 13505 y(user)303
b(to)h(kno)-31 b(w)304 b(ab)31 b(out)305 b(the)f(concrete)f(syn)-31
b(tax)305 b(of)f(the)f(input)h(language)i(so)d(one)h(could)9741
14833 y(refer)369 b(to)h(it)f(as)h(a)f(syn)-31 b(tax-directed)371
b(editor)f(as)f(w)-31 b(ell.)8634 16980 y Fp(\017)554
b Fq(A)374 b(sk)-31 b(eleton)376 b(program)f(\(sprout\))g(whic)-31
b(h)375 b(de\014nes)f(a)g(sample)h(metho)31 b(d)376 b(for)e(eac)-31
b(h)375 b(ob-)9741 18309 y(ject)435 b(in)g(the)g(hierarc)-31
b(h)g(y)-92 b(.)689 b(Eac)-31 b(h)436 b(metho)31 b(d)435
b(includes)g(a)g(reference)e(to)j(all)g(of)f(the)g(in-)9741
19637 y(stance)364 b(v)-61 b(ariables)364 b(of)g(the)f(ob)61
b(ject)365 b(as)e(w)-31 b(ell)365 b(as)e(a)h(commen)-31
b(t)365 b(header)e(describing)h(the)9741 20966 y(ob)61
b(ject)312 b(for)e(whic)-31 b(h)311 b(the)f(metho)31
b(d)311 b(is)f(de\014ned.)473 b(This)310 b(metho)31 b(d)311
b(is)f(the)g(initial)j(w)-31 b(orking)9741 22294 y(system.)497
b(Its)371 b(sole)g(function)h(is)e(to)i(w)-31 b(alk)372
b(through)f(the)g(ob)61 b(ject)372 b(hierarc)-31 b(h)g(y)371
b(prin)-31 b(ting)9741 23622 y(the)479 b(v)-61 b(alue)478
b(of)h(an)-31 b(y)479 b(class)f(terminals)i(in)e(the)h(hierarc)-31
b(h)g(y)-92 b(.)820 b(The)478 b(Demeter)h(system)9741
24951 y(supp)31 b(orts)334 b(the)i(prede\014ned)e(class)h(terminals)h
(Iden)-31 b(t,)342 b(Num)-31 b(b)31 b(er,)343 b(and)335
b(String)g(as)g(w)-31 b(ell)9741 26279 y(as)490 b(a)g(facilit)-31
b(y)492 b(for)e(the)g(de\014nition)h(of)f(additional)j(class)c
(terminals.)855 b(The)490 b(en)-31 b(tire)9741 27607
y(system)366 b(is)f(gro)-31 b(wn)366 b(from)g(this)g(simple)g(sk)-31
b(eleton)366 b(program.)492 b(This)366 b(simple)g(program)9741
28936 y(is)j(the)h(sprout)f(from)h(whic)-31 b(h)370 b(the)f(soft)-31
b(w)g(are)371 b(plan)-31 b(t)371 b(will)g(b)31 b(e)368
b(gro)-31 b(wn.)8634 31083 y Fp(\017)554 b Fq(A)330 b(gro)-31
b(wth)332 b(plan)f(generator)g(whic)-31 b(h)331 b(suggests)g(in)f(whic)
-31 b(h)331 b(order)f(to)h(gro)-31 b(w)331 b(the)g(plan)-31
b(t.)9741 32411 y(The)381 b(gro)-31 b(wth)383 b(plan)e(is)g(determined)
h(b)-31 b(y)381 b(the)g(c)-31 b(hromosomes)382 b(\(pro)31
b(ductions\))382 b(in)g(the)9741 33740 y(class)369 b(dictionary)j
(\(seed\).)6974 37371 y Fi(4)1793 b(The)521 b(Gro)-50
b(wth)520 b(and)h(Ev)-50 b(olution)521 b(of)f(a)g(System)i(\(Nur-)9664
39364 y(turing\))6974 41789 y Fq(Once)378 b(a)h(Demeter)g(en)-31
b(vironmen)g(t)380 b(has)f(b)31 b(een)378 b(generated)i(from)f(the)g
(class)f(dictionary)j(de-)6974 43117 y(scription)344
b(w)-31 b(e)344 b(w)-31 b(an)g(t)345 b(our)e(system)g(to)h(gro)-31
b(w)345 b(and)e(ev)-31 b(olv)g(e.)486 b(W)-92 b(e)342
b(will)j(presen)-31 b(t)343 b(t)-31 b(w)g(o)345 b(metho)31
b(ds)6974 44445 y(asso)g(ciated)525 b(with)h(our)e(Meal)h(en)-31
b(vironmen)g(t.)961 b(The)525 b(\014rst)e(is)i(to)g(calculate)i(the)d
(cost)h(of)6974 45774 y(a)542 b(meal.)1010 b(This)542
b(metho)31 b(d)542 b(will)h(w)-31 b(alk)543 b(the)f(ob)61
b(ject)543 b(hierarc)-31 b(h)g(y)542 b(and)f(compute)i(the)e(cost)6974
47102 y(of)479 b(eac)-31 b(h)479 b(ob)61 b(ject)480 b(in)e(the)h
(hierarc)-31 b(h)g(y)-92 b(.)821 b(The)479 b(metho)31
b(d)479 b(is)f(v)-31 b(ery)479 b(mo)31 b(dular,)507 b(thanks)479
b(to)h(the)6974 48430 y(ob)61 b(ject-orien)-31 b(ted)369
b(nature)d(of)g(Demeter,)h(so)f(w)-31 b(e)367 b(can)f(use)g(it)h(to)f
(compute)i(the)e(cost)g(of)h(an)-31 b(y)6974 49759 y(comp)31
b(onen)-31 b(t)300 b(of)f(a)f(meal)i(as)e(w)-31 b(ell.)470
b(W)-92 b(e)298 b(de\014ne)g(fo)31 b(o)g(d)298 b(costs)h(in)f(the)h
(follo)-31 b(wing)302 b(men)-31 b(u:)457 b(Melon)6974
51087 y(0.75,)370 b(Shrimp)f(Co)31 b(c)-31 b(ktail)370
b(0.65)g(p)31 b(er)367 b(shrimp,)i(co)31 b(c)-31 b(ktail)370
b(sauce)e(0.15)i(extra,)f(Steak)g(Platter)6974 52415
y(5.00,)i(Bak)-31 b(ed)370 b(Stu\013ed)f(Shrimp)h(6.00,)h(Pie)f(0.60,)h
(Cak)-31 b(e)371 b(.65,)g(Jello)f(0.35.)8136 54684 y
Fa(;)581 b(Banquet)i(~)e(Meal)h({)f(Meal)h(}.)6974 56012
y(\(defmethod)g(\(Banquet)h(:cost\))f(\(\))8136 57341
y(\(let)g(\(\(total-cost)9298 58669 y(\(loop)g(for)g(each-meal)g(in)g
(child)g(sum)10461 59997 y(\(send)g(each-meal)g(':cost\)\)\)\))10461
61326 y(\(format)g(t)f("cost)h(of)g(~A)f(meals:)h(~A.~\045")11623
62654 y(\(length)g(child\))g(total-cost\)\)\))8136 63982
y(;)f(Meal)h(=)8136 65311 y(;)1744 b("Appetizer:")583
b(Appetizer)p eop
%%Page: 10 10
10 9 bop 6974 4317 a Fj(4)1107 b(THE)370 b(GR)-31 b(O)g(WTH)370
b(AND)f(EV)-31 b(OLUTION)370 b(OF)f(A)g(SYSTEM)g(\(NUR)-92
b(TURING\))1047 b Fq(10)8136 8192 y Fa(;)1744 b("Entree:")582
b(Entree)8136 9520 y(;)1744 b("Dessert")582 b(Dessert.)6974
10848 y(\(defmethod)g(\(Meal)g(:cost\))g(\(\))8136 12177
y(\(+)g(\(send)f(Appetizer)i(':cost\))9880 13505 y(\(send)e(Entree)i
(':cost\))9880 14833 y(\(send)e(Dessert)i(':cost\)\)\))8136
16162 y(;)e(Melon)h(=)g("melon".)6974 17490 y(\(defmethod)g(\(Melon)h
(:cost\))f(\(\))f(0.75\))8136 18818 y(;)g(ShrimpCocktail)j(=)d(Shrimps)
h(Lettuce)8136 20147 y(;)1744 b([CocktailSauce].)6974
21475 y(\(defmethod)582 b(\(ShrimpCocktail)i(:cost\))e(\(\))8136
22803 y(\(+)g(\(send)f(Shrimps)i(':cost\))9880 24132
y(\(if)e(CocktailSauce)11042 25460 y(then)h(\(send)g(CocktailSauce)h
(':cost\))11042 26788 y(else)f(0.0\)\)\))8136 28117 y(;)f(Shrimps)i(~)e
({Shrimp}.)6974 29445 y(\(defmethod)h(\(Shrimps)h(:cost\))f(\(\))8136
30773 y(\(loop)g(for)g(each-shrimp)g(in)g(child)g(sum)9298
32102 y(\(send)g(each-shrimp)h(':cost\)\)\)\))8136 33430
y(;)e(Shrimp)h(=)g("shrimp".)6974 34759 y(\(defmethod)g(\(Shrimp)h
(:cost\))f(\(\))f(0.65\))8136 36087 y(;)g(CocktailSauce)j(=)d(Ketchup)h
(HorseRadish.)6974 37415 y(\(defmethod)g(\(CocktailSauce)i(:cost\))e
(\(\))f(0.15\))8136 38744 y(;)g(SteakPlatter)i(=)f(Steak)g(Trimmings.)
6974 40072 y(\(defmethod)g(\(SteakPlatter)i(:cost\))e(\(\))f(5.00\))
8136 41400 y(;)g(BakedStuffedShrimp)j(=)8136 42729 y(;)1744
b(StuffedShrimp)583 b(Trimmings.)6974 44057 y(\(defmethod)f
(\(BakedStuffedShrimp)i(:cost\))f(\(\))8136 45385 y(6.00\))8136
46714 y(;)e(Pie)h(=)f("pie".)6974 48042 y(\(defmethod)h(\(Pie)g
(:cost\))g(\(\))g(0.60\))8136 49370 y(;)f(Cake)h(=)f("cake".)6974
50699 y(\(defmethod)h(\(Cake)g(:cost\))g(\(\))g(0.70\))8136
52027 y(;)f(Jello)h(=)g("jello".)6974 53355 y(\(defmethod)g(\(Jello)h
(:cost\))f(\(\))f(0.35\))8634 55791 y Fq(W)-92 b(e)304
b(no)-31 b(w)305 b(examine)h(a)e(situation)j(whic)-31
b(h)305 b(is)g(common)h(in)e(soft)-31 b(w)g(are)306 b(dev)-31
b(elopmen)g(t.)473 b(Our)6974 57119 y(restauran)-31 b(t)457
b(o)-31 b(wner)458 b(tak)-31 b(es)457 b(one)g(lo)31 b(ok)458
b(at)g(our)f(\014nished)f(soft)-31 b(w)g(are)459 b(and)e(informs)g(us)g
(that)6974 58447 y(our)308 b(meal)i(de\014nition)g(is)e(all)h(wrong.)
474 b(The)308 b(co)31 b(c)-31 b(ktail)311 b(shrimp)d(should)h(come)g
(in)g(three)f(sizes;)6974 59776 y(small,)353 b(medium,)h(and)347
b(large)h(costing)h(0.20,)354 b(0.50,)f(and)348 b(1.00)h(\(resp)31
b(ectiv)-31 b(ely\).)487 b(W)-92 b(e)347 b(kindly)6974
61104 y(ask)488 b(the)h(irate)f(restauran)-31 b(t)489
b(o)-31 b(wner)489 b(to)g(ha)-31 b(v)g(e)489 b(a)f(seat)h(and)f(relax.)
850 b(W)-92 b(e)488 b(then)g(mak)-31 b(e)490 b(the)6974
62433 y(follo)-31 b(wing)450 b(c)-31 b(hanges)448 b(to)g(our)e(class)h
(dictionary)i(without)g(the)e(least)h(concern)f(of)g(ruining)6974
63761 y(our)367 b(existing)j(system.)492 b(W)-92 b(e)367
b(mo)31 b(dify)370 b(the)e(atomic)i(ob)61 b(ject)369
b Fk(Shrimp)f Fq(to)h(b)31 b(e)367 b(an)h(alternation)6974
65089 y(pro)31 b(duction)370 b(of)g(the)f(follo)-31 b(wing)373
b(form.)p eop
%%Page: 11 11
11 10 bop 6974 4317 a Fj(4)1107 b(THE)370 b(GR)-31 b(O)g(WTH)370
b(AND)f(EV)-31 b(OLUTION)370 b(OF)f(A)g(SYSTEM)g(\(NUR)-92
b(TURING\))1047 b Fq(11)6974 8192 y Fa(Shrimp)582 b(:)f(SmallShrimp)i
(|)e(MediumShrimp)i(|)f(LargeShrimp.)6974 10405 y Fq(W)-92
b(e)468 b(remo)-31 b(v)g(e)470 b(the)f(cost)g(metho)31
b(d)469 b(for)g(shrimp)g(and)g(replace)g(it)h(b)-31 b(y)469
b(the)g(follo)-31 b(wing)472 b(three)6974 11734 y(metho)31
b(d)370 b(de\014nitions)g(\(one)g(for)g(eac)-31 b(h)369
b(of)h(the)f(new)h(atomic)h(ob)61 b(jects\).)6974 13948
y Fa(\(defmethod)582 b(\(SmallShrimp)h(:cost\))f(\(\))g(0.20\))6974
15276 y(\(defmethod)g(\(MediumShrimp)i(:cost\))e(\(\))f(0.50\))6974
16604 y(\(defmethod)h(\(LargeShrimp)h(:cost\))f(\(\))g(1.00\))8634
18818 y Fq(Mo)31 b(di\014cations)472 b(are)e(made)h(at)g(or)f(b)31
b(elo)-31 b(w)471 b(the)g(p)31 b(oin)-31 b(t)471 b(at)g(whic)-31
b(h)471 b(the)f(ob)61 b(ject)472 b(hierar-)6974 20147
y(c)-31 b(h)g(y)424 b(de\014nitions)g(are)g(c)-31 b(hanged.)656
b(This)424 b(allo)-31 b(ws)425 b(the)f(user)e(the)i(freedom)g(of)g(up)
31 b(dating)425 b(his)6974 21475 y(underlying)506 b(data)g(structure)e
(without)j(ha)-31 b(ving)506 b(to)g(w)-31 b(orry)505
b(ab)31 b(out)505 b(the)g(loss)g(of)h(system)6974 22803
y(in)-31 b(tegrit)g(y)-92 b(.)8634 24132 y(The)359 b(next)g(set)g(of)g
(metho)31 b(ds)359 b(w)-31 b(e)359 b(will)h(de\014ne)f(are)f(more)h
(complex.)490 b(W)-92 b(e)358 b(w)-31 b(ould)360 b(lik)-31
b(e)360 b(to)6974 25460 y(sim)-31 b(ulate)350 b(an)e(action)i(suc)-31
b(h)347 b(as)h(eating.)487 b(When)348 b(w)-31 b(e)348
b(eat)h(a)f(meal)h(w)-31 b(e)349 b(are)f(left)h(with)g(ob)61
b(jects)6974 26788 y(whic)-31 b(h)448 b(w)-31 b(e)448
b(refer)f(to)i(as)e(garbage.)729 b(Eac)-31 b(h)449 b(ob)61
b(ject)449 b(in)f(the)f(hierarc)-31 b(h)g(y)449 b(either)e(completely)
6974 28117 y(disapp)31 b(ears)359 b(or)g(lea)-31 b(v)g(es)360
b(some)f(ob)61 b(ject)361 b(b)31 b(ehind.)489 b(F)-92
b(or)359 b(example,)k(a)c(melon)h(lea)-31 b(v)g(es)361
b(a)e(rind,)i(a)6974 29445 y(p)31 b(otato)356 b(lea)-31
b(v)g(es)356 b(a)e(skin,)k(a)d(steak)g(lea)-31 b(v)g(es)356
b(a)e(b)31 b(one)355 b(and)f(p)31 b(ossibly)355 b(some)g(fat,)k(etc.)
488 b(The)354 b(\014rst)6974 30773 y(step)331 b(in)g(suc)-31
b(h)330 b(a)i(task)f(is)g(to)h(build)f(a)h(class)f(dictionary)i(whic)
-31 b(h)331 b(will)i(allo)-31 b(w)334 b(us)c(to)i(represen)-31
b(t)6974 32102 y(and)423 b(build)h(a)f(hierarc)-31 b(h)g(y)424
b(of)f(garbage.)655 b(This)424 b(class)f(dictionary)i(can)e(b)31
b(e)423 b(constructed)g(as)6974 33430 y(follo)-31 b(ws:)6974
35644 y Fa(Gbanquet)582 b(~)f(Gmeal)h({Gmeal}.)6974 36972
y(Gmeal)g(=)8136 38301 y("Appetizer)h(Garbage:")f(Gappetizer)8136
39629 y("Entree)g(Garbage:")h(Gentree)8136 40958 y("Dessert)f
(Garbage:")h(Gdessert.)6974 42286 y(Gappetizer)f(:)g(Rind)g(|)f
(GShrimpCocktail.)6974 43614 y(GshrimpCocktail)i(=)f(Shrimptails)g
(Lettuce)8136 44943 y([CocktailSauce].)6974 46271 y(Shrimptails)h(~)e
(Shrimptail)i({Shrimptail}.)6974 47599 y(Gentree)f(:)f(Gsteak)h(|)g
(Gshrimp.)6974 48928 y(Gsteak)g(=)f([)g(Bones)h(])g([)f(Fat)h(])f
(Gtrimmings.)6974 50256 y(Gshrimp)h(=)f(Shrimptail)i(Gtrimmings.)6974
51584 y(Gtrimmings)f(=)g(PotatoSkin.)6974 52913 y(Gdessert)g(:)f(Crust)
h(|)g(Frosting)g(|)f(GJello.)6974 54241 y(GJello)h(=)f([)g(Jello)h(])g
([)f(WhippedCream)i(].)6974 56455 y Fq(The)369 b(follo)-31
b(wing)373 b(sym)-31 b(b)31 b(ols)370 b(in)f(this)h(class)f(dictionary)
6974 58669 y Fa(Rind,)582 b(Shrimptail,)h(Bones,)f(Fat,)f(PotatoSkin,)
6974 59997 y(Crust,)h(Frosting,)g(Jello,)g(WhippedCream.)6974
62211 y Fq(are)372 b(de\014ned)g(b)-31 b(y)373 b(construction)h(pro)31
b(ductions)373 b(eac)-31 b(h)373 b(consisting)h(of)f(one)g(or)f(more)h
(strings,)6974 63540 y(e.g.,)p eop
%%Page: 12 12
12 11 bop 6974 4317 a Fj(4)1107 b(THE)370 b(GR)-31 b(O)g(WTH)370
b(AND)f(EV)-31 b(OLUTION)370 b(OF)f(A)g(SYSTEM)g(\(NUR)-92
b(TURING\))1047 b Fq(12)6974 8192 y Fa(Fat)581 b(=)h("fat".)6974
9520 y(WhippedCream)h(=)e("whipped")i("cream".)6974 10848
y(etc.)8634 12767 y Fq(In)348 b(this)h(example)g(steak)g(and)g(jello)h
(can)e(return)g(some)h(optional)h(garbage.)487 b(F)-92
b(or)348 b(these)6974 14095 y(optional)289 b(c)-31 b(hoices)287
b(w)-31 b(e)287 b(\015ip)g(a)g(coin.)466 b(F)-92 b(or)286
b(example,)305 b(some)287 b(steaks)f(will)j(lea)-31 b(v)g(e)288
b(b)31 b(ehind)286 b(b)31 b(ones)6974 15424 y(and)369
b(fat)h(when)g(eaten)g(but)f(others)g(will)i(not.)8136
17490 y Fa(;)581 b(Banquet)i(~)e(Meal)h({)f(Meal)h(}.)6974
18818 y(\(defmethod)g(\(Banquet)h(:eat\))f(\(\))8136
20147 y(\(make-instance)h('Gbanquet)9298 21475 y(':child)6974
22803 y(;)e(initialize)i(Gbanquet)f(slot)g(called)g(child)10461
24132 y(\(loop)g(for)f(each-meal)i(in)e(child)h(collect)11623
25460 y(\(send)g(each-meal)g(':eat\)\)\)\))8136 26788
y(;)f(Meal)h(=)f(Appetizer)i(Entree)f(Dessert.)6974 28117
y(\(defmethod)g(\(Meal)g(:eat\))g(\(\))8136 29445 y(\(make-instance)h
('Gmeal)9298 30773 y(':Gappetizer)g(\(send)f(Appetizer)h(':eat\))9298
32102 y(':Gentree)g(\(send)f(Entree)g(':eat\))9298 33430
y(':Gdessert)h(\(send)f(Dessert)g(':eat\)\)\))8136 34759
y(;)f(ShrimpCocktail)j(=)d(Shrimps)h(Lettuce)8136 36087
y(;)1744 b([CocktailSauce].)6974 37415 y(\(defmethod)582
b(\(ShrimpCocktail)i(:eat\))e(\(\))8136 38744 y(\(make-instance)h
('GshrimpCocktail)9298 40072 y(':Shrimptails)h(\(send)d(Shrimps)i
(':eat\))9298 41400 y(':Lettuce)g(\(send)f(Lettuce)g(':copy\))9298
42729 y(':CocktailSauce)10461 44057 y(\(send)g(CocktailSauce)h
(':copy\)\)\))9298 45385 y(;)f(copy)f(returns)i(a)e(new)h(object)9298
46714 y(;)g(which)g(is)f(a)g(copy)h(of)g(the)f(argument)8136
48042 y(;)g(Shrimps)i(~)e({Shrimp}.)6974 49370 y(\(defmethod)h
(\(Shrimps)h(:eat\))f(\(\))8136 50699 y(\(make-instance)h('Shrimptails)
9298 52027 y(':child)g(\(loop)f(for)f(each-shrimp)10461
53355 y(in)g(child)h(collect)11623 54684 y(\(send)g(each-shrimp)h
(':eat\)\)\)\))8136 56012 y(;)e(Shrimp)h(=)g("shrimp".)6974
57341 y(\(defmethod)g(\(Shrimp)h(:eat\))f(\(\))8136 58669
y(\(make-instance)h('ShrimpTail\)\))8136 59997 y(;)e(SteakPlatter)i(=)f
(Steak)g(Trimmings.)6974 61326 y(\(defmethod)g(\(SteakPlatter)i(:eat\))
d(\(\))8136 62654 y(\(make-instance)i('Gsteak)9298 63982
y(':Bones)10461 65311 y(\(if)e(\(eql)h(\(flip\))g('head\))p
eop
%%Page: 13 13
13 12 bop 6974 4317 a Fj(4)1107 b(THE)370 b(GR)-31 b(O)g(WTH)370
b(AND)f(EV)-31 b(OLUTION)370 b(OF)f(A)g(SYSTEM)g(\(NUR)-92
b(TURING\))1047 b Fq(13)11042 8192 y Fa(then)582 b(\(make-instance)h
('Bones\))11042 9520 y(else)f(nil\))9298 10848 y(':Fat)10461
12177 y(\(if)f(\(eql)h(\(flip\))g('head\))11623 13505
y(then)g(\(make-instance)h('Fat\))11623 14833 y(else)f(nil\))9298
16162 y(':Gtrimmings)h(\(send)f(Trimmings)h(':eat\)\)\))8136
17490 y(;)e(BakedStuffedShrimp)j(=)8136 18818 y(;)1744
b(StuffedShrimp)583 b(Trimmings.)6974 20147 y(\(defmethod)f
(\(BakedStuffedShrimp)i(:eat\))e(\(\))8136 21475 y(\(make-instance)h
('Gshrimp)9298 22803 y(':Shrimptail)g(\(send)f(StuffedShrimp)h(':eat\))
9298 24132 y(':Gtrimmings)g(\(send)f(Trimmings)h(':eat\)\)\))8136
25460 y(;)e(Trimmings)i(=)e(Potato)8136 26788 y(;)1744
b(<veggie1>)582 b(Veggie)g(<veggie2>)h(Veggie.)6974 28117
y(\(defmethod)f(\(Trimmings)h(:eat\))f(\(\))8136 29445
y(\(make-instance)h('PotatoSkin\)\))8136 30773 y(;)e(Pie)h(=)f("pie".)
6974 32102 y(\(defmethod)h(\(Pie)g(:eat\))g(\(\))8136
33430 y(\(make-instance)h('Crust\)\))8136 34759 y(;)e(Cake)h(=)f
("cake".)6974 36087 y(\(defmethod)h(\(Cake)g(:eat\))g(\(\))8136
37415 y(\(make-instance)h('Frosting\)\))8136 38744 y(;)e(Jello)h(=)g
("jello".)6974 40072 y(\(defmethod)g(\(Jello)h(:eat\))e(\(\))8136
41400 y(\(make-instance)i('GJello)9298 42729 y(':Jello)10461
44057 y(\(if)e(\(eql)h(\(flip\))g('head\))11623 45385
y(then)g(\(make-instance)h('Jello\))11623 46714 y(else)f(nil\))9298
48042 y(':WhippedCream)10461 49370 y(\(if)f(\(eql)h(\(flip\))g('head\))
11623 50699 y(then)g(\(make-instance)h('WhippedCream\))11623
52027 y(else)f(nil\)\)\))6974 54377 y Fq(In)369 b(suc)-31
b(h)368 b(a)i(system)f(a)h(meal)g(input)g(\014le)f(migh)-31
b(t)372 b(lo)31 b(ok)370 b(lik)-31 b(e:)8136 56523 y
Fa(Appetizer:)9298 57851 y(smallshrimp)583 b(smallshrimp)g(smallshrimp)
9298 59180 y(lettuce)8136 60508 y(Entree:)f(steak)g(potato)g(corn)g
(peas)8136 61836 y(Dessert:)g(pie)8634 63982 y Fq(After)467
b(sending)f(this)g(ob)61 b(ject)468 b(hierarc)-31 b(h)g(y)466
b(the)h(:eat)g(message)g(w)-31 b(e)466 b(get)h(a)f(garbage)i(hi-)6974
65311 y(erarc)-31 b(h)g(y)442 b(returned)g(to)i(us.)712
b(W)-92 b(e)442 b(can)g(send)g(this)h(returned)f(hierarc)-31
b(h)g(y)443 b(the)g(prett)-31 b(y)443 b(prin)-31 b(t)p
eop
%%Page: 14 14
14 13 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(14)6974 8192 y(message)369
b(\(a)h(Demeter)f(generated)h(metho)31 b(d\))371 b(and)e(prin)-31
b(t)370 b(the)g(follo)-31 b(wing)372 b(ASCI)31 b(I)369
b(text.)6974 10405 y Fa(Appetizer)582 b(Garbage:)8136
11734 y(shrimptail)h(shrimptail)f(shrimptail)8136 13062
y(lettuce)6974 14390 y(Entree)g(Garbage:)g(bones)g(fat)g(potato)g(skin)
6974 15719 y(Dessert)g(Garbage:)g(crust)8634 17933 y
Fq(This)386 b(tec)-31 b(hnique)386 b(is)g(p)31 b(o)-31
b(w)g(erful)386 b(in)g(that)g(y)-31 b(ou)386 b(can)g(ev)-31
b(olv)g(e)387 b(one)f(ob)61 b(ject)386 b(hierarc)-31
b(h)g(y)386 b(in)-31 b(to)6974 19261 y(another)338 b(fairly)h(easily)
-92 b(.)483 b(This)338 b(easy)g(ev)-31 b(olution)341
b(frees)c(us)g(from)h(the)g(b)31 b(ounds)337 b(of)h(ine\013ectiv)-31
b(e)6974 20589 y(programming)304 b(languages)f(and)g(allo)-31
b(ws)303 b(us)f(the)g(lib)31 b(ert)-31 b(y)303 b(of)f(declaring)h(the)f
(follo)-31 b(wing)305 b(rule:)6974 21918 y(\\If)391 b(the)h(language)h
(y)-31 b(ou)392 b(are)f(w)-31 b(orking)393 b(with)f(do)31
b(es)391 b(not)h(allo)-31 b(w)393 b(y)-31 b(ou)392 b(to)g(write)g(a)f
(necessary)6974 23246 y(task)349 b(comfortably)-92 b(,)356
b(then)350 b(create)f(y)-31 b(our)349 b(o)-31 b(wn)350
b(language)h(and)e(translate)i(the)e(curren)-31 b(t)348
b(rep-)6974 24575 y(resen)-31 b(tation)472 b(in)-31 b(to)472
b(the)e(new)h(represen)-31 b(tation.")798 b(This)471
b(rule)f(is)g(meaningful)j(only)f(if)f(the)6974 25903
y(task)371 b(of)g(creating)h(a)f(new)g(language)i(and)e(building)i(a)e
(translator)h(is)e(signi\014can)-31 b(tly)374 b(easier)6974
27231 y(than)c(the)f(original)j(task.)493 b(This)370
b(is)f(usually)h(the)f(case)g(within)i(the)f(realm)g(of)f(Demeter.)6974
30892 y Fi(5)1793 b(Inheritance)599 b(\(Grafting\))6974
33316 y Fq(There)389 b(are)h(three)g(w)-31 b(a)g(ys)391
b(of)f(acquiring)h(plan)-31 b(ts.)556 b(The)390 b(easiest)g(and)g(most)
h(exp)31 b(ensiv)-31 b(e)390 b(w)-31 b(a)g(y)6974 34645
y(is)396 b(to)h(buy)g(mature)g(plan)-31 b(ts.)576 b(The)396
b(ma)61 b(jor)398 b(dra)-31 b(wbac)g(k)398 b(\(b)31 b(esides)396
b(cost\))i(of)f(this)f(metho)31 b(d)398 b(is)6974 35973
y(the)419 b(una)-31 b(v)-61 b(ailabilit)-31 b(y)424 b(of)c(man)-31
b(y)421 b(v)-61 b(arieties.)643 b(Man)-31 b(y)420 b(plan)-31
b(t)421 b(fanciers)e(decide)h(to)g(gro)-31 b(w)420 b(their)6974
37301 y(fa)-31 b(v)g(orite)326 b(v)-61 b(arieties)324
b(from)g(seed.)477 b(While)324 b(the)g(cost)g(ma)-31
b(y)324 b(b)31 b(e)323 b(lo)-31 b(w)g(er,)335 b(the)324
b(time)h(in)-31 b(v)g(olv)g(ed)326 b(can)6974 38630 y(b)31
b(e)446 b(quite)i(substan)-31 b(tial.)729 b(In)447 b(addition,)469
b(there)447 b(are)g(man)-31 b(y)448 b(things)g(whic)-31
b(h)448 b(can)f(go)h(wrong)6974 39958 y(as)j(our)h(seed)f(tak)-31
b(es)452 b(the)g(long)h(trip)f(from)g(sprout)g(to)g(mature)h(plan)-31
b(t.)741 b(In)452 b(the)g(w)-31 b(orld)452 b(of)6974
41287 y(soft)-31 b(w)g(are)347 b(dev)-31 b(elopmen)g(t)349
b(w)-31 b(e)346 b(\014nd)g(w)-31 b(e)347 b(ha)-31 b(v)g(e)347
b(the)f(same)g(t)-31 b(w)g(o)348 b(c)-31 b(hoices.)485
b(Either)347 b(w)-31 b(e)347 b(buy)f(the)6974 42615 y(necessary)e(soft)
-31 b(w)g(are)346 b(from)g(someone)f(who)h(has)f(already)h(dev)-31
b(elop)31 b(ed)345 b(it)h(or)f(w)-31 b(e)345 b(dev)-31
b(elop)346 b(it)6974 43943 y(ourselv)-31 b(es.)581 b(Again)401
b(w)-31 b(e)399 b(ha)-31 b(v)g(e)400 b(the)f(same)g(adv)-61
b(an)-31 b(tages)400 b(and)f(dra)-31 b(wbac)g(ks.)583
b(There)398 b(is)h(a)g(fair)6974 45272 y(c)-31 b(hance)368
b(that)h(the)f(a)-31 b(v)-61 b(ailable)370 b(soft)-31
b(w)g(are)369 b(will)h(not)e(b)31 b(e)367 b(the)h(sp)31
b(eci\014c)367 b(v)-61 b(ariet)-31 b(y)369 b(w)-31 b(e)368
b(w)-31 b(an)g(t)369 b(or)f(it)6974 46600 y(ma)-31 b(y)338
b(b)31 b(e)337 b(of)h(dubious)f(qualit)-31 b(y)-92 b(.)485
b(If)337 b(w)-31 b(e)337 b(decide)h(to)g(dev)-31 b(elop)338
b(it)g(ourselv)-31 b(es)337 b(then)h(w)-31 b(e)337 b(m)-31
b(ust)338 b(b)31 b(e)6974 47928 y(willing)423 b(to)e(w)-31
b(ait)422 b(a)f(long)h(time)f(and)g(there)f(is)g(alw)-31
b(a)g(ys)423 b(the)d(c)-31 b(hance)421 b(of)g(something)h(going)6974
49257 y(wrong)370 b(during)f(that)i(long)f(dev)-31 b(elopmen)g(t)372
b(pro)31 b(cess.)8634 50585 y(Man)-31 b(y)342 b(horticulturists)h(lo)31
b(ok)343 b(to)f(a)g(third)g(alternativ)-31 b(e)344 b(called)f
(grafting.)485 b(The)342 b(pro)31 b(cess)6974 51913 y(of)330
b(grafting)h(in)-31 b(v)g(olv)g(es)331 b(splicing)g(together)f(part)g
(of)f(a)h(desired)e(plan)-31 b(t)331 b(with)f(a)g(host)g(plan)-31
b(t)330 b(of)6974 53242 y(a)318 b(related)h(t)-31 b(yp)31
b(e.)476 b(This)318 b(metho)31 b(d)319 b(has)f(the)g(adv)-61
b(an)-31 b(tage)320 b(in)e(that)h(the)f(cost)h(is)e(lo)-31
b(w)320 b(and)e(m)-31 b(uc)g(h)6974 54570 y(of)372 b(the)h(risk)e(of)i
(n)-31 b(urturing)373 b(a)f(seed)f(to)i(maturit)-31 b(y)375
b(is)d(remo)-31 b(v)g(ed.)502 b(Soft)-31 b(w)g(are)374
b(dev)-31 b(elop)31 b(ers)372 b(are)6974 55898 y(usually)427
b(at)f(a)h(loss)e(when)h(they)h(attempt)h(this)e(third)g(alternativ)-31
b(e.)666 b(While)426 b(plan)-31 b(ts)427 b(ha)-31 b(v)g(e)6974
57227 y(a)458 b(common)i(in)-31 b(terface)459 b(\(t)-31
b(ypically)462 b(a)c(w)-31 b(o)31 b(o)g(dy)460 b(tissue\))e(soft)-31
b(w)g(are)460 b(systems)e(do)g(not.)761 b(The)6974 58555
y(c)-31 b(hances)328 b(of)g(t)-31 b(w)g(o)329 b(systems)f(using)g(the)g
(same)g(underlying)h(data)g(structure,)336 b(the)328
b(same)g(lan-)6974 59883 y(guage,)423 b(and)411 b(b)31
b(eing)411 b(mo)31 b(dular)412 b(enough)f(to)g(tak)-31
b(e)412 b(functions)g(for)f(reuse)f(in)h(a)g(new)g(system)6974
61212 y(are)397 b(v)-31 b(ery)398 b(lo)-31 b(w.)580 b(The)398
b(Demeter)g(system)g(a)-31 b(v)g(oids)399 b(these)e(problems)i(b)-31
b(y)398 b(pro)-31 b(viding)399 b(a)f(com-)6974 62540
y(mon)412 b(language)i(for)e(the)h(abstract)f(data)h(structure)f(of)g
(eac)-31 b(h)413 b(system,)423 b(a)412 b(means)g(of)h(easy)6974
63869 y(language)396 b(translation,)403 b(and)394 b(v)-31
b(ery)394 b(mo)31 b(dular)395 b(co)31 b(ding.)569 b(This)394
b(latter)h(qualit)-31 b(y)397 b(is)d(enforced)p eop
%%Page: 15 15
15 14 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(15)6974 8192 y(b)-31 b(y)369
b(the)h(underlying)g(ob)61 b(ject-orien)-31 b(ted)372
b(tec)-31 b(hnology)371 b(and)f(the)f(La)-31 b(w)370
b(of)g(Demeter)40899 7790 y Ff(2)41396 8192 y Fq(.)8634
9520 y(The)437 b(Demeter)f(system)g(grafts)h(one)g(soft)-31
b(w)g(are)437 b(system)g(on)-31 b(to)438 b(another)f(through)g(the)6974
10848 y(use)479 b(of)h(the)g(k)-31 b(eyw)g(ords)481 b
Fp(\003)p Fq(inherit)p Fp(\003)g Fq(and)f Fp(\003)p Fq(o)-31
b(v)g(erride)p Fp(\003)481 b Fq(in)f(the)g(class)f(descriptions.)825
b(If)479 b(an)6974 12177 y Fp(\003)p Fq(inherit)p Fp(\003)367
b Fq(k)-31 b(eyw)g(ord)366 b(pre\014xes)e(a)i(sym)-31
b(b)31 b(ol)366 b(it)g(sp)31 b(eci\014es)364 b(that)j(the)e(class)g(is)
h(to)f(b)31 b(e)365 b(\\copied")6974 13505 y(in)-31 b(to)512
b(the)e(host)h(system.)917 b(F)-92 b(or)509 b(the)i(purp)31
b(ose)510 b(of)g(language)j(de\014nition)f(the)f(cop)-31
b(ying)512 b(is)6974 14833 y(explicit.)494 b(F)-92 b(or)369
b(example,)6974 17047 y Fa(A)581 b(=)g(Ident)h(Number.)6974
18376 y(B)f(=)g(String)h(*inherit*)h(A)e("end".)6974
20589 y Fq(implies)370 b(that)h(the)e(language)j Fb(B)d
Fq(is)g(de\014ned)g(b)-31 b(y)6974 22803 y Fa(B)581 b(=)g(String)h
(Ident)g(Number)g("end".)8634 25017 y Fq(F)-92 b(or)428
b(the)g(purp)31 b(ose)427 b(of)i(class)f(de\014nition)i(w)-31
b(e)428 b(use)g(the)g(inheritance)i(seman)-31 b(tics)429
b(of)g(the)6974 26346 y(underlying)527 b(ob)61 b(ject-orien)-31
b(ted)528 b(system.)962 b(In)526 b(the)g(ab)31 b(o)-31
b(v)g(e)527 b(example)g(w)-31 b(e)526 b(simply)h(sp)31
b(ecify)6974 27674 y(that)318 b(class)e(B)h(inherits)g(from)g(class)g
(A.)g(W)-92 b(e)316 b(mak)-31 b(e)318 b(the)f(assumption)h(that)g(the)f
(underlying)6974 29002 y(ob)61 b(ject-orien)-31 b(ted)352
b(system)e(uses)e(dynamic)j(binding)f(of)g(the)g(\014rst)f(argumen)-31
b(t,)355 b(often)c(called)6974 30331 y Fb(self)p Fq(.)1038
b(This)551 b(implies)g(that)h(the)f(metho)31 b(ds)551
b(attac)-31 b(hed)553 b(to)e(sup)31 b(erclasses)549 b(of)i(a)g(class)g
(are)6974 31659 y(a)-31 b(v)-61 b(ailable)372 b(at)e(that)g(class.)493
b(A)369 b(more)g(detailed)i(discussion)f(of)f(inheritance)i(is)e(giv)
-31 b(en)370 b(later.)8634 32987 y(The)379 b Fp(\003)p
Fq(o)-31 b(v)g(erride)p Fp(\003)379 b Fq(k)-31 b(eyw)g(ord)380
b(is)e(only)h(used)e(in)i(conjunction)h(with)f(the)f
Fp(\003)p Fq(inherit)p Fp(\003)i Fq(k)-31 b(ey-)6974
34316 y(w)g(ord.)486 b(It)347 b(sp)31 b(eci\014es)346
b(that)i(the)g(class)f(is)g(to)g(b)31 b(e)347 b(inherited)h(with)g
(some)f(c)-31 b(hanges)348 b(whic)-31 b(h)348 b(will)6974
35644 y(alw)-31 b(a)g(ys)430 b(b)31 b(e)427 b(declared)h(after)g(the)g
Fp(\003)p Fq(o)-31 b(v)g(erride)p Fp(\003)429 b Fq(k)-31
b(eyw)g(ord.)669 b(A)427 b(similar)i(approac)-31 b(h)429
b(is)f(tak)-31 b(en)6974 36972 y(in)369 b(T)-92 b(rellis/Owl)372
b([SCB*86)r(].)8634 38301 y(Our)412 b(motiv)-61 b(ation)417
b(for)c(using)g(o)-31 b(v)g(erride)413 b(is)g(as)g(follo)-31
b(ws:)582 b(A)413 b(sub)31 b(class)413 b(is)f(made)i(from)f(a)6974
39629 y(n)-31 b(um)g(b)31 b(er)453 b(of)h(sup)31 b(erclasses)452
b(b)-31 b(y)454 b(sp)31 b(ecifying)454 b(additional)i(prop)31
b(erties)453 b(\(instance)i(v)-61 b(ariables)6974 40958
y(and)452 b(metho)31 b(ds\))452 b(that)h(elemen)-31 b(ts)453
b(of)f(the)g(sub)31 b(class)451 b(m)-31 b(ust)452 b(ha)-31
b(v)g(e)453 b(compared)f(to)h(elemen)-31 b(ts)6974 42286
y(of)459 b(the)f(sup)31 b(erclasses.)759 b(It)458 b(is)h(also)g
(necessary)f(to)h(mak)-31 b(e)459 b(a)g(sub)31 b(class)458
b(in)g(whic)-31 b(h)460 b(some)e(of)6974 43614 y(the)348
b(prop)31 b(erties)347 b(inherited)h(from)g(sup)31 b(erclasses)346
b(are)h(mo)31 b(di\014ed.)486 b(Inherited)348 b(metho)31
b(ds)348 b(and)6974 44943 y(instance)250 b(v)-61 b(ariable)250
b(t)-31 b(yp)31 b(es)249 b(can)g(b)31 b(e)249 b(mo)31
b(di\014ed)250 b(in)f(a)g(sub)31 b(class,)273 b(sub)61
b(ject)250 b(to)g(some)f(restrictions)6974 46271 y(that)370
b(insure)f(that)h(the)g(inheritance)g(is)f(conceptually)j(a)d(sp)31
b(ecialization)372 b(hierarc)-31 b(h)g(y)-92 b(.)8634
47599 y(The)285 b(abilit)-31 b(y)288 b(to)e(mo)31 b(dify)286
b(the)f(t)-31 b(yp)31 b(e)285 b(of)h(instance)g(v)-61
b(ariables)285 b(in)g(sub)31 b(classes)284 b(is)h(restricted)6974
48928 y(in)396 b(suc)-31 b(h)396 b(a)g(w)-31 b(a)g(y)397
b(that)h(static)f(t)-31 b(yp)31 b(e)396 b(c)-31 b(hec)g(king)398
b(of)e(the)h(class)f(de\014nitions)h(is)f(still)h(p)31
b(ossible.)6974 50256 y(If)505 b(this)h(prop)31 b(ert)-31
b(y)506 b(is)g(violated,)542 b(a)506 b(w)-31 b(arning)508
b(will)f(b)31 b(e)505 b(giv)-31 b(en.)904 b(W)-92 b(e)505
b(w)-31 b(an)g(t)507 b(the)f(Demeter)6974 51584 y(system)485
b(to)g(b)31 b(e)485 b(able)g(to)h(guaran)-31 b(tee)486
b(that)g(if)g(B)e(inherits)h(from)h(A)e(then)i(all)g(ob)61
b(jects)485 b(in)6974 52913 y(class)422 b(B)g(ma)-31
b(y)423 b(safely)g(b)31 b(e)422 b(treated)g(as)g(A-ob)61
b(jects.)653 b(If)422 b(B)f(is)h(de\014ned)g(b)-31 b(y)422
b(inheriting)i(from)6974 54241 y(A)363 b(and)f(adding)i(additional)i(v)
-61 b(ariables,)365 b(then)e(the)g(B-ob)61 b(jects)364
b(ma)-31 b(y)364 b(b)31 b(e)362 b(treated)h(safely)h(as)6974
55569 y(A-ob)61 b(jects.)477 b(If)320 b(B)f(is)h(de\014ned)f(b)-31
b(y)320 b(inheriting)h(from)f(A)g(and)g(mo)31 b(difying)322
b(some)e(of)g(the)g(t)-31 b(yp)31 b(es)6974 56898 y(of)492
b(the)g(inherited)g(instance)h(v)-61 b(ariables)492 b(\(i.e.)862
b(using)492 b(an)g Fp(\003)p Fq(o)-31 b(v)g(erride)p
Fp(\003)493 b Fq(clause\))g(then)f(the)6974 58226 y(rule)320
b(that)i(the)f(t)-31 b(yp)31 b(e)320 b(m)-31 b(ust)322
b(b)31 b(e)319 b(sp)31 b(ecialized)322 b(will)g(insure)e(that)i(B-ob)61
b(jects)321 b(ma)-31 b(y)322 b(b)31 b(e)320 b(treated)6974
59554 y(safely)438 b(as)f(A-ob)61 b(jects.)698 b(The)438
b(B-ob)61 b(jects)438 b(will)h(kno)-31 b(w)439 b(ab)31
b(out)438 b(all)h(the)e(messages)g(that)i(are)6974 60883
y(kno)-31 b(wn)370 b(to)g(A-ob)61 b(jects.)p 6974 61591
15276 45 v 8206 62307 a Fe(2)8668 62620 y Fd(The)301
b(La)-26 b(w)301 b(of)h(Demeter)g(states)h(that)f(messages)h(ma)-26
b(y)302 b(only)g(b)26 b(e)302 b(sen)-26 b(t)301 b(to)i(self)e(and)h(ob)
52 b(jects)302 b(whic)-26 b(h)302 b(are)6974 63671 y(an)324
b(instance)g(of)f(a)h(t)-26 b(yp)26 b(e)323 b(whic)-26
b(h)323 b(is)h(asso)26 b(ciated)326 b(with)d(the)h(instance)g(v)-52
b(ariable)324 b(t)-26 b(yp)26 b(es)323 b(or)h(argumen)-26
b(t)323 b(t)-26 b(yp)26 b(es)6974 64723 y(of)313 b(the)h(giv)-26
b(en)314 b(metho)26 b(d.)419 b(This)313 b(la)-26 b(w)314
b(is)g(discussed)g(in)g([LHR88)q(])p eop
%%Page: 16 16
16 15 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(16)8634 8192 y(There)401 b(is)g(an)g
(alternate)h(w)-31 b(a)g(y)402 b(of)g(sp)31 b(ecifying)401
b(inheritance)h(in)f(the)g(Demeter)g(system:)6974 9520
y(w)-31 b(e)455 b(can)f(use)g(an)h(alternation)i(pro)31
b(duction)456 b(with)f(implied)h(inheritance.)750 b(Syn)-31
b(tactically)6974 10848 y(this)413 b(is)g(expressed)f(b)-31
b(y)413 b(using)g(the)g(the)g(*common*)j(tok)-31 b(en)414
b(after)f(the)g(alternativ)-31 b(es.)627 b(F)-92 b(or)6974
12177 y(example,)8717 14390 y Fa(Object)582 b(:)g(Pen)f(|)h(Brick)14529
15719 y(*common*)g(<weight>)g(Number.)8717 17047 y(Pen)g(=)f(...)8717
18376 y(Brick)h(=)f(...)6974 20589 y Fq(de\014nes)452
b(an)g(abstract)i(class)e(\(one)h(whic)-31 b(h)454 b(will)g(nev)-31
b(er)452 b(b)31 b(e)452 b(instan)-31 b(tiated\))456 b(Ob)61
b(ject)454 b(whic)-31 b(h)6974 21918 y(is)462 b(inherited)h(b)-31
b(y)462 b(b)31 b(oth)462 b(P)-31 b(en)463 b(and)f(Bric)-31
b(k.)772 b(P)-31 b(en)462 b(and)g(Bric)-31 b(k)463 b(ha)-31
b(v)g(e)463 b(a)f(common)i(instance)6974 23246 y(v)-61
b(ariable)483 b(called)g(w)-31 b(eigh)g(t.)832 b(It)482
b(is)g(helpful)h(to)f(think)h(of)f(these)g(classes)f(in)h(terms)g(of)h
(lik)-31 b(e)6974 24575 y(relations.)550 b(W)-92 b(e)387
b(sa)-31 b(y)388 b(that)h(a)f(P)-31 b(en)388 b(is)g(lik)-31
b(e)389 b(a)f(Bric)-31 b(k)388 b(in)g(that)h(they)g(share)e(a)h(common)
i(data)6974 25903 y(de\014nition,)556 b(namely)-92 b(,)555
b(a)517 b(w)-31 b(eigh)g(t.)938 b(Alternation)519 b(pro)31
b(ductions)517 b(are)g(the)g(preferred)e(w)-31 b(a)g(y)6974
27231 y(of)501 b(in)-31 b(tro)31 b(ducing)502 b(inheritance)g(since)e
(it)h(expresses)e(the)i(generalization)j(principle)d(in)f(a)6974
28560 y(natural)383 b(w)-31 b(a)g(y)-92 b(.)532 b(Of)382
b(course,)j(for)d(the)g(purp)31 b(oses)381 b(of)i(grafting)h(from)e
(previously)h(dev)-31 b(elop)31 b(ed)6974 29888 y(pro)61
b(jects,)538 b(the)503 b(explicit)i Fp(\003)p Fq(inherit)p
Fp(\003)g Fq(is)e(necessary)-92 b(.)894 b(W)-92 b(e)503
b(assume)g(that)h(the)g(underlying)6974 31216 y(ob)61
b(ject-orien)-31 b(ted)372 b(system)d(supp)31 b(orts)369
b(transitivit)-31 b(y)372 b(of)e(the)f(inheritance)h(relation.)8634
32545 y(Our)268 b(class)g(dictionary)i(notation)g(requires)d(that)j(w)
-31 b(e)268 b(giv)-31 b(e)269 b(our)f(data)h(t)-31 b(yp)31
b(e)269 b(information)6974 33873 y(precisely)378 b(for)f(instance)i(v)
-61 b(ariables.)518 b(If)378 b(w)-31 b(e)378 b(sa)-31
b(y)378 b(that)h(an)f(instance)g(v)-61 b(ariable)379
b(x)f(is)f(of)h(t)-31 b(yp)31 b(e)6974 35201 y(A,)427
b(where)f(A)h(is)g(de\014ned)f(b)-31 b(y)427 b(a)g(construction)h(pro)
31 b(duction)427 b(then)g(x)g(cannot)h(con)-31 b(tain)429
b(an)6974 36530 y(instance)371 b(of)f(a)g(sub)31 b(class)370
b(of)g(A;)h(it)g(has)e(to)i(b)31 b(e)370 b(an)g(instance)h(of)f(A.)h
(If)f(w)-31 b(e)370 b(w)-31 b(an)g(t)372 b(to)f(store)e(a)6974
37858 y(subt)-31 b(yp)31 b(e)353 b(of)h(A)f(in)h(x)f(w)-31
b(e)354 b(cannot)g(de\014ne)f(A)g(b)-31 b(y)354 b(a)f(construction)i
(pro)31 b(duction;)360 b(w)-31 b(e)354 b(ha)-31 b(v)g(e)354
b(to)6974 39186 y(use)368 b(an)i(alternation)i(pro)31
b(duction)370 b(whic)-31 b(h)370 b(sp)31 b(eci\014es)368
b(the)i(legal)h(subt)-31 b(yp)31 b(es)369 b(of)g(A.)8634
40515 y(F)-92 b(or)359 b(the)g(de\014nition)i(of)f(legalit)-31
b(y)363 b(of)d(ob)61 b(jects)360 b(and)g(for)f(subt)-31
b(yping,)363 b(w)-31 b(e)360 b(need)f(to)h(de\014ne)6974
41843 y(the)442 b(set)h(of)g(classes)f(asso)31 b(ciated)443
b(with)h(a)e(giv)-31 b(en)444 b(class.)712 b(As)442 b(an)h
(abbreviation)i(of)e(asso)31 b(ci-)6974 43171 y(ated\(S\))371
b(w)-31 b(e)369 b(use)g(S'.)6974 45607 y Fc(De\014nition)425
b(1)554 b Fk(F)-85 b(or)443 b(a)g(c)-57 b(onstruction,)456
b(r)-57 b(ep)g(etition)445 b(or)e(terminal)h(class)f
Fh(S)64 b Fk(,)455 b Fq(S')444 b Fk(is)f Fh(S)64 b Fk(.)652
b(F)-85 b(or)6974 46935 y(an)346 b(alternation)g(class)f
Fh(S)64 b Fk(,)356 b Fq(S')347 b Fk(c)-57 b(onsists)346
b(of)g(the)g(union)h(of)g(the)f(classes)f(asso)-57 b(ciate)g(d)346
b(with)f(the)6974 48263 y(alternatives)396 b(on)g(the)g
(right-hand-side)f(of)i(the)e(alternation)h(pr)-57 b(o)g(duction.)8634
50699 y Fq(F)-92 b(or)369 b(the)g(follo)-31 b(wing)373
b(class)c(dictionary)-92 b(,)8717 52913 y Fa(Expression)583
b(:)e(Simple)h(|)g(Compound.)8717 54241 y(Simple)g(:)g(Ident)g(|)f
(Number.)8717 55569 y(Compound)i(=)e(...)6974 57783 y
Fb(Exp)-31 b(ression')372 b Fq(consists)d(of)h Fb(Ident)p
Fq(,)f Fb(Numb)31 b(er)370 b Fq(and)f Fb(Comp)31 b(ound)p
Fq(.)6974 60219 y Fc(De\014nition)425 b(2)554 b Fk(A)398
b(c)-57 b(onstruction)397 b(obje)-57 b(ct)399 b(is)e
Fq(legal)i Fk(with)e(r)-57 b(esp)g(e)g(ct)398 b(to)f(a)g(c)-57
b(onstruction)398 b(pr)-57 b(o-)6974 61547 y(duction)440
b(if)g(every)h(instanc)-57 b(e)440 b(variable)g(c)-57
b(ontains)441 b(an)e(obje)-57 b(ct)441 b(which)e(is)h(an)g(instanc)-57
b(e)440 b(of)g(a)6974 62875 y(class)411 b(asso)-57 b(ciate)g(d)413
b(with)e(the)i(instanc)-57 b(e)413 b(variable)g(class)e(given)j(in)f
(the)f(pr)-57 b(o)g(duction.)560 b(Ther)-57 b(e)6974
64204 y(is)396 b(an)g(exc)-57 b(eption)397 b(for)f(optional)f(instanc)
-57 b(e)398 b(variables:)509 b(their)396 b(value)g(may)h(b)-57
b(e)397 b(nil.)p eop
%%Page: 17 17
17 16 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(17)8634 8192 y Fk(A)491 b(r)-57
b(ep)g(etition)493 b(obje)-57 b(ct)493 b(is)e Fq(legal)j
Fk(with)d(r)-57 b(esp)g(e)g(ct)492 b(to)f(a)g(r)-57 b(ep)g(etition)493
b(pr)-57 b(o)g(duction)492 b(if)g(every)6974 9520 y(element)442
b(of)g(the)f(obje)-57 b(ct)442 b(is)f(an)h(instanc)-57
b(e)442 b(of)g(a)f(class)f(asso)-57 b(ciate)g(d)441 b(with)g(the)g
(class)g(on)g(the)6974 10848 y(right-hand-side)502 b(of)h(the)f(r)-57
b(ep)g(etition)504 b(pr)-57 b(o)g(duction.)830 b(If)503
b(the)f(r)-57 b(ep)g(etition)504 b(pr)-57 b(o)g(duction)503
b(do)-57 b(es)6974 12177 y(not)377 b(al)57 b(low)376
b(an)h(empty)h(list,)j(the)c(r)-57 b(ep)g(etition)379
b(obje)-57 b(ct)378 b(must)f(c)-57 b(ontain)378 b(at)f(le)-57
b(ast)377 b(one)h(element.)8634 13505 y(A)559 b(terminal)h(obje)-57
b(ct)560 b(is)f Fq(legal)i Fk(if)f(it)g(c)-57 b(ontains)560
b(a)f(value)g(which)g(satis\014es)g(the)f(rules)6974
14833 y(de\014ne)-57 b(d)397 b(in)g(the)f(sc)-57 b(anner)396
b(gener)-57 b(ator)397 b(sp)-57 b(e)g(ci\014c)g(ation)398
b(\(i.e.)510 b(its)396 b(lexic)-57 b(al)396 b(de\014nition\).)8634
17182 y Fq(F)-92 b(or)369 b(de\014ning)h(the)f(subt)-31
b(yp)31 b(e)369 b(concept)h(w)-31 b(e)370 b(need)f(the)g(follo)-31
b(wing)373 b(de\014nitions:)6974 19328 y Fc(De\014nition)425
b(3)554 b Fk(A)445 b(class)e(T)h(dir)-57 b(e)g(ctly)446
b(inherits)f(fr)-57 b(om)445 b(class)f(S)g(if)i(the)e(de\014nition)i
(of)e(T)h(is)6974 20656 y(of)396 b(one)h(of)f(the)g(fol)57
b(lowing)395 b(forms:)8717 22801 y Fa(T)582 b(=)1162
b(...)582 b(*inherit*)g(S)f(...)8717 24129 y(S)h(:)f(T)g(|)g(...)h
(*common*)g(...)6974 26478 y Fc(De\014nition)425 b(4)554
b Fk(A)376 b(class)f(T)h(inherits)g(fr)-57 b(om)377 b(class)e(S)h(if)h
(ther)-57 b(e)376 b(is)f(a)h(se)-57 b(quenc)g(e)378 b(of)e(interme-)
6974 27807 y(diate)396 b(classes)f(which)h(form)g(dir)-57
b(e)g(ct)397 b(inheritanc)-57 b(e)398 b(links)e(b)-57
b(etwe)g(en)398 b(class)d(T)h(and)g(S.)8634 30156 y Fq(F)-92
b(or)520 b(example,)561 b(the)521 b(follo)-31 b(wing)524
b(pro)31 b(duction)522 b(implies)g(that)g(Orange)f(inherits)g(from)6974
31484 y(class)369 b(EatableOb)61 b(ject.)496 b(F)-92
b(ruit)369 b(is)g(an)g(in)-31 b(termediate)372 b(class.)6974
33834 y Fa(Fruit)582 b(:)f(Orange)h(|)f(Apple)8136 35162
y(*common*)h(*inherit*)h(EatableObject.)6974 37511 y
Fc(De\014nition)425 b(5)554 b Fk(The)483 b(class)f(T)h(is)h(c)-57
b(omp)g(atible)484 b(with)e(class)g(S)i(if)g(the)e(classes)g(asso)-57
b(ciate)g(d)6974 38840 y(with)395 b(the)h(class)f(T)h(ar)-57
b(e)397 b(a)e(subset)h(of)g(the)g(classes)f(asso)-57
b(ciate)g(d)396 b(with)f(class)h(S.)6974 41189 y Fc(De\014nition)425
b(6)554 b Fk(A)396 b(class)f(T)h(is)h(a)e(subtyp)-57
b(e)397 b(\(or)e(sub)-57 b(class\))395 b(of)i(class)e(S)h(if)8634
43334 y Fp(\017)554 b Fk(T)396 b(inherits)h(fr)-57 b(om)397
b(S)f(or)8634 45513 y Fp(\017)554 b Fk(T)396 b(is)h(c)-57
b(omp)g(atible)397 b(with)e(S.)6974 47658 y(Every)h(class)g(is)g(a)g
(subtyp)-57 b(e)396 b(\(or)f(sub)-57 b(class\))395 b(of)i(itself.)6974
50008 y Fq(W)-92 b(e)368 b(can)i(summarize)g(the)f(subt)-31
b(yp)31 b(e)369 b(de\014nition)i(b)-31 b(y:)p 11402 51399
4720 45 v 11402 53047 45 1649 v 11778 52499 a(Subt)g(yp)31
b(e)p 16077 53047 V 11402 53091 4720 45 v 746 w(=)p 17720
51399 6199 45 v 17720 52832 45 1433 v 745 w(Inheritance)p
23874 52832 V 17720 52876 6199 45 v 746 w(or)p 25643
51399 7457 45 v 25643 53047 45 1649 v 746 w(Compatibilit)-31
b(y)p 33055 53047 V 25643 53091 7457 45 v 8634 54991
a(T)-92 b(o)370 b(illustrate)h(the)e(subt)-31 b(yp)31
b(e)370 b(de\014nition,)h(consider)e(the)h(follo)-31
b(wing)372 b(example:)6974 57341 y Fa(AutoDealer)582
b(=)g(<cars>)g(List\(Car\).)6974 58669 y(Car)f(:)8136
59997 y(GasolineCar)i(*override*)g(<fuel>)f(Gasoline)g(|)8136
61326 y(CombustionCar)h(*override*)g(<fuel>)f(GasolineOrCoal)9298
62654 y(*common*)h("speed")f(<speed>)g(Number)g(*inherit*)h(Machine.)
6974 63982 y(List\(S\))f(~)f({S}.)6974 65311 y(GasolineCar)i(=)e
("gasolinecar".)p eop
%%Page: 18 18
18 17 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(18)6974 8192 y Fa(CombustionCar)583
b(=)e("combustioncar".)6974 9520 y(Machine)h(=)8136 10848
y("age")g(<age>)g(Number)g("fuel")g(<fuel>)g(FuelType.)6974
12177 y(FuelType)g(:)f(Coal)h(|)g(Gasoline)g(|)f(Electricity.)6974
13505 y(GasolineOrCoal)i(:)e(Gasoline)i(|)e(Coal.)6974
16162 y(Gasoline)h(=)f("gas".)6974 17490 y(Coal)h(=)f("coal".)6974
18818 y(Electricity)i(=)e("electricity".)8634 20962 y
Fq(W)-92 b(e)398 b(de\014ne)h(a)g(class)f Fb(Ca)-31 b(r)399
b Fq(whic)-31 b(h)400 b(inherits)f(from)h(class)e Fb(Machine)p
Fq(.)581 b(The)399 b Fb(Ca)-31 b(r)399 b Fq(class)g(has)6974
22291 y(t)-31 b(w)g(o)432 b(alternativ)-31 b(es:)618
b Fb(GasolineCa)-31 b(r)433 b Fq(and)e Fb(CombustionCa)-31
b(r)p Fq(.)679 b(Both)432 b(o)-31 b(v)g(erride)431 b(the)g(inherited)
6974 23619 y(instance)530 b(v)-61 b(ariable)530 b(t)-31
b(yp)31 b(e)530 b(for)f Fb(fuel)p Fq(.)974 b(A)529 b(mac)-31
b(hine)531 b(can)e(ha)-31 b(v)g(e)530 b(an)-31 b(y)530
b(t)-31 b(yp)31 b(e)530 b(of)g(\\fuel",)571 b(b)31 b(e)6974
24947 y(it)549 b(gas,)594 b(coal)549 b(or)f(electricit)-31
b(y)-92 b(.)1032 b(A)548 b(com)-31 b(bustion)550 b(car)f(can)f(use)g
(only)h(gasoline)h(or)e(coal.)6974 26276 y(Since)438
b(w)-31 b(e)438 b(w)-31 b(an)g(t)439 b(to)f(consider)g(a)f(com)-31
b(bustion)440 b(car)d(as)h(a)g(sp)31 b(ecial)438 b(kind)g(of)g(car,)455
b(w)-31 b(e)438 b(ha)-31 b(v)g(e)6974 27604 y(in)g(tro)31
b(duced)310 b(compatibilit)-31 b(y)314 b(in)-31 b(to)310
b(our)f(de\014nition)i(of)f(subt)-31 b(yp)31 b(e.)473
b(There)309 b(are)g(other)g(reasons)6974 28932 y(to)346
b(ha)-31 b(v)g(e)346 b(b)31 b(oth)346 b(compatibilit)-31
b(y)350 b(and)345 b(inheritance)h(in)g(the)f(subt)-31
b(yp)31 b(e)346 b(de\014nition:)482 b(reduction)6974
30261 y(of)370 b(inheritance)g(links,)g(a)-31 b(v)g(oidance)372
b(of)e(m)-31 b(ultiple)371 b(inheritance,)g(and)e(e\016ciency)-92
b(.)8634 31589 y(The)404 b(main)g(idea)g(b)31 b(ehind)403
b(the)h(subt)-31 b(yp)31 b(e)403 b(de\014nition)i(is)e(that)i(if)e(a)h
(t)-31 b(yp)31 b(e)404 b(kno)-31 b(ws)404 b(ab)31 b(out)6974
32917 y(a)381 b(message)g(then)f(all)i(ob)61 b(jects)382
b(b)31 b(elonging)382 b(to)g(subt)-31 b(yp)31 b(es)380
b(of)h(that)h(t)-31 b(yp)31 b(e)381 b(also)g(kno)-31
b(w)382 b(ab)31 b(out)6974 34246 y(that)490 b(message.)851
b(W)-92 b(e)488 b(w)-31 b(an)g(t)490 b(to)g(pro)-31 b(v)g(e)489
b(that)h(an)-31 b(y)489 b(com)-31 b(bination)492 b(of)d(compatibilit)
-31 b(y)494 b(and)6974 35574 y(inheritance)410 b(will)i(supp)31
b(ort)409 b(this)h(condition.)615 b(The)410 b(com)-31
b(bination)413 b(of)d(compatibilit)-31 b(y)414 b(and)6974
36903 y(inheritance)439 b(tends)f(to)h(constrain)g(the)f(form)g(of)h
(class)f(dictionaries.)701 b(This)438 b(is)g(partially)6974
38231 y(due)412 b(to)i(the)f(fact)g(that)h(w)-31 b(e)414
b(restrict)e(inherited)i(classes)e(to)h(those)h(de\014ned)e(b)-31
b(y)413 b(construc-)6974 39559 y(tion)420 b(pro)31 b(ductions.)642
b(W)-92 b(e)418 b(follo)-31 b(w)422 b(sev)-31 b(eral)419
b(de\014nitions)h(b)-31 b(y)419 b(a)g(case)g(analysis)h(on)f(the)g
(legal)6974 40888 y(structure)269 b(of)h(class)f(dictionaries)j(for)e
(eac)-31 b(h)270 b(of)g(the)f(four)h(compatibilit)-31
b(y/inheritance)276 b(com-)6974 42216 y(binations.)767
b(W)-92 b(e)460 b(will)i(de\014ne)e(sev)-31 b(eral)461
b(seman)-31 b(tic)461 b(rules)f(to)h(deal)g(with)h(class)e(dictionary)
6974 43544 y(structures)368 b(whic)-31 b(h)370 b(violate)i(our)d
(de\014nition)i(of)e(subt)-31 b(yp)31 b(e.)8634 44873
y(T)-92 b(o)355 b(supp)31 b(ort)355 b(our)f(subt)-31
b(yp)31 b(e)355 b(de\014nition)h(w)-31 b(e)355 b(need)f(need)h(to)g(in)
-31 b(tro)31 b(duce)355 b(the)g(concept)g(of)6974 46201
y(a)377 b(signature.)515 b(Informally)-92 b(,)380 b(signature\(S\))f
(for)d(a)h(class)f(S)h(consists)f(of)h(all)h(messages)e(m)h(to)6974
47529 y(whic)-31 b(h)367 b(all)g(classes)e(in)h(S')g(can)g(react)g(to)g
(b)-31 b(y)366 b(ha)-31 b(ving)368 b(a)e(metho)31 b(d)366
b(attac)-31 b(hed)368 b(to)f(them)f(or)g(b)-31 b(y)6974
48858 y(inheritance.)8634 50186 y(T)-92 b(o)342 b(de\014ne)f(the)h
(concept)g(of)f(signature)i(more)e(formally)-92 b(,)350
b(w)-31 b(e)341 b(use)g(the)h(follo)-31 b(wing)345 b(nota-)6974
51514 y(tion:)6974 53658 y Fc(De\014nition)425 b(7)2215
b Fp(\017)554 b Fk(A)474 b(class)f Fh(S)537 b Fk(is)475
b Fq(resp)31 b(onsiv)-31 b(e)474 b Fk(to)f(message)h(m)g(if)h(m)g(is)f
(attache)-57 b(d)473 b(to)9741 54987 y(S)434 b(or)g(ther)-57
b(e)434 b(is)f(a)h(class)f(T)h(such)f(that)g(m)h(is)g(attache)-57
b(d)433 b(to)h(T)f(and)h(ther)-57 b(e)434 b(ar)-57 b(e)434
b(dir)-57 b(e)g(ct)9741 56315 y(inheritanc)g(e)398 b(links)f(fr)-57
b(om)396 b(S)h(to)e(T.)8634 58413 y Fp(\017)554 b Fk(A)396
b(class)f Fh(S)460 b Fk(knows)395 b(message)h(m)h(if)g(e)-57
b(ach)396 b(class)f(in)i(S')g(is)f(r)-57 b(esp)g(onsive)397
b(to)e(m.)8634 60510 y Fp(\017)554 b Fh(S)64 b(ig)40
b(natur)31 b(e)p Fq(\()p Fh(S)64 b Fq(\))309 b(=)e Fp(f)p
Fh(m)p Fp(j)p Fh(S)460 b Fk(knows)396 b(m)g Fp(g)p Fk(.)8634
62654 y Fq(The)382 b(distinction)i(b)31 b(et)-31 b(w)g(een)383
b(resp)31 b(onsiv)-31 b(eness)381 b(and)h(kno)-31 b(wledge)384
b(is)e(useful;)389 b(kno)-31 b(wledge)6974 63982 y(in)g(v)g(olv)g(es)
517 b(the)f(compatibilit)-31 b(y)519 b(relationships)e(while)g(resp)31
b(onsiv)-31 b(eness)514 b(relies)h(on)h(inheri-)6974
65311 y(tance.)p eop
%%Page: 19 19
19 18 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(19)8634 8192 y(W)-92 b(e)479
b(giv)-31 b(e)481 b(no)-31 b(w)481 b(the)f(rules)f(for)h(computing)h
(the)f(signature)h(of)f(a)g(class.)824 b(W)-92 b(e)479
b(de\014ne)6974 9520 y Fh(attached)p Fq(\()p Fh(C)79
b Fq(\))536 b(to)f(b)31 b(e)534 b(the)h(set)g(of)g(metho)31
b(ds)535 b(attac)-31 b(hed)537 b(to)e Fh(C)79 b Fq(.)989
b(W)-92 b(e)534 b(assume)h(that)h(the)6974 10848 y(subt)-31
b(yp)31 b(e)476 b(graph)f(do)31 b(es)476 b(not)g(con)-31
b(tain)478 b(cycles)d(and)h(w)-31 b(e)476 b(apply)h(the)f(follo)-31
b(wing)479 b(rules)c(to)h(a)6974 12177 y(top)31 b(ologically)422
b(sorted)c(order)g(of)g(the)g(classes.)639 b(W)-92 b(e)417
b(assume)h(that)h(the)f(signature)h(of)g(the)6974 13505
y(abstract)370 b(classes)f(univ)-31 b(ersal,)370 b(construction,)h(rep)
31 b(etition,)371 b(and)f(terminal)h(are)e(giv)-31 b(en.)8634
15719 y Fp(\017)554 b Fq(CONSTR)-31 b(UCTION:)9741 18597
y Fa(S)582 b(=)f(<name>)h(A)f(...)9741 19925 y(signature\(S\))i(=)10904
21254 y({name,)f(set-name,)g(...})g(union)12066 22582
y(signature\(construction\))i(union)13228 23910 y(attached\(S\).)9741
26567 y(S)e(=)f(*inherit*)h(A.)9741 27895 y(signature\(S\))h(=)10904
29224 y(signature\(A\))f(union)12066 30552 y(signature\(construction\))
i(union)13228 31880 y(attached\(S\).)9741 34537 y(S)e(=)f(<name1>)h(A)f
(...)h(*inherit*)g(B)g(*override*)g(<name2>)h(C)e(...)9741
35866 y(signature\(S\))i(=)10904 37194 y({name1,)f(set-name1,)g(name2,)
g(set-name2,)h(...})f(union)12066 38522 y(signature\(B\))h(union)13228
39851 y(signature\(construction\))i(union)14390 41179
y(attached\(S\).)8634 45385 y Fp(\017)554 b Fq(REPETITION:)9741
48263 y Fa(S)582 b(~)f({R}.)9741 49592 y(signature\(S\))i(=)e
(signature\(repetition\))k(union)10904 50920 y(attached\(S\).)8634
53798 y Fp(\017)554 b Fq(AL)-92 b(TERNA)g(TION:)11485
56676 y Fa(S)581 b(:)g(A)h(|)f(B.)9741 59554 y(signature\(S\))i(=)e
(signature\(A\))i(intersection)g(signature\(B\))8634
62433 y Fp(\017)554 b Fq(AL)-92 b(TERNA)g(TION)370 b(with)h(implied)g
(inheritance:)p eop
%%Page: 20 20
20 19 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(20)9741 8192 y Fa(S)582 b(:)f(A)g(|)g(B)h
(*common*)g(X)f(Y.)9741 9520 y(A)h(=)f(<b>)g(Ident.)9741
10848 y(B)h(=)f(<c>)g(Ident.)9741 13505 y(signature\(S\))i(=)10904
14833 y(\(signature\(A\))g(intersection)g(signature\(B\)\))g(union)
12066 16162 y({X,)e(Y,)h(set-X,)g(set-Y})g(union)13228
17490 y(attached\(S\).)9741 20147 y(signature\(A\))h(=)10904
21475 y({b,)e(set-b})h(union)g(signature\(S\))h(union)12066
22803 y(signature\(construction\))h(union)13228 24132
y(attached\(S\).)9741 25460 y(signature\(B\))f(=)10904
26788 y({c,)e(set-c})h(union)g(signature\(S\))h(union)12066
28117 y(signature\(construction\))h(union)13228 29445
y(attached\(S\).)8634 31844 y Fq(W)-92 b(e)346 b(are)g(no)-31
b(w)347 b(ready)g(to)g(pro)-31 b(v)g(e)347 b(an)g(imp)31
b(ortan)-31 b(t)348 b(prop)31 b(ert)-31 b(y)347 b(of)f(the)h(subt)-31
b(yp)31 b(e)347 b(predicate.)6974 33879 y Fc(Theorem)425
b(1)554 b Fq(Name-Signature-Theorem:)459 b Fk(If)286
b Fq(T)g Fk(is)g(a)g(subtyp)-57 b(e)286 b(of)h Fq(S)e
Fk(then)h Fq(signature\(T\))6974 35207 y Fk(is)396 b(a)g(sup)-57
b(erset)395 b(of)i Fq(signature\(S\))p Fk(.)8634 37243
y Fq(T)-92 b(o)516 b(pro)-31 b(v)g(e)515 b(this)g(theorem)g(w)-31
b(e)516 b(need)e(to)i(de\014ne)e(seman)-31 b(tic)516
b(rules)e(whic)-31 b(h)516 b(are)f(easily)6974 38571
y(c)-31 b(hec)g(k)g(ed)305 b(at)g(compile-time.)474 b(W)-92
b(e)304 b(state)h(those)g(seman)-31 b(tic)306 b(rules)d(in)i(the)g(pro)
31 b(of)304 b(at)h(the)g(place)6974 39900 y(where)385
b(they)g(are)g(needed)g(to)h(highligh)-31 b(t)387 b(the)f(exact)g(dep)
31 b(endency)384 b(of)i(of)f(the)h(theorem)g(on)6974
41228 y(the)369 b(seman)-31 b(tic)371 b(rules.)8634 42556
y(The)419 b(pro)31 b(of)419 b(is)f(divided)i(in)-31 b(to)420
b(the)f(pro)31 b(of)419 b(of)g(four)g(claims.)642 b(They)419
b(state)g(that)h(kno)-31 b(wl-)6974 43885 y(edge)299
b(of)h(messages)g(and)f(resp)31 b(onsiv)-31 b(eness)299
b(to)h(messages)f(are)h(transmitted)h(prop)31 b(erly)299
b(along)6974 45213 y(inheritance)370 b(and)g(compatibilit)-31
b(y)373 b(links.)6974 47249 y Fc(Claim)423 b(1)554 b
Fk(If)434 b(B)f(inherits)h(fr)-57 b(om)434 b(A)f(and)g(A)g(is)g(r)-57
b(esp)g(onsive)434 b(to)f(m,)443 b(then)433 b(B)h(is)f(r)-57
b(esp)g(onsive)6974 48577 y(to)395 b(m.)8634 50613 y
Fq(This)328 b(follo)-31 b(ws)330 b(immediately)h(from)e(the)e
(de\014nition)j(of)e(resp)31 b(onsiv)-31 b(eness)327
b(and)h(the)f(tran-)6974 51941 y(sitivit)-31 b(y)372
b(of)d(inheritance.)6974 53977 y Fc(Claim)423 b(2)554
b Fk(If)397 b(B)f(inherits)g(fr)-57 b(om)397 b(A)f(and)g(A)g(knows)f(m)
i(then)f(B)g(knows)f(m.)8634 56012 y Fq(W)-92 b(e)434
b(ha)-31 b(v)g(e)435 b(only)h(to)f(discuss)e(the)i(case)f(where)g(A)g
(kno)-31 b(ws)436 b(m,)451 b(but)435 b(is)f(not)h(resp)31
b(onsiv)-31 b(e)6974 57341 y(to)452 b(m.)740 b(This)451
b(implies)i(that)g(A)e(is)g(de\014ned)g(b)-31 b(y)452
b(an)g(alternation)i(pro)31 b(duction)452 b(and)g(ev)-31
b(ery)6974 58669 y(class)381 b(in)h(A')f(is)g(resp)31
b(onsiv)-31 b(e)381 b(to)h(m.)529 b(If)381 b(B)g(is)g(in)h(A')g(then)f
(B)g(is)g(not)h(an)g(alternation)h(and)f(is)6974 59997
y(resp)31 b(onsiv)-31 b(e)416 b(to)g(m)h(and)f(therefore)g(kno)-31
b(ws)417 b(ab)31 b(out)417 b(m.)633 b(If)416 b(B)g(is)g(not)g(in)h(A',)
g(w)-31 b(e)416 b(ha)-31 b(v)g(e)417 b(t)-31 b(w)g(o)6974
61326 y(cases:)541 b(In)394 b(the)g(\014rst)f(case,)400
b(B)394 b(inherits)g(from)g(A)g(using)g(a)g(*inherit*)i(link.)567
b(If)394 b(w)-31 b(e)394 b(request)6974 62654 y(that)326
b(A)f(b)31 b(e)324 b(a)h(construction)h(class,)334 b(w)-31
b(e)325 b(kno)-31 b(w)326 b(that)g(A)f(m)-31 b(ust)325
b(b)31 b(e)324 b(resp)31 b(onsiv)-31 b(e)325 b(to)g(m)g(\(whic)-31
b(h)6974 63982 y(implies)381 b(that)f(B)f(is)h(resp)31
b(onsiv)-31 b(e)379 b(to)h(m)g(and)f(therefore)h(B)f(kno)-31
b(ws)380 b(m.\))524 b(Therefore)380 b(w)-31 b(e)379 b(use)6974
65311 y(the)369 b(follo)-31 b(wing)373 b(seman)-31 b(tic)371
b(rule.)p eop
%%Page: 21 21
21 20 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(21)6974 8192 y Fc(Seman)-35
b(tic)424 b(rule)h(1)554 b Fk(Inheritanc)-57 b(e)382
b(with)g(*inherit*)g(is)f(only)i(al)57 b(lowe)-57 b(d)380
b(fr)-57 b(om)382 b(c)-57 b(onstruction)6974 9520 y(classes.)8634
11955 y Fq(In)292 b(the)g(second)f(case,)308 b(B)292
b(is)g(a)g(sub)31 b(class)291 b(of)h(A)g(through)h(alternation)h(pro)31
b(ductions)293 b(with)6974 13284 y(implied)385 b(inheritance)f(and)f(B)
g(is)g(an)g(alternation)j(class)d(itself.)535 b(The)383
b(claim)i(follo)-31 b(ws)386 b(with)6974 14612 y(the)369
b(follo)-31 b(wing)373 b(seman)-31 b(tic)371 b(rule:)6974
16826 y Fc(Seman)-35 b(tic)424 b(rule)h(2)554 b Fk(In)451
b(an)g(alternation)g(class)f(with)h(implie)-57 b(d)452
b(inheritanc)-57 b(e)453 b(\(i.e.)675 b(using)6974 18154
y Fb(*common*)p Fk(\))448 b(the)e(alternatives)g(which)g(ar)-57
b(e)447 b(de\014ne)-57 b(d)447 b(by)g(alternation)f(pr)-57
b(o)g(ductions)446 b(must)6974 19482 y(also)395 b(use)h(implie)-57
b(d)397 b(inheritanc)-57 b(e.)6974 21918 y Fc(Claim)423
b(3)554 b Fk(If)371 b(B)g(is)g(c)-57 b(omp)g(atible)372
b(with)e(A)g(and)h(A)f(is)h(r)-57 b(esp)g(onsive)372
b(to)e(m,)376 b(then)371 b(B)g(is)g(r)-57 b(esp)g(on-)6974
23246 y(sive)396 b(to)g(m.)8634 25681 y Fq(A)466 b(m)-31
b(ust)466 b(b)31 b(e)464 b(de\014ned)h(b)-31 b(y)466
b(an)g(alternation)i(pro)31 b(duction.)782 b(If)465 b(A)g(is)g(resp)31
b(onsiv)-31 b(e)465 b(to)h(m)6974 27010 y(then)442 b(A)g(has)g(either)h
(m)f(attac)-31 b(hed)444 b(or)e(inherits)g(it.)713 b(If)441
b(A)h(has)g(m)h(attac)-31 b(hed,)463 b(w)-31 b(e)442
b(require)6974 28338 y(that)341 b(the)f(alternation)i(pro)31
b(duction)341 b(has)e(implied)j(inheritance)e(with)h(the)f(follo)-31
b(wing)343 b(rule:)6974 30773 y Fc(Seman)-35 b(tic)424
b(rule)h(3)554 b Fk(If)f(an)g(alternation)h(class)e(has)g(a)h(metho)-57
b(d)553 b(attache)-57 b(d,)593 b(it)553 b(must)g(b)-57
b(e)6974 32102 y(de\014ne)g(d)397 b(with)f(implie)-57
b(d)397 b(inheritanc)-57 b(e)398 b(\(i.e.)510 b(with)396
b(*c)-57 b(ommon*\).)8634 34537 y Fq(As)370 b(a)f(side-e\013ect,)i
(this)f(rule)f(implies)i(that)g(if)f(A)f(is)h(resp)31
b(onsiv)-31 b(e)369 b(to)i(m)f(then)f(A)h(kno)-31 b(ws)6974
35866 y(m.)534 b(Note)384 b(that)g(an)f(alternation)j(class)d(B)g(can)g
(only)h(inherit)f(from)h(another)g(class)f(if)g(B)g(is)6974
37194 y(an)369 b(alternation)j(class)d(with)i(implied)g(inheritance.)
6974 39629 y Fc(Claim)423 b(4)554 b Fk(If)397 b(B)f(is)g(c)-57
b(omp)g(atible)397 b(with)f(A)g(and)g(A)f(knows)h(m)g(then)g(B)h(knows)
e(m.)8634 42064 y Fq(A)294 b(m)-31 b(ust)295 b(b)31 b(e)293
b(de\014ned)h(b)-31 b(y)294 b(an)g(alternation)j(pro)31
b(duction.)468 b(W)-92 b(e)293 b(ha)-31 b(v)g(e)295 b(to)g(discuss)e
(the)h(case)6974 43393 y(where)326 b(A)h(kno)-31 b(ws)327
b(m)g(but)g(is)g(not)g(resp)31 b(onsiv)-31 b(e)327 b(to)g(m.)479
b(All)328 b(classes)e(in)h(A')g(are)g(resp)31 b(onsiv)-31
b(e)326 b(to)6974 44721 y(m.)536 b(If)383 b(B)g(is)g(in)h(A')g(then)g
(B)f(is)g(resp)31 b(onsiv)-31 b(e)384 b(to)g(m)g(and)f(therefore)h(kno)
-31 b(ws)384 b(ab)31 b(out)384 b(m.)536 b(If)383 b(B')6974
46050 y(is)369 b(a)g(subset)g(of)h(A',)g(the)f(claim)i(holds)f(b)-31
b(y)369 b(the)h(de\014nition)h(of)e(kno)-31 b(wledge)372
b(of)d(a)h(message.)8634 47378 y(These)319 b(four)g(claims)h(allo)-31
b(w)322 b(us)c(to)i(pro)-31 b(v)g(e)319 b(the)g(theorem)h(as)f(follo)
-31 b(ws:)470 b(If)318 b(T)i(is)e(a)i(subt)-31 b(yp)31
b(e)6974 48706 y(of)465 b(S)f(then)g(there)g(m)-31 b(ust)465
b(b)31 b(e)464 b(a)g(sequence)g(of)h(compatibilit)-31
b(y)469 b(and/or)c(inheritance)g(links)6974 50035 y(b)31
b(et)-31 b(w)g(een)301 b(T)f(and)h(S.)g(The)f(claims)i(guaran)-31
b(tee)301 b(that)h(the)e(kno)-31 b(wledge)303 b(relation)f(is)e
(transitiv)-31 b(e)6974 51363 y(along)371 b(those)e(links)h(whic)-31
b(h)370 b(completes)h(the)e(pro)31 b(of)370 b(of)f(the)h
(Name-Signature-Theorem.)8634 52691 y(The)552 b(subt)-31
b(yp)31 b(e)552 b(concept)g(is)g(used)f(b)31 b(oth)552
b(for)f(c)-31 b(hec)g(king)554 b(whether)d(the)h(t)-31
b(yp)31 b(e)552 b(of)h(the)6974 54020 y(\014rst)448 b(actual)i
(parameter)f(of)g(a)g(metho)31 b(d)449 b(is)f(a)h(subt)-31
b(yp)31 b(e)449 b(of)f(the)h(\014rst)f(formal)i(parameter)6974
55348 y(t)-31 b(yp)31 b(e)360 b(and)f(for)h(c)-31 b(hec)g(king)360
b(the)g(sp)31 b(ecialization)362 b(hierarc)-31 b(h)g(y)360
b(prop)31 b(ert)-31 b(y)359 b(for)h Fp(\003)p Fq(o)-31
b(v)g(erride)p Fp(\003)p Fq(.)491 b(The)6974 56676 y(ab)31
b(o)-31 b(v)g(e)252 b(pro)31 b(of)250 b(guaran)-31 b(tees)252
b(the)f(desirable)g(prop)31 b(ert)-31 b(y)250 b(of)h(name)g
(compatibilit)-31 b(y)255 b(for)c(Demeter)6974 58005
y(subt)-31 b(yp)31 b(es.)598 b(W)-92 b(e)404 b(ha)-31
b(v)g(e)405 b(pro)-31 b(v)g(en)405 b(stronger)g(forms)f(of)h
(compatibilit)-31 b(y)-92 b(,)418 b(but)405 b(a)g(discussion)f(of)6974
59333 y(this)285 b(topic)h(is)f(b)31 b(ey)-31 b(ond)285
b(the)g(scop)31 b(e)285 b(of)g(this)h(pap)31 b(er.)464
b(W)-92 b(e)284 b(no)-31 b(w)286 b(pro)-31 b(v)g(e)285
b(the)g(transitivit)-31 b(y)288 b(of)e(the)6974 60661
y(subt)-31 b(yp)31 b(e)272 b(relation)i(b)-31 b(y)272
b(examining)j(four)d(cases.)459 b(This)273 b(pro)31 b(of)272
b(is)g(needed)g(since)g(our)g(subt)-31 b(yp)31 b(e)6974
61990 y(de\014nition)408 b(con)-31 b(tains)409 b(a)e(disjunction)h
(\(or\).)607 b(The)407 b(subt)-31 b(yp)31 b(e)407 b(transitivit)-31
b(y)410 b(theorem)d(is)g(not)6974 63318 y(essen)-31 b(tial)428
b(for)e(ob)61 b(ject-orien)-31 b(ted)429 b(programming.)668
b(It)426 b(is)h(the)f(Name-Signature-Theorem)6974 64646
y(that)370 b(is)f(imp)31 b(ortan)-31 b(t.)p eop
%%Page: 22 22
22 21 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(22)6974 8192 y Fc(Theorem)425
b(2)554 b Fq(Subt)-31 b(yp)31 b(e-T)-92 b(ransitivit)-31
b(y-Theorem:)502 b Fk(The)372 b(subtyp)-57 b(e)372 b(r)-57
b(elation)371 b(is)h(tr)-57 b(ansitive.)8634 10627 y
Fq(Pro)31 b(of)370 b(b)-31 b(y)370 b(case)f(analysis.)8634
13062 y Fp(\017)554 b Fq(If)404 b(a)g(class)g(C)g(inherits)g(from)g(a)g
(class)g(B)g(and)g(the)g(class)g(B)f(inherits)h(from)h(A)f(then)9741
14390 y(the)370 b(class)f(C)g(inherits)h(from)g(the)f(class)g(A.)10762
16826 y(1.)555 b(T)-92 b(rue)368 b(b)-31 b(y)370 b(de\014nition)h(of)e
(inheritance.)8634 19261 y Fp(\017)554 b Fq(If)466 b(a)h(class)f(C)h
(is)f(compatible)j(with)f(a)f(class)f(B)g(and)h(the)f(class)h(B)f(is)g
(compatible)9741 20589 y(with)371 b(a)e(class)g(A)h(then)f(the)g(class)
h(C)f(is)g(compatible)j(to)e(the)f(class)h(A.)10762 23025
y(1.)555 b(C')370 b Fp(\022)e Fq(B')1477 b(b)-31 b(y)369
b(def.)493 b(of)370 b(compatibilit)-31 b(y)12177 24575
y(B')369 b Fp(\022)g Fq(A')1477 b(b)-31 b(y)369 b(def.)493
b(of)370 b(compatibilit)-31 b(y)12177 26124 y(C')370
b Fp(\022)e Fq(A')1477 b(b)-31 b(y)370 b(transitivit)-31
b(y)372 b(of)e(subset)12177 27674 y(C)f(is)g(compatible)j(to)e(A)1476
b(b)-31 b(y)370 b(de\014nition)g(of)g(compatibilit)-31
b(y)9741 30441 y(F)-92 b(or)318 b(the)g(last)i(t)-31
b(w)g(o)320 b(cases)d(w)-31 b(e)319 b(presen)-31 b(t)318
b(class)g(dictionary)j(templates)f(whic)-31 b(h)319 b(demon-)9741
31770 y(strate)559 b(the)g(relationship)i(b)31 b(et)-31
b(w)g(een)559 b(class)g(dictionary)i(structure)d(and)h(subt)-31
b(yp)31 b(e)9741 33098 y(links.)8634 35312 y Fp(\017)554
b Fq(If)383 b(a)h(class)f(C)h(inherits)f(from)h(a)g(class)f(B)g(and)h
(a)f(class)h(B)f(is)g(compatible)j(to)e(a)g(class)9741
36640 y(A)369 b(then:)10762 39076 y(1.)555 b(This)499
b(third)g(case)g(com)-31 b(bines)501 b(inheritance)f(with)g
(compatibilit)-31 b(y)504 b(suc)-31 b(h)499 b(that)12177
40404 y(there)329 b(exists)g(a)h(class)f(C)g(whic)-31
b(h)330 b(inherits)g(from)g(a)f(class)h(B)f(and)g(the)h(class)f(B)g(is)
12177 41732 y(compatible)397 b(with)e(a)g(class)f(A.)h(There)f(are)h
(three)f(p)31 b(ossible)394 b(class)h(dictionary)12177
43061 y(templates)302 b(whic)-31 b(h)301 b(will)h(pro)31
b(duce)300 b(this)h(t)-31 b(yp)31 b(e)301 b(of)g(subt)-31
b(yp)31 b(e)301 b(link.)470 b(In)300 b(the)h(second)12177
44389 y(w)-31 b(e)377 b(use)g(set)h(notation)i(to)e(restrict)f(the)h
(classes)f(whic)-31 b(h)378 b(app)31 b(ear)377 b(on)h(the)g(righ)-31
b(t)12177 45717 y(hand)428 b(side)g(of)h(B)f(to)h(b)31
b(e)428 b(a)g(subset)g(of)h(the)g(classes)e(app)31 b(earing)430
b(on)e(the)h(righ)-31 b(t)12177 47046 y(hand)369 b(side)g(of)h(A.)f
(This)h(is)f(to)h(ensure)e(the)i(compatibilit)-31 b(y)373
b(relation.)19150 50367 y Fa(inheritance)6976 b(compatibility)14501
51695 y(C)581 b(<----------------------)k(B)c(<----------------------)k
(A)13920 54352 y(case)d(3a:)15663 57008 y(A)g(:)f(B)g(|)h(.....)g
(*common*.)15663 58337 y(B)g(:)f(C)g(|)h(.....)g(*common*.)13920
60993 y(case)g(3b:)15663 63650 y(A)g(:)f(C)g(|)h({X1)f(...)h(XN}.)15663
64979 y(B)g(:)f(C)g(|)h({)f(y)g(|)h(y)f(is)g(in)h(subset)g(of)f({X1)h
(..)f(XN}})h(*common*.)p eop
%%Page: 23 23
23 22 bop 6974 4317 a Fj(5)1107 b(INHERIT)-92 b(ANCE)371
b(\(GRAFTING\))20110 b Fq(23)15663 8192 y Fa(C)582 b(=)f(......)13920
10848 y(case)h(3c)f(\(disallowed)i(by)e(semantic)i(rule)f(5.4\):)15082
12177 y(for)g(guaranteeing)h(transitivity,)g(not)f(needed)15082
13505 y(for)g(theorem)g(5.1.)15663 16162 y(A)g(:)f(B)g(|)h(......)15663
17490 y(B)g(=)f(.....)15663 18818 y(C)h(=)f(*inherit*)i(B.)12177
22139 y Fq(In)368 b(case)g(3a)i(w)-31 b(e)369 b(can)g(pro)-31
b(v)g(e)369 b(the)g(subt)-31 b(yp)31 b(e)369 b(relation)i(in)e(t)-31
b(w)g(o)370 b(w)-31 b(a)g(ys.)494 b(C)369 b(is)f(b)31
b(oth)12177 23468 y(compatible)487 b(to)e(A)f(via)i(the)f(de\014nition)
h(of)f(compatibilit)-31 b(y)489 b(and)c(C)f(inherits)12177
24796 y(from)460 b(A)f(via)i(the)e(de\014nition)j(of)e(inheritance.)765
b(This)460 b(o)31 b(ccurs)458 b(b)31 b(ecause)459 b(B)h(is)12177
26124 y(b)31 b(oth)392 b(compatible)j(and)d(inherits)h(from)f(A)g(and)h
(C)f(is)g(b)31 b(oth)393 b(compatible)i(and)12177 27453
y(inherits)369 b(from)h(B.)10762 29224 y(2.)555 b(In)245
b(case)h(3b)h(the)f(class)h(C)f(is)g(compatible)j(to)e(A)f(b)-31
b(y)246 b(de\014nition)i(of)f(compatibilit)-31 b(y)-92
b(.)12177 30552 y(C')370 b(is)f(a)g(subset)g(of)g(A')h(b)-31
b(y)370 b(insp)31 b(ection.)10762 32323 y(3.)555 b(W)-92
b(e)368 b(disallo)-31 b(w)372 b(the)d(case)g(3c)h(with)g(the)g(follo)
-31 b(wing)372 b(seman)-31 b(tic)371 b(rule.)12177 34537
y Fc(Seman)-35 b(tic)424 b(rule)g(4)554 b Fk(A)c(class)f(which)h(is)g
(use)-57 b(d)550 b(for)g(inheritanc)-57 b(e)552 b(with)d(*in-)12177
35866 y(herit*)415 b(c)-57 b(annot)417 b(b)-57 b(e)417
b(use)-57 b(d)416 b(as)g(an)g(alternative)g(in)h(an)f(alternation)g(pr)
-57 b(o)g(duction)12177 37194 y(without)395 b(implie)-57
b(d)397 b(inheritanc)-57 b(e)398 b(\(i.e.)510 b(without)395
b(*c)-57 b(ommon*\).)12177 39408 y Fq(W)-92 b(e)435 b(need)g(this)i
(restriction)f(since)g(w)-31 b(e)437 b(cannot)g(reduce)e(the)h(com)-31
b(bined)437 b(sub-)12177 40736 y(t)-31 b(yp)31 b(e)351
b(links)g(in)g(class)g(dictionaries)h(of)g(this)f(form)g(to)h(either)f
(compatibilit)-31 b(y)355 b(or)12177 42064 y(inheritance)420
b(exclusiv)-31 b(ely)-92 b(.)646 b(Our)419 b(restriction)h(do)31
b(es)420 b(not)g(reduce)f(the)h(expres-)12177 43393 y(siv)-31
b(eness)409 b(of)h(our)g(notation.)616 b(W)-92 b(e)409
b(can)h(simply)h(add)f(implied)h(inheritance)g(to)12177
44721 y(the)369 b(alternation)j(pro)31 b(duction)370
b(in)f(case)h(3c)f(\(i.e.)494 b(w)-31 b(e)370 b(use)e(*common*\).)8634
47156 y Fp(\017)554 b Fq(The)304 b(fourth)g(and)g(\014nal)h(case)f(is)f
(a)h(class)g(hierarc)-31 b(h)g(y)304 b(where)g(a)g(class)g(C)f(is)h
(compatible)9741 48485 y(to)381 b(a)g(class)f(B)g(and)g(the)h(class)f
(B)g(inherits)g(from)h(a)f(class)h(A.)f(There)g(are)g(four)g(cases)9741
49813 y(where)369 b(this)h(can)f(o)31 b(ccur.)492 b(W)-92
b(e)369 b(will)i(analyze)f(these)f(separately)-92 b(.)16134
54020 y Fa(compatibility)6976 b(inheritance)12066 55348
y(C)581 b(<----------------------)k(B)c(<----------------------)k(A)
11485 58005 y(case)c(4a:)13228 60661 y(A)g(=)h(......)13228
61990 y(B)f(:)h(X)f(|)g(Y)h(|)f(Z)g(*common*)i(*inherit*)f(A.)13228
63318 y(C)f(:)h(X)f(|)g(Z.)p eop
%%Page: 24 24
24 23 bop 6974 4317 a Fj(6)1107 b(P)-92 b(ARAMETERIZED)371
b(CLASSES)e(\(THE)i(R)-31 b(OOT)369 b(STOCKS\))7981 b
Fq(24)11485 8192 y Fa(case)581 b(4b)h(\(disallowed)h(by)e(semantic)h
(rule)g(5.3\):)13228 10848 y(A)f(:)h(B)f(|)g(.....)h(*common*.)13228
12177 y(B)f(:)h(X)f(|)g(Y)h(|)f(Z.)13228 13505 y(C)g(:)h(X)f(|)g(Y.)
11485 16162 y(case)g(4c:)13228 18818 y(A)g(=)h(......)13228
20147 y(B)f(=)h(......)g(*inherit*)g(A.)13228 21475 y(C)f(:)h(B.)11485
24132 y(case)f(4d:)13228 26788 y(A)g(:)h(B)f(|)g(......)h(*common*.)
13228 28117 y(B)f(=)h(......)13228 29445 y(C)f(:)h(B.)10762
33209 y Fq(1.)555 b(In)363 b(case)h(4a)g(C)h(inherits)f(from)g(A)g
(since)g(all)h(elemen)-31 b(ts)365 b(in)f(C')h(inherit)g(from)f(A.)
10762 34980 y(2.)555 b(The)369 b(case)g(4b)g(has)h(b)31
b(een)368 b(de\014ned)h(as)g(illegal)j(b)-31 b(y)370
b(a)f(seman)-31 b(tic)371 b(rule.)10762 36751 y(3.)555
b(In)313 b(cases)g(4c)h(and)g(4d)h(the)f(class)g(C)g(inherits)g(from)g
(class)g(A)g(since)g(all)h(elemen)-31 b(ts)12177 38079
y(in)369 b(C')h(inherit)g(from)g(A.)8634 40515 y(This)g(completes)g
(the)g(pro)31 b(of)369 b(of)h(the)f(Subt)-31 b(yp)31
b(e-T)-92 b(ransitivit)-31 b(y-Theorem.)6974 44175 y
Fi(6)1793 b(P)-50 b(arameterized)600 b(Classes)f(\(The)g(Ro)50
b(ot)597 b(Sto)50 b(c)-50 b(ks\))6974 46600 y Fq(The)507
b(notion)h(of)g(parameterized)g(classes)e(is)h(related)g(to)h(grafting)
h(in)e(that)h(w)-31 b(e)507 b(inherit)6974 47928 y(and/or)367
b(o)-31 b(v)g(erride)367 b(classes)e(when)i(w)-31 b(e)367
b(w)-31 b(an)g(t)367 b(to)g(use)f(parameterized)h(classes.)492
b(The)366 b(di\013er-)6974 49257 y(ence)j(is)g(that)h(these)f(classes)g
(ha)-31 b(v)g(e)370 b(one)g(or)f(more)g(formal)i(t)-31
b(yp)31 b(e)370 b(parameters.)8634 50585 y(This)477 b(parameterization)
i(adds)c(complexit)-31 b(y)479 b(to)e(the)f(construction)h(of)f(a)h
(class)f(dic-)6974 51913 y(tionary)-92 b(,)400 b(but)393
b(the)f(p)31 b(o)-31 b(w)g(er)393 b(endo)-31 b(w)g(ed)394
b(on)f(suc)-31 b(h)392 b(a)h(system)f(more)h(than)g(mak)-31
b(es)394 b(up)e(for)h(the)6974 53242 y(additional)338
b(complexit)-31 b(y)-92 b(.)484 b(Systems)336 b(whic)-31
b(h)336 b(are)f(built)h(around)g(parameterized)g(class)g(dic-)6974
54570 y(tionaries)330 b(are)f(constructed)g(under)f(a)i(di\013eren)-31
b(t)329 b(philosoph)-31 b(y)330 b(than)g(ones)f(whic)-31
b(h)330 b(are)f(built)6974 55898 y(around)465 b(classes.)779
b(P)-31 b(arameterized)466 b(class)f(systems)g(are)f(t)-31
b(ypically)468 b(not)e(designed)f(to)g(b)31 b(e)6974
57227 y(stand)381 b(alone)h(w)-31 b(orking)383 b(systems,)h(although)g
(they)d(sometimes)h(are.)528 b(These)381 b(systems)g(are)6974
58555 y(built)357 b(as)e(generic)h(foundations)i(to)e(b)31
b(e)355 b(inherited)i(b)-31 b(y)355 b(man)-31 b(y)357
b(soft)-31 b(w)g(are)358 b(systems.)488 b(By)355 b(w)-31
b(a)g(y)6974 59883 y(of)362 b(analogy)-92 b(,)366 b(they)d(are)e(gro)
-31 b(wn)363 b(for)f(their)h(ro)31 b(ots)362 b(and)g(not)h(their)f
(fruit.)491 b(The)362 b(fruiting)h(p)31 b(or-)6974 61212
y(tion)398 b(will)h(b)31 b(e)396 b(gro)-31 b(wn)399 b(in)e(other)g(en)
-31 b(vironmen)g(ts,)406 b(and)398 b(eac)-31 b(h)397
b(will)i(use)d(the)i(parameterized)6974 62540 y(class)369
b(system)g(for)h(ro)31 b(ots.)8634 63869 y(F)-92 b(or)519
b(an)h(example,)560 b(consider)519 b(a)h(generic)g(library)h(of)f
(routines)g(related)h(to)f(graphs.)6974 65197 y(Since)388
b(all)h(graphs)f(ha)-31 b(v)g(e)389 b(no)31 b(des)388
b(and)g(edges)g(of)h(di\013eren)-31 b(t)388 b(t)-31 b(yp)31
b(es)388 b(w)-31 b(e)389 b(w)-31 b(ould)390 b(need)d(a)i(class)p
eop
%%Page: 25 25
25 24 bop 6974 4317 a Fj(6)1107 b(P)-92 b(ARAMETERIZED)371
b(CLASSES)e(\(THE)i(R)-31 b(OOT)369 b(STOCKS\))7981 b
Fq(25)6974 8192 y(dictionary)381 b(for)e(eac)-31 b(h)379
b(graph)g(application.)525 b(W)-92 b(e)378 b(could)h(then)h(exploit)g
(the)f(use)g(of)g(inherit)6974 9520 y(and)387 b(o)-31
b(v)g(erride)387 b(to)h(reuse)d(the)i(soft)-31 b(w)g(are.)547
b(Ho)-31 b(w)g(ev)g(er,)393 b(it)388 b(w)-31 b(ould)388
b(b)31 b(e)386 b(b)31 b(etter)387 b(to)g(construct)g(a)6974
10848 y(generic)426 b(graph)h(class)f(dictionary)i(through)e(the)h(use)
e(of)i(parameterized)g(classes.)663 b(Con-)6974 12177
y(sider)430 b(the)i(follo)-31 b(wing)435 b(class)c(dictionary)i(whic)
-31 b(h)432 b(sp)31 b(eci\014es)430 b(a)i(generic)f(graph)h(as)f(a)g
(list)h(of)6974 13505 y(edges)308 b(where)g(an)h(edge)f(is)g(de\014ned)
g(as)h(t)-31 b(w)g(o)310 b(no)31 b(des.)472 b(W)-92 b(e)307
b(ha)-31 b(v)g(e)309 b(added)g(some)g(concrete)f(syn-)6974
14833 y(tax,)384 b(but)c(recall)h(that)g(all)g(applications)h(are)e
(completely)i(shielded)e(from)h(this)f(syn)-31 b(tactic)6974
16162 y(sugaring)370 b(of)g(the)f(input)h(language.)6974
18376 y Fa(Graph\(Node\))583 b(=)e("edgeList")8136 19704
y(<edgeList>)i(List\(Edge\(Node\)\).)6974 21032 y(Edge\(Node\))f(=)8136
22361 y("from")g(<from>)g(Node)g("to")g(<to>)f(Node.)6974
23689 y(List\(S\))h(~)f({S}.)6974 25903 y Fq(W)-92 b(e)508
b(can)h(no)-31 b(w)510 b(write)g(a)f(lot)i(of)e(generic)g(graph)h(soft)
-31 b(w)g(are)510 b(whic)-31 b(h)510 b(can)f(b)31 b(e)509
b(used)f(b)-31 b(y)510 b(all)6974 27231 y(graphs)381
b(whic)-31 b(h)381 b(can)g(b)31 b(e)381 b(represen)-31
b(ted)379 b(as)i(a)g(list)h(of)f(edges)g(where)f(edges)h(are)g
(represen)-31 b(ted)6974 28560 y(as)396 b(a)g(list)h(of)g(t)-31
b(w)g(o)398 b(no)31 b(des.)573 b(Let)397 b(us)e(assume)h(w)-31
b(e)397 b(ha)-31 b(v)g(e)397 b(made)g(a)g(large)f(in)-31
b(v)g(estmen)g(t)399 b(in)d(this)6974 29888 y(t)-31 b(yp)31
b(e)373 b(of)g(graph)f(soft)-31 b(w)g(are)374 b(and)f(it)g(has)g(serv)
-31 b(ed)372 b(us)f(w)-31 b(ell.)504 b(W)-92 b(e)372
b(no)-31 b(w)373 b(\014nd)g(that)g(w)-31 b(e)373 b(ha)-31
b(v)g(e)374 b(an)6974 31216 y(application)434 b(whic)-31
b(h)431 b(requires)f(lab)31 b(eled)432 b(edges.)677 b(This)431
b(application)j(happ)31 b(ens)430 b(to)h(in)-31 b(v)g(olv)g(e)6974
32545 y(graphs)365 b(where)g(the)h(no)31 b(des)365 b(are)g(to)-31
b(wns)367 b(or)e(villages)j(and)e(the)f(lab)31 b(els)366
b(are)g(the)f(distance)h(in)6974 33873 y(kilometers)382
b(b)31 b(et)-31 b(w)g(een)381 b(the)g(to)-31 b(wns)382
b(and/or)f(villages.)529 b(W)-92 b(e)380 b(w)-31 b(ould)382
b(lik)-31 b(e)382 b(to)f(write)g(soft)-31 b(w)g(are)6974
35201 y(whic)g(h)422 b(uses)f(our)g(previous)g(in)-31
b(v)g(estmen)g(t)424 b(in)e(generic)f(graph)h(soft)-31
b(w)g(are)423 b(and,)435 b(if)422 b(p)31 b(ossible,)6974
36530 y(w)-31 b(e)340 b(w)-31 b(ould)340 b(lik)-31 b(e)341
b(the)e(new)h(soft)-31 b(w)g(are)341 b(to)f(b)31 b(e)338
b(generic)i(for)f(an)-31 b(y)340 b(graph)g(with)g(a)g(lab)31
b(eled)340 b(edge.)6974 37858 y(W)-92 b(e)368 b(accomplish)j(b)31
b(oth)370 b(goals)g(b)-31 b(y)370 b(constructing)g(the)g(follo)-31
b(wing)373 b(class)c(dictionary)-92 b(.)6974 40072 y
Fa(LabeledGraph\(Node,)584 b(EdgeLabel\))e(=)8136 41400
y(*inherit*)h(Graph\(Node\))9298 42729 y(*override*)g(<edgeList>)10461
44057 y(List\(LabeledEdge\(Node,)h(EdgeLabel\)\).)6974
45385 y(LabeledEdge\(Node,)g(EdgeLabel\))e(=)8136 46714
y(*inherit*)h(Edge\(Node\))9298 48042 y("label")g(<label>)f(EdgeLabel.)
6974 50256 y Fq(W)-92 b(e)457 b(can)i(use)e(this)i(parameterized)g
(class)f(dictionary)i(to)f(de\014ne)f(our)g(regional)h(map)g(of)6974
51584 y(to)-31 b(wns,)489 b(villages,)h(and)464 b(distances)g(b)-31
b(y)464 b(giving)i(actual)g(parameters)e(to)h(the)f(ab)31
b(o)-31 b(v)g(e)465 b(class)6974 52913 y(dictionary)-92
b(.)6974 55127 y Fa(Map)581 b(=)h(*inherit*)8136 56455
y(LabeledGraph)h(\(=>)f(EdgeLabel)g(Road,)g(=>)g(Node)f(Community\).)
6974 57783 y(Community)h(:)g(Village)g(|)f(Town)8136
59112 y(*common*)h(<communityname>,)i(<desc>)e(String.)6974
60440 y(Village)g(=)f("village".)6974 61768 y(Town)h(=)f("town".)6974
63097 y(Road)h(=)f("road")h(<roadname>)h(String)11042
64425 y(<routeNumber>,)g(<distance>Nnumber.)p eop
%%Page: 26 26
26 25 bop 6974 4317 a Fj(6)1107 b(P)-92 b(ARAMETERIZED)371
b(CLASSES)e(\(THE)i(R)-31 b(OOT)369 b(STOCKS\))7981 b
Fq(26)6974 8192 y(This)523 b(class)h(dictionary)h(is)e(expanded)h(b)-31
b(y)523 b(the)g(Demeter)h(system)f(in)-31 b(to)525 b(the)e(follo)-31
b(wing)6974 9520 y(grammar:)6974 11734 y Fa(map)581 b(=)8136
13062 y("edgelist")i(<)e(edgelist)h(>)g
(road_community-labelededge-list)j(.)6974 14390 y(community)d(:)g
(village)g(|)f(town)h(.)6974 15719 y(village)g(=)8136
17047 y("village")h(<)e(communityname)i(>)e(string)h(<)g(desc)f(>)h
(string)g(.)6974 18376 y(town)g(=)8136 19704 y("town")g(<)f
(communityname)j(>)d(string)h(<)f(desc)h(>)f(string)h(.)6974
21032 y(road)g(=)8136 22361 y("road")g(<)f(roadname)i(>)e(string)8136
23689 y(<)g(routenumber)i(>)f(number)g(<)f(distance)h(>)g(number)g(.)
6974 25017 y(community-edge)h(=)8136 26346 y("from")f(<)f(from)h(>)g
(community)g("to")g(<)f(to)h(>)f(community)h(.)6974 27674
y(road_community-labelededge)j(=)8136 29002 y("from")d(<)f(from)h(>)g
(community)8136 30331 y("to")g(<)f(to)h(>)f(community)8136
31659 y("label")h(<)g(label)g(>)f(road)h(.)6974 32987
y(road_community-labelededge-list)k(~)8136 34316 y({)581
b(road_community-labelededge)k(})d(.)6974 35644 y(community-edge-list)i
(~)d({)g(community-edge)j(})d(.)6974 36972 y(community-graph)i(=)8136
38301 y("edgelist")g(<)e(edgelist)h(>)g(community-edge-list)i(.)6974
39629 y(road_community-labeledgraph)h(=)8136 40958 y("edgelist")e(<)e
(edgelist)h(>)g(road_community-labelededge-list)j(.)6974
43171 y Fq(The)288 b(follo)-31 b(wing)292 b(sho)-31 b(ws)289
b(the)f(inheritance)h(relationships)h(b)31 b(et)-31 b(w)g(een)289
b(the)g(generated)g(classes.)6974 44500 y(W)-92 b(e)401
b(use)g(the)g(follo)-31 b(wing)406 b(notation:)560 b(W)-92
b(e)401 b(use)f Fa(!)i Fq(to)g(in)-31 b(tro)31 b(duce)403
b(an)e(abstract)i(class)e(\(i.e.)591 b(a)6974 45828 y(class)461
b(whic)-31 b(h)462 b(cannot)g(b)31 b(e)461 b(instan)-31
b(tiated\))465 b(and)c Fa(!!)g Fq(to)h(in)-31 b(tro)31
b(duce)462 b(an)g(instan)-31 b(tiable)464 b(class)6974
47156 y(in)520 b(the)h(underlying)g(ob)61 b(ject-orien)-31
b(ted)522 b(system.)946 b Fb(*inherit*)522 b Fq(follo)-31
b(w)g(ed)523 b(b)-31 b(y)520 b(sev)-31 b(eral)521 b(class)6974
48485 y(names)410 b(determines)g(from)h(where)f(where)f(the)h(class)g
(inherits.)616 b(These)409 b(pro)31 b(ductions)411 b(are)6974
49813 y(generated)370 b(b)-31 b(y)369 b(the)h(system)f(and)g(can)h(b)31
b(e)369 b(dra)-31 b(wn)369 b(as)g(a)h(directed)f(acyclic)i(graph.)6974
53355 y Fa(map)581 b(!!)8136 54684 y(*inherit*)i
(road_community-labeledgraph,)8136 56012 y(construction)g(.)6974
57341 y(community)f(!)g(<)f(communityname)i(>)e(,)h(<)f(desc)h(>)f
(string)h(.)6974 58669 y(village)g(!!)f("village")i(*inherit*)f
(construction)h(.)6974 59997 y(town)f(!!)f("town")h(*inherit*)h
(construction)g(.)6974 61326 y(road)f(!!)8136 62654 y("road")g(<)f
(roadname)i(>)e(string)8136 63982 y(<)g(routenumber)i(>)f(,)f(<)g
(distance)h(>)g(number)8136 65311 y(*inherit*)h(construction)g(.)p
eop
%%Page: 27 27
27 26 bop 6974 4317 a Fj(6)1107 b(P)-92 b(ARAMETERIZED)371
b(CLASSES)e(\(THE)i(R)-31 b(OOT)369 b(STOCKS\))7981 b
Fq(27)6974 8192 y Fa(labeledgraph)583 b(!)e(*inherit*)i(construction)g
(.)6974 9520 y(labelededge)g(!)8136 10848 y("label")f(<)g(label)g(>)f
(anytype)h(*inherit*)h(construction)f(.)6974 12177 y(graph)g(!)8136
13505 y("edgelist")h(<)e(edgelist)h(>)g(anytype)g(*inherit*)g
(construction)h(.)6974 14833 y(edge)f(!)8136 16162 y("from")g(<)f(from)
h(>)g(anytype)8136 17490 y("to")g(<)f(to)h(>)f(anytype)h(*inherit*)h
(construction)g(.)6974 18818 y(list)f(!)f(*inherit*)h(repetition)h(.)
6974 20147 y(community-edge)g(!!)f(*inherit*)g(edge)g(.)6974
21475 y(road_community-labelededge)j(!!)8136 22803 y(*inherit*)e
(labelededge)f(,)g(community-edge)h(.)6974 24132 y
(road_community-labelededge-list)j(!!)581 b(*inherit*)i(list)e(.)6974
25460 y(community-edge-list)j(!!)d(*inherit*)i(list)f(.)6974
26788 y(community-graph)h(!!)f(*inherit*)g(graph)g(.)6974
28117 y(road_community-labeledgraph)j(!!)8136 29445 y(*inherit*)e
(labeledgraph)g(,)e(community-graph)i(.)6974 31305 y
Fq(This)405 b(inheritance)i(allo)-31 b(ws)407 b(us)e(to)g(write)h
(generic,)415 b(reusable)405 b(soft)-31 b(w)g(are.)603
b(A)405 b(t)-31 b(ypical)407 b(input)6974 32633 y(\014le)369
b(for)h(this)f(class)g(dictionary)i(migh)-31 b(t)372
b(lo)31 b(ok)370 b(lik)-31 b(e:)6974 34493 y Fa(edgelist)8136
35821 y(from)582 b(village)g("Ebnat-Kappel")1164 b("small")9298
37150 y(to)582 b(town)g("Wattwil")g("bigger")10461 38478
y(label)g(road)f("howart")i(12)e(5)8136 39806 y(from)h(village)g
("Diepoldsau")h("on)f(Austrian)g(side")9298 41135 y(to)g(village)g
("Widnau")g("on)g(Swiss)g(side")10461 42463 y(label)g(road)f("bridge")i
(34)e(2)8634 44323 y Fq(F)-92 b(or)380 b(a)i(thorough)g(description)g
(of)f(the)g(meanings)h(of)g(a)f(parameterized)h(class)f(dictio-)6974
45651 y(nary)369 b(w)-31 b(e)370 b(refer)e(the)i(reader)e(to)i([Lie88b)
r(].)8634 46979 y(Th)-31 b(us)408 b(far)g(w)-31 b(e)409
b(ha)-31 b(v)g(e)408 b(used)g(parameterized)h(classes)e(without)j
(restrictions.)610 b(The)408 b(fol-)6974 48308 y(lo)-31
b(wing)524 b(example)f(illustrates)g(the)f(need)f(for)g(restrictions)i
(on)e(the)h(usage)g(of)g(parame-)6974 49636 y(terized)417
b(classes.)637 b(It)417 b(sho)-31 b(ws)418 b(that)g(parameterized)h
(con)-31 b(text-free)418 b(grammars)h(can)e(de\014ne)6974
50964 y(non-con)-31 b(text-free)371 b(languages.)6974
52824 y Fa(ContextSensitive)583 b(=)f(<example>)g(A\(U,V,W\).)6974
54152 y(A\(X,Y,Z\))g(:)f(L\(X,Y,Z\))i(|)e(R\(X,Y,Z\).)6974
55481 y(L\(X,Y,Z\))h(=)f(<first>)i(X)e(<second>)h(Y)g(<third>)g(Z.)6974
56809 y(R\(X,Y,Z\))g(=)f(<u>)h(A\(H1\(X\),)g(H2\(Y\),)g(H3\(Z\)\).)6974
58138 y(H1\(S\))g(=)f("u")h(<t>)f(S.)6974 59466 y(H2\(S\))h(=)f("v")h
(<t>)f(S.)6974 60794 y(H3\(S\))h(=)f("w")h(<t>)f(S.)6974
62123 y(U)g(=)g("u".)h(V)f(=)h("v".)g(W)f(=)g("w".)8634
63982 y Fq(When)313 b(w)-31 b(e)314 b(apply)h(the)f(expansion)g(pro)31
b(cess)313 b(in)-31 b(tro)31 b(duced)314 b(with)h(the)e(lab)31
b(eled)315 b(graph)f(ex-)6974 65311 y(ample)303 b(to)f(this)h(class)e
(dictionary)j(w)-31 b(e)302 b(get)h(in)-31 b(to)303 b(an)f(in\014nite)h
(lo)31 b(op:)460 b(the)302 b(expansion)h(pro)31 b(cess)p
eop
%%Page: 28 28
28 27 bop 6974 4317 a Fj(6)1107 b(P)-92 b(ARAMETERIZED)371
b(CLASSES)e(\(THE)i(R)-31 b(OOT)369 b(STOCKS\))7981 b
Fq(28)6974 8192 y(w)-31 b(ould)441 b(generate)f(in\014nitely)i(man)-31
b(y)441 b(in)-31 b(termediate)442 b(classes.)703 b(Our)439
b(implemen)-31 b(tation)444 b(has)6974 9520 y(to)370
b(b)31 b(e)368 b(protected)i(from)g(this)g(condition.)8634
10848 y(Also,)302 b(the)284 b(language)i(de\014ned)e(b)-31
b(y)284 b(this)g(grammar)h(is)f(a)g(w)-31 b(ell-kno)g(wn)287
b(con)-31 b(text-sensitiv)g(e)6974 12177 y(language)377
b(whic)-31 b(h)377 b(is)e(kno)-31 b(wn)376 b(not)g(to)g(b)31
b(e)375 b(con)-31 b(text-free:)506 b Fh(u)31379 11775
y Fg(n)31982 12177 y Fh(v)32559 11775 y Fg(n)33160 12177
y Fh(w)33982 11775 y Fg(n)34585 12177 y Fk(,n)403 b Fh(>)e
Fk(0.)511 b Fq(The)375 b(recursiv)-31 b(e)6974 13505
y(descen)g(t-parsing)440 b(approac)-31 b(h)441 b(is)f(not)h(capable)g
(of)f(parsing)h(suc)-31 b(h)439 b(languages.)707 b(Therefore)6974
14833 y(w)-31 b(e)294 b(will)i(restrict)d(the)h(recursiv)-31
b(e)293 b(parameterized)i(class)f(de\014nitions)h(so)f(that)g(an)-31
b(y)295 b(instance)6974 16162 y(de\014nes)j(a)g(con)-31
b(text-free)300 b(language.)471 b(In)298 b(applications)j(one)e(do)31
b(es)298 b(not)h(need)f(the)h(generalit)-31 b(y)6974
17490 y(of)300 b(the)g(Con)-31 b(textSensitiv)g(e)303
b(example.)471 b(The)300 b(follo)-31 b(wing)303 b(condition)e(places)f
(a)g(b)31 b(ound)300 b(on)g(the)6974 18818 y(parameterization)372
b(but)e(do)31 b(es)368 b(not)i(limit)i(the)d(practical)i(applications.)
6974 21227 y Fc(De\014nition)425 b(8)554 b Fk(A)415 b(p)-57
b(ar)g(ameterize)g(d)415 b(class)f(T)h(is)g Fq(b)31 b(ounded)p
Fk(,)420 b(if)c(every)g(r)-57 b(e)g(cursive)416 b(use)f(of)g(T)6974
22555 y(satis\014es)325 b(the)g(r)-57 b(estriction)326
b(that)e(every)i(actual)f(p)-57 b(ar)g(ameter)325 b(of)h(the)f(r)-57
b(e)g(cursive)327 b(use)e(is)g(either:)8634 24747 y Fp(\017)554
b Fk(a)396 b(formal)g(p)-57 b(ar)g(ameter)396 b(of)g(T)8634
26950 y Fp(\017)554 b Fk(an)540 b(instanc)-57 b(e)540
b(of)f(some)h(p)-57 b(ar)g(ameterize)g(d)539 b(class)g(which)g(do)-57
b(es)539 b(not)g(have)g(a)g(formal)9741 28279 y(p)-57
b(ar)g(ameter)396 b(of)h(T)f(as)f(an)h(actual)g(p)-57
b(ar)g(ameter.)8634 30482 y Fp(\017)554 b Fk(a)396 b(class.)6974
32890 y Fq(Some)370 b(in)-31 b(teresting)371 b(examples)f(of)f(b)31
b(ounded)370 b(parameterized)g(class)f(de\014nitions)i(are:)8634
35083 y Fp(\017)554 b Fq(P)-31 b(erm)g(utation)9741 37928
y Fa(MyT)582 b(=)f(<ex>)h(T\(Ident,)g(Number\).)9741
39257 y(T\(X,Y\))g(:)g(E)f(|)g(N\(X,Y\).)9741 40585 y(E)h(=)f("e".)9741
41913 y(N\(X,Y\))h(=)g("n")f(<first>)h(X)g(<second>)g(Y)f(<third>)i
(T\(Y,X\).)8634 44759 y Fp(\017)554 b Fq(Exp)31 b(onen)-31
b(tial)9741 46525 y(A)412 b(parameterized)g(class)g(instan)-31
b(tiation)415 b(can)d(generate)g(an)g(exp)31 b(onen)-31
b(tial)414 b(n)-31 b(um)g(b)31 b(er)9741 47853 y(of)455
b(parameterized)h(class)e(instances)h(\(exp)31 b(onen)-31
b(tial)457 b(in)e(the)f(size)h(of)f(the)h(parame-)9741
49181 y(terized)435 b(class)g(de\014nition)i(and)e(the)g(size)f(of)i
(the)f(actual)h(parameters\).)690 b(Consider)9741 50510
y(the)463 b(follo)-31 b(wing)465 b(example)f(whic)-31
b(h)463 b(basically)h(generates)f(all)g(p)31 b(erm)-31
b(utations)464 b(of)f(the)9741 51838 y(symmetric)371
b(group)e(on)g(4)h(elemen)-31 b(ts:)9741 54684 y Fa(MyA)582
b(=)f(<ex>)h(A\(C1,C2,C3,C4\).)9741 56012 y(C1)g(=)f("c1".)9741
57341 y(C2)h(=)f("c2".)9741 58669 y(C3)h(=)f("c3".)9741
59997 y(C4)h(=)f("c4".)9741 61326 y(A\(X1,X2,X3,X4\))i(=)10904
62654 y(["t1")e(<t1>)h(A\(X2,X1,X3,X4\)])10904 63982
y(["t2")f(<t2>)h(A\(X1,X3,X2,X4\)])10904 65311 y(["t3")f(<t3>)h
(A\(X1,X2,X4,X3\)].)p eop
%%Page: 29 29
29 28 bop 6974 4317 a Fj(7)1107 b(OR)-31 b(GANIZING)369
b(THE)h(GARDEN)20010 b Fq(29)9741 8192 y(The)424 b(instan)-31
b(tiation)428 b(of)d(parameterized)g(class)f(A)g(on)g(the)h(\014rst)e
(line)i(generates)f(24)9741 9520 y(=)325 b(4)h Fp(\003)g
Fq(3)g Fp(\003)f Fq(2)h Fp(\003)g Fq(1)g(parameterized)g(class)g
(instan)-31 b(tiations)329 b(or)c(in)h(general)g Fh(n)p
Fq(!)g(\(i.e.)480 b(the)9741 10848 y(size)349 b(of)g(the)g(symmetric)h
(group)e(on)h Fh(n)g Fq(elemen)-31 b(ts\).)488 b(In)348
b(practical)i(applications)h(this)9741 12177 y(\\p)31
b(erm)-31 b(utation)313 b(feature")e(is)f(seldom)h(used.)473
b(One)309 b(could)i(exclude)g(this)f(exp)31 b(onen)-31
b(tial)9741 13505 y(b)31 b(eha)-31 b(vior)336 b(b)-31
b(y)336 b(requiring)f(that)i(ev)-31 b(ery)335 b(parameter)h(of)f(a)h
(parameterized)g(class)f(b)31 b(e)334 b(in)9741 14833
y(the)370 b(same)f(p)31 b(osition)371 b(throughout)g(a)e(giv)-31
b(en)371 b(rule\(s\).)8634 17042 y Fp(\017)554 b Fq(Splitting)9741
19904 y Fa(MyT)582 b(=)f(<ex>)h(T\(Ident,Number\).)9741
21232 y(T\(X,Y\))g(:)g(E\(X\))f(|)h(N\(Y\).)9741 22560
y(E\(X\))g(=)f(String)h(<first>)h(X)e(.)9741 23889 y(N\(Y\))h(=)f("n")h
(<erstes>)g(T\(Y,)g(List\(Number\)\).)9741 25217 y(List\(S\))g(~)g
("list")g({S}.)9741 28079 y Fq(A)369 b(legal)i(input)f(is:)9741
30722 y Fa(n)582 b(n)f(n)g(n)g(n)h("ab")f(list)h(45)8634
33365 y Fq(The)480 b(follo)-31 b(wing)484 b(theorems)c(guaran)-31
b(tee)482 b(that)f(b)31 b(ounded)479 b(parameterized)j(classes)d(al-)
6974 34694 y(w)-31 b(a)g(ys)538 b(de\014ne)f(con)-31
b(text-free)538 b(languages)h(and)e(that)h(the)f(expansion)h(of)g
(parameterized)6974 36022 y(classes)369 b(is)g(\014nite.)6974
38444 y Fc(Theorem)425 b(3)554 b Fk(A)-28 b(n)510 b(instanc)-57
b(e)512 b(of)e(a)g(b)-57 b(ounde)g(d)511 b(p)-57 b(ar)g(ameterize)g(d)
510 b(class)g(gener)-57 b(ates)510 b(a)g(\014nite)6974
39772 y(numb)-57 b(er)397 b(of)f(classes.)6974 42194
y Fc(Theorem)425 b(4)554 b Fk(The)462 b(language)g(de\014ne)-57
b(d)463 b(by)f(an)g(instanc)-57 b(e)463 b(of)e(a)h(b)-57
b(ounde)g(d)462 b(p)-57 b(ar)g(ameterize)g(d)6974 43522
y(class)395 b(is)h(c)-57 b(ontext-fr)g(e)g(e.)8634 45944
y Fq(The)370 b(concept)g(of)f(subt)-31 b(yp)31 b(e)370
b(is)f(easy)g(to)h(generalize)g(to)g(parameterized)h(classes.)6974
49603 y Fi(7)1793 b(Organizing)598 b(the)g(Garden)6974
52027 y Fq(W)-92 b(e)523 b(need)h(a)g(structuring)h(mec)-31
b(hanism)525 b(to)g(organize)g(class)f(dictionaries)i(and)f(the)f(as-)
6974 53355 y(so)31 b(ciated)493 b(soft)-31 b(w)g(are.)863
b(Therefore)493 b(w)-31 b(e)492 b(in)-31 b(tro)31 b(duce)493
b(the)g(concept)f(of)h(a)g(mo)31 b(dule)493 b(whic)-31
b(h)493 b(is)6974 54684 y(a)521 b(collection)j(of)d(\(parameterized\))i
(class)e(and)g(metho)31 b(d)522 b(de\014nitions.)949
b(W)-92 b(e)520 b(follo)-31 b(w)524 b(the)6974 56012
y(Mo)31 b(dula-2)472 b(rules)e(and)h(group)g(our)f(mo)31
b(dules)471 b(in)-31 b(to)472 b(t)-31 b(w)g(o)473 b(parts:)695
b(a)471 b(de\014nition)i(part)e(and)6974 57341 y(an)504
b(implemen)-31 b(tation)508 b(part.)896 b(In)503 b(the)h(de\014nition)h
(part)f(w)-31 b(e)504 b(put)g(all)h(the)f(classes)f(whic)-31
b(h)6974 58669 y(are)461 b(imp)31 b(ortan)-31 b(t)464
b(for)e(clien)-31 b(ts)463 b(and)f(the)g(metho)31 b(d)462
b(headings)h(with)g(t)-31 b(yp)31 b(e)462 b(information)j(for)6974
59997 y(argumen)-31 b(ts)407 b(and)f(result.)602 b(In)406
b(the)g(implemen)-31 b(tation)410 b(part)c(w)-31 b(e)406
b(put)g(the)g(implemen)-31 b(tation)6974 61326 y(related)434
b(class)g(de\014nitions)g(and)g(the)g(complete)h(metho)31
b(ds.)686 b(The)434 b(implemen)-31 b(tation)437 b(part)6974
62654 y(also)358 b(con)-31 b(tains)359 b(a)f(list)g(of)g(\014le)f
(names)h(whic)-31 b(h)358 b(refer)f(to)h(the)f(\014les)g(con)-31
b(taining)361 b(the)c(metho)31 b(ds)6974 63982 y(written)357
b(in)g(the)g(language)h(of)f(the)g(underlying)g(ob)61
b(ject-orien)-31 b(ted)359 b(system.)488 b(Mo)31 b(dules)357
b(and)6974 65311 y(their)369 b(organization)k(in)-31
b(to)370 b(pairs)f(ha)-31 b(v)g(e)371 b(the)e(follo)-31
b(wing)373 b(adv)-61 b(an)-31 b(tages:)p eop
%%Page: 30 30
30 29 bop 6974 4317 a Fj(8)1107 b(RELA)-92 b(TED)370
b(W)-31 b(ORK)26013 b Fq(30)8634 8192 y Fp(\017)554 b
Fq(Information)291 b(hiding.)467 b(W)-92 b(e)288 b(can)h(hide)g(metho)
31 b(d)290 b(b)31 b(o)g(dies,)305 b(the)289 b(in)-31
b(ternals)290 b(of)f(construc-)9741 9520 y(tion)353 b(classes)e(and)h
(auxiliary)i(classes)d(whic)-31 b(h)353 b(are)f(only)g(used)f(for)h
(implemen)-31 b(tation.)8634 11734 y Fp(\017)554 b Fq(Separate)370
b(en)-31 b(vironmen)g(t)371 b(generation)g(and)f(separate)f
(compilation.)8634 13948 y Fp(\017)554 b Fq(Av)-31 b(oiding)372
b(con\015icts)e(b)31 b(et)-31 b(w)g(een)370 b(class)f(names.)6974
17608 y Fi(8)1793 b(Related)598 b(W)-149 b(ork)6974 20033
y Fq(The)424 b(Demeter)g(system)h(has)f(b)31 b(ene\014tted)425
b(from)g(w)-31 b(ork)425 b(done)f(in)h(three)f(areas:)603
b(Program-)6974 21361 y(ming)398 b(languages,)405 b(Arti\014cial)399
b(In)-31 b(telligence)398 b(and)f(Data)g(Bases.)575 b(A)396
b(detailed)i(comparison)6974 22690 y(exceeds)333 b(the)g(space)g
(requiremen)-31 b(ts)334 b(of)g(this)f(pap)31 b(er)333
b(and)g(can)h(b)31 b(e)333 b(found)g(in)h(the)f(forthcom-)6974
24018 y(ing)370 b(b)31 b(o)g(ok)369 b([Lie88b)r(].)493
b(W)-92 b(e)369 b(giv)-31 b(e)370 b(here)f(a)g(few)h(p)31
b(oin)-31 b(ters:)8634 26232 y Fp(\017)554 b Fq(Ob)61
b(ject-orien)-31 b(ted)311 b(programming:)464 b(Ob)61
b(ject-orien)-31 b(ted)311 b(programming)f(is)f(promoted)9741
27560 y(b)-31 b(y)321 b(Sim)-31 b(ula-67)324 b([DMN70)q(],)331
b(Smalltalk-80)326 b([GR83)q(],)331 b(Fla)-31 b(v)g(ors)322
b([Mo)31 b(o86)r(],)331 b(Ob)61 b(jectiv)-31 b(e-)9741
28889 y(C)446 b([Co)-31 b(x86)s(],)466 b(C++)446 b([Str86)r(],)466
b(Ei\013el)446 b([Mey86)r(].)723 b(Our)445 b(protot)-31
b(yp)31 b(e)447 b(implemen)-31 b(tation)9741 30217 y(uses)476
b(Fla)-31 b(v)g(ors)478 b(and)g(F)-92 b(ranz)476 b(Lisp.)816
b(Demeter)477 b(extends)g(the)g(ob)61 b(ject-orien)-31
b(ted)480 b(lan-)9741 31545 y(guages)370 b(men)-31 b(tioned)371
b(ab)31 b(o)-31 b(v)g(e)371 b(in)e(a)h(useful)f(w)-31
b(a)g(y)-92 b(.)9741 33316 y(The)591 b(o)-31 b(v)g(erride)591
b(mec)-31 b(hanism)592 b(of)f(Demeter)f(exists)h(in)f(similar)i(form)f
(in)g(Galileo)9741 34645 y([A)-31 b(CO85)s(])369 b(and)h(T)-92
b(axis)370 b([MBW80)q(])f(and)g(in)h([Tho86)r(].)8634
36859 y Fp(\017)554 b Fq(Language)464 b(design)f(and)g(parsing:)679
b(W)-92 b(e)462 b(use)g(the)h(ideas)f(promoted)i(b)-31
b(y)463 b(N.)g(Wirth)9741 38187 y(on)533 b(language)j(design)d([Wir74)q
(],)575 b([Wir84)q(],)g(data)534 b(structure)e(and)h(parser)f(design)
9741 39515 y([Wir76)q(],)370 b(grammar)h(notation)h([Wir77)q(])d(and)h
(t)-31 b(yp)31 b(e)370 b(c)-31 b(hec)g(king)370 b([Wir71)q(].)8634
41729 y Fp(\017)554 b Fq(Grammar-based)387 b(programming:)530
b(A)387 b(grammar-based)h(approac)-31 b(h)388 b(to)f(meta)h(pro-)9741
43058 y(gramming)314 b(in)e(P)-31 b(ascal)313 b(has)e(b)31
b(een)311 b(in)-31 b(tro)31 b(duced)312 b(in)g([CI84)r(].)474
b([F)-92 b(ra81])312 b(uses)f(grammars)9741 44386 y(for)362
b(de\014ning)g(data)h(structures.)489 b([KMMN85)q(])361
b(in)-31 b(tro)31 b(duce)363 b(an)e(algebra)i(of)f(program)9741
45714 y(fragmen)-31 b(ts.)463 b(The)276 b(POP)-92 b(AR)g(T)276
b(system)g(treats)g(grammars)h(as)f(ob)61 b(jects)277
b([Wil83)r(].)462 b(The)9741 47043 y(syn)-31 b(thesizer)305
b(generator)g(pro)61 b(ject)306 b(also)f(uses)f(a)h(grammar)h(based)e
(approac)-31 b(h)306 b([T)-92 b(ei84)r(].)9741 48371
y(GEM)369 b(describ)31 b(ed)368 b(in)i([GL85)q(])f(is)g(the)h
(predecessor)d(of)j(Demeter.)9741 50142 y(Our)361 b(w)-31
b(ork)363 b(is)f(no)-31 b(v)g(el)363 b(in)f(that)h(it)f(com)-31
b(bines)363 b(language)h(de\014nition)f(and)f(data)h(struc-)9741
51471 y(ture)390 b(de\014nition)h(for)e(ob)61 b(ject-orien)-31
b(ted)393 b(programming)e(in)-31 b(to)391 b(one)f(coheren)-31
b(t)390 b(frame-)9741 52799 y(w)-31 b(ork.)592 b(Suc)-31
b(h)402 b(an)g(in)-31 b(tegration)405 b(has)d(not)h(b)31
b(een)401 b(attempted)j(b)31 b(efore.)591 b(It)402 b(supp)31
b(orts)401 b(a)9741 54127 y(succinct,)370 b(clear,)g(mo)31
b(dular)370 b(programming)i(st)-31 b(yle.)8634 56341
y Fp(\017)554 b Fq(Arti\014cial)461 b(in)-31 b(telligence:)674
b(Man)-31 b(y)460 b(pap)31 b(ers)457 b(in)i(kno)-31 b(wledge)461
b(engineering)f(prop)31 b(ose)458 b(a)9741 57670 y(similar)371
b(approac)-31 b(h)370 b(as)f(Demeter.)493 b(One)369 b(whic)-31
b(h)370 b(comes)f(close)h(is)f([F)-123 b(AS*86)r(].)8634
59883 y Fp(\017)554 b Fq(P)-31 b(arameterized)488 b(data)f(t)-31
b(yp)31 b(es:)727 b(An)486 b(excellen)-31 b(t)488 b(surv)-31
b(ey)485 b(is)h(in)g([CW85)r(].)844 b(Solomon)9741 61212
y(in)-31 b(tro)31 b(duces)338 b(the)g(concept)g(of)g(b)31
b(ounded)337 b(parameterized)h(classes)f([Sol78)s(,)344
b(page)338 b(25].)9741 62540 y(P)-31 b(arameterized)311
b(data)e(t)-31 b(yp)31 b(es)309 b(are)f(pro)-31 b(vided)309
b(in)g(sev)-31 b(eral)309 b(programming)h(languages,)9741
63869 y(including)409 b(CLU)f([LSAS77)r(],)417 b(T)-92
b(rellis/Owl)410 b([SCB*86)r(])e(and)g(Ada.)607 b(P)-31
b(arameteriza-)9741 65197 y(tion)399 b(of)f(data)g(t)-31
b(yp)31 b(e)398 b(sp)31 b(eci\014cations)399 b(is)e(used)g(in)g(the)h
(algebraic)h(approac)-31 b(h)398 b(to)h(data)p eop
%%Page: 31 31
31 30 bop 6974 4317 a Fj(8)1107 b(RELA)-92 b(TED)370
b(W)-31 b(ORK)26013 b Fq(31)9741 8192 y(t)-31 b(yp)31
b(es)531 b([Kre87])g(and)f([TWW82)r(].)976 b([Mac85)q(],)571
b([Mac86)r(])531 b(discusses)d(man)-31 b(y)532 b(of)f(the)9741
9520 y(imp)31 b(ortan)-31 b(t)372 b(issues)c(related)i(to)g(generic)f
(soft)-31 b(w)g(are)371 b(design.)8634 11612 y Fp(\017)554
b Fq(Program)382 b(transformation)i(systems:)515 b(Our)381
b(dev)-31 b(elopmen)g(t)383 b(of)e(Demeter)g(has)f(b)31
b(een)9741 12940 y(motiv)-61 b(ated)249 b(b)-31 b(y)246
b(w)-31 b(ork)247 b(on)g(program)g(transformation)i(systems)d([PS83)q
(],[CI84)s(],)272 b([BM84)q(],)9741 14268 y([KW87)q(].)1012
b(The)542 b(MENTOR)g(system)g([DHK*75)r(],)586 b([DHKL80)q(])542
b(is)g(designed)h(for)9741 15597 y(manipulating)423 b(structured)c
(data)i(represen)-31 b(ted)419 b(b)-31 b(y)420 b(abstract)g(syn)-31
b(tax)421 b(trees.)644 b(The)9741 16925 y(Mj\034lner)352
b(pro)61 b(ject)352 b(uses)f(a)h(Demeter-lik)-31 b(e)352
b(approac)-31 b(h,)357 b(but)351 b(without)j(parameteriza-)9741
18253 y(tion)371 b(and)e(m)-31 b(ultiple)372 b(inheritance)e([MN88)q
(].)8634 20345 y Fp(\017)554 b Fq(Data)374 b(base)f(design:)501
b(Our)372 b(class)i(dictionaries)g(share)f(some)g(prop)31
b(erties)373 b(with)i(data)9741 21673 y(dictionaries.)744
b(The)452 b(data)i(dictionary)g(approac)-31 b(h)453 b(in)f(the)h(data)g
(base)f(\014eld)h(is)f(de-)9741 23002 y(scrib)31 b(ed)349
b(in)h(the)g(surv)-31 b(ey)349 b([ALM82)q(].)487 b(A)350
b(pap)31 b(er)349 b(b)-31 b(y)350 b(John)f(and)h(Diane)g(Smith)h([SS77)
q(])9741 24330 y(outlines)568 b(some)f(of)h(the)f(features)g(of)g(the)g
(Demeter)f(system.)1086 b(Their)567 b(aggrega-)9741 25659
y(tion/generalization)496 b(concepts)491 b(corresp)31
b(ond)491 b(to)g(our)g(construction/alternation)9741
26987 y(concepts.)8634 29079 y Fp(\017)554 b Fq(Program)453
b(enhancemen)-31 b(t:)658 b([Bal86)r(])452 b(prop)31
b(oses)450 b(a)i(frame-based)f(ob)61 b(ject)453 b(mo)31
b(del)452 b(to)9741 30407 y(simplify)286 b(program)f(enhancemen)-31
b(t)286 b(whic)-31 b(h)285 b(has)f(some)g(similarities)j(to)e(the)f
(Demeter)9741 31735 y(system.)8634 33827 y Fp(\017)554
b Fq(Exc)-31 b(hange)524 b(of)f(structured)f(data:)801
b(The)523 b(programming)h(language)h(indep)31 b(enden)-31
b(t)9741 35155 y(data)412 b(structure)e(language)j(of)e(Demeter)f(supp)
31 b(orts)410 b(the)h(exc)-31 b(hange)411 b(of)g(structured)9741
36484 y(data)278 b(b)31 b(et)-31 b(w)g(een)278 b(di\013eren)-31
b(t)276 b(programming)j(languages.)464 b(The)277 b(w)-31
b(ork)277 b(on)g(IDL)e([Lam87)r(])9741 37812 y(is)369
b(related.)8634 39904 y Fp(\017)554 b Fq(Demeter)322
b(Pro)61 b(ject:)470 b([Lie88a)r(])322 b(in)-31 b(tro)31
b(duces)322 b(the)g(formal)h(syn)-31 b(tax)323 b(for)f(parameterized)
9741 41232 y(class)369 b(dictionaries)i(and)f(discusses)e(class)h
(dictionary)i(design)f(tec)-31 b(hniques.)6974 44057
y Fc(Conclusions)1108 b Fq(W)-92 b(e)292 b(ha)-31 b(v)g(e)294
b(presen)-31 b(ted)292 b(a)h(new)g(soft)-31 b(w)g(are)295
b(design)e(metho)31 b(dology)296 b(based)d(on)6974 45385
y(gro)-31 b(wing)286 b(and)f(reusing)f(soft)-31 b(w)g(are.)466
b(W)-92 b(e)283 b(\014nd)h(gro)-31 b(wing)287 b(soft)-31
b(w)g(are)285 b(to)g(b)31 b(e)284 b(a)h(b)31 b(etter)284
b(paradigm)6974 46714 y(than)523 b(building)h(soft)-31
b(w)g(are.)953 b(The)522 b(philosoph)-31 b(y)524 b(of)f(gro)-31
b(wing)524 b(soft)-31 b(w)g(are)524 b(requires)d(that)i(a)6974
48042 y(running)k(system)h(b)31 b(e)527 b(in)h(place)g(from)g(the)f
(earliest)i(stages)f(of)g(pro)61 b(ject)528 b(dev)-31
b(elopmen)g(t.)6974 49370 y(This)464 b(metho)31 b(dology)468
b(has)c(b)31 b(een)463 b(implemen)-31 b(ted)467 b(and)d(tested)h(in)f
(the)h(protot)-31 b(yp)31 b(e)466 b(system)6974 50699
y(\\Demeter")451 b(whic)-31 b(h)451 b(uses)f(this)g(gro)-31
b(wth)452 b(paradigm)g(to)g(pro)-31 b(vide)451 b(an)f(ideal)i(en)-31
b(vironmen)g(t)6974 52027 y(for)369 b(the)h(dev)-31 b(elopmen)g(t)371
b(and)f(reuse)e(of)h(large)h(soft)-31 b(w)g(are)371 b(systems.)8634
53355 y(The)303 b(Demeter)g(system)g(has)f(b)31 b(een)302
b(used)g(b)-31 b(y)303 b(o)-31 b(v)g(er)303 b(200)h(graduate)g(and)f
(undergraduate)6974 54684 y(studen)-31 b(ts)398 b(o)-31
b(v)g(er)399 b(the)f(past)h(18)g(mon)-31 b(ths.)581 b(The)398
b(feedbac)-31 b(k)399 b(from)g(these)f(studen)-31 b(ts)398
b(has)g(b)31 b(een)6974 56012 y(v)-31 b(ery)347 b(fa)-31
b(v)g(orable)349 b(and)f(has)f(indicated)i(that)f(the)g(class)f
(dictionary)i(is)e(a)h(v)-31 b(ery)347 b(natural)h(w)-31
b(a)g(y)6974 57341 y(of)494 b(describing)g(an)g(abstract)h(data)g
(structure.)866 b(In)493 b(addition,)528 b(the)494 b(learning)h(curv)
-31 b(e)494 b(for)6974 58669 y(Demeter)324 b(is)g(short.)478
b(F)-92 b(or)323 b(example,)336 b(a)324 b(group)h(of)g(35)g(CS)f
(sophomore)i(studen)-31 b(ts)324 b(ha)-31 b(v)g(e)325
b(used)6974 59997 y(Demeter)478 b(within)h(the)g(framew)-31
b(ork)479 b(of)g(a)f(soft)-31 b(w)g(are)480 b(design)e(and)g(dev)-31
b(elopmen)g(t)481 b(course.)6974 61326 y(Most)439 b(of)h(the)g(studen)
-31 b(ts)440 b(w)-31 b(ere)439 b(b)31 b(eginning)441
b(w)-31 b(ork)440 b(on)g(fairly)g(complex)h(systems)e(in)h(three)6974
62654 y(w)-31 b(eeks.)728 b(All)448 b(of)g(these)g(studen)-31
b(ts)447 b(had)h(no)g(previous)f(exp)31 b(erience)447
b(with)i(either)f(Demeter)6974 63982 y(or)392 b(ob)61
b(ject-orien)-31 b(ted)395 b(programming,)401 b(ho)-31
b(w)g(ev)g(er,)400 b(they)393 b(did)g(ha)-31 b(v)g(e)394
b(some)e(exp)31 b(erience)393 b(with)6974 65311 y(F)-92
b(ranz)368 b(Lisp)h(\(one)h(course\).)p eop
%%Page: 32 32
32 31 bop 6974 4317 a Fj(REFERENCES)29474 b Fq(32)8634
8192 y(In)375 b(addition)i(to)e(the)g(p)31 b(edagogical)378
b(uses)373 b(of)j(Demeter)e(w)-31 b(e)376 b(ha)-31 b(v)g(e)375
b(implemen)-31 b(ted)378 b(man)-31 b(y)6974 9520 y(applications.)698
b(Some)438 b(of)f(the)g(more)g(in)-31 b(teresting)439
b(ones)d(include)i(all)g(the)f(Demeter)g(co)31 b(de)6974
10848 y(generators)302 b(and)g(the)h(generic)f(programs,)316
b(a)303 b(sim)-31 b(ulator)304 b(for)e(the)g(parallel)i(language)g
(Zeus-)6974 12177 y(2,)350 b(sim)-31 b(ulators)345 b(for)f(subsets)g
(of)g(Sc)-31 b(heme)345 b(and)f(Prolog,)351 b(a)344 b(F)-92
b(ortran-77)345 b(to)g(P)-31 b(ascal)345 b(T)-92 b(ransla-)6974
13505 y(tor,)352 b(a)c(P)-31 b(ascal)348 b(parser)e(generator,)353
b(an)348 b(exp)31 b(ert)346 b(system)i(shell)f(for)h(mo)31
b(delling)349 b(transp)31 b(orta-)6974 14833 y(tion)309
b(systems,)320 b(a)308 b(generic)g(adv)-31 b(en)g(ture)309
b(game)g(generator,)321 b(and)308 b(a)g(protot)-31 b(yp)31
b(e)309 b(en)-31 b(vironmen)g(t)6974 16162 y(for)392
b(the)h(mo)31 b(delling)395 b(and)e(sim)-31 b(ulation)395
b(of)e(arbitrary)g(w)-31 b(orlds)393 b(of)g(ob)61 b(jects)394
b(and)f(rules.)562 b(The)6974 17490 y(latter)405 b(\014v)-31
b(e)404 b(pro)61 b(jects)404 b(w)-31 b(ere)404 b(dev)-31
b(elop)31 b(ed)405 b(b)-31 b(y)404 b(groups)g(of)g(\014v)-31
b(e)404 b(sophomore)g(studen)-31 b(ts)404 b(in)h(an)6974
18818 y(elev)-31 b(en)522 b(w)-31 b(eek)522 b(course.)949
b(This)522 b(time)h(includes)f(the)g(learning)g(curv)-31
b(e)522 b(for)f(Demeter)h(and)6974 20147 y(ob)61 b(ject-orien)-31
b(ted)372 b(programming.)8634 21475 y(W)-92 b(e)463 b(are)h(con)-31
b(tin)g(uing)466 b(our)d(w)-31 b(ork)465 b(with)g(Demeter)e(and)h(the)g
(philosoph)-31 b(y)466 b(of)e(gro)-31 b(wing)6974 22803
y(soft)g(w)g(are)334 b(b)31 b(oth)333 b(for)g(teac)-31
b(hing)334 b(and)f(researc)-31 b(h.)480 b(W)-92 b(e)332
b(will)i(in)-31 b(v)g(estigate)336 b(man)-31 b(y)333
b(exiting)i(areas)6974 24132 y(of)371 b(researc)-31 b(h:)496
b(Ob)61 b(ject-orien)-31 b(ted)373 b(sp)31 b(eci\014cation,)374
b(abstraction)f(b)-31 b(y)371 b(example,)j(class)d(dictio-)6974
25460 y(nary)e(design)h(from)f(examples,)i(exp)31 b(ert)369
b(system)g(for)h(class)f(dictionary)i(design.)6974 28321
y Fc(Ac)-35 b(kno)g(wledgmen)g(ts)1108 b Fq(The)445 b(design)f(and)g
(implemen)-31 b(tation)448 b(of)d(the)f(predecessor)e(sys-)6974
29650 y(tem)498 b(of)g(Demeter)f(\(called)j(GEM,)d(P)-31
b(ascal)499 b(based\))f(w)-31 b(as)498 b(done)g(at)g(GTE)g(Lab)31
b(oratories)6974 30978 y(in)503 b(collab)31 b(oration)506
b(with)e(Andrew)e(Goldb)31 b(erg)503 b(and)g(with)h(managemen)-31
b(t)505 b(supp)31 b(ort)502 b(from)6974 32306 y(Sandy)491
b(Hirsc)-31 b(hhorn)491 b(and)g(Bill)h(Gri\016n.)857
b(A)-31 b(t)492 b(Northeastern,)522 b(the)491 b(Demeter)g(pro)61
b(ject)492 b(is)6974 33635 y(supp)31 b(orted)333 b(b)-31
b(y)333 b(n)-31 b(umerous)334 b(dedicated)g(graduate)h(studen)-31
b(ts,)341 b(including)335 b(\(in)f(alphab)31 b(etical)6974
34963 y(order\):)448 b(Bill)281 b(Bro)-31 b(wn,)298 b(Ian)280
b(Holland,)300 b(Gar-Lin)280 b(Lee,)297 b(Kath)-31 b(y)281
b(Lee,)298 b(Da)-31 b(vid)280 b(Lincoln,)299 b(Beno)-123
b(^)-430 b(\020t)6974 36291 y(Menendez,)369 b(Jing)h(Na,)g(Rob)31
b(ert)369 b(P)-31 b(aul,)371 b(Johannes)e(Sujendro)h(and)f(Carl)h(W)-92
b(o)31 b(olf.)8634 37620 y(Mitc)-31 b(hell)440 b(W)-92
b(and)437 b(taugh)-31 b(t)440 b(us)d(that)j(a)e(parameterized)h(con)-31
b(text-free)439 b(grammar)g(do)31 b(es)6974 38948 y(not)393
b(necessarily)g(de\014ne)f(a)h(con)-31 b(text-free)394
b(language.)565 b(He)392 b(brough)-31 b(t)394 b(the)f(example,)400
b(whic)-31 b(h)6974 40276 y(w)g(e)490 b(called)h Fb(ContextSensitive)h
Fq(in)e(this)g(pap)31 b(er,)520 b(to)491 b(our)e(atten)-31
b(tion.)858 b(This)490 b(example)i(ap-)6974 41605 y(p)31
b(eared)401 b(originally)k(in)d(Mic)-31 b(hael)403 b(Fisc)-31
b(her's)402 b(thesis)g(at)g(MIT.)g(Mitc)-31 b(hell's)404
b(seminar)e(on)g(se-)6974 42933 y(man)-31 b(tics)455
b(of)f(programming)h(languages)h(w)-31 b(as)454 b(v)-31
b(ery)453 b(useful)h(for)f(learning)i(ab)31 b(out)454
b(sev)-31 b(eral)6974 44262 y(k)g(ey)370 b(con)-31 b(tributions)371
b(to)f(the)f(\014eld.)8634 45590 y(Carl)386 b(W)-92 b(o)31
b(olf)385 b(has)f(impro)-31 b(v)g(ed)386 b(the)f(pro)31
b(of)385 b(of)g(theorem)g(5.1.)540 b(He)385 b(prop)31
b(osed)384 b(the)h(termi-)6974 46918 y(nology)371 b(of)f(resp)31
b(onsiv)-31 b(eness)368 b(to)i(a)f(message)h(and)f(kno)-31
b(wledge)372 b(of)d(a)h(message.)8634 48247 y(Professors)468
b(Bro)-31 b(wn,)494 b(Bugrara,)g(Casey)469 b(and)g(Rasala)g(pro)-31
b(vided)469 b(v)-61 b(aluable)470 b(feedbac)-31 b(k)6974
49575 y(on)369 b(this)h(pap)31 b(er.)6974 53220 y Fi(References)6974
55644 y Fq([A)-31 b(CO85])1817 b(A.)436 b(Albano,)455
b(L.)436 b(Cardelli,)455 b(and)436 b(R.)g(Orsini.)690
b(Galileo:)628 b(a)436 b(strongly-t)-31 b(yp)31 b(ed,)12970
56972 y(in)-31 b(teractiv)g(e)465 b(conceptual)e(language.)771
b Fk(A)-28 b(CM)481 b(T)-85 b(r)-57 b(ansactions)482
b(on)g(Datab)-57 b(ase)12970 58301 y(Systems)p Fq(,)370
b(10\(2\):230)j({)c(260,)i(June,)f(1985.)6974 60477 y([ALM82])1739
b(F.)313 b(Allen,)325 b(M.)314 b(Lo)31 b(omis,)325 b(and)313
b(M.)g(Mannino.)401 b(The)313 b(In)-31 b(tegrated)315
b(Dictionary/)12970 61806 y(Directory)369 b(System.)492
b Fk(A)-28 b(CM)396 b(Computing)g(Surveys)p Fq(,)370
b(14\(2\),)i(1982.)6974 63982 y([Bal86])2632 b(R.N.)538
b(Balzer.)995 b(Program)539 b(enhancemen)-31 b(t.)995
b Fk(A)-28 b(CM)550 b(SIGSOFT)h(Softwar)-57 b(e)12970
65311 y(Engine)g(ering)399 b(Notes)p Fq(,)368 b(11\(4\):66,)374
b(1986.)p eop
%%Page: 33 33
33 32 bop 6974 4317 a Fj(REFERENCES)29474 b Fq(33)6974
8192 y([BM84])2477 b(J.M.)410 b(Bo)-31 b(yle)410 b(and)g(M.N.)g
(Muralidharan.)612 b(Program)411 b(reusabilit)-31 b(y)411
b(through)12970 9520 y(program)270 b(transformation.)330
b Fk(IEEE)303 b(T)-85 b(r)-57 b(ansactions)304 b(on)g(Softwar)-57
b(e)304 b(Engine)-57 b(er-)12970 10848 y(ing)p Fq(,)370
b(SE-10\(5\),)j(Septem)-31 b(b)31 b(er)369 b(1984.)6974
13062 y([Bro87])2505 b(F)-92 b(rederic)-31 b(k)333 b(P)-92
b(.)334 b(Bro)31 b(oks.)433 b(No)334 b(silv)-31 b(er)334
b(bullet,)343 b(essence)332 b(and)i(acciden)-31 b(ts)335
b(of)f(soft-)12970 14390 y(w)-31 b(are)370 b(engineering.)492
b Fk(IEEE)396 b(Computer)f(Magazine)p Fq(,)370 b(10{19,)i(April)d
(1987.)6974 16604 y([CI84])3077 b(R.D.)251 b(Cameron)g(and)g(M.R.)g
(Ito.)298 b(Grammar-based)251 b(de\014nition)i(of)e(metapro-)12970
17933 y(gramming)291 b(systems.)359 b Fk(A)-28 b(CM)321
b(T)-85 b(r)-57 b(ansactions)322 b(on)g(Pr)-57 b(o)g(gr)g(amming)324
b(L)-57 b(anguages)12970 19261 y(and)396 b(Systems)p
Fq(,)370 b(6\(1\):20{54,)k(Jan)-31 b(uary)370 b(1984.)6974
21475 y([Co)-31 b(x86])2371 b(Brad)443 b(J.)h(Co)-31
b(x.)715 b Fk(Obje)-57 b(ct-Oriente)g(d)466 b(Pr)-57
b(o)g(gr)g(amming,)484 b(A)-28 b(n)464 b(evolutionary)h(ap-)12970
22803 y(pr)-57 b(o)g(ach)p Fq(.)491 b(Addison)370 b(W)-92
b(esley)g(,)369 b(1986.)6974 25017 y([CW85])2339 b(L.)366
b(Cardelli)i(and)e(P)-92 b(.)367 b(W)-92 b(egner.)485
b(On)366 b(understanding)h(t)-31 b(yp)31 b(es,)367 b(data)g(abstrac-)
12970 26346 y(tion,)358 b(and)353 b(p)31 b(olymorphism.)468
b Fk(A)-28 b(CM)380 b(Computing)i(Surveys)p Fq(,)357
b(17\(4\):471,)k(De-)12970 27674 y(cem)-31 b(b)31 b(er)369
b(1985.)6974 29888 y([DHK*75])1186 b(V.)386 b(Donzeau-Gouge,)k(G.)385
b(Huet,)391 b(G.)385 b(Kahn,)390 b(B.)385 b(Lang,)391
b(and)385 b(J.J.)h(Levy)-92 b(.)539 b(A)12970 31216 y(structure)465
b(orien)-31 b(ted)467 b(program)g(editor:)687 b(a)466
b(\014rst)f(step)h(to)-31 b(w)g(ards)467 b(computer)12970
32545 y(assisted)405 b(programming.)599 b(In)404 b Fk(Pr)-57
b(o)g(c)g(e)g(e)g(dings)431 b(of)e(International)f(Computing)12970
33873 y(Symp)-57 b(osium)397 b(1975)p Fq(,)369 b(page)h(,)f(1975.)6974
36087 y([DHKL80])1047 b(V.)334 b(Donzeau-Gouge,)341 b(G.)334
b(Huet,)341 b(G.)333 b(Kahn,)341 b(and)334 b(B.)g(Lang.)433
b Fk(Pr)-57 b(o)g(gr)g(amming)12970 37415 y(envir)g(onments)490
b(b)-57 b(ase)g(d)489 b(on)g(structur)-57 b(e)g(d)488
b(e)-57 b(ditors:)694 b(The)489 b(MENTOR)f(exp)-57 b(eri-)12970
38744 y(enc)g(e)p Fq(.)493 b(T)-92 b(ec)-31 b(hnical)370
b(Rep)31 b(ort,)370 b(Res.)f(Rep.)g(26)h(INRIA,)f(1980.)6974
40958 y([DMN70])1585 b(O.J.)409 b(Dahl,)420 b(B.)409
b(Myhrhaug,)420 b(and)409 b(K.)g(Nygaard.)612 b(SIMULA)408
b(67)i(Common)12970 42286 y(Base)324 b(Language.)420
b Fk(Publ.)355 b(N.)g(S-22,)364 b(Norwe)-57 b(gian)355
b(Computing)g(Center)p Fq(,)334 b(Oct.)12970 43614 y(1970.)6974
45828 y([F)-123 b(AS*86])1678 b(M.J.)260 b(F)-92 b(reiling,)283
b(J.H.)261 b(Alexander,)283 b(S.J.)261 b(Sh)-31 b(ulman,)284
b(J.L.)260 b(Staley)-92 b(,)284 b(S.)260 b(Rehfuss,)12970
47156 y(and)247 b(S.L.)g(Messic)-31 b(k.)292 b(Kno)-31
b(wledge)249 b(lev)-31 b(el)248 b(engineering:)433 b(on)-31
b(tological)251 b(analysis.)12970 48485 y(In)369 b Fk(Pr)-57
b(o)g(c)g(e)g(e)g(dings)398 b(AAAI)p Fq(,)369 b(pages)g(963{968,)k
(1986.)6974 50699 y([F)-92 b(ra81])2658 b(C.W.)328 b(F)-92
b(raser.)422 b(Syn)-31 b(tax-directed)329 b(editing)g(of)f(general)g
(data)g(structures.)422 b(In)12970 52027 y Fk(Pr)-57
b(o)g(c.)440 b(A)-28 b(CM)438 b(SIGPLAN/SIGO)-28 b(A)439
b(Confer)-57 b(enc)g(e)442 b(on)e(T)-85 b(ext)438 b(Manipulation)p
Fq(,)12970 53355 y(pages)369 b(17{21,)j(P)-31 b(ortland,)372
b(Oregon,)e(1981.)6974 55569 y([GL85])2715 b(A.V.)486
b(Goldb)31 b(erg)486 b(and)f(K.J.)h(Lieb)31 b(erherr.)836
b(GEM:)485 b(A)g(generator)h(of)g(en)-31 b(vi-)12970
56898 y(ronmen)g(ts)518 b(for)f(metaprogramming.)936
b(In)517 b Fk(SOFTF)-113 b(AIR)531 b(II,)i(A)-28 b(CM/IEEE)12970
58226 y(Confer)-57 b(enc)g(e)398 b(on)f(Softwar)-57 b(e)396
b(T)-85 b(o)-57 b(ols)p Fq(,)369 b(pages)g(86{95,)j(San)e(F)-92
b(rancisco,)369 b(1985.)6974 60440 y([GR83])2592 b(A.)412
b(Goldb)31 b(erg)411 b(and)h(D.)f(Robson.)617 b Fk(Smal)57
b(ltalk-80:)586 b(The)435 b(L)-57 b(anguage)436 b(and)f(its)12970
61768 y(Implementation)p Fq(.)492 b(Addison)369 b(W)-92
b(esley)g(,)369 b(1983.)p eop
%%Page: 34 34
34 33 bop 6974 4317 a Fj(REFERENCES)29474 b Fq(34)6974
8192 y([KMMN85])555 b(Ben)-31 b(t)598 b(Bruun)g(Kristensen,)655
b(Ole)598 b(Lehrmann)g(Madsen,)655 b(Birger)598 b(Moller-)12970
9520 y(P)-31 b(ederson,)623 b(and)571 b(Kristen)h(Nygaard.)1096
b(An)571 b(algebra)i(for)f(program)g(frag-)12970 10848
y(men)-31 b(ts.)738 b(In)451 b Fk(A)-28 b(CM)472 b(SIGPLAN)g(85)f(Symp)
-57 b(osium)474 b(on)e(Pr)-57 b(o)g(gr)g(amming)474 b(L)-57
b(an-)12970 12177 y(guages)334 b(and)g(Pr)-57 b(o)g(gr)g(amming)336
b(Envir)-57 b(onments)p Fq(,)317 b(SIGPLAN,)302 b(Seattle,)317
b(W)-92 b(ash-)12970 13505 y(ington,)371 b(1985.)6974
15719 y([Kre87])2489 b(H.J.)421 b(Kreo)-31 b(wski.)644
b(Some)421 b(initial)i(sections)d(of)h(the)f(algebraic)i(sp)31
b(eci\014cation)12970 17047 y(tale.)330 b Fk(Bul)57 b(letin)305
b(of)g(the)f(Eur)-57 b(op)g(e)g(an)306 b(Asso)-57 b(ciation)304
b(for)h(The)-57 b(or)g(etic)g(al)305 b(Computer)12970
18376 y(Scienc)-57 b(e)p Fq(,)372 b(\(31\):55{78,)i(F)-92
b(ebruary)368 b(1987.)6974 20589 y([KW87])2277 b(E.)463
b(Kohlb)31 b(ec)-31 b(k)g(er)464 b(and)f(Mitc)-31 b(hell)465
b(W)-92 b(and.)770 b(Macro)463 b(b)-31 b(y)463 b(example.)772
b(In)463 b Fk(A)-28 b(CM)12970 21918 y(Symp)-57 b(osium)392
b(on)e(Principles)h(of)f(Pr)-57 b(o)g(gr)g(amming)392
b(L)-57 b(anguages)p Fq(,)366 b(A)-31 b(CM,)364 b(1987.)6974
24132 y([Lam87])2109 b(D.A.)543 b(Lam)-31 b(b.)1007 b(IDL:)542
b(Sharing)g(In)-31 b(termediate)544 b(Represen)-31 b(tations.)1008
b Fk(A)-28 b(CM)12970 25460 y(T)-85 b(r)-57 b(ansactions)502
b(on)g(Pr)-57 b(o)g(gr)g(amming)505 b(L)-57 b(anguages)503
b(and)f(Systems)p Fq(,)514 b(9\(3\):297{)12970 26788
y(318,)371 b(July)e(1987.)6974 29002 y([LHR88])1939 b(Karl)254
b(J.)g(Lieb)31 b(erherr,)276 b(Ian)253 b(Holland,)279
b(and)254 b(Arth)-31 b(ur)254 b(J.)g(Riel.)304 b(Ob)61
b(ject-orien)-31 b(ted)12970 30331 y(programming:)508
b(an)376 b(ob)61 b(jectiv)-31 b(e)378 b(sense)c(of)j(st)-31
b(yle.)511 b(In)376 b Fk(Obje)-57 b(ct-Oriente)g(d)403
b(Pr)-57 b(o-)12970 31659 y(gr)g(amming)519 b(Systems,)550
b(L)-57 b(anguages)518 b(and)g(Applic)-57 b(ations)518
b(Confer)-57 b(enc)g(e)p Fq(,)538 b(San)12970 32987 y(Diego,)340
b(CA.,)g(Septem)-31 b(b)31 b(er)331 b(1988.)430 b(A)331
b(short)g(v)-31 b(ersion)331 b(of)h(this)f(pap)31 b(er)330
b(app)31 b(ears)12970 34316 y(in)369 b(IEEE)h(Computer,)h(June)e(88,)h
(Op)31 b(en)369 b(Channel)h(section,)h(pages)e(78-79.)6974
36530 y([Lie88a])2232 b(Karl)479 b(Lieb)31 b(erherr.)816
b(Ob)61 b(ject-orien)-31 b(ted)481 b(programming)g(with)f(class)f
(dictio-)12970 37858 y(naries.)464 b Fk(Journal)381 b(on)g(Lisp)g(and)g
(Symb)-57 b(olic)383 b(Computation)p Fq(,)356 b(1\(2\):pages)f(un-)
12970 39186 y(kno)-31 b(wn,)371 b(1988.)6974 41400 y([Lie88b])2170
b(Karl)601 b(J.)g(Lieb)31 b(erherr.)1181 b Fk(The)609
b(A)-28 b(rt)609 b(of)g(Gr)-57 b(owing)610 b(Softwar)-57
b(e:)937 b(A)-28 b(n)609 b(obje)-57 b(ct-)12970 42729
y(oriente)g(d)581 b(CASE)g(appr)-57 b(o)g(ach)p Fq(.)1088
b(publisher)569 b(to)i(b)31 b(e)569 b(determined,)621
b(Jan)-31 b(uary)12970 44057 y(1988.)493 b(b)31 b(o)g(ok)370
b(in)f(preparation,)i(appro)-31 b(ximately)373 b(400)d(pages.)6974
46271 y([LR88])2769 b(Karl)472 b(J.)f(Lieb)31 b(erherr)470
b(and)i(Arth)-31 b(ur)471 b(J.)g(Riel.)797 b(Demeter:)697
b(a)472 b(CASE)g(study)12970 47599 y(of)346 b(soft)-31
b(w)g(are)346 b(gro)-31 b(wth)347 b(through)f(parameterized)g(classes.)
452 b(In)345 b Fk(International)12970 48928 y(Confer)-57
b(enc)g(e)460 b(on)d(Softwar)-57 b(e)458 b(Engine)-57
b(ering)p Fq(,)455 b(pages)437 b(254{264,)456 b(Ra\017es)436
b(Cit)-31 b(y)-92 b(,)12970 50256 y(Singap)31 b(ore,)371
b(1988.)6974 52470 y([LSAS77])1524 b(B.)418 b(Lisk)-31
b(o)g(v,)432 b(A.)419 b(Sn)-31 b(yder,)430 b(R.)419 b(A)-31
b(tkinson,)432 b(and)418 b(C.)h(Sc)-31 b(ha\013ert.)637
b(Abstraction)12970 53798 y(mec)-31 b(hanisms)338 b(in)e(CLU.)439
b Fk(Communic)-57 b(ations)367 b(of)g(the)e(A)-28 b(CM)p
Fq(,)336 b(20\(8\):564{576,)12970 55127 y(August)370
b(1977.)6974 57341 y([Mac85])2216 b(D.)379 b(MacQueen.)521
b(Mo)31 b(dules)379 b(for)g(standard)h(ML.)520 b Fk(Polymorphism)405
b(Newslet-)12970 58669 y(ter)p Fq(,)369 b(2\(2\),)i(Octob)31
b(er)370 b(1985.)6974 60883 y([Mac86])2216 b(D.)259 b(MacQueen.)312
b(Using)260 b(dep)31 b(enden)-31 b(t)259 b(t)-31 b(yp)31
b(es)260 b(to)g(express)e(mo)31 b(dular)260 b(structure.)12970
62211 y(In)274 b Fk(A)-28 b(CM)308 b(Symp)-57 b(osium)310
b(on)f(Principles)g(of)g(Pr)-57 b(o)g(gr)g(amming)311
b(L)-57 b(anguages)p Fq(,)295 b(Jan-)12970 63540 y(uary)369
b(1986.)p eop
%%Page: 35 35
35 34 bop 6974 4317 a Fj(REFERENCES)29474 b Fq(35)6974
8192 y([MBW80])1339 b(J.)511 b(Mylop)31 b(oulos,)549
b(P)-92 b(.)512 b(A.)g(Bernstein,)547 b(and)511 b(H.K.T.)i(W)-92
b(ong.)915 b(A)512 b(language)12970 9520 y(facilit)-31
b(y)395 b(for)e(designing)g(in)-31 b(teractiv)g(e)395
b(database)f(in)-31 b(tensiv)g(e)393 b(systems.)561 b
Fk(A)-28 b(CM)12970 10848 y(T)-85 b(r)-57 b(ansactions)396
b(on)g(Datab)-57 b(ase)396 b(Systems)p Fq(,)369 b(5\(2\):185)k({)d
(207,)h(June,)e(1980.)6974 13062 y([Mey86])2185 b(B.)683
b(Mey)-31 b(er.)1425 b(Genericit)-31 b(y)683 b(v)-31
b(ersus)682 b(inheritance.)1426 b(In)682 b Fk(Obje)-57
b(ct-Oriente)g(d)12970 14390 y(Pr)g(o)g(gr)g(amming)643
b(Systems,)703 b(L)-57 b(anguages)643 b(and)e(Applic)-57
b(ations)641 b(Confer)-57 b(enc)g(e)p Fq(,)12970 15719
y(pages)369 b(391{405,)k(1986.)6974 17933 y([Mil71])2647
b(H.D.)299 b(Mills.)376 b(T)-92 b(op-do)-31 b(wn)299
b(programming)i(in)d(large)h(systems.)375 b(In)298 b(R.)g(Ruskin,)12970
19261 y(editor,)284 b Fk(Debugging)298 b(T)-85 b(e)-57
b(chniques)298 b(in)f(L)-57 b(ar)g(ge)298 b(Systems)p
Fq(,)283 b(Pren)-31 b(tice)262 b(Hall,)285 b(1971.)6974
21475 y([MN88])2431 b(Ole)495 b(Lehrmann)g(Madsen)g(and)g(Claus)h
(N\034rgaard.)867 b(An)495 b(ob)61 b(ject-orien)-31 b(ted)12970
22803 y(metaprogramming)509 b(system.)897 b(In)505 b
Fk(Pr)-57 b(o)g(c)g(e)g(e)g(dings)524 b(of)d(the)g(A)-28
b(nnual)521 b(Hawaii)12970 24132 y(International)335
b(Confer)-57 b(enc)g(e)338 b(on)d(System)h(Scienc)-57
b(es)p Fq(,)318 b(pages)304 b(406{415,)320 b(1988.)6974
26346 y([Mo)31 b(o86])2124 b(Da)-31 b(vid)443 b(A.)f(Mo)31
b(on.)709 b(Ob)61 b(ject-Orien)-31 b(ted)444 b(Programming)h(with)e
(Fla)-31 b(v)g(ors.)709 b(In)12970 27674 y Fk(Obje)-57
b(ct-Oriente)g(d)642 b(Pr)-57 b(o)g(gr)g(amming)642 b(Systems,)703
b(L)-57 b(anguages)641 b(and)g(Applic)-57 b(a-)12970
29002 y(tions)396 b(Confer)-57 b(enc)g(e)p Fq(,)372 b(pages)d(1{8,)i(P)
-31 b(ortland,)372 b(Oregon,)e(1986.)6974 31216 y([PS83])2908
b(H.)273 b(P)-31 b(artsc)g(h)273 b(and)f(R.)g(Stein)-31
b(brueggen.)335 b(Program)274 b(transformation)g(systems.)12970
32545 y Fk(A)-28 b(CM)395 b(Computing)i(Surveys)p Fq(,)370
b(15\(3\):199{236,)376 b(Septem)-31 b(b)31 b(er)369 b(1983.)6974
34759 y([SCB*86])1525 b(Craig)539 b(Sc)-31 b(ha\013ert,)580
b(T)-92 b(opher)538 b(Co)31 b(op)g(er,)580 b(Bruce)537
b(Bullis,)582 b(Mik)-31 b(e)538 b(Kilian,)582 b(and)12970
36087 y(Carrie)312 b(Wilp)31 b(olt.)398 b(An)312 b(in)-31
b(tro)31 b(duction)313 b(to)f(T)-92 b(rellis/Owl.)400
b(In)310 b Fk(Obje)-57 b(ct-Oriente)g(d)12970 37415 y(Pr)g(o)g(gr)g
(amming)643 b(Systems,)703 b(L)-57 b(anguages)643 b(and)e(Applic)-57
b(ations)641 b(Confer)-57 b(enc)g(e)p Fq(,)12970 38744
y(pages)369 b(9{16,)j(1986.)6974 40958 y([Sol78])2801
b(M.)467 b(Solomon.)785 b(T)-31 b(yp)31 b(e)468 b(de\014nitions)g(with)
g(parameters.)784 b(In)466 b Fk(Principles)487 b(of)12970
42286 y(Pr)-57 b(o)g(gr)g(amming)398 b(L)-57 b(anguages)p
Fq(,)370 b(T)-92 b(ucson,)370 b(Arizona,)h(1978.)6974
44500 y([SS77])3046 b(J.M.)302 b(Smith)h(and)g(D.C.P)-92
b(.)303 b(Smith.)383 b(Data)303 b(base)f(abstractions:)461
b(aggregation)12970 45828 y(and)354 b(generalization.)469
b Fk(A)-28 b(CM)381 b(T)-85 b(r)-57 b(ansactions)382
b(on)g(Datab)-57 b(ase)381 b(Systems)p Fq(,)358 b(2\(2\),)12970
47156 y(June)369 b(1977.)6974 49370 y([Str86])2797 b(B.)313
b(Stroustrup.)400 b Fk(The)344 b(C++)g(Pr)-57 b(o)g(gr)g(amming)346
b(L)-57 b(anguage)p Fq(.)401 b(Addison)314 b(W)-92 b(esley)g(,)12970
50699 y(1986.)6974 52913 y([T)g(ei84])2770 b(T.)522 b(Reps)e(T.)i(T)-92
b(eitelbaum.)947 b(The)522 b(syn)-31 b(thesizer)521 b(generator.)945
b Fk(SIGPLAN)p Fq(,)12970 54241 y(19\(5\),)372 b(1984.)6974
56455 y([Tho86])2309 b(K.)355 b(S.)g(Thomsen.)469 b Fk(Multiple)382
b(Inheritanc)-57 b(e,)387 b(a)c(structuring)g(me)-57
b(chanism)384 b(for)12970 57783 y(data,)373 b(pr)-57
b(o)g(c)g(esses)367 b(and)g(pr)-57 b(o)g(c)g(e)g(dur)g(es)p
Fq(.)442 b(T)-92 b(ec)-31 b(hnical)340 b(Rep)31 b(ort)338
b(D)-31 b(AIMI)337 b(PB)h(-)g(209,)12970 59112 y(Univ)-31
b(ersit)g(y)371 b(of)e(Aarh)-31 b(us,)370 b(Denmark,)g(April)f(1986.)
6974 61326 y([TWW82])1201 b(J.W.)388 b(Thatc)-31 b(her,)393
b(E.G.)388 b(W)-92 b(agner,)392 b(and)c(J.B.)g(W)-92
b(righ)-31 b(t.)546 b(Data)388 b(t)-31 b(yp)31 b(e)388
b(sp)31 b(eci\014-)12970 62654 y(cation:)469 b(parameterization)322
b(and)c(the)h(p)31 b(o)-31 b(w)g(er)319 b(of)g(sp)31
b(eci\014cation)321 b(tec)-31 b(hniques.)12970 63982
y Fk(A)j(CM)391 b(T)-85 b(r)-57 b(ansactions)393 b(on)g(Pr)-57
b(o)g(gr)g(amming)394 b(L)-57 b(anguages)393 b(and)f(Systems)p
Fq(,)367 b(711{)12970 65311 y(732,)k(1982.)p eop
%%Page: 36 36
36 35 bop 6974 4317 a Fj(REFERENCES)29474 b Fq(36)6974
8192 y([Wil83])2524 b(D.)306 b(Wile.)389 b(Program)307
b(dev)-31 b(elopmen)g(ts:)463 b(formal)307 b(explanations)i(of)d
(implemen-)12970 9520 y(tations.)493 b Fk(Communic)-57
b(ations)398 b(of)e(the)g(A)-28 b(CM)p Fq(,)369 b(26\(11\),)j(1983.)
6974 11734 y([Wir71])2397 b(Niklaus)457 b(Wirth.)748
b(The)456 b(Programming)i(Language)f(P)-31 b(ascal.)750
b Fk(A)-57 b(cta)476 b(Infor-)12970 13062 y(matic)-57
b(a)p Fq(,)370 b(1:35{63,)j(1971.)6974 15276 y([Wir74])2397
b(Niklaus)342 b(Wirth.)445 b(On)340 b(the)h(design)g(of)g(programming)i
(languages.)446 b(In)340 b Fk(IFIP,)12970 16604 y(A)-28
b(mster)-57 b(dam)p Fq(,)369 b(pages)g(386{393,)k(North-Holland,)f
(1974.)6974 18818 y([Wir76])2397 b(Niklaus)259 b(Wirth.)310
b Fk(A)-28 b(lgorithms)293 b(+)h(Data)e(Structur)-57
b(es)294 b(=)g(Pr)-57 b(o)g(gr)g(ams)p Fq(.)310 b(Pren)-31
b(tice)12970 20147 y(Hall,)371 b(Englew)-31 b(o)31 b(o)g(d)371
b(Cli\013s,)g(N.)e(J.,)h(1976.)6974 22361 y([Wir77])2397
b(N.)542 b(Wirth.)1005 b(What)542 b(can)g(w)-31 b(e)542
b(do)f(ab)31 b(out)543 b(the)f(unnecessary)e(div)-31
b(ersit)g(y)543 b(of)12970 23689 y(notation)427 b(for)d(syn)-31
b(tactic)426 b(de\014nitions?)889 b Fk(Comm.)447 b(A)-28
b(CM)p Fq(,)424 b(20\(11\):822{823,)12970 25017 y(1977.)6974
27231 y([Wir84])2397 b(Niklaus)370 b(Wirth.)492 b Fk(Pr)-57
b(o)g(gr)g(amming)398 b(in)f(Mo)-57 b(dula-2)p Fq(.)490
b(Springer)369 b(V)-92 b(erlag,)370 b(1984.)p eop
%%Trailer
end 
end