3. Smallstep: Small-step Operational Semantics
The hiding lean (above in the source file) should not be needed any more and should be removed from all files everywhere it exists.
This chapter adapts Smallstep to follow Slang, the initial part of Imp, on just Aexp and Bexp (without variables). This means that parts of this chapter had to adjust: Concurrent Imp is dropped in favor of Nondeterministic Aexp, and the stack machine is simplified to just Aexps without variables.
In this and later chapters, we are not very consistent about presenting computation rules first and congruence rules after...
HIDE: Sometime in the early 2010s, we did some mining past exams for exercises...
-
Loris: No interesting exercise in Finals of 2007-2009-2010-2011. Nothing in second midterms except for 2011.
-
2011 midterm proposes the following exercise: give the small step relation of FLIP X (alternatively HAVOC, ANYTHING). We could then ask to extend the proof of equivalence of big step vs small step (personally don't like it too much).
-
Maybe we can ask how they would adapt the definition of Hoare triple to small step (maybe in the exam).
HIDE: BCP: I also have a bunch of slides from earlier offerings of CIS500 that might be good additions to the TERSE notes.
HIDE: Possible major restructuring: This chapter might better be postponed to later in the course. A big-step presentation of STLC (and maybe even some of the extensions like subtyping?) could come first. However, this would invite a much bigger change, where all the variants of STLC (with refs, with subtyping, ...) are done in big-step style. This requires more thought...
HIDE: Wonder whether it would be interesting to show them how to make a correspondence with a "real abstract machine" at a lower level...? There's a start at an exercise along these lines below.
3.1. Big-step and Small-step Evaluation
Our semantics for expressions is written in the so-called "big-step" style. Evaluation rules take an expression to a final answer "all in one step":
2 + 2 + 3 * 4 ⇓ 16
But big-step semantics makes it hard to talk about what happens along the way.
Small-step style: alternatively, we can show how to "reduce" an expression to a simpler form by performing a single step of computation:
2 + 2 + 3 * 4 ⟶ 2 + 2 + 12 ⟶ 4 + 12 ⟶ 16
Advantages of the small-step style include:
-
Finer-grained "abstract machine", closer to real implementations.
-
Extends smoothly to concurrent languages and languages with other sorts of computational effects.
-
Separates divergence (nontermination) from stuckness (run-time error).
3.2. A Toy Language
inductive Tm where
| c (n : Nat) -- Constant
| p (t₁ t₂ : Tm) -- Plus
A standard big-step evaluator, as a function.
def evalF (t : Tm) : Nat :=
match t with
| .c n => n
| .p t₁ t₂ => evalF t₁ + evalF t₂
Here is the same evaluator, written in exactly the same style, but formulated as an
inductively defined relation. We use the notation t ⇓ n for "t evaluates to n."
The notation command below is how that is declared: it introduces ⇓ as
infix syntax for the Eval relation defined with it, with a precedence saying
how tightly it binds.
This is the lightweight way to name a relation; later chapters, where a whole
object language needs a grammar rather than a single operator, reach for
declare_syntax_cat instead.
------- (const)
c n ⇓ n
t₁ ⇓ n₁
t₂ ⇓ n₂
----------------- (plus)
p t₁ t₂ ⇓ n₁ + n₂
inductive Eval : Tm → Nat → Prop where
| const (n : Nat) : Eval (.c n) n
| plus (t₁ t₂ : Tm) (n₁ n₂ : Nat)
(h₁ : Eval t₁ n₁) (h₂ : Eval t₂ n₂) :
Eval (.p t₁ t₂) (n₁ + n₂)
notation:50 t " ⇓ " n => Eval t n
namespace SimpleArith1
inductive Step : Tm → Tm → Prop where
| plus (n₁ n₂ : Nat) :
Step (.p (.c n₁) (.c n₂)) (.c (n₁ + n₂))
| plusLeft (t₁ t₁' t₂ : Tm)
(h : Step t₁ t₁') :
Step (.p t₁ t₂) (.p t₁' t₂)
| plusRight (n₁ : Nat) (t₂ t₂' : Tm)
(h : Step t₂ t₂') :
Step (.p (.c n₁) t₂) (.p (.c n₁) t₂')
scoped notation:40 t:41 " ⟶ " t':41 => Step t t'
Notice: each step reduces the leftmost p node that is ready to go — the first rule tells how
to rewrite it, the second and third tell where to find it — and constants do not step to anything.
Let's pause and check a couple of examples of reasoning with the step relation.
If t₁ steps to t₁', then p t₁ t₂ steps to p t₁' t₂.
example :
(.p
(.p (.c 1) (.c 3))
(.p (.c 2) (.c 4))) ⟶
(.p
(.c 4)
(.p (.c 2) (.c 4))) := ⊢ ((Tm.c 1).p (Tm.c 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶ (Tm.c 4).p ((Tm.c 2).p (Tm.c 4))
⊢ (Tm.c 1).p (Tm.c 3) ⟶ Tm.c 4; All goals completed! 🐙
To what does the following term step?
.p
(.p
(.c 1)
(.c 2))
(.p
(.c 1)
(.c 2))
(A) .c 6
(B) .p (.c 3) (.p (.c 1) (.c 2))
(C) .p (.p (.c 1) (.c 2)) (.c 3)
(D) .p (.c 3) (.c 3)
(E) None of the above
Show solution
(B) .p (.c 3) (.p (.c 1) (.c 2))
What about this one?
.c 1
(A) .c 1
(B) .p (.c 0) (.c 1)
(C) None of the above
Show solution
(C) None of the above
end SimpleArith1
3.3. Relations
The step relation ⟶ is an example of a relation on Tm.
Should we be getting this (and Deterministic, Multi, etc.
if appropriate) from the Lean standard library? If not, should we match the
concepts in CSLib, if they exists there?
def Relation (X : Type) := X → X → Prop
One simple property a relation may have is being deterministic: like Slang's big-step evaluation, each element is related to at most one other.
Theorem: For each t, there is at most one t' such that t steps to
t'. We prove it by induction on the derivation of the first step.
Proof sketch: We show that if x steps to both y₁ and y₂, then y₁
and y₂ are equal, by induction on a derivation of x ⟶ y₁. There are
several cases, depending on the last rule used in this derivation and the
last rule in the given derivation of x ⟶ y₂.
-
If both are
plus, the result is immediate. -
The cases when both derivations end with
plusLeftorplusRightfollow by the induction hypothesis. -
It cannot happen that one is
plusand the other isplusLeft/plusRight, since this would imply thatxhas the formp t₁ t₂where botht₁andt₂are constants (byplus) and one oft₁ort₂has the formp _. -
Similarly, it cannot happen that one is
plusLeftand the other isplusRight, since this would imply thatxhas the formp t₁ t₂wheret₁has both the formp t₁₁ t₁₂and the formc n.
Formally,
def Deterministic {X : Type} (R : Relation X) : Prop :=
∀ x y₁ y₂ : X, R x y₁ → R x y₂ → y₁ = y₂
namespace SimpleArith2
theorem step_deterministic : Deterministic SimpleArith1.Step := ⊢ Deterministic SimpleArith1.Step
x:Tmy₁:Tmy₂:Tmh₁:SimpleArith1.Step x y₁⊢ SimpleArith1.Step x y₂ → y₁ = y₂
induction h₁ generalizing y₂ with
x:Tmy₁:Tmn₁:Natn₂:Naty₂:Tm⊢ SimpleArith1.Step ((Tm.c n₁).p (Tm.c n₂)) y₂ → Tm.c (n₁ + n₂) = y₂
x:Tmy₁:Tmn₁:Natn₂:Naty₂:Tmh₂:SimpleArith1.Step ((Tm.c n₁).p (Tm.c n₂)) y₂⊢ Tm.c (n₁ + n₂) = y₂
x:Tmy₁:Tmn₁:Natn₂:Nat⊢ Tm.c (n₁ + n₂) = Tm.c (n₁ + n₂)x:Tmy₁:Tmn₁:Natn₂:Natt₁'✝:Tmh✝:SimpleArith1.Step (Tm.c n₁) t₁'✝⊢ Tm.c (n₁ + n₂) = t₁'✝.p (Tm.c n₂)x:Tmy₁:Tmn₁:Natn₂:Natt₂'✝:Tmh✝:SimpleArith1.Step (Tm.c n₂) t₂'✝⊢ Tm.c (n₁ + n₂) = (Tm.c n₁).p t₂'✝ x:Tmy₁:Tmn₁:Natn₂:Nat⊢ Tm.c (n₁ + n₂) = Tm.c (n₁ + n₂)x:Tmy₁:Tmn₁:Natn₂:Natt₁'✝:Tmh✝:SimpleArith1.Step (Tm.c n₁) t₁'✝⊢ Tm.c (n₁ + n₂) = t₁'✝.p (Tm.c n₂)x:Tmy₁:Tmn₁:Natn₂:Natt₂'✝:Tmh✝:SimpleArith1.Step (Tm.c n₂) t₂'✝⊢ Tm.c (n₁ + n₂) = (Tm.c n₁).p t₂'✝ first | x:Tmy₁:Tmn₁:Natn₂:Natt₂'✝:Tmh✝:SimpleArith1.Step (Tm.c n₂) t₂'✝⊢ Tm.c (n₁ + n₂) = (Tm.c n₁).p t₂'✝ | All goals completed! 🐙
x:Tmy₁:Tmt₁:Tmt₁':Tmt₂:Tmhs:SimpleArith1.Step t₁ t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step t₁ y₂ → t₁' = y₂y₂:Tm⊢ SimpleArith1.Step (t₁.p t₂) y₂ → t₁'.p t₂ = y₂
x:Tmy₁:Tmt₁:Tmt₁':Tmt₂:Tmhs:SimpleArith1.Step t₁ t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step t₁ y₂ → t₁' = y₂y₂:Tmh₂:SimpleArith1.Step (t₁.p t₂) y₂⊢ t₁'.p t₂ = y₂
x:Tmy₁:Tmt₁':Tmn₁✝:Natn₂✝:Naths:SimpleArith1.Step (Tm.c n₁✝) t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step (Tm.c n₁✝) y₂ → t₁' = y₂⊢ t₁'.p (Tm.c n₂✝) = Tm.c (n₁✝ + n₂✝)x:Tmy₁:Tmt₁:Tmt₁':Tmt₂:Tmhs:SimpleArith1.Step t₁ t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step t₁ y₂ → t₁' = y₂t₁'✝:Tmh✝:SimpleArith1.Step t₁ t₁'✝⊢ t₁'.p t₂ = t₁'✝.p t₂x:Tmy₁:Tmt₁':Tmt₂:Tmn₁✝:Natt₂'✝:Tmhs:SimpleArith1.Step (Tm.c n₁✝) t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step (Tm.c n₁✝) y₂ → t₁' = y₂h✝:SimpleArith1.Step t₂ t₂'✝⊢ t₁'.p t₂ = (Tm.c n₁✝).p t₂'✝ x:Tmy₁:Tmt₁':Tmn₁✝:Natn₂✝:Naths:SimpleArith1.Step (Tm.c n₁✝) t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step (Tm.c n₁✝) y₂ → t₁' = y₂⊢ t₁'.p (Tm.c n₂✝) = Tm.c (n₁✝ + n₂✝)x:Tmy₁:Tmt₁:Tmt₁':Tmt₂:Tmhs:SimpleArith1.Step t₁ t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step t₁ y₂ → t₁' = y₂t₁'✝:Tmh✝:SimpleArith1.Step t₁ t₁'✝⊢ t₁'.p t₂ = t₁'✝.p t₂x:Tmy₁:Tmt₁':Tmt₂:Tmn₁✝:Natt₂'✝:Tmhs:SimpleArith1.Step (Tm.c n₁✝) t₁'ih:∀ (y₂ : Tm), SimpleArith1.Step (Tm.c n₁✝) y₂ → t₁' = y₂h✝:SimpleArith1.Step t₂ t₂'✝⊢ t₁'.p t₂ = (Tm.c n₁✝).p t₂'✝ first | All goals completed! 🐙 | All goals completed! 🐙
| plusRight n₁ t₂ t₂' hs ih => plusRight x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂y₂:Tm⊢ SimpleArith1.Step ((Tm.c n₁).p t₂) y₂ → (Tm.c n₁).p t₂' = y₂
intro h₂ plusRight x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂y₂:Tmh₂:SimpleArith1.Step ((Tm.c n₁).p t₂) y₂⊢ (Tm.c n₁).p t₂' = y₂
cases h₂ plusRight.plus x:Tmy₁:Tmn₁:Natt₂':Tmn₂✝:Naths:SimpleArith1.Step (Tm.c n₂✝) t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step (Tm.c n₂✝) y₂ → t₂' = y₂⊢ (Tm.c n₁).p t₂' = Tm.c (n₁ + n₂✝)plusRight.plusLeft x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂t₁'✝:Tmh✝:SimpleArith1.Step (Tm.c n₁) t₁'✝⊢ (Tm.c n₁).p t₂' = t₁'✝.p t₂plusRight.plusRight x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂t₂'✝:Tmh✝:SimpleArith1.Step t₂ t₂'✝⊢ (Tm.c n₁).p t₂' = (Tm.c n₁).p t₂'✝ <;> plusRight.plus x:Tmy₁:Tmn₁:Natt₂':Tmn₂✝:Naths:SimpleArith1.Step (Tm.c n₂✝) t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step (Tm.c n₂✝) y₂ → t₂' = y₂⊢ (Tm.c n₁).p t₂' = Tm.c (n₁ + n₂✝)plusRight.plusLeft x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂t₁'✝:Tmh✝:SimpleArith1.Step (Tm.c n₁) t₁'✝⊢ (Tm.c n₁).p t₂' = t₁'✝.p t₂plusRight.plusRight x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂t₂'✝:Tmh✝:SimpleArith1.Step t₂ t₂'✝⊢ (Tm.c n₁).p t₂' = (Tm.c n₁).p t₂'✝ first | cases ‹SimpleArith1.Step (.c _) _› plusRight.plusRight x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂t₂'✝:Tmh✝:SimpleArith1.Step t₂ t₂'✝⊢ (Tm.c n₁).p t₂' = (Tm.c n₁).p t₂'✝ | rw [ih _ ‹SimpleArith1.Step t₂ _› plusRight.plusRight x:Tmy₁:Tmn₁:Natt₂:Tmt₂':Tmhs:SimpleArith1.Step t₂ t₂'ih:∀ (y₂ : Tm), SimpleArith1.Step t₂ y₂ → t₂' = y₂t₂'✝:Tmh✝:SimpleArith1.Step t₂ t₂'✝⊢ (Tm.c n₁).p t₂'✝ = (Tm.c n₁).p t₂'✝] All goals completed! 🐙
end SimpleArith2
In the Rocq there is the development of a special tactic to make this proof simpler. Do we want that here?
3.3.1. Values
Final states of our machine are terms of the form c n. We call such terms values.
inductive IsValue : Tm → Prop where
| const (n : Nat) : IsValue (.c n)
Here are the formal rules.
inductive Step : Tm → Tm → Prop where
| plus (n₁ n₂ : Nat) :
Step (.p (.c n₁) (.c n₂)) (.c (n₁ + n₂))
| plusLeft (t₁ t₁' t₂ : Tm)
(h : Step t₁ t₁') :
Step (.p t₁ t₂) (.p t₁' t₂)
| plusRight (v₁ t₂ t₂' : Tm)
(hv : IsValue v₁)
(h : Step t₂ t₂') :
Step (.p v₁ t₂) (.p v₁ t₂')
notation:40 t:41 " ⟶ " t':41 => Step t t'
3.3.2. Strong Progress and Normal Forms
theorem strong_progress (t : Tm) : IsValue t ∨ ∃ t', t ⟶ t' := by t:Tm⊢ IsValue t ∨ ∃ t', t ⟶ t'
induction t with
| c n => c n:Nat⊢ IsValue (Tm.c n) ∨ ∃ t', Tm.c n ⟶ t' left c n:Nat⊢ IsValue (Tm.c n); exact .const n All goals completed! 🐙
| p t₁ t₂ ih₁ ih₂ => p t₁:Tmt₂:Tmih₁:IsValue t₁ ∨ ∃ t', t₁ ⟶ t'ih₂:IsValue t₂ ∨ ∃ t', t₂ ⟶ t'⊢ IsValue (t₁.p t₂) ∨ ∃ t', t₁.p t₂ ⟶ t'
right p t₁:Tmt₂:Tmih₁:IsValue t₁ ∨ ∃ t', t₁ ⟶ t'ih₂:IsValue t₂ ∨ ∃ t', t₂ ⟶ t'⊢ ∃ t', t₁.p t₂ ⟶ t'
cases ih₁ with
| inl hv₁ => p.inl t₁:Tmt₂:Tmih₂:IsValue t₂ ∨ ∃ t', t₂ ⟶ t'hv₁:IsValue t₁⊢ ∃ t', t₁.p t₂ ⟶ t'
cases ih₂ with
| inl hv₂ => p.inl.inl t₁:Tmt₂:Tmhv₁:IsValue t₁hv₂:IsValue t₂⊢ ∃ t', t₁.p t₂ ⟶ t'
cases hv₁ with
| const n₁ => p.inl.inl.const t₂:Tmhv₂:IsValue t₂n₁:Nat⊢ ∃ t', (Tm.c n₁).p t₂ ⟶ t'
cases hv₂ with
| const n₂ => p.inl.inl.const.const n₁:Natn₂:Nat⊢ ∃ t', (Tm.c n₁).p (Tm.c n₂) ⟶ t' exact ⟨.c (n₁ + n₂), .plus n₁ n₂⟩ All goals completed! 🐙
| inr h₂ => p.inl.inr t₁:Tmt₂:Tmhv₁:IsValue t₁h₂:∃ t', t₂ ⟶ t'⊢ ∃ t', t₁.p t₂ ⟶ t'
obtain ⟨t₂', ht₂⟩ := h₂ p.inl.inr t₁:Tmt₂:Tmhv₁:IsValue t₁t₂':Tmht₂:t₂ ⟶ t₂'⊢ ∃ t', t₁.p t₂ ⟶ t'
exact ⟨.p t₁ t₂', .plusRight t₁ t₂ t₂' hv₁ ht₂⟩ All goals completed! 🐙
| inr h₁ => p.inr t₁:Tmt₂:Tmih₂:IsValue t₂ ∨ ∃ t', t₂ ⟶ t'h₁:∃ t', t₁ ⟶ t'⊢ ∃ t', t₁.p t₂ ⟶ t'
obtain ⟨t₁', ht₁⟩ := h₁ p.inr t₁:Tmt₂:Tmih₂:IsValue t₂ ∨ ∃ t', t₂ ⟶ t't₁':Tmht₁:t₁ ⟶ t₁'⊢ ∃ t', t₁.p t₂ ⟶ t'
exact ⟨.p t₁' t₂, .plusLeft t₁ t₁' t₂ ht₁⟩ All goals completed! 🐙
def IsNormalForm {X : Type} (R : Relation X) (t : X) : Prop :=
¬ ∃ t', R t t'
We can use this terminology to generalize the observation we made in the strong progress theorem: in this language (though not necessarily, in general), normal forms and values are actually the same thing.
theorem value_is_nf (v : Tm)
(h : IsValue v) : IsNormalForm Step v := by v:Tmh:IsValue v⊢ IsNormalForm Step v
intro hc v:Tmh:IsValue vhc:∃ t', v ⟶ t'⊢ False
obtain ⟨t', ht⟩ := hc v:Tmh:IsValue vt':Tmht:v ⟶ t'⊢ False
cases h with
| const n => const t':Tmn:Natht:Tm.c n ⟶ t'⊢ False cases ht All goals completed! 🐙
theorem nf_is_value (t : Tm)
(h : IsNormalForm Step t) : IsValue t := by t:Tmh:IsNormalForm Step t⊢ IsValue t
cases strong_progress t with
| inl hv => inl t:Tmh:IsNormalForm Step thv:IsValue t⊢ IsValue t exact hv All goals completed! 🐙
| inr hstep => inr t:Tmh:IsNormalForm Step thstep:∃ t', t ⟶ t'⊢ IsValue t exact absurd hstep h All goals completed! 🐙
theorem nf_same_as_value (t : Tm) :
IsNormalForm Step t ↔ IsValue t := by t:Tm⊢ IsNormalForm Step t ↔ IsValue t
exact ⟨nf_is_value t, value_is_nf t⟩ All goals completed! 🐙
Tactic absurd is first introduced here. Do we want to explain it?
I think some of these proofs were originally Claude-generated, so we probably want to redo them from scratch, in which case introducing absurd is likely not necessary.
Why is this interesting? Because IsValue is a syntactic concept — it is
defined by looking at the way a term is written — while IsNormalForm is a
semantic one — it is defined by looking at how the term steps.
It is not obvious that these concepts should characterize the same set of terms!
Indeed, we could easily have written the definitions (incorrectly) so that they would not coincide.
Suppose, for example, we define IsValue so that it includes some terms that
are not finished reducing. (Even if you don't work the exercise
value_not_same_as_normal_form1 below and the following ones, make sure you
can think of an example of such a term.)
namespace Temp1
inductive IsValue : Tm → Prop where
| const (n : Nat) : IsValue (.c n)
| funny (t₁ : Tm) (n : Nat) : IsValue (.p t₁ (.c n)) -- <---
inductive Step : Tm → Tm → Prop where
| plus (n₁ n₂ : Nat) : Step (.p (.c n₁) (.c n₂)) (.c (n₁ + n₂))
| plusLeft (t₁ t₁' t₂ : Tm)
(h : Step t₁ t₁') :
Step (.p t₁ t₂) (.p t₁' t₂)
| plusRight (v₁ t₂ t₂' : Tm)
(hv : IsValue v₁)
(h : Step t₂ t₂') :
Step (.p v₁ t₂) (.p v₁ t₂')
Using this wrong definition of IsValue, to how many different values does
the following term reduce in zero or more steps?
.p (.p (.c 1) (.c 2)) (.c 3)
Show solution
Three: `.p (.p (.c 1) (.c 2)) (.c 3)` itself is a value; `.p (.c 3) (.c 3)` is a value; `.c 6` is a value.
To how many different terms does the following term Step (in one step)?
.p (.p (.c 1) (.c 2)) (.p (.c 3) (.c 4))
Show solution
Two: `.p (.c 3) (.p (.c 3) (.c 4))` via `plusLeft` and `.p (.p (.c 1) (.c 2)) (.c 7)` via `plusRight`.
theorem value_not_same_as_normal_form :
∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by ⊢ ∃ v, IsValue v ∧ ¬IsNormalForm Step v
apply Exists.intro (.p (.c 0) (.c 0)) ⊢ IsValue ((Tm.c 0).p (Tm.c 0)) ∧ ¬IsNormalForm Step ((Tm.c 0).p (Tm.c 0))
apply And.intro (.funny _ 0) ⊢ ¬IsNormalForm Step ((Tm.c 0).p (Tm.c 0))
sorry All goals completed! 🐙
end Temp1
Or we might (again, wrongly) define Step so that it permits something
designated as a value to reduce further. We again lose the property that
values are the same as normal forms.
namespace Temp2
inductive IsValue : Tm → Prop where
| const (n : Nat) : IsValue (.c n) -- Original definition
inductive Step : Tm → Tm → Prop where
| funny (n : Nat) : Step (.c n) (.p (.c n) (.c 0)) -- <--- NEW
| plus (n₁ n₂ : Nat) : Step (.p (.c n₁) (.c n₂)) (.c (n₁ + n₂))
| plusLeft (t₁ t₁' t₂ : Tm)
(h : Step t₁ t₁') :
Step (.p t₁ t₂) (.p t₁' t₂)
| plusRight (v₁ t₂ t₂' : Tm)
(hv : IsValue v₁)
(h : Step t₂ t₂') :
Step (.p v₁ t₂) (.p v₁ t₂')
With this definition, to how many different terms does the following term step (in exactly one step)?
.p (.c 1) (.c 3)
Show solution
Three: `plus` yields `.c 4`; `plusLeft` with `funny` yields `.p (.p (.c 1) (.c 0)) (.c 3)`; `plusRight` with `funny` yields `.p (.c 1) (.p (.c 3) (.c 0))`.
theorem value_not_same_as_normal_form :
∃ v, IsValue v ∧ ¬ IsNormalForm Step v := by ⊢ ∃ v, IsValue v ∧ ¬IsNormalForm Step v
apply Exists.intro (.c 5) ⊢ IsValue (Tm.c 5) ∧ ¬IsNormalForm Step (Tm.c 5)
apply And.intro (.const 5) ⊢ ¬IsNormalForm Step (Tm.c 5)
sorry All goals completed! 🐙
end Temp2
Finally, we might define IsValue and Step so that there is some term that
is not a value but that also cannot take a step. Such terms are said to
be stuck. In this case, this is caused by a mistake in the semantics, but
we will also see situations where, even in a correct language definition, it
makes sense to allow some terms to be stuck. (Note that plusRight is missing
below.)
namespace Temp3
inductive IsValue : Tm → Prop where
| const (n : Nat) : IsValue (.c n)
inductive Step : Tm → Tm → Prop where
| plus (n₁ n₂ : Nat) : Step (.p (.c n₁) (.c n₂)) (.c (n₁ + n₂))
| plusLeft (t₁ t₁' t₂ : Tm)
(h : Step t₁ t₁') :
Step (.p t₁ t₂) (.p t₁' t₂)
With this definition, to how many terms does the following term step (in one step)?
.p (.c 1) (.p (.c 1) (.c 2))
Show solution
none!
theorem value_not_same_as_normal_form :
∃ t, ¬ IsValue t ∧ IsNormalForm Step t := by ⊢ ∃ t, ¬IsValue t ∧ IsNormalForm Step t
apply Exists.intro (.p (.c 1) (.p (.c 1) (.c 2))) ⊢ ¬IsValue ((Tm.c 1).p ((Tm.c 1).p (Tm.c 2))) ∧ IsNormalForm Step ((Tm.c 1).p ((Tm.c 1).p (Tm.c 2)))
apply And.intro left ⊢ ¬IsValue ((Tm.c 1).p ((Tm.c 1).p (Tm.c 2)))right ⊢ IsNormalForm Step ((Tm.c 1).p ((Tm.c 1).p (Tm.c 2)))
· left ⊢ ¬IsValue ((Tm.c 1).p ((Tm.c 1).p (Tm.c 2))) sorry All goals completed! 🐙
· right ⊢ IsNormalForm Step ((Tm.c 1).p ((Tm.c 1).p (Tm.c 2))) sorry All goals completed! 🐙
end Temp3
3.4. Multi-Step Reduction
inductive Multi {X : Type} (R : Relation X) : X → X → Prop where
| refl (x : X) : Multi R x x
| step (x y z : X) (h₁ : R x y) (h₂ : Multi R y z) : Multi R x z
I would make some arguments implicit to provide a cleaner interface (FYI the mathlib version)
We write ⟶* for the Multi Step relation on terms
notation:40 t:41 " ⟶* " t':41 => Multi Step t t'
The relation Multi R has several crucial properties.
attribute [refl] Multi.refl
example : (.c 5 : Tm) ⟶* .c 5 := by ⊢ Tm.c 5 ⟶* Tm.c 5 rfl All goals completed! 🐙
example : (.p (.c 1) (.c 2)) ⟶* .c (1 + 2) := by ⊢ (Tm.c 1).p (Tm.c 2) ⟶* Tm.c (1 + 2)
apply Multi.step (y := .c (1 + 2)) h₁ ⊢ (Tm.c 1).p (Tm.c 2) ⟶ Tm.c (1 + 2)h₂ ⊢ Tm.c (1 + 2) ⟶* Tm.c (1 + 2)
· h₁ ⊢ (Tm.c 1).p (Tm.c 2) ⟶ Tm.c (1 + 2) exact .plus 1 2 All goals completed! 🐙
· h₂ ⊢ Tm.c (1 + 2) ⟶* Tm.c (1 + 2) rfl All goals completed! 🐙
theorem multi_single {X : Type} (R : Relation X) (x y : X)
(h : R x y) : Multi R x y := by X:TypeR:Relation Xx:Xy:Xh:R x y⊢ Multi R x y
exact .step x y y h (.refl y) All goals completed! 🐙
theorem multi_trans {X : Type} (R : Relation X) (x y z : X)
(g : Multi R x y) (h : Multi R y z) : Multi R x z := by X:TypeR:Relation Xx:Xy:Xz:Xg:Multi R x yh:Multi R y z⊢ Multi R x z
induction g with
| refl a => refl X:TypeR:Relation Xx:Xy:Xz:Xa:Xh:Multi R a z⊢ Multi R a z exact h All goals completed! 🐙
| step a b c h₁ h₂ ih => step X:TypeR:Relation Xx:Xy:Xz:Xa:Xb:Xc:Xh₁:R a bh₂:Multi R b cih:Multi R c z → Multi R b zh:Multi R c z⊢ Multi R a z exact .step a b z h₁ (ih h) All goals completed! 🐙
Which of the following relations on numbers cannot be expressed as
Multi R for some R?
(A) less than or equal (B) strictly less than (C) equal (D) none of the above
Show solution
(B) strictly less than
3.4.1. Examples
example :
(.p (.p (.c 0) (.c 3)) (.p (.c 2) (.c 4)))
⟶* .c ((0 + 3) + (2 + 4)) := by ⊢ ((Tm.c 0).p (Tm.c 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶* Tm.c (0 + 3 + (2 + 4))
apply Multi.step (y := .p (.c (0 + 3)) (.p (.c 2) (.c 4))) h₁ ⊢ ((Tm.c 0).p (Tm.c 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶ (Tm.c (0 + 3)).p ((Tm.c 2).p (Tm.c 4))h₂ ⊢ (Tm.c (0 + 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶* Tm.c (0 + 3 + (2 + 4))
· h₁ ⊢ ((Tm.c 0).p (Tm.c 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶ (Tm.c (0 + 3)).p ((Tm.c 2).p (Tm.c 4)) exact .plusLeft _ _ _ (.plus 0 3) All goals completed! 🐙
apply Multi.step (y := .p (.c (0 + 3)) (.c (2 + 4))) h₂.h₁ ⊢ (Tm.c (0 + 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶ (Tm.c (0 + 3)).p (Tm.c (2 + 4))h₂.h₂ ⊢ (Tm.c (0 + 3)).p (Tm.c (2 + 4)) ⟶* Tm.c (0 + 3 + (2 + 4))
· h₂.h₁ ⊢ (Tm.c (0 + 3)).p ((Tm.c 2).p (Tm.c 4)) ⟶ (Tm.c (0 + 3)).p (Tm.c (2 + 4)) exact .plusRight _ _ _ (.const _) (.plus 2 4) All goals completed! 🐙
· h₂.h₂ ⊢ (Tm.c (0 + 3)).p (Tm.c (2 + 4)) ⟶* Tm.c (0 + 3 + (2 + 4)) exact multi_single _ _ _ (.plus (0 + 3) (2 + 4)) All goals completed! 🐙
3.4.2. Normal Forms Again
If t reduces to t' in zero or more steps and t' is a normal form, we
say that "t' is a normal form of t."
def IsNormalFormOf {X : Type} (R : Relation X) (t t' : X) : Prop :=
Multi R t t' ∧ IsNormalForm R t'
When R is deterministic (as for our language's semantics), its normal form is unique.
theorem normal_forms_unique :
Deterministic (IsNormalFormOf Step) := by ⊢ Deterministic (IsNormalFormOf Step)
-- We recommend using this initial setup as-is!
intro x y₁ y₂ p₁ p₂ x:Tmy₁:Tmy₂:Tmp₁:IsNormalFormOf Step x y₁p₂:IsNormalFormOf Step x y₂⊢ y₁ = y₂
obtain ⟨p₁₁, p₁₂⟩ := p₁ x:Tmy₁:Tmy₂:Tmp₂:IsNormalFormOf Step x y₂p₁₁:x ⟶* y₁p₁₂:IsNormalForm Step y₁⊢ y₁ = y₂
obtain ⟨p₂₁, p₂₂⟩ := p₂ x:Tmy₁:Tmy₂:Tmp₁₁:x ⟶* y₁p₁₂:IsNormalForm Step y₁p₂₁:x ⟶* y₂p₂₂:IsNormalForm Step y₂⊢ y₁ = y₂
sorry All goals completed! 🐙
The Step relation is normalizing: every term reaches a normal form in
a finite number of steps. Determinism guarantees that normal form is unique.
unique.
def Normalizing {X : Type} (R : Relation X) : Prop :=
∀ t, ∃ t', IsNormalFormOf R t t'
theorem multistep_congr_1 (t₁ t₁' t₂ : Tm) (h : t₁ ⟶* t₁') :
(.p t₁ t₂) ⟶* (.p t₁' t₂) := by t₁:Tmt₁':Tmt₂:Tmh:t₁ ⟶* t₁'⊢ t₁.p t₂ ⟶* t₁'.p t₂
induction h with
| refl x => refl t₁:Tmt₁':Tmt₂:Tmx:Tm⊢ x.p t₂ ⟶* x.p t₂ exact .refl _ All goals completed! 🐙
| step x y z h₁ h₂ ih => step t₁:Tmt₁':Tmt₂:Tmx:Tmy:Tmz:Tmh₁:x ⟶ yh₂:y ⟶* zih:y.p t₂ ⟶* z.p t₂⊢ x.p t₂ ⟶* z.p t₂ exact .step _ (.p y t₂) _ (.plusLeft x y t₂ h₁) ih All goals completed! 🐙
theorem multistep_congr_2 (v₁ t₂ t₂' : Tm) (hv : IsValue v₁)
(h : t₂ ⟶* t₂') :
(.p v₁ t₂) ⟶* (.p v₁ t₂') := by v₁:Tmt₂:Tmt₂':Tmhv:IsValue v₁h:t₂ ⟶* t₂'⊢ v₁.p t₂ ⟶* v₁.p t₂'
sorry All goals completed! 🐙
theorem step_normalizing : Normalizing Step := by ⊢ Normalizing Step
intro t t:Tm⊢ ∃ t', IsNormalFormOf Step t t'
induction t with
| c n => c n:Nat⊢ ∃ t', IsNormalFormOf Step (Tm.c n) t' exact ⟨.c n, .refl _, (nf_same_as_value _).mpr (.const n)⟩ All goals completed! 🐙
| p t₁ t₂ ih₁ ih₂ => p t₁:Tmt₂:Tmih₁:∃ t', IsNormalFormOf Step t₁ t'ih₂:∃ t', IsNormalFormOf Step t₂ t'⊢ ∃ t', IsNormalFormOf Step (t₁.p t₂) t'
obtain ⟨t₁', hs₁, hnf₁⟩ := ih₁ p t₁:Tmt₂:Tmih₂:∃ t', IsNormalFormOf Step t₂ t't₁':Tmhs₁:t₁ ⟶* t₁'hnf₁:IsNormalForm Step t₁'⊢ ∃ t', IsNormalFormOf Step (t₁.p t₂) t'
obtain ⟨t₂', hs₂, hnf₂⟩ := ih₂ p t₁:Tmt₂:Tmt₁':Tmhs₁:t₁ ⟶* t₁'hnf₁:IsNormalForm Step t₁'t₂':Tmhs₂:t₂ ⟶* t₂'hnf₂:IsNormalForm Step t₂'⊢ ∃ t', IsNormalFormOf Step (t₁.p t₂) t'
obtain ⟨n₁⟩ := (nf_same_as_value _).mp hnf₁ p t₁:Tmt₂:Tmt₂':Tmhs₂:t₂ ⟶* t₂'hnf₂:IsNormalForm Step t₂'n₁:Naths₁:t₁ ⟶* Tm.c n₁hnf₁:IsNormalForm Step (Tm.c n₁)⊢ ∃ t', IsNormalFormOf Step (t₁.p t₂) t'
obtain ⟨n₂⟩ := (nf_same_as_value _).mp hnf₂ p t₁:Tmt₂:Tmn₁:Naths₁:t₁ ⟶* Tm.c n₁hnf₁:IsNormalForm Step (Tm.c n₁)n₂:Naths₂:t₂ ⟶* Tm.c n₂hnf₂:IsNormalForm Step (Tm.c n₂)⊢ ∃ t', IsNormalFormOf Step (t₁.p t₂) t'
apply Exists.intro (.c (n₁ + n₂)) p t₁:Tmt₂:Tmn₁:Naths₁:t₁ ⟶* Tm.c n₁hnf₁:IsNormalForm Step (Tm.c n₁)n₂:Naths₂:t₂ ⟶* Tm.c n₂hnf₂:IsNormalForm Step (Tm.c n₂)⊢ IsNormalFormOf Step (t₁.p t₂) (Tm.c (n₁ + n₂))
apply And.intro _ ((nf_same_as_value _).mpr (.const _)) t₁:Tmt₂:Tmn₁:Naths₁:t₁ ⟶* Tm.c n₁hnf₁:IsNormalForm Step (Tm.c n₁)n₂:Naths₂:t₂ ⟶* Tm.c n₂hnf₂:IsNormalForm Step (Tm.c n₂)⊢ t₁.p t₂ ⟶* Tm.c (n₁ + n₂)
apply multi_trans _ _ _ _ (multistep_congr_1 t₁ (.c n₁) t₂ hs₁) t₁:Tmt₂:Tmn₁:Naths₁:t₁ ⟶* Tm.c n₁hnf₁:IsNormalForm Step (Tm.c n₁)n₂:Naths₂:t₂ ⟶* Tm.c n₂hnf₂:IsNormalForm Step (Tm.c n₂)⊢ (Tm.c n₁).p t₂ ⟶* Tm.c (n₁ + n₂)
apply multi_trans _ _ _ _ (multistep_congr_2 (.c n₁) t₂ (.c n₂) (.const n₁) hs₂) t₁:Tmt₂:Tmn₁:Naths₁:t₁ ⟶* Tm.c n₁hnf₁:IsNormalForm Step (Tm.c n₁)n₂:Naths₂:t₂ ⟶* Tm.c n₂hnf₂:IsNormalForm Step (Tm.c n₂)⊢ (Tm.c n₁).p (Tm.c n₂) ⟶* Tm.c (n₁ + n₂)
exact multi_single _ _ _ (.plus n₁ n₂) All goals completed! 🐙
3.4.3. Equivalence of Big-Step and Small-Step
Having defined the operational semantics of our tiny programming language in two different ways (big-step and small-step), it makes sense to ask whether these definitions actually define the same thing!
They do, though it takes a little work to show it. The details are left as an exercise. We consider the two implications separately. First, big-step evaluation implies multi-step reduction to a value.
theorem multistep_of_eval (t : Tm) (n : Nat) (h : t ⇓ n) :
t ⟶* .c n := by t:Tmn:Nath:t ⇓ n⊢ t ⟶* Tm.c n
sorry All goals completed! 🐙
The key ideas in the proof can be seen in the following picture:
p t₁ t₂ ⟶ (by plusLeft) p t₁' t₂ ⟶ (by plusLeft) p t₁'' t₂ ⟶ (by plusLeft) ... p (c n₁) t₂ ⟶ (by plusRight) p (c n₁) t₂' ⟶ (by plusRight) p (c n₁) t₂'' ⟶ (by plusRight) ... p (c n₁) (c n₂) ⟶ (by plus) c (n₁ + n₂)
That is, the multi-step reduction of a term of the form p t₁ t₂ proceeds in
three phases:
-
First, we use
plusLeftsome number of times to reducet₁to a normal form, which must (bynf_same_as_value) be a term of the formc n₁for somen₁. -
Next, we use
plusRightsome number of times to reducet₂to a normal form, which must again be a term of the formc n₂for somen₂. -
Finally, we use
plusone time to reducep (c n₁) (c n₂)toc (n₁ + n₂).
To formalize this intuition, you'll need the congruence lemmas from above,
plus some basic properties of ⟶* (that it is reflexive, transitive, and
includes ⟶).
For the converse, we need one lemma, which establishes a relation between single-step reduction and big-step evaluation. A single step preserves the big-step value.
theorem eval_of_step (t t' : Tm) (n : Nat) (hs : t ⟶ t')
(he : t' ⇓ n) : t ⇓ n := by t:Tmt':Tmn:Naths:t ⟶ t'he:t' ⇓ n⊢ t ⇓ n
sorry All goals completed! 🐙
The fact that small-step reduction implies big-step evaluation is now
straightforward to prove, once we have factored out the observation that
every normal form is a value. The proof proceeds by induction on the
multi-step reduction sequence that is buried in the hypothesis
IsNormalFormOf t t'. (Make sure you understand the statement before you
start to work on the proof.)
theorem eval_of_multistep (t t' : Tm) (h : IsNormalFormOf Step t t') :
∃ n, t' = .c n ∧ t ⇓ n := by t:Tmt':Tmh:IsNormalFormOf Step t t'⊢ ∃ n, t' = Tm.c n ∧ t ⇓ n
sorry All goals completed! 🐙
3.5. Small-Step Slang
Small-step semantics for the richer Slang arithmetic and boolean
expressions. Notations: ⟶a (arithmetic) and ⟶b (boolean).
We work in the Slang namespace, reusing the arithmetic and boolean expression
syntax (Aexp, Bexp) and the big-step evaluator (Aexp.eval) from the
Slang chapter:
namespace Slang
3.5.1. Arithmetic Expressions
The arithmetic values (the normal forms of the small-step relation below) are just the numeric literals:
inductive IsAValue : Aexp → Prop where
| num (n : Nat) : IsAValue (.num n)
inductive AStep : Aexp → Aexp → Prop where
| plusLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
AStep (.plus a₁ a₂) (.plus a₁' a₂)
| plusRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
AStep (.plus v₁ a₂) (.plus v₁ a₂')
| plus (n₁ n₂ : Nat) :
AStep (.plus (.num n₁) (.num n₂)) (.num (n₁ + n₂))
| minusLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
AStep (.minus a₁ a₂) (.minus a₁' a₂)
| minusRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
AStep (.minus v₁ a₂) (.minus v₁ a₂')
| minus (n₁ n₂ : Nat) :
AStep (.minus (.num n₁) (.num n₂)) (.num (n₁ - n₂))
| multLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
AStep (.mult a₁ a₂) (.mult a₁' a₂)
| multRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
AStep (.mult v₁ a₂) (.mult v₁ a₂')
| mult (n₁ n₂ : Nat) :
AStep (.mult (.num n₁) (.num n₂)) (.num (n₁ * n₂))
scoped notation:40 a:41 " ⟶a " a':41 => AStep a a'
Here is a one-step reduction: since the left operand 3 is already a value,
the right operand is the one that takes a step.
example :
(Aexp.plus (.num 3) (.plus (.num 2) (.num 1)))
⟶a (.plus (.num 3) (.num 3)) := by ⊢ (Aexp.num 3).plus ((Aexp.num 2).plus (Aexp.num 1)) ⟶a (Aexp.num 3).plus (Aexp.num 3)
exact .plusRight (.num 3) (.plus 2 1) All goals completed! 🐙
3.5.2. Boolean Expressions
inductive BStep : Bexp → Bexp → Prop where
| eqLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
BStep (.eq a₁ a₂) (.eq a₁' a₂)
| eqRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
BStep (.eq v₁ a₂) (.eq v₁ a₂')
| eq (n₁ n₂ : Nat) :
BStep (.eq (.num n₁) (.num n₂)) (.bool (decide (n₁ = n₂)))
| neqLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
BStep (.neq a₁ a₂) (.neq a₁' a₂)
| neqRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
BStep (.neq v₁ a₂) (.neq v₁ a₂')
| neq (n₁ n₂ : Nat) :
BStep (.neq (.num n₁) (.num n₂)) (.bool (decide (n₁ ≠ n₂)))
| leLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
BStep (.le a₁ a₂) (.le a₁' a₂)
| leRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
BStep (.le v₁ a₂) (.le v₁ a₂')
| le (n₁ n₂ : Nat) :
BStep (.le (.num n₁) (.num n₂)) (.bool (decide (n₁ ≤ n₂)))
| gtLeft {a₁ a₁' a₂ : Aexp}
(h : AStep a₁ a₁') :
BStep (.gt a₁ a₂) (.gt a₁' a₂)
| gtRight {v₁ a₂ a₂' : Aexp}
(hv : IsAValue v₁)
(h : AStep a₂ a₂') :
BStep (.gt v₁ a₂) (.gt v₁ a₂')
| gt (n₁ n₂ : Nat) :
BStep (.gt (.num n₁) (.num n₂)) (.bool (decide (n₁ > n₂)))
| notStep {b₁ b₁' : Bexp}
(h : BStep b₁ b₁') :
BStep (.not b₁) (.not b₁')
| notTrue : BStep (.not (.bool true)) (.bool false)
| notFalse : BStep (.not (.bool false)) (.bool true)
| andStep {b₁ b₁' b₂ : Bexp}
(h : BStep b₁ b₁') :
BStep (.and b₁ b₂) (.and b₁' b₂)
| andTrueStep {b₂ b₂' : Bexp} (h : BStep b₂ b₂') :
BStep (.and (.bool true) b₂) (.and (.bool true) b₂')
| andFalse (b₂ : Bexp) : BStep (.and (.bool false) b₂) (.bool false)
| andTrueTrue : BStep (.and (.bool true) (.bool true)) (.bool true)
| andTrueFalse :
BStep (.and (.bool true) (.bool false)) (.bool false)
scoped notation:40 b:41 " ⟶b " b':41 => BStep b b'
A boolean example — the left comparison operand reduces first:
example :
(Bexp.le (.plus (.num 1) (.num 1)) (.num 3))
⟶b (.le (.num 2) (.num 3)) := by ⊢ Bexp.le ((Aexp.num 1).plus (Aexp.num 1)) (Aexp.num 3) ⟶b Bexp.le (Aexp.num 2) (Aexp.num 3)
exact .leLeft (.plus 1 1) All goals completed! 🐙
Which of these properties does this small-step semantics for Slang
expressions satisfy? (Yes or No for each.)
-
determinism
-
strong progress (every non-value takes a step)
-
values and normal forms coincide (i.e., there are no "stuck" terms)
-
the step relation is normalizing (i.e., evaluation always terminates)
Show solution
Yes to all four. Expression evaluation always terminates, so ⟶a (and ⟶b) are normalizing.
3.5.3. Nondeterministic Evaluation
⟶n: like ⟶a, but with the IsAValue guard on the "step the right operand"
rules removed, so the evaluation order is nondeterministic.
inductive ANStep : Aexp → Aexp → Prop where
| plusLeft {a₁ a₁' a₂ : Aexp}
(h : ANStep a₁ a₁') :
ANStep (.plus a₁ a₂) (.plus a₁' a₂)
| plusRight {a₁ a₂ a₂' : Aexp}
(h : ANStep a₂ a₂') :
ANStep (.plus a₁ a₂) (.plus a₁ a₂')
| plus (n₁ n₂ : Nat) :
ANStep (.plus (.num n₁) (.num n₂)) (.num (n₁ + n₂))
| minusLeft {a₁ a₁' a₂ : Aexp}
(h : ANStep a₁ a₁') :
ANStep (.minus a₁ a₂) (.minus a₁' a₂)
| minusRight {a₁ a₂ a₂' : Aexp}
(h : ANStep a₂ a₂') :
ANStep (.minus a₁ a₂) (.minus a₁ a₂')
| minus (n₁ n₂ : Nat) :
ANStep (.minus (.num n₁) (.num n₂)) (.num (n₁ - n₂))
| multLeft {a₁ a₁' a₂ : Aexp}
(h : ANStep a₁ a₁') :
ANStep (.mult a₁ a₂) (.mult a₁' a₂)
| multRight {a₁ a₂ a₂' : Aexp}
(h : ANStep a₂ a₂') :
ANStep (.mult a₁ a₂) (.mult a₁ a₂')
| mult (n₁ n₂ : Nat) :
ANStep (.mult (.num n₁) (.num n₂)) (.num (n₁ * n₂))
scoped notation:40 a:41 " ⟶n " a':41 => ANStep a a'
Unlike ⟶a, this relation really is nondeterministic: a single term can step
in two different ways, depending on which operand we choose to advance.
theorem anstep_not_deterministic : ¬ Deterministic ANStep := by ⊢ ¬Deterministic ANStep
intro hd hd:Deterministic ANStep⊢ False
have s₁ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
(.plus (.num 2) (.plus (.num 2) (.num 2))) :=
.plusLeft (.plus 1 1) hd:Deterministic ANSteps₁:((Aexp.num 1).plus (Aexp.num 1)).plus ((Aexp.num 2).plus (Aexp.num 2)) ⟶n
(Aexp.num 2).plus ((Aexp.num 2).plus (Aexp.num 2))⊢ False
have s₂ : ANStep (.plus (.plus (.num 1) (.num 1)) (.plus (.num 2) (.num 2)))
(.plus (.plus (.num 1) (.num 1)) (.num 4)) :=
.plusRight (.plus 2 2) hd:Deterministic ANSteps₁:((Aexp.num 1).plus (Aexp.num 1)).plus ((Aexp.num 2).plus (Aexp.num 2)) ⟶n
(Aexp.num 2).plus ((Aexp.num 2).plus (Aexp.num 2))s₂:((Aexp.num 1).plus (Aexp.num 1)).plus ((Aexp.num 2).plus (Aexp.num 2)) ⟶n
((Aexp.num 1).plus (Aexp.num 1)).plus (Aexp.num 4)⊢ False
have heq := hd _ _ _ s₁ s₂ hd:Deterministic ANSteps₁:((Aexp.num 1).plus (Aexp.num 1)).plus ((Aexp.num 2).plus (Aexp.num 2)) ⟶n
(Aexp.num 2).plus ((Aexp.num 2).plus (Aexp.num 2))s₂:((Aexp.num 1).plus (Aexp.num 1)).plus ((Aexp.num 2).plus (Aexp.num 2)) ⟶n
((Aexp.num 1).plus (Aexp.num 1)).plus (Aexp.num 4)heq:(Aexp.num 2).plus ((Aexp.num 2).plus (Aexp.num 2)) = ((Aexp.num 1).plus (Aexp.num 1)).plus (Aexp.num 4)⊢ False
simp at heq All goals completed! 🐙
Prove that one nondeterministic step leaves the big-step value unchanged.
Hint: induction on the step derivation; each case is immediate from eval
and, where present, the induction hypothesis.
theorem anstep_preserves_eval (a a' : Aexp) (h : a ⟶n a') :
a.eval = a'.eval := by a:Aexpa':Aexph:a ⟶n a'⊢ a.eval = a'.eval
sorry All goals completed! 🐙
This lifts to any number of steps by a routine induction on the multi-step derivation:
theorem multi_anstep_preserves_eval (a a' : Aexp)
(h : Multi ANStep a a') : a.eval = a'.eval := by a:Aexpa':Aexph:Multi ANStep a a'⊢ a.eval = a'.eval
induction h with
| refl x => refl a:Aexpa':Aexpx:Aexp⊢ x.eval = x.eval rfl All goals completed! 🐙
| step x y z h₁ _ ih => step a:Aexpa':Aexpx:Aexpy:Aexpz:Aexph₁:x ⟶n yh₂✝:Multi ANStep y zih:y.eval = z.eval⊢ x.eval = z.eval rw [anstep_preserves_eval x y h₁ step a:Aexpa':Aexpx:Aexpy:Aexpz:Aexph₁:x ⟶n yh₂✝:Multi ANStep y zih:y.eval = z.eval⊢ y.eval = z.eval] step a:Aexpa':Aexpx:Aexpy:Aexpz:Aexph₁:x ⟶n yh₂✝:Multi ANStep y zih:y.eval = z.eval⊢ y.eval = z.eval; exact ih All goals completed! 🐙
theorem astep_imp_anstep (a a' : Aexp) (h : a ⟶a a') : a ⟶n a' := by a:Aexpa':Aexph:a ⟶a a'⊢ a ⟶n a'
induction h with
| plusLeft _ ih => plusLeft a:Aexpa':Aexpa₁✝:Aexpa₁'✝:Aexpa₂✝:Aexph✝:a₁✝ ⟶a a₁'✝ih:a₁✝ ⟶n a₁'✝⊢ a₁✝.plus a₂✝ ⟶n a₁'✝.plus a₂✝ exact .plusLeft ih All goals completed! 🐙
| plusRight _ _ ih => plusRight a:Aexpa':Aexpv₁✝:Aexpa₂✝:Aexpa₂'✝:Aexphv✝:IsAValue v₁✝h✝:a₂✝ ⟶a a₂'✝ih:a₂✝ ⟶n a₂'✝⊢ v₁✝.plus a₂✝ ⟶n v₁✝.plus a₂'✝ exact .plusRight ih All goals completed! 🐙
| plus n₁ n₂ => plus a:Aexpa':Aexpn₁:Natn₂:Nat⊢ (Aexp.num n₁).plus (Aexp.num n₂) ⟶n Aexp.num (n₁ + n₂) exact .plus n₁ n₂ All goals completed! 🐙
| minusLeft _ ih => minusLeft a:Aexpa':Aexpa₁✝:Aexpa₁'✝:Aexpa₂✝:Aexph✝:a₁✝ ⟶a a₁'✝ih:a₁✝ ⟶n a₁'✝⊢ a₁✝.minus a₂✝ ⟶n a₁'✝.minus a₂✝ exact .minusLeft ih All goals completed! 🐙
| minusRight _ _ ih => minusRight a:Aexpa':Aexpv₁✝:Aexpa₂✝:Aexpa₂'✝:Aexphv✝:IsAValue v₁✝h✝:a₂✝ ⟶a a₂'✝ih:a₂✝ ⟶n a₂'✝⊢ v₁✝.minus a₂✝ ⟶n v₁✝.minus a₂'✝ exact .minusRight ih All goals completed! 🐙
| minus n₁ n₂ => minus a:Aexpa':Aexpn₁:Natn₂:Nat⊢ (Aexp.num n₁).minus (Aexp.num n₂) ⟶n Aexp.num (n₁ - n₂) exact .minus n₁ n₂ All goals completed! 🐙
| multLeft _ ih => multLeft a:Aexpa':Aexpa₁✝:Aexpa₁'✝:Aexpa₂✝:Aexph✝:a₁✝ ⟶a a₁'✝ih:a₁✝ ⟶n a₁'✝⊢ a₁✝.mult a₂✝ ⟶n a₁'✝.mult a₂✝ exact .multLeft ih All goals completed! 🐙
| multRight _ _ ih => multRight a:Aexpa':Aexpv₁✝:Aexpa₂✝:Aexpa₂'✝:Aexphv✝:IsAValue v₁✝h✝:a₂✝ ⟶a a₂'✝ih:a₂✝ ⟶n a₂'✝⊢ v₁✝.mult a₂✝ ⟶n v₁✝.mult a₂'✝ exact .multRight ih All goals completed! 🐙
| mult n₁ n₂ => mult a:Aexpa':Aexpn₁:Natn₂:Nat⊢ (Aexp.num n₁).mult (Aexp.num n₂) ⟶n Aexp.num (n₁ * n₂) exact .mult n₁ n₂ All goals completed! 🐙
theorem multi_astep_imp_anstep (a a' : Aexp)
(h : Multi AStep a a') : Multi ANStep a a' := by a:Aexpa':Aexph:Multi AStep a a'⊢ Multi ANStep a a'
induction h with
| refl x => refl a:Aexpa':Aexpx:Aexp⊢ Multi ANStep x x exact .refl x All goals completed! 🐙
| step x y z h₁ _ ih => step a:Aexpa':Aexpx:Aexpy:Aexpz:Aexph₁:x ⟶a yh₂✝:Multi AStep y zih:Multi ANStep y z⊢ Multi ANStep x z exact .step x y z (astep_imp_anstep x y h₁) ih All goals completed! 🐙
3.5.4. A Small-Step Stack Machine
Our last example is a small-step semantics for a stack machine that evaluates
arithmetic expressions. The machine's instructions push a constant or combine the
top two stack entries. The machine's behavior should match the big-step Aexp.eval
function defined earlier.
A program is a list of instructions, and the stack is a list of numbers.
inductive SInstr where
| push (n : Nat)
| plus
| minus
| mult
abbrev Stack := List Nat
abbrev Prog := List SInstr
The compiler emits code in the postfix order sketched above:
def compile : Aexp → Prog
| .num n => [.push n]
| .plus a₁ a₂ => compile a₁ ++ compile a₂ ++ [.plus]
| .minus a₁ a₂ => compile a₁ ++ compile a₂ ++ [.minus]
| .mult a₁ a₂ => compile a₁ ++ compile a₂ ++ [.mult]
example :
compile (.plus (.num 2) (.num 3)) =
[.push 2, .push 3, .plus] := by ⊢ compile ((Aexp.num 2).plus (Aexp.num 3)) = [SInstr.push 2, SInstr.push 3, SInstr.plus]
rfl All goals completed! 🐙
Now the small-step machine itself: each step consumes the next instruction and updates the stack.
inductive StackStep : Prog × Stack → Prog × Stack → Prop where
| push (p : Prog) (stk : Stack) (n : Nat) :
StackStep (.push n :: p, stk) (p, n :: stk)
| plus (p : Prog) (stk : Stack) (n m : Nat) :
StackStep (.plus :: p, n :: m :: stk) (p, (m + n) :: stk)
| minus (p : Prog) (stk : Stack) (n m : Nat) :
StackStep (.minus :: p, n :: m :: stk) (p, (m - n) :: stk)
| mult (p : Prog) (stk : Stack) (n m : Nat) :
StackStep (.mult :: p, n :: m :: stk) (p, (m * n) :: stk)
The machine is deterministic:
theorem stack_step_deterministic : Deterministic StackStep := by ⊢ Deterministic StackStep
intro x y₁ y₂ h₁ h₂ x:Prog × Stacky₁:Prog × Stacky₂:Prog × Stackh₁:StackStep x y₁h₂:StackStep x y₂⊢ y₁ = y₂
cases h₁ push y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Nath₂:StackStep (SInstr.push n✝ :: p✝, stk✝) y₂⊢ (p✝, n✝ :: stk✝) = y₂plus y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Natm✝:Nath₂:StackStep (SInstr.plus :: p✝, n✝ :: m✝ :: stk✝) y₂⊢ (p✝, (m✝ + n✝) :: stk✝) = y₂minus y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Natm✝:Nath₂:StackStep (SInstr.minus :: p✝, n✝ :: m✝ :: stk✝) y₂⊢ (p✝, (m✝ - n✝) :: stk✝) = y₂mult y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Natm✝:Nath₂:StackStep (SInstr.mult :: p✝, n✝ :: m✝ :: stk✝) y₂⊢ (p✝, m✝ * n✝ :: stk✝) = y₂ <;> push y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Nath₂:StackStep (SInstr.push n✝ :: p✝, stk✝) y₂⊢ (p✝, n✝ :: stk✝) = y₂plus y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Natm✝:Nath₂:StackStep (SInstr.plus :: p✝, n✝ :: m✝ :: stk✝) y₂⊢ (p✝, (m✝ + n✝) :: stk✝) = y₂minus y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Natm✝:Nath₂:StackStep (SInstr.minus :: p✝, n✝ :: m✝ :: stk✝) y₂⊢ (p✝, (m✝ - n✝) :: stk✝) = y₂mult y₂:Prog × Stackp✝:Progstk✝:Stackn✝:Natm✝:Nath₂:StackStep (SInstr.mult :: p✝, n✝ :: m✝ :: stk✝) y₂⊢ (p✝, m✝ * n✝ :: stk✝) = y₂ cases h₂ mult.mult p✝:Progstk✝:Stackn✝:Natm✝:Nat⊢ (p✝, m✝ * n✝ :: stk✝) = (p✝, m✝ * n✝ :: stk✝) <;> push.push p✝:Progstk✝:Stackn✝:Nat⊢ (p✝, n✝ :: stk✝) = (p✝, n✝ :: stk✝)plus.plus p✝:Progstk✝:Stackn✝:Natm✝:Nat⊢ (p✝, (m✝ + n✝) :: stk✝) = (p✝, (m✝ + n✝) :: stk✝)minus.minus p✝:Progstk✝:Stackn✝:Natm✝:Nat⊢ (p✝, (m✝ - n✝) :: stk✝) = (p✝, (m✝ - n✝) :: stk✝)mult.mult p✝:Progstk✝:Stackn✝:Natm✝:Nat⊢ (p✝, m✝ * n✝ :: stk✝) = (p✝, m✝ * n✝ :: stk✝) rfl All goals completed! 🐙
end Slang
3.5.5. Automation with solve_by_elim
Proofs that one expression multisteps to another can be tedious...
example : (.p (.c 3) (.p (.c 3) (.c 4))) ⟶* (.c 10) := by ⊢ (Tm.c 3).p ((Tm.c 3).p (Tm.c 4)) ⟶* Tm.c 10
apply Multi.step (y := .p (.c 3) (.c 7)) h₁ ⊢ (Tm.c 3).p ((Tm.c 3).p (Tm.c 4)) ⟶ (Tm.c 3).p (Tm.c 7)h₂ ⊢ (Tm.c 3).p (Tm.c 7) ⟶* Tm.c 10
· h₁ ⊢ (Tm.c 3).p ((Tm.c 3).p (Tm.c 4)) ⟶ (Tm.c 3).p (Tm.c 7) apply Step.plusRight h₁.hv ⊢ IsValue (Tm.c 3)h₁.h ⊢ (Tm.c 3).p (Tm.c 4) ⟶ Tm.c 7
· h₁.hv ⊢ IsValue (Tm.c 3) apply IsValue.const All goals completed! 🐙
· h₁.h ⊢ (Tm.c 3).p (Tm.c 4) ⟶ Tm.c 7 apply Step.plus All goals completed! 🐙
· h₂ ⊢ (Tm.c 3).p (Tm.c 7) ⟶* Tm.c 10 apply Multi.step (y := .c 10) h₂.h₁ ⊢ (Tm.c 3).p (Tm.c 7) ⟶ Tm.c 10h₂.h₂ ⊢ Tm.c 10 ⟶* Tm.c 10
· h₂.h₁ ⊢ (Tm.c 3).p (Tm.c 7) ⟶ Tm.c 10 apply Step.plus All goals completed! 🐙
· h₂.h₂ ⊢ Tm.c 10 ⟶* Tm.c 10 apply Multi.refl All goals completed! 🐙
We can automate such tedious proofs with solve_by_elim:
example : (.p (.c 3) (.p (.c 3) (.c 4))) ⟶* (.c 10) := by ⊢ (Tm.c 3).p ((Tm.c 3).p (Tm.c 4)) ⟶* Tm.c 10
repeat apply Multi.step h₂.h₁ ⊢ (Tm.c 3).p (Tm.c (3 + 4)) ⟶ ?h₂.yh₂.h₂ ⊢ ?h₂.y ⟶* Tm.c 10h₂.y ⊢ Tm <;> h₂.h₁ ⊢ (Tm.c 3).p (Tm.c (3 + 4)) ⟶ ?h₂.yh₂.h₂ ⊢ ?h₂.y ⟶* Tm.c 10h₂.y ⊢ Tm
try solve_by_elim [Step.plusRight, Step.plusLeft, Step.plus, IsValue.const] All goals completed! 🐙
This one script would suffice to prove most concrete reduction sequences
for this simple language. To make it work for others, we would need to supply
constructors for those other languages to solve_by_elim. The languages we
will study in this book can grow to a large number of constructors for their Step
relations, so we'd like a way to supply all of them to solve_by_elim more easily.
Luckily, Lean supports this. We can register a constructor (or lemma) for use with
solve_by_elim with an attribute command:
Attributes
The command below tags all of these constructors with the SimpleArith attribute,
which we can then use to automatically pull all of these constructors in when we use
solve_by_elim. However, due to a limitation of Lean, this attribute needs to be
pre-declared in a different file; we can't create it here and then immediately use it.
For this book, we've predeclared all the attributes we'll use in a file called
AttributeDecls.lean, following the typical pattern from libraries like Mathlib.
attribute [SimpleArith]
Step.plusRight Step.plusLeft Step.plus IsValue.const
This using option then tells solve_by_elim to try to use every constructor
we've registered with the supplied attribute:
example : (.p (.c 3) (.p (.c 3) (.c 4))) ⟶* (.c 10) := by ⊢ (Tm.c 3).p ((Tm.c 3).p (Tm.c 4)) ⟶* Tm.c 10
repeat apply Multi.step h₂.h₁ ⊢ (Tm.c 3).p (Tm.c (3 + 4)) ⟶ ?h₂.yh₂.h₂ ⊢ ?h₂.y ⟶* Tm.c 10h₂.y ⊢ Tm <;> h₂.h₁ ⊢ (Tm.c 3).p (Tm.c (3 + 4)) ⟶ ?h₂.yh₂.h₂ ⊢ ?h₂.y ⟶* Tm.c 10h₂.y ⊢ Tm
try solve_by_elim using SimpleArith All goals completed! 🐙
We can package all this up into a dedicated tactic for solving reduction sequences,
which we'll call normalize:
syntax "normalize" " using " ident,+ : tactic
macro_rules
| `(tactic| normalize using $xs,*) =>
`(tactic|
first
| apply Multi.refl
| (apply Multi.step
· solve_by_elim (maxDepth := 15) (constructor := false) only using $xs,*
· normalize using $xs,*))
And voilà:
example : (.p (.c 3) (.p (.c 3) (.c 4))) ⟶* (.c 10) := by ⊢ (Tm.c 3).p ((Tm.c 3).p (Tm.c 4)) ⟶* Tm.c 10
normalize using SimpleArith All goals completed! 🐙