A. Schlosser
等人
/
理论计算机科学电子笔记
174
(
2007
)
61
上下文相关过程的语义被简单地定义为其
相对化
版本函数
f
(x
1
:τ
1
,
.
,
xn
:τ
n
):
τ<
=
主体
ctx
,其中
body
ctx
:
= if
c
f
then body
f
else*end
表示
f
的
相对化
body
。以来
所有的选择器都是不完全定义的,选择器也被分配了一个上下文子句:对于一个构
造函数
,
cons
与相应的选择器sel
1
,
.
,
sel
n
,选择器调用sel
i
(
x
)的上下文子句
c sel i
定义为
?
cons(x)声明选择器只能应用于它所属的构造函数。
例如,程序!!可以使用如图
2
所示的上下文子句来重新表述图
1
的结构。这个上
下文子句要求过程调用(k!!n)只出现在保证n是列表k的合法地址的上下文中。
作为
|K|> n
如果
k
=
/
ε
,
则
对
?
ε
(
k
)(
和
i∈
T
∈R
∈
R
∈
S
∈
T
*
i
∈
R∈
N
)被简化
在过程的上下文相关版本的主体中, 因此调用时没有异常!!
now
由
context
子句
静态
保证。因此,执行程序!!更
重要
的是,当(
|K|
,
n
)测试
?
ε(k)保存在上下文相关版本中。
过程find的定义也在图2中得到了细化。上下文子句要求|
一
|
对于
列表a中的搜索
区间的上界
j
和下界
i
, 同样在这里,由于在每次(递归)调用过程find时动态执行
的
测试
被静态测试所取代,因此获得了更有效的过程:
|
一
|>
j
和
j> i
被保存,这两
者都导致成本与[log
2
(j-i + 1)]成比例。|在原始版本的find。
2.2
语境假设
为了保证过程(或选择器)
f
仅在术语t
内
的有效上下文中被调用,为t生成所谓的
上
下文要求,
表示在t中调用任何
f
的
上下文需要
f
的
上下文子句
c
f
(其中
c
f
中的形式参
数被调用的实际参数替换
定义2.1 [上下文要求]对于项t,集合Octx(t)<$Occ(t)是t中所有
上下文敏感事
件的集合
,即事件
π∈
Occ(
t
)使得
t
|
π
= g
(
ti
,
.
,
t
,
n
), 并且
g
是选择器或过程函
数符号。
1
项
t
的
上下文要求
CR
(t)被给出为
AND
(
{
CR
(t
,
π)
|
π
∈
Octx
(t)
}
),其
中
CR
(t
,
π)
= if
{
COND
(t
,
π)
,
θ(c
g
)
,
true
}
if
t
|
π
=
g(ti
,
.
,
tn
),θ用
实际参数
ti
代替
g
的形式参数
xi
。
2
对于(
1
)中的
过程
f
,
f
的
上下文假设
被定义为引理
f$ctx
<
=
π
x
1
:
τ
1
,
. . .
,
xn
:
τ
n
CR
(
bodyctx
),且该系数
x
该
点
是
一
个
线性矩阵
引理
lem
<
=
λ
x
1
:
τ
1
,
. . .
,
xk
:
τ
k
bodydylem
(
2
)
定义
了一个
引理
m
$
ctx
<
=
π
x
1
:
τ
1
,
. .
,
xk
:
τ
kCR
(
bodylem
)
.
1
通常,Occ(t)是所有
出现
的t,t
| π
表示t
在出现
π
时的子项
,
t [π←r]由t替换t
得到
|π
R
2
AN D (
{
b1
,
. . .
,
bn
}
)
-
所 有
的 随 机 数 都
是
AND (
b1
,
. . .
,
BN
)
-
abb_reeviate_
sabo
_l
_eant
er
_r_
e
r_e
r
COND
(
t
,
π
)
是子
项
t
的所有第二个条件的共轭
|π
。