r6rs.pdf

Revised 6 ReportontheAlgorithmicLanguage

Scheme

M ICHAEL S PERBER

R.K ENT D YBVIG ,M ATTHEW F LATT ,A NTONVAN S TRAATEN

(Editors)

R ICHARD K ELSEY ,W ILLIAM C LINGER ,J ONATHAN R EES

(Editors,Revised 5 ReportontheAlgorithmicLanguageScheme)

R OBERT B RUCE F INDLER ,J ACOB M ATTHEWS

(Authors,formalsemantics)

26September2007

SUMMARY

ThereportgivesadeﬁningdescriptionoftheprogramminglanguageScheme.Schemeisastaticallyscopedandproperly

tail-recursivedialectoftheLispprogramminglanguageinventedbyGuyLewisSteeleJr.andGeraldJaySussman.Itwas

designedtohaveanexceptionallyclearandsimplesemanticsandfewdierentwaystoformexpressions.Awidevariety

ofprogrammingparadigms,includingfunctional,imperative,andmessagepassingstyles,ﬁndconvenientexpressionin

Scheme.

Thisreportisaccompaniedbyareportdescribingstandardlibraries[24];referencestothisdocumentareidentiﬁedby

designationssuchas“librarysection”or“librarychapter”.Itisalsoaccompaniedbyareportcontainingnon-normative

appendices[22].Afourthreportgivessomehistoricalbackgroundandrationalesformanyaspectsofthelanguageand

itslibraries[23].

Theindividualslistedabovearenotthesoleauthorsofthetextofthereport.Overtheyears,thefollowingindividuals

wereinvolvedindiscussionscontributingtothedesignoftheSchemelanguage,andwerelistedasauthorsofpriorreports:

HalAbelson,NormanAdams,DavidBartley,GaryBrooks,WilliamClinger,R.KentDybvig,DanielFriedman,Robert

Halstead,ChrisHanson,ChristopherHaynes,EugeneKohlbecker,DonOxley,KentPitman,JonathanRees,Guillermo

Rozas,GuyL.SteeleJr.,GeraldJaySussman,andMitchellWand.

Inordertohighlightrecentcontributions,theyarenotlistedasauthorsofthisversionofthereport.However,their

contributionandserviceisgratefullyacknowledged.

WeintendthisreporttobelongtotheentireSchemecommunity,andsowegrantpermissiontocopyitinwholeorin

partwithoutfee.Inparticular,weencourageimplementorsofSchemetousethisreportasastartingpointformanuals

andotherdocumentation,modifyingitasnecessary.

2Revised 6 Scheme

CONTENTS

Introduction...................... 3

Descriptionofthelanguage

1OverviewofScheme................. 5

1.1Basictypes.................. 5

1.2Expressions.................. 6

1.3Variablesandbinding............ 6

1.4Deﬁnitions................... 6

1.5Forms..................... 7

1.6Procedures .................. 7

1.7Procedurecallsandsyntactickeywords... 7

1.8Assignment.................. 7

1.9Derivedformsandmacros.......... 8

1.10Syntacticdataanddatumvalues...... 8

1.11Continuations................. 8

1.12Libraries.................... 9

1.13Top-levelprograms.............. 9

2Requirementlevels ................. 9

3Numbers....................... 10

3.1Numericaltower ............... 10

3.2Exactness................... 10

3.3Fixnumsandﬂonums............. 10

3.4Implementationrequirements........ 10

3.5InﬁnitiesandNaNs.............. 11

3.6Distinguished-0.0.............. 11

4Lexicalsyntaxanddatumsyntax......... 11

4.1Notation.................... 12

4.2Lexicalsyntax................. 12

4.3Datumsyntax................. 16

5Semanticconcepts.................. 17

5.1Programsandlibraries............ 17

5.2Variables,keywords,andregions...... 17

5.3Exceptionalsituations............ 18

5.4Argumentchecking.............. 18

5.5Syntaxviolations............... 19

5.6Safety..................... 19

5.7Booleanvalues................ 19

5.8Multiplereturnvalues............ 19

5.9Unspeciﬁedbehavior............. 20

5.10Storagemodel................. 20

5.11Propertailrecursion............. 20

5.12Dynamicextentandthedynamicenvironment20

6Entryformat..................... 20

6.1Syntaxentries................. 21

6.2Procedureentries............... 21

6.3Implementationresponsibilities....... 22

6.4Otherkindsofentries ............ 22

6.5Equivalententries............... 22

6.6Evaluationexamples............. 22

6.7Namingconventions............. 23

7Libraries....................... 23

7.1Libraryform................. 23

7.2Importandexportlevels........... 25

7.3Examples................... 26

8Top-levelprograms................. 27

8.1Top-levelprogramsyntax.......... 27

8.2Top-levelprogramsemantics......... 28

9Primitivesyntax................... 28

9.1Primitiveexpressiontypes.......... 28

9.2Macros..................... 29

10Expansionprocess.................. 29

11Baselibrary..................... 31

11.1Basetypes................... 31

11.2Deﬁnitions................... 31

11.3Bodies..................... 32

11.4Expressions.................. 32

11.5Equivalencepredicates............ 37

11.6Procedurepredicate............. 39

11.7Arithmetic................... 39

11.8Booleans.................... 47

11.9Pairsandlists................. 47

11.10Symbols.................... 49

11.11Characters................... 50

11.12Strings..................... 50

11.13Vectors .................... 51

11.14Errorsandviolations............. 52

11.15Controlfeatures................ 53

11.16Iteration.................... 55

11.17Quasiquotation................ 55

11.18Bindingconstructsforsyntactickeywords. 56

11.19Macrotransformers.............. 57

11.20Tailcallsandtailcontexts.......... 59

Appendices

AFormalsemantics.................. 61

A.1Background.................. 61

A.2Grammar................... 62

A.3Quote..................... 65

A.4Multiplevalues................ 65

A.5Exceptions .................. 67

A.6Arithmeticandbasicforms......... 69

A.7Lists...................... 69

A.8Eqv...................... 69

A.9Proceduresandapplication......... 70

A.10Call/ccanddynamicwind.......... 72

A.11Letrec..................... 73

A.12Underspeciﬁcation.............. 74

BSampledeﬁnitionsforderivedforms........ 75

CAdditionalmaterial................. 77

DExample....................... 77

ELanguagechanges.................. 79

References........................ 80

Alphabeticindexofdeﬁnitionsofconcepts,key-

words,andprocedures ............... 82

Introduction3

INTRODUCTION

Programminglanguagesshouldbedesignednotbypiling

featureontopoffeature,butbyremovingtheweaknesses

andrestrictionsthatmakeadditionalfeaturesappearnec-

essary.Schemedemonstratesthataverysmallnumberof

rulesforformingexpressions,withnorestrictionsonhow

theyarecomposed,sucetoformapracticalandecient

programminglanguagethatisﬂexibleenoughtosupport

mostofthemajorprogrammingparadigmsinusetoday.

•makeprocedurecallspowerfulenoughtoexpressany

formofsequentialcontrol,andallowprogramstoper-

formnon-localcontroloperationswithouttheuseof

globalprogramtransformations;

•allowinteresting,purelyfunctionalprogramstorun

indeﬁnitelywithoutterminatingorrunningoutof

memoryonﬁnite-memorymachines;

Schemewasoneoftheﬁrstprogramminglanguagestoin-

corporateﬁrst-classproceduresasinthelambdacalculus,

therebyprovingtheusefulnessofstaticscoperulesand

blockstructureinadynamicallytypedlanguage.Scheme

wastheﬁrstmajordialectofLisptodistinguishproce-

duresfromlambdaexpressionsandsymbols,touseasin-

glelexicalenvironmentforallvariables,andtoevaluate

theoperatorpositionofaprocedurecallinthesameway

asanoperandposition.Byrelyingentirelyonprocedure

callstoexpressiteration,Schemeemphasizedthefactthat

tail-recursiveprocedurecallsareessentiallygotosthatpass

arguments.Schemewastheﬁrstwidelyusedprogramming

languagetoembraceﬁrst-classescapeprocedures,from

whichallpreviouslyknownsequentialcontrolstructures

canbesynthesized.AsubsequentversionofSchemein-

troducedtheconceptofexactandinexactnumberobjects,

anextensionofCommonLisp’sgenericarithmetic.More

recently,Schemebecametheﬁrstprogramminglanguage

tosupporthygienicmacros,whichpermitthesyntaxofa

block-structuredlanguagetobeextendedinaconsistent

andreliablemanner.

•alloweducatorstousethelanguagetoteachprogram-

mingeectively,atvariouslevelsandwithavarietyof

pedagogicalapproaches;and

•allowresearcherstousethelanguagetoexplorethede-

sign,implementation,andsemanticsofprogramming

languages.

Inaddition,thisreportisintendedto:

•allowprogrammerstocreateanddistributesubstan-

tialprogramsandlibraries,e.g.,implementationsof

SchemeRequestsforImplementation,thatrunwith-

outmodiﬁcationinavarietyofSchemeimplementa-

tions;

•supportprocedural,syntactic,anddataabstraction

morefullybyallowingprogramstodeﬁnehygiene-

bendingandhygiene-breakingsyntacticabstractions

andnewuniquedatatypesalongwithproceduresand

hygienicmacrosinanyscope;

Guidingprinciples

•allowprogrammerstorelyonalevelofautomaticrun-

timetypeandboundscheckingsucienttoensure

typesafety;and

Tohelpguidethestandardizationeort,theeditorshave

adoptedasetofprinciples,presentedbelow.Likethe

SchemelanguagedeﬁnedinRevised 5 ReportontheAlgo-

rithmicLanguageScheme[14],thelanguagedescribedin

thisreportisintendedto:

•allowimplementationstogenerateecientcode,with-

outrequiringprogrammerstouseimplementation-

speciﬁcoperatorsordeclarations.

WhileitwaspossibletowriteportableprogramsinScheme

asdescribedinRevised 5 ReportontheAlgorithmicLan-

guageScheme,andindeedportableSchemeprogramswere

writtenpriortothisreport,manySchemeprogramswere

not,primarilybecauseofthelackofsubstantialstan-

dardizedlibrariesandtheproliferationofimplementation-

speciﬁclanguageadditions.

•allowprogrammerstoreadeachother’scode,andal-

lowdevelopmentofportableprogramsthatcanbeex-

ecutedinanyconformingimplementationofScheme;

•deriveitspowerfromsimplicity,asmallnumberof

generallyusefulcoresyntacticformsandprocedures,

andnounnecessaryrestrictionsonhowtheyarecom-

posed;

Ingeneral,Schemeshouldincludebuildingblocksthatal-

lowawidevarietyoflibrariestobewritten,includecom-

monlyuseduser-levelfeaturestoenhanceportabilityand

readabilityoflibraryandapplicationcode,andexcludefea-

turesthatarelesscommonlyusedandeasilyimplemented

inseparatelibraries.

Thelanguagedescribedinthisreportisintendedtoalsobe

backwardcompatiblewithprogramswritteninSchemeas

•allowprogramstodeﬁnenewproceduresandnewhy-

gienicsyntacticforms;

•supporttherepresentationofprogramsourcecodeas

data;

4Revised 6 Scheme

describedinRevised 5 ReportontheAlgorithmicLanguage

Schemetotheextentpossiblewithoutcompromisingthe

aboveprinciplesandfutureviabilityofthelanguage.With

respecttofutureviability,theeditorshaveoperatedunder

theassumptionthatmanymoreSchemeprogramswillbe

writteninthefuturethanexistinthepresent,sothefu-

tureprogramsarethosewithwhichweshouldbemost

concerned.

JulieSussman,PerryWagle,DanielWeise,HenryWu,and

OzanYigit.

WethankCarolFessenden,DanielFriedman,andChristo-

pherHaynesforpermissiontousetextfromtheScheme

311version4referencemanual.WethankTexasIn-

struments,Inc.forpermissiontousetextfromtheTI

SchemeLanguageReferenceManual[26].Wegladlyac-

knowledgetheinﬂuenceofmanualsforMITScheme[20],

T[21],Scheme84[12],CommonLisp[25],ChezScheme[8],

PLTScheme[11],andAlgol60[1].

WealsothankBettyDexterfortheextremeeortsheput

intosettingthisreportinT E X,andDonaldKnuthforde-

signingtheprogramthatcausedhertroubles.

TheArtiﬁcialIntelligenceLaboratoryoftheMassachusetts

InstituteofTechnology,theComputerScienceDepartment

ofIndianaUniversity,theComputerandInformationSci-

encesDepartmentoftheUniversityofOregon,andthe

NECResearchInstitutesupportedthepreparationofthis

report.SupportfortheMITworkwasprovidedinpartby

theAdvancedResearchProjectsAgencyoftheDepartment

ofDefenseunderOceofNavalResearchcontractN00014-

80-C-0505.SupportfortheIndianaUniversityworkwas

providedbyNSFgrantsNCS83-04567andNCS83-03325.

Acknowledgements

Manypeoplecontributedsigniﬁcanthelptothisrevision

ofthereport.Speciﬁcally,wethankAzizGhuloumand

Andr´evanTonderforcontributingreferenceimplemen-

tationsofthelibrarysystem.WethankAlanBawden,

JohnCowan,SebastianEgner,AubreyJaer,ShiroKawai,

BradleyLucier,andAndr´evanTonderforcontributingin-

sightsonlanguagedesign.MarcFeeley,MartinGasbichler,

AubreyJaer,LarsTHansen,RichardKelsey,OlinShiv-

ers,andAndr´evanTonderwroteSRFIsthatservedas

directinputtothereport.MarcusCrestani,DavidFrese,

AzizGhuloum,ArthurA.Gleckler,EricKnauel,Jonathan

Rees,andAndr´evanTonderthoroughlyproofreadearly

versionsofthereport.

Wewouldalsoliketothankthefollowingpeoplefortheir

helpincreatingthisreport:LauriAlanko,EliBarzilay,

AlanBawden,BrianC.Barnes,PerBothner,TrentBuck,

ThomasBushnell,TaylorCampbell,LudovicCourt`es,Pas-

calCostanza,JohnCowan,RayDillinger,JedDavis,J.A.

“Biep”Durieux,CarlEastlund,SebastianEgner,Tom

Emerson,MarcFeeley,MatthiasFelleisen,AndyFree-

man,KenFriedenbach,MartinGasbichler,ArthurA.

Gleckler,AzizGhuloum,DaveGurnell,LarsTHansen,

BenHarris,SvenHartrumpf,DaveHerman,NilsM.

Holm,StanislavIevlev,JamesJackson,AubreyJaer,

ShiroKawai,AlexanderKjeldaas,EricKnauel,Michael

Lenaghan,FelixKlock,DonovanKolbly,MarcinKowal-

czyk,ThomasLord,BradleyLucier,PauloJ.Matos,Dan

Muresan,RyanNewton,JasonOrendor,ErichRast,

JeRead,JonathanRees,JorgenSch¨afer,PaulSchlie,

ManuelSerrano,OlinShivers,JonathanShapiro,JensAxel

Søgaard,JaySulzberger,PinkuSurana,MikaelTillenius,

SamTobin-Hochstadt,DavidVanHorn,Andr´evanTon-

der,ReinderVerlinde,AlanWatson,AndrewWilcox,Jon

Wilson,LynnWinebarger,KeithWright,andChongkai

Zhu.

Wewouldliketothankthefollowingpeoplefortheirhelp

increatingthepreviousrevisionsofthisreport:Alan

Bawden,MichaelBlair,GeorgeCarrette,AndyCromarty,

PavelCurtis,JeDalton,OlivierDanvy,KenDickey,

BruceDuba,MarcFeeley,AndyFreeman,RichardGabriel,

YektaG¨ursel,KenHaase,RobertHieb,PaulHudak,

MorryKatz,ChrisLindblad,MarkMeyer,JimMiller,Jim

Philbin,JohnRamsdell,MikeSha,JonathanShapiro,

1.OverviewofScheme5

DESCRIPTIONOFTHELANGUAGE

1.OverviewofScheme

ThischaptergivesanoverviewofScheme’ssemantics.The

purposeofthisoverviewistoexplainenoughabouttheba-

sicconceptsofthelanguagetofacilitateunderstandingof

thesubsequentchaptersofthereport,whichareorganized

asareferencemanual.Consequently,thisoverviewisnot

acompleteintroductiontothelanguage,norisitprecise

inallrespectsornormativeinanyway.

InScheme,theargumentexpressionsofaprocedurecall

areevaluatedbeforetheproceduregainscontrol,whether

theprocedureneedstheresultoftheevaluationornot.

C,C#,CommonLisp,Python,Ruby,andSmalltalkare

otherlanguagesthatalwaysevaluateargumentexpressions

beforeinvokingaprocedure.Thisisdistinctfromthelazy-

evaluationsemanticsofHaskell,orthecall-by-namese-

manticsofAlgol60,whereanargumentexpressionisnot

evaluatedunlessitsvalueisneededbytheprocedure.

FollowingAlgol,Schemeisastaticallyscopedprogram-

minglanguage.Eachuseofavariableisassociatedwitha

lexicallyapparentbindingofthatvariable.

Scheme’smodelofarithmeticprovidesarichsetofnumer-

icaltypesandoperationsonthem.Furthermore,itdistin-

guishesexactandinexactnumberobjects:Essentially,an

exactnumberobjectcorrespondstoanumberexactly,and

aninexactnumberobjectistheresultofacomputation

thatinvolvedroundingorothererrors.

Schemehaslatentasopposedtomanifesttypes[28].Types

areassociatedwithobjects(alsocalledvalues)ratherthan

withvariables.(Someauthorsrefertolanguageswithla-

tenttypesasuntyped,weaklytypedordynamicallytyped

languages.)OtherlanguageswithlatenttypesarePython,

Ruby,Smalltalk,andotherdialectsofLisp.Languages

withmanifesttypes(sometimesreferredtoasstrongly

typedorstaticallytypedlanguages)includeAlgol60,C,

C#,Java,Haskell,andML.

1.1.Basictypes

Schemeprogramsmanipulateobjects,whicharealsore-

ferredtoasvalues.Schemeobjectsareorganizedintosets

ofvaluescalledtypes.Thissectiongivesanoverviewofthe

fundamentallyimportanttypesoftheSchemelanguage.

Moretypesaredescribedinlaterchapters.

AllobjectscreatedinthecourseofaSchemecomputation,

includingproceduresandcontinuations,haveunlimitedex-

tent.NoSchemeobjectiseverdestroyed.Thereasonthat

implementationsofSchemedonot(usually!)runoutof

storageisthattheyarepermittedtoreclaimthestorage

occupiedbyanobjectiftheycanprovethattheobject

cannotpossiblymattertoanyfuturecomputation.Other

languagesinwhichmostobjectshaveunlimitedextentin-

cludeC#,Java,Haskell,mostLispdialects,ML,Python,

Ruby,andSmalltalk.

Note:AsSchemeislatentlytyped,theuseofthetermtype

inthisreportdiersfromtheuseoftheterminthecontextof

otherlanguages,particularlythosewithmanifesttyping.

BooleansAbooleanisatruthvalue,andcanbeeither

trueorfalse.InScheme,theobjectfor“false”iswritten #f .

Theobjectfor“true”iswritten #t .Inmostplaceswherea

truthvalueisexpected,however,anyobjectdierentfrom

#f countsastrue.

ImplementationsofSchememustbeproperlytail-

recursive.Thisallowstheexecutionofaniterativecom-

putationinconstantspace,eveniftheiterativecompu-

tationisdescribedbyasyntacticallyrecursiveprocedure.

Thuswithaproperlytail-recursiveimplementation,iter-

ationcanbeexpressedusingtheordinaryprocedure-call

mechanics,sothatspecialiterationconstructsareuseful

onlyassyntacticsugar.

NumbersSchemesupportsarichvarietyofnumerical

datatypes,includingobjectsrepresentingintegersofarbi-

traryprecision,rationalnumbers,complexnumbers,and

inexactnumbersofvariouskinds.Chapter3givesan

overviewofthestructureofScheme’snumericaltower.

Schemewasoneoftheﬁrstlanguagestosupportproce-

duresasobjectsintheirownright.Procedurescanbe

createddynamically,storedindatastructures,returned

asresultsofprocedures,andsoon.Otherlanguageswith

thesepropertiesincludeCommonLisp,Haskell,ML,Ruby,

andSmalltalk.

CharactersSchemecharactersmostlycorrespondto

textualcharacters.Moreprecisely,theyareisomorphic

tothescalarvaluesoftheUnicodestandard.

OnedistinguishingfeatureofSchemeisthatcontinuations,

whichinmostotherlanguagesonlyoperatebehindthe

scenes,alsohave“ﬁrst-class”status.First-classcontinu-

ationsareusefulforimplementingawidevarietyofad-

vancedcontrolconstructs,includingnon-localexits,back-

tracking,andcoroutines.

StringsStringsareﬁnitesequencesofcharacterswith

ﬁxedlengthandthusrepresentarbitraryUnicodetexts.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: