Programming-Languages.pdf

(861 KB) Pobierz
341209711 UNPDF
ProgrammingLanguages
Version 1.02
MikeGrant
ScottSmith
341209711.002.png
ii
Copyright c 2002-2008ScottF.Smith.Permissionisgrantedtocopy,
distributeand/ormodifythisdocumentunderthetermsoftheGNUFreeDoc-
umentationLicense,Version1.1oranylaterversionpublishedbytheFreeSoft-
wareFoundation;withnoInvariantSections,withnoFront-CoverTexts,and
withnoBack-CoverTexts.Acopyofthelicenseisincludedinthesection
entitled“GNUFreeDocumentationLicense”.
ThisdocumentwaslastcompiledonMarch31,2008.
Contents
Preface
vii
1Introduction 1
1.1ThePre-HistoryofProgrammingLanguages............ 1
1.2ABriefEarlyHistoryofLanguages................. 2
1.3ThisBook............................... 3
2OperationalSemantics 5
2.1AFirstLookatOperationalSemantics............... 5
2.2BNFgrammarsandSyntax..................... 6
2.2.1OperationalSemanticsforLogicExpressions ....... 6
2.2.2OperationalSemanticsandInterpreters.......... 9
2.3TheF[ProgrammingLanguage................... 10
2.3.1F[Syntax........................... 11
2.3.2VariableSubstitution.................... 13
2.3.3OperationalSemanticsforF[................ 17
2.3.4TheExpressivenessofF[.................. 20
2.3.5Russell’sParadoxandEncodingRecursion........ 24
2.3.6Call-By-NameParameterPassing.............. 28
2.4OperationalEquivalence....................... 28
2.4.1DefiningOperationalEquivalence.............. 29
2.4.2ExampleEquivalences.................... 30
2.4.3Capture-AvoidingSubstitution............... 32
2.4.4ProvingEquivalencesHold................. 33
3Tuples,Records,andVariants 35
3.1Tuples................................. 35
3.2Records................................ 36
3.2.1RecordPolymorphism.................... 37
3.2.2TheF[RLanguage...................... 38
3.3Variants................................ 40
3.3.1VariantPolymorphism.................... 40
3.3.2TheF[VLanguage ..................... 40
iii
341209711.003.png
iv CONTENTS
4SideEects:StateandExceptions 45
4.1State.................................. 45
4.1.1TheF[SLanguage...................... 47
4.1.2CyclicalStores........................ 52
4.1.3The“Normal”KindofState................ 54
4.1.4AutomaticGarbageCollection............... 54
4.2Environment-BasedInterpreters................... 55
4.3TheF[SRLanguage......................... 57
4.3.1MultiplicationandFactorial................. 57
4.3.2MergeSort.......................... 58
4.4ExceptionsandOtherControlOperations............. 61
4.4.1 InterpretingReturn..................... 62
4.4.2TheF[XLanguage...................... 64
4.4.3 ImplementingtheF[XInterpreter............. 65
4.4.4EcientImplementationofExceptions........... 67
5Object-OrientedLanguageFeatures 69
5.1EncodingObjectsinF[SR..................... 72
5.1.1SimpleObjects........................ 72
5.1.2ObjectPolymorphism.................... 74
5.1.3 InformationHiding...................... 75
5.1.4Classes ............................ 77
5.1.5 Inheritance.......................... 77
5.1.6DynamicDispatch...................... 79
5.1.7StaticFieldsandMethods.................. 80
5.2TheF[OBLanguage......................... 81
5.2.1ConcreteSyntax....................... 82
5.2.2ADirectInterpreter..................... 83
5.2.3TranslatingF[OBtoF[SR................. 85
6TypeSystems 89
6.1AnOverviewofTypes........................ 90
6.2TF[:ATypedF[Variation..................... 93
6.2.1DesignIssues......................... 93
6.2.2TheTF[Language...................... 94
6.3TypeChecking............................ 98
6.4TypesforanAdvancedLanguage:TF[SRX........... 99
6.5Subtyping...............................103
6.5.1Motivation..........................103
6.5.2TheSTF[RTypeSystem:TF[withRecordsandSub-
typing.............................105
6.5.3 ImplementinganSTF[RTypeChecker..........106
6.5.4SubtypinginOtherLanguages...............107
6.6TypeInferenceandPolymorphism.................107
6.6.1TypeInferenceandPolymorphism.............107
6.6.2AnEquationalTypeSystem:EF[.............108
341209711.004.png
CONTENTS
v
6.6.3PEF[:EF[with Let Polymorphism............113
6.7ConstrainedTypeInference.....................115
7CompilationbyProgramTransformation 119
7.1ClosureConversion..........................120
7.1.1TheOcialClosureConversion...............123
7.2A-Translation.............................124
7.2.1TheOcialA-Translation..................126
7.3FunctionHoisting...........................128
7.4TranslationtoC...........................130
7.4.1MemoryLayout........................131
7.4.2ThetoCtranslation.....................136
7.4.3CompilationtoAssemblycode...............139
7.5Summary...............................139
7.6Optimization.............................140
7.7GarbageCollection..........................140
ADDK:TheF[DevelopmentKit 141
A.1InstallingtheDDK..........................141
A.2Using F [and F [ SR ..........................142
A.2.1TheToplevel .........................142
A.2.2File-BasedIntrepretation..................143
A.3TheDDKSourceCode........................143
A.3.1 $DDKSRC/src/ddk.ml ....................144
A.3.2 $DDKSRC/src/application.ml ..............144
A.3.3 $DDKSRC/src/D/d.ml ....................146
A.3.4 $DDKSRC/src/D/dast.ml ..................146
A.3.5 $DDKSRC/src/D/dpp.ml ...................147
A.3.6ScanningandParsingConcreteSyntax...........148
A.3.7WritinganInterpreter....................148
BGNUFreeDocumentationLicense 151
Bibliography 155
Index
157
341209711.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin