Anne Frank, a 13-year-old, strong-willed, and courageous girl, is living in the Secret Annex during WW Ⅱto escape the Nazi regime. Anne, along with her family and close friends, are hiding from the Nazis because they are of the Jewish faith. Anne falls in love with Peter, a 15 year-old boy who is living with her in the Secret Annex. They become very close as they spend time in the attic trying to escape Peter's annoying mother. The group living in the Secret Annex has to be extremely careful. If they make too much noise, they have a chance of being caught. If they are caught, they will most likely be sent to a concentration camp. Any loud noise or movement could cost the eight tenants of the Secret Annex to die.

"Anne Frank: The Diary of a Young Girl" is an amazing book. It lets you realize how lucky we are to live in the world we live in today. The struggles that Anne and the group go through to live a "normal" life are nothing like anyone in today's world would be forced to go through. It allows people interested in WW Ⅱ to gain information as to what it was like to live during the war.

"Anne Frank: The Diary of a Young Girl" is a must read. It is very informative, yet allows the reader to learn about WW Ⅱ in an interesting way. So, if you like WW Ⅱ and are interested in learning what it was like to live back then, this book is for you. It is also a good

piece of historical fiction. Pick it up today!

第二篇：The Book Review Column

TheBookReviewColumn1

byWilliamGasarch

DepartmentofComputerScience

UniversityofMarylandatCollegePark

CollegePark,MD,20742

email:gasarch@cs.umd.edu

WelcometotheBookReviewsColumn.Wehopetobringyouatleasttworeviewsofbookseverymonth.Inthiscolumnfourbooksarereviewed.

1.StableMarriageanditsRelationtoOtherCombinatorialProblems:AnIntro-ductiontoAlgorithmAnalysisbyDonaldKnuth.ReviewedbyTimMcNichol.Thisbookusesthestablemarriageproblemasmotivationtolookatsomemathematicsofinter-est.Itwouldbeusefulforundergrads;however,foraseriousstudyofmatchingtherearemoreadvancedandmoreup-to-datebooksavailable.

2.TheLimitsofMathematicsbyGregoryJ.Chaitin.ReviewedbyVladimirTasic.ThisbookisonalgorithmicinformationtheoryandrandomnessastheyrelatetoBerry’sParadox(“theshortestnumberthatrequireslessthan1000characterstodescribeit”hasjustbeendescribedbythatphraseinquotes,yetthatphrasewaslessthan1000characters.)

3.PrivacyontheLinebyWhit?eldDi?eandSusanLandau.ReviewedbyJosephMakle-vitch.Thisbookisaboutthebalancebetweenthecitizen’sneedforprivacyandthegovern-ment’sneedtointrudetopreventorsolvecrimes.Theseissuesarerelevantnowbecauseofcrytographyandcomputers.Theauthorsarerespectedtheoristswhohaveworkedincryptog-raphy,hencetheircommentsareworthyconsidering.Thisbookhascausedsomecontroversyinthemathcommunity—seetheJune-July1998issueofNoticesoftheAMS,alsoavailableat/notices.Or,betteryet,readthebook!

4.ATheoryofObjectsbyAuthors:Mart??nAbadiandLucaCardelli.ReviewedbyBrianPostow.Thisbookisaboutformalizingthesemanticsofobject-orientedlanguages.Todothis,anewcalculusisintroduced.

Reviewof

StableMarriageanditsRelationtoOtherCombinatorialProblems:

AnIntroductiontoAlgorithmAnalysis2

Author:DonaldE.Knuth

PublishedbyAmericanMathematicalSocietyin1996

$19.00,Softcover

ISBNnumber0-821-80603-3

Reviewer:TimothyH.McNicholl

1Overview

ThisbookisatranslationoftherevisedandcorrectededitionofMarriagesstablesetleursrelationsavecd’autresprobl`emescombinatoriespublishedin1976byLesPressesdel’Universit?edeMontr?eal.ItisbasedonaseriesoflecturesgivenbytheauthorattheCentrederecherchesmathematicques.

Thepurposeofthebookistogiveaninformalintroductiontoalgorithmanalysisinwhichthemainideasareintroducedbyexampleratherthanbytheorems.

Thechiefexampleusedisthestablemarriageproblemwhichcanbede?nedasfollows.A?nitesetof‘men’isgivenalongwithasetof‘women’ofthesamecardinality.Inaddition,eachpersonisassumedtohavearankingofthemembersoftheoppositesex.Amatchingisabijectionbetweenthetwosets.Wethinkofamatchingasasetofnmonogamousmarriages.AnunstablematchingisoneinwhichthereisamanXandawomanYsuchthatXranksYhigherthanhisspouseandYranksXhigherthanherspouse.Themethodsusedto?ndthemeannumberofstepsrequiredbythisalgorithmarethenappliedtoanalgorthmto?ndtheshortestdistancesbetweenanodeandalltheothernodesinagraph.Analgorithmforstoringinformationinatablebyhashingisthenconsideredandtheresultsobtainedareusedtodevelopalowerboundonthismeaninthecasewherethewomenallhavethesamerankingofthemen.Theasymptoticvalueofthismeanasafunctionofthenumberofmenisthenobtainedusingaprobabalisticmethod.

2SummaryofContents

Thematerialispresentedinseven‘lectures’.The?rstofthesede?nesthestablemarriageprobleminasuitablyinformalstyle(nomentionismadeoflinearordersandthelike;rather,rankingsarepresentedviamatrices).Examplesaregiventoillustratestableandunstablematchingsaswellastodemonstratethatmany‘societies’haveseveralstablematchings.Thisraisestheissuesastowhethersomestablematchingsarebetterthanothersandwhetherthereexistsan‘optimal’stablematching.Theseissuesareaddressedintheproblemsetforthischapterviathefollowingprovocativeexercise:showthatthematchingobtainedbymarryingeachmantothehighestrankedofallbrideshecanobtaininsomestablematchingisastablematching.Thismatching,whichis‘male-optimal’byde?nition,turnsouttobe‘female-minimal’inthesensethatnowomancandoanyworsethanshedoesinthismatching.

Lecture2presentsanalgorithmforobtainingastablematching.Althoughthisterminologyisnotusedinthetext,thealgorithmcouldbecalledthe‘courtshipalgorithm’sinceitmimicshowmarriagesareformedinmanysocieties.Thealgorithmismercilesslypresentedinpseudo-ALGOL,butitsoperationcanbesummarizedasfollows.Eachmancontinuestomakemarriageproposalsuntilhebecomespermanentlyengaged.Onlyonemanisallowedtomakeproposalsatanypointintime,andwheneveramanmakesaproposal,hedoessotothewomanherankshighestoutofallthosewhohavenotpreviouslyrejectedor‘dumped’him.Awomanrejectsaproposalonlyifsheisalreadyengagedtoamanshelikesbetterthanthesuitor;otherwiseshedumpshercurrent?anceinordertoaccepttheproposal.Itisshownthatthealgorithmeventuallyterminatesandthatwhenitdoesthematchingobtainedisstable.Furthermore,itisshownthatthematchingobtainedisthemale-optimalmatchingdiscussedintheexercisesforlecture1.Anexampleislaborouslyworkedthorughinordertoillustratetheoperationofthealgorithm.Moreinsightintothealgorithm’smachinationscouldhavebeenconveyedifaninformalpresentationofthemainideasinvolvedhadpreceededthepseudo-code.

Thenumberofpropsosalsmadeduringthecourseofthealgorithmprovidesagoodestimateofthenumberofstepsneededbythealgorithm,andtheformerquantityisanalyzedinlecture3.Itisshownthatthemeannumberofproposalsmadewhentherearenmenandnwomenandthepreferencematrixofthewomenis?xedisnomorethan(n?1)Hn+1whereHnisthesumofthe?rstntermsoftheharmonicseries.Onlyanupperboundisobtainedsincetheproblemissimpli?edbyassumingthatthemenhave‘partialamnesia’.Namely,whenvertheymakeaproposal,theycanonlyrememberthelastwomanwhohasdumpedorrejectedthemwhenevertheyaremaking

2

aproposal.Asaresulteachmanpossiblymakessomeredundantproposalsandhenceandupperboundisobtained.Theassumptionofpartialamnesiaallowstheproblemtobealmostcompletelyreducedtothatofdeterminingtheprobabilitythatacouponcollectorwhoalreadypossesesmofncouponsnextobtainsacouponalreadyinhercollection.

Inthefourthlecture,thesetechniquesareappliedtoDijkstra’salgorithmfor?ndingtheshortestdistancesfromanodeinagraphtoeachoftheothernodesinthegraph.Theapplicationismadeviaananalogybetweenthenodesinthegraphandthewomeninthemarriagealgorithm.Thelogicisglossedover,butitisdemonstratedthatthemeannumberofstepsinDijkstra’salgorithmisnomorethanthemeannumberofproposalsinthemarriagealgorithm.

The?fthlectureconsidersthesearchingofatableviahashing.Itisshowninastraightforwardmannerthatwhentherearemitemsinatablewithnstorageblocks,thenthemeannumberofstepsrequiredtoplacethenextitemis

n+1

Reviewof

TheLimitsofMathematics3

Author:G.J.Chaitin

PublishedbySpringerVerlagin1998

Hardcover,$32.00

160pages

ISBN981-308-359X

Reviewby

VladimirTasic

UniversityofNewBrunswick

vlad@conway.math.unb.ca

Ifyou?ndpleasureinbeingba?edbytheausterityoflogicistincompletenessproofsbasedonBerry’sparadox,thisisnotabookforyou;Boolos’sminimalistgem(whichappearedinthe“NoticesoftheA.M.S.”afewyearsago)isyournaturalchoice.If,ontheotherhand,youactuallywanttolearnsomethingabouttherelationshipbetweenBerry’sparadox,randomnessandincomplete-nesspheno-mena,Irecommend“TheLimitsofMathematics”.Chaitinhasinvestedconsiderableenergyintoexplaininghiswayofthinkingaboutthetopic,fromthepointofviewofalgorithmicinformationtheory.Thisbookisprimarilyconcernedwiththe“why”andthe“how”oflimitativeresults.Theideasarecarefullymotivated,revisitedandreinforcedthroughout,emphasizingintuitiveunderstandingratherthanadrylyformal“theorem-proof”approach.Theresultisabookthatleavesthereaderwiththefeelingofhavingwitnessedoneofthoserareevents:agoodlecture.“TheLimitsofMathematics”isnotintendedtobebed-timereading.Itrequiresactiveparticipationofthereader,whoischallengedtosupplythedetailsandinvitedtotryoutthesoftwarethatcomesalongwiththiscourse.Admittedly,the?ftypagesofcodeattheendofthebookmightappearslightlyintimidatingtothoseofuswhoquitprogramminguponencounteringCOBOL.However,thepresentationofalgorithmicinformationtheoryintermsofanexplicitcomplexitymeasurebasedonamodi?edversionofLISPisoneofthekeyfeaturesofthebook.Inadditiontomakingpossiblethehands-onapproachwhichtheauthorsuggests,dealingwithasuitablychosenLISPdialectallowsChaitintoestablishexplicitlysomeoftheconstantsthatoccurincomplexityestimates.Forexample,itisderivedthatthecomplexity(inChaitin’ssense)ofthebit-stringconsistingofthe?rstNbitsofthehaltingprobabilitymustbegreaterthanN?8000.Variousotherresultsaremadeexplicit,includingtheboundonthecomplexityofthetheoremsofaformalaxiomaticsystem.Thisincompletenesstheoremisusedtomakethecasefora“quasi-empirical”philosophyofmathematicsandtheuseofcomputersastoolsformathematicalexperimentation.Iamnotaspecialistonalgorithmicinformationtheory;havingreadthisbook,IfeelIunderstandsomethingaboutthis?eld.

Reviewof

PrivacyontheLine4

Author:Whit?eldDi?eandSusanLandau

PublishedbyMITPress1998

Hardcover,$25.00

360pages

ISBN0-262-04167-7

Reviewby

JosephMaklevitch

YorkCollege(CUNY)

joeyc@cunyvm.cuny.edu

InhisbookAMathematician’sApology,thepaci?stG.H.Hardyattemptedtotakecomfortfromthefactthatnumbertheory,hisareaofspecialty,mightneverbeputtoanyuse,especiallyusethatHardywouldnothaveapprovedof.Hardywasnaive.StanislasUlam,the”pure”mathematicianturnedphysicist,iscreditedwithbeingtheco-inventerofthehydrogenbomb-adubioushonor.Yetthepaththatideaswillleadto,eventhoseinitiallydevelopedforreasonsofunlikelyvaluetomankind,aredi?culttochart.WhatisperhapsclosertothetruththanHardy’shopeisathoughtofthetopologistLeoZippin:ifsomemathematicianiscleverenoughto?ndwhatseemstobehopelesslyabstractresults,someothermathematicianwillbecleverenoughto?ndausefortheresults.Manytheoristsinmathematicsandcomputersciencetodayliveinaworldmorede?nedbythepotentialofbigdollarsignsthanthattheirworkmaysitadmiredmerelyforits”beautyandelegance”inascholarlyjournal.Today,theoreticiansmaybereluctanttopublishsomeoftheir”beautiful”workinascholarlyjournaltoosoon,lestthisactionserveasanimpedimenttotheuseoftheideaaspartofapatentapplication.Softwarepatentsandotheremergingtrendsinintellectualpropertylawarebecomingpartoftheivorytowerworld.Hardy,Isuspect,wouldnothaveapproved.

Althoughtheissueofthegoodandevilthatcanbeaconsequenceofone’sworkinmathematicsorcomputerscienceisnotexplicitinthenewbookPrivacyontheLinebyWhit?eldDi?eandSusanLandau,itmightwellbe.Researchershavedevelopedawidevarietyofmathematicalandcomputersciencetoolswhich,whenusedinconjunctionwithotherdevelopmentsinphysicsandengineering,arerelatedtoawidearrayofnewdigitaltechnologies.Thesenewtechnologies,suchasbarcodes,fax,emailandvoicemail,awidearrayofnewkindsofpagers,wirelesstelephony,ATMmachines,digitaltelevision,theWorldWideWeb,etc.,arechangingthewaypeopleallovertheworldleadtheirlivesanddobusiness.Althoughtheydonotalwaysrequirecodesfortheirfunctioning,codesareinmanywaysdirectlyrelatedtothesenewtechnologiesbecausecodescanbeusedinawidevarietyofinformationsettings.Theycanbeusedtotrack,correct,compress,hide,andsynchronizedata,tonamebutafewofthemorevisiblepurposesthatcodesareputto.Di?eandLandau’sbookzoomsinonarelativelynarrowpartoftheinformationrevolutionbut,nonetheless,apartofitthata?ectsallpeople.Di?eandLandauzeroinonprivacy.

Concernwithprivacyisveryancient.Fromoneperspective,toachieveprivacyistohideinformationthatyoudonotwantotherstohave.Theneedforkeepingsecretsinthea?airsofstateandthemilitaryareclear.Furthermore,thereisalongtraditionofusingcodesandothertechnicaldevices(e.g.secretwriting)toachievethissecrecy.JuliusCaesarisoftencreditedwithagreatleapforwardinthesystematicattempttohideinformationusingcodes.Hedevisedtheidea

thataplaintextcouldbedisguisedbyreplacingeachletterofthealphabetwiththeletterofthealphabetobtainedbyshiftingthethealphabeta?xednumberofpositionsandcyclinglettersatthebeginningaroundtotheend(orviceversa).Thegoalevenduringearlye?ortsincryptographywasthedevelopmentofeasy-to-useandimpossible-to-breakcodes.(Intechnicalparlancethereisadi?erencebetweencodesandciphers,buthereIwillusethetermcodesinagenericfashion.)

FromCaesar’searlybreakthrough,progresshasaccelerated.BythetimeWorldWarIIoc-curredmostcountrieshadsophisticatedgovernmentagenciesinvolvedinthedesignandattempttodeciphercodes.Goingintothewarthegeneralpublicactuallyhadtheimpressionthatbyusingingeniousmechanicalmachines,thatmilitaryoperationsandgovernmentoperationscouldbecar-riedoutwithoutrevealinginformationtothepryingeyesofothercountries.However,revelationsmadeafterthewarexplodedthatmyth.ItwaslearnedthatBritishandAmericancryptographershadchangedthecourseofthewarandhistorybyusingmathematicsandemergingcomputationaltechniquestobreaktheGermanandJapanesecodes.Thesigni?canceofthefactthatEnglandwasreadingGermancodeswasofsuchimportanceandvalue,thatsomehaveclaimedthatChurchillchosenottoalerto?cialsinCoventryofanimpendingGermanattack(whichresultedinhorri?clossoflifeandproperty)ratherthanriskthattheGermanswoulddeducethattheircodeswerecompromisedifCoventrydisplayedpreparationforthewell-guardedattackplans.(Britishgovern-mento?cialsdenythatChurchilldidthis,givinganexplanationofwhyBritishauthoritiesdidnotknowoftheCoventryattackplans.However,wouldauthoritieseventodayadmitthetruereasonsifthedecisioninvolvedtradingthelivesofinnocentpeoplefora”higher”good?)

Thesetriumphsofhumaningenuityraisedthepossibilitythattherewasnosuchthingasanunbreakablecryptologicalsystem.Thisisnottechnicallytrue.Thereistheone-timepad,asystemwhichusestwocopiesofarandomlygeneratedkeytoguaranteesecurity.Theproblemwiththeone-timepadisthatitrequiresahighoverheadtoimplement.Thus,eventhoughduringthecoldwartheSovietUnionusedone-timepads,theUnitedStateswasabletotakeadvantageofthesloppyimplementationused.

Untilafewyearsagocryptology,thescienceofconstructingandbreakingcodes,waslargelywithintherealmofagenciesofgovernmentsconcernedwithnationalsecurity.IntheUnitedStatesthisagencyistheNationalSecurityAgency(NSA),anorganizationwhichuntilveryrecentlyworkedinwaysandatcoststhatwerelargelyunscrutinized,certainlybythepublicatlargeandevenbyotherpartsofthegovernment.WhileinrecentyearsNSAwasknownforhiringlargenumbersofcomputerscientists,mathematicians,andlanguagespecialists,itdidnothavetoomuchinterfacewithotherpartsofnationallife.Thiswastochangeinpartduetoaremarkabletheoreticalbreakthroughinvolvingthemanagementofcodekeys.Firstdescribedintheopenairofscholarlyideas,Whit?eldDi?e,MartinHellmanandRalphMerkledevelopedarevolutionarynewapproachtocryptographywhichinvolvedwhathascometobecalledpublic-keycryptography.Basedonthisinnovation,otherworkers,notablyLeonardAdleman,RonaldRivest,andAdiShamir,generatedimplementablesystemsbasedontheseprinciples.

Thedevelopmentofpublic-keyconceptsnotonlyraisedthepossibilityofcheapsecurecodesbutalsootherinterestingpossibilities.Forexample,whenmessagesaresentthereareconcernsaboutissuessuchaswhoreallysentthemessageorwhetheramessagesentbyXhasbeenalteredafterXsentit.Cansystemsbedevisedthatprovideelectronicequivalentsofsharingpower,signingabindingdocument,provingidentity,etc.?Notalloftheearlysuggestionsforpublic-keysystemshavesurvivedattemptstoshowthattheycouldnotbebroken(i.e.MerkleandHellman’sknapsacksystemhasbeenshowntobeinsecure).However,public-keyideashaveraisedthespecterofeasytoimplement,secure(i.e.forallpracticalpurposesunbreakable)codesthatcanbeusedtoprotectemail,wirelesstelephony,andrelatedtechnologies,includingonesnotyetthoughtof.Public-key

6

cryptographycatapultedcodesintothebusinessworld.Inaglobaleconomysellingsecuresystemsfortheinterchangeofmoneyorideasbetweenbanks,creditcardtransitions,etc.o?ersahugemarket.Suddenly,theactivitiesofscholarsandbusinessescametotheattentionofNSAand/ortheFBI.NSAwasconcernedthathardwareofAmericanoriginwouldbesoldabroadandusedtoprotectthesecretsofforeigncountrieswhosesecretswerecurrentlypotentiallymonitorablebytheUS.TheFBIwasconcernedthatmembersoforganizedcrimewouldbeabletoavoidbeingbroughttojusticeiftheycouldtakeadvantageofthesecuritythatnewtechnologiesmightmakepossible.

ThisbringsustosomedetailsofDi?eandLaudau’sbook.Thebookbeginswithabriefhistoryofcryptographyandaprimerofpublic-keymethodsandadiscussionthatnewencryptionideasbringforawidevarietyofimprovedandemergingtechnologies.(Tosupportthisdiscussion,Imighthavewishedforanappendixthattreatedsomeofthedetailsoftheconceptsbehindpublic-keyideas.)Thebookthengivesadetailedhistoryofthewaythatlawenforcementagencieshaveoperatedtoobtaininformationthatmightbeofvalueinsolvingorprosecutingcrime.Speci?cattentionisgiventotheissueoflawenforcementagencies’beingabletomonitorandlisteninontelephonetra?cascomparedwithusingsurveillancedevicesand”wires”assourcesofinformation.Theauthorsdetailtheconsequencesthatnewencryptiontechnologymighthaveforlawenforcementagenciesandthepublic’sdesireforandperceptionofprivacy.Mightthegeneralpublicpreferanassuranceofcommunicationprivacyevenwhenthismeanscriminalswouldhavethesameprotectionasthosewhoobeythelaw?Willkey-escrowsystemsworkasexpectedweresocietytodecidethatitwishedtogothisroute?Thesekindsofquestionsandissues,aswellasmanyrelatedones,areablyraisedbythisbook.

AlthoughDi?eandLandauareconcernedaboutprivacyissues,theydonotbringtotheirreaders’attentionallaspectsofnewtechnologythata?ectthismatter.Examplesarethepowerofglobalpositioningsystemstomonitorthelocationofpeopleusingcellphones,securityviacomputervoicerecognitionsystems,or?ngerprintchips.Theissuestheyraise,infact,havebroadersettingsthantheysuggest.

SincemanyfeelthatprivacyisoneofthecoreAmericanvalues,Di?eandLaudau’sbookisavaluableservicetoallofus.Itraisestheimportantandsubtleissuesthatscholars,legislators,andcitizenshavetobalanceinacapitalisticdemocracy.Thiswellwrittenandresearchedbookdeservestobewidelyread.

References

Hardy,G.H.,AMathematician’sApology,CambridgeU.Press,NewYork,1940.

Lebrow,I.,TheDigitalConnection,ComputerSciencePress,Rockville,1991.

Rivest,R.,TheCaseagainstRegulatingEncryptionTechnology,inSpecialReport,

ComputerSecurityandtheInternet,Scienti?cAmerican,October,1998,p.116-117.

Schneier,B,andD.Banisar,TheElectronicPrivacyPapers:Documentsonthe

BattleforPrivacyintheAgeofSurveillance,Wiley,1996.

7

Reviewof

ATheoryofObjects

Series:MonographsinComputerScience

Authors:Mart??nAbadiandLucaCardelli

Publisher:Springer-Verlag,1996

ISBN:0-387-94775-2

$44.95,Hardcover,396pages

Reviewer:BrianPostow

1Overview

Whenanewprogramminglanguageisdesigneditissometimesusefultohaveaformallanguageinwhichwecandescribewithmathematicalrigorwhataprograminthatlanguageisdoing.Thismathematicallanguagecanbethoughtofasasemanticsoftheprogramminglanguage.Ifthesemanticsissu?cientlywelldevelopedwecanuseittoprovethataprogramdoeswhatwethinkitdoes.Noactualprogrammereverdoesthis,butitiscomfortingtoknowthatitcanbedone.

Thereareseveraldi?erentmathematicallanguagesforgivingthesemanticsofimperativepro-gramminglanguages(e.g.CorPascal).Control?owgraphs,orlogicalinvariantscanbeusedforthis.Therearealsoseveraldi?erentλ?calculifordescribingthesemanticsoffunctionalprogram-minglanguages(e.g.LisporML).Likewisewecanuseclassicallogicandresolutionasasemanticsoflogicallanguages(e.g.Prolog).However,thereisnomathematicallanguagefordiscussingthesemanticsofobjectorientedprogramminglanguages(e.g.JavaorSmalltalk)thatisfullysatisfying.Thegoalofthisbookisto?llthisvoid,oratleasttomakeastart.

Theauthorscomefromthefunctionalprogrammingandformalsemanticssideofthe?eld,ratherthanthesoftwareengineeringside,thereforetheyproposeacalculusthatisbasedontheλ?calculus,ratherthananyactualprogramminglanguageinuse.However,inthisnewcalculus,whichtheycallthe??calculus,insteadoffunctionsbeingprimitive,objectsare.Theauthorsproduceafamilyof??calculiinordertohopefullyrepresentmoreandmorecomplicatedobjectorientedtechniquesandstructures.

2SummaryofContents

Thebookisdividedinto4sections:areviewofobjectorientedfeatures,?rstordercalculi,secondordercalculi,andhigherordercalculi.

2.1Review:ObjectOrientedFeatures

Thisisagoodoverviewoftheobjectorientedstructuresandtechniquesthatwillbediscussedintherestofthebook.Theauthorsdiscussthedi?erencesbetweenclass-basedlanguagesandobjectbasedlanguages,andtheadvantagesanddisadvantagesthereof(thecalculiinthebookarealmostallobjectbasedbecauseoftheincreasedsimplicity).Theyalsodiscusssubclassing,subtyping,inheritance,andsubsumption,andexplainwhatuseanddi?cultiesthesewillcauselaterinthebook.

8

2.2PartI:UntypedandFirst-OrderCalculi

InPartI,theactualcontentofthebookbegins.Theauthorsstartbygivingthesimplest??calculus,anuntypedobjectcalculuswithnobellsorwhistles.Sincethiscalculusdoesn’tdescribesubtypingatall,itismerelyajumpingo?pointforthe?rstordertypedcalculi.

Throughouttherestofthepart,variousissuesareraisedandconstructsareaddedtothecalculustodealwiththem.Forexample,whensubtypingisaddedtothecalculus,itisfoundthatfunctiontypesdon’tfollowthesubtypingrelationintheexpectedway.Ifyouhave2functiontypes:F=A→BandF′=A′→B′andyouwantFtobeasubtypeofF′(F<F′),whatdoyouneedtoknowaboutA,A′,B,andB′?Well,youwantanobjectoftypeFtobeusableinanyplacethatexpectsanobjectoftypeF′.IfB<B′thenwhateverafunctionoftypeFreturns,itwillbeacceptabletothereceiver.Thisiscalledco-variance.Ontheotherhand,whenwelookattheargument,theresultsarenotasintuitive.AnyargumentthatwouldbevalidtopasstoafunctionoftypeF′mustbevalidinthefunctionofclassF.ThereforeA′<Amusthold.Thisiscalledcontra-variance.Issuesofco/contra-varianceoccuratregularintervalsthroughoutthebook.

2.3PartII:Second-OrderCalculi

PartIdealsmainlywithmethodsandsub-typing.PartIIgetstotheothermaindi?cultyofobjectorientedsemantics:thetypeofSelf.

Manyusefulprogramsareverydi?culttowriteifobjectscan’ttalkabouttheirowntype.However,determiningthetypecorrectnessofobjectsthatDOknowwhattypetheyarebecomesunintuitiveveryquickly.Inaddition,Selftypesaddavarietyofnewvarianceissues.Forexample,whatisthee?ectofinheritanceonaninheritedmethodthatusesaSelftype?Thisisaquestionthatrelatestomuchoftherestofthebook.

2.4PartIII:Higher-OrderCalculi

Havingfailedtocometoasatisfying?rstorsecond-ordercalculi,theauthorsresorttohigher-ordercalculitodealwithproblemsthattheyhaddevelopedearlier.Theyreferencetypetheory,especiallyGirard’ssystemF.

Usingahigherordertechniques,theauthorsdoarriveatacalculusthatallowsthemtodoprettymucheverythingthattheywantto(includingbinarymethodsofthetypeSelf*Self→Self).Howeveratthispointthecalculusissocomplexandclutteredwithsyntaxthatitbecomesverydi?culttoworkwith.

3Style

Thisisnotaneasybook.TheoverviewinPart0isrelativelyeasy,andshouldbereadabletoanyonewhoknowsalittlebitaboutwhatobjectorientedprogrammingis.PartIisalittlemorechallengingandassumessomefamiliaritywiththeλ?calculus,andtheconceptofatypederivation.PartIIismoredi?cultwithmorerelianceontypetheory.PartIIIgetsverydense,withpagesofcomplextypederivations.However,tomakeiteasierthesame3-5examplesareusedrepeatedlythroughoutthebook,soitiseasytocomparecalculi.

9

4Opinion

Thisbookdoesn’tclaimtobeacompletetheoryofobjects,merelya?rstattempt.Atthisitsucceeds.Thetheorythattheauthorsdevelopismuchmorecomplexthanwouldbehoped.Forexample,thelistofnotationsusedinthebooktakes15pages,andthereareover30di?erentcalculiandlanguagesdescribedinthebook.

Overall,itisaveryinterestingbook,buttheauthorsdon’tquiteliveuptotheirgoalofmakingasimplelanguagefordiscussingobjectorientedissues.

10