4.6. Loops
The rule While-T recurs on its own conclusion. A return in the body interrupts the loop. The divergence of while (true) {} has no derivation, a limitation of inductive big step semantics (Kahn, RR-0601, §4.4, p. 11).
\dfrac{\Gamma \vdash e : \mathsf{bool} \qquad \Gamma \vdash \{c\} \dashv \Gamma}{\Gamma \vdash \mathtt{while}\ (e)\ \{c\} \dashv \Gamma}\;\textsf{(T-While)}
\dfrac{\rho, \sigma \vdash e \Rightarrow \mathsf{bool}\,\mathtt{false}, \sigma_1}{\rho, \sigma \vdash \mathtt{while}\ (e)\ \{c\} \Rightarrow \mathsf{normal}, \rho, \sigma_1}\;\textsf{(While-F)}
\dfrac{\begin{array}{c} \rho, \sigma \vdash e \Rightarrow \mathsf{bool}\,\mathtt{true}, \sigma_1 \qquad \rho, \sigma_1 \vdash \{c\} \Rightarrow \mathsf{normal}, \rho, \sigma_2 \\ \rho, \sigma_2 \vdash \mathtt{while}\ (e)\ \{c\} \Rightarrow r, \rho, \sigma_3 \end{array}}{\rho, \sigma \vdash \mathtt{while}\ (e)\ \{c\} \Rightarrow r, \rho, \sigma_3}\;\textsf{(While-T)}
\dfrac{\rho, \sigma \vdash e \Rightarrow \mathsf{bool}\,\mathtt{true}, \sigma_1 \qquad \rho, \sigma_1 \vdash \{c\} \Rightarrow \mathsf{ret}\,v, \rho, \sigma_2}{\rho, \sigma \vdash \mathtt{while}\ (e)\ \{c\} \Rightarrow \mathsf{ret}\,v, \rho, \sigma_2}\;\textsf{(While-Ret)}
The implementations are partial, so Lean records opaque constants that carry the type and not the body, and no property of them is proved here.
Lean code for Definition4.6.1●2 definitions
Associated Lean declarations
-
CoreCpp.Typing.cmd[complete]
-
CoreCpp.Eval.cmd[complete]
-
CoreCpp.Typing.cmd[complete] -
CoreCpp.Eval.cmd[complete]
-
opaquedefined in CoreCpp/Typing.leancomplete
opaque CoreCpp.Typing.cmd (p : CoreCpp.Program) (τᵣ : CoreCpp.Ty) (Γ : CoreCpp.TEnv) : CoreCpp.Cmd → CoreCpp.T CoreCpp.TEnv
opaque CoreCpp.Typing.cmd (p : CoreCpp.Program) (τᵣ : CoreCpp.Ty) (Γ : CoreCpp.TEnv) : CoreCpp.Cmd → CoreCpp.T CoreCpp.TEnv
Γ ⊢ c ⊣ Γ', under the return type τᵣ of the enclosing function.
-
opaquedefined in CoreCpp/Eval.leancomplete
opaque CoreCpp.Eval.cmd (fs : CoreCpp.FunEnv) (ρ : CoreCpp.Env) (σ : CoreCpp.Store) (c : CoreCpp.Cmd) : CoreCpp.M (CoreCpp.Ctrl × CoreCpp.Env × CoreCpp.Store)
opaque CoreCpp.Eval.cmd (fs : CoreCpp.FunEnv) (ρ : CoreCpp.Env) (σ : CoreCpp.Store) (c : CoreCpp.Cmd) : CoreCpp.M (CoreCpp.Ctrl × CoreCpp.Env × CoreCpp.Store)
ρ, σ ⊢ c ⇒ r, ρ', σ'
The for is defined through while. The variable of the initialiser has the loop as its scope, the body is a block of its own, and the step runs after the body, outside the body's scope.
\dfrac{\begin{array}{c} \Gamma \vdash c_0 \dashv \Gamma_0 \qquad \Gamma_0 \vdash e : \mathsf{bool} \\ \Gamma_0 \vdash c_s \dashv \Gamma_0 \qquad \Gamma_0 \vdash \{c\} \dashv \Gamma_0 \end{array}}{\Gamma \vdash \mathtt{for}\ (c_0;\, e;\, c_s)\ \{c\} \dashv \Gamma}\;\textsf{(T-For)}
\dfrac{\begin{array}{c} \rho, \sigma \vdash c_0 \Rightarrow \mathsf{normal}, \rho_0, \sigma_0 \\ \rho_0, \sigma_0 \vdash \mathtt{while}\ (e)\ \{\, \{c\}\ c_s \,\} \Rightarrow r, \rho_0, \sigma_1 \end{array}}{\rho, \sigma \vdash \mathtt{for}\ (c_0;\, e;\, c_s)\ \{c\} \Rightarrow r, \rho, \sigma_1 \setminus (\rho_0 \setminus \rho)}\;\textsf{(For)}
The implementations are partial, so Lean records opaque constants that carry the type and not the body, and no property of them is proved here.
Lean code for Definition4.6.2●2 definitions
Associated Lean declarations
-
CoreCpp.Typing.cmd[complete]
-
CoreCpp.Eval.cmd[complete]
-
CoreCpp.Typing.cmd[complete] -
CoreCpp.Eval.cmd[complete]
-
opaquedefined in CoreCpp/Typing.leancomplete
opaque CoreCpp.Typing.cmd (p : CoreCpp.Program) (τᵣ : CoreCpp.Ty) (Γ : CoreCpp.TEnv) : CoreCpp.Cmd → CoreCpp.T CoreCpp.TEnv
opaque CoreCpp.Typing.cmd (p : CoreCpp.Program) (τᵣ : CoreCpp.Ty) (Γ : CoreCpp.TEnv) : CoreCpp.Cmd → CoreCpp.T CoreCpp.TEnv
Γ ⊢ c ⊣ Γ', under the return type τᵣ of the enclosing function.
-
opaquedefined in CoreCpp/Eval.leancomplete
opaque CoreCpp.Eval.cmd (fs : CoreCpp.FunEnv) (ρ : CoreCpp.Env) (σ : CoreCpp.Store) (c : CoreCpp.Cmd) : CoreCpp.M (CoreCpp.Ctrl × CoreCpp.Env × CoreCpp.Store)
opaque CoreCpp.Eval.cmd (fs : CoreCpp.FunEnv) (ρ : CoreCpp.Env) (σ : CoreCpp.Store) (c : CoreCpp.Cmd) : CoreCpp.M (CoreCpp.Ctrl × CoreCpp.Env × CoreCpp.Store)
ρ, σ ⊢ c ⇒ r, ρ', σ'