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!

What If The Romans Had Vim?

---

This is much more about VimL than MDCLXVI strings; if this code doesn’t rape your cat, you’re welcome.

Call it a kata if you will; I decided over breakfast to have a go at writing a Roman Numeral to Arabic Number converter in VimL. It’d been sufficiently long since I’d written such a converter in any language, and I’d never done one in VimL, so I thought, why not?

I prefer to think away from the console, so I grabbed a notepad and pencil and started doodling a solution based on how I think about parsing Roman Numerals in wet-ware. Roughly, that looked a bit like:

to_arabic(str) new stack for each roman_letter in str val = arabic_value(roman_letter) if val < stack.tos() stack.push(val - pop()) elseif val == stack.tos() stack.push(val + pop()) else stack.push(val) end end return sum(stack) end

Yes, I am aware that might expose potentially embarrassing belief systems I might be operating under regarding life, the universe and everything. Meh.

I did some mental as well as paper-based run-throughs of the algorithm to convince myself that it would work and then implemented it in VimL. I don’t have the VimL solution to show you because after getting a working version I began refactoring it as I saw opportunities and generalities lurking within the code.

Here is what I ended up with:

function! Roman() let obj = {} let obj.values = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1 } func obj.to_arabic(str) dict let self.prior = 0 return eval(join(map( \ reverse(map(split(a:str, '\zs'), 'self.values[v:val]')) \, 'self.calc(v:val)'), '+')) endfunc func obj.calc(v) dict let [n, self.prior] = [(a:v < self.prior ? -a:v : a:v), a:v] return n endfunc return obj endfunction

So while my pseudo-code used a stack and processed the string in original order, the final algorithm reversed the string and just tracked the prior value each time through the loop (map()).

Some explanations of the weirder VimL:

• I’m using VimL’s Object Oriented approach which is more like javascript’s than C++'s. The Roman() function is actually an object generator. Each such object then has a to_arabic(roman_string) method.
• I’m also using VimL’s functional-ish approach to processing data lists. Reading such constructs is usually better from the inside out, which begins with:
  
  • The split(a:str, '\zs') yields a LIST OF individual LETTERS. Unfortunately, the explanation at :help /\zs doesn’t include the idiomatic use shown here of exploding strings out to a list of their component characters.
    
  • The map( LIST OF LETTERS , 'self.values[v:val]') converts individual Roman Numerals to equivalent Arabic numbers. This, therefore, returns a LIST OF NUMBERS. VimL’s map() function takes the list first and an expression to be evaluated against each element in turn (the resulting list returned by map() is the modification of each element through this evaluated expression). A simple example might help; this generates squares:
    

    echo map(range(1,10), 'v:val * v:val')

    The archaic looking `v:val` is VimL's Way of exposing access to the value of
    the element. If it helps, this would be equivalent to the Ruby code:

    (1..10).map {|val| val * val}

    map() in VimL is destructive, not that that matters here, though.

  • The map( LIST OF NUMBERS , 'self.calc(v:val)') inverts numbers in the list if they precede bigger numbers. Remember the original string order of letters is reversed in this algorithm.
    
  • The eval(join( LIST OF NUMBERS , '+')) sums the list.
    

All in all… I think this algorithm does what it’s supposed to do, and it does so with less aggression than solutions I googled for afterwards. o_O

At least the first comment in that last one tries to head the complainant in the right direction early.

The other thing I wanted to show today is micro-tests. Of course, being able to refactor sloppy code into a better solution is made practical with tests.

We all know and love testing, and Vim has decent plugins for doing it properly when you have to (i.e. writing your own plugin.) However, for quick’n'dirty jobs like this, I usually just drop a small inline test at the end of the script:

if expand('%:p') == expand('<sfile>:p') let fail = 0 for t in [ \ [1, 'I'] \, [2, 'II'] \, [3, 'III'] \, [1992, 'MCMXCII'] \, [1999, 'MCMXCIX'] \] if t[0] != Roman().to_arabic(t[1]) echo 'Fail: ' . t[0] let fail = 1 endif endfor if ! fail echo "Ok" endif endif

The if expand('%:p') == expand('<sfile>:p') trick is to allow this script to be `:source`d from another script without triggering the unit-tests. I didn’t need this here because roman numeracy has been out of fashion for a while now, but I thought I would show this here as an added bonus. I’ve shown few tests here to keep the post brief. My real tests for this little algorithm number in the fifties. I bet even then I’ve overlooked some poignant design aspect of Roman Numerals. This was meant to be an exercise in the general approach rather than aiming to provide an exhaustively accurate turn-key solution. One notable absence in that vein is the lack of data validation to ensure the roman numeral string is not of Celtic descent. For those with the inability to read between the lines (osse), that last paragraph means: if I have flubbed some VimL, I’d love to hear from you; if I’ve merely upset dead Romans and their counting system, I don’t so much care.

Update: The testing code has been extracted out into a tiny little plugin called vim-u-test if you're interested in experimenting with it.

VimL List Gymnastics

---

Some common flexing between lists and dicts in VimL.

let a_list = range(1,10) echo a_list "=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] " from list -> dict let a_dict = {} call map(copy(a_list), 'extend(a_dict, {v:val : (v:val * v:val)})') echo a_dict "=> {'1': 1, '2': 4, '3': 9, '4': 16, '5': 25, '6': 36, '7': 49, '8': 64, '9': 81, '10': 100} " from dict -> list echo keys(a_dict) "=> ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'] echo map(keys(a_dict), 'str2nr(v:val)') "=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] echo values(a_dict) "=> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] " collecting a single dictionary from multiple dictionaries let b_text = "one thing\ntwo things\nthree more things" let b_dict = {} call map(split(b_text, '\n'), 'extend(b_dict, {split(v:val)[0] : v:val})') echo b_dict "=> {'one': 'one thing', 'two': 'two things', 'three': 'three more things'}