How is it shown that Big Step semantics and Small Step semantics are equivalent for IMP?

I know there is this document but I wanted to do a special case test just for IMP for fun. Then the theorem is:

$$ langle P, sigma rangle to_ {Big} langle {}, sigma & # 39; rangle iff exists N in mathbf N: langle P, sigma rangle to ^ N_ {Small} langle {}, sigma & # 39; rangle $$

in words; the program p in state $ sigma $ evaluates to the empty block IFF there is a certain number of small steps inference steps that lead us to the same configuration, the empty program in state $ sigma & # 39; $. Note $ langle P, sigma rangle $ represents a stateful program configuration $ sigma $. I assume that both the small step and the large step have the same type of configuration, which could be a big and difficult assumption to formalize in real code …

I'm happy with just a sketch / sketch, since a rigorous test is probably too much work and I prefer to get something than nothing.

I want to focus on $ Rightarrow $ (large to small). I think one of my main difficulties is finding such $ N $ that works. But conceptually, for me, I think I would break the test by induction in the P program. The program has 6 constructors / cases:

  1. Empty block {}
  2. Block B that is fair $ {S } $
  3. Assignments $ x = AExp; $
  4. Sequences $ S_1; S_2 $ where $ S_i $ It is a statement.
  5. while the statements $ While (BExp) do S $.
  6. ifElse statements $ If (BExp) do S_1 Else S_2 $.

for the first case 1) it's simple we have $ langle {}, sigma & # 39; rangle $ in HRH for big steps and in the LHS $ langle {}, sigma & # 39; rangle $ For small steps, which are the same configuration. Fact.

3) For the case assignment case, we have to show that the AExp expressed in the semantics, let's say that big step or small step is evaluated just like the "aeval" function that recursively only evaluates a real arithmetic expression. I'm not sure how I can do this more rigorously, but at least it's a start.

Things with boolean expressions in them also need the same beval equivalence with the Boolean evaluation equivalence in their corresponding semantics.

However, when things involve affirmations, I am honestly not sure what one would have to argue to prove that they are equivalent. Do we induce again in each statement and then proceed by applying the inference rules as many times as possible and show that they are evaluated to the same final state and empty block? Or what needs to be done? So, especially, how do you find one? $ N $?


The rules of inference I had in mind are any standard semantics of IMP: