The Q Programming Language

TheQProgrammingLanguageVersion4.514October2003byAlbertGr¨afJohannesGutenberg-UniversityMainzCopyrightc1992-2003byAlbertGr¨afThisdocumentdescribesversion4.5oftheQprogramminglanguageandsystem.ThismanualhasbeenpublishedintheseriesMusikinformatikundMedientechnik,BereichMusikinformatik,MusikwissenschaftlichesInstitut,JohannesGutenberg-Universit¨atMainzP.O.Box398055099MainzGermanyISSN0941-0309TheQprogrammingsystemisdistributedunderthetermsoftheGNUGeneralPublicLicense.Seethesoftwarelicenseaccompanyingthedistributionfordetails.Permissionisgrantedtomakeanddistributeverbatimcopiesofthismanualprovidedthecopyrightnoticeandthispermissionnoticearepreservedonallcopies.Permissionisgrantedtocopyanddistributemodifiedversionsofthismanualunderthecon-ditionsforverbatimcopying,providedthattheentireresultingderivedworkisdistributedunderthetermsofapermissionnoticeidenticaltothisone.Permissionisgrantedtocopyanddistributetranslationsofthismanualintoanotherlan-guage,undertheaboveconditionsformodifiedversions,exceptthatthispermissionnoticemaybestatedinatranslationapprovedbytheauthor.Chapter1:Introduction11IntroductionQstandsfor“equational”,soQ,inanutshell,isaprogramminglanguagewhichletsyou“programbyequations”.Youspecifyasystemofequationswhichtheinterpreterusesas“rewriterules”toreduceexpressionsto“normalform”.Thisallowsyoutoformulateyourprogramsinahigh-level,conciseanddeclarativestyle.Q’sdevelopmentstartedoutinthe1990s,motivatedbytheauthor’sresearchontermpatternmatching[Gr¨af1991]andinspiredbythepioneeringworkonequationalprogrammingbyMichaelO’Donnellandothers[O’Donnell1985],asanattempttoshowthattermrewritingwouldprovideafeasiblebasisforapracticalprogramminglanguage.Ithinkthatthisgoalhasbeenachieved,andthatthepresentinterpreterisefficientandrobustenoughforpracticalpurposes.Qhasbeenportedtoavarietyofoperatingsystems,suchasBeOS,FreeBSD,Linux,MacOSX,SolarisandWindows.PortingtoothermodernUNIX/POSIXenvironmentsshouldbeapieceofcake.ThusQcanbeusedonmostmoderncomputersystems,andQscriptswrittenononesystemwillusuallyrunonallsupportedplatforms.TheQlanguagesupportsarichvarietyofbuilt-intypes,likearbitraryprecisionintegers,floatingpointnumbers(doubleprecision64bit),truthvalues,strings,listsandfiles.Italsoprovidesprimitivesforexceptionhandlingandmultithreadedexecution.Qscriptscanbebrokendowninto“modules”,eachwiththeirseparatenamespace,andQgivesyoufullcontroloverwhichsymbols(function,variableandtypenames)areimportedandexportedbyeachmodule.Thismakesiteasytoorganizelargescriptsinamodularfashion.Qalsoallowsyoutointerfaceto“external”moduleswrittenintheCprogramminglanguage,whichprovidesameanstoaccessfunctionsinClibrariesandemployC’shigherprocessingspeedfortime-criticaltasks.Asapracticalprogramminglanguage,Qcomeswith“batteriesincluded”:Acompre-hensivestandardlibrary,writtenmostlyinQitself,providesacomplexnumbertype,alotofusefullistprocessingfunctions(includinglistcomprehensions),a“lazy”(call-by-need)listdatastructure(a.k.a.“streams”),manycommoncontainerdatastructures(dictionar-ies,sets,etc.),thelambdacalculus,andoperationsforcreatingPostScriptgraphics.ItalsoincludesanextensivesysteminterfacewhichoffersservicessuchasbinaryandC-styleformattedI/O,BSDsocketI/O,processmanagement,POSIXmultithreadingandregularexpressionmatching.AdditionalextensionmodulesforinterfacingtoGNUOctave,Tcl/Tk,GGI,IBM’sDataExplorerandODBC-compatibledatabasesmakeQavaluabletoolforscientificprogrammingandotheradvancedapplications.Indifferencetootherfunctionallanguages,Qisentirelybasedonthenotionsofrewriterules,reductionsandirreducibleexpressions(alsoknownasnormalforms)pertainingtothetermrewritingcalculus.AQ“program”,calledascript,consistsofequationswhicharetreatedasrewriterulesandareusedtoreduceexpressionstonormalform.Thenormalformofanexpressiondenotesitsvalue,whichcanitselfbeacompoundexpression.Qhasnorigiddistinctionbetween“constructor”and“defined”functionsymbolsanditalsoallowsyoutoevaluateexpressionscontaining“free”variables.Basically,bothsidesofanequationmayinvolvearbitraryexpressions.ThereforeQcanalsobeusedasatoolforsymbolicexpressionevaluation.Q’ssymbolicprocessingcapabilitiesarebestillustratedbythefactthatadvancedfeaturessuchasthelambdacalculusandlistcomprehensionsarenotbuiltintothelanguage,butareprovidedbyscriptswrittenintheQlanguage.2TheQProgrammingLanguageOnthesurface,QlooksverymuchlikecontemporaryfunctionallanguagessuchasMi-randaorHaskell.Infact,thesyntaxofthelanguagehaslargelybeeninspiredbythebookIntroductiontoFunctionalProgrammingbyRichardBirdandPhilipWadler.However,Qisaninterpretedlanguagewithdynamictypingandeager(leftmost-innermost)evalua-tion,whichismoreinlinewithclassicalfunctionallanguagessuchasLisp.Forthesakeofefficiency,Qscriptsarefirsttranslatedinto“bytecode”(anintermediatebinaryformat)whichisexecutedonavirtualstackmachine.Theinterpreterautomaticallyoptimizestailrecursion,suchthat“iterative”algorithmscanberealizedinconstantstackspace.Besidesthebuilt-inI/Ooperations,thelanguageisfreeofside-effects;inparticular,Qdoesnothavemutablevariables.Qalsoprovidestwonoveland(IMHO)interestingfeature