今日の英語 - Control flow analysis in scheme その3
速読の練習。速読はしない。文の構造を意識しつつ読み進める習慣をつける。方法論はTOEFLテスト速読・速聴大特訓 基礎編で。
ルールは以下の通り。少し内容が難しくなり定型をつかむのも同様に難しくなってきた。何か良い題材ないですかね？＞M氏
* トピックセンテンスは ** ** で囲む
* シグナルワードは == ==
* パラグラフのトピックは必ず書く。
* サポート情報のスタイルを書く
* 列挙には(1)(2)(3)と振る
* 対比には (A)(a) のように目印
* 例示は何に対するサポートかを一言書き添える
* 原因・結果には => を
Lisp can be easily transformed into an equivalent CPS program
**Standard non-CPS Lisp can be easily transformed into an
equivalent CPS program, so this representation carries no loss
of generality**. Once committed to CPS, we make further simplifications:
(1)No special syntactic forms for conditional branch.
The semantics of Primitive conditional branch is captured
by the primitive function %if which takes one boolean argument,
and two continuation arguments. If the boolean is
true, the first continuation is called; otherwise, the second
is called.
(2)No special labels or letrec syntax for mutual recursion.
Mutual recursion is captured by the primitive function Y,
which is the “paradoxical combinator” of the X-caIculus.
(3)Side effects to variables are not allowed.
We allow side effects to data structures only. Hence side
effects are handled by primitive functions, and special syntax
is not required.
Lisp code violating any of these restrictions is easily mapped
into equivalent Lisp code preserving them, so they carry no
loss of generality. ==In point of fact==（例示：簡単に変換できる）, the front end of the ORBIT
compiler [ORBIT] performs the transformation of standard
Scheme code into the above representation as the first phase of
compilation.
syntactic entities
These restrictions leave us with a fairly simple language to
deal with: **There are only five syntactic entities: 列挙(1)lambdas, (2)variables,
(3)primops. (4)constants and (5)calls (fig. 2). and two basic semantic
operations: abstraction and application.**
Lambda expressions: (lambda var-set call)
Variable references: foo, bar, . . .
Constants: 3. "doghen".' (a 3 elt list),...
Primitive Operations: +. %if, Y. . . .
Function calls: ( fun arg’ )
where fun is a lambda, var. or primop. and the args are
lambdas, vxs, or constants.
Figure 2: CPS language grammar
Lambda Expressions:
A lambda expression has the syntax
(lambda var-set cali) , where var-set is a list of variables,
e.g. (n m a), and call is a function call. A lambda
expression denotes a function.
Function Calls:
A function call has the syntax ( fun arg1, . . . argm) for
n >=0. fun must be a function, and the argi, must be args.
[see below]
- Function:
A function is a lambda expression, a variable reference.
or a primop.
- Args:
An argument is a lambda expression. a variable reference.
or a constant.
Primitive Operations:
A primop denotes some primitive function, and is given
by a predefined identifier, e.g., +. %if.
Variables:
Variables have the standard identifier syntax.
constants:
Constants have no functional interpretation, and so have
syntax and semantics of little relevance to our analysis.
I use integers, represented by base 10 numerals, in my
examples.
primop is second class
** == Note that ==this syntax specification relegates primops to second
class status: they may only be called. not used as data,
or passed around as arguments. This =>（原因・結果） leads to no loss of generality,
since everywhere one would like to use the + primop
as data, for instance. one can instead use an equivalent lambda
expression: (lambda (a b c) (+ a b c)).
Why primop is second class?
== The reason == behind splitting out primops as second class is
fairly operational:=> we view primops as being small, opencodeable
types of objects. Calls to primops are where computation
actually gets done. There are == other== formulations possible
with first-class primops. with corresponding flow analytic solutions.
** Relegating primops to second class status simplifies => the
presentation of the analysis technique presented in this paper.**
Nested call of the form are not allowed
Note ==also== that the definition of CPS Lisp ==implies== that the
only possible body a lambda expression can have is a function
call. This is directly reflected in our syntax specification.
A restatement of the syntactic invariants in our representation:
- A lambda’s body consists of a single function call.
- A function call’s arguments may only be lambdas, variables,
or constants. **That is, nested calls of the form:
(f (g a) (h b)) arenotallowed.**
%if
%if, test: ==As discussed above==, **%if is a primop taking ==three arguments==:**
列挙(1)a boolean, and (2,3)two continuations. If the boolean
is true, => the first continuation is called, ==otherwise== the second
continuation is called.
%if can have specialised test forms that take a nonboolean
first argument, and perform some test on if e.g.
(test-zero? x f g) calls f ifxiszero,otherwise
g.
Y combinator
Y: **Y is the CPS version of the XcalcuIus “paradoxical combinator”
fixpoint function**. The CPS definition is tricky, and
is best arrived at in stages. Consider the following use of
the non-CPS fixpoint operator:
(Y (lambda (f)
(lambda (II)
(if (zero? n) 1
(* n (f (- n 1)))))))
Y returns the fixpoint of its argument, i.e. that function f'
such that (lambda (f) . . .) applied to f' yields f'.
However, if we convert (lambda (f) . ..) to CPS
notation, we get: （コード略）
