今日の英語 - Control flow analysis in scheme その2

study english

速読の練習。速読はしない。文の構造を意識しつつ読み進める習慣をつける。方法論はTOEFLテスト速読・速聴大特訓 基礎編で。


読み進めて分かったが良い論文。読んだことのあるCPSの説明で一番分かりやすい。


ルールは以下の通り（前回からいくつか追加）

  • トピックセンテンスは ** ** で囲む
  • シグナルワードは == ==
  • パラグラフのトピックは必ず書く。
  • サポート情報のスタイルを書く
  • 列挙には(1)(2)(3)と振る
  • 対比には (A)(a) のように目印
  • 例示は何に対するサポートかを一言書き添える
  • 原因・結果には => を

2 The Problem

Pascal example

** Consider the following piece of Pascal code**:

FOR i := 0 to 30 DO BEGIN
s := a[i];
IF s < 0 THEN
a[i] := (s+4)^2
ELSE
a[i] := cos(s+4);
b[i] := s+4;
END

Flow analysis requires construction of a cotirolflow graph for
the code fragment (fig. 1).

Example of control flow graph

Every vertex in the graph represents a basic block of code:
a sequence of instructions such that the only branches into the
block are branches to the beginning of the block, and the only
branches from the block occur at the end of the block. The
edges in the graph represent possible transfers of control between
basic blocks. **Having constructed the control flow graph,=>
we can use graph algorithms to determine path invariant facts
about the verteces.**

control flow analsys can elminate a redundant addition.

** In this example, ==for instance==, we can determine that on all
control paths from START to the dashed block (b [i] : =s+4 ;
i : =i t 1). the expression s+4 is evaluated with no subsequent
assignments to s. ==Hence==, ==by== caching the result of s+4
in a temporary, we can eliminate the redundant addition in
b [ i ] : =s+4. ** This information is ==arrived at through== <= consideration
of the paths through the control flow graph.

The problem with Lisp is that there is no static controlflow

**The problem with Lisp is that there is no static controlflow
graph at compile time.** [直前を例示]==Consider== the following fragment of
Scheme code:

(let ((f (foo 7 g k))
      (h (aref a7 i j)))
  (if (< i j) (h 30) (f h)))

==Consider== the control flow of the if expression. Its graph is:

After evaluating the conditional’s predicate, control can transfer
either to the function that is the value of h, or to the function
that is the value of f. ==But what’==s the value of f? What’s the
value of h? Unhappily, they are computed at run time.

In order to do flow analysis, we need a control flow graph, but in order to determine control flow graphs, we need to do flow analysis.

==If== we knew all the functions that h and f could possibly be
bound to. independent of program execution, =>[原因・結果] we could build
a control flow graph for the code fragment. ==So==, if we wish
a control flow graph for a piece of Scheme code, => we need to
answer the following question: for every function call in the
program, what are the possible lambda expressions that call
could be a jump to? ==But== this is a flow analysis question! **So
with regard to flow analysis in Lisp. we are faced with the
following unfortunate situation:
In order to do flow analysis, we need a control flow graph.
In order to determine control flow graphs, we need to do flow analysis.
Oops.**

この章

最終パラグラフがメインアイディア。
With regard to flow analysis in Lisp. we are faced with the
following unfortunate situation:
In order to do flow analysis, we need a control flow graph.
In order to determine control flow graphs, we need to do flow analysis.

3 CPS: The Hedgehog’s Representation

Develop a more suitable representation for Lisp

**==The first step== towards finding a solution to this conundrum
is to develop a representation for our Lisp programs suitably
adapted to the task at hand.** In this section, we will develop an
intermediate representation language, CPS Lisp, which is well
suited for doing flow analyis and representing Lisp programs.
We will handle the full syntax of Lisp, but at one remove:
“standard” Lisp is mapped into a much simpler, restricted subset
of Lisp, which has the effect of greatly simplifying the analysis.

問題に対してrepresentation を開発することがメインアイディア。 representation をの特徴をサポート。

CPS

In Lisp, we must represent and deal with transfers of control
caused by function calls. This is most important in the Scheme
dialects [R3-Report], where lambda expressions occur with extreme
frequency. **In the interests of simplicity, ==then==, we adopt
a representation where all transfers of control - [列挙](1)sequencing,
(2)looping, (3)function call/return, (4)conditional branching - are represented
with the same mechanism: the tail recursive function
call.*: This representation is called CPS. or Continuation Passing
Style, and is treated at length in [Declarative].

The advantage of CPS

CPS stands in ==contrast to==[対比] (A)the intermediate representation
languages commonly chosen for traditional optimising compilers.
These languages are conventionally some form of slightly
cleaned-up assembly language: (1)quads, (2)three-address code, ==or==
(3)triples. The ==disadvantage of== such representations are their
(1)adhoc, (2)machine-specific. and (3)low-level semantics. The alternative
of CPS was first proposed by Steele in [Rabbit], and further explored
by Kranz, et al. in [ORBIT]. **==The advantages== of (a)CPS lie
in its appeal to the formal semantics of the lambda-calculus, and its
representational simplicity.**

The advantage of CPS

[例示:1つのものを知ればよいという意味で]CPS conversion can be referred to as the “hedgehog” approach,
after a quotation by Archilocus. All control and environment
structures are represented in CPS by lambda expressions
and their application. **After CPS conversion, the compiler
need only know “one great thing” - how to compile lambdas
very well**. This approach has an interesting effect on the pragmatics
of Scheme compilers. Basing the compiler on lambda
expressions makes lambda expressions very cheap, and encourages
the programmer to use them explicitly in his code. Since
lambda is a very powerful construct, this is a considerable boon
for the programmer.

The continuation in CPS

In CPS, function calls are tail recursive. ==That is==, (1)they do
not return; (2)they are like GOTOs. ==If== we are interested in the
value computed by a function f of two values, => we must pass
f a third argument, the continuation. The continuation is a
function; after f computes its value v. instead of “returning”
the value v, it calls the continuation on v. **Thus the continuation
represents the control point which will be transferred to after
the execution off-**

Example of CPS

**==For example==, if we wish to print the value computed by
(x+y)* (z+w). we do not write:

(print (* (+ x y) (t z w)))

instead, we write:

(+ x y (lambda (xy)
         (+ z w (lambda (zw)
           (* xy zw print)))))

**
Here, the primitive operations - +, *, and print -
are all redefined to take a continuation as in extra argument
The first + function calls its third argumen
(lambda (xy) . . . ) on the sum of its first two arguments,
x and y. Likewise, the second + function calls its third argument,
(lambda (zw) . . . ) on the sum of its first two arguments,
z and w. And the * function calls its third argument,
the print function, on the product of its first two arguments,
xty, andz+w.

The invariant of CPS

**Continuation passing style has the folIowing invariant**
The only expressions that can appear as arguments to a
function call are constants, variables, and lambda expressions.