CedarLanguageOverviewVersion4.2Releaseas[Indigo]Documentation>Overview.tioga,.pressCamefrom[Indigo]Manual>Overview.tioga,.pressLasteditedbyHorningonJune1,19836:48pmAbstract:ThisOverviewisintendedtointroduceyoutothebasicvocabularyandconceptsthatyouneedbeforeplungingintosourcesofmoredetailedinformationabouttheCedarLanguage.ItassumesthatyouhavealreadyreadtheBriefingBlurbandtheIntroductiontoCedar.Ifyouhaven't,readthemfirstandreturn.ItstartswithabriefreviewofthecommonconceptsthatCedarshareswithothermembersofthePascalfamily,thengivesasomewhatlesshastytourofthemorenovelfeaturesofMesa,followedbyadiscussionoftheadditionalchangesthatproducedCedar.Finally,thereisaguidetosourcesoffurtherinformation.Version4.2oftheCedarlanguagedocumentationcorrespondstoRelease4.2oftheCedarsystem.ItisintendedtosupersedealldescriptionspriortoJune1983.Previousdocumentsmaybereadforhistoricalinterest,butarebelievedonlyatthereader'speril.[Ifyouarereadingthisdocumenton-line,IsuggestthatyouusetheTiogaLevelsandLinesmenustoinitiallybrowsethetopfewlevelsofitsstructurebeforereadingitstraightthrough.]XEROXXeroxCorporationPaloAltoResearchCenter3333CoyoteHillRoadPaloAlto,California94304DRAFTForInternalXeroxUseOnlyDRAFTp ^k!q Ynr TqosTq,0r R LsR).r Q sQW~( $s't Jws=JwJws^"u$3*-/_15 =K@2F H 7]S#%)/5 7;>=B=t G( c,|g"?%(.3B6[9 BbD; E WY;:"s( E(nE)?-+0/1Y49%:=2C$ C q$A&&(-2~59;[BE B2 X# $*,.& 5y7?9 @F @`j>!%-&,.N3 =7HO"| , 57=@WB^E+ ;G1R!N#M +/8048>Fj 9 o  Z"(+-0=6t 6 @&$b# (*07369<A4Fa 4z "'%)(,+0l25hB9EDF^ V  T/S "(*-Z2u8 ;lA GR R P. &,/6C{ PVo!i ')+06P8 A;BE* O9r I&|(-38H>qATG\ M ]$ (+P.3 \ABEtG/ F3cW%4') 2m ;F CE Dv `(d$'+16\9>vD B W #P (*0m279< D A( / !#'s >37 -&(/ 7<93;? F =t$^'Z,R..17@ >BEw ;[P $&'-/715y:S;[:;[;>D F 9 ,# #m% -/3587=[@zCF 8 v 5Tf"D&(+V187:>OBE 3~"$*- 035.7; >CE 2@y  #(+m157W:=>C D 0 ) .W R"&]),R-26e:m@C ,s TZ>a!$h +K-14r8P=M?AFH *   $'F-4/27 :L;o>ACF )% :$&u+O/5~7: AEv '} ql $ $,. 6S8;=:?BE #XN)#%(* 057Q;,= E{G/ !s{ %U((,/P2e59;=?C_F  m  "j$2)36=AEFH  R2- q#&*-2y4I5<9\;=X?C =  <!@#l% 'W+H0 1z28R9@B  S)"%'*, 28G:=&BhEwG0 vqX!V'H)7+158_='>E G GR#'%* 1#4:7 ADE Mw&+  TVm$CEDARLANGUAGEOVERVIEW4ReviewofthePascal-likefeaturesThefollowingsummarizesaspectsofCedar(andMesa)thatarebasicallysimilartothoseofothermembersofthe"Pascalfamily"oflanguages(e.g.,Euclid,Modula,Ada).Ifthereareanyconceptsinthissectionthatarenotalreadyfamiliartoyou,youshouldprobablyfindaPascaltextbookandstudyitbeforeproceedingtofurthermaterialonCedar.(Youwillfindthatthenamesfortheseconceptsvarysomewhatfromlanguagetolanguage.)Analgorithmorcomputerprogramconsistsoftwoessentialparts,adescriptionofactionsthataretobeperformed,andadescriptionofthedatathataremanipulatedbytheseactions.Actionsaredescribedbystatements,anddataaredescribedbytypedefinitions.DataandtypesDataarerepresentedbyvalues.Valuesareimmutable;theyarenotchangedbycomputation.Aconstantalwaysdenotesthesamevaluewithinascope.Avariableisavaluethatmaycontainanothervalue;assignmentchangesthevaluecontainedbyavariable,butnotthevaluethatisthevariable.Avalueusedinaprogrammayberepresentedbyaliteralconstant,thenameofaconstantorvariable,orbyanexpression,whichwillitselfcontainothervalues.Everynameoccurringintheprogrammustbeintroducedbyadeclaration.Adeclarationassociateswithanamebothadatatypeandaconstantvalue(whichmayitselfbeavariable,andcontaindifferentvaluesatdifferenttimes).Adatatypedefinesbothasetofvaluesandtheactionsthatmaybeperformedonelementsofthatset.Itmayeitherbedirectlydescribedinadeclarationthatusesit,oritmaybereferencedbyatypename,introducedinatypedeclaration.Thetypeofeveryconstant,variable,andexpressioncanbededucedfromstaticanalysis.Thisanalysisisperformedbythecompilertoensurethatallprogramsaretype-correct;thusthelanguageissaidtobestronglytyped.Anenumeratedtypedefinitionindicatesanorderedsetofvalues,i.e.,introducesnamesstandingforeachvalueintheset.Thesimpletypesaretheenumeratedtypes,thesubrangetypes,andthebuilt-intypes,includingBOOL,INT,REAL,andCHAR.Therearestandarddenotationsforliteralconstantsofthebuilt-intypes:TRUEandFALSEforBOOL,numbersforINTanditssubrangesandforREAL,quotationsforCHAR.Numbersandquotationsaresyntacticallydistinctfromnamesasarethe"reservedwords"ofthelanguage.ThesetofvaluesoftypeCHARisan8-bitvariantoftheASCIIcharactercodes.Atypemaybedefinedasasubrangeofasimpletypebyindicatingthesmallestandlargestvalueofthesubrange.Structuredtypesaredefinedbydescribingthetypesoftheircomponents,andindicatingastructuringmethod:ARRAYorRECORD.Thesedifferinthemechanismforselectingacomponentofavalue.Inanarraystructure,allcomponentsareofthesametype.Acomponentisselectedbyacomputableselector,orindex.Theindextype,whichmustbesimple,isindicatedinthearraytypedefinition.Itisusuallyaprogrammer-definedenumeratedtype,orasubrangeofINT.Givenavalueoftheindextype,anarrayselectoryieldsavalueofthecomponenttype.Everyarraystructurevaluecanthereforeberegardedasamappingoftheindextypeintothecomponenttype.Inarecordstructure,thecomponents(calledfields)arenotnecessarilyofthesametype.Inorderthatthetypeofaselectedcomponentbeevidentfromtheprogramtext(withoutexecutingtheprogram),arecordselectorisnotacomputablevalue,butmustinsteadbeanameuniquelydenotingthecomponenttobeselected.Arecordtypemaybespecifiedasconsistingofseveralvariants.Thisallowsdifferentrecordvaluesofthesametypetohavestructuresthatdifferinthenumberofcomponents,theirtypes,ortheirnames.Thevariantdescribingaparticularvalueisindicatedbyaspecialfield,calleditstag.VariantsofatypeCEDAR4.2v;gw 9g gv$Rgw%:gv,gw-+gsHDgx ^j v [ 8!#'+/M2*4:*>@{D(E Y.&C).v4 79~=?B3G XW Ay#$'*/!479,=[CE V @ J"F$J(,>.14z6V7Vv;$V;V=_@F U X3 R RS"'),j156 >z?R@uRvDdRDRG; P  f] !#z%P&`Pv(P)dP,. 69<AG; O?zO?O?v&O?O?!'=z)9O?)O?, v2#O?y K ^v H6 JzqH HvH!H%z('H(Hv/kH/H25$7=_? Hz Fv_FFc"'(?,sz.F.Fv39F3F459<z?F@=FvDFE)F ER  L V&()/U14K6:T=#Dcz=#ER=D=ERv>ER@ Ba2kr!# +G-jz.B/B2v7B8Bz;8B;Bv?B?B@B5G A/jzA/A/vA/A/"V%*p-2r6X:@AD ? < z?? vT? ?! ( .126T9x:=w@oCD  = !}n!&z#=$y=v(=)u=.T249 ;ez7;e;e9v;e;e4N!%.'*>.146=P?SE F 9 q   "N$ %G ,i/H2R457M:a|-V?O-VvA-VB~-V +w =+ +v++r @" *s/\29D * " w#*$*v'*'*(*.,246;;A# 'E_nit,za''v$'$'%'+.0 79}>AE % z #j Av#j;#j &((r+-0 8;W AzB#jC;#j !w(!!v!o!wx!L!vf!B!D#$'.O06&7P>x@1A[ GjzHGGvGG #%%e' )X,0189?AB OzvQ7b#z&(-/&5%69G<? FH#  $<')q*0w2=2v4I5)9[:>7?BXF' Qz Q QvQ|Q3"p)-Q1p5!;>AG V;S #.&(f/ .z.P.v. . $>z(.)1.v+.,./=1 8:|<@~CE   "'*-225U:@C/  /d '$&t).Y0.1=4:@#Bg 8   < U" (\*z./Dv3@479;hAEa   gmP "N&'* /.0 8<?AD n e + c#$|*r,o-259z;y n; nv=J n>( nCESFw&+  TVm$CEDARLANGUAGEOVERVIEW5mayalsosharefieldsinadditiontothetag.Anexplicitvariabledeclarationassociatesanameandastaticvariable;thenameisusedtodenotethevariableinexpressions.Dynamicvariablesaregeneratedbyaspecialprocedure(NEW)thatyieldsapointerorreferencevaluethatsubsequentlyservesinplaceofanametorefertothevariable.Finitegraphsintheirfullgeneralitymayberepresentedusingpointersorreferences.StatementsThesimpleststatementistheassignmentstatement.Itspecifiesthatanewlycomputedvaluebeassignedtoavariable(oracomponentofavariable).Thevalueisobtainedbyevaluatinganexpression.Expressionsconsistofvariables,constants,operators,andprocedurevaluesoperatingonargumentstoproducenewvalues.Constantsareliteralordeclared;variablesandproceduresarebuilt-inordeclared;thesetofoperatorsisdefinedwithinthelanguage,andincludesoperatorsforarithmetic,comparison,andlogicaloperations.Theprocedurestatementcausestheapplication(invocation,call)ofadesignatedprocedurevaluetothevaluesofitsarguments(actualparameters).Basicstatementsarethecomponentsofstructuredstatements,whichspecifysequential,selective,orrepeatedexecutionoftheircomponents.Sequentialexecutionofasequenceofstatementsisspecifiedbyseparatingthembysemicolons;conditionalorselectiveexecutionbytheifstatementandtheselectstatement;andrepeatedexecutionbyloopstatements.Ablockcanbeusedtoassociatedeclarationswithstatements.Thenamessodeclaredhavesignificanceonlywithintheblock.Hence,theblockisthescopeofthesenames,andtheyaresaidtobelocaltotheblock.Sinceablockmayappearasastatement,scopesmaybenested.Ablockcanbethebodyofaprocedurevalue.Aprocedurehasafixednumberofparameters,eachofwhichisdenotedwithintheprocedurebyanamecalledtheformalparameter.Actualargumentvaluesaresuppliedforparametersateachapplication.Proceduresmayalsohaveresults;applicationsofsuchproceduresmayappearwithinexpressions.CEDAR4.2v;gw 9g gv$Rgw%:gv,gw-+gsHDgv _/ [,": \ , &Y'+J.z/2\/\v2\3}\8:>@CVE [ SH z[[v [!\[&o(/1!2R6=aw=[>[v@[A[DrHez YZvYZ_YZzYZ YZvkYZYZ6& %)+/812^6?8;=Q?E W] R 26!& (,:13K y TU v P5.zP jP&v,cP-kP/479=0CG OP_+[!#$ *-1%285:+ @zBOPCBOPvHOP M   $ +-4r8>AG LF4d#P%+03 :<AC JZ fzpJZ JZvhJZJZ!g#*,2i8: A H  F,zF,:F,vF,lF, z"sF,##F, v)`F,)F, 0356 =D3G D Ky2z DDvDD AD V #gz%#A%A+w v1A2jA6z; A G @W}W " )I/t1#2C8!9 @AG > o L %'-T35z8>8>:v@_>A>CLzE>Fg> = vy= = 0z = !`= # v* = :z::v:3:g 'W*L 17389?B% 8 F`"|#z&C8&8v)8*8+/36n9|;>@PzB?8B8vE8E8G/ 74-! '+.0 4;{z44v44z44%)v(/4) 4*1348>=lz?&4?4vE4F^4 3 ,a##%&()-z030}34Pv:%3:3?GEa 1_ ?  . z.[.v!."1. )"*. 58<@ w&+ TVm$CEDARLANGUAGEOVERVIEW6FromPascaltoMesaMesaextendedPascalinanumberofdirectionsintendedtomakeitmoreeffectiveforthedevelopmentoflargesystems.StudentsofprogramminglanguageswilldiscerninfluencesfromAlgol68,BCPL,andseveralothersystemimplementationlanguages.Itisalargerlanguage,andisrathermoredifficulttomasterinitsentirety,thanPascal.Itisintendedforprofessionalprogrammers,notforbeginningstudents.Mesamodulesareseparatelycompiledprogramunits,withtype-checkingpreservedacrossmoduleboundaries.Mesaprovidesmechanismsforsystematichandlingofexceptions,processesandmonitors,proceduresasfirst-classvaluesthatcanbeassignedtovariables,andafairnumberofsyntacticandsemanticamenitiesintendedtomakeprogrammingmoreconvenient.Thefollowingsectionsintroduceeachofthemajorconceptualextensions,butdonotexplainthemingreatdepth.See[Geschke,etal.]foramoreextensiverationale,andCSL-79-3forfulldetails.ModulesMesamodulesarea"programminginthelarge"mechanismforpartitioningasystemintomanageableunits.Theycanbeusedtoencapsulateabstractions,toprovideadegreeofprotection,andtoenforce"informationhiding."Theyarealsotheunitsofseparatecompilation.Therearetwokindsofmodules:DEFINITIONSmodules,whichdefineinterfaces,andPROGRAMmodules,whichcontaintheexecutablecodetoimplementtheseinterfaces.Definitions(ordefs)modulesdefineinterfacestoabstractions.Theytypicallydeclaresomesharedtypes,usefulconstants,andthedomainsandrangesofasetofprocedurenames.Theycompileintosymboltables,whicharesharedbybothclientsandimplementations.Checksareperformedwhenmodulesareboundintoaconfigurationtoensurethatseparatelycompiledpieceshaveusedconsistentversionsoftheshareddefinitions.Interfacesproducenoexecutablecode;theymanifestthemselvesatruntimeprimarilyassymboltablesthatareaccessiblefordebuggingandsimilarpurposes.Programmodulesprovideimplementationsofabstractions.Theytypicallydeclarecollectionsofvariablesthatdefinetheirstateandprovidebodiesfortheproceduresoftheirinterfaces.Viewedassourcetext,theyaresimilartoPascalproceduresandSimulaclassdefinitions.Theycanbeloadedandinterconnectedtoformcompletesystems.Atruntime,oneormoreinstancesofanimplementationmaybecreated.Aseparateglobalframe(activationrecord)isallocatedforeach,containingstorageforitsglobalvariables(thosewhicharedeclaredoutsideitsprocedures),whichpersistbetweenapplicationsofitsprocedures.Thelifetimesofimplementationinstances(unlikethoseofprocedureapplications)arenotrestrictedtofollowanyparticulardiscipline.Communicationpathsamongimplementationsareestablisheddynamicallyandarenotconstrainedbyany(staticordynamic)nestingrelationships;lifetimesandaccesspathsarecompletelydecoupled.Themodulebodyitselfgenerallycontainsthecodetoinitializetheglobalvariablesandestablishanynecessaryinvariants.Itwillbeexecutedwhenthemoduleisstarted,oruponapplicationofoneofthemodule'sprocuedures,whichevercomesfirst.Amodulethataccesses(reliesondeclarationsfrom)othermodulesmustincludeDIRECTORYstatements,sothenecessarysymboltablescanbeacquired.Ifitusesonlyasubsetofthedeclarations,itisgoodpracticetoindicatewhichoneswithaUSINGlist.DeclarationsinaninterfacearepublicunlessdeclaredtobePRIVATE.Normallytheimportingmoduleaccessesonlythepublicnames;privatedeclarationsmaybeaccessedbyimplementingmodulesthatindicatetheySHAREtheinterface.Adirectorystatementmaylistthenameofafilecontainingthesymboltabletobeused,butifthefilenameisthesameasthemodulename(exceptfortheextension.bcd)itisomitted.Amodulethatusesnon-constantdeclarations(e.g.,exportedtypesandprocedures)fromanotherCEDAR4.2v;gw 9g gv$Rgw%:gv,gw-+gsHDgx _]v [ad$d&r -3$5'90:>DG/ Z g"# ,92x59 @BCGR XcNB (9 .023H7L=@RAE VeU#')+>1<3 ; DGR UX RziRRvR[R $*K.1K :@pD P }N "%H +1z3P4\P :v@PAhPzCPDPv OK  s k# %:*, 257&9?0AF Mw& )l- K( $&%(F,? 3) :(<>A/F I  Rz=IIv9I I"]#'- 35<>=@y F2v B0 !#a%)02 9:?SB A< cb( " *,V1y27B9 @BD ? &~Z &"%', =x^MA{"y=#U= v*=+=052z9=: =v?0=@G={C9=C=v ;r !%!z&;r'2;rv-[;r-;r0 z 8 v^88#T )+e 3Y6<AzE) 7P 9 #&*,.*0k2H8=A\Fz 5Zv5o5bz!5"5v&5&5z(5)5 v252579@pD  4z ;4 4vF44z>44 v~44'"%Q +159<= BG 2Z 9 z2Z>2Zv2Z-2Z$' .2!5t;G B{DX 0_Km %'.1[5z .7v.7.7N(=*7 2O6;@ G ,/ &*-/ 68< BG *E^wc!G (W+/3 :2=@YBSF )A 1G/ &m3z&!&v"&#W&$oz&z&&& v0&1<&305;:v<zA&B@&Ev %  # */2Sz4n%5%8v>%?%BG; #wma Tz"{#w#,#wv&#w'#w,M 357 ?<B-G ! !HP#E%T,- 47<: @\B`F ) '  $w)3j5 < DG;  M t#(= 06!8<@TB  '[  &,N.2[4= :<@F 3"  +"$*l.0p5hz637O3v:3;3=@@ G  Q %@)n zv #L +6/k3^96<wB&C v i #&G(1.)/0368zAAAvEOF wvC #*8/5 8;J?D s aClF %+G-3w5s6sv:$s:sC "'e?j ').2 359U;=8?BEG/ $ iww6!=#)-9./ Yxe} ! ),269_ @Dw&+  TVm$:CEDARLANGUAGEOVERVIEW7modulemustexplicitlyimportit.Ifamoduleimplementsanypartofaninterface(e.g.,bysupplyingthevalueofaprocedureortypethatitdeclares),itmustexplicitlyexportit.ThecompilerwillcheckthatitsPUBLICdeclarationsaretype-consistentwiththecorrespondingdeclarationsintheexportedinterface(s).Eachmoduleiseffectivelyparameterizedbyasetofinterfacerecords,oneforeachinterfaceitimports,andsuppliesasetofexportrecords,oneforeachinterfaceitexports.Notethatinterfacesandimplementationsneednotbeinone-to-onecorrespondence.Bindingagroupofmodulestogetherintoaconfigurationinvolvesassigningvaluesfromtheexportrecordstothecorrespondingfieldsintheinterfacerecords.Thereisaspecialsublanguage,C/Mesa,tocontrolthisprocess.Accessingothermodulesintroducescompilationorderdependencies.Eachmodulemustbecompiledafterthemodulesitaccesses(andrecompilediftheychange),sincethecompilerneedstheirsymboltables.Butinformationdoesnotflowintheotherdirection.Modulesthatarenotaccessedbyothers(virtuallyallimplementations)maybefreelyrecompiledwithoutinvalidatingpreviouscompilationandcheckingofanyothermodules.Types,aswellasprocedures,canbedeclaredopaquelyininterfacesandsubsequentlyboundtoconcretevaluessuppliedbyimplementations.Thismakestheinternalstructureofthetypeinvisibletoclientsoftheinterface,andensuresthattherecanbenocompilationdependenciesbetweenthedefinitionoftheconcretetypeandtheinterfacemodule.Thedefinitionofthetypecanbechangedatanytimewithoutrequiringrecompilationoftheinterfaceoranyclientsoftheinterface.EffectiveuseofMesarequiresathoroughunderstandingofmodulesandtheiruse.Theyhavesignificantlyinfluencedourprogramdesignandconstructiontechniques.Programsarealmostneverself-containedmodules;theimportationandre-useofexistingcodehasalltheadvantagesoftheftoverhonesttoilwithoutthemoralstigma.Considerableemphasisislaidonthecarefuldesignofinterfaces,andontheirdocumentation.Sinceitisonlyinterfacechangesthatforcerecompilation(orperhapsevenrewriting)ofclientprograms,itisimportantthatinterfacesremainstableforsubstantialperiods,evenwhiletheirimplementationsareundergoingchange.Arecommendedapproachistodefine,comment,andcirculateforreview,alloftheinterfacesina(sub)systembeforewritinganyoftheimplementations.Interfacesplaymuchthesameroleas"programdesignlanguages"inotherenvironments,withtheadditionaladvantagesofbeingpreciselydefinedandmechanicallyenforced.TheMesalanguagedefinitionomitsmanyofthefeaturescommonlyexpectedinprogramminglanguages,suchasinput/outputandstring-manipulationoperations.Ofcourse,thesefacilitiesareavailabletoMesaprogrammers,buttheyareprovidedbypackageswritteninthelanguageitself.ThedescriptionsofstandardpackagesintheMesaProgrammer'sManual,Version8.0,runtomorethan300pages.Whenmanaginglargecollectionsofmodules(andinsystemsliketheMesaDevelopmentEnvironmentandCedartheyrunintothethousands),modulenamesbecomeveryimportant.Theuseofcrypticoracronymicnamesisdiscouraged.Byconvention,sourcefilenameshavetheextension.mesa,andobjectfilenameshavetheextension.bcd(forBinaryConfigurationDescription).ThedefinitionsmoduleforaninterfaceXiscustomarilynamedX;ifitisimplementedbyasingleprogrammodule,thatiscustomarilynamedXImpl.ExceptionsMesaprovidesawaytoindicatewhenexceptionalconditionsariseinthecourseofexecutionandanorderlymeansfordealingwiththemthatisinexpensiveiftheydonotarise.Exceptionscauseatransferofcontrolfromthestatementthatraisesthemtoadynamically-selectedpartoftheprogramintendedtohandlethesituation.Theymayberaisedinresponsetothedetectionof"impossible"situations,invalidinputs,theinabilityofanabstractiontosupplyitsspecifiedservice,orsimplyunusualevents.CEDAR4.2v;gw 9g gv$Rgw%:gv,gw-+gsHDgv _'B z!_'_'vk_'_' % -/2t4$6 ;>@G/ ] l6 ( j &'+h z1^]1]v5]6 ]7e:L@BF [w [ O[v,[[ #&(N 1% 8:*BbH9 WXozW$W v$W%W(*. 35:N=@ F VJ $.359:@3EHez Tg vTgzTgT!!6$&+/1O3 lACz Nv EN NuP &(|+1R47q=RAYD LL !#& ) 058;+=CSEk KN !% ,2 9?? F Ia G,=/ "H$cz*G,*G,v/G,0GG,1 8: C[G EvT`&*)T-0 52:<?8BXG C `"%')+ 3< ;@CD B6 +!';*& 02P47:<B CFi @ c!'h),+014* >WF' " (5 1o3_9<?BFH CG 8I < 8:T! *,x0n5 =rCeDG 6 G Q "%G /245j8> CHF 4  #i%(/)0s18(: AE 3S ) 0w+"r,/( 6q 0; 33 O$+D-35:*@ FHe /0 kj ! + 2$5'8;[>ACP -A A #&) / 68L<AF + ' )f *$%(**,29?@ ' ht + 249D7  &  y b v gA*!&$ ,: 2697:h>@F k o !#&(k 0 147 9z=kk>^kvDkEkHe L""z%%v()`,.j/<?AD zvw K#&Y(,.4691?fA_ u ^m!&"$ +-f139_>8?Db w&+  TVm$CEDARLANGUAGEOVERVIEW8Mesaexceptionsareconceptuallysimilartoprocedures,exceptthatthebindingtothehandlerisdeterminedbysearchingthecatchphrasesinthecallstackoftheprocessinwhichtheexceptionisraised;thedynamicallyinnermosthandlerthatacceptstheconditionisapplied.Likenormalprocedures,handlerscantakeparametersandreturnvalues.Theyarewritteninadistinctivesyntaxthatclearlyidentifiesthemascodefortheexceptionalcase.CatchphrasesaresyntacticallyandsemanticallysimilartoSELECTstatements,withtestitemsindicatingtheexceptionsforwhichtheassociatedhandlershouldbeapplied.Therearespecialtestitemstocatcharbitraryexceptionsandtocatchanattempttounwindtheapplicationstackinresponsetoanexception.Aseriesofcatchphrasesmaybeassociatedwithaprocedureapplication,orenabledthroughoutablock.Ahandlerislikeaprocedurebody,butwhenitcompletes,thereareanumberofadditionalcontroloptions:GOTO,EXIT,LOOP,RETRY,CONTINUE,REJECT,andRESUME.Resumptionisanalogoustoreturningfromaprocedure,possiblywitharesult.ExceptionsaredividedintoSIGNALs,whichmayberesumed,andERRORs,whichmaynot;incommonparlancetheyaregenerallyallcalledsignals.Sincehandlersmaytakeparametersandreturnresults,eachexceptionnamemustbedeclaredinascopethatincludesallthepointswhereitisraisedaswellasallthecatchphrasesthatacceptit.Thecostofraisinganexceptionissignificantlyhigherthanthecostofprocedureapplication,butitshouldn'thappenveryoften.Thesystemguaranteesthatallexceptionsarehandledatsomelevel;thosethattheprogramfailstocatchareacceptedbythedebugger,keepingintactthestateoftheprogramthatraisedit.Exceptionscanbeusedinveryintricatewaystoachievesubtleeffects(e.g.,byraisinganotherexceptionwithinahandler).Experiencehasshownthatthisisalmostalwaysamistake.Somecallitelegance,otherscallitincomprehensible:"Fortheprogrammer,themainimportofnestedsignalsisthatoneneedstoconsider,whenwritingaroutine,notonlywhatsignalscanbegenerated,directlyorindirectly,bythecalledprocedures,butalsothosewhichcanbegeneratedbycatchphrasesinthatprocedureoreventhecatchphrasesofanycallingprocedures,alsobothdirectlyandindirectly."[MesaLanguageManual]Althoughhislanguageproposalshavenotbeenimplemented,RoyLevin'sdiscussionintheworkingpaper[Indigo]Style>SignallingGuidelines.pressisthebestsourceofguidanceontastefulandappropriateusesofexceptions.Themostimportantpointisthattheexceptionsaproceduremayraisemustbeconsideredpartofitsinterface,anddocumentedassuch.Unfortunately,thecompilercurrentlydoesn'tenforcethis,andmanyotherwiseexcellentinterfacesdonotcomply.Processes,monitors,andconditionvariablesMesaprovidesefficientmechanismsforconcurrentexecutionofmultipleprocesseswithinasinglesystem.Thismakesitnaturaltostructureprogramstoreflecttheirinherentconcurrency.Mesaalsoprovidesfacilitiesformutuallyexclusiveaccesstoresourcesandprocesssynchronizationbymeansofentrytomonitorsandwaitingonconditionvariables.FORKmakesitpossibletostarttheexecutionofanotherprocedureconcurrentlywiththeprogramthatappliesit.Itreturnsaprocess,whichmayeitherbedetachedtoproceedindependently,orsavedforafutureJOIN.Thereisnoruleagainstmultiplecoexistinginstancesofaprocedure,eitherforkedorapplied,althoughcaremustbetakentoensuremutualexclusiononaccessestosharedglobaldata.JOINtakesasingleprocessargument.WhentheforkedprocedurehasexecutedaRETURNandtheJOINhasbeenexecuted(ineitherorder),thereturningprocessisdeleted,andthejoiningprocessreceivesitsresultsandcontinuesexecution.Aprocesstypeisdeclaredsimilarlytoaproceduretype,exceptthatonlythetypeoftheresultisspecified.CEDAR4.2v;gw 9g gv$Rgw%:gv,gw-+gsHDgv _/s H !&n(9 /4 7 9>@BH# ] `zO]] v%]%h]&)h,/14)9(;?9AH# [a _#z&['K[v+>[+[-35:P=yB/ Z9c $(,j.357 =B.E* X h] $7 V; $ ,"0w3V3Vv7V8V ?gBE To B Duw! (,-+138<>CeE R H  <#%*z,R-iRv1qR1R3 :>y@3EG Q Yfu?"## *A-<.F4 ;z=Q >3Q vBfQ BQ  Oy  L/01P"% (* 04867<>p D KVwKVKVvKVw$KVKVvKVwKVKVvKVwIKVKVv 7KVw!eKV"/KVv'KVw(KV)KVv-KV.@KVw1IKV2KVv6&KV7SKV ?gA$G Io  $%4)a 0f27w:I;BIv?I?I@yDG HwHDHvH!H !#)[.14C:*<@ Ef #%).18 ;?8A,FHe C 9\"t#%6)8*-/1r37fW EH9 ?#' ),. 5i7=>B2E > P}%'*@069#B/ 0+  $S&K).0m379;v>AD /8gl "'* 1z2 /83`/85<v@/8 , #&G) 2159 @HAD8 + 3./f148:e@#BF )n ^k7 wl)nvI)n 5#*-/J2+4 ;j<C=FT ' SB & "%K -#.2W ;=C &E#9( /1%3y " ?Fv kz #D% ,24z:3:v@A DfE =0$+*- 1v4: BF 2 !i#g')f/2^7SASCpG  z.Dvi{NzU$8 v w qv;< T"(*/6X >ZA|C h Qe1U#Z&U*9z,"h,hv1h2h3R8 ACGR  <wv14\"(| /468+ ?-C?G /A2 "'+138:?C6 w H%vWnq#(*.5}7=w>?zDKDvFGfw v  QBU-"$*/06 8:?DM O  !#%) *{057P8}?BmF  eu.Y w&+  TVm$xCEDARLANGUAGEOVERVIEW9Allprocessesexecuteinthesameaddressspace.Thismeansthattheyarenotprotectedfromeachother,whichispresumablyacceptableinasingle-usersystem.Italsomeansthatprocesscreationandswitchingbetweenprocessesischeap(notmuchmoretime-consumingthanaprocedurecall).Generally,twoormorecooperatingprocessesneedtointeractinmorecomplicatedwaysthansimplyforkingandjoining.TheinterprocesssynchronizationmechanismprovidedinMesaisavariantof"monitors"adaptedfromtheworkofHoare,BrinchHansen,andDijkstra.Theunderlyingviewisthatinteractionamongprocessesisalwaysbasedonaccesstosharedresources(e.g.,data)andthatapropervehicleforthisinteractionmustunifythesynchronization,theshareddata,andtheproceduresthatperformtheaccesses.Amonitoristypicallyamoduleinstance,withshareddatainitsglobalframe,anditsownproceduresforaccessingthem.Someoftheproceduresarepublic,allowingapplicationsofmonitorproceduresfromoutside.Obviously,conflictscouldariseiftwoprocesseswereexecutinginthesamemonitoratthesametime.Topreventthis,amonitorlockisusedformutualexclusion.Applicationofoneofamonitor'sENTRYproceduresautomaticallyacquiresitslock(waitingifnecessary),andareturnreleasesit.Anintegrityconstraintthattheprogrammerimposesonthemonitor'sdataiscalledamonitorinvariant.Thelockmakesitpossiblefortheprogrammertoensurethatthisinvariantwillbetruewheneveranentryprocedurebeginsexecutionregardlessofwhatishappeninginvariousprocessessimplybymakingsurethatitistrueinitiallyandthateveryentryprocedurerestoresitbeforereturning.Ofcourse,aprocessmayenterthemonitorandfindthatthemonitordataisinagoodstatebutindicatesthattheprocessmaynotproceeduntilsomeotherprocessentersthemonitorandchangesthesituation.TheWAIToperationallowsaprocesstoreleasethemonitorlocktemporarily(andsuspendexecution)withoutreturning.Thewaitisperformedonaconditionvariable,whichisassociatedbyagreementwiththeactualconditionneeded.Aftermakingachangethatmayhavechangedthecondition,someotherprocessmustperformaBROADCASTorNOTIFYontheconditionvariable;thisallowsawaitingprocesstoreacquirethelock,retestthecondition,andresumeexecutionifitistrue.Notethatsinceawaitreleasesthelock,themonitorinvariantsmustberestoredbeforewaiting.Theproceduresofamonitorareclassifiedasentry,internal,andexternal.Internalproceduresmayonlybeappliedbyentryorinternalproceduresofthesamemonitor,sincetheyareintendedtobeexecutedwithinthemonitor'smutualexclusion,butdonotacquirethemonitorlock.Externalproceduresarelogicallyoutsidethemonitor,butaredeclaredwithinthesamemoduleforreasonsoflogicalpackaging.Beingoutside,theymustnotreferenceanymonitordatanorapplyanyinternalprocedures;theyareoftenusedtoprovideaconvenientinterfacethat"hides"oneormoreapplicationsofentryprocedures.TheattributesENTRYandINTERNALareassociatedwithaprocedure'sbody,notwithitstype;thustheydonotappearininterfaces.Fromtheclientsideofaninterface,amonitorappearslikeanyothermodule.Insimplecases,amonitor'sdatacomprisesitsglobalvariables,protectedbyanimplicitlockthatisautomaticallyallocatedinitsglobalframe.However,manyapplicationsdealwithmultipleobjects,represented,say,asrecordsaccessedthroughpointers.Itmaybenecessarytoensurethatoperationsontheseobjectsareatomic,i.e.,oncetheoperationhasbegun,theobjectwillnotbeotherwisereferenceduntiltheoperationisfinished.Itispossibletoassociatealockwiththeobject,ratherthanwiththemodule'sglobalframe,bydeclaringthedataasaMONITOREDRECORD.Asinglemoduleinstancecanthenimplementeachoperationasanentryprocedure,takingtheobjectasaparameter.LockingisspecifiedinthemoduleheadingbyaLOCKSclause.Asomewhatsubtlesourceofdeadlocksoccursifcontrolleavesanentryprocedurebymeansofanuncaughtexception.Unlessitiscertainthatallexceptions(includingthoseraisedbyinvokedprocedures)arehandled,eachentryprocedureshouldincludeanUNWINDcatchphrase,whichwillimplicitlyreleasethemonitorlock.ControlconstructsCEDAR4.2v;gw 9g gv$Rgw%:gv,gw-+gsHDgv _/ "!&*-247:Y<BF^ ] " ) !#$ +02h5M9<A}F [ol #'+( 538Y9@ Ye P "r(Z+-:2370 >BE WEb ">,b39;?ABG V W+!m%*|/288; B EOF To Z^!;%$'0+D,1f7j:>PACE R0  "p$/d16:<? F Q!D NF%(,/1G37;C=?B L < $&+Q0 8O9?. F( KW B"5#&.,!/i57-9<B-CF I zJI`Iyv!I!I#&t(- 4 ;=@RB)Cqw HvHIH f#&);.0R 7l:X;@EYG< Fa\ n "'),(2=586:z;Fa i"(1*-03U8;=C?@CCG =Ik$P'+*.37: ?KBG/ ; w;";v;^;!K"')q.0693 @D 9  z9 9v"9#T9$+-z/99/95Wv99:9?G@ G 8S$(B-."25e8O;|@C 6 e-w=66v&6'f6w(T6)=6v-6-6/ 1N7S<?oCD 5 h *" )+068d9;?>B DHe 3] OA %(*014 0 R! &z(0)J0v+0z,0,0v1010z405=0v9e0:E0? F /: 1MbH7!x (*-06:$=_?EG -  &)\+K-2p49=B + b@ "='+-1N6(8@<>B *D 9jz*D*Dvv*D*D"%U*-04s74`A &" w&"V&"v &"&"w&"+&"v#9&"#&"% +/0A 7;x=A BFo ${  \"9$(h+H- / 568;@CGE " X{ 'N)'-H 3Z9m;g=VB_EWH#  !G%,`0u 8V;?zDEuvH  m u%+Y,/179>@ G b ~$zb1bvfbKb8!'*Q.1J5l8 :<B  X+z &'-.25X7 D T Ky  w&+ TVm$CEDARLANGUAGEOVERVIEW10Mesa'sfacilitiesforordinarysequential"programminginthesmall"areextensive,butfairlyconventional.Thesyntaxisnotexactlylikethatofanyotherlanguage,butforthemostpartitcanbepickedupeasilywithafewminutesstudyofthegrammar.(Infact,sincemostprogramtextisproducedeitherbyeditingexistingprogramsorbytheuseoftheTiogaeditortoexpandsyntactictemplates,youmaybeabletojust"fakeit.")ThissectionmentionsanumberofareaswhereMesaprovides"convenience"extensionsorconceptuallysmallchanges.SELECTstatementsgeneralizePascal's"case"constructbyallowingseveralwaystospecifyhowonestatementistobechosenforexecutionfromanorderedlist.Themostcommonformisbasedontherelationbetweenthevalueofagivenexpressionandthoseofexpressionsassociatedwitheachselectablestatement.Therelationmaybeequality(thedefault),anyrelationaloperatorappropriatetothetypesofthevaluesinvolved,orcontainmentinasubrange.Asingleselectionmaybeprefixedbyseveralselectors,andanoptionalENDCASEstatementisselectedonlyifnoneoftheothersare.Discriminatingselectionisusedtobranchonthetypeofavariantrecordvalue(andinCedar,onthecurrenttypereferredtobyaREFANY).SELECTexpressionsareanalogous,butchoosefromanorderedlistofexpressions.Iterationisprovidedbyloopstatementsinwhichseveraldifferentkindsofcontrolcanbefreelyintermixed.Aloophasacontrolclauseandabody.Thecontrolclausemayspecifyalogicalconditionfornormaltermination,possiblycombinedwitharangeorasequenceofassignmentsforacontrolledvariable.Inadditiontoordinarystatements,thebodymaycontainEXITorGOTOstatementstoexplicitlyterminateitsexecution,andmaybefollowedbyaREPEATclausethatactslikeaselectionontheGOTOusedtoterminatetheloop.(GOTOcannotbeusedtosynthesizearbitrarycontrolstructures.Itismuchmorelikea"local"exception.)InPascal,procedureexecutionmustproceedsomehowtotheendofthebodybeforeterminating;inMesa,itcanbeterminatedanywherebyexecutingaRETURNstatement.Iftheprocedure'stypeincludesresults,thereturnstatementmaysupplythevaluestobereturnedotherwisetheyaretakenfromtheresultvariablesnamedinthetype.Eachprocedurebodyisfollowedbyanimplicitreturn.Pascalproceduresarenotvaluesthatmaybeassignedtovariables;Mesaproceduresare.Inmostcases,theprogrammerstillthinksofaconstantassociationbetweenaprocedurenameanditsbody,buttotrulyunderstandwhatisgoingonwheninterfacerecordsarebound,ithelpstorealizethatprocedurevaluesfromtheexportrecordsarebeingassignedtoappropriatefieldsoftheinterfacerecords.ThissamepowerisavailabletotheMesaprogrammer;onepopularformof"object-orientedprogramming"isbasedonthecreationofanexplicitrecordofproceduresforeachkindofobject,andpassingaroundtogetherapairofpointers,onetotheprocedurerecord,andanothertotheobjectinstancedata.INLINEprocedureconstantsmaybedeclaredininterfacesorlocally.Thisisaninstructiontothecompilertoexpandtheprocedurebodyinlineforeachapplication,ratherthancompilingacalltoout-of-linecode.Itisintendedtoimprovethespeedwithoutchangingthesemanticsoftheprocedureinlinesarenotmacros.INLINEshouldbeconsideredaformoftightbindingbestreservedforlatestagesofsystemtuning;amongotherthings,itcancausethecompilertorunoutofresources,evenwhencompilingwhatappeartobesmallmodules.Inadditiontoproceduresandexceptions,Mesahasathirdmechanismfortransferofcontrol,calledaPORT.Whenusedinpairs,portscanprovideaverygeneralformofcoroutineimplementation.Insomecircumstances,coroutineshaveadvantagessimilartoprocesses,atslightlylowercost,buttheyarenotusedmuchinMesaorCedar.MiscellaneousEveryexpressioninaMesaprogramhasasyntactictypethatcanbededucedfromitsstructurebystaticanalysisoftheprogramtext,aprocesscalledtypedetermination.Thelanguageimposesconstraintsonthetypeofeachexpressionaccordingtothecontextinwhichitisused,eveninseparatelycompiledmodules.CEDAR4.2vgwg gv#gw$gv+gw,gsG~gv _/ N & 0O2Y59 2w>>z> 2>v$>$>& )P+ 17D< BD%E FY 6j,!>$\(+a/1q3|@7CaE 5 S~9m!%4(/*249;=B 2 d!-$'%)(.0u 6:x ADPF2 0   g!& -3I4p:>AbC:G /9  Ln k$).}05q6:S;@GC  -?P 6$&)+ 368;YA$Fu + q ) +04W6@L *C Y;B!e%'p .x0378=D?D (PyR \ !i',/K4W68d<}A &!w 2&!&!v^&!%&! !(#4(* 027:Q EGG $yj %#'*i- 5t9=CEG " Jxz"(*z/`"0G"v4"5c";4>#DG/ !+*w S!+!AvC9  2S7 "&t aps m &),!->079>@E w  ve!R&N'j*k//2z434v::v D;E   5 $L(* 1'27;>ADG k (Vy  v  dC#%z'(',v/02}5 7<?AG % s;$1 W%(z)%)%+ v4%4%7=uB ~ Q`I #A$'N,"-133482;x=% C w&+ QTVm$CEDARLANGUAGEOVERVIEW11Thesyntactictypeofanameisestablishedbydeclaration.Theformofaliteralimpliesitstype.Eachoperatorproducesaresultwithatypethatisafunctionofthetypesoftheoperands.ThetyperulesinMesataketwogeneralforms:Thetyperequiredbythecontextisknownexactly,andagivenexpressionmusthaveit.Therequiredtypeiscalledthetargettype.Examplesoccurinassignment,initialization,recordconstruction,arrayconstruction,argumentlistconstruction,andarraysubscripting.Severalcoercions(e.g.,pointerdereferencing,base/subrangeconversion,single-componentrecordtofield)willbeappliedifneededtoconvertavaluewhosesyntactictypeisnotitstargettypetoonethatis.Theexacttypeisnotimpliedbycontext,butarelationthatmustbesatisfiedbyasetoftypesisknown.Theprocessoffindingtypestosatisfythatrelationiscalledbalancing.Examplesincludegenericoperators(suchasrelationals)thatrequiretwooperandsofthesametype,conditionalexpressions,andselectexpressions.Thecommontypeselectedwillbetheonerequiringthefewestcoercions.AsequenceinMesaisanindexablecollectionofitems,allofwhichhavethesametype.Inthisrespect,asequenceresemblesanarray;however,thelengthofthesequenceisnotpartofitstype.The(maximum)lengthofasequenceisspecifiedwhentheobjectcontainingthatsequenceiscreated,anditcannotsubsequentlybechanged.Itistheresponsibilityoftheprogrammertokeeptrackofthenumberofitemsinthesequenceatanytime.Mesaallowsadefaultinitialvaluetobeassociatedwithatype.IfatypeisconstructedfromothertypesusingoneofMesa'sstructures,suchasRECORD,animplicitdefaultvaluefortheconstructedtypeisderivedfromthedefaultvaluesofthecomponenttypes,butitcanbeoverriddenwithanexplicitdefaultvalue.Defaultvaluesforargumentscansimplifyprocedureapplications;defaultfieldsofrecordsmakethecorrespondingconstructorsmoreconciseandmoreconvenient;initialvaluesareusefultoensurethatthecorrespondingstorageisalwayswell-formed,evenbeforethevariablehasbeenusedbytheprogram.DynamicvariablesinMesaareallocatedinzones.Thesearenotnecessarilyassociatedwithfixedareasofstorage;rather,theyareobjectscharacterizedbyproceduresforallocationanddeallocation.Thereisastandardsystemzone,butprogramsthatallocatesubstantialnumbersofsimilardynamicvariablescanoftenimproveperformancebysegregatingeachkindintoitsownzone.TheoperatorNEWisusedtocreateadynamicvariableinazone,andFREEtoreleaseit.TheMACHINEDEPENDENTattributeallowsprecisecontroloftherepresentationofvaluesatthebitlevel.CEDAR4.2vgwg gv#gw$gv+gw,gsG~gv _/!1 ? 'F)B ]< ^ [H! w#$'*,-/24b6:V<>n XIC % Vka " &t+O-.2 94<?AACU*!zNU*U*v!U*"FU*(p,- 5 =.Ah S] "$ -%/3n ;wz@OS@SvF4SFSQ  ($ /:?*@DGP4"o#'<+h14 5v79=@BWEG NA.NMh!s&)@*y/2q57=F?Q@BDH#L$(*Z.168z9@BF'IK  "& .=167:7?BQDcFG-f E zXE E vE yE 4B# )+/137;a=AzEF Cy aU"Z(9*.028:S<?AnCLF A]IoT%u)'+/ 6N9>@fEH9 @*e O!+# +-0 79<@QBDb > O\E~ <]n_"#% ,,/L0|35q69;( BE :X ' #w%:X&U:Xv*o:X+J:X-92B6:<?+ F 8 zh!$+a/p236:8M ?jBD 7 {$z&,?2 :?_C D 5b g  !q%8*4-0 8<ACG 3W+ !D"' /32699>u@DRG 2 K /M &`z()/(/v+R/,H/0d25a A ,BZ" (O+N0~ 7=`?IC *., #.%( ,M/|257Y:[=@wFO*G7*v ( XBEn 4!# &w)b(*(v,(-:(.y2 &pw&p&pv.&p&p"&+0L2 4l =g?$CVDGV $w&+  =TVm$LCEDARLANGUAGEOVERVIEW12FromMesatoCedarTheCedarLanguageisverycloselyrelatedtoMesa.Themostradicalchangeistheprovisionofautomaticdeallocationofdynamicstorage,orgarbagecollection.Severalotherchangesextendtherangeofbindingtimesavailableforsuchimportantattributesasthetypesofvariables.ItisintendedthatmostCedarprogramswillbewritteninthesafesubset,whichimposesanumberofrestrictionsnotpresentinMesatoensurethesafeoperationofthegarbagecollector,andintroducessomenew(safe)featurestomaketheserestrictionstolerable.Thefull(unsafe)languageisgenerally"upwardcompatible"withMesa.Garbagecollection,collectiblestorage,andREFsAlthoughMesapointersaretyped,theyprovidearichsourceofopportunitiesforcreationofsafetyproblems,includingtheclassicaldanglingpointerproblem,whereapointerisusedafterthestorageitreferstohasbeendeallocated,andtheoppositestorageleakproblem,wherestoragebecomesinaccessiblewithoutbeingdeallocatedforreuse.FreeingtheprogrammerfromresponsibilityfordeallocatingstorageatjusttherighttimewasamajorgoalofCedar.ItaddsanewclassofREFtypesthatarejustlikethecorrespondingpointertypesexceptthatthesystemisresponsibleforfreeingthedynamicvariablestheyrefertoaftertheyhavebecomeinaccessible.Cedarprovidesthreetypesofstorage:Frame:Thisisstoragethatisimplicitlyallocatedbyaprocedureapplicationoranimplementationinstantiationtoholdvariablesdeclaredinthecorrespondingscope.Itisalsoimplicitlydeallocated,uponexitfromthescope(e.g.,returnfromtheprocedure).Collectible:ThisisstoragethatisexplicitlyallocatedbyNEW,andimplicitlydeallocatedaftertherearenomoreaccessibleREFstoit.FREEappliedtoaREFvariablewillcauseit(andREFfieldsinthedynamicvariableitrefersto)tobe"NILedout,"butthedynamicvariablewillonlybefreedwhennootherREFstoitremain.Heap:ThisisstoragethatisexplicitlyallocatedbyNEW,anddeallocatedby(unsafe)FREEstatements,asinMesa.Heapstorageisreferencedbypointers,whichmaynotbedereferencedincheckedregions,andshouldnotrefertodynamicvariablescontainingREFs.TheintroductionofcollectiblestoragehassubstantiallyrevisedprogrammingstyleandinterfacedesigninCedar.Whentheprojectwasbeingcontemplated,someMesaprogrammersindicatedthatasmuchas40%oftheirtimewentintodesigningandcheckingthecodetoavoiddanglingpointersandstorageleaks,totrackingerrorsinthiscode,andtowastingtimeintrackingothererrorsbysuspectingstoragedeallocationproblems.WithREFsandareliablegarbagecollectorthatallgoesaway.Frame(static)variablesarestilllessexpensivethandynamicvariables,sinceentireframesareallocatedandfreedonprocedureentryandexit(andthemechanismfordoingithasbeenrathercarefullytuned).However,itisentirelyreasonabletousedynamicvariablesfordatawhoselifetimeisnotcloselyconnectedtoaparticularprocedureapplicationormoduleinstance.Objectsoflargeorvaryingsizearealmostalwayspassedacrossinterfacesbyreference.Definitivemeasurementsonthecostofgarbagecollectionhavenotyetbeenmade,butpreliminarydataindicatesthatitisgenerallylessthan20%.Onlyinveryspecialcircumstancesisheapstorageworththeaddedprogramcomplexityandpotentialforerrors.SafetyAdesirablepropertyofahigh-levellanguagesystemisimplementationindependence.Thismeansthattheeffectsof(evenerroneous)programscanbeunderstoodintermsofthelanguageratherthanrequiringanunderstandingoftheparticularimplementation.MesacomesratherclosetomeetingthisCEDAR4.2vgwg gv#gw$gv+gw,gsG~gx ^]v [2#r()-04d8=?=AG Y? &$-z%Y&Y* v0Y1_Y6.9>CiE XWz XW UXW~v XWXW4% +-Y/3L5 U"Ch}%(5*".0}z2U3^U5v9U9U=C<Db T5 'd!%'*025:5 @#B R # * 036<BC P _zy Mo  !|$gM%2My&Mv JHi"&%0*4+X.2h4 <}>CE HbzNHH#v(H)`H.238:X=@CqH9 F F d!Pz&F'DF+Tv.8F.F38<B% ER  %'i /D2 ;=C D C 7' "#(G)- .>154mw6/C7Cv8C9UC<?YAD_G B E"h$)F* 14'8;1@F @\ =z@\@\v@\@\.u =Ur+z ;vv;^; %<+ -.C4 ;=? :K |$*_,^/ 8X<>@RCp 8 ["$b(-+/35} z 6 v66h!` 'K-w/6/6v16265m ; BF5 w55v! 5"5#%Hw&05'5v(5)z5-/Sw0o51C5v35358=:>?wB5C5vE5F 53gvT $&(b*Kw*3g+3gv-3g-3g.2e474<ADG1dw11v 1! 1"$z /v//B #Y)w*/+/v-/.[/0 8 9w?/?/vBh/B/ .*e} !i ()/3w6a8: BDA,#"$*'/ w6,7o,v8,9f, *  ]%@' /4 =AC (`H"t&L /;26 ?EG & q }!k'*y0K267;AtF %z1=!%(P*/2239?<@B #j Jw (#j #jv"n#j#w#j&.'X,A1b69;> W!$o*.h4< :>KB|G; G8 !$"&),3-5Q9:V<?C . #a%'-258<0A8BE u)X   '3(.38:f=?DG; Q$ z"gQ#Q$yv)Q*Q 1v :<?yB~Dn  VVf! )>,:1457Y=6?BF   (!&*-C17P >AhGR [y  v [M - #).2z/0" 9] vABEK  1R &!(* 1379Iz; < v@ BO Fi n *v %038!NCZ LLnzLRLvLL$,%+.136<@[C KN5#)+:-w 3;58=?C| I:#%(S+Q03I7:=B H_ 5] %a)/v1U5;2B D  !,&( /; 79,>A[D C  $W&(pz ?Z.v AC ,JW Q#_& 3.5v ;F<?A`F + gw ( }(h(w(j( }&q(&(w*F(+;(}-(.^(w/s(0h(2f}5m(5(w7m(8>(9>U@~E 'z Uv $3o  #c% (i)-027w:$;$v@$wA$BE$vF$G$w #Wvu#W !i*) 127;=k>BoCV2"'% +.04o6:> EF R !&(C*.c05S7 -?#P$c&+.F2; 8;q=D-GD !$'B,!-.24* ;j? Fy 9#'q) 0?2,9P;~@ F7 >!.$'$+-R18F;~BKGg{!L$0 +o/ 6;:=C@CFe8 Y!& -8/1M28:RAVCeSN<Z "^ )#w* S*Sv/@S/S02 :?BG}y #D), /05S8:< 0gx #\'k)/538;ACWD  Tw  v  =$(mw) * v/ 0 24 := BDBF/w&+  TVm$ECEDARLANGUAGEOVERVIEW14otherwise,theoutermostblockisUNCHECKEDandallinterfacesareassumedtobeunsafe.Thecheckingattributeisinherited;unlessanestedblockisexplicitlyprefixed,itischeckedoruncheckedlikethetextuallyenclosingblock.Ifasystemconsistsentirelyofsaferegions(andtheinvariantsholdinitially),thenbyinductionthesystemisinvulnerable.However,anerrorinanuncheckedregioncanmakeeventhecheckedregionsvulnerable.ThustheCHECKED/UNCHECKEDboundarylimitsresponsibility,butnotvulnerability.Confidencethaterrorsincheckedregionswillnotcausesystemcrashesisbasedonthetheautomaticenforcementofsafetyrestrictions.Confidencethatuncheckedregionswillnotcausesystemcrashesisbasedontrustthattheyarefreefromerrorsthatviolatethesafetyinvariants.Caveat:TheconversionoftheCedarsystemtosafeinterfacesispresentlyunderway.Theunsafeinterfacesarebeginningtodisappear.Youshouldprogramassafelyasyoucan,butdonotbesurprisedbytheinitialdensityofsafetycomplaintsfromthecompiler.AgoodruleistoprefixeachmodulewithCEDAR,andthentoputTRUSTEDoneachblockaboutwhichthecompilercomplains,afterconvincingyourselfthatthecomplaintisnotyourfault,becauseitresultsfromanecessaryuseofanunsafesysteminterface.ThereasonforeachTRUSTEDshouldbedocumentedinanaccompanyingcomment.TypeconfusionMesaisastronglytypedlanguage,whichmeansthatthetypesofnamesaredeclared,andthatthelanguageimposesrestrictionstokeepvaluesofonetypefrombeingaccidentallyinterpretedasvaluesofanother.Becauseknowledgeofthetypestructureofvaluesinmemoryissoessentialtothegarbagecollector(itmustlocateandfollowREFsinordertodeterminecurrentstorageusage),itisparticularlyvulnerabletoanyoperationsthatcausedatainmemorytobeinterpretedashavingotherthantheirtruetypes.Thus,muchoftheeffortindesigningthesafesubsetwentintoidentifyingallthefeaturesinMesathatallowtype-checkingtobecircumvented(accidentallyordeliberately)anddesigningsafereplacementsfortheimportantusesofthosefeatures.LOOPHOLEisa"typeconverter"inMesathatallowsanyvaluetobetreatedashavinganyspecifiedtype;itisthemostobviousbreachoftypesecurity.Itcausesasafetyproblemonlyifitallowsmistypeddatatobestoredintomemory(i.e.,ifthetargettypecontainsanaddress,suchasapointerorprocedurevalue);otheruseswillintroduceimplementationdependencies,butnotthreatensafety.Withincheckedregions,LOOPHOLEisnotallowedtoproduceavalueofareference-containing(RC)type.NarrowingandtypediscriminationCedarintroducesanumberofnewtypedistinctions,frequentlyleadingtoanumberofseparate,butcloselyrelatedtypes.Itisoftendesirabletocoerceavalueofoneofthesetypesintoavalueofarelatedtype.Wherethetypesaresuchthatitcanbestaticallyguaranteedthatnoinformationwilleverbelostbythecoercion,itiscalledawidening,andisperformedautomaticallywheneverdemandedbycontext(e.g.,assigningaboundvariantvaluetoavariantrecordvariable).Ingeneral,conversionintheotherdirectionrequiresaruntimechecktoensurethatinformationisnotbeinglost.Tomakethepossibilityofsuchfailureexplicitintheprogramtext,theNARROWtypeconvertermaybeapplied(andmayincludeacatchphrasetohandletheNarrowFaultexception).Thebuilt-intestISTYPEcanbeappliedtoavaluetodeterminewhetheritcanbenarrowedtoaspecifiedtypewithouterror.Ifso,itissaidtosatisfythetype'spredicate.Ifthetargettypeofanarrowingisuniquelydeterminedbycontext,itneednotbeanexplicitargumenttoNARROW.DelayedbindingCEDAR4.2vgwg gv#gw$gv+gw,gsG~gv _/ e)wC_/(_/v&._/&_/(* 03/8:[A Tn U8Ci$F')-Z168><4>O@C8 R  G &)058K:>CHH# Q  7!k%a(/,.2 y NvNN  $M(*- 35n;sB?E4 L `p $(y./3517:=>?@AC KU E0 #&)E/W04T7+8:D>EAuFtw Iv IIw8IIvII!/$p(A,30Q28 z?wI@'IB H'hC!dv$H$H*+y/3;4k:<>@E F_ XwF_BF_v"]F_"F_&( 02Q4A =Cz C Hv ?[>"<&N*-h/3d5!9i;AD]G/ >  $&)P,Z/3 : BCG AH 4, ); 1w 1q1v11 "(%(,/I246w; <A#C 0  p'i!$')+/60Z4@9<>.?C .a nS! #`'6*;/1x69;x<ASC  ,55 ' 03b5;H?DA +w ++v+(+0 i%&*,N-x:$=z 'J/ v $s = #&J - 49;y<B C " }- M&.',A-{15257;>ABFHe !$ol!$&((* 0W 7n:A EG/ . D $+&*- 5r79=@CDG/  l$T ,"(+'w-.mv3H36W6@BF|HE + !$&t*-z01v6' @_?'"<#) 1<3g8:I=@zBD wvy I8w&+  TVm$CEDARLANGUAGEOVERVIEW15Adesirablepropertyofahigh-levelprogramminglanguageisthatisallowawiderangeofbindingtimes:thatis,itshouldallowtheprogrammermaximalcontroloverwhentheattributesofaparticularvariablearedetermined,withdifferentchoicesnotrequiringchangesinallexpressionscontainingthevariable.Examplesofsuchattributesareitstype,storageallocationmethod,implementation(forabstractobjects),andactualvalue;examplesofbindingtimesincludeprogram-writingtime,compilation,configurationbinding,programinitialization,blockentry,andstatementexecution.Generallyspeaking,deferringthebindingofanattributeleadstogreatergeneralityintheprogramatthecostofdecreasedstaticcheckabilityand(often)lowerruntimeefficiency.ExperiencewithlanguageslikeLISPandSmalltalk,inwhichmostbindingisdonedynamically,showsthatitismucheasiertowritecertainkindsofprograms,iftypeand/orimplementationbindingcanbedeferred.Programmingtools(debuggers,performancemonitors)andknowledgerepresentationsystemsaretypicalexamples.Butfewprogramstakefulladvantageofthisflexibilityveryoften.Cedarwasdesignedtotakeadvantageofearlybinding,asMesadoes,buttoallowcertainbindingstobeexplicitlydeferred.Dynamictyping,REFANY,anddynamicallytypedprocedurevariablesMesaprovidesverylimitedvariabilityinthebindingtimeofanobject'stype.Variantrecordsallowadeferredchoicebetweenspecificenumeratedalternatives,andsequencesallowdeferringthespecificationofanobject'slengthuntilitisallocated.Otherwise,alltypesmustbestatic.ThismakesitvirtuallyimpossibletoavoidLOOPHOLEsandadhoctypetaggingschemeswhenwritingschedulers,sorters,outputformatters,etc.thatmustoperateonobjectsofunpredictabletype.Cedar'ssolutiontothisproblemrequirestwonewmechanisms:aruntimerepresentationfortypes,andawaytoassociateatypewithanobjectatruntimethatisguaranteedconsistentwiththetypesystemandstaticchecking.(NotethatCedaradoptstheviewthatanobject'stypeisinherentintheobjectitself,ratherthaninthewaytheobjectisreferredto.)TYPEisatypeintheCedarLanguage.The"structuringmethods"(e.g.,ARRAY,RECORD,andREF)areviewedasoperatorsthattaketypeargumentsandreturntypevaluesasresults.Inthecurrentlanguage,theargumentstosuchoperatorsmustbestatic(compile-time)constants.ANYisnotatypeinCedar,butcanstandinplaceofatypeintheargumentstotwooperators:REFandPROC.AREFANYvaluemayrefertoadynamicvariableofanytypewhatsoever.ThusaREFTvalue,foranyT,canbewidenedtoaREFANYvalue.ButaREFANYvaluecannotbedirectlydereferenced,becausethetypeoftheresultisnotstatic.ThediscriminatingselectionstatementhasbeengeneralizedtoallowdiscriminationonthereferenttypeofaREFANY;withineachselectablestatement,thetypeis(statically)knowntobethetypespecifiedinitstestitem.NARROWcanalsobeusedtosafelyconvertaREFANYvaluebacktoaREFTvalue;ISTYPEcanbeusedtocheckwhetherNARROWwillsucceed.APROCtypemayalsohaveANYinplaceofthetypeofitsformalparameterrecordtypeand/orresultrecordtype.PROCvalueswithspecificdomainsandrangesmaybewidenedtothesedynamictypes,andlatertestedandnarrowedanalogouslytoREFANYs.Theymustbenarrowedbeforebeingapplied.Inprinciple,eachvalueinCedarcarriesitssyntactictypewithitatalltimes.Inpractice,almostallanalysisandcheckingoftypesisdonebythecompiler,andbothspaceandtimeefficiencyaregainedbynotstoringconstanttypeswithvalues.However,thesymboltablesproducedbythecompilercontainenoughinformationtorecoveranytypeondemand,madeavailablethroughastandardpackage.RuntimeTypesprovidestype-conversionroutinesinbothdirectionsbetweentypedvalues(withtypeRTTypesBasic.TV)andordinaryCedarvalues,andnumerousoperationsontypedvaluestoexaminethetypeandstructureofatypedvalue,tochangeitsattributes,etc.ThusitispossibletowriteaprogramCEDAR4.2vgwg gv#gw$gv+gw,gsG~gv _,<i " +1V257:;?.BzD_,Ef_, ]v ]k]> &,8047:B @bB%CY [= h"]'A)/5069 @[ G/ Z6kEh n"$~',{ 28 ADx XI"7$W)-3+=A V i|%)-0D6 =C U@Lj*" $?%* 025:ACC S v  J %L Q C w!~Q!Qv#Q$dQ& -@/3Z6<+=Ag Ov?> %Z)*1U25: Dy M  W (B 0d69@ L'U0!'*-@3583 >gAEw J Z B#)t+Q/(257l;C?EG H z E{!EEz;EE $4'-v B:R $%( -0>138<2AE @ Mlx % -M/6$9?rA >  vl $O +V-r1346:>9BD! =D Ew=D=DvA=D7=Dz=D =D!v$*=D$=D''+1:49} @rE ; g5 %+& / 9!G &"(+ 35):e C`E 7z r $&6+\./u 6v <?BE 5  %'e*-P/2478v=?AE 4+  -d}%+ 1w 1h1v311$'u /5Ww8191v<1w=1>1vB1Cz1wF11G1vHw1 0 fT#2* -149C;1@B&D .a j$'h)Y, 6' +w ++v+6+3b ="&\'+-5.S1X25O;=@6 wF+G+v *>w *> K*>v*> 'w;''v'' &S+-E/2 :l=w?'?'zA'vC4'G7 &z v&v ^&#rxw&_&)v & &#&w'&(l&*6v-&-&056; DA $t Sk,fW@" +07 9< D0E " -LO w""""$v'M"(=",u/ 5 AB !&{3.v-!#'-w(P!&)#!&v-3!&-!&/2479=BtwC!&D{!&F_v ~ w~~ze~v~w~]~v T~ ~"$( )-w2~3~v8~9~;Y wOv\+ wh<v!r!#6&(+".G026= AD [ Vw[[v[l[!S&e,.3f68>V@,C  %B!b )w*+-v06015i8; APE   { n!0%'`,03 4t6 7;=C<G j " $&,/m26}9CD ) 8!+$&,07<>C  o<#d(*.V 4z::>`vBC&F MV!&k)/ 6%8#;@AG/  Vm z"3&( /E15d68<=?BBDw&+  TVm$CEDARLANGUAGEOVERVIEW16thatdealswithanygivenCedarvalueortypewithoutanticipatingthespecifictypewhentheprogramiswritten.ProgramssuchasBugBane(theCedardebugger)absolutelyrequiresuchflexibility.Thecurrentimplementationistooslowtobeusedeffectivelybyclientprogramsasasubstitutefortruepolymorphisminthelanguage,butissuitableforexaminingandchangingvariablesinteractivelywiththeCedardebugger.MiscellaneousAlthoughCedarwasnotintendedasaresearchprojectinprogramminglanguages,itsdeveloperswerenotimmunetothetemptationtomakeMesabetterinwaysthatwerenotstrictlyrequiredtoenablethenewprogrammingenvironment.Thissectiondiscussesafewofthesenewfeatures.TypesasclustersofoperationsEachtypehasanassociatedclusterofoperations.Themainpurposeofthisassociationistosupportastyleof"objectoriented"notation.Usingarecord-likenotation,aprocedure"field"willbelookedupintheclusteroftheobject'stype,andthenappliedtotheobjectandtheotherarguments.ItispreferredstyleinCedartousethisobjectnotationininvokingoperationsofinterfacesdesignedtosupportit.Consulttherelevantpackagedocumentationifindoubt.Eachbuilt-intypeandtypeconstructorinCedarimplicitlysuppliesastandardcluster.Theclusterextensionmechanismisthateachopaqueorrecordtypedefinedinainterfaceacquiresallproceduresdeclaredinthesamemoduleaspartsofitscluster.ROPEsandIOMesaSTRINGsareratherawkwardobjects,havingbeentunedforefficiencyinasmall-machine(Alto)world,ratherthanforflexibilityandconvenience.TheyarePOINTERstofixed-lengthsequencesofcharacters.Considerablecareisrequiredtoavoidsurprisingresults,evenforratherstraightforwardstring-processingapplications.CedarROPEs,ontheotherhand,aresomewhatheavier-weight,moreconvenienttouse,andlesspronetosurprises.Severaldifferentimplementationsofropes,efficientfordifferentpurposes,providethesameinterface.RopeisaCedarpackagethatsupportsthecreationandmanipulationofimmutablereference-countedsequencesofcharacters.Proceduresareprovidedforconcatenation,takingsubstrings,scanning,andotheroperations.Aclientcanprovidespecializedimplementationsforropeobjects.ThestandardimplementationattemptstoavoidcopyingwhenperformingSubstr,ConcatandReplaceoperations.TheRopepackageisthestandardsupportforsequencesofcharactersinCedar,.Mostofthecommonoperationsoninput/outputstreams,plusstringconversionsthatarecommonlyusedindealingwithinputorformattingoutput,havebeencollectedintheIOinterface.Implementationsareavailableforstreaminterfacestoallcommondevices,andtoallowropesandstreamstobereadilyinterconverted.LISTsandATOMsCedarincludesLISTOFasanewtypeconstructorforsingly-linked(byREFs)lists,andaconstructorforlistvaluesthatmimicsthatofLISP,avoidingtheneedforalotofNEWsorCONSs.TheanalogofLISP'sCARandCDRareprovidedbythestandardfieldsfirstandrest.UnlikeLISP,Cedarlistsarestaticallytyped(althoughtheelementtypemaybeREFANY).Cedaralsohasabuilt-intypeATOM,whichcanbeusedforvaluesthatareuniquelydeterminedbytheirprintnames.Anyropecanbeconvertedtoanatomandconversely;theadvantageofatomsisthat,CEDAR4.2vgwg gv#gw$gv+gw,gsG~gv _/ Rz(!#&+ 3P5:=AD ] Xb_!;$(,. 519=+ [ J '!%&(+ 24|8:>J?A GR Ye +r #J$*,_3(5;A W f~y To v Q q"H$%U*/1U : @B Oy * !J$(,g.1L47F9>CE) M K9  2#L'-.1z3369z J ] v G3 u zG3tG3v"$G3"G3# *-16R8: AyBD E 8 $}% ,2H3j9>pABG} C  `xm!$)+L-14{6:z Ajrk+3"8$(.2/5q <= C ? Tu$Y -/ 0 =G+ : %I'+$ 1M67=~BFE) ;a#%*)-K2]45Y;@B 9q~!"${ 6z 66{676v 3[w3[&3[v3[-3["(,0N4l6 =??@w 1g "V%" -\0w3c14 1v8191;a C" 0   %@'* 1]69~;? .e w!9.e" .ev$J.e$.e%(:*.25u<&E , b  &+1;=AGR + (AV#&+"- 57>Y &A  !') 26 =_CPE %L R!J (36:@jC # F#'j .3/7:? F ! OI!U#)+ 2%3 & Z"O */26r =@B  z! "'D*{-3t5w7b7v99i> 3 JV  "(r-0_259bAB4 G A~Ow 6G Gv!G"G(+.y0249w6 G6Gv8G9Gw;G<Gv>G?vG@iCYG w  =v  wvw v#!$u*Ez...v111z44v607A<w<=Wv>?CF  i!5$D'Hw)9* +v.x. } w } }v" }#e }'o)+/1S5}8G:@N G  ' .%')d,/ 68?fAE Fhw&+  uTVm$CEDARLANGUAGEOVERVIEW17unlikeropes,itisverycheaptocomparethemforequality;atomsmayalsohavepropertylists.Atomliteralsarejustnamesprefixedby$.CEDAR4.2vgwg gv#gw$gv+gw,gsG~gv _,:\Hly=#')/369z=_,=_,BvD_,E_, ]\Qw&+ TVm$rCEDARLANGUAGEOVERVIEW18ConvertingMesaProgramstoCedarJimMorrisThissectionassumesyoualreadyknowhowtoprograminMesa(orthatyouhaveaMesaprogramtobeconverted),andisintendedtoexplainthedifferencesforprogramminginCedar.SimpleprogramsLet'ssupposeyouwanttorunasimpleprograminCedar.IfanexistingMesa5or6programusesfairlyvanillastuff,it'seasytoconvert:Thenamesofmostinterfacesandsomeprocedureshavechanged,butthefunctionalityisbasicallythesame.ThemostobviousdifferenceswillbewithstringsandI/O.Youshouldonlyneedtoknowabouttwointerfacesforthese:RopeandIO,respectively.Ingeneral,theCedar/Pilotcommunityhasdroppedtheuseof"Defs"asasuffixfordefinitionfilenames,andintroducedthesuffix"Impl"forimplementationfiles;e.g."InlineDefs"became"Inline".Here'swhatyouneedtodotoyourMesa5or6program:ChangeallSTRINGstoROPEs(actuallyRope.ROPE).Removeallallocationsanddeallocationsofstrings.ChangeallreferencestoStringDefsroutinestouseRopeorIOroutines.Ropeprovidesprocedurestoparseandmanipulateropes.IOprovidesprocedurestoconvertROPEstonumbersandbackasnotedbelow.Onecannowputspecialcharactersinropeliteralsbyusingtheescapecharacter"\"."...\n..."insertsacarriagereturn(newline),"...\t..."atab,"...\\..."abackslash,and"...\123..."thecharacterwhoseoctalcodeis123.NoteaROPEisimmutable,unlikeastring.AppendingacharactercreatesanewROPE.Youshouldusespecificsubrangesfornumericvariableswheneverpossible.Ifyoudon'tknowtherange,useINT(32-bitinteger),unlessyouknowyoudon'tneedthatbiganumberandknowyouneedefficiency.InthosecasesuseINTEGERorNAT=[0..77777B].AvoidusingCARDINALSorLONGCARDINALS;theirmainuseisindealingwithSTRINGs.ThecompilerrecognizestheabbreviationINTforLONGINTEGER,BOOLforBOOLEAN,CHARforCHARACTER,andPROCforPROCEDURE.ChangeallreferencestoI/Opackagesofallkinds(streams,files,TTY)touseequivalentIOroutines.IOistheonlyinterfaceyoushouldneedtoknowaboutforI/Oofalmostanytypeofvariableorconstant(ROPE,INT,etc.)toalmostanytypeofdevice(keyboard,display,files,temporarybufferetc.).IOcontains:AsetofCreateXroutinesforeachkindofstreamXfile,display,etc.AsetofGetXroutinesforeachtypeX(integers,ropes,etc.)APutFroutinethatcanbeusedwithanytype(integers,ropes,etc.)viaasetofinlineprocedures(int,rope,etc.)whichareusedtotagthetypeofthearguments.ItalsoprovidesaformatargumentwhichmaybeusedtogetFORTRAN-styleformattingofoutput.Forexample,theformat"%g"printsalmostanythingindefaultfree-format:stream.PutF["Thesumof%gand%gis%g.\n",int[x],int[y],int[x+y]]APutFRroutinethatisidenticaltoPutFexceptitproducesaropeasoutputinsteadofputtingitsresultonastream,andaRSroutinethatmakesaropelooklikeastreamsothattheGetXprocedurescanbeused.Thusonecanconvertvarioustypestoandfromropes,e.g.thefollowingcodewhichconvertsanintegertoaropeandback:r:ROPE_PutFR[,int[i]];j:INT_GetInt[RS[r]];MakeuseofLISTsandSEQUENCEsinsteadofARRAYsandDESCRIPTORsforARRAYs.TheinterfaceListcontainssomeusefulroutines.CEDAR4.2vgwg gv#gw$gv+gw,gsG~gx ^ KH Yy%(^' ^)v [WN!$')y/04K69J;?:@]D Y  j A%'t .o0 9?:y V|v S`HW %!*,Y02F449<<>?A F Q h O "!%w ,/58!: BDN$/ L5 B S"$'J+.149t<@AEJ| #w&RJ&Jv'J(uJ H| $'?,/"13N79:>@ G%Ft3 -!%r*7,| 6b9}=?Q=vBC=B=C;!9$U&*,1@ 79<AZCnG/:K' x  !#$%[&+0,W15 <=>u?M@ABD(ENH8~X "$I%7&%)}*k+X,/h5c9=@`ADHew6vK66 !-"W&-.49E:ow=]6>16v 5K"'$m)/5;~= ?CgG/3fwW3f3fv3f@3f/#'*^.04P7:k<=CE1` "%hw'1( 1v-A1-1w.1/1v113]1 :>wB1B1v0w0K0f v0t0!J$'7(*M/w26020v7 070:@u G.p w.p.pv.p.pwQ.p .p!'v*.p+ .pw,.p-|.p3 v6.p7=.pw8.p9.pv@.pA.pwC.pD-.pvG .pG.pw, v *} 8#%'f+0379=; wB5*B*vC*DX*)4wT)4v)4GM!%)6*.~2M4w708=(?BDX'wu'I'3v''!#'*-/X3 :o?vB%Zw%v?%o#z#v4#!$( )z.I#v/G#3i8to" z" v"  #Mz&]" v'" -1o 2"%(h+Z 1.58:!;,=+>B so #&G'*,m/l13c :Y;>|CE "n%'1)f 4 :&)3*/37=/oH_=#%c(- .W4(5F8j: >rCDh/1V!#$'C,.34,7X:m=>:BDeG/zvj !,#5&*w-;/49=m?3BERz!%+O-@1347:1dwddvdd9~Bw ~ v $w  vJ  w  v"3 " &w( ) v- .h w0 1p v8 9= w; ; v? @ Cr ' w&+  TVm$}CEDARLANGUAGEOVERVIEW19NewlanguagefeaturesThechangesintheCedarlanguagefromMesa6arefairlyeasytounderstandforsimpleprograms:(a)REFsprovideautomaticdeallocationandeasierallocation:Node:TYPE=REFRec;Rec:TYPE=RECORD[first:INTEGER,rest:Node];...x:Node_NEW[Rec_[5,NIL]];(b)RuntimetypesviaREFANYgivelooserbinding:TNode:REFBlRec;Node:REFB2Rec;x:Node_...;t:TNode_...;q:REFANY;...q_t;q_x;--bothofthesearelegalt_NARROW[q];--raisesNarrowRefFaultifqisnotaTNode--q^_Eisalwaysillegal.YoucannotupdatethroughaREFANY....--typecanalsobecheckedexplicitly:WITHqSELECTFROMm:TNode=>{t_m;q_m.lson};n:Node=>{x_n;q_n.rest};ELSEERROR;--orIFISTYPE[q,TNode]THEN{t_NARROW[q];q_t.lson}ELSEIFISTYPE[q,Node]THEN{x_NARROW[q];q_x.rest}ELSEERROR.REFANYispreferredtotheuseofvariantrecords.(c)Listsarebuiltintothelanguage:Node:TYPE=LISTOFINT;x:Node_CONS[5,NIL];y:Node_LIST[5,6];--sameasCONS[5,CONS[6,NIL]]i:INT_y.first;--iis5z:Node_y.rest;--zisCONS[6,NIL]FORl:Node_y,l.restUNTILl=NILDO...(d)ROPEs,ATOMs,SEQUENCEs,andINTsarealsobuilt-in.(e)Toprotectyourselfandthegarbagecollectorfromobscureerrorsyoushouldprograminthesafesubsetofthelanguage.Togetaprogramintothesafesubsetprefixeachmodule(PROGRAM,MONITOR,orDEFINITIONS)withthewordCEDAR.Thecompilerwillthentellyouwhenyouarestrayingoutsidethesafesubset.YoucanwavethecompileroffanyblockbyplacingthewordTRUSTEDbeforeit.Ifyoucallaproceduredeclaredinanunsafeinterface(i.e.,onethatdoesn'tstartwithCEDARDEFINITIONS),thecompilerwillcomplainunlessthecallisinaTRUSTEDblock.Mostofthehigh-levelinterfacesintheCedarsystemarenowsafe.RestrictionsofthesafelanguageThe@operatorisnotpermitted.Therearethreegeneralwaystocopewiththisrestriction:specializing,copying,andindirecting.Forexample,supposeyouhaveaprogramthatsaysW:ARRAY[0..100)OFZ;CEDAR4.2vgwg gv#gw$gv+gw,gsG~gy _, v [Sz[$[v"|["[%)*-035E C YwYYvYYE $'+ ~XGwXGXG~XGwXGXG~XGXGVwVV~/VwVV~!RV!Vw$V% V~*V+V-TmISQ?wSQSQ~SQSQ t"w#SQ$SQ~&LSQ&SQv Qb<wyQbMQb)v "Qb Qb#'~OwOO~`OGONwNN~NqNLl?wS.JAIwVI*I~GumIEj!W!#M&))D&wD&D&~D&D&g# -/Z0245B~ Q$',@06 w74B~8B~9~@mI?/_P" wS=~=w,==~d;B!#{%'/(z*d:8( "r#%'(wd8~6w5A~d5A+5Aw !5A 5A~#5A$|5A%ow&5A'5A~,5A-m5A.01w3d~3p3 Mw$3%83~(*3(3*w+3,3~1E32 33m46Ew10K0~)0K0K L"%!&+vv .\Yy~,w,,~,w,,~+ ?w+ f+ ~+ + w+ + ~"+ )f?w)fT)f~f)f)f!"{%w')f(q)f~+$)f+)fw,)f-|)f~00)f0)fw1)f2)f~4)f'w'\'~;''  _&| 4w!&"k&~%&%&w&&'&$o~e$o$o!w" $o"$o~&$o&$ow'$o($o*W,-yv "w""v2""w"f"v ""wn" "v"2" w""#/"v$"%"(-* *M! %+/ 4<8N;!?EeG/zv#%e')R/2347A:DTFO#&(-03069>A CGw\v!"G%')!+.z/6>;=?CNN!lw$N%`N) v1N2N4p:9<BG/ywv":%'*7 0 68;I?DFy  9nz aG2t va a#%)6-1258; A p' e!'$)-!.K36~ w  ~  wz W z~3 w&+ TVm$CEDARLANGUAGEOVERVIEW20P[@W];FORiIN[0..100)DO...Q[@W[i]]...ENDLOOP;Toeliminatethefirst@byspecializingwewouldmakeacopyoftheprocedurePthatdealtwiththeWdirectlynotverysatisfactory.Toeliminatethefirst@bycopyingwewouldpassthearrayWinbyvalueandbackbyresultalsonotverysatisfactory.Itisbesttodealwiththefirst@byindirecting;justallocateWfromcollectablestorage,writingW:REFARRAY[0..100)OFZ=NEW[ARRAY[0..100)OFZ];P[W];Eliminatingthesecond@byspecializationisplausibleifQknowsitisalwaysdealingwitharrayelements:passareferencetoWalongwithanindex.Otherwise,decidingbetweencopyingandindirectingdependsuponthesizeofaZ.Ifitissmallcopyit,writing"W[i]_Q[W[i]]".Ifitisbigcreatereferencestoitandpassthose,writingW:REFARRAY[0..100)OFREFZ;P[W];FORiIN[0..100)DO...Q[W[i]]...ENDLOOP;Theformofvariantrecorddiscriminationthatdoesnotcopythevaluetoanewlocationcannotbeused.Supposeyouhaveavariant-recorddatastructurelikeT:TYPE=REFTR;TR:TYPE=RECORD[SELECTt:*FROMname,string=>[x:ROPE];link=>[i:INT,r:T];ENDCASE];andareaccustomedtoperformingdiscriminationslikee:T;WITHx:e^SELECTFROMname,string=>"Statementsusingx";link=>{S1[x.i];S2[@x]};ENDCASE;YoushoulddeclareasetofREFstoboundvarianttypeslikeName:TYPE=REFnameTR;String:TYPE=REFstringTR;Link:TYPE=REFlinkTR;andrewritethediscriminationtobeWITHeSELECTFROMx:Name=>"Statementsusingx";x:String=>"Statementsusingx";x:Link=>{S1[x.i];S2[x]};ENDCASE;ThetypeofxisnowaREFtype,notaTR,sovariousothertypesneedtobeadjustedandthe@inS2isnolongerneeded.If"Statementsusingx"isalargeblock,youwillprobablywanttointroduceaproceduretoavoidcopyingit.Variantrecordscannotbeoverwritten.Similiartechniquescanbeusedforsanitizingaprogramthatoverwritesvariantrecords.AssumingthedeclarationsofTandTRfromabove,supposeyouwantedtowritex:T_NEW[TR_[name["END"]];x^_[link[5,x]];Thespecialization/copyingtechniqueistosimplyupdatethethingthatpointsattherecord,writing"x_NEW[TR_[link[5,x]]]".However,ifyoudon'tknowalltheplacesthatpointattherecord,youmustintroduceanotherlevelofindirection,writingT:TYPE=REFREFTR;x:T_NEW[REFTR_NEW[TR_[rope["END"]]];CEDAR4.2vgwg gv#gw$gv+gw,gsG~g~_,w]~]w]]~G]]w]]~D] ]&!&'w(])m]v [ )yks "%)A-.813\5%@DEG X z t#$ *,<-02}58;4>"@B0 V r "~U?wU?U?~YU?U?w*U?U?*~ MU?w"2U?#U?~)U?*,U?w.U?/wU?0~1SU?1U?Sv Q : +d &'-/j1?57S8=BF PIT #%) 0D5;@B NO+wL  l#'C(-1?28:;d<?C L  ~KSwKSKS~YKSKSw*KSKS*!~"KSIwH~HwHH~GHHwHH~DH H$%&ww'SH( Hz ED~ &])F,a.24{89;#=C;G Cv UCC "%+~B:wB:]B:~B:wB:B:~B:wB:@w@w@~@w@@ ~#Z@#@w%w@&0@~>dwu> I>~">=CCw=Cq=C~=CG=CEw;~_;;v 9  b B(~8Mbw6~]66 w66~4d %(3VCw1v 0 w5^{w400vN00$X(,~.`wT.` .`~.`w.`d.`~@.`.`,wb,,~,w,r,~N,,!$+w+S+~+w++~++Sv )i K Zw'~L'wv''.~&~/ $$s~, $"~dw!#v | $&wN|"|v|l|c !$&+R.2579x>ADEG  z K $&()k,1.46<@HBHe -o z Q v#$) /2x4j79 @A0F  .a #. *,-0396;@RCG c~mweN~qXr Bv m  "o$%(-7/396::;>ABG w w _vi{ " $(S,-0[4q7=:CrF' "h! !i~ ww w] w~ ww w w@~ w w ~ww _ 2~ x w  ~" " $&w&+ TVm$CEDARLANGUAGEOVERVIEW21x^_NEW[TR_[link[5,x]]];Unsafeprocedurescannotbepassedasargumentstosafeones.Thesymptomofaviolationofthisruleisgenerallyamessagecomplainingaboutanincorrecttypewhenthereisnoobvioustypemismatch.AllproceduretypesinaninterfaceprefixedbyCEDARareimplicitlyprefixedwithSAFE.ThesimplestthingtodoistoputSAFEinfrontofPROCintheargumentproceduredeclaration,andputTRUSTEDinfrontofitsbody.AswithallusesofTRUSTED,youshouldverifythatthesafetyinvariantsareactuallymaintained,anddocumentthereasonfortheTRUSTEDinacomment.CEDAR4.2vgwg gv#gw$gv+gw,gsG~g~_,wB_,*_,~M_,4_,Oz \W "$+=,/v3N\46\6<?[EF Z N "%'-y0z4 78:@Cz YKv GYK YKCF%~w'YK(WYKv,YK,YK.| 4:.w=[YK=YKv@@YKA.YKD W ~+/FwWdWvWuW/w W!Wv$qW$W&({.5$ <?AwAWBzWvGWGW U j.515w U!Uv&cU'JU* .25c7; BDx TU l#!I#w%TU&TUv+TU,TU-h.w&+ TVm$wCEDARLANGUAGEOVERVIEW22ForMoreInformation...CedarLanguageSyntaxThisisaone-pagereferencegrammardescribingthecompletesyntaxoftheCedarLanguage,inacompactvariationonBNFdevelopedbyButlerLampson.Keepithandyasyouwriteprograms.Itprovidesarelativelycompactsourceofinformationontheexactformofconstructsacceptedbythecompiler.Itwillalsoalertyoutomuchoftheavailablevarietyinthelanguagebutofcourse,noteverysyntacticallyvalidprogrammakessemanticsense.TheparsinggrammarusedbythecompilerissomewhatlargerandmorecomplexthantheReferenceGrammar.SomeofthisisfortechnicalreasonsassociatedwithLALR(1)parsing,andsomeofittoenablethecompilertomakecertainsemanticdistinctionswhileparsing.Thedifferencesshouldbeinvisiblewhendealingwithcorrectprograms,butmayaffecttheerrormessagesgivenforincorrectones.AnnotatedCedarExamplesThisdocumentcontainsfourcomplete,runnableCedarprogramschosentoillustratetheuseofmostofthemajorfeaturesofthelanguage,andtoprovideanintroductiontothestyleofprogrammingthatispreferredinCedar.YoushouldcertainlyinvesttimeinstudyingthembeforeattemptingtowriteCedarprograms.Ifyouareoneofthosewholearnsbestfromexamples,youmayfindthemvirtuallytheonlytutorialinformationyouneedtolearnthelanguage.TheseexampleshavebeenchosensothattheyarealsousefulprototypesofkindsofprogramsyoumaywanttowriteinCedar.IfyouarelikemostCedarprogrammers,youwillprobablyfinditeasiertostartfromsuchaprototype,andchangeittodowhatyouwant,thantoenterawholeprogram"fromscratch."StylizingCedarProgramsBecauseCedarprogrammerssofrequentlyreadeachother'scode,itisconsideredgoodcitizenshiptoadheretocertainstylisticconventions.StylizingCedarProgramsdiscussesthegenerallyagreedconventions.Youcansaveyourselfalotoftyping,andproducenicelyformattedcodeatthesametime,byusingTioga'sabbreviationexpansionmechanismtogenerateallthehigh-levelstructureofyourprogram(atleast,allthebitsthataren'tsimplycopied).ThefileCedar.abbreviationsliststheavailablemacrosandtheirexpansions;youcanaddyourownfavorites.CedarProgramStyleSheetThisisanannotatedprototypethatyouwillprobablywanttokeepclosetohand,becauseitcompactlyillustratesthemostimportantprinciplesfromthepreviousdocument.CedarLanguageReferenceManualEventually,thisisintendedtobeaprecisedefinitionofthecompletesyntaxandsemanticsoftheCedarLanguage.Itisstillincomplete.Theformaldefinitionofthelanguageisgivenintermsofakernellanguage,intowhichallCedarconstructscanbedesugaredtodeterminetheirprecisesemantics.TheReferenceManualcontainsboththedefinitionofthekernel,andanexplanationofthedesugarings.ItalsocontainsseveraltablesthatcollectimportantinformationabouttheprimitivetypesandtypeconstructorsofCedar.CEDAR4.2vgwg gv#gw$gv+gw,gsG~gx ^  y [ 7v XVI~px$^ +-l3_79r;?FHe V]"%$Q(/?3&49 :=A}H U !/# *,/~3068 ?:E G/ S`^&!#%+014 =(>CqE Q  $ O=k$!+&(.n2>48S=@C  Mv v#i(r / 2P8=@D{F_G K.'!' /73*8; BG JGYb%(7+0.1E4:|>%@WFy Fv C \L$x*5.9488:P ?B-DF2 B Lx!$`&+,-& 569)% F @Y 3o %*-W/248=" D6F >+\#&*-187:k=@D! =  Ke9 z!#')b :W!#&)+.2 9;R?@F 8 @_p!$'+ 47^:?BDG 7@ x N#$b&(,+.U25F6:;?Ew 5y 2Jv .  S &*!-Z1568W ?EB -S  %-+)/6 <*>E + )00(]{.#&j+/592:=@CE ' N$&[+-0p 6<>AG} % yyxi%;(#*7 9BH9 z `" ) ,s.4by  7v U !"' -/28 <^?$EhG/ * 2 c($e%)+W/-0z2(2226Zv;2<}2?aC{Ew  izvT#&+ 2A5);@FS  b } (),J 4,58>BF << ' "i(P+.1 9X;w&+  $TVm$\CEDARLANGUAGEOVERVIEW23CedarLanguageReferenceSummarySheetsThisisintendedtobetheessenceoftheentireCedarLanguagecarefullycondensedintotwopagesforreadyreference.Itcoversbothsyntaxandsemantics,withexamplesandnotes.Itisdefinitelynotforthosewithweakeyes,andshouldprobablynotevenbereaduntilyouhavestudiedtheReferenceManualproper.Butitshouldbeveryhelpfulincheckingdetailsthatyoumayhaveforgotten.Keepithandy.CedarCatalogSincesomuchCedarprogrammingisdone"atthecomponentlevel,"youneedtoknowwhatpackagesandtoolsareavailableandwhattheydo.Ingeneral,fulldocumentation(oratleastthebestavailableapproximationthereto)foreachcomponentisstoredon[Indigo]Documentation>,orisreferencedinthecomponent'sDFfile,storedon[Indigo]Top>.Theproblemisfindingoutwhichcomponentsyoushouldbeinterestedin.That'swheretheCedarCatalogcomesinhandy.ItcontainsasomewhatstructuredlistofallthecomponentsinCedarconsidered"interesting"bytheirmaintainers.Acomponentmaybeinterestingbecauseofwhatitprovides(yourprogrammaybecomeaclient),becauseofwhatitdoes(youpersonallymaybecomeauser),orbecauseofhowitdoesit(youmaystudyitorcopysomepartofitinyourprogram).Foreachentry,theCatalogindicateswhyitisconsideredinteresting,andhowtoacquiredocumentationandthecomponentitself.Italsoidentifiesthemaintainer,whoistheultimatesourceofadviceandhelp.Mesa5.0ManualTheMesaLanguageManual,Version5.0,PARCTechnicalReportCSL-79-3,isthemostrecentself-containedmanualontheMesaLanguage.Itfallssomewherebetweenatutorialandareferencemanual,andmanyusershavecomplainedthatitisn'tentirelysatisfactoryforeitherpurpose.ButifyouneedmoreinformationabouttheMesa-likepartsofCedar,itmaybeyourbestsource.Chapter4givesthedetailsofMesa'sbasiccontrolconstructs.Chapter5tellsallaboutprocedures.Chapter7goesintomoredetailthanyouprobablywantaboutthefinepointsofmodules,programs,andconfigurations.YoumaybebetteroffextrapolatingfromtheAnnotatedCedarExamples.Chapter8givessomeofthegorydetailsofexceptionsandexceptionhandling.Itiseasytogetintroubleunlessyouusetheminstraightforwardways.Chapter10providesaprettyreasonablediscussionofhowtomakeeffectiveuseofprocesses,monitors,conditionvariables,etc.WhotoseeIfyouhaven'tmanagedtofindinformationthatyouwantafteryouhavelookedinwhatyouconsidertobetheobviousplaces(orifyoudon'tunderstandwhatyouhavefound),don'thesitatetoask.AlmostanyoneinCSLisafountofwisdom,willingtobeaskedalmostanyquestiononalmostanysubject.(Ofcourse,theanswersaren'tequallyreliable,butyoucan'thaveeverything.)Ifthefirstpersonyouaskdoesn'tknowtheanswer,chancesaregoodthatyou'llgetapointertoeitherapersonordocumentthatwillhavetheanswer.Morespecificallyherearesomegoodpeopletoask:JohnMaxwellassistantoffirstresortforgeneralproblemswithCedarRussAtkinsonBugBaneCEDAR4.2vgwg gv#gw$gv+gw,gsG~gy _, 7 v [(q!#W%)-39@LCE Z6  +#4% ,e/v5i8<=p> DGR X ZE%(,.B15 7;q@yC  V zu!&V( -2-57:>$ DxH9 U@y Q v N #%L(+o.5^9<@\B?F2 LQ $Q'r)+03 =?\AD;F KS  -#Z*}+02FdH# I _ M"&2(9 G0 t<! )k,!02 8:?CEw Ec ' -/1T3.5x =>B C I  '*, A<!'*/(z0RA0Av3|A3A @<l %4(7-Nz.w@/4@v0@1Q@2- >i"&S')m,0R3646E7;. ;f &$)+O-) 4} ;?!BD 9 Vu#Y$' -/ 7@:H;>CG 8M1y 4 v 1z11z$v&\1'_1+2P7=?cAEk 0 + 'Y(,3h9:Y?YB<C .`-,r #&'*/ 79Q==BEwF , I fH$(Y*./248: *0Q #'+ (0 & V #"%+.247;=ZC$%Gs"$s(W*u 258D>B #YGc'!&' .1j7=?L@CEG!s"q$- ;`. & -/248>AAC9  # y  Hv ~fT_rX!} )>,C/12679%<A_CDF z=C!l"%)W 046:.?"BG / d%Vx!%"(<,._0H48s; @BF cVl!C& +D-0h36 >x?BEE  }sj .%}(+.25H6;=ACG 9Y'y l$+ +2.L0437