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

english

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

ルールは以下の通り。思うように進まない。文章構造を意識できていないと思う。

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

XLAMBDA and XCALL

{{==Besides== call sites, lambda expressions and primops, there are
==two other special(列挙)== syntactic values we must represent in our
analysis.}} (1つめ)We need a way to represent unknown functions that
are passed into our program from the outside world at run time.
(2つめ)==In addition==, we need a call site to correspond to calls to functions
that happen external to the program text. ==For example,==(two other specialの例示)
==suppose== we have the following fragment in our program

 (foo (lambda (k) (k 7))

==If ==foo is free over the program, then in general we have no idea
at compile time what functions foo could be bound to at run
time. The call to foo is essentially an escape from the program
to the outside world, and we must record this fact. We do this
by including XLAMBDA, the external lambda, in Defs[foo].
==Further==, since (lambda (k) (k 7) ) is passed out of the
program to external routines, it can be called from outside the
program. This is represented with a special call site, XCALL,
the external call. Werecord that (lambda (k) (k 7)) is
inL(XCALL).

rules for external call and lambda

{{Functions such as (lambda (k) (k 7)) in the above
example that are passed to the external lambda have escaped
to program text unavailable at compile time, and ==so （原因と結果）==can be
called in arbitrary, unobservable ways.}} They have escaped close
scrutiny, and in the face of limited information, we are forced
simply to assume the worst. We maintain a set ESCAPED of
escaped functions, which initially contains XLAMBDA and the
top level lambda of the program. The rules for the external
call, the external lambda and escaped functions are simple:

  1. Any escaped function can be called from the external call:
  2. Any escaped function may be applied to any escaped

This provides very weak information, but for external functions
whose properties are completely unknown at compile time, it
is the best we can do. (On the other hand, many external functions,
e.g. print, or length, have well known properties.
==For instance== ,both print and length only call the their continuations.
==Thus==, their continuations do not properly escape. Nor
are their continuations passed escaped functions as arguments.
It is straightforward to extend the analysis presented here to
utilise this stronger information.)

Example1

Consider the program

(lambda () (if 5 (+ 3 4) (- 1 2)))

which evaluates to 7. In CPS form, this is:

(lambda (kl) (%if 5 (lambda () (+ 3 4 kl))
                    (lambda () (- 1 2 kl))))

Labeling all the lambda expressions and call sites for reference,
we get:

l1:(lambda (kl)
      cl:(%if 5 l2:(lambda () c2:(+ 3 4 kl))
                l3:(lambda () c3:(- 1 2 kl))))

ESCAPED is initially {XLAMBDA, l1}. Our escaped function
rules tell us that It can be. called from XCALL, or that
l1 ∈ L(XCALL), and that {l1,XLAMBDA} C Defs(ki). The
propagation condition for % if gives us that % if's first internal
call site, icfkif, calls 12. i.e. 12 E L(iciif), and %if's
second internal call site, 'CSif, calls 13, i.e. 13 E L(~c&~).
The propagation condition for + gives us that ic+ contains
Defs(ki) = {II, XLAMBDA}, or that +‘s internal continuation
call can transfer control to I1 or the XLAMBDA. Similarly, we
derive for - that L(k) contains {II, XLAMBDA} . This completes
the control flow analysis for the program.

Example2

Consider the inlInite loop:

(labels ((f (lambda (n) (f n))))
  (f 5))

With top-level continuation * k*, this is CPSised into:

(lambda (*k*)
  (Y (lambda (ignore-b f k1)
    (k1 (lambda (k2) (f 5 k2))
    (lambda (n k3) (f n k3)))))
  (lambda (b ignore-f) (b* k*)))

Labelling all the call sites for reference:

(lambda (*k*)
  c1:(Y (lambda (ignore-b f k1)
  c2:(k1 (lambda (k2) c3:(f 5 k2))
     (lambda (n k3) c4:(f n k3)))))
     (lambda (b ignore-f) c5:(b *k*)))

Defs(val) C ESCAPED
etc.
Y’s internal call site is labelled io. After performing the prop
propagations,
we get:
L(XCALL) = {(lambda (*k*) . ..).XLAMBDA}
L(Cl) = {Y}
L(iQ) = {(lambda (ignore-b f kl) . ..)}
L(Q) = {(lambda (b ignore-f) . ..)}
L(c3) = {(lambda (n k3) (f n k3))
L(y) = {(lambda (n k3) (f n k3))
L(cs) = .{(lambda (k2) (f 5 k2)))