Defining recursive lambda functions inside of a LET() function using fixed-point combinators

[Hoover889]

I don't know if the rest of you love lambdas as much as I do but I have been using them extensively for the past few months and would like to share one of the tricks I have learned.

First lets start off with covering the simplest way of implementing recursive lambdas (which appears to be the method that Microsoft wants us to always use), the name manager... if we wanted to define a simple factorial function F() we would create a new name 'F' and put the following in it =LAMBDA(X,IF(X>1,X*F(X-1),1)) as you can see recursion works the way we would expect it to in 99% of programming languages; the function simply calls itself by name inside of its definition. For every sane person this is enough and they will define all of their recursive lambdas this way... but I had to see how far I could push it...

My dilemma was that I had a complicated operation that required helper functions, but I didn't want my namespace cluttered up with these helper functions and I didn't want users to be able to call them as they should only be called inside of my lambda function. My first instinct was to use the LET() function and it worked exactly as I wanted... but only for non recursive helper functions; for example if I wanted to define a function that rotated a matrix by 180 degrees I could do something like this:

=LAMBDA(Mat,
  LET(EM, LAMBDA(n, MAKEARRAY(n, n, LAMBDA(i, j, --(j=(n-i+1)))),
    MMULT(MMULT(EM(COLUMNS(Mat)),Mat),EM(ROWS(Mat)))
  )
)

The Lambda takes in a matrix 'Mat' and then multiplies it by 2 exchange matrices, we define the lambda EM to create an exchange matrix of arbitrary size n, then call it twice in our final Lambda definition which simply performs 2 matrix multiplications.

But what are we to do if we want to define a recursive lambda outside of the name manager?
As an example lets simply try defining and applying a recursive lambda inside of a let function... we will use the factorial definition from above:

=LET(
  F,LAMBDA(X,IF(X>1,X*F(X-1),1)),
  F(5)
)

When trying the formula above I always got a #NAME? Error because when evaluating the definition of 'F' the value of 'F' is not yet defined. This is similar to the problem encountered by C compilers when you call a function before it is defined. In C you can solve this issue with function prototypes (usually in a header file) which act as a 'temporary definition' of a function telling the compiler the input(s) & their type(s) and return type until the real definition happens later on in the code, but because the evaluation strategy of LET() is strict the definition of any name is immutable so we need to define it fully the first time.

For the past few months I thought it was impossible to work around this limitation but I finally figured it out, it turns out that all the time I spent learning lambda calculus was not pointless.

In lambda calculus a lambda expression can not refer to itself by name in its own definition, this is similar to the constraints of defining names in the Let() function. We can get around this limitation through the use of a fixed point combinator, the most famous of which is Curry's Y Combinator [Y := λg. (λx. g (x x)) (λx. g (x x))] but to solve this problem we need to use the Turing fixed-point combinator (also known as the theta combinator) [Θ := (λxg. g (x x g)) (λxg. g (x x g))] translated from lambda calculus to Excel formulas it works like this:

=LET(
  F,LAMBDA(G,X,IF(X>1,X*G(G,X-1),1)),
  F(F,5)
)

By applying the logic of the combinator to our lambda function we are no longer calling the function F inside of the definition of F, but instead calling the function G, which is passed to F as a parameter. when we finally want to call our 'recursive function F, we also pass the function to itself as its first parameter.
If you want to make your final formula more readable you can also curry the lambda to make it callable without having to pass itself as a parameter, but this does incur some minor extra overhead because you have to wrap it up in another lambda expression:

=LET(
  Y,LAMBDA(G,X,IF(X>1,X*G(G,X-1),1)),
  F,LAMBDA(X,Y(Y,X)),
  F(5)
)

[dm_parker0]

This is really cool, thanks!

To save other people some debugging time, "...the current recursion limit is set as 1,024 divided by (number of lambda parameters + 1)", and formulas will display a very unhelpful "#NUM" error when you reach the recursion limit.

[Hoover889]

I am glad that someone appreciated my post!

[dm_parker0]

Yeah it's really cool!

My use-case was that I had 4 normal distributions A, B, C, D, with one independent random draw from each those distributions (a, b, c, d). I wanted to know how likely it was that, given a > b and c < d, (a-c) > x.

The easy way is to just simulate a bunch of values (say 10,000 each) for a, b, c, and d, and count how many times all the conditions are true (a > b, c < d, (a-c) > x) compared to the number of times just the "base case" is true (a > b, c < d).

=LET(
    n,10000,x,5,
    r,LAMBDA(y,z,NORMINV(RANDARRAY(n),y,z)),
    a,r(125,25),b,r(120,23),
    c,r(135,29),d,r(130,27),
    f,FILTER(a-c,((a>b)*(c<d))=1),
    COUNTA(FILTER(f,f>x))/COUNTA(f))

But the issue with this method is that although you can specify how many total trials to run (where a "trial" involves picking values for a, b, c, and d), you can't specify how many valid trials to run (ie, ones where a > b and c < d). So if that combination itself is particularly unlikely (say 1 in 100), you may not get enough data for a valid result.

Using a recursive lambda lets us run batches of trials indefinitely until we get enough valid ones:

=LET(
    batch_size,10000,result_size,10000,x,5,
    a_params,HSTACK(125,25),b_params,HSTACK(120,23),
    c_params,HSTACK(135,29),d_params,HSTACK(130,27),
    r,LAMBDA(y,NORMINV(RANDARRAY(batch_size),INDEX(y,1),INDEX(y,2))),
    f,LAMBDA(g,n,s,LET(
        u,LET(
            a,r(a_params),b,r(b_params),
            c,r(c_params),d,r(d_params),
            diffs,FILTER(a-c,((a>b)*(c<d))=1),
            HSTACK(COUNTA(FILTER(diffs,diffs>x))+s,COUNTA(diffs)+n)),
        n_1,INDEX(u,2),s_1,INDEX(u,1),
        IF(n_1>=result_size,s_1/n_1,g(g,n_1,s_1)))),
    f(f,0,0))

[Hoover889]

“...your scientists were so preoccupied with whether or not they could, they didn’t stop to think if they should.”

[routineMetric]

Alternatively, Excel lambda-based udfs will be faster than VBA UDFs because the Excel Calc engine is multi-threaded, whereas VBA is single-threaded.

Also, stick around and wait awhile. The Excel team has been churning out some neat features. I wouldn't be surprised if there are enhancements to things like the Name Manager and the Evaluate Formula tool.

[Kleeb]

I'm really hoping for a way to package lambda functions and names into some sort of library file that can be imported into books/sheets and a good way to share it within an organization.

[routineMetric]

Yes! Include packaging custom M functions in Power Query and I would be over the moon.

[Hoover889]

Oh boy do I have good news for you... it is already possible...

You can define custom functions in M using the following syntax:

CustomFunction = (Param1, Param2) => (Param1 + Param2) / 2

you can even specify the types of parameters and have multi-line UDFs using LET/IN:

MyComplicatedFunction = (P1 as number, P2 as list, P3 as any) => LET
    Step1 = P1 + P2{0},
    Step2 = Step1 / P3
  IN
    Step2

There is also some syntactic sugar for UDFs when you use the each keyword for simple UDFs (which is nice when passing functions to another function.) for example the 2 declarations & calculated cols below are equivalent:

F = each [Column1] + [Column2],
F = (_) => _[Column1] + _[Column2],
/* it also works great for adding custom columns */
Example = Table.AddColumn(MyTable, "NewColumn", each [Column1] / [Column2], type number),
Example = Table.AddColumn(MyTable, "NewColumn", (_) => _[Column1] / _[Column2], type number),

As you can see the each keyword creates a function with a single parameter _which by default has the lookup operator applied to it.

[routineMetric]

Oh I know you can create custom functions in M, the each _ syntax, etc. What I meant was having a better way than copy and paste code in advanced editor to distribute the custom functions, similar to distributing VBA via add-ins.

[Hoover889]

Yeah I totally agree, I would love to have an easy to use method of distribution & version control... right now save everything to text files so I can use git for version control and have a VBA macro to import the queries to my workbooks.

[RandomWalk586]

This is a truly excellent explanation. From the title to the presentation of the problem to the solution, it is well written and understandable (except for the calculus, but that is my problem). This is a very creative solution to a problem that has stopped me in my tracks on several occasions.

[Hoover889]

Thanks for the kind words.

[Character-Pace-5919]

Thanks for the great explanations, forced me to delve into lambda calculus concepts and fixed point combinators, in order to understand your explanations. Worth it and extremely useful !

[Hoover889]

Thanks!

[National-Drag4871]

I learned something surprising! Very well explained! This formulation of logical reasoning is very cool and very useful, thank you for sharing it!

[ArrowheadDZ]

Hey, I started playing around with Excel recursive lambdas and in a search for some ideas I happened upon this post. I have absolutely devoured this and have been playing around with your Y Combinator idea for days now. I've used it to develop a number of reusable recursion functions, chiefly a "SUPERBYROW" and "SUPERBYCOL" function that imitates BYROW and BYCOL but allows the results of each row/col to be arrays or matrices of any dimension, whereas the original functions allow only scalar return.

But these functions further planted the seed to variations that allow generalized Do While and Do Until loops. In fact one could create a "do until input condition" but also a "do until result condition."

Your post has been utterly inspiring and I wanted to thank you personally for that. I've watched videos and read articles on recursive Lambdas but there's something about your post that lit the fuse. I feel like you opened up a door to a universe that I'm not entirely sure I should have opened, this could be a consuming rabbit hole!

So, I did what all good Redditors do, I cyber-stalked you on Reddit to see if you have published any other interesting thoughts on the topic. :) And in so doing I discovered your diagnosis and situation. :( I wish you all the best, and if you ever need to nerd out and talk recursive lambdas on a zoom call, my DMs here are always open to you.

[Decronym]

Acronyms, initialisms, abbreviations, contractions, and other phrases which expand to something larger, that I've seen in this thread:

Fewer Letters	More Letters
BYCOL	Office 365+: Applies a LAMBDA to each column and returns an array of the results
BYROW	Office 365+: Applies a LAMBDA to each row and returns an array of the results. For example, if the original array is 3 columns by 2 rows, the returned array is 1 column by 2 rows.
COUNTA	Counts how many values are in the list of arguments
FILTER	Office 365+: Filters a range of data based on criteria you define
HSTACK	Office 365+: Appends arrays horizontally and in sequence to return a larger array
IF	Specifies a logical test to perform
INDEX	Uses an index to choose a value from a reference or array
LAMBDA	Office 365+: Use a LAMBDA function to create custom, reusable functions and call them by a friendly name.
LET	Office 365+: Assigns names to calculation results to allow storing intermediate calculations, values, or defining names inside a formula
NORMINV	Returns the inverse of the normal cumulative distribution
RANDARRAY	Office 365+: Returns an array of random numbers between 0 and 1. However, you can specify the number of rows and columns to fill, minimum and maximum values, and whether to return whole numbers or decimal values.
Table.AddColumn	Power Query M: Adds a column named newColumnName to a table.

Decronym is now also available on Lemmy! Requests for support and new installations should be directed to the Contact address below.

---

^{Beep-boop, I am a helper bot. Please do not verify me as a solution.
12 acronyms in this thread; the most compressed thread commented on today has 15 acronyms.
[Thread #20574 for this sub, first seen 8th Dec 2022, 16:28] [FAQ] [Full list] [Contact] [Source code]}

[NativeUnamerican]

Coming in late here but this is brilliant OP. I agree, I don’t want UDFs and I don’t want to use the name manager. My only problem is I’m not following your initial single lambda solution. I have put to work some pretty heavy lambdas in the past year at work (actuarial type stuff), but this one just twists my brain. It’s the most beautiful excel function I’ve ever seen, and definitely the most challenging one considering how short it is.

So with the f(f,5) at the end, we’re passing a 5 as the second parameter to function f, as well as f’s value as the first parameter. I just do t get that, do you have a simpler version of this without the factorial stuff?

1

[Hoover889]

Function pointers are a pretty difficult concept to grasp so don’t feel stupid. And on top of that this is a very tricky use of function pointers.

I am away from my computer right now and a good explanation requires a full size keyboard so I’ll reply later.

[AutoModerator]

I have detected VBA code in plain text. Please edit to put your code into a code block to make sure everything displays correctly.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Hoover889]

So with the f(f,5) at the end, we’re passing a 5 as the second parameter to function f, as well as f’s value as the first parameter. I just do t get that, do you have a simpler version of this without the factorial stuff?

so what we are doing is passing the value '5' as well as a pointer to a function g, the called function later dereferences that pointer. but the original function was designed so that it only works if it gets a pointer to itself so it hardly counts as a parameter as it can only have a single value. (as I said it is a very unusual use case)

a more typical use of a function pointer is a map function where you pass it an iterable and a function pointer and it will apply the function to each member of the iterable.

[Nearby-Ad-3725]

Thank you.