今日の英語 - Control flow analysis in scheme
速読の練習。速読はしない。文の構造を意識しつつ読み進める習慣をつける。方法論はTOEFLテスト速読・速聴大特訓 基礎編で学んだ。
ルールは以下の通り
- トピックセンテンスは ** ** で囲む
- シグナルワードは == ==
- パラグラフのトピックは必ず書く。
- サポート情報のスタイルを書く
Control flow analysis in scheme by Olin Shivers
Abstract
(1) Flow analysis for Scheme like language
Traditional flow analysis techniques, such as the ones typically
employed by optimising Fortran compilers, do not work for
Scheme-like languages. **This paper presents a flow analysis
technique - control flow analysis - which is applicable to
Scheme-like languages.** ==As== a demonstration application, the
information gathered by control flow analysis is used to perform
a traditional flow analysis problem, induction variable
elimination. Extensions and limitations are discussed.
(2) The techniques are backuped by working code.
**The techniques presented in this paper are backed up by
working code.** They are applicable ==not only== to Scheme, ==but
also== to related languages, ==such as== Common Lisp and ML.
メインアイディアは (1)
1章 The task
(3) What flow analysis does.
Flow analysis is a traditional optimising compiler technique
for determining useful information about a program at compile
time. **Flow analysis determines path invariant facts about points
in a program.** A flow analysis ==problem is == a question of the form:
“What is true at a given point p in my program, independent
of the execution path taken to p from the
start of the program?”
==Example== domains of interest might be the following:
Range analysis: What is the range of values that a given
reference to an integer variable is constrained to he within?
Range analysis can be used, ==for instance==, to do array
bounds checking at compile time,
Loop invariant detection: Do all possible prior assignments
to a given variable reference lie outside its containing
loop?
[例示][列挙]
(4) Standard techniques have been developed for the standard imperative languages.
**Over the ==last thirty years==, standard techniques have been developed
to answer these questions for the standard imperative,**
==Algol-like languages (e.g., Pascal, C, Ada, Bliss, and chiefly
Fortran).== Representative texts describing these techniques are
[Dragon], and in more detail, [Hecht]. Flow analysis is perhaps
the chief tool in the optimising compiler writer’s bag of tricks;
an incomplete list of the problems that can be addressed with
flow analysis ==includes== global constant subexpression elimination,
loop invariant detection, redundant assignment detection,
dead code elimination, constant propagation, range analysis,
code hoisting, induction variable elimination, copy propagation,
live variable analysis, loop unrolling, and loop jamming
[列挙][時系列：次につながる？]
(5) Traditional flow analysis techniques have never beeen applied to Lisp.
==However==, **these traditional flow analysis techniques have
never successfully been applied to the Lisp family of computer
languages.** This is a curious omission. The Lisp community
has had sufficient time to consider the problem. Flow analysis
==dates back at least to 1960==, ([Dragon], pp. 516). and Lisp is
one of the oldest computer programming languages currently
in use, rivalled only by Fortran and COBOL.
[対比]
(6) Lisp users may be willing to consider compiler techniques.
==Indeed==, the Lisp community has long been concerned with
the execution speed of their programs. Typical Lisp programs,
such as large AI systems, are both interactive and cycleintensive.
AI researchers often find their research efforts frustrated
by the necessity of waiting several hours for their enormous
Lisp-based production system or back-propagation network
to produce a single run. ==Since== Lisp users are willing to
pay premium prices for special computer architectures specially
designed to execute Lisp rapidly, **we can safely assume they are
even more willing to consider compiler techniques that apply
generally to target machines of any nature.**
[原因と結果]
(7) Flow analysis problems are relevant to Lisp.
==Finally==, **the problems addressed by flow analysis are relevant
to Lisp**. None of the flow analysis problems listed above are
restricted to arithmetic computation; they apply just as well to
symbolic processing. ==Furthermore==, Lisp opens up new domains
of interest. ==For example==, Lisp permits weak typing and run time
type checking. Type information is not statically apparent, as
it is in the Algol family of languages. Type information is
nonetheless extremely important to the efficient execution of
Lisp programs, both to remove run time safety checks of function
arguments, and to open code functions that operate on a
variety of argument types. Thus flow analysis ==offers== a tempting
opportunity to perform type inference from the occurence
of calls to type predicates in Lisp programs.
[追加][例示][列挙]
(8) Flow analysis has much potential with compiling Lisp programs.
==So== **it is clear that flow analysis has much potential with respect
to compiling Lisp programs**. Unfortunately, this potential
has not been realised because Lisp is sufficiently different from
the Algol family of languages that the traditional techniques
developed for them are not applicable.
(9) Difference between Lisp and the Alogol family
**Dialects of Lisp can be ==contrasted== with the Algol family in
==the following ways:==**
Binding versus assignment:
Both classes of language have the same two mechanisms
for associating values with variables: parameter binding
and variable assignment. ==However==, there are differences
in frequency of useage. Algol-family languages tend to encourage
the use of assignment statements; Lisp languages
tend to encourage binding.
Functions as first class citizens:
Functions in modern Lisps are data that can be passed as
arguments to procedures, returned as values from function
calls, stored into arrays, etc..
[列挙][対比]
(10)Lisp's Analysis of binding is a more tractable problem than analysis of assignments
==Since== traditional flow analysis techniques tend to concentrate
on tracking assignment statements, it’s clear that the Lisp
emphasis on variable binding changes the complexion of the
problem. ==Generally, however==, variable binding is a simpler,
weaker operation than the extremely powerful operation of side
effecting assignments. **Analysis of binding is a more tractable
problem than analysis of assignments**, ==because== the semantics of
binding are simpler, and there are more invariants for programanalysis
tools to invoke. In particular, the invariants of the
X-calculus are usually applicable to modern Lisps.
[原因と結果][対比]
(11) Lisp's Higher-order, first class can hinder flow analysis.
==On the other hand==, **the higher-order, first-class nature of Lisp
functions can hinder efforts even to derive basic flow analysis
information from Lisp programs**. I claim it is this aspect of
Lisp which is chiefly responsible for the mysterious absence of
flow analysis from Lisp compilers to date. A brief discussion
of traditional flow analytic techniques will show why this is so.
[対比]
