I have been trying to avoid implementing continuations in the small-step interpreter, and just... ugh. It's really been such a headache. Currently, it means a single "step" can occasionally take multiple steps. Then the rules in the rule-list get out of order, and I feel that I shouldn't have to re-order them.
The solution is what you knew from the beginning: use continuations instead of immediately reducing sub-expressions.
A traditional implementation might separate continuations from code and environment. However, we can incorporate the continuations directly into the code semantics by creating a continuation type (denoted with kappa, of course) and returning that. I think it is the case that any such value will always be reducible, so it won't be necessary to handle as an error. A simple implementation would probably just be a single-argument function that produces the desired code expression.
I have been trying to avoid implementing continuations in the small-step interpreter, and just... ugh. It's really been such a headache. Currently, it means a single "step" can occasionally take multiple steps. Then the rules in the rule-list get out of order, and I feel that I shouldn't have to re-order them.
The solution is what you knew from the beginning: use continuations instead of immediately reducing sub-expressions.
A traditional implementation might separate continuations from code and environment. However, we can incorporate the continuations directly into the code semantics by creating a continuation type (denoted with kappa, of course) and returning that. I think it is the case that any such value will always be reducible, so it won't be necessary to handle as an error. A simple implementation would probably just be a single-argument function that produces the desired code expression.