Refocusing (semantics)

Article summary

In computer science, refocusing is a program transformation used to implement a reduction semantics—i.e., a small-step operational semantics with an explicit representation of the reduction context—more efficiently. It is a step towards implementing a deterministic semantics as a deterministic abstract machine. A small-step operational semantics defines the meaning of a given program p_0 as a sequence of one-step reductions that starts with p_0 and continues with a sequence of reducts p_i , where i > 0 : p_0 \rightarrow p_1 \rightarrow p_2 \rightarrow \cdots A one-step reduction from p_n to p_{n+1} is achieved by # locating the smallest potentially reducible term (potential redex) using a given reduction strategy, if this potential redex exists in p_n (otherwise p_n is irreducible); and # contracting this potential redex using given contraction rules if it is an actual one (otherwise p_n is stuck). A reduction semantics is a small-step operational semantics with an explicit representation of the context of each potential redex.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.