BerkeleyFPUser’sManual,Rev.4.1 by ScottBaden ABSTRACT ThismanualdescribestheBerkeleyimplementationofBackus’ FunctionalProgrammingLanguage,FP.SincethisimplementationdiffersfromBackus’originaldescriptionofthelanguage, thosefamiliarwiththeliteraturewillneedtoreadaboutthesystemcommandsandthelocalmodifications. April8,1993 1.Background FPstandsforaFunctionalProgramminglanguage.Functionalprogramsdealwithfunctionsinsteadofvalues.Thereisnoexplicitrepresentationofstate,therearenoassignmentstatments,andhence,novariables.Owingtothelackofstate,FPfunctionsarefreefromside-effects; sowesaytheFPisapplicative. AllfunctionstakeoneargumentandtheyareevaluatedusingthesingleFPoperation,application(thecolon’:’istheapplyoperator).Forexample,weread+:<34>as“applythefunction’+’toitsargument<34>”. Functionalprogramsexpressafunctional-levelcombinationoftheircomponentsinsteadof describingstatechangesusingvalue-orientedexpressions.Forexample,wewritethefunction returningthesinofthecosofitsinput,i.e.,sin(cos(x)),as:sin@cos.Thisisafunctionalexpression,consistingofthesinglecombiningformcalledcompose(’@’isthecomposeoperator)andits functionalargumentssinandcos. Allcombiningformstakefunctionsasargumentsandreturnfunctionsasresults;functions mayeitherbeapplied,e.g.,sin@cos:3,orusedasafunctionalargumentinanotherfunctional expression,e.g.,tan@sin@cos. Aswehaveseen,FP’scombiningformsallowustoexpresscontrolabstractionswithoutthe useofvariables.Theapplytoallfunctionalform(&)isanothercaseinpoint.Thefunction’& exp’exponentiatesalltheelementsofitsargument: (1.1)

&exp:<1.02.0>≡<2.7187.389> In(1.1)therearenoinductionvariables,noraloopboundsspecification.Moreover,thecodeis usefulforanysizeargument,solongasthesub-elementsofitsargumentconformtothedomain oftheexpfunction. Wemustchangeourviewoftheprogrammingprocesstoadapttothefunctionalstyle. Insteadofwritingdownasetofstepsthatmanipulateandassignvalues,wecomposefunctional expressionsusingthehigher-levelfunctionalforms.Forexample,thefunctionthataddsascalar toallelementsofavectorwillbewrittenintwosteps.First,thefunctionthatdistributesthe scalaramongsteachelementofthevector: (1.2) distl:<3<46>>≡<<34><36>> Next,thefunctionthataddsthepairsofelementsthatmakeupasequence: (1.3)

&+:<<34><36>>≡<79> Inavalue-orientedprogramminglanguagethecomputationwouldbeexpressedas: (1.4)

&+:distl:<3<46>>, whichmeanstoapply’distl’totheinputandthentoapply’+’toeveryelementoftheresult.In FPwewrite(1.4)as: (1.5)

&+@distl:<3<46>>. Thefunctionalexpressionof(1.5)replacesthetwostepvalueexpressionof(1.4). Often,functionalexpressionsarebuiltfromtheinsideout,asinLISP.Inthenextexample wederiveafunctionthatscalesthenshiftsavector,i.e.,forscalarsa,bandavector→v,compute a+b→v.ThisFPfunctionwillhavethreearguments,namelya,band→v.Ofcourse,FPdoesnot useformalparameternames,sotheywillbedesignatedbythefunctionsymbols1,2,3.Thefirst codesegmentscales→vbyb(defintionsaredelimitedwithcurlybraces’{}’):

(1.6)

{scaleVec&∗@distl@[2,3]} Thecodesegmentin(1.5)shiftsthevector.Thecompletedfunctionis: (1.7)

{changeVec&+@distl@[1,scaleVec]} Inthederivationoftheprogramwewrotefromrighttoleft,firstdoingthedistl’sandthen composingwiththeapply-to-allfunctionalform.Usinganimperativelanguage,suchasPascal, wewouldwritetheprogramfromtheoutsidein,writingtheloopbeforeinsertingthearithmetic operators. AlthoughFPencouragesarecursiveprogrammingstyle,itprovidescombiningformsto avoidexplicitrecursion.Forexample,therightinsertcombiningform(!)canbeusedtowritea functionthataddsupalistofnumbers: (1.8)

!+:<123>≡6 Theequivalent,recursivefunctionismuchlonger: (1.9)

{addNumbers(null->%0;+@[1,addNumbers@tl])} Thegeneralityofthecombiningformsencourageshierarchicalprogramdevelopment.Unlike APL,whichrestrictstheuseofcombiningformstocertainbuiltinfunctions,FPallowscombining formstotakeanyfunctionalexpressionasanargument.

2.SystemDescription 2.1.Objects ThesetofobjectsΩconsistsoftheatomsandsequences<x1,x2,...,xk>(wherethe xi∈Ω).(Lispusersshouldnotethesimilaritytotheliststructuresyntax,justreplacetheparenthesisbyanglebracketsandcommasbyblanks.Thereareno’quoted’objects,i.e.,’abc).The atomsuniquelydeterminethesetofvalidobjectsandconsistofthenumbers(ofthetypefoundin FRANZLISP[Fod80]),quotedasciistrings("abcd"),andunquotedalphanumericstrings(abc3). Therearethreepredefinedatoms,TandF,thatcorrespondtothelogicalvalues’true’and’false’, andtheundefinedatom?,bottom.Bottomdenotesthevaluereturnedastheresultofanundefinedoperation,e.g.,divisionbyzero.Theemptysequence,<>isalsoanatom.Thefollowing areexamplesofvalidFPobjects: ?1.473888888888888 ab"CD"<1,<2,3>> <>T<a,<>> Thereisonerestrictiononobjectconstruction:noobjectmaycontaintheundefinedatom,such anobjectisitselfundefined,e.g.,<1,?>≡?.Thispropertyistheso-called“bottompreserving property”[Ba78]. 2.2.Application ThisisthesingleFPoperationandisdesignatedbythecolon(":").Forafunctionσand anobjectx,σ:xisanapplicationanditsmeaningistheobjectthatresultsfromapplyingσtox (i.e.,evaluatingσ(x)).Wesaythatσistheoperatorandthatxistheoperand.Thefollowingare examplesofapplications: +:<7,8>≡15tl:<1,2,3>≡<2,3> 1:<a,b,c,d>≡a2:<a,b,c,d>≡b 2.3.Functions Allfunctions(F)mapobjectsintoobjects,moreover,theyarestrict: (2.1) σ:?≡?,\/—σ∈F Toformallycharacterizetheprimitivefunctions,weuseamodificationofMcCarthy’sconditional expressions[Mc60]: (2.2) p1→e1;...;pn→en;en+1 Thisstatementisinterpretedasfollows:returnfunctione1ifthepredicate’p1’istrue,...,enif ’pn’istrue.Ifnoneofthepredicatesaresatisfiedthendefaulttoen+1.Itisassumedthat x,xi,y,yi,zi∈Ω. 2.3.1.Structural SelectorFunctions Foranonzerointegerμ, μ:x≡ x=<x1,x2,...,xk>//\\0<μ≤k→xμ; x=<x1,x2,...,xk>//\\−k≤μ<0→xk+μ+1;? pick:<n,x>≡ x=<x1,x2,...,xk>//\\0<n≤k→xn; x=<x1,x2,...,xk>//\\−k≤n<0→xk+n+1;? Theusershouldnotethatthefunctionsymbols1,2,3,...aretobedistinguishedfromthe atoms1,2,3,.... last:x≡ x=<>→<>; x=<x1,x2,...,xk>//\\k≥1→xk;? first:x≡ x=<>→<>; x=<x1,x2,...,xk>//\\k≥1→x1;? TailFunctions tl:x≡ x=<x1>→<>; x=<x1,x2,...,xk>//\\k≥2→<x2,...,xk>;? tlr:x≡ x=<x1>→<>; x=<x1,x2,...,xk>//\\k≥2→<x1,...,xk−1>;? Note:Thereisalsoafunctionfrontthatisequivalenttotlr.

Distributefromleftandright distl:x≡ x=<y,<>>→<>; x=<y,<z1,z2,...,zk>>→<<y,z1>,...,<y,zk>>;? distr:x≡ x=<<>,y>→<>; x=<<y1,y2,...,yk>,z>→<<y1,z>,...,<yk,z>>;? Identity id:x≡x out:x≡x Outissimilartoid.Likeiditreturnsitsargumentastheresult,unlikeiditprintsits resultonstdout−Itistheonlyfunctionwithasideeffect.Outisintendedtobeusedfordebuggingonly. Appendleftandright apndl:x≡ x=<y,<>>→<y>; x=<y,<z1,z2,...,zk>>→<y,z1,z2,...,zk>;? apndr:x≡ x=<<>,z>→<z>; x=<<y1,y2,...,yk>,z>→<y1,y2,...,yk,z>;? Transpose trans:x≡ x=<<>,...,<>>→<>; x=<x1,x2,...,xk>→<y1,...,ym>;? wherexi=<xi1,...,xim>//\\yj=<x1j,...,xkj>, 1≤i≤k,1≤j≤m. reverse:x≡ x=<>−>; x=<x1,x2,...,xk>→<xk,...,x1>;?

RotateLeftandRight rotl:x≡ x=<>→<>;x=<x1>→<x1>; x=<x1,x2,...,xk>//\\k≥2→<x2,...,xk,x1>;? rotr:x≡ x=<>→<>;x=<x1>→<x1>; x=<x1,x2,...,xk>//\\k≥2→<xk,x1,...,xk−2,xk−1>;? concat:x≡ x=<<x11,...,x1k>,<x21,...,x2n>,...,<xm1,...,xmp>>//\\k,m,n,p>0→ <x11,...,x1k,x21,...,x2n,...,xm1,...,xmp>;? Concatenateremovesalloccurrencesofthenullsequence: (2.3) concat:<<1,3>,<>,<2,4>,<>,<5>>≡<1,3,2,4,5> pair:x≡ x=<x1,x2,...,xk>//\\k>0//\\kiseven→<<x1,x2>,...,<xk−1,xk>>; x=<x1,x2,...,xk>//\\k>0//\\kisodd→<<x1,x2>,...,<xk>>;? x=<x1>→<<x1>,<>>; x=<x1,x2,...,xk>//\\k>1→<<x1,...,x⌈k/2⌉>,<x⌈k/2⌉+1,...,xk>>;? iota:x≡ x=0→<>; x∈N+→<1,2,...,x>;? 2.3.2.Predicate(Test)Functions atom:x≡x∈atoms→T;x≠?→F;? eq:x≡x=<y,z>//\\y=z→T;x=<y,z>//\\y≠z→F;? Alsolessthan(<),greaterthan(>),greaterthanorequal(>=),lessthanorequal(<=), notequal(˜ =);’=’isasynonymforeq. null:x≡x=<>→T;x≠?→F;? length:x≡x=<x1,x2,...,xk>→k;x=<>→0;? 2.3.3.Arithmetic/Logical +:x≡x=<y,z>//\\y,zarenumbers→y+z;?−:x≡x=<y,z>//\\ y,zarenumbers→y−z;?*:x≡x=<y,z>//\\y,zarenumbers→y×z;? /:x≡x=<y,z>//\\y,zarenumbers//\\z≠0→y÷z;? And,or,not,xor and:<x,y>≡x=T→y;x=F→F;? or:<x,y>≡x=F→y;x=T→T;? xor:<x,y>≡ x=T//\\y=T→F;x=F//\\y=F→F; x=T//\\y=F→T;x=F//\\y=T→T;? not:x≡x=T→F;x=F→T;? 2.3.4.LibraryRoutines sin:x≡xisanumber→sin(x);? asin:x≡xisanumber//\\|x|≤1→sin−1(x);? cos:x≡xisanumber→cos(x);? acos:x≡xisanumber//\\|x|≤1→cos−1(x);? exp:x≡xisanumber→ex;? log:x≡xisapositivenumber→ln(x);? mod:<x,y>≡xandyarenumbers→x−y×⌊xy⌋;? 2.4.FunctionalForms Functionalformsdefinenewfunctionsbyoperatingonfunctionandobjectparametersofthe form.Theresultantexpressionscanbecomparedandcontrastedtothevalue-orientedexpres-sionsoftraditionalprogramminglanguages.Thedistinctionliesinthedomainoftheoperators; functionalformsmanipulatefunctions,whiletraditionaloperatorsmanipulatevalues. Onefunctionalformiscomposition.Fortwofunctionsϕandψtheformϕ@ψdenotes theircompositionϕψ: (2.4)

(ϕ@ψ):x≡ϕ:(ψ:x),\/—x∈Ω Theconstantfunctiontakesanobjectparameter: (2.5)

%x:y≡y=?→?;x,\/—x,y∈Ω Thefunction%?alwaysreturns?. Inthefollowingdescriptionofthefunctionalforms,weassumethatξ,ξi,σ,σi,τ,andτiare functionsandthatx,xi,yareobjects. Composition (σ@τ):x≡σ:(τ:x) Construction [σ1,...,σn]:x≡<σ1:x,...,σn:x> Notethatconstructionisalsobottom-preserving,e.g., (2.6)

[+,/]:<3,0>=<3,?>=? Condition (ξ->σ;τ):x≡ (ξ:x)=T→σ:x; (ξ:x)=F→τ:x;? Thereadershouldbeawareofthedistinctionbetweenfunctionalexpressions,inthevariant ofMcCarthy’sconditionalexpression,andthefunctionalformintroducedhere.Intheformercase theresultisavalue,whileinthelattercasetheresultisafunction.UnlikeBackus’FP,theconditionalformmustbeenclosedinparenthesis,e.g., (2.7)

(isNegative->-@[%0,id];id) Constant %x:y≡y=?→?;x,\/—x∈Ω Thisfunctionreturnsitsobjectparameterasitsresult. RightInsert !σ:x≡ x=<>→ef:x; x=<x1>→x1; x=<x1,x2,...,xk>//\\k>2→σ:<x1,!σ:<x2,...,xk>>;? e.g.,!+:<4,5,6>=15. Ifσhasarightidentityelementef,then!σ:<>=ef,e.g., (2.8)

!+:<>=0and!*:<>=1 Currently,identityfunctionsaredefinedfor+(0),−(0),*(1),/(1),alsoforand(T),or(F), xor(F).Allotherunitfunctionsdefaulttobottom(?). TreeInsert |σ:x≡ x=<>→ef:x; x=<x1>→x1; x=<x1,x2,...,xk>//\\k>1→ σ:<|σ:<x1,...,x⌈k/2⌉>,|σ:<x⌈k/2⌉+1,...,xk>>;? e.g., (2.9)

|+:<4,5,6,7>≡+:<+:<4,5>,+:<6,7>>≡15 Treeinsertusesthesameidentityfunctionsasrightinsert. ApplytoAll &σ:x≡ x=<>−><>; x=<x1,x2,...,xk>→<σ:x1,...,σ:xk>;? While (whileξσ):x≡ ξ:x=T→(whileξσ):(σ:x); ξ:x=F→x;? 2.5.UserDefinedFunctions AnFPdefinitionisenteredasfollows: (2.10)

{fn-namefn-form}, wherefn-nameisanasciistringconsistingofletters,numbersandtheunderlinesymbol,andfn-formisanyvalidfunctionalform,includingasingleprimitiveordefinedfunction.Forexample thefunction (2.11)

{factorial!*@iota} isthenon-recursivedefinitionofthefactorialfunction.SinceFPsystemsareapplicativeit ispermissibletosubstitutetheactualdefinitionofafunctionforanyreferencetoitinafunctionalform:iff≡1@2thenf:x≡1@2:x,\/—x∈Ω.

Referencestoundefinedfunctionsbottomout: (2.12) f:x≡?\/—x∈Ω,f∈/F 3.GettingonandofftheSystem StartupFPfromtheshellbyenteringthecommand: /usr/local/fp. Thesystemwillpromptyouforinputbyindentingoversixcharacterpositions.Exitfrom FP(backtotheshell)withacontrol/D(ˆ D). 3.1.Comments Ausermayendanyline(includingacommand)withacomment;thecommentcharacteris ’#’.Theinterpreterwillignoreanycharacterafterthe’#’untilitencountersanewlinecharacterorend-of-file,whichevercomesfirst. 3.2.Breaks BreaksinterruptanyworkinprogresscausingthesystemtodoaFRANZresetbeforereturningcontrolbacktotheuser. 3.3.Non-Termination LISP’snamestackmay,onoccasion,overflow.FPrespondsbyprinting“non-terminating” andreturningbottomastheresultoftheapplication.ItdoesaFRANZresetbeforereturning controltotheuser. 4.SystemCommands Systemcommandsstartwitharightparenthesisandtheyarefollowedbythecommandnameandpossiblyoneormorearguments.Allthisinformationmustbetypedonasingleline, andanynumberofspacesortabsmaybeusedtoseparatethecomponents. 4.1.Load Redirectthestandardinputtothefilenamedbythecommand’sargument.Ifthefile doesn’texistthenFPappends’.fp’tothefile-nameandretriestheopen(errorifthefiledoesn’t exist).ThiscommandallowstheusertoreadinFPfunctiondefinitionsfromafile.Theusercan alsoreadinapplications,butsuchoperationisoflittleutilitysincenoneoftheinputisechoedat theterminal.Normally,FPreturnscontroltotheuseronanend-of-file.Itwillalsodosowhen-everitdoesaFRANZreset,e.g.,whenevertheuserissuesabreak,orwheneverthesystemencoun-tersanon-terminatingapplication. 4.2.Save Outputthesourcetextforalluser-definedfunctionstothefilenamedbytheargument. 4.3.CsaveandFsave Thesecommandsoutputthelispcodeforalltheuser-definedfunctions,includingtheorigi-nalsource-code,tothefilenamedbytheargument.Csaveprettyprintsthecode,Fsavedoesnot. Unlesstheuserwishestoexaminethecode,heshoulduse’fsave’;itisabouttentimesfasterthan ’csave’,andtheresultingfilewillbeaboutthreetimessmaller. Thesecommandsareintendedtobeusedwiththelisztcompilerandthe’cload’command, asexplainedbelow.

4.4.Cload Thiscommandloadsorfaslsinthefileshownbytheargument.First,FPappendsa’.o’to thefile-name,andattemptsaload.Failingthat,ittriestoloadthefilenamedbytheargument. Iftheuseroutputshisfunctiondefinitionsusingfsaveorcsave,andthencompilesthemusing liszt,thenhemayfaslinthecompiledcodeandspeeduptheexecutionofhisdefinedfunctionsby afactorof5to10. 4.5.Pfn Printthesourcetext(s)(attheterminal)fortheuser-definedfunction(s)namedbythe argument(s)(errorifthefunctiondoesn’texist). 4.6.Delete Deletetheuser-definedfunction(s)namedbytheargument(errorifthefunctiondoesn’t exist). 4.7.Fns Listthenamesofalluser-definedfunctionsinalphabeticalorder.Tracedfunctionsare labeledbyatrailing’@’(see§4.7forsampleoutput). 4.8.Stats The“stats”commandhasseveraloptionsthathelptheusermanagethecollectionof dynamicstatisticsforfunctions1andfunctionalforms.Optionnamesfollowthekeyword“stats”, e.g.,“)statsreset”. Thestatisticpackagerecordsthefrequencyofusageforeachfunctionandfunctionalform; alsothesize2ofalltheargumentsforallfunctionsandfunctionalexpressions.Thesetwomeasuresallowtheusertoderivetheaverageargumentsizepercall.Forfunctionalformsthepackagetalliesthefrequencyofeachfunctionalargument.Constructionhasanadditionalstatistic thattellsthenumberoffunctionalargumentsinvolvedintheconstruction. Statisticsaregatheredwheneverthemodeison,exceptforapplicationsthat“bottomout” (i.e.,returnbottom−?).Statisticcollectionslowsthesystemdownby×2to×4.Thefollowingprintoutillustratestheuseofthestatisticpackage(userinputisemboldened): 1Measurementofuser-definedfunctionsisdonewiththeaidofthetracepackage,discussedin§4.9. 2“Size”isthetop-levellengthoftheargument,formostfunctions.Exceptionsare:apndl,distl(top-levellengthof thesecondelement),apndr,distr(top-levellengthofthefirstelement),andtranspose(toplevellengthofeachtoplevelel-ement).

)statson Statscollectionturnedon. +:<34> 7 !*@iota:3 6 )statsprint plus:times1 times:times2 iota:times1 insert:times1size3 FunctionalArgs Name Times times 1 compos:times1size1 FunctionalArgs Name Times insert 1 iota 1 4.8.1.On Enablestatisticscollection. 4.8.2.Off Disablestatisticscollection.Theusermayselectivelycollectstatisticsusingtheonandoff commands. 4.8.3.Print Printthedynamicstatisticsattheterminal,or,outputthemtoafile.Thelatteroption requiresanadditionalargument,e.g.,“)statsprintfooBar”printsthestatstothefile“fooBar”. 4.8.4.Reset Resetthedynamicstatisticscounters.Topreventaccidentallossofcollectedstatistics,the systemwillquerytheuserifhetriestoresetthecounterswithoutfirstoutputtingthedata(the systemwillalsoquerytheuserifhetriestologoutwithoutoutputtingthedata).

4.9.Trace Enableordisablethetracingandthedynamicmeasurementoftheuserdefinedfunctions namedbytheargument(s).Thefirstargumenttellswhethertoturntracingofforonandthe othersgivethenameofthefunctionsaffected.Thetracinganduntracingcommandsareindependentofthedynamicstatisticscommands.Thiscommandiscumulativee.g.,’)traceonf1’,followedby’)traceonf2’isequivalentto’)traceonf1f2’. FPtraceroutputissimilartotheFRANZtraceroutput:functionentriesandexits,calllevel, thefunctionalargument(rememberthatFPfunctionshaveonlyoneargument!),andtheresult, areprintedattheterminal: )pfnfact {fact(eq0->%1;*@[id,fact@s1])} )fns eq0facts1 )traceonfact )fns eq0fact@s1 fact:2 1>Enter>fact[2] |2>Enter>fact[1] |3>Enter>fact[0] |3<EXIT<fact1 |2<EXIT<fact1 1<EXIT<fact2 2 4.10.Timer FPprovidesasimpletimingfacilitytotimetop-levelapplications.Thecommand“)timer on”putsthesystemintimingmode,“)timeroff”turnsthemodeoff(themodeisinitiallyoff). Whileintimingmode,thesystemreportsCPUtime,garbagecollectiontime,andelapsedtime,in seconds.Thetimingoutputfollowstheprintoutoftheresultoftheapplication. 4.11.Script Openorcloseascriptfile.Thefirstargumentgivestheoption,thesecondtheoptional scriptfile-name.The“open”optioncausesanewscript-filetobeopenedandanycurrentlyopen scriptfiletobeclosed.Ifthefilecannotbeopened,FPsendsanderrormessageand,ifascript filewasalreadyopened,itremainsopen.Thecommand”)scriptclose”closesanopenscriptfile. Theusermayelecttoappendscriptoutputtothescript-filewiththeappendmode.

4.12.Help Printashortsummaryofallthesystemcommands: )help Commandsare: load<file>Redirectinputfrom<file> save<file>Savedefinedfnsin<file> pfn<fn1>...Printsourcetextof<fn1>... delete<fn1>...Delete<fn1>... fns Listallfunctions statson/off/reset/print[file]Collectandprintdynamicstats traceon/off<fn1>...Start/Stopexectraceof<fn1>... timeron/ofTurntimeron/off scriptopen/close/appendOpenorcloseascript-file lisp Exittothelispsystem(returnwith’ˆ D’) debugon/offTurndebuggeroutputon/off csave<file>OutputLispcodeforalluser-definedfns cload<file>LoadLispcodefromafile(maybecompiled) fsave<file>Sameascsaveexceptwithoutpretty-printing 4.13.SpecialSystemFunctions Therearetwosystemfunctionsthatarenotgenerallymeanttobeusedbyaverageusers. 4.13.1.Lisp Thisexitstothelispsystem.Use"ˆ D"toreturntoFP. 4.13.2.Debug Turnsthe’debug’flagonoroff.Thecommand“)debugon”turnstheflagon,“)debugoff” turnstheflagoff.Themainpurposeofthecommandistoprintouttheparsetree.

5.ProgrammingExamples WewillstartoffbydevelopingalargerFPprogram,mergeSort.WemeasuremergeSort usingthetracepackage,andthenwecommentonthemeasurements.FollowingmergeSortwe showanactualsessionattheterminal. 5.1.MergeSort ThesourcecodeformergeSortis: #Useadivideandconquerstrategy {mergeSort|merge} {mergeatEnd@mergeHelp@[[],fixLists]} #Mustconvertatomicargumentsintosequences #Atomicargumentsoccurattheleavesoftheexecutiontree {fixLists&(atom->[id];id)} #Mergeuntiloneorbothinputlistsareempty {mergeHelp(whileand@&(not@null)@2 (firstIsSmaller->takeFirst; takeSecond))} #Findthelistwiththesmallerfirstelement {firstIsSmaller<@[1@1@2,1@2@2]} #Takethefirstelementofthefirstlist {takeFirst[apndr@[1,1@1@2],[tl@1@2,2@2]]} #Takethefirstelementofthesecondlist {takeSecond[apndr@[1,1@2@2],[1@2,tl@2@2]]} #Ifonelistisn’tnull,thenappendittothe #endofthemergedlist {atEnd(firstIsNull->concat@[1,2@2]; concat@[1,1@2])} {firstIsNullnull@1@2} Themergesortalgorithmusesadivideandconquerstrategy;itsplitstheinputinhalf, recursivelysortseachhalf,andthenmergesthesortedlists.Ofcourse,allthesesub-sortscan executeinparallel,andthetree-insert(|)functionalformexpressesthisconcurrency.Merge removessuccessivelylargerelementsfromtheheadsofthetwolists(eithertakeFirstortakeSecond)andappendstheseelementstotheendofthemergedsequence.Mergeterminateswhenone sequenceisempty,andthenatEndappendsanyremainingnon-emptysequencetotheendofthe mergedone. Onthenextpagewegivethetraceofthefunctionmerge,whichinformationwecanuseto determinethestructureofmerge’sexecutiontree.Sincethetreeiswell-balanced,manyofthe merge’scouldbeexecutedinparallel.Usingthistracewecanalsocalculatetheaveragelengthof theargumentspassedtomerge,oradistributionofargumentlengths.Thisinformationisuseful fordeterminingcommunicationcosts.

)traceonmerge mergeSort:<03-21118-22-33> |3>Enter>merge[<03>] |3<EXIT<merge<03> |3>Enter>merge[<-21>] |3<EXIT<merge<-21> |2>Enter>merge[<<03><-21>>] |2<EXIT<merge<-2013> |3>Enter>merge[<118>] |3<EXIT<merge<811> |3>Enter>merge[<-22-33>] |3<EXIT<merge<-33-22> |2>Enter>merge[<<811><-33-22>>] |2<EXIT<merge<-33-22811> 1>Enter>merge[<<-2013><-33-22811>>] 1<EXIT<merge<-33-22-2013811> <-33-22-2013811> 5.2.FPSession Userinputisemboldened,terminaloutputinRomanscript. fp FP,v.4.111/31/82 )loadexman {allle} {sort} {absval} {find} {ip} {mm} {eq0} {fact} {sub1} {altfnd} {altfact} )fns absvalalllealtfactaltfndeq0factfind ipmmsortsub1 absval:3 3 absval:-3 3 absval:0 0 absval:<-5066> ? &absval:<-5066> <5066> )pfnabsval {absval((>@[id,%0])->id;(-@[%0,id]))} [id,%0]:-3 <-30> [%0,id]:-3 <0-3> -@[%0,id]:-3 3 allle:<1357> T allle:<1057> F )pfnallle {allle!and@&<=@distl@[1,tl]} distl@[1,tl]:<1234> <<12><13><14>> &<=@distl@[1,tl]:<1234> <TTT> !and:<FTT> F !and:<TTT> T sort:<3124> <1234> sort:<1> <1> sort:<> ? sort:4 ? )pfnsort {sort(null@tl->[1];(allle->apndl@[1,sort@tl];sort@rotl))} fact:3 6 )pfnfactsub1eq0 {fact(eq0->%1;*@[id,fact@sub1])} {sub1-@[id,%1]} {eq0=@[id,%0]} &fact:<12345> <12624120> eq0:3 F eq0:<> F eq0:0 T sub1:3 2 %1:3 1 altfact:3 6 )pfnaltfact {altfact!*@iota} iota:3 <123> !*@iota:3 6 !+:<123> 6 find:<3<345>> T find:<<><34<>>> T find:<3<45>> F )pfnfind {find(null@2->%F;(=@[1,1@2]->%T;find@[1,tl@2]))} [1,tl@2]:<3<345>> <3<45>> [1,1@2]:<3<345>> <33> altfnd:<3<345>> T )pfnaltfnd {altfnd!or@&eq@distl} distl:<3<345>> <<33><34><35>> &eq@distl:<3<345>> <TFF> !or:<TFT> T !or:<FFF> F )deletealtfnd )fns absvalalllealtfacteq0factfindip mmsortsub1 altfnd:<3<345>> altfndnotdefined ? {gg} {g} g:3 non-terminating ? [Returntotoplevel] FP,v.4.010/8/82 [+,*]:<34> <712> [+,*:<34> syntaxerror: [+,*:<34> ˆ ip:<<345><567>> 74 )pfnip {ip!+@&*@trans} trans:<<345><567>> <<35><46><57>> &*@trans:<<345><567>> <152435> mm:<<<10><01>><<34><56>>> <<34><56>> )pfnmm {mm&&ip@&distl@distr@[1,trans@2]} [1,trans@2]:<<<10><01>><<34><56>>> <<<10><01>><<34><56>>> distr:<<<10><01>><<34><56>>> <<<10><<34><56>>><<01><<34><56>>>> &distl:<<<10><<34><56>>><<01><<34><56>>>> <<<<10><34>><<10><56>>><<<01><34>><<01><56>>>> &ip@&dist&distr@[1,trans@2]:<<<10><01>><<34><56>>> syntaxerror: [+,*:<34> ˆ &ip@&distl&distr@[1,trans@2]:<<<10><01>><<34><56>>> ˆ &ip@&distl@distr@[1,trans@2]:<<<10><01>><<34><56>>> ?

6.ImplementationNotes FPwaswrittenin3000linesofFRANZLISP[Fod80].Table1breaksdownthedistribution ofthecodebyfunctionality. Functionality%(bytes) compiler34 userinterface32 dynamicstats16 primitives14 miscellaneous3 Table1 6.1.TheTopLevel Thetop-levelfunctionrunFpstartsupthesubsystembycallingtheroutinefpMain,that takesthreearguments: (1)Abooleanargumentthatsayswhetherdebuggingoutputwillbe enabled. (2)AFontidentifier.Currentlytheonlyoneissupported’asc (ASCII). (3)Abooleanargumentthatidentifieswhethertheinterpreterwas invokedfromtheshell.IfsothenallexitsfromFPreturnthe userbacktotheshell. ThecompilerconvertstheFPfunctionsintoLISPequivalentsintwostages:firstitforms theparsetree,andthenitdoesthecodegeneration. 6.2.TheScanner Thescannerconsistsofamainroutine,gettkn,andasetofactionfunctions.Thereexists onesetofactionfunctionsforeachcharacterfont(currentlyonlyASCIIissupported).Allthe actionfunctionsarenamedscan$<font>,where<font>isthespecifiedfont,andeachiskeyedon aparticularcharacter(orsometimesaparticularcharacter-type−e.g.,aletteroranumber). gettknreturnsthetokentype,andanyancillaryinformation,e.g.,forthetoken"name"thename itselfwillalsobeprovided.(SeeAppendixCforthefont-tokennamecorrespondences).Whena characterhasbeenreadthescannerfindstheactionfunctionbydoinga (get′scan$<font><char>) Asyntaxerrormessagewillbegeneratedifnoactionexistsfortheparticularcharacterread. 6.3.TheParser Themainparsingfunction,parse,acceptsasingleargument,thatidentifiestheparsingcontext,or typeofconstructbeinghandled.Table2showsthevalidparsingcontexts. idconstruct toplevinitialcall constr$$construction compos$$composition alpha$$apply-to-all insert$$insert ti$$treeinsert arrow$$ affirmativeclause ofconditional semi$$ negativeclause ofconditional lparen$$parentheticexpr. while$$while Table2,ValidParsingContexts Foreachtypeoftokenthereexistsasetofparseactionfunctions,ofthenamep$<tknname>.Eachparse-actionfunctioniskeyedonavalidcontext,anditislookedupinthesame mannerasscanactionfunctionsarelookedup.Ifanactionfunctioncannotbefound,thenthere isasyntaxerrorinthesourcecode.Parsingproceedsasfollows:initiallyparseiscalledfromthe top-level,withthecontextargumentsetto“toplev”.Certaintokenscauseparsetoberecur-sivelyinvokedusingthattokenasacontext.Theresultistheparsetree. 6.4.TheCodeGenerator ThesystemcompilesFPsourceintoLISPsource.Normally,thiscodeisinterpretedbythe FRANZLISPsystem.Tospeeduptheimplementation,thereisanoptiontocompileintomachine codeusingthelisztcompiler[Joy79].Thisfeatureimprovesperformancetenfold,forsomeprograms. ThecompilerexpandsallfunctionalformsintotheirLISPequivalentsinsteadofinserting callstofunctionsthatgeneratethecodeatrun-time.Otherwise,lisztwouldbeineffectivein speedingupexecutionsinceallthefunctionalformswouldbeexecutedinterpretively.Although theamountofcodegeneratedbyanexpandingcompileris3or4timesgreaterthanwouldbe generatedbyanon-expandingcompiler,evenininterpretedmodethecoderunstwiceasquickly asunexpandedcode.Withlisztcompilationthisperformanceadvantageincreasestomorethan tenfold. Aparsetreeiseitheranatomorahunkofparsetrees.Anatomicparse-treeidentifies eitheranfpbuilt-infunctionorauserdefinedfunction.Thehunk-typeparsetreerepresents functionalforms,e.g.,composeorconstruct.Thefirstelementidentifiesthefunctionalformand theotherelementsareitsfunctionalparameters(theymayinturnbefunctionalforms).Table3 showstheparse-treeformats.

FormFormat user-defined<atom> fpbuiltin<atom> apply-to-all{alpha$$Φ} insert{insert$$Φ} treeinsert{ti$$Φ} select{select$$μ} constant{constant$$μ} conditional{condit$$Φ1Φ2Φ3} while{while$$Φ1Φ2} compose{compos$$Φ1Φ2} construct{constr$$Φ1Φ2,...,Φnnil} Note:ΦandtheΦkareparse-treesandμisanoptionallysignedintegerconstant. Table3,Parse-TreeFormats 6.5.FunctionDefinitionandApplication Oncethecodehasbeengenerated,thenthesystemdefinesthefunctionviaputd.The sourcecodeisplacedontoapropertylist,′sources,topermitlateraccessbythesystemcommands. Foranapplication,theindicatedfunctioniscompiledandthendefined,onlytemporarily,as tmp$$.Thesingleargumentisreadandtmp$$isappliedtoit. 6.6.FunctionNamingConventions Whentheparserdetectsanamedprimitivefunction,itreturnsthename<name>$fp, where<name>isthenamethatwasparsed(allprimitivefunction-namesendin$fp).See AppendixDforthesymbolic(e.g.,compose,+)functionnames. Anynamethatisn’tfoundinthelistofbuiltinfunctionsisassumedtorepresentauserdefinedfunction;hence,itisn’tpossibletoredefineFPprimitivefunctions.FPprotectsitself fromaccidentalormaliciousinternaldestructionbyappendingthesuffix“fp”toalluser-defined functionnames,beforetheyaredefined. 6.7.MeasurementImpelementation ThisworkwasdonebyDorabPatelatUCLA.Mostofthemeasurementcodeisinthefile ’fpMeasures.l’.Manyoftheremainingchangeswereeffectedin’primFp.l’,toaddcallsonthe measurementpackageatrun-time;to’codeGen.l’,toaddtracingofuserdefinedfunctions;to ’utils.l’,toaddthenewsystemcommands;andto’fpMain.l’,toprotecttheuserfromforgetting tooutputstatisticswhenheleavesFP. 6.7.1.DataStructures AllthestatisticsareinthepropertylistoftheglobalsymbolMeasures.Associatedwith eacheachfunction(primitiveoruser-defined,orfunctionalform)isanindicator;thestatistics gatheredforeachfunctionarethecorrespondingvalues.Thenamescorrespondingtoprimitive functionsandfunctionalformsendin’$fp’andthenamescorrespondingtouser-definedfunctions endin’fp’.Eachofthepropertyvaluesisanassociationlist:

(get’Measures’rotl$fp)==>((times.0)(size.0)) Thecarofthepairisthenameofthestatistic(i.e.,times,size)andthecdristhevalue. Thereisoneexception.Functionalformshaveastatisticcalledfunargtyp.Insteadofbeinga dottedpair,itisalistoftwoelements: (get’Measures’compose$fp)==> ((times.2)(size.4)(funargtyp((select$fp.2)(sub$fp.2)))) Thecaristheatom’funargtyp’andthecdrisanalist.Eachelementofthealistconsistsof afunctionalargument-frequencydottedpair. Thestatisticpackagesusestwootherglobalsymbols.ThesymbolDynTraceFlgisnon-nilif dynamicstatisticsarebeingcollectedandisnilotherwise.ThesymbolTracedFnsisalist(initiallynil)ofthenamesoftheuserfunctionsbeingtraced. 6.7.2.InterpretationofDataStructures 6.7.2.1.Times Thenumberoftimesthisfunctionhasbeencalled.Allfunctionsandfunctionalformshave thisstatistic. 6.7.2.2.Size Thesumofthesizesoftheargumentspassedtothisfunction.Thiscouldbedividedbythe timesstatistictogivetheaveragesizeofargumentthisfunctionwaspassed.Withfewexceptions, thesizeofanobjectisitstop-levellength(note:version4.0definedthesizeasthetotalnumber ofatomsintheobject);theemptysequence,“<>”,hasasizeof0andallotheratomshavesize ofone.Theexceptionsare:apndl,distl(top-levellengthofthesecondelement),apndr,distr(top-levellengthofthefirstelement),andtranspose(toplevellengthofeachtoplevelelement). Thisstatisticisnotcollectedforsomeprimitivefunctions(mainlybinaryoperatorslike +,-,∗). 6.7.2.3.Funargno Thenumberoffunctionalargumentssuppliedtoafunctionalform. Currentlythisstatisticisgathereredonlyfortheconstructionfunctionalform. 6.7.2.4.Funargtyp Howmanytimesthenamedfunctionwasusedasafunctionalparametertotheparticular functionalform. 6.8.TraceInformation Thelevelnumberofacallshowsthenumberofstepsrequiredtoexecutethefunctiononan idealmachine(i.e.,onewithunboundedresources).Thelevelnumberiscalculatedunderan assumptionofinfiniteresources,andthesystemevaluatestheconditionofaconditionalbefore evaluatingeitherofitsclauses.Thenumberoffunctionsexecutedateachlevelcangiveanidea ofthedistributionofparallelisminthegivenFPprogram.

7.Acknowledgements SteveMuchnickproposedtheinitialconstructionofthissystem.BobBallanceaddedsome ofisowninsights,andJohnFoderaroprovidedhelpfulhintsregardingeffectiveuseoftheFRANZ LISPsystem[Fod80].DorabPatel[Pat81]wrotethedynamictraceandstatisticspackageand madegeneralimprovementstotheuserinterface.Portionsofthismanualwereexcerptedfrom theCOMPCON-83DigestofPapers3. 8.References [Bac78] JohnBackus,“CanProgrammingBeLiberatedfromthevonNeumannStyle?AFunctional StyleandItsAlgebraofPrograms,”CACM,TuringAwardLecture,21,8(August1978), 613-641. [Fod80] JohnK.Foderaro,“TheFRANZLISPManual,”UniversityofCalifornia,Berkeley,California, 1980. [Joy79] W.N.Joy,O.Babaoglu,“UNIXProgrammer’sManual,”November7,1979,ComputerScienceDivision,UniversityofCalifornia,Berkeley,California. [Mc60] J.McCarthy,“RecursiveFunctionsofSymbolicexpressionsandtheirComputationby Machine,”PartI,CACM3,4(April1960),184-195. [Pat80] DorabRatanPatel,“ASystemOrganizationforApplicativeProgramming,”M.SThesis, UniversityofCalifornia,LosAngeles,California,1980. [Pat81] DorabPatel,“FunctionalLanguageInterpreterUserManual,”UniversityofCalifornia,Los Angeles,California,1981. 3ScottB.BadenandDorabR.Patel,“BerkeleyFP−ExperiencesWithaFunctionalProgrammingLanguage”,◯c 1982,IEEE.

AppendixA:LocalModifications 1.CharacterSetChanges Backus[Ba78]usedsomecharactersthatdonotappearonourASCIIterminals,sowehave madethefollowingsubstitutions: constantx%x insert/! apply-to-allα& composition@ arrow→-> emptysetϕ<> bottom? divide÷/ multiply×∗ 2.SyntacticModifications 2.1.WhileandConditional Whileandconditionalfunctionalexpressionsmustbeenclosedinparenthesis,e.g., (whilefg) (p->f;g) 2.2.FunctionDefinitions Functiondefinitionsareenclosedbycurlybraces;theyconsistofaname-definitionpair,sep-aratedbyblanks.Forexample: {fact!∗@iota} definesthefunctionfact(thereadershouldrecognizethisasthenon-recursivefactorialfunction). 2.3.SequenceConstruction Itisnotnecessarytoseparateelementsofasequenceswithacomma;ablankwillsuffice: <1,2,3>≡<123> Fornestedsequences,theterminatingrightanglebracketactsasthedelimiter: <<1,2,3>,<4,5,6>>≡<<123><456>> 3.UserInterface Wehaveprovidedarichsetofcommandsthatallowtheusertocatalog,print,anddelete functions,toloadthemfromafileandtosavethemaway.Theusermaygeneratescriptfiles, dynamicallytraceandmeasurefunctionalexpressionexecution,generatedebuggingoutput,and, temporarilyexittotheFRANZLISPsystem.Acommandmustbeginwitharightparenthesis. ConsultAppendixCforacompletedescriptionofthecommandsyntax. DebugginginFPisdifficult;allundefinedresultsmaptoasingleatom−bottom(“?”).To pinpointthecauseofanerrortheusercanusethespecialdebuggingoutputfunction,out,orthe tracer. 4.AdditionsandOmmissions Manyrelationalfunctionshavebeenadded:<,>,=,≠,≤,≥;theirsyntaxis:<,>,=, ˜ =,<=,>=.Alsoaddedaretheiotafunction(ThisistheAPLiotafunctionann-element sequenceofnaturalnumbers)andtheexclusiveOR(◯+)function. Severalnewstructuralfunctionshavebeenadded:pairpairsupsuccessiveelementsofa sequence,splitsplitsasequenceintotwo(roughly)equalhalves,lastreturnsthelastelementof thesequence(<>ifthesequenceisempty),firstreturnsthefirstelementofthesequence(<>if itisempty),andconcatconcatenatesallsubsequencesofasequence,squeezingoutnull sequences(<>).Frontisequivalenttotlr.Pickisaparameterizedformoftheselectorfunction;thefirstcomponentoftheargumentselectsasingleelementfromthesecondcomponent. Outistheonlyside-effectfunction;itisequivalenttotheidfunctionbutitalsoprintsitsargu-mentoutattheterminal.Thisfunctionisintendedtobeusedonlyfordebugging. Onenewfunctionalformhasbeenadded,treeinsert.Thisfunctionalformbreaksupthe theargumentintotworoughlyequalpiecesapplyingitselfrecursivelytothetwohalves.The functionalparameterisappliedtotheresult. Thebinary-to-unaryfunctions(’bu’)hasbeenomitted. Sevenmathematicallibraryfunctionshavebeenadded:sin,cos,asin(sin−1),acos(cos−1), log,exp,andmod(theremainderfunction)

AppendixB:FPGrammar I.BNFSyntax fpInput→(fnDef|application|fpCmda)∗|’ˆ D’ fnDef→’{’namefunForm’}’ application→funForm’:’object name→letter(letter|digit|’’)∗ nameList→(name)∗ object→atom|fpSequence|’?’ fpSequence→’<’(ϵ|object((’,’|’’)object)∗)’>’ atom→’T’|’F’|’<>’|’"’(ascii-char)∗’"’|(letter|digit)∗|number funForm→simpFn|composition|construction|conditional| constantFn|insertion|alpha|while|’(’funForm’)’ simpFn→fpDefined|fpBuiltin fpDefined→name fpBuiltin→selectFn|’tl’|’id’|’atom’|’not’|’eq’|relFn|’null’|’reverse’| ’distl’|’distr’|’length’|binaryFn|’trans’|’apndl’|’apndr’| ’tlr’|’rotl’|’rotr’|’iota’|’pair’|’split’|’concat’|’last’|’libFn’ selectFn→(ϵ|’+’|’-’)unsignedInteger relFn→’<=’|’<’|’=’|’˜ =’|’>’|’>=’ binaryFn→’+’|’-’|’∗’|’/’|’or’|’and’|’xor’ libFn→’sin’|’cos’|’asin’|’acos’|’log’|’exp’|’mod’ composition→funForm’@’funForm construction→’[’formList’]’ formList→ϵ|funForm(’,’funForm)∗ conditional→’(’funForm’->’funForm’;’funForm’)’ constantFn→’%’object insertion→’!’funForm|’|’funForm alpha→’&’funForm while→’(’’while’funFormfunForm’)’ II.Precedences 1.%,!,&(highest) 2.@ 3.[...] 4.->...;... 5.while(least) aCommandSyntaxislistedinAppendixC.

AppendixC:CommandSyntax Allcommandsbeginwitharightparenthesis(“)”). )fns )pfn<nameList> )load<UNIXfilename> )cload<UNIXfilename> )save<UNIXfilename> )csave<UNIXfilename> )fsave<UNIXfilename> )delete<nameList> )statson )statsoff )statsreset )statsprint[UNIXfilename] )traceon<nameList> )traceoff<nameList> )timeron )timeroff )debugon )debugoff )scriptopen<UNIXfilename> )scriptclose )scriptappend<UNIXfilename> )help )lisp AppendixD:Token-NameCorrespondences TokenName [lbrack$$ ]rbrack$$ {lbrace$$ }rbrace$$ (lparen$$ )rparen$$ @compos$$ !insert$$ |ti$$ &alpha$$ ;semi$$ :colon$$ ,comma$$ +builtin$$ +μaselect$$ ∗builtin$$ /builtin$$ =builtin$$ -builtin$$ ->arrow$$ -μselect$$ >builtin$$ >=builtin$$ <builtin$$ <=builtin$$ ˜ =builtin$$ %obconstant$$ aμisanoptionallysignedintegerconstant. boisanyFPobject.

AppendixE:SymbolicPrimitiveFunctionNames Thescannerassignsnamestothealphabeticprimitivefunctionsbyappendingthestring “$fp”totheendofthefunctionname.Thefollowingtabledesignatesthenamingassignmentsto thenon-alphabeticprimitivefunctionnames. FunctionName +plus$fp -minus$fp ∗times$fp /div$fp =eq$fp >gt$fp >=ge$fp <lt$fp <=le$fp ˜ =ne$fp TableofContents 1.Background.....................................................................................................................1 2.SystemDescription..........................................................................................................3 2.1.Objects.........................................................................................................................3 2.2.Application...................................................................................................................3 2.3.Functions......................................................................................................................3 2.3.1.Structural...................................................................................................................4 2.3.2.Predicate(Test)Functions.........................................................................................6 2.3.3.Arithmetic/Logical....................................................................................................7 2.3.4.LibraryRoutines........................................................................................................7 2.4.FunctionalForms..........................................................................................................7 2.5.UserDefinedFunctions.................................................................................................9 3.GettingonandofftheSystem........................................................................................11 3.1.Comments.....................................................................................................................11 3.2.Breaks...........................................................................................................................11 3.3.Non-Termination..........................................................................................................11 4.SystemCommands..........................................................................................................11 4.1.Load..............................................................................................................................11 4.2.Save..............................................................................................................................11 4.3.CsaveandFsave...........................................................................................................11 4.4.Cload............................................................................................................................12 4.5.Pfn................................................................................................................................12 4.6.Delete...........................................................................................................................12 4.7.Fns................................................................................................................................12 4.8.Stats.............................................................................................................................12 4.8.1.On..............................................................................................................................13 4.8.2.Off..............................................................................................................................13 4.8.3.Print..........................................................................................................................13 4.8.4.Reset..........................................................................................................................13 4.9.Trace.............................................................................................................................14 4.10.Timer..........................................................................................................................14 4.11.Script..........................................................................................................................14 4.12.Help............................................................................................................................15 4.13.SpecialSystemFunctions............................................................................................15 4.13.1.Lisp..........................................................................................................................15 4.13.2.Debug.......................................................................................................................15 5.ProgrammingExamples..................................................................................................16 5.1.MergeSort.....................................................................................................................16 5.2.FPSession....................................................................................................................18 6.ImplementationNotes.....................................................................................................24 6.1.TheTopLevel..............................................................................................................24 6.2.TheScanner..................................................................................................................24 6.3.TheParser....................................................................................................................24 6.4.TheCodeGenerator.....................................................................................................25 i 6.5.FunctionDefinitionandApplication............................................................................26 6.6.FunctionNamingConventions......................................................................................26 6.7.MeasurementImpelementation.....................................................................................26 6.7.1.DataStructures.........................................................................................................26 6.7.2.InterpretationofDataStructures..............................................................................27 6.7.2.1.Times......................................................................................................................27 6.7.2.2.Size..........................................................................................................................27 6.7.2.3.Funargno.................................................................................................................27 6.7.2.4.Funargtyp................................................................................................................27 6.8.TraceInformation.........................................................................................................27 7.Acknowledgements..........................................................................................................28 8.References........................................................................................................................28 AppendixA:LocalModifications.......................................................................................29 1.CharacterSetChanges....................................................................................................29 2.SyntacticModifications...................................................................................................29 2.1.WhileandConditional..................................................................................................29 2.2.FunctionDefinitions.....................................................................................................29 2.3.SequenceConstruction.................................................................................................29 3.UserInterface..................................................................................................................30 4.AdditionsandOmmissions..............................................................................................30 AppendixB:FPGrammar.................................................................................................31 AppendixC:CommandSyntax.........................................................................................32 AppendixD:Token-NameCorrespondences......................................................................33 AppendixE:SymbolicPrimitiveFunctionNames.............................................................34 ii iii