ISWIM

ISWIM（「If you See What I Mean」的首字母縮寫），是一種抽象的電腦程式語言或程式語言家族，它由彼得·蘭丁設計，並描述在他1966年於ACM通訊發表的文章《接下來的700種程式語言》之中。

儘管沒有實現，它被證明為在程式語言開發中非常有影響力的語言，特別是對於函數式程式語言，比如SASL、ML、NPL、Haskell和它們的後繼者，還有數據流程程式語言如Lucid。

## 概述

ISWIM是具有函數式核心的指令式程式語言，它構成自加了語法糖的叫做「應用式程式語言表達式 (電腦科學)」（AE）的擴展λ演算，並增加了強力控制機制即對應J算子的程序點算子`pp`。ISWIM的操作語義，可以使用Landin的SECD機來定義，並且使用了傳值調用，從而具有及早求值的求值策略。

ISWIM基於了λ演算，從而具有高階函數和詞法作用域變量。ISWIM的目標之一，就是要看起來更像數學表示，所以在定義結構之時，放棄了ALGOL的語句括號`begin……end`，轉而採用了越位規則和基於縮進的作用域。

沒有進行過直接實現ISWIM的嘗試，但是Arthur Evans的PAL，和John C. Reynolds的Gedanken，獲取了Landin的多數概念，包括強力的控制轉移運算，這兩者都是動態類型語言。Robin Milner的ML，可以被認為等價於沒有J算子，而有類型推論的ISWIM。

從ISWIM衍生出的另一條路線，是去掉指令式特徵如J算子並加以單賦值限制，從而成為純函數式語言並進一步切換為惰性求值。這條路線導致了SASL、Hope、KRC、Miranda、Haskell、Clean。

## 語法

ISWIM程序基於了一個單一表達式，它由`where`或`let`子句、條件表達式和函數定義所限定。ISWIM在表示法上的特色，是與CPL一起，最早使用了局部定義子句

```sml
L where x = M
```

$$\ \equiv\ $$

```sml
let x = M; L
```

尤其是`let`子句適合表達ALGOL 60的嵌套函數的塊結構而為後繼者語言所承襲：

AE｜邏輯ISWIM

```bash
{λf.f(b+2c)+f(2b-c)}
[λx.x(x+a)]

{λ(f,b,c).f(b+2c)+f(2b-c)}
[λx.x(x+a),
  u/(u+1),
  v/(v+1)]

{λf.f(6)}
[Yλf.λn.if(n=0)(1,nf(n-1))]

{λ(f,g).f(g(a))+g(f(b))}
[Yλ(f,g).
  (λx.F(f,g,x),λx.G(f,g,x))]

{λg.g({λf.f}[λx.ax²+bx+c],
  u/(u+1),
  v/(v+1))}
[λ(f,p,q).f(p+2q,2p-q)]

{λx.xy(x+y)}
[{λy.a²+a√y}
  [a²+b²]]

{λ(a,b,f).
  {λ(g,h).
    {λk.X}
    [λ(u,v).λx.K]}
  [Yλ(g,h).
    (λx.G,λ(y,z).H)]}
[A,B,λ(x,y).F]
```

```sml
f(b+2c)+f(2b-c)
where f(x) = x(x+a)

f(b+2c)+f(2b-c)
where f(x) = x(x+a)
  and b = u/(u+1)
  and c = v/(v+1)

f(6)
where rec f(n) = (n=0)→1; nf(n-1)

f(g(a))+g(f(b))
where rec f(x) = F(f,g,x)
      and g(x) = G(f,g,x)

g(f where f(x) = ax²+bx+c,
  u/(u+1),
  v/(v+1))
where g(f,p,q) = f(p+2q,2p-q)

xy(x+y)
where x = a²+a√y
      where y = a²+b²

X
where k(u,v)(x) = K
where rec g(x) = G
      and h(y,z) = H
where a = A
  and b = B
  and f(x,y) = F
```

```sml
let f(x) = x(x+a)
f(b+2c)+f(2b-c)

let f(x) = x(x+a)
and b = u/(u+1)
and c = v/(v+1)
f(b+2c)+f(2b-c)

let rec f(n) = (n=0)→1; nf(n-1)
f(6)

let rec f(x) = F(f,g,x)
    and g(x) = G(f,g,x)
f(g(a))+g(f(b))

let g(f,p,q) = f(p+2q,2p-q)
g((let f(x) = ax²+bx+c; f),
  u/(u+1),
  v/(v+1))

let x =
    let y = a²+b²; a²+a√y
xy(x+y)

let a = A
and b = B
and f(x,y) = F
let rec g(x) = G
    and h(y,z) = H
let k(u,v)(x) = K
X
```

λ演算中的函數應用項`(M N)`及其關聯的抽象項`M := λx.L`，在應用表達式中要一起表示為：

```bash
{λM.(M N)}[λx.L]
```

它對應的ISWIM表示為：

```sml
M(N) where M(x) = L
```

或

```sml
let M(x) = L; M(N)
```

ISWIM所基於的應用表達式，採用花括號包圍算子，採用方括號包圍運算元或運算元列表，它為了「同時」或「平行」定義而在`λ`和`.`之間擴展了標識符列表，列表用圓括號包圍並在其中用逗號分隔元素。應用表達式為遞歸定義而採用了Y不動點組合子，採用`λ().L`表示無參數函數thunk。示例中處置函數參數問題的`{λf.f}`對應於I恆等組合子，此外還可能用到K常量組合子，和B複合組合子。

在ISWIM論文中首次出現了用來定義結構的代數數據類型定義，這是通過自然語言的`either……or……`和`……and……`描述完成的，但明確的表示出了當代函數式程式語言比如Standard ML中的「積類型之和」：

抽象ISWIM｜Standard ML

an $\mathrm{aexpression}$ ($\mathrm{aexp}$) is either $simple$, and has a $body$, which is an $\mathrm{identifier}$ or a $combination$, in which case it has a $rator$, which is an $\mathrm{aexp}$, and a $rand$, which is an $\mathrm{aexp}$, or a $conditional$, …… , or $one\text{-}armed$, …… , or a $listing$, …… , or $beet$, …… .

```SML
datatype aexp
  = SIMPLE of body 
  | COMBINATION of rator * rand
  | CONDITIONAL ……
  | ONE_ARMED ……
  | LISTING ……
  | BEET ……
and body = BODY of identifier
and rator = RATOR of aexp
and rand = RAND of aexp    
```

這裡的特有術語`beet`是對beta可歸約式（beta redex）的簡稱，它代表了

```sml
L where x = M
```

或

```sml
let x = M; L
```

這裡的`L`稱為主要子句，`x = M`稱為支持（support）即輔助定義。

在ISWIM論文中，Landin將頂層的ISWIM構造稱為`amessage`即消息，並示例了兩個命令，特定的需求例如`<span style="color:green;">'''Print'''</span> a+2b`，和定義例如`<span style="color:green;">'''Def'''</span> x = a+2b`。

## 規則

ISWIM基本的等價規則包括：

```sml
x = L and y = M and …… and z = N
```

$$\ \equiv\ $$

```sml
(x, y, ……, z) = (L, M, ……, N)
```

此規則對應於Standard ML中的模式匹配。

```sml
f(x) = L
```

$$\ \equiv\ $$

```sml
f = (g where g(x) = L)
```

這裡的

```sml
(g where g(x) = L)
```

是閉包，此規則對應於Standard ML中的

```sml
fun f x = L
```

$$\ \Leftrightarrow\ $$

```sml
val f = fn x => L
```

- (I')規則還有更一般性的柯里化形式，形如

```sml
f(a, b, c)(x, y) = L
```

$$\ \equiv\ $$

```sml
f(a, b, c) = (g where g(x, y) = L)
```

```sml
(f where f(x) = L) M
```

$$\ \equiv\ $$

```sml
L where x = M
```

這裡的

```sml
(f where f(x) = L)
```

是閉包。

```sml
(x = L) where y = M
```

$$\ \equiv\ $$

```sml
x = (L where y = M)
```

```sml
L where x = M
```

$\ \equiv\ $`Subst<big><math>\,\begin{smallmatrix} \mathsf{M} \\ \mathsf{x} \end{smallmatrix}\,</math></big>L`，此規則對應於λ演算中的β-歸約，即用`M`代換 (邏輯)`L`中出現的所有適合的`x`。

```sml
rec x = L
```

$$\ \equiv\ $$

```sml
x = (L where rec x = L)
```

這裡的

```sml
rec
```

對應於λ演算中的Y不動點算子。

通過運用(I')、(β')、(D')和(Y)等價規則，ISWIM確使任何定義都能被標準化，即表達為`lhs = rhs`的綁定形式，等式的等式的兩側分別為：左手側（lhs）的確切的一個約束變量，右手側（rhs）的它所對應的主體（body）。下面以階乘函數的函數應用為例，這裡採用了ISWIM派生語言比如PAL和可計算函數邏輯 ML之中的let表達式：

```sml
let x = M in L
```

$$\ \equiv\ $$

```sml
let x = M; L
```

設 `C = (n=0)→1; nf(n-1)`、 `G = (g where g(n) = C)` 並且 `F = (G where rec f = G)`

`f(6) where rec f(n) = (n=0)→1; nf(n-1)`｜ ｜`let rec f(n) = (n=0)→1; nf(n-1) in f(6)`

$\,\equiv\,$｜`f(6) where rec f(n) = C`｜(I')｜$\,\equiv\,$｜` let rec f(n) = C in f(6)`

$\,\equiv\,$｜`f(6) where rec f = (g where g(n) = C)`｜ ｜$\,\equiv\,$｜`let rec f = (let g(n) = C in g) in f(6)`

$\,\equiv\,$｜`f(6) where rec f = G`｜(Y)｜$\,\equiv\,$｜`let rec f = G in f(6)`

$\,\equiv\,$｜`f(6) where f = (G where rec f = G)`｜ ｜$\,\equiv\,$｜`let f = (let rec f = G in G) in f(6)`

$\,\equiv\,$｜`f(6) where f = F`｜(β)｜$\,\equiv\,$｜`let f = F in f(6)`

$\,\equiv\,$｜`F(6)`｜ ｜$\,\equiv\,$｜`F(6)`

$\,\equiv\,$｜`(G where rec f = G)(6)`｜(Y)｜$\,\equiv\,$｜`(let rec f = G in G)(6)`

$\,\equiv\,$｜`(G where f = (G where rec f = G))(6)`｜ ｜$\,\equiv\,$｜`(let f = (let rec f = G in G) in G)(6)`

$\,\equiv\,$｜`(G where f = F)(6)`｜ ｜$\,\equiv\,$｜`(let f = F in G)(6)`

$\,\equiv\,$｜`((g where g(n) = C) where f = F)(6)`｜ ｜$\,\equiv\,$｜`(let f = F in (let g(n) = C in g))(6)`

$\,\equiv\,$｜`((g where g(n) = (n=0)→1; nf(n-1)) where f = F)(6)`｜(β)｜$\,\equiv\,$｜`(let f = F in (let g(n) = (n=0)→1; nf(n-1) in g))(6)`

$\,\equiv\,$｜`(g where g(n) = (n=0)→1; nF(n-1))(6)`｜(I)｜$\,\equiv\,$｜`(let g(n) = (n=0)→1; nF(n-1) in g)(6)`

$\,\equiv\,$｜`((n=0)→1; nF(n-1)) where n = 6 `｜(β)｜$\,\equiv\,$｜`let n = 6 in ((n=0)→1; nF(n-1))`

$\,\equiv\,$｜`(6=0)→1; 6(F(5))`｜ ｜$\,\equiv\,$｜`(6=0)→1; 6(F(5))`

$\,=\,$｜`6(F(5))`｜ ｜$\,=\,$｜`6(F(5))`

⋮｜ ｜⋮

$\,=\,$｜`6(5(4(3(2(1(F(0)))))))`｜ ｜$\,=\,$｜`6(5(4(3(2(1(F(0)))))))`

通過反向運用等價規則，ISWIM可在這個例子中恢復出等式的左手側為形式的表達式：

`6(F(5))`｜ ｜`6(F(5))`

$\,\equiv\,$｜`6(f(5) where f = F)`｜(β)↑｜$\,\equiv\,$｜`6(let f = F in f(5))`

$\,\equiv\,$｜`6(f(5) where f = (G where rec f = G))`｜ ｜$\,\equiv\,$｜`6(let f = (let rec f = G in G) in f(5))`

$\,\equiv\,$｜`6(f(5) where rec f = G)`｜(Y)↑｜$\,\equiv\,$｜`6(let rec f = G in f(5))`

$\,\equiv\,$｜`6(f(5) where rec f = (g where g(n) = C))`｜ ｜$\,\equiv\,$｜`6(let rec f = (let g(n) = C in g) in f(5))`

$\,\equiv\,$｜`6(f(5) where rec f(n) = C)`｜(I')↑｜$\,\equiv\,$｜`6(let rec f(n) = C in f(5))`

$\,\equiv\,$｜`6(f(5) where rec f(n) = (n=0)→1; nf(n-1))`｜ ｜$\,\equiv\,$｜`6(let rec f(n) = (n=0)→1; nf(n-1) in f(5))`

## 語義

R. D. Tennent在1976年論文《程式語言的指稱語義》中將應用表達式（AE）用於示範。

基於應用表達式的如下形式語法：

```bash
B ∈ Bas     #基础值 
I ∈ Ide     #标识符
E ∈ Exp     #表达式

E ⩴ B
  | I
  | λI.E    #抽象
  | E₁E₂    #组合
  | (E)     #加圆括号 
```

定義如下指稱語義：

```sml
δ ∈ D           (*可指称值*)
ρ ∈ U = Ide → D (*环境*)
ϕ ∈ F = D → E   (*函数*)

ℬ : B → E
ℰ : Exp → U → E
ℰ⟦(E)⟧ρ = ℰ⟦E⟧ρ
ℰ⟦B⟧ρ = ℬ⟦B⟧
ℰ⟦I⟧ρ = ρ⟦I⟧ in E
ℰ⟦λI.E⟧ρ = ϕ in E
    where ϕ(δ) = ℰ⟦E⟧(ρ[δ/I]) (*闭包*)
ℰ⟦E₁E₂⟧ρ = ϕ(δ)
    where ϕ = ℰ⟦E₁⟧ρ | F
    and   δ = ℰ⟦E₂⟧ρ | D
```

在BNF範式中，`⩴`（U+2A74常寫為`::=`）表示產生式，`|`表示交替 (形式語言)。在指稱語義中，`in`表示內射而入，而`|`表示投射而出，二者由Dana Scott和Christopher Strachey在1971年介入。

具有let表達式的應用式程式語言很適合用於形式語義示範。R. D. Tennent在1991年著作《程式語言的語義》中採用了新的指稱語義表示法並將編程可計算函數用於示範。Matthew Hennessy在1990年著作《程式語言的語義：使用結構性操作語義的初步介紹》中將簡單的函數式語言用於小步操作語義示範。Gilles Kahn在1987年論文《自然語義》中將Mini-ML用於大步操作語義示範。

## 執行

SECD機是第一個專門設計用來求值應用表達式（AE）的抽象機，SECD四者分別指示堆棧、環境、控制和轉儲。它最初描述於Peter Landin的1964年論文《表達式的機器求值》中。常見的處理指令序列的SECD虛擬機，是Peter Henderson於1980年在LispKit Lisp編譯器中定義並實現的。

應用表達式擴展了的賦值器（assigner）$\,\Leftarrow\,$，其應用形式為`lhs<math>\,\Leftarrow\,</math>rhs`，則稱為指令式應用表達式（IAE）。為了執行擴展了J算子的具有賦值器的指令式應用表達式，所細化的SECD機叫做共享機。

Matthias Felleisen和Daniel P. Friedman在1986年借鑑John C. Reynolds於1972年提出的擴展了續體的元循環解釋器，修訂Peter Landin的SECD機，從而規定了CEK機

$\mathcal{C}$

$\mathcal{A}$

$\mathcal{A}$

$\mathcal{C}$

$\mathcal{C}$

$\mathcal{C}$

$\mathcal{C}$

$\mathcal{A}$

$\mathcal{A}$

CEK三者分別指示控制、環境和續體。

### SECD機

對應用表達式進行機器求值的SECD機，將狀態 (電腦科學)變遷規則定義為狀態變換 (函數)函數`Transform(S,E,C,D)`：

S｜E｜C｜D｜ $\rightarrow$ ｜S｜E｜C｜D

s｜e｜combination(rator,rand)::c｜d｜ $\rightarrow$ ｜s｜e｜rand::rator::ap::c｜d

S｜E｜C｜D｜ $\rightarrow$ ｜S｜E｜C｜D

s｜e｜identifier(x)::c｜d｜ $\rightarrow$ ｜locate(position(e,x),e)::s｜e｜c｜d

s｜e｜λexp(v,L)::c｜d｜ $\rightarrow$ ｜closure((e,v),L)::s｜e｜c｜d

S｜E｜C｜D｜ $\rightarrow$ ｜S｜E｜C｜D

closure((e',v),L)::x::s｜e｜ap::c｜d｜ $\rightarrow$ ｜(v,x)::e'｜L｜(s,e,c,d)

f::x::s｜e｜ap::c｜d｜ $\rightarrow$ ｜f(x)::s｜e｜c｜d

x::s｜e｜(s',e',c',d')｜ $\rightarrow$ ｜x::s'｜e'｜c'｜d'

這裡的`[]`是空列表，它在ISWIM中表示為`nullist`，在應用表達式中表示為`()`。這裡的`::`是列表構造的中綴構造子，`x::L`$\, \equiv\,$`cons(x,L)`$\, \equiv\,$`prefix(x)(L)`。

在Landin的規定中，取得標識符`X`有關於環境`E`所指稱的值的函數為：`'''val'''(E)(X) = '''location'''(E*)(X)(E*)`，其中的`E*`指示與環境`E`對應的名值對的列表，這裡將這個取值函數表示為`'''locate'''('''position'''(e,x),e)`，即定位在環境`e`中占據位置`position(e,x)`的常量`x`並取得它的原始值。

在Landin的規定中，設`v = bv(X)`且`L = body(X)`，從λ表達式`X`所在的環境`E`派生出在其中求值`L`的新環境的函數為：`'''derive'''('''assoc'''(v,x))(E)`，這裡假定環境`E`已經實現為特定LISP共享結構即元素為有序對的可持久性單向鍊表，從而將這個派生函數直接用代數數據類型的元組和遞歸數據類型的列表的特定算子來表示。

J算子的應用形式`f = '''J'''(λX.L)`稱為「程序點」，它將函數`F = λX.L`變換成程序閉包。J算子對應的狀態變換函數為：

S｜E｜C｜D｜ $\rightarrow$ ｜S｜E｜C｜D

F::s｜e｜J::ap::c｜d｜ $\rightarrow$ ｜program-closure(F,d)::s｜e｜c｜d

S｜E｜C｜D｜ $\rightarrow$ ｜S｜E｜C｜D

program-closure(F,(s',e',c',d'))::x::s｜e｜ap::c｜d｜ $\rightarrow$ ｜F::x::s'｜e'｜ap::c'｜d'

程序點在ISWIM中表示為`<span style="color:green;">'''pp'''</span> f(X) = L`。

### 共享機

共享機建模於指令式程式語言ALGOL 60的過程調用機制，這裡默認傳遞給形式參數的是函數的變元的名字，在這個過程內定義的形式參數的名字，與在這個過程外定義的實際參數的名字，二者之間具有等價關係。歷經可能的多次傳名調用得到這些等價的名字，其狀態內位置屬於同一個等價類故而稱為共享，在直接電腦表示中每個等價類對應一個地址。

這裡採用了Christopher Strachey在1963年提出的左值和右值概念，共享機默認共享一個變量的左值，這裡的左值表示了它所處在的環境和它在這個環境中的位置，傳名調用形式參數的狀態內位置保存傳遞過來的左值。執行指令式應用表達式的抽象機的狀態變換函數為：

C｜E｜共享｜S｜D｜ $\rightarrow$ ｜C｜E｜共享｜S｜D

combination(rator,rand)::c｜e｜s｜d｜ $\rightarrow$ ｜rand::rator::ap::c｜e｜s｜d

::identifier(x)::ap::c｜e｜s｜d｜ $\rightarrow$ ｜parameter(x)::c｜e｜s｜d

assigner(lhs,rhs)::c｜e｜s｜d｜ $\rightarrow$ ｜rhs::lhs::assign::c｜e｜s｜d

C｜E｜共享｜S｜D｜ $\rightarrow$ ｜C｜E｜共享｜S｜D

identifier(x)::c｜e｜s｜d｜ $\rightarrow$ ｜c｜e｜l=(position(e,x),e)｜locate(l)::s｜d

parameter(x)::c｜e｜s｜d｜ $\rightarrow$ ｜c｜e｜l=locate(position(e,x),e)｜locate(l)::s｜d

assign::c｜e｜l｜r::x::s｜d｜ $\rightarrow$ ｜c｜e｜reset(l,x)::s｜d

λexp(v,L)::c｜e｜s｜d｜ $\rightarrow$ ｜c｜e｜closure((e,v),L)::s｜d

C｜E｜共享｜S｜D｜ $\rightarrow$ ｜C｜E｜共享｜S｜D

ap::c｜e｜l｜closure((e',v),L)::r::s｜d｜ $\rightarrow$ ｜L｜(v,l)::e'｜(s,e,c)::d

ap::c｜e｜l｜f::r::s｜d｜ $\rightarrow$ ｜c｜e｜x::s｜d

e｜l｜r::s｜(s',e',c')::d｜ $\rightarrow$ ｜c'｜e'｜l｜r::s'｜d

Landin規定在這個過程內以無參數函數調用的形式，來訪問傳名調用形式參數所引用的系統存儲的那個值本身，即處在賦值器`rhs`的右值，例如通過`x()`訪問形式參數`x`。賦值器重置其`lhs`確定的左值所引用的那個右值，並在堆棧`S`上留下`nullist`作為結果。

`separate(x)`函數共享一個變量所引用的右值，從而避免了後續的賦值變更這個處在外層的非局部變量值。在處置ALGOL 60時它的用途典型為：聲明已經傳遞來的形式參數為傳值調用，例如

```SML
let x = separate(x()); L
```

通過回溯傳名調用形式參數傳遞，最終能確定其對應的實際參數，是在某個外層過程中聲明即採用`separate`函數初始化的局部標識符，比如

```SML
let x = separate(0.0)
```

`separate`函數對應的狀態變換函數可以定義為：

C｜E｜共享｜S｜D｜ $\rightarrow$ ｜C｜E｜共享｜S｜D

separate::ap::c｜e｜r::s｜d｜ $\rightarrow$ ｜c｜e｜r｜r::s｜d

separate::ap::c｜e｜l｜r::s｜d｜ $\rightarrow$ ｜c｜e｜r｜r::s｜d

Landin將在SECD機和共享機上執行的Y不動點算子，實現為指令式應用表達示式：

```bash
Y(F) ≡ {λz.{λz′.2nd(z⇐z′,z)}[F(z)]}[separate(nullist)]
```

它對應的ISWIM表示為：

`<span style="color:green;">'''Y'''</span>(F) <math>\equiv</math> <span style="color:green;">'''let'''</span> z = <span style="color:green;">separate</span>(<span style="color:green;">nullist</span>); <span style="color:green;">'''let'''</span> z' = F(z); 2nd(z<math>\,\Leftarrow\,</math>z',z)`

Landin為處置ALGOL 60而規定了賦值且保全命令`assignandhold`，它採用守衛命令處置原始數據類型：

`assignandhold(x)(y) <math>\equiv</math> <span style="color:green;">'''let'''</span> x = (<span style="color:green;">real</span>(y)→float(x); <span style="color:green;">integer</span>(y)→entier(x+0.5); <span style="color:green;">Boolean</span>(y)→(<span style="color:green;">Boolean</span>(x)→x)); 2nd(y<math>\,\Leftarrow\,</math>x,x)`。

### CEK機

在CEK機中定義了捕獲當前續體算子$\,\mathcal{C}\,$和以當前續體調用算子`call/cc ≡ λf.<math>\mathcal{C}</math>λk.(f k)`。下面是CEK機的狀態 (電腦科學)變遷函數：

C｜E｜K｜ $\mapsto$ ｜C｜E｜K

λx.L｜ρ｜κ｜ $\mapsto$ ｜""｜{}｜(ret (λx.L,ρ))::κ

M N｜ρ｜κ｜ $\mapsto$ ｜M｜ρ｜(arg N ρ)::κ

""｜{}｜(ret V)::(fun (λx.L,ρ))::κ｜ $\mapsto$ ｜L｜ρx:=V｜κ

C｜E｜K｜ $\mapsto$ ｜C｜E｜K

$\mathcal{C}\,$L｜ρ｜κ｜ $\mapsto$ ｜L｜ρ｜cont::κ

""｜{}｜(ret (λk.L,ρ))::cont::κ｜ $\mapsto$ ｜L｜ρk:=(p,κ)｜stop

""｜{}｜(ret (p,κ'))::cont::κ｜ $\mapsto$ ｜""｜{}｜(ret (p,κ))::κ'

""｜{}｜(ret V)::(fun (p,κ'))::κ｜ $\mapsto$ ｜""｜{}｜(ret V)::κ'

$\mathcal{A}\,$L｜ρ｜κ｜ $\mapsto$ ｜L｜ρ｜stop

這裡的`""`表示空字符串，而`{}`表示空集合。這裡的環境`ρ`是從變量到語義值的有限映射。這裡的`(λx.L,ρ)`是閉包，而`('''p''',κ)`是叫做「續延點」的標籤結構，二者都屬於語義值。初始狀態是三元組`⟨L, {}, ['''stop''']⟩`，終止狀態是三元組`⟨"", {}, [('''ret''' V), '''stop''']⟩`。

Matthias Felleisen和Daniel P. Friedman在1986年又將CEK機擴展為CESK機，CESK四者分別指示控制、環境、存儲和續體，在其中增加了賦值抽象`σx.L`。下面是CESK機的狀態變遷函數：

C｜E｜S｜K｜ $\mapsto$ ｜C｜E｜S｜K

λx.L｜ρ｜θ｜κ｜ $\mapsto$ ｜""｜{}｜θ｜(ret (λx.L,ρ))::κ

M N｜ρ｜θ｜κ｜ $\mapsto$ ｜M｜ρ｜θ｜(arg N ρ)::κ

""｜{}｜θ｜(ret V)::(fun (λx.L,ρ))::κ｜ $\mapsto$ ｜L｜ρx:=n｜θn:=V｜κ

這裡的環境`ρ`是從變量到表示位置的自然數的有限映射，而存儲`θ`是從自然數到語義值即λ-閉包或σ-閉包的有限映射。這裡的`θ[n:=V]`有著`n ∉ Dom(θ)`。

C｜E｜S｜K｜ $\mapsto$ ｜C｜E｜S｜K

σx.L｜ρ｜θ｜κ｜ $\mapsto$ ｜""｜{}｜θ｜(ret (σx.L,ρ))::κ

""｜{}｜θ｜(ret V)::(fun (σx.L,ρ))::κ｜ $\mapsto$ ｜L｜ρ｜θρ(x):=V｜κ

## 引用

本條目部分或全部內容出自以GFDL授權發佈的《自由線上電腦詞典》（FOLDOC）

## 基本資料

- 編程范型：函數式, 指令式
- 發行時間：1966年
- 設計者：彼得·蘭丁
- 作用域：詞法
- 受影響於：ALGOL 60、Lisp
- 施影響於：PAL、SASL、ML、NPL、Lucid、Haskell