Skip to main content
1 of 4
Andrej Bauer
  • 31.2k
  • 1
  • 73
  • 119

You can get an important hint from thinking about how to make the yin-yang puzzle work in a typed language, see this question. OCaml computes the type of yin and yang to be ('a -> 'a) as 'a, which is a recursive type equal to its own function space. Such a type is precisely what it takes to implement the untyped $\lambda$-calculus in a typed language.

What does this have to do with your question? In the untyped $\lambda$-calculus (or typed calculus with general recursive types) we can define $\mu$ and other fixed-point combinators. So, since yin and yang cannot be given types, we must use the untyped $\lambda$-calculus, but then $\mu$ is not needed as a primitive. In fact, the CPS transform of the puzzle will be just pure $\lambda$-calculus.

You can compute the CPS transform in the privacy of your mind. I do not have the time right now, but will come back to complete the answer. The morale is that you should be able to do this just with $\lambda$-calculus.

Andrej Bauer
  • 31.2k
  • 1
  • 73
  • 119