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'}

Anonymous Functions in VimL

Admit it, you’ve wanted this for a long time now.

Update: These two functions are now available in VimaholicsAnonymous.

VimL’s list sort() method allows the caller to provide a custom comparison function with which to sort by. Unfortunately, VimL doesn’t support anonymous functions (sometimes called lambdas), so the caller is forced to pre-write their comparator as a full-fledged function and provide its funcref to sort(). Well, that ends today. Now, VimL has anonymous function love! Check it:

This humble little snippet of code lets vimmers declare anonymous functions on the fly:

let fn_idx = 0 function! Fn(fn_form) let [fn_args, fn_body] = split(a:fn_form, '\s*=>\s*') let g:fn_idx = g:fn_idx + 1 let fname = 'AnonFn_' . g:fn_idx let b_elems = split(fn_body, '|') let b_elems[-1] = 'return ' . b_elems[-1] exe 'func! ' . fname . fn_args . "\n" \. join(b_elems, "\n") . "\n" \. 'endfunc' return function(fname) endfunction

Like this:

let x = ["one","two","three","four","five","six","seven","eight","nine","ten"] echo sort(x, Fn('(a, b) => len(a:a) > len(a:b)'))

The magic is in the Fn() call. It takes a string argument of the form:

(arguments) => function-body statements separated by | (pipe)

The last statement will be implicitly returned by the anonymous function, so no need to explicitly add a return statement.

Unicorns, or what?!

What? You want more. Certainly, sir. Behold:

function! Fx(fn, ...) return call(a:fn, a:000) endfunction

That lets you execute an anonymous function, like:

echo '2 ^ 6 = ' . string(Fx(Fn('(a, b) => pow(a:a, a:b)'), 2, 6))

Any cooler and you’d need your jumper! :-D Oh, but there’s more… I’m just getting warmed up!

Just because I like you, here’s a little extra gift:

let Mul = Fn('(a,b)=>let x = a:a | let y=a:b | x*y') echo '5 * 6 = ' . Fx(Mul, 5, 6)

That lets you call your funcref'd anonymous function by name. Did you see what I did there? Yes, I cheated God! I named an annonymous function. Cool, eh?

So, apart from the obvious, is this really that amazing? My vote is: YES! I have plans for this technology. Here’s a sneaky hint of where I’m looking to take this:

CompileMacros Mul = ((a,b) => let x = a:a | let y=a:b | x*y) echo '5 * 6 = ' . #(Mul, 5, 6) echo '2 * 6 = ' . #(((a, b) => a:a * a:b), 2, 6)

That’s right. I want hygenic macros in VimL. And that code works in my current experiments. The notation is stolen from… clojure I believe, where #(…) executes a lambda.

The call to CompileMacros will process any macros in the surrounding expressions before sourcing the result. Just for completeness, defining macros currently looks like this:

call Macro('(\+\((.\{-})\s*=>.\{-}\))', "Fn('\\1')") call Macro('\%(\n\|^\)\@<=\s*\(\w\+\)\s*=\s*\(Fn(.*=>.\{-})\)\s*\n', \ "let \\1 = \\2\n" ) call Macro('#(\(.*\))\n', "Fx(\\1)\n") call Macro('#Fn(\(.\{-}\))\n', "Fx(Fn(\\1)\n")

But that will change in the next version. Using regex to parse is an abomination; I was merely proof-of-concepting here. I’ll use VimPEG instead.

Stay tuned, if bending the spoon is what you’re in to.

Help Us Help You

I know: you want to be a good #vim citizen; you want to be a good vimmer; you want to learn and grow and solve your problems in a timely manner and do so in a safe and supportive environment filled with smart, caring and funny peers.

I know; we all do. And we all can. Here’s how:

Help Yourself

Vim has an awesome built-in manual filled with more answers than you have questions. Almost every problem you have is addressed somewhere within its many chapters. Unfortunately, newcomers often can’t find what they’re looking for in the manual, or don’t understand the answer because of a lack of jargon or fundamental Vim-specific knowledge. This feeling of inaccessibility passes over time as you level up in Vim, but can be debilitating to the beginner. But despair not! When you don’t understand something in the manual, then that is the time for asking on #vim, but more on that later. First, here are some tips for helping yourself to some Vim love:

I use the loose term manual here to treat the reference-manual and user-guide as a whole, just as the built in tools for navigating them do.

• :help topic will jump to topic within the manual.
  
• :helpgrep pattern will search for all occurrences of pattern throughout the manual. Use :cope to open the quickfix window of search results.
  
• There is a decent FAQ: http://vimhelp.appspot.com/vim_faq.txt.html
  
• The #vim channel has a fact bot called vimgor filled with answers to common problems. These facts are often keyed on weird terms that must be supplied to vimgor precisely to elicit their associated gems of wisdom, which is practically useless to the uninitiated. Thankfully, vimgor supports a listfacts interface that will return all known facts containing the given term, e.g:
  

  /msg vimgor listfacts file

  will list all known keys containing file.
  

You should explore vimgor using either /msg or /query to limit interference on the #vim channel. Feel free to call upon vimgor directly from within #vim if you are using it to answer someone else’s question. Here are some additional tools in that vein: ;help topic ⇐ will provide a URL to Vim’s manual for the given topic. ;man topic ⇐ will provide a URL to the appropriate unix man page.

Ask For Help

So you’ve looked in the manual and can’t find an answer, or don’t understand the answer; you’ve looked at the FAQs and checked in with vimgor to no avail. Now is the time to ask for help on #vim. Alternatively, ask reddit's vim channel. The guidelines for asking on #vim apply equally well for reddit's forum, of course.

Both for reasons of courtesy to others and self-edification, it’s important to try to find the answers to your own questions yourself before asking others on #vim. But just as important is how you ask:

For simple, easy and short examples, asking inline is acceptable and preferred, but if your problem is dense or requires more than a couple lines of data, using a pastebin service is preferred. Github’s gist is popular, but any decent ad-free pastebin will be happily tolerated. The format of your pastebin is also important. Here is an excellent example: https://gist.github.com/2759774

Etiquette

It’s obvious to most people that asking politely will yield better responses; some people need to be told explicitly. The good folk of #vim freely donate their time and energy to helping others discover the joy of being a vimmer. They delight in sharing their arcane knowledge with interested learners and inquisitive minds. In case you’re having trouble reading between the lines here, don’t approach #vim with these attitudes:

• impatience or unwillingness to learn: You don’t care to read the :help topic provided, you just want the solution to your exact problem RIGHT NOW. Nothing upsets a vimmer more. The :help is extremely well written if not a bit obtuse for newcomers, but we’ll help you understand those intricacies — very rarely is someone told to rtfm and then left to drown in their own incomprehension.
  
• rudeness or ungratefulness: diagnosing your problem might take some time and several steps requiring your participation. If you get frustrated at this or interact poorly then your chances of continued support diminish quickly. Be nice, get nice; say please and thank you.
  

One of my greatest teaching mentors gave me this gem once:

Teach as if your mentor is watching from the corner.

The analogy here is: ask as if you weren’t sitting behind a terminal; ask as if your mum or boss or teacher or doctor or someone you respect were listening.

In fairness, I have rarely seen such bad behaviour on #vim; it’s generally one of the most polite chat rooms I’ve ever seen. Let’s keep it that way! :-)

Not Classy, VimLPOO!

Rise, fellow VimLers and cease sobbing onto your consoles about the stink of VimLPOO (VimL Programming Object Orientedly). Vim keeps an open mind and so should you.

tl;dr : VimL OOP can haz class-reopening like Ruby

Okay, maybe not exactly like Ruby, but check it:

VimL’s OOP is more like javascript’s than Ruby’s. It doesn’t have explicit classes. It uses dictionaries to store data and methods that operate on it.

Here is one way in VimL to create an object factory:

function! Kid(name) <1> let k = {} <2> let k.name = a:name <3> func k.say(blah) dict <4> echo self.name . ': ' . a:blah endfunc return k <5> endfunction let boy = Kid('Jack') <6> let girl = Kid('Jill') call boy.say('wassup?') <7> call girl.say('chillin'' at the hill. u?') echo boy <8>

Jack: wassup?
Jill: chillin' at the hill. u?
{'name': 'Jack', 'say': function('69')}

1. I like to use the full command form function when creating object factories (classes?).
   
2. The object container is a dictionary (hash).
   
3. You can explicitly set attributes outside of methods if desired.
   
4. I like to use the short command form func for methods. The dict argument tells Vim that this is an instance method, providing us the self. accessor.
   

   You don’t need the ! on method declarations as you do for the outer-level.

5. The factory must return the newly created object.
   
6. Create an instance using the factory.
   
7. Call methods using dot notation.
   
8. The object in its native format is just a dictionary (hash).
   

Typically, after creating the object factory, the VimLPOO developer can’t re-open it to augment its behaviour although you can derive a new factory type from an existing one (inheritance without paternity):

function! RudeKid(name) let rk = Kid(a:name) <1> func! rk.say(blah) dict <2> echo self.name . ': Yo, biatch! ' . a:blah endfunc return rk endfunction let boy = RudeKid('Jack') let girl = Kid('Jill') call boy.say('wassup?') call girl.say('wtf?') echo boy

Jack: Yo, biatch! wassup?
Jill: wtf?
{'name': 'Jack', 'say': function('72')}

1. Base this object on the parent factory.
   
2. Override methods as desired.
   

   The use of ! is now required because the method already exists in the base object.

But I’m not here today to talk about weak inheritance. I wanna play with class re-opening, Vim style.

As a quick recap, a Vim object is a dictionary with data and methods that can use the self. modifier internally to refer to its data and other methods. It turns out that Vim is not too particular about who gets to claim dict access on your objects. You’re free to create external functions, adorned with the dict modifier, and have them manipulate your objects as if they were created with the class originally:

function! s:slapped() dict echo self.name . " just got slapped!" endfunction

This happens to be a script-local (s:) function; global scope would work too, but why pollute unnecessarily? Now, if you tried to do a naive direct call of this, you’d be sorely disappointed:

call boy.slapped()

Error detected while processing jack_and_jill.vim:
Line   42:
E716: Key not present in Dictionary: slapped

That makes sense… We created slapped() as a script-local function, not a method on the boy instance.

Adding the method to the Kid() factory after having created the boy instance would be just as useless.

Happiness is just a call away:

call call('s:slapped', [], boy) " Jack just got slapped!

:-D How cool is that?!

I have a little project in the works that uses this to allow clients of the engine to inject their own solutions to various parts of the workflow. It’s almost done, so I should be able to show something a bit more real-worldy soon. For now, what mischief can you concoct with this shiny new toy? I look forward to finding out. :-)

Vim on!