An Operational Account of Call-by-Value Minimal and Classical λ-Calculus in “Natural Deduction” Form

We give a decomposition of the equational theory of call-by-value

λ

-calculus into a confluent rewrite system made of three independent subsystems that refines Moggi’s computational calculus:

the

purely operational system

essentially contains Plotkin’s

β

v

rule and is necessary and sufficient for the evaluation of closed terms;

the

structural system

contains commutation rules that are necessary and sufficient for the reduction of all “computational” redexes of a term, in a sense that we define;

the

observational system

contains rules that have no proper computational content but are necessary to characterize the valid observational equations on finite normal forms.

We extend this analysis to the case of

λ

-calculus with control and provide with the first presentation as a confluent rewrite system of Sabry-Felleisen and Hofmann’s equational theory of

λ

-calculus with control.

Incidentally, we give an alternative definition of standardization in call-by-value

λ

-calculus that, unlike Plotkin’s original definition, prolongs weak head reduction in an unambiguous way.