.png)
1 month ago
2
Welcome back code champs, number ninjas, and data divers to our first episode of Beating Code Interviews with Stupid Stuff. People often send me emails asking, “How can I use lambda calculus to impress people?” Today, we find out.
I have an interview with ZCorp lined up in 5 minutes, and our challenge is to only use anonymous functions. No defn, no loops, and definitely no self-reference. I’ll allow myself the occasional def for brevity, but beyond that, we’ll be running on pure lambda calculus.
20 minutes later
Hey, sorry to keep you waiting. I just got out of a more important meeting. I’m kind of a big deal here at ZCorp. Why don’t you tell me a little bit about yourself?
Born of binary, raised on algorithms, I walk the path of lambda…
Riiiight… Let’s just start with the warm-up problem. Show me how you would reverse a list.
Ah, the timeless list reversal. Deceptively simple, perilously deep. We must first define our purpose.
We’re just writing a function, and it only needs to take a list…
Not just any function, my friend, but one that knows itself. To know yourself is to find your fixed point.
SELF is an input to itself, the logic of reversal.
Ok let’s just move on to the next problem, creating a Fibonacci sequence.
Oh no, our definition of reverse is intertwined with recursion. Let’s factor that out:
We need to lift our SELF
Oh, no… SELF doesn’t take LIST, it’s a function that returns a function that operates on LIST, and the argument to SELF is… SELF. Therefore, we need to give it (SELF SELF).
That’s a confusing way to write it
Quite right, because it’s not obvious what (SELF SELF) is. We need to extract it out. What we want is:
Believe me when I say that is not what I meant…
Oh, right. Now SELF = (SELF SELF).
Not what I meant, and also that sounds impossible.
But identity is the identity of itself:
O.K. sure, but that’s a special case.
This is an identity crisis.
We just need to find the right conditions for (SELF SELF) = SELF.
Well, it’s a function! That much is clear…
But it doesn’t work, because (REV-LOGIC REV-LOGIC) =/= REV-LOGIC. Let’s try something easier:
FIX takes the logic function, and makes a function such that (FIXED (FIX LOGIC)) = FIXED
(FIXED FIXED) => FIXED which means that ((FIX LOGIC) (FIX LOGIC)) = (FIX LOGIC)
Right, that sounds way easier… shaking head in disbelief
Exactly! Because we just reverse it: (FIX F) = ((FIX F) (FIX F))
Why did you call it FIX?
Well, it was broken before right?
I’m starting to think that you are the broken one.
But FIX can still see itself. We need to parameterize the use of FIXED
There, I fixed it.
What is fixed?
FIXED is (FIXED FIXED), obviously.
Obviously. raises hands in dispair
Because (FIX F) = ((FIX F) (FIX F)), it was your idea to refactor remember?
Everything looks to be inside out now.
Oh, you are right, we can’t pass (FIXED FIXED) as an argument because it will be evaluated first. Thanks for the tip.
Can we fix it? slaps self
Instead of calling (FIXED FIXED) we need a function that will create (FIXED FIXED) when it’s needed, after LOGIC gets called. LOGIC needs to take itself as it’s argument, so the function we pass to LOGIC should look very much like LOGIC, but of course without any actual logic in it.
That actually sounds logical.
LOGIC is a function of itself, returning a function that acts on a value:
didn’t you say that (FIXED FIXED) = FIXED?
Yes but only after we FIX it. Fixing it requires us to go from FIXED to (FIXED FIXED) remember?
Ah sure…
So while we are fixing logic, let’s replace (LOGIC (FIXED FIXED)) with our deferring function.
Did you know this is called continuation passing style?
CSP?
No, that’s communicating subprocesses.
That’s confusing.
Isn’t it!? Fortunately, we are about to be unconfused.
At least it didn’t blow up this time…
Nice, that’s the right answer.
Even nicer is that our fixed logic behaves like identity now:
I can’t believe something so ridiculous actually works.
Yes it is ridiculous to have all those silly names. Let’s fix that:
You are not your variables. Rename them, rebind them. Your essence is invariant.
Wait, we are meant to be doing Fibonacci, remember?
We are factoring out our LOGIC.
It looks to me like you doubled the code, that’s not great refactoring. Using single letters make it totally unreadable.
Hmmm, there does seem to be a lot of doubling. We can factor out a function for f => (f f).
The replication of identity is itself.
But test not the serpent lightly
The replication of replication is eternal. Now we can clean up that duplication.
That’s not really any clearer…
Very well, we can keep extracting.
If the infinite is deferred, is it infinite?
OMEGA diverges, ZETA folds, LOGIC writes QED.
That’s much nicer, I’m so glad you suggested using longer names.
Can we write Fibonacci, please?
Oh, that’s easy now!
That’s all backward!!
Oh, my mistake
You can’t be serious… This is ridiculous. We’ll be here forever if you keep this up.
I love that idea! An infinite sequence is exactly what we need…
That’s so nice.
Oh look at the time! I have a more important meeting to go to! disconnects
Ouch, Rough. ZCorp never got back to me, so let’s update the scoreboard as a loss.
That’s all for today. Until next time, keep on coding.
