= Solution
Add the <abstract syntax tree> alternative `Fix Ident Expr`. Its <syntactic sugar> expansion and the semantic equations from part (a) give
$$
\begin{aligned}
\operatorname{eval}(\operatorname{Fix}\ x\ e)\,\rho
&=\operatorname{eval}(\operatorname{Let}\ (\operatorname{Rec}\ x\ e)\ (\operatorname{Variable}\ x))\,\rho\\
&=\operatorname{defn}(\operatorname{Rec}\ x\ e)\,\rho
\triangleright(\lambda\rho'.\,\operatorname{result}(\operatorname{lookupEnv}(\rho',x)))\\
&=\operatorname{result}(\rho^*)
\triangleright(\lambda\rho'.\,\operatorname{result}(\operatorname{lookupEnv}(\rho',x)))\\
&=\operatorname{result}(v),
\end{aligned}
$$
where $\rho^*=\operatorname{extend}(\rho,[(x,v)])$ and $v=\operatorname{close}(e,\rho^*)$. The final step uses left identity from the <monad laws> and the lookup rule for the newly bound identifier.
Thus a direct evaluator equation is:
``
eval (Fix x e@(Lambda xs body)) rho = result v
where
rho' = extend rho [(x,v)]
v = close e rho'
``
Equivalently, spelling out <programming closure> construction,
$$
\boxed{\operatorname{eval}(\operatorname{Fix}\ x\ (\operatorname{Lambda}\ xs\ b))\,\rho
=\operatorname{result}(v),\quad
v=\operatorname{Function}\bigl(\lambda args.\,
\operatorname{eval}(b)(\operatorname{extend}(\rho^*,\operatorname{zip}(xs,args)))\bigr).}
$$
The result is a <recursive closure>, not the result of calling its body. Its self-binding is visible inside that body but does not extend the caller's surrounding <semantic environment>.
Back to article page
