Introduction

We want to do some calculations on a remote server. The server lets us send expressions to evaluate, one at a time, but doesn’t let us define variables or functions because that would use up memory, a Denial-of-Service Attack.
For example, we want to compute the factorial of a number, say 6, but the server doesn't have a built-in for factorial. We'd like to send the standard recursive definition
In[]:=
fact[n_]:=If[n<1,1,nfact[n-1]]
then, call it like this:
In[]:=
fact[6]
Out[]=
720
But that’s two shots, and we only get one shot. We can’t define fact, using up memory in the server’s symbol table, and then use it on the next shot.
Are we out of luck? No. In fact, The following does the trick, as this article explains:
In[]:=
(d(gg@g)[sfd[msf[sf]@m]])[​​fnIf[n<1,1,nf[n-1]]]@6
Out[]=
720
We’ll show how to convert any recursive function into an anonymous version of itself. Furthermore, to sweeten the deal, we’ll show how to convert expensive anonymous recursive functions into cheap anonymous recursive functions. We’ll do it in Mathematica and talk about doing it in Scheme and Python (Python version here https://github.com/rebcabin/rebcabin.github.io/blob/main/PythonYCombinators.ipynb). Along the way, we’ll uncover deep and lovely secrets about Mathematica programming, secrets that make it my favorite programming language.

Anonymous Functions

We already know how to define functions that don’t have names: lambda expressions. Mathematica has a concise notation via esc-fn-esc. Here is a lambda expression in shorthand, one that computes its argument, x, times (x+1), its argument plus one:
In[]:=
xx*(x+1)
Out[]=
Function[x,x(x+1)]

Notation

That is a lambda expression of one argument, namely x. Read it as “the function of
x
that produces
x
times
(x+1)
, or
x(x+1)
.” The star for multiplication is optional in Mathematica, so you can write x*(x+1) as x(x+1). In Scheme or Python, you must write the star.
We know how to apply such a lambda expression to an actual argument, say, to 6: wrap the lambda expression in parentheses and follow it with an @ sign:
In[]:=
(xx(x+1))@6
Out[]=
42
Or, write the function application with square brackets like this:
In[]:=
(xx(x+1))[6]
Out[]=
42
The meaning is exactly the same. x@y means the same as x[y], no matter what x and y mean. We choose one or the other at will to satisfy subjective aesthetics.
In the following, Script letters like , ℰ, ℱ, ℒ, and , are notional names: non-denotable names, names we can’t write in our programming language, but names of denotable things we need to think about and don’t want to keep writing out verbatim over and over again. For example, we’ll see the following symbol-blizzard over and over again:
d(gg@g)[sfd[msf[sf]@m]]
That’s a literal, denotable expression that we’ll send to our server as part of other expressions. But it’s too much to look at while thinking, so we’ll just call it  for the sake of discussion. In fact, explaining that expression is the whole point of this article. It’s a gadget that makes anonymous recursive functions and passes them into domain code for application; twisty!

Recursion as Squaring the Square Root

It turns out we can evaluate anonymous recursive functions in one shot. We’ll do it by taking the square root
ℱ
of the function ℱ that we want, in a notional space where squaring the square root
ℱ
is applying
ℱ
to itself.
For example, we want fact, but the server doesn’t let us define the name fact. But the server does let us define temporary names that go away in one shot. Those names are the formal parameters of lambda expressions. So if we can define
fact
and then apply it to itself — square it — we get the same effect as fact.
More generally, for any function ℱ, pass
ℱ
as an actual argument to
ℱ
. When
ℱ
is invoked, bind the actual argument
ℱ
to the parameter sf. In the body of
ℱ
, refer to ℱ by the expression sf[sf]
=
ℱ

ℱ
=
2

ℱ

=ℱ
; square the square root
ℱ
to get the recursive function ℱ that we want. What a great trick!

Is this a Joke?

How did we get from applying a function to itself
ℱ

ℱ

to squaring a function
2

ℱ

? It’s a pun, but not a joke! In the world of functions at large, linear functions are very, very important and special. Applying a linear function
f
to an argument
g
is multiplication, often matrix multiplication, seen everywhere.
f(g)=fg
. This pun is so powerful that a whole programming language, Haskell, writes all function applications, linear or not, without parentheses, as if function application were always multiplication. It’s not, be we always wish it were.

The Square Root of Factorial

Turns out we can easily compute
ℱ
for any function ℱ. We do fact as an example, first, then generalize.
To get the square root
ℱ
of factorial ℱ, just assume it exists and has a name, sf, in the only allowed place for named entities, as the parameter of an anonymous lambda expression. Let the return value of
sf=
ℱ
be the function of
n
that computes factorial. How? By invoking sf[sf], the square — the self-application — of sf, in the recursive position where we call ℱ on
n-1
. What is the value of sf? Just
ℱ
! So
ℱ

ℱ

must be factorial, and we can apply it to numerical arguments, here 6:
In[]:=
((sfnIf[n<1,1,nsf[sf][n-1]])@​​(sfnIf[n<1,1,nsf[sf][n-1]]))@6
Out[]=
720
Before the final actual argument, 6, and its application symbol, @, there is a lambda expression of one parameter sf applied to a cut-and-paste copy of its whole self via another application symbol @ on the first line. sf is a function of itself, sf, that returns a function of
n
. Applying sf to sf squares the function
ℱ
. Inside the If[...] part, we see another self application, sf[sf], applied to a numerical argument, sf[sf][n-1]. So we see that the external squaring, ((sf...)@(sf...)) produces the same result as the internal squaring sf[sf]. The external squaring is applied to the application argument, 6 in this case.
This is enough. Stop here if all you care about is a programming pattern for anonymous, remotable, recursive functions: just replace the body of the function, namely the If[...] part, in both places where it occurs, with the body of your desired recursive function, and call your function recursively via the self-application syntax sf[sf]. We’ll show another example, fib, later.
However, there are worthwhile improvements, particularly to remove copy-paste repetition, an opportunity for error when sf gets big. We can write a general function  that squares the square root of any function ℱ.

Two Abstractions, One Model, and Packaging

To refresh the main idea: we have a square root
ℱ
, that, when squared, produces the recursive domain function ℱ of the domain parameters; ℱ does the real work we want.
Let’s make a combinator (a function of a function) that can convert any function into a new function that receives its self application, the recursive function f=sf[sf], as its first argument. This is a twist on the prior development. We want sf[sf] as the value of the first parameter f. We want to write ((...)[fn...])@6 in our example, with f as the domain function sf[sf] and n as the domain parameter. We must solve for (...).
Solve in two steps: first, start with the prior development, in which sf is the parameter in a cut-and-paste squaring of
ℱ
. Inside the domain code — inside
ℱ
— replace the square sf[sf] by the parameter f of a new anonymous function of f. Apply the new anonymous function of f to the actual argument sf[sf].
That’s what abstraction means in general: replacing an expression ℰ with a parameter e of a new anonymous function, then applying that new function to ℰ as an actual argument, which becomes the value of the parameter e.
In the second step, abstract the domain code into a parameter d of the final, general combinator , so that we write the domain code only once.
Here are all the improvements, spelled out for factorial:

Step 1: Abstract the Internal Self-Application

Looking at the body of
ℱ
, namely the If[...] part of
sfnIf[n<1,1,nsf[sf][n-1]],
the first task is to abstract the internal self-application sf[sf] into a parameter f of a new abstracted function of f applied to sf[sf] (or to sf@sf, same thing). This is exactly as we had before, only with f standing in for sf[sf].
sf((fnIf[n<1,1,nf[n-1]])[sf@sf]),
The fragment highlighted in yellow, below, is the new abstracted function of f. However, this new abstraction blows up — fails to terminate — even before it is applied to a numerical argument:
In[]:=
(sf((fnIf[n<1,1,nf[n-1]])[sf@sf]))@(*sfisstillinscope!*)​​(sf((fnIf[n<1,1,nf[n-1]])[sf@sf])(*sfisstillinscope!*));
$RecursionLimit
:Recursion depth of 1024 exceeded.
Why? Let’s calculate. Let sℱ, notionally, stand for this function of sf that binds sf@sf to the parameter f:
ℱ=(sf((fnIf[n<1,1,nf[n-1]])[sf@sf]))
Out[]=
Function[sf,Function[f,Function[n,If[n<1,1,nf[n-1]]]][sf[sf]]]
Apply sℱ — this function of sf — to a copy of itself exactly as before:
In[]:=
ℱ@ℱ;
$RecursionLimit
:Recursion depth of 1024 exceeded.
This can’t work. The argument in the application ((f...)[sf@sf]), namely sf@sf, is evaluated to sℱ@sℱ, via the value of sf as copy-paste code, before being bound to f, but there we go evaluating sf@sf in the pasted copy again before knowing what it is! Evaluating arguments before binding them is called applicative-order evaluation or call-by-value. It’s the norm in practical programming languages like Mathematica, C, Scheme, Python, Lisp, and most things we’re familiar with, and it’s too early for this job.
◼
  • Aside: An alternative is called normal-order evaluation or call-by-name, but we can’t have it directly without support from the programming language.
    • This unbounded recursion has nothing to do with the computation If[n<1,1,n*f[n-1]] inside (f...), we never get there. The following blows up with the computation removed and replaced by a constant return value.
    In[]:=
    (sf(f0)[sf@sf])@(sf(f0)[sf@sf]);
    $RecursionLimit
    :Recursion depth of 1024 exceeded.

    Delay the Squaring

    We can delay evaluation of sf[sf] by redefining ℱ to apply, instead of f, yet another anonymous function:
    In[]:=
    msf[sf]@m
    Out[]=
    Function[m,sf[sf][m]]
    to the numerical argument, as follows
    In[]:=
    (sfnIf[n<1,1,n*(msf[sf]@m)[n-1]]);
    We’ve temporarily lost the abstraction of sf[sf] into f, but gained a delayed evaluation of sf[sf]. We’ll get f back in a minute.
    msf[sf]@m always has the same value as sf[sf] when applied to any argument. The two expressions just evaluate sf@sf at different times. In the first case, sf@sf is evaluated later when msf[sf]@m is applied to the actual argument n, substituting the value of n for the parameter m.
    ◼
  • This is a general technique for delaying the application of any function: replace the application with a function of some (any) parameter, the new function getting evaluated at the correct time.
    • ◼
  • In lazy languages like Haskell, this step is automatic and implicit — we don’t write it — because evaluation of all expressions is always delayed.
    • Let’s back off and write our very first original self-application with msf[sf][m] manually in place of f.
    In[]:=
    (sfnIf[n<1,1,n(msf[sf]@m)[n-1]])[​​sfnIf[n<1,1,n(msf[sf]@m)[n-1]]]@6
    Out[]=
    720
    Now, as before, abstract msf[sf]@m, merely a delayed version of sf[sf], into a parameter f of a new lambda:
    In[]:=
    (sf(fnIf[n<1,1,nf[n-1]])[msf[sf]@m])[​​sf(fnIf[n<1,1,nf[n-1]])[msf[sf]@m]]@6
    Out[]=
    720
    the result does not spin forever because evaluation of sf[sf] is delayed until needed on the argument n==6.

    Step 2: Abstract the Domain Code

    The abstraction on f now completely and minimally encloses the domain code
     =fnIf[n<1,1,n f[n-1]].
    Abstract that:
    1. Write a new function (d...) of a parameter d for domain code
    2. ... with a body that replaces application of the old function of f to the delayed square of sf
    ​(f...)[m...], with an application of d to the same argument, d[m...]
    3. Apply that new function (d...) to the old function of f: (d...)[f...]
    We get a big benefit: we only write the domain code once, and that’s a big deal, especially if it’s big and complicated. Don’t Repeat Yourself is a general principle in software engineering. It saves pitfalls now, during development, and later, during maintenance.

    Step 3: Model the Self-Application

    with an application of gg@g to sf[msf[sf]m]:

    Demonstrate the Generality

    Try out the outer combinator — which always stays the same — on some new domain code, which we only write once:

    Step 4: Packaging as a Combinator

    Package the outer combinator as a notional function . Its only argument is the domain code!
    and test on our two examples

    Step 5: More Arguments

    Because we have a good grip on how  works, we can write the two-argument version straightaway, without a hiccup! Functions of two arguments are invoked in Curried fashion, one argument at a time, as in f[a][b] rather than f[a,b]. Such Currying makes it trivial to extend  to any number of arguments.
    My made-up function explodes rapidly. The following are the only results on positive-integer inputs that don’t overflow Mathematica’s recursion limits.
    That' s a nice segue into ...

    Memoizing [sic]

    A downside of recursive functions is that they are often expensive. That “different famous recursive function” mentioned above is Fibonacci, a schoolbook case of exponential complexity, certainly a Denial-of-Service attack both on stack space and on computation time. Calling our anonymous version of Fibonacci on 27 feels really slow (more than 2 seconds), and exponentially slower for bigger arguments: 10 seconds on 30 and a couple of minutes on 35. Don’t try it on 40, it might not finish in your lifetime.
    Our paranoid evaluation server has a time limit of a quarter of a second or so and would kill our jobs.
    Are we out of luck for recursive functions? NO!
    If our evaluator lets us define temporary symbols, and it always does so as function parameters, and if the built-ins give us hash tables, dictionaries, association lists, or some such, we can build tables of intermediate values and avoid recursive calls. This, also, is a general technique, the simplest instance of dynamic programming, and it’s called memoization [sic, not memorization].
    Mathematica automatically has a hash table, DownValues, for every symbol. So memoizing Fibonacci is nearly trivial, if we can name it:
    Orders of magnitude faster, linear instead of exponential, just by saving intermediate values onto the DownValues hash-table via mfib[n] = ...
    The expressions m[n-1] and m[n-2] then become table lookups instead of recursive calls almost all the time. Wolfram perhaps foresaw this in 1980 when he designed Mathematica to use the same notation [] for table lookup in DownValues as for function-call. Actually, it’s inherent in the term-rewriting method of Mathematica, but it’s brilliant, however it was conceived, even if only by accident.
    We can’t easily exploit Mathematica’s DownValues: function parameters don’t have them. Even so, it doesn’t port easily to non-symbolic programming languages like Python. Instead, we’ll use Mathematica’s Association, which is like Python’s dictionary.
    The idea for linearizing the exponential process of Fibonacci by memoizing is as follows:
    1
    .
    Factor our domain code d to do “lookup,” check-or-install a given key-value pair in an Association. Use it twice, that’s why we want to name it rather than write it out verbatim twice.
    3
    .
    Check the association before recursively calling; this is the critical step for avoiding exponential run time.
    4
    .
    Incrementally add new key-values pairs to the association before returning it to recursive calls already on the stack.
    We’ll use Mathematica’s Module to save keyboarding. Module allocates local variables. In an ordinary language like Scheme, we’d use let to allocate temporary variables. Let is 100% equivalent to Scheme lambda applied to arguments, where the symbolic parameter of the lambda is the temporary. In Mathematica, Module is likewise equivalent to a lambda applied to arguments, but only when the parameters are not mutated. That’s because Mathematica is actually a term-
    rewriter instead of an applicative-order-evaluator. Mathematica feels free to throw away parameters, replacing them with values. Function parameters are not first-class, mutable symbols in Mathematica; they’re pattern variables. The distinction between mutable symbols and pattern variables has many profound benefits, to many and too deep to go into here. Let us just say that distinction is syntactic in Mathematica and one of the reasons I prefer Mathematica to Scheme and Haskell.
    We want to mutate the values to avoid grotesque argument threading. We trust we could do this entire thing with only lambdas and no Modules, but it would be longer and not instructive.
    Here is memoized Fibonacci applied to 400. Without memoization, this computation would not complete in 15 billion years. Here, it takes 35 milliseconds.
    Finally, just to show that we could eliminate at least the outer Module, is an equivalent expression:

    CITE THIS NOTEBOOK

    Squaring the Square Root of a Function (Y Combinator Revisited)​
    by Brian Beckman​
    Wolfram Community, STAFF PICKS, February 20, 2024
    ​https://community.wolfram.com/groups/-/m/t/3127112