21
$\begingroup$

A friend showed me this snippet of code today:

(#[#] &)[#[#][#] &]

I can sort of see that we're constructing an anonymous function that takes a function as an argument and calls that function passing it itself. Then we're calling that anonymous function, passing another, and I get lost...

A cogent explanation of this code would be great.

Apologies if this is well known, I tried to google for it, but its nature makes searching for it hard.

$\endgroup$
3
  • 2
    $\begingroup$ Maybe a rewrite in explicit Function[] form is more enlightening: Function[f, f[f]][Function[f, f[f][f]]]. Or, in another form: Function[f, f[f]] @ Function[f, f[f][f]]. $\endgroup$ Feb 9, 2012 at 3:46
  • 1
    $\begingroup$ $RecursionLimit::reclim: Recursion depth of 256 exceeded. - This snippet is nonsense. $\endgroup$
    – David
    Feb 9, 2012 at 3:55
  • 6
    $\begingroup$ Yes, it's a headache-generating function. $\endgroup$
    – Cassini
    Feb 9, 2012 at 11:24

3 Answers 3

36
$\begingroup$

Going out on a limb here, but the exhibited expression looks like a brave but flawed attempt to implement the Y-combinator extremely concisely.

The Y-combinator is a technical trick used to implement recursion in the lambda calculus. Here is an implementation that stoops to using some symbols:

Y[f_] := #[#]&[Function[n, f[#[#]][n]]&]

... and here is an example of its use to calculate factorials recursively:

fac[r_] := If[# < 2, 1, # * r[# - 1]]&

Y[fac][10]

3628800

Of course, in Mathematica there is no need to engage in such gymnastics since explicit recursion is supported directly. But it is a nice brain-teaser: can Y be expressed using no symbols? (Ideally using nothing other than special input form #, the postfix operator &, the matchfix operator [...] and parentheses -- just like the original expression.)

The Obscurity Continues

Since we are exploring obscure corners of Mathematica function syntax, here is another version of the Y-combinator that uses the rarely seen \[Function], an infix operator for function definition (keyboard shortcut: ESCfnESC):

Y = f ↦ (g ↦ g[g])[h ↦ n ↦ f[h[h]][n]]

(* but copy this instead to get the correct Mathematica character:
ClearAll[Y]
Y = f \[Function] (g \[Function] g[g])[h \[Function] n \[Function] f[h[h]][n]]
*)
$\endgroup$
6
  • 1
    $\begingroup$ ...but Slot[] (#, that is) is a symbol. Maybe you mean to say that you want an expression for Y that is just composed of Slot[]s and Function[]s? On that note, this is related. $\endgroup$ Feb 10, 2012 at 0:27
  • $\begingroup$ @J.M. Indeed, that is my meaning. $\endgroup$
    – WReach
    Feb 10, 2012 at 0:36
  • 1
    $\begingroup$ I've written some "perverse" code myself, but that's just evil! (read: I'm still trying to wrap my head around what this does) $\endgroup$
    – Mr.Wizard
    Feb 11, 2012 at 11:13
  • $\begingroup$ @WReach it's really hard to find examples of \Function on MMA.SSE - could you edit your (excellent!) answer for people to find this more easily to include the phrase "infix operator" or similar? $\endgroup$ Feb 24, 2015 at 11:38
  • 1
    $\begingroup$ @MartinJohnHadley I added the phrase "infix operator for function definition", along with a link to the documentation page. $\endgroup$
    – WReach
    Feb 24, 2015 at 15:25
20
$\begingroup$
(#[#] &)[#[#][#] &]

You have a function that applies its argument to itself

(#[#] &)[8] --> 8[8]

We have, on the other hand, a function that applies to itself to make the head it applies to itself

(#[#][#]&)[8] --> (8[8])[8]

8[8] is the head of 8[8][8]

If we apply the first function to the second one, we get the second function applied to the second function. We then evaluate that and get the second function applied to the second function as a head, with argument the second function... Then you expand the head again, and you got a terrible infinite recursion. As David said in the comment, nonsense snippet of code.

$\endgroup$
1
  • $\begingroup$ Great explanation. I appreciate your help. TIL what a head is. $\endgroup$
    – Harold
    Feb 9, 2012 at 4:27
9
$\begingroup$

Here's what it looks like if we limit the recursion level to something smaller:

Block[{$RecursionLimit = 20}, 
 Function[f, f[f]][Function[g, g[g][g]]]]

(* 
   $RecursionLimit::reclim :  "Recursion depth of 20 exceeded.

   $RecursionLimit::reclim :  "Recursion depth of 20 exceeded.
*)

(*
==> Hold[Function[g, g[g][g]][Function[g, g[g][g]]]][
                  Hold[Function[g, g[g][g]]]][Function[g, g[g][g]]][
                Function[g, g[g][g]]][Function[g, g[g][g]]][
              Function[g, g[g][g]]][Function[g, g[g][g]]][
            Function[g, g[g][g]]][Function[g, g[g][g]]][
          Function[g, g[g][g]]][Function[g, g[g][g]]][
        Function[g, g[g][g]]][Function[g, g[g][g]]][
      Function[g, g[g][g]]][Function[g, g[g][g]]][
    Function[g, g[g][g]]][Function[g, g[g][g]]][Function[g, g[g][g]]][
 Function[g, g[g][g]]]
*)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.