Ciobaca: From Small-Step Semantics to Big-Step Semantics, Automatically

describes how to go from small-step to big-step semantics.

I need to do the other way around: from big-step to small-step. Is there literature for this? What should I be careful of?

EXTENSION: I have a big-step operational semantics for a functional language and for my purposes I need to write a small-step operational semantics for it. Can you point to relevant scientific literature on how I should do this, what are the pitfalls?

  • 1
    $\begingroup$ Going from big-steps to small-steps is known as "the Art of Programming", IMO. $\endgroup$
    – user16034
    Commented Feb 21, 2022 at 15:15
  • $\begingroup$ Please edit your question to expand a bit more on what you mean by "go from big-step to small-step semantics". $\endgroup$
    – D.W.
    Commented Feb 21, 2022 at 17:20

1 Answer 1


Here are a couple articles on the matter.

From Big-Step to Small-Step Semantics and Back with Interpreter Specialisation and Automatic Transformation of a Big-Step Skeletal Semantics into Small-Step

Also, if you need to write your own semantics for a functionnal language, you should have a look at pcf's semantics, for example here. If you feel adventurous, start with a semantics for the lambda calculus and go your own way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.