4
$\begingroup$

Can't solve this task:

Let there be a mutually recursive definition of the terms ${foo}$ and ${bar}$. In general, it can be written as $$ {foo} = P {foo} {bar} $$ $$ {bar} = Q {foo} {bar} $$ Here $P$ and $Q$ are some terms that contain neither ${foo}$ nor ${bar}$. Using the $Y$-combinator, find nonrecursive definitions for ${foo}$ and ${bar}$. Try to find the most "compact" solution, with the smallest number of $Y$-combinators possible

My attempts

  1. I tried to explicitly write $foobar = PfoobarQfoobar$, but it didn't work.
  2. I tried to start an auxiliary $bar'=\lambda f.Qf(bar'f)$, and through it get a nonrecursive form with $Y$ combinator.
  3. I tried to find the dependence by explicitly describing $foo=Pfoobar=PPfoobarbar=...=P...Pfoobar...bar$.
$\endgroup$
2
  • $\begingroup$ Are you interpreting the 1st one as $foo=((P\text{ }foo)(bar))$? $\endgroup$
    – Soham Saha
    Feb 26 at 13:13
  • 1
    $\begingroup$ @SohamSaha Yes. $\endgroup$
    – replikeit
    Feb 26 at 13:40

2 Answers 2

3
$\begingroup$

Mutual recursion can always be merged. If $f,g$ are mutually recursive, then define a third function $h = \lambda x. x f g$. Now you can express $f = h (\lambda p q. p)$ (Exercise: express $g$), and write a recursive equation using $h$ alone.


Another way to solve this is to solve for $f$ assuming you already know $g$. This gives you an expression $f = \dots g\dots$. Now substitute this into the equation for $g$ and you get a recursive equation for $g$ alone, which you can solve using Y.

$\endgroup$
1
  • $\begingroup$ Do you talking something like this: for $foo$ -- $hP = f$ and $f = h(\lambda p q. p)$; for $bar$ -- $hQ = g$ and $g = h(\lambda p q. q)$ $\endgroup$
    – replikeit
    Feb 26 at 17:02
2
$\begingroup$

Disclaimer: I have been reading about lambda calculus and combinatory logic only for some months. But I think that I have an idea for this question. If you find any problems, please comment.

$$\begin{align*} \text{foo} &= \text{P foo bar}\\ &=\text{P foo (Q foo bar)}\\ &=\text{P foo (Q foo (Q foo (...)))}\\ &=\text{P foo (Y (Q foo))}\\ &=\text{P foo (S (K Y) Q foo)}\\ &=\text{S P (S (K Y) Q) foo}\\ &=\text{Y (S P (S (K Y) Q))} \end{align*}$$

Similarly we can extract a definition for $\text{bar}$

$\endgroup$
5
  • $\begingroup$ $\text{P foo (Y (Q foo))}$ why we cant take outside foo at this step? like: $\text{P foo (Y (Q foo))}=(\lambda f. \text{P f (Y (Q f))) foo}$. $\endgroup$
    – replikeit
    Feb 26 at 15:53
  • $\begingroup$ @replikeit of course we can, but I thought that the situation demanded a purely CL-type solution. If your context permits you to mix combinators with lambda calculus, I don’t think there should be any problem. But I am not experienced enough to know if that is admitted as good practice or not. $\endgroup$
    – Soham Saha
    Feb 26 at 16:14
  • $\begingroup$ Actually I had done it that way too, but changed it to combinatorial format at the end. $\endgroup$
    – Soham Saha
    Feb 26 at 16:14
  • $\begingroup$ Then this is right solution. Thank you. $\endgroup$
    – replikeit
    Feb 26 at 16:15
  • 1
    $\begingroup$ You’re welcome :) @replikeit $\endgroup$
    – Soham Saha
    Feb 26 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .