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

ルールは以下の通り。まだ読み終わっていないがべつの題材を探そうと思う。後半は式の説明ばかりだ。

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

6. Side Effects

#### Side effects in Lisp is not important

{{For the purposes of doing control flow analysis of Lisp, tracking

side effects is not of primary importance.}} ==Since(原因・理由)== Lisp makes

variable binding convenient and cheap, side effects occur ==relatively（比較：ALGOL系）==

infrequently. (This is especially true of well written

Lisp.) The pieces of Lisp we are most interested in flow

analysing - inner loops - use side effects primarily for updating

iteration variables, which are rarely functional values. The

control flow of inner loops is usually explicitly written out, and

tends not to use functions as first class citizens.

#### Updating of loop variables is a task of loop packages

{{To further editorialise, I believe that the updating of loop

variables is a task best left to loop packages such as Waters’

Lets [Lets] or the Yale Loop [YLoop], where the actual updating

technique can be left to the macro writer to implement

efficiently, and ignored by the application programmer.}} ==Even==

the standard Common Lisp and Scheme looping construct, do,

permits a binding interpretation of its iteration variable update

semantics.

#### side effects on control flow analsys

For these reasons, we can afford to settle for a solution that

is merely correct, without being very informative. {{==Therefore==,

the control flow analysis presented here uses a very weak technique

to deal with side effects.}} The CPS transformation discussed

in section 3 removes all side effects to variables. Only

side effects to data structures are allowed. All side effects and

accesses to data structures are performed by primops. Among

these primopsare cons, rplaca, rplacd.car.cdr,vref,

and vset. We divide these into ==two== sets: data 1(stashers), and

2(datafetchers). Stashers. such as cons, rplaca, rplacd,

and vset, take functions and tuck them away into some data

structure. Fetchers - car, cdr, vref - fetch functions

from some data structure.

#### Stashers and fetchers.

The analysis takes the simple view that once a function is

stashed into a data structure, it has escaped from the analyser’s

ability to track it. It could potentially be the value of

any data structure access, or escape outside the program to the

ESCAPED set. Thus we have ==two rules== for side effects:

1. Any lambda passed to a stasher primop is included in the

ESCAPED set.

(cons a d kont) 3 [S-1]

Defs(a), Defs(d) ⊂ ESCAPED

(vset vec index val kont) [S-2]

Defs(val) C ESCAPED

etc.

2. A fetcher primop can pass any ESCAPED function to its

continuation:

(fetcher . . . cont) (F-1)

V (lambda (xl . . . ) ∈ Defs(cont),

ESCAPED ⊂ Defs(x)

{{In a sense, stashers and fetchers act as black and white holes:

values disappear into stasher primops and pop out at fetcher

primops.}}

7. Induction Variable Elimination: An Application

#### control flow analysis can usefor other data flow analysis

{{Once we’ve performed control flow analysis on a program, we

can use the information gained to do other data flow analyses.}}

Control flow analysis by itself does not provide enough information

to do all the data flow problems we might desire - the

limitations of control flow analysis are discussed in the section

8 -but we can still solve some useful problem

#### Example of induction variables elimination

{{As an ==example==, consider induction variable elimination. Induction

variable elimination is a technique used to transform

array references inside loops into pointer incrementing operations.}}

For example, suppose we have the following C routine:

int a[50] [30]; example() { integer r, c; for(r=O; r<50; r++) for(c=O; c<30; c++) a[r][c] = 4; }

#### We can remove the entire address calculation

The example function assigns 4 to all the elements of array

a. The array reference a [r] [c] on a byte addressed machine

is equivalent to the address computation a+4* (c+30*r).

This calculation requires two multiplications and two additions.

{{By replacing the array indices with a pointer variable, we can

remove the entire address calculation:}}

example () { integer *ptr; for(ptr=a; ptr<a+1500; ptr++) *ptr = 4; }

#### Induction variable elimination is a technique for automatically performing the above transformation.

{{Induction variable elimination is a technique for automatically

performing the above transformation.}} The Lisp variant

uses control flow analysis.