Advanced LISP Technology (Advanced Information Processing Technology, V. 4)

Book Cover......Page 1
Half-Title......Page 2
Title......Page 4
Copyright......Page 5
Contents......Page 6
Series Foreword......Page 8
Preface......Page 9
The Authors......Page 11
1  Introduction......Page 15
2  PaiLisp......Page 16
3  Outline of PaiLisp Interpreter and Compiler......Page 17
3.2  Evaluator of the PaiLisp/MT interpreter......Page 18
4  The Steal-Help Evaluation Strategy and Its Implementation in the PaiLisp/MT Interpreter......Page 19
4.1  SHE-based Implementation of pcall......Page 20
(3) par-and, par-or and pif......Page 21
4.3.1  Basic costs in the PaiLisp/MT interpreter......Page 22
5  PaiLisp/MT Compiler......Page 23
(1) Compilation rules for quote and a constant......Page 24
(3) Compilation rules for function application (f e1…en)......Page 26
(4) Compilation rules for define and begin......Page 27
(6) Compilation of other Scheme expressions......Page 28
5.2.2  Compilation Rules for pcall......Page 29
5.3  Transforming RM Programs into C Programs......Page 31
6  Conclusion......Page 32
APPENDIX: Extended Register Machine Commands......Page 33
1  Introduction......Page 36
2.2  Process Model......Page 37
2.3  Inter-process Communication and Synchronization......Page 39
2.5  Extent ion to the Lisp Functions......Page 40
3.1  Lisp Process......Page 42
3.2.2  Interprocess Communications among Multiple Hosts......Page 43
4.2  Process Management......Page 44
4.3  Message Management......Page 45
5.1  8-queen Problem......Page 46
5.2  Results......Page 47
5.4  Results......Page 48
Bibliography......Page 49
1  Introduction......Page 52
2  Implementation......Page 53
3  Example......Page 54
4  Synchronization......Page 55
5  Load Balancing......Page 57
6  Modification......Page 59
Bibliography......Page 60
1  Introduction......Page 61
2  EusLisp......Page 62
3.1  Multithread paradigm of Solaris-2......Page 63
3.3  Thread allocation......Page 65
3.5  Comparison with other parallel Lisp systems......Page 66
4.2  Memory allocation in the multithread EusLisp......Page 67
4.4  Garbage Collection......Page 69
5  Concurrent Programming in EusLisp......Page 70
5.3  Thread pool......Page 71
5.4  Synchronization......Page 72
6  Performance Evaluation......Page 73
6.2  Benchmark programs......Page 74
6.4  Performance measurement......Page 75
6.5.1  (1) Bottleneck for shared memory access......Page 76
6.6  Applicability of parallel Lisp......Page 77
7  Conclusion......Page 78
Bibliography......Page 79
1  Introduction......Page 80
2  An Overview......Page 81
3  Parallel List Processing......Page 83
4.1  Data Objects......Page 85
4.2  PE Forms......Page 86
5  Implementation......Page 87
5.2  Data Representation and Allocation......Page 88
5.3  Symbol Cells......Page 89
6  Performance Measurements......Page 90
7  Concluding Remarks......Page 91
Bibliography......Page 92
1  Introduction......Page 94
2  PaiLisp and Its Concurrency Constructs......Page 95
3.1  Basic Idea of Steal-Help Evaluation Strategy......Page 97
3.2  On Implementation of the SHE Strategy for (pcall f e1…ewn)......Page 99
3.3  On SHE Strategies for Other Concurrency Constructs......Page 102
4.1 SHE-based Implementation of future......Page 103
4.2  Comparisons between the LTC-based future and the SHE-based future......Page 105
On implementation of stealable......Page 106
5  Parallelization of delay and Stream Computation......Page 107
6  Conclusion......Page 109
Bibliography......Page 110
1  Introduction......Page 111
3  Futures......Page 112
4  Interaction of Continuations and Futures......Page 113
5  Extended Continuations......Page 114
6  Application 1: Producer and Consumer......Page 115
7  Application 2: Sequential Semantics......Page 117
8  Implementation of Extended Continuations......Page 119
9.2  MultiScheme......Page 120
Bibliography......Page 121
Appendix: Parallel Program for Eight-Queen Problem, Using Extended Continuations......Page 122
8  Lightweight Processes for Real-Time Symbolic Processing......Page 123
3.1  The concept of TAO process......Page 125
3.2  Process Implementation......Page 126
3.3  Concurrent Primitives......Page 128
4  Microkernel......Page 129
5  Stack management......Page 130
6  Process Switching......Page 132
7  Evaluation......Page 133
8  Interrupt Response Delay......Page 136
Bibliography......Page 138
1  Introduction......Page 140
2  Indefinite One-time Continuations......Page 142
Abstract syntax......Page 144
Semantic domain......Page 145
4  Implementation......Page 147
5  Tail-Recursion Optimization......Page 150
6  Performance Evaluation......Page 151
Bibliography......Page 152
1  Introduction......Page 154
4  Implementing a parallel Lisp system with parallel GC......Page 155
5.1  Statements for parallelism......Page 156
5.2.2  Managing information of a Lisp process......Page 157
6.2.1  Root insertion......Page 158
7.1  GC phase switching......Page 159
8  Issues in paralleling list processing......Page 160
9.2  Deciding CPU allocation......Page 161
11.1  Experiments......Page 163
11.2  Programs......Page 164
11.3.2  Performance gain by the number of units......Page 165
11.3.4  GC cycle time......Page 166
11.3.6  Time for root insertion......Page 167
11.4  Experiments on dynamic CPU allocation......Page 168
12  Conclusion......Page 169
Bibliography......Page 170
1  Introduction......Page 172
2  Snapshot-at-beginning Algorithm......Page 174
2.1  Snapshot Algorithm......Page 175
3.1  Generational Garbage Collection......Page 176
3.2  The Basic Idea......Page 177
3.3  Coordination between the imitator and the collector......Page 179
4  Performance Analysis......Page 180
4.1  Performance Analysis of Snapshot Collector......Page 182
4.2  Performance Analysis of Partial Marking Collector......Page 183
5  Experimental Results......Page 184
5.1  Evaluation of Parallel Garbage Collection......Page 185
5.2  Experimental Results......Page 187
5.3  A Comparison with Analysis Results......Page 188
6.1  Design of Partial Marking Garbage Collector on EusLisp......Page 189
6.2  Experimental Results......Page 190
Acknowledgment......Page 191
Bibliography......Page 192
1  Introduction......Page 193
2.1  Heaps......Page 194
2.2  Data Representation and Allocation......Page 195
3  Garbage Collection......Page 196
3.1  Problems in Implementing the Mark Phase......Page 197
3.3  Marking from PEs......Page 198
3.4  The Mark Phase......Page 200
3.5  Compaction of the PE Global Areas......Page 201
4.1  Effects of Parallel Marking......Page 202
4.2  Effects of Buffering......Page 203
4.3  Effects of Repeated Scanning......Page 204
Bibliography......Page 206
1  Introduction......Page 208
2.2  Sorting Technique in GC......Page 211
3.1  PHL and its Data Representation......Page 212
3.2.2  Application of Genetic Order......Page 214
3.2.3  The Offset Table......Page 215
3.3.1  Marking......Page 216
3.4  Relocation......Page 217
4  Analysis of FSC......Page 218
5  Concluding Remarks......Page 220
Bibliography......Page 221
1  Introduction......Page 223
2  Interpreted Functions vs. Compiled Functions......Page 224
3  Automatic Recompilation......Page 225
4  Dependence Graph with Weak Conses......Page 227
5.1  Incremental Compiler......Page 228
5.3  Recompilation......Page 229
5.4  Eval for Automatic Recompilation......Page 231
Bibliography......Page 232
1  Introduction......Page 233
2  FractalView......Page 234
3.1  Traditional algorithm......Page 235
4  Example Sessions......Page 237
6  Discussions......Page 239
7  Conclusion......Page 241
Bibliography......Page 243
Index......Page 245