Y u no, Vim?

Well, Y you can, it would seem…

I was recently reminded (hi, dhruvasagar) of the Y combinator while idling on #vim and I thought to myself… can you Y, Vim? I decided to find out.

I just recently wrote about Anonymous Functions in Vim and they form the cornerstone of my attempt at Y-ing here. I used Mike Vanier’s excellent article: The Y Combinator as a guide (any and all errors are wholly mine); reading it will fill in the huge holes I have chosen to skip over here.

Mr Fibonacci is in the studio with us today, representing la raison d’recurse.

Mr Fibonacci, Zero?

"=> 0

Lovely! Er… and 14?

"=> 377

Amazing!

Now to some code… First up is the standard recursive definition of Fibonacci:

function! RecursiveFibonnaci(n) if a:n == 0 return 0 elseif a:n == 1 return 1 else return RecursiveFibonnaci(a:n - 1) + RecursiveFibonnaci(a:n - 2) endif endfunction

And asking our studio guest…

echo RecursiveFibonnaci(10) "=> 55

Decent. Now just for fun, here’s the same thing written as an Anonymous Function:

let RF = Fn('(n) => if a:n == 0' \.'| return 0' \.'|elseif a:n == 1' \.'| return 1' \.'|else' \.'| return call(g:RF, [a:n - 1]) + call(g:RF, [a:n - 2])' \.'|endif')

Fn() is provided by VimaholicsAnonymous.

How does she measure up, Mr Fibonacci?

echo RF(11) "=> 89

…and does it agree with our recursive stalwart?

echo RecursiveFibonnaci(12) == RF(12) "=> 1

Standard! But we haven’t even begun to look at Y yet, so here is Mike’s AlmostFibonacci a la Vim:

function! AlmostFibonacci(f) silent! unlet b:f let b:f = a:f return Fn('(n) => if a:n == 0' \.'| return 0' \.'|elseif a:n == 1' \.'| return 1' \.'|else' \.'| return call(b:f, [a:n - 1]) + call(b:f, [a:n - 2])' \.'|endif') endfunction

You will notice that it contains an almost identical copy of the anonymous recursive Fibonacci (RF) we declared above. It’s not quite the same, of course, because this version is not meant to be self-recursive. It calls the function f provided to AlmostFibonacci. The little silent! unlet b:f dance and the use of a buffer variable in the first place is just some necessary mechanics to pass AlmostFibonacci's f argument into the inner anonymous function. Basically, we cheat through the use of a global. I use a buffer-local here as a baby-global.

How are we doing, Mr F.?

echo call(AlmostFibonacci('RecursiveFibonnaci'), [12]) "=> 144 echo RecursiveFibonnaci(12) == call(AlmostFibonacci('RecursiveFibonnaci'), [12]) "=> 1

Respect.

Heh… The astute among you are half way through a hate comment right now that I have violated one of the laws of thermodynamics, or at least common decency by employing RecursiveFibonnaci in the call to AlmostFibonacci there. Relax. I know I’m cheating. I just wanted to prove that the code worked. We’ll get to actual Y below. :-p

I hesitated whether I would even show this next piece. It’s using the exact same functions as we just used above, but I am using a slightly different call() interface. I actually use this call() interface in the real Y; I wanted you to know that this difference wasn’t.

echo call(call('AlmostFibonacci', ['RecursiveFibonnaci']), [13]) "=> 233 echo RecursiveFibonnaci(13) == call(call('AlmostFibonacci', ['RecursiveFibonnaci']), [13]) "=> 1

And here she is: Y in Vim!

function! Y(f) let b:f_ = a:f return call(a:f, [Fn('(x) => call(call("Y", [b:f_]), [a:x])')]) endfunction

Again, you will notice the same buffer-local dance for marshalling the function in a:f into the inner anonymous function.

And, hopefully unsurprising by now, here is how we define Fibonacci with Y:

function! Fibonacci(n) return call(call('Y', ['AlmostFibonacci']), [a:n]) endfunction

Still kosher, Mr F.?

echo Fibonacci(14) "=> 377 echo RecursiveFibonnaci(14) == Fibonacci(14) "=> 1

Splendid! But… how does the Y version compare to the recursive version?

let start = reltime() call RecursiveFibonnaci(20) echo reltimestr(reltime(start)) "=> 0.99 seconds

uh huh…

let start = reltime() call RF(20) echo reltimestr(reltime(start)) "=> 1.066 seconds

I guess the indirection there causes some overhead, but nothing disastrous…

let start = reltime() call Fibonacci(20) echo reltimestr(reltime(start)) "=> 14.56 seconds

:-( There is no God!

It would seem that although "possible", Y in Vim is not advised*. Or, at least, not the way I approached it. Perhaps there’s a brighter way? I’d love to see it.

(*): Y is not advised anywhere, as far as I can tell, except as a mind-stretching exercise from the church of functional dys.

Just to scare little Vimmers late at night, after running this code, the number of anonymous functions in my Vim session was 48098! This code maims unicorns.

That’s Y!