Why Functional Programming matters.pdf

(161 KB) Pobierz
736010551 UNPDF
WhyFunctionalProgrammingMatters
JohnHughes,Institutionenf¨orDatavetenskap,
ChalmersTekniskaH¨ogskola,
41296G¨oteborg,
SWEDEN.rjmh@cs.chalmers.se
Thispaperdatesfrom1984,andcirculatedasaChalmersmemoformany
years.Slightlyrevisedversionsappearedin1989and1990as[Hug90]and
[Hug89].ThisversionisbasedontheoriginalChalmersmemo nroff
source,lightlyeditedforLaTeXandtobringitclosertothepublishedver-
sions,andwithoneortwoerrorscorrected.Pleaseexcusetheslightlyold-
fashionedtype-setting,andthefactthattheexamplesarenotinHaskell!
Abstract
Assoftwarebecomesmoreandmorecomplex,itismoreandmore
importanttostructureitwell.Well-structuredsoftwareiseasytowrite,
easytodebug,andprovidesacollectionofmodulesthatcanbere-used
toreducefutureprogrammingcosts.Conventionallanguagesplacecon-
ceptuallimitsonthewayproblemscanbemodularised.Functionallan-
guagespushthoselimitsback.Inthispaperweshowthattwofeaturesof
functionallanguagesinparticular,higher-orderfunctionsandlazyeval-
uation,cancontributegreatlytomodularity.Asexamples,wemanipu-
latelistsandtrees,programseveralnumericalalgorithms,andimplement
thealpha-betaheuristic(analgorithmfromArtificialIntelligenceusedin
game-playingprograms).Sincemodularityisthekeytosuccessfulpro-
gramming,functionallanguagesarevitallyimportanttotherealworld.
1Introduction
Thispaperisanattempttodemonstratetothe“realworld”thatfunctional
programmingisvitallyimportant,andalsotohelpfunctionalprogrammers
exploititsadvantagestothefullbymakingitclearwhatthoseadvantagesare.
Functionalprogrammingissocalledbecauseaprogramconsistsentirelyof
functions.Themainprogramitselfiswrittenasafunctionwhichreceivesthe
program’sinputasitsargumentanddeliverstheprogram’soutputasitsresult.
Typicallythemainfunctionisdefinedintermsofotherfunctions,whichin
turnaredefinedintermsofstillmorefunctions,untilatthebottomlevelthe
functionsarelanguageprimitives.Thesefunctionsaremuchlikeordinarymath-
ematicalfunctions,andinthispaperwillbedefinedbyordinaryequations.Our
1
notationfollowsTurner’slanguageMiranda(TM)[Tur85],butshouldberead-
ablewithnopriorknowledgeoffunctionallanguages.(Mirandaisatrademark
ofResearchSoftwareLtd.)
Thespecialcharacteristicsandadvantagesoffunctionalprogrammingare
oftensummedupmoreorlessasfollows.Functionalprogramscontainno
assignmentstatements,sovariables,oncegivenavalue,neverchange.More
generally,functionalprogramscontainnoside-e®ectsatall.Afunctioncallcan
havenoe®ectotherthantocomputeitsresult.Thiseliminatesamajorsource
ofbugs,andalsomakestheorderofexecutionirrelevant-sincenoside-e®ect
canchangethevalueofanexpression,itcanbeevaluatedatanytime.This
relievestheprogrammeroftheburdenofprescribingtheflowofcontrol.Since
expressionscanbeevaluatedatanytime,onecanfreelyreplacevariablesby
theirvaluesandviceversa-thatis,programsare“referentiallytransparent”.
Thisfreedomhelpsmakefunctionalprogramsmoretractablemathematically
thantheirconventionalcounterparts.
Suchacatalogueof“advantages”isallverywell,butonemustnotbesur-
prisedifoutsidersdon’ttakeittooseriously.Itsaysalotaboutwhatfunctional
programmingis not (ithasnoassignment,nosidee®ects,noflowofcontrol)but
notmuchaboutwhatitis.Thefunctionalprogrammersoundsratherlikeame-
dievalmonk,denyinghimselfthepleasuresoflifeinthehopethatitwillmake
himvirtuous.Tothosemoreinterestedinmaterialbenefits,these“advantages”
arenotveryconvincing.
Functionalprogrammersarguethatthere are greatmaterialbenefits-that
afunctionalprogrammerisanorderofmagnitudemoreproductivethanhis
conventionalcounterpart,becausefunctionalprogramsareanorderofmagni-
tudeshorter.Yetwhyshouldthisbe?Theonlyfaintlyplausiblereasonone
cansuggestonthebasisofthese“advantages”isthatconventionalprograms
consistof90%assignmentstatements,andinfunctionalprogramsthesecanbe
omitted!Thisisplainlyridiculous.Ifomittingassignmentstatementsbrought
suchenormousbenefitsthenFORTRANprogrammerswouldhavebeendoingit
fortwentyyears.Itisalogicalimpossibilitytomakealanguagemorepowerful
byomittingfeatures,nomatterhowbadtheymaybe.
Evenafunctionalprogrammershouldbedissatisfiedwiththeseso-called
advantages,becausetheygivehimnohelpinexploitingthepoweroffunctional
languages.Onecannotwriteaprogramwhichisparticularlylackinginassign-
mentstatements,orparticularlyreferentiallytransparent.Thereisnoyardstick
ofprogramqualityhere,andthereforenoidealtoaimat.
Clearlythischaracterisationoffunctionalprogrammingisinadequate.We
mustfindsomethingtoputinitsplace-somethingwhichnotonlyexplainsthe
poweroffunctionalprogramming,butalsogivesaclearindicationofwhatthe
functionalprogrammershouldstrivetowards.
2
2AnAnalogywithStructuredProgramming
Itishelpfultodrawananalogybetweenfunctionalandstructuredprogramming.
Inthepast,thecharacteristicsandadvantagesofstructuredprogramminghave
beensummedupmoreorlessasfollows.Structuredprogramscontainnogoto
statements.Blocksinastructuredprogramdonothavemultipleentriesorexits.
Structuredprogramsaremoretractablemathematicallythantheirunstructured
counterparts.These“advantages”ofstructuredprogrammingareverysimilarin
spirittothe“advantages”offunctionalprogrammingwediscussedearlier.They
areessentiallynegativestatements,andhaveledtomuchfruitlessargument
about“essentialgotos”andsoon.
Withthebenefitofhindsight,itisclearthatthesepropertiesofstructured
programs,althoughhelpful,donotgototheheartofthematter.Themostim-
portantdi®erencebetweenstructuredandunstructuredprogramsisthatstruc-
turedprogramsaredesignedinamodularway.Modulardesignbringswith
itgreatproductivityimprovements.Firstofall,smallmodulescanbecoded
quicklyandeasily.Secondly,generalpurposemodulescanbere-used,leadingto
fasterdevelopmentofsubsequentprograms.Thirdly,themodulesofaprogram
canbetestedindependently,helpingtoreducethetimespentdebugging.
Theabsenceofgotos,andsoon,hasverylittletodowiththis.Ithelpswith
“programminginthesmall”,whereasmodulardesignhelpswith“programming
inthelarge”.Thusonecanenjoythebenefitsofstructuredprogrammingin
FORTRANorassemblylanguage,evenifitisalittlemorework.
Itisnowgenerallyacceptedthatmodulardesignisthekeytosuccessfulpro-
gramming,andlanguagessuchasModula-II[Wir82],Ada[oD80]andStandard
ML[MTH90]includefeaturesspecificallydesignedtohelpimprovemodularity.
However,thereisaveryimportantpointthatisoftenmissed.Whenwriting
amodularprogramtosolveaproblem,onefirstdividestheproblemintosub-
problems,thensolvesthesub-problemsandcombinesthesolutions.Theways
inwhichonecandivideuptheoriginalproblemdependdirectlyontheways
inwhichonecangluesolutionstogether.Therefore,toincreaseonesability
tomodulariseaproblemconceptually,onemustprovidenewkindsofgluein
theprogramminglanguage.Complicatedscoperulesandprovisionforseparate
compilationonlyhelpwithclericaldetails;theyo®ernonewconceptualtools
fordecomposingproblems.
Onecanappreciatetheimportanceofgluebyananalogywithcarpentry.
Achaircanbemadequiteeasilybymakingtheparts-seat,legs,backetc.-
andstickingthemtogetherintherightway.Butthisdependsonanability
tomakejointsandwoodglue.Lackingthatability,theonlywaytomakea
chairistocarveitinonepieceoutofasolidblockofwood,amuchharder
task.Thisexampledemonstratesboththeenormouspowerofmodularisation
andtheimportanceofhavingtherightglue.
Nowletusreturntofunctionalprogramming.Weshallargueintheremain-
derofthispaperthatfunctionallanguagesprovidetwonew,veryimportant
kindsofglue.Weshallgivemanyexamplesofprogramsthatcanbemodu-
larisedinnewways,andtherebygreatlysimplified.Thisisthekeytofunctional
3
programming’spower-itallowsgreatlyimprovedmodularisation.Itisalsothe
goalforwhichfunctionalprogrammersmuststrive-smallerandsimplerand
moregeneralmodules,gluedtogetherwiththenewgluesweshalldescribe.
3GlueingFunctionsTogether
Thefirstofthetwonewkindsofglueenablessimplefunctionstobeglued
togethertomakemorecomplexones.Itcanbeillustratedwithasimplelist-
processingproblem-addinguptheelementsofalist.Wedefinelistsby
listofX::=nil|consX(listofX)
whichmeansthatalistofXs(whateverXis)iseithernil,representingalist
withnoelements,oritisaconsofanXandanotherlistofXs.Aconsrepresents
alistwhosefirstelementistheXandwhosesecondandsubsequentelements
aretheelementsoftheotherlistofXs.Xheremaystandforanytype-for
example,ifXis“integer”thenthedefinitionsaysthatalistofintegersiseither
emptyoraconsofanintegerandanotherlistofintegers.Followingnormal
practice,wewillwritedownlistssimplybyenclosingtheirelementsinsquare
brackets,ratherthanbywritingconsesandnilsexplicitly.Thisissimplya
shorthandfornotationalconvenience.Forexample,
[] means nil
[1] means cons1nil
[1,2,3] means cons1(cons2(cons3nil))
Theelementsofalistcanbeaddedupbyarecursivefunction sum .Summust
bedefinedfortwokindsofargument:anemptylist(nil),andacons.Sincethe
sumofnonumbersiszero,wedefine
sumnil=0
andsincethesumofaconscanbecalculatedbyaddingthefirstelementofthe
listtothesumoftheothers,wecandefine
sum(consnumlist)=num+sumlist
Examiningthisdefinition,weseethatonlytheboxedpartsbelowarespecific
tocomputingasum.
+---+
sumnil=|0|
+---+
+---+
sum(consnumlist)=num|+|sumlist
+---+
Thismeansthatthecomputationofasumcanbemodularisedbyglueing
togetherageneralrecursivepatternandtheboxedparts.Thisrecursivepattern
isconventionallycalled reduce andsosumcanbeexpressedas
4
sum=reduceadd0
whereforconveniencereduceispassedatwoargumentfunction add ratherthan
anoperator.Addisjustdefinedby
addxy=x+y
Thedefinitionofreducecanbederivedjustbyparameterisingthedefinitionof
sum,giving
(reducefx)nil=x
(reducefx)(consal)=fa((reducefx)l)
Herewehavewrittenbracketsaround(reducefx)tomakeitclearthatit
replacessum.Conventionallythebracketsareomitted,andso((reducefx)l)is
writtenas(reducefxl).Afunctionof3argumentssuchasreduce,appliedto
only2istakentobeafunctionoftheoneremainingargument,andingeneral,
afunctionof n argumentsappliedtoonly m ( <n )istakentobeafunctionof
the n¡m remainingones.Wewillfollowthisconventioninfuture.
Havingmodularisedsuminthisway,wecanreapbenefitsbyre-usingthe
parts.Themostinterestingpartisreduce,whichcanbeusedtowritedown
afunctionformultiplyingtogethertheelementsofalistwithnofurtherpro-
gramming:
product=reducemultiply1
Itcanalsobeusedtotestwhetheranyofalistofbooleansistrue
anytrue=reduceorfalse
orwhethertheyarealltrue
alltrue=reduceandtrue
Onewaytounderstand(reducefa)isasafunctionthatreplacesalloccurrences
ofconsinalistbyf,andalloccurrencesofnilbya.Takingthelist[1,2,3]as
anexample,sincethismeans
cons1(cons2(cons3nil))
then(reduceadd0)convertsitinto
add1(add2(add30))=6
and(reducemultiply1)convertsitinto
multiply1(multiply2(multiply31))=6
Nowitisobviousthat(reduceconsnil)justcopiesalist.Sinceonelistcanbe
appendedtoanotherbyconsingitselementsontothefront,wefind
appendab=reduceconsba
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin