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

english

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

ルールは以下の通り。少し内容が難しくなり定型をつかむのも同様に難しくなってきた。何か良い題材ないですかね？＞M氏

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

At first use sideeffectless control flow

**==As== an initial approximation, let’s discuss control flow analysis
for a Scheme that does not allow side effects, ==even== side
effects to data structures.** This =>allows=> us to avoid worrying
about functions that "escape" into data structures, to emerge
who-knows-where. ==Later== in the paper, we will patch our sideeffectless
solution up to include side-effects.

By using CPS Lisp transfers of control are represented by function call

**The ==point== of using CPS Lisp for an intermediate representation
is that all transfers of control are represented by function
call.** ==Thus==（いいかえ） the controlflow problem is defined by the following
question:
For each call site c in program P, what is the set L(c)
of lambda expressions that c could be a call to? I.e.,
if there is a possible execution of P such that lambda
l is called from call site c. then l must be an element
of L(c).

すぐには意味が取れなかった。
「プログラム P を実行することで call site c においてある lambda 式 l が call されるならば、l は L(c)に含まれる」
Control flow イコール 全ての call site c において L(c) を考えること。L(c)とは call site c で call される可能性のある lambda 式の集合。

We can define L(c), but must be content with an approximation to the optimal solution

The definition of the problem does not define a unique function
L. The ==trivial==（例示） solution is the function L(c) = AllLambdas,
==i.e==. the ==conclusion == that all lambdas can be reached from any
call site. What we want is the tightest possible L. It is possible,
in fact, to construct algorithms that compute the smallest
L function for a given program. ** The catch lies in determining
when to halt the algorithm. In ==general==, then, we must be
content with an approximation to the optimal solution.**

define Defs function

Let ARGS be the set of arguments to calls in program P,
and LAMBDAS be the set of lambda expressions in P. That
is, ARGS is the set of variables and lambda expressions in P
(we assume variables names are unique here, i.e. that variables
have been a-converted to unique names.) **We define a function
Defs : ARGS -+ P(LAMBDAS). Defs(a) gives all the lambda
expressions that a could possibly evaluate to. That is,
Defs[ (lambda . . . )] = {(lambda . ..)}
Defs[primop] = iprimvl
Defs[v] = {I 1 v bound to lambda I}
L is trivially determined from Defs. In a call c : vu1 . . . a.) ,
L(c) is just Defs(n.**

またも文章につまる。あ。分かった。
(f a1. .. an) とあった場合に Defs(f) は L(c) ってことね。

Defs can be given with a recursive definition

**Defs can be given with a recursive definition**: In
...
==I.e.== if lambda 1 can be called from call site c, then l's ith variable
can evaluate to any of the lambdas that c's ith argument can
evaluate to.


内容が難しくなってきたのであまり進まなかった。