-
Notifications
You must be signed in to change notification settings - Fork 9
/
sideeff.bib
451 lines (392 loc) · 16.3 KB
/
sideeff.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
%%% sideeff.bib -*- BibTeX -*-
%%% Bibliography on side effects / purity / immutability.
@Book{AbelsonS,
Key={Abelson, Sussman},
Author={Abelson, Harold and Gerald Jay Sussman},
Publisher={MIT Press and McGraw-Hill},
Title={Structure and Interpretation of Computer Programs},
Year={1985}
}
@Article{Boehm85,
Author="Hans-Juergen Boehm",
Journal=toplas,
Title="Side Effects and Aliasing Can Have Simple Axiomatic Descriptions",
Year=1985,
Month=oct,
Pages="637--655",
Volume=7,
Number=4
}
@techreport{Cardelli85:typetype,
Author={Luca Cardelli},
Title={A polymorphic calculus with type:type},
institution={DEC System Research Center},
number={00},
Year=1985}
@inproceedings{Cardelli85:Amber,
author = {Luca Cardelli},
title = {Amber},
booktitle = {Combinators and functional programming languages},
series={$13^{th}$ Summer School of the LITP},
publisher = {Le Val D'Ajol, Vosges, France},
year = 1985}
@TechReport{Hailperin85,
Key={Hailperin},
Author={Hailperin, Max},
Institution={MIT},
Title={What Price for Eliminating Expression Side-Effects?},
Year={1985},
Number={281},
Type={MIT-LCS-TM}
}
@unpublished{Halpern81:PhD,
key={Halpern},
author={Halpern, J.},
title={Axiomatic Definitions of Programming Languages and Logics of Programs},
year={1981},
note={Ph.D. dissertation, Dept. of Mathematics, Harvard Univ. Cambridge, MA.}
}
@TechReport{Halpern81,
Key={Halpern},
Author={Halpern, J.},
Title={On the Expressive Power of Dynamic Logic. II},
Number={MIT-LCS-TM-204},
Institution={MIT},
Year=1981}
@Inproceedings{Halpern84a,
Key={Halpern},
Author={Halpern, Joseph Y.},
crossref= "POPL84",
Title={A good {Hoare} axiom system for an {\sc Algol}-like language},
Pages={262--271}
}
@article{Halpern84,
key={Halpern},
author={Halpern, J.},
journal=IandC,
title={Deterministic process logic is elementary},
year={1984},
pages={56--89},
volume=57
}
@inproceedings(HalpernMT84,
key="Halpern, Meyer, Trakhtenbrot",
Author="Halpern, Joseph Y. and Albert R. Meyer and Boris Trakhtenbrot",
title="The semantics of local storage, or what makes the free-list free?",
crossref = "POPL84",
pages="245--257"
)
@article{HalpernR83a,
key={Halpern, Reif},
author={Halpern, J. and J. Reif},
journal=TCS,
title={The propositional dynamic logic of deterministic, well-structured programs},
year={1983},
pages={127--165},
volume=27
}
@Inproceedings{HalpernR83,
Key={Halpern, Rabin},
Author={Halpern, J. and M. Rabin},
Booktitle={$15^{th}$ Symp. Theory of Computing},
publisher={ACM},
Title={The logic of likelihood},
Year={1983},
Pages={310--319}
}
@Unpublished{LucassenG,
Key={Lucassen, Gifford},
Author={Lucassen, John M. and David K. Gifford},
Title={A strongly typed language with an extensible type system},
Note={MIT, extended abstract submitted to POPL 86.},
Year={1985}
}
@Book{Mason86,
Author="Ian A. Mason",
Publisher="Center for the Study of Language and Information",
Title="The Semantics of Destructive Lisp",
Year=1986,
Series="Center for the Study of Language and Information Lecture Notes",
Volume=5
}
@article{Meyer.1982,
author = {Albert R. Meyer},
title = {What is a Model of the Lambda Calculus?},
journal = iandc,
volume = 52,
number = 1,
month = jan,
year = 1982,
pages = {87--122}
}
@article{MeyerH.1982,
Author={Albert R. Meyer and Joseph Y. Halpern},
Title={Axiomatic definitions of programming languages:
a theoretical assessment},
journal=JACM,
Volume=29,
Year=1982,
pages={555--576}
}
@Inproceedings{Meyer83,
Key={Meyer},
Author={Meyer, A. R.},
Booktitle={INFORMATION PROCESSING 83},
Publisher={Elsevier Science Publishers B.V. (North Holland)},
Title={Understanding {\sc Algol}: the view of a recent convert to
denotational semantics},
Year={1983},
Editor={R. E. A. Mason},
Pages={951--961}
}
@Inproceedings{Schwartz79,
Key={Schwartz},
Author={Schwartz, Richard L.},
Booktitle={$6^{th}$ Int'l. Coll. Automata, Languages and Programming},
Publisher={Springer-Verlag},
Title={An axiomatic treatment of {\sc Algol} 68 routines},
Year=1979,
Editor={Maurer, H.},
Pages={530--545},
Series=lncs,
Volume=71
}
@inproceedings{TrakhtenbrotHM.1984,
Author={Boris A. Trakhtenbrot and Joseph Y. Halpern and Albert R. Meyer},
Title={From denotational to operational and axiomatic semantics for
{\sc Algol}-like languages: an overview},
Booktitle={Logic of Programs, Proceedings 1983},
Publisher={Springer-Verlag}, series="Lecture Notes for Computer Science",
editor={Edmund Clarke and Dexter Kozen},
volume=164,
Year=1984,
pages={474--500}
}
% Previously DamasM82
@inproceedings(DamasM1982,
author="Luis Damas and Robin Milner",
title="Principal type-schemes for functional programs",
booktitle="$9^{th}$ Symp. Principles of Programming Languages",
publisher={ACM},
year="1982",
pages="207--212"
)
@misc{Mitchell88,
author = {John Mitchell},
year = {Communication in the electronic forum
types@theory.lcs.mit.edu, April 6, 1988}
}
@InProceedings{Rountev2004,
author = "Atanas Rountev",
title = "Precise identification of side-effect-free methods in {Java}",
crossref = "ICSM2004",
pages = "82--91",
abstract =
"Knowing which methods do not have side effects is necessary in a variety of
software tools for program understanding, restructuring, optimization, and
verification. We present a general approach for identifying
side-effect-free methods in Java software. Our technique is parameterized
by class analysis and is designed to work on incomplete programs. We
present empirical results from two instantiations of the approach, based on
Rapid Type Analysis and on points-to analysis. In our experiments with
several components, on average 22\% of the investigated methods were
identified as free of side effects. We also present a precision evaluation
which shows that the approach achieves almost perfect precision---i.e., it
almost never misses methods that in reality have no side effects. These
results indicate that very precise identification of side-effect-free
methods is possible with simple and inexpensive analysis techniques, and
therefore can be easily incorporated in software tools.",
}
@InProceedings{SalcianuR2005,
author = "Alexandru S{\u{a}}lcianu and Martin C. Rinard",
authorASCII = "Alexandru Salcianu",
title = "Purity and side-effect analysis for {Java} programs",
crossref = "VMCAI2005",
pages = "199--215",
abstract =
"We present a new purity and side effect analysis for Java programs. A
method is pure if it does not mutate any location that exists in the
program state right before the invocation of the method. Our analysis is
built on top of a combined pointer and escape analysis, and is able to
determine that methods are pure even when the methods mutate the heap,
provided they mutate only new objects. Our analysis provides useful
information even for impure methods. In particular, it can recognize
read-only parameters (a parameter is read-only if the method does not
mutate any objects transitively reachable from the parameter) and safe
parameters (a parameter is safe if it is read-only and the method does not
create any new externally visible heap paths to objects transitively
reachable from the parameter). The analysis can also generate regular
expressions that characterize the externally visible heap locations that
the method mutates. We have implemented our analysis and used it to
analyze several applications. Our results show that our analysis
effectively recognizes a variety of pure methods, including pure methods
that allocate and mutate complex auxiliary data structures."
}
@PhdThesis{Salcianu2006,
author = "Alexandru S{\u{a}}lcianu",
title = "Pointer analysis for {Java} programs: Novel techniques and applications",
school = MITEECS,
year = 2006,
address = MITaddr,
month = sep,
}
@Article{DoladoHOH2003,
author = "Jos{\'e} Javier Dolado and Mark Harman and Mari Carmen Otero and Lin Hu",
title = "An Empirical Investigation of the Influence of a Type of Side Effects on Program Comprehension",
journal = TSE,
year = 2003,
volume = 29,
number = 7,
pages = "665--670",
month = jul,
abstract =
"This paper reports the results of a study on the impact of a type of side
effect (SE) upon program comprehension. We applied a crossover design on
different tests involving fragments of C code that include increment and
decrement operators. Each test had an SE version and a side-effect-free
counterpart. The variables measured in the treatments were the number of
correct answers and the time spent in answering. The results show that the
side-effect operators considered significantly reduce performance in
comprehension-related tasks, providing empirical justification for the
belief that side effects are harmful.",
}
@InProceedings{CooperK88,
author = "Keith D. Cooper and Ken Kennedy",
title = "Interprocedural side-effect analysis in linear time",
crossref = "PLDI88",
pages = "57--66",
abstract =
"We present a new method for solving Banning's alias-free flow-insensitive
side-effect analysis problem. The algorithm employs a new data structure,
called the binding multi-graph, along with depth-first search to achieve a
running time that is linear in the size of the call multi-graph of the
program. This method can be extended to produce fast algorithms for
data-flow problems with more complex lattice structures."
}
@InProceedings{Banning79,
author = "John P. Banning",
title = "An efficient way to find the side effects of procedure
calls and the aliases of variables",
crossref = "POPL79",
pages = "29--41",
}
@InProceedings{LeLH2005,
author = "Anatole Le and Ond\v{r}ej Lhot{\'a}k and Laurie Hendren",
authorASCII = "Ondrej Lhotak",
title = "Using inter-procedural side-effect information in {JIT} optimizations",
crossref = "CC2005",
pages = "287--304",
abstract =
"Inter-procedural analyses such as side-effect analysis can provide
information useful for performing aggressive optimizations. We present a
study of whether side-effect information improves performance in
just-in-time (JIT) compilers, and if so, what level of analysis precision
is needed.
\par
We used SPARK, the inter-procedural analysis component of the SOOT Java
analysis and optimization framework, to compute side-effect information and
encode it in class files. We modified Jikes RVM, a research JIT, to make
use of side-effect analysis in local common sub-expression elimination,
heap SSA, redundant load elimination and loop-invariant code motion. On the
SpecJVM98 benchmarks, we measured the static number of memory operations
removed, the dynamic counts of memory reads eliminated, and the execution
time.
\par
Our results show that the use of side-effect analysis increases the number
of static opportunities for load elimination by up to 98\%, and reduces
dynamic field read instructions by up to 27\%. Side-effect information
enabled speedups in the range of 1.08x to 1.20x for some
benchmarks. Finally, among the different levels of precision of side-effect
information, a simple side-effect analysis is usually sufficient to obtain
most of these speedups.",
}
@MastersThesis{Razafimahefa1999,
author = "Chrislain Razafimahefa",
title = "A study of side-effect analyses for {Java}",
school = "School of Computer Science, McGill University",
year = 1999,
address = Montreal,
month = dec,
abstract =
"In the context of an object-oriented programming language such as Java, the
ubiquitous use of instance fields and the presence of pointers (references
to objects) make it difficult to understand a program's memory
usage. Understanding memory usage is a key element for optimizing programs
and side-effect analysis, an analysis to estimate variables that are
inspected or altered by a computation, is of prime importance for
understanding and optimizing Java programs.
\par
In this thesis, we study the impact of a set of practical side-effect
analyses on optimizing Java programs. The main contribution of the thesis
is the design and implementation of two groups of analyses, namely
type-based analysis and refers-to analysis. These analyses use different
strategies to capture the effect of an instruction on variables present in
the program. The former uses type information whereas the second models the
program's storage shape graph. In both type-based analysis and refers-to
analysis, two variations of the analysis are presented, one which considers
the internal structure of objects such as fields as a key element of the
analysis, and another which considers objects as aggregates and ignores
their internal structure.
\par
In order to assess the effectiveness of each analysis, we have implemented
loop- invariant removal, an optimization which moves invariant computation
out of loops. We used the Soot framework to implement the analyses and the
optimization. We present both static and dynamic results based on
experiments performed on a set of Java benchmarks of various sizes. Our
results suggests that side-effect analysis is beneficial. Furthermore, we
also notice that analyses that exploit the internal structure of objects,
as a key element of the analysis, performs significantly better than their
counterparts which do not.",
}
@InProceedings{XuPV2007,
author = "Haiying Xu and Christopher J. F. Pickett and Clark Verbrugge",
title = "Dynamic purity analysis for {Java} programs",
crossref = "PASTE2007",
pages = "75--82",
abstract =
"The pure methods in a program are those that exhibit functional or side
effect free behaviour, a useful property in many contexts. However,
existing purity investigations present primarily static results. We perform
a detailed examination of dynamic method purity in Java programs using a
JVM-based analysis. We evaluate multiple purity definitions that range from
strong to weak, consider purity forms specific to dynamic execution, and
accommodate constraints imposed by an example consumer application,
memoization. We show that while dynamic method purity is actually fairly
consistent between programs, examining pure invocation counts and the
percentage of the bytecode instruction stream contained within some pure
method reveals great variation. We also show that while weakening purity
definitions exposes considerable dynamic purity, consumer requirements can
limit the actual utility of this information.",
}
@InProceedings{DemskyR2002,
author = "Brian Demsky and Martin Rinard",
title = "Role-based exploration of object-oriented programs",
crossref = "ICSE2002",
pages = "313--324",
}
@InProceedings{LeinoPHZ02,
author = "K. Rustan M. Leino and Arnd Poetzsch-Heffter and Yunhong Zhou",
title = "Using data groups to specify and check side effects",
crossref = "PLDI2002",
pages = "246--257",
doi = {https://doi.acm.org/10.1145/512529.512559},
}
@InProceedings{KuncakL2003,
author = "Viktor Kuncak and Rustan Leino",
title = "In-place refinement for effect checking",
crossref = "AVIS2003",
NEEDpages = "*",
}
% LocalWords: sideeff AbelsonS Sussman Boehm Juergen toplas oct Luca Hu
% LocalWords: techreport Cardelli typetype inproceedings booktitle LITP
% LocalWords: D'Ajol Vosges TechReport Hailperin Halpern HalpernMT Reif
% LocalWords: Trakhtenbrot HalpernR TCS Symp LucassenG Lucassen iandc
% LocalWords: jan MeyerH JACM Int'l Coll Maurer lncs TrakhtenbrotHM RTA
% LocalWords: Kozen Milner DamasM Damas misc InProceedings Rountev ICSM
% LocalWords: Atanas addr java SalcianuR lcianu authorASCII prestate ej
% LocalWords: PhdThesis MITEECS MITaddr sep DoladoHOH Jos Dolado Harman
% LocalWords: Otero TSE jul CooperK Banning's mis LeLH Ond Lhot Hendren
% LocalWords: Ondrej Lhotak CC RVM SSA SpecJVM AMD CHA sideeffect Ghiya
% LocalWords: Modula Razafimahefa VM Pechtchanski Sarkar behaviour dec
% LocalWords: MastersThesis Chrislain inlining XuPV Haiying
% LocalWords: Xu Verbrugge NEEDpages mtrt DemskyR