VimScript - gregorymorrison/euler1 GitHub Wiki

Vim, everybody's favorite text editor, has a scripting component that lets you bend it to your will. Oddly, this language seems not to have a formal name - Vim's official documentation refers to it as merely as "vim script", while others have dubbed it VimL. Interestingly, it doesn't really look like any other language I've used. Apparently, it's derived from the original vi editor's Ex scripting language, which itself is derived from the ed editor's scripting language, which derived from the QED editor's scripting language, which derived from the TECO command language used to control paper tape on DEC PDP minicomputers in the 60's. Whew, interesting pedigree!

Vim script is not a large, complex language, since it's merely meant to extend Vim. And much of it is simple, Basic-like Procedural declarations. Vim script is worth exploring because it's actually a fully-Turing-complete language. It has exception handling, list and dictionary data structures, and prototype-based object orientation. Vim also exposes an elaborate collection of functions and properties to Vim script, concerning documents, the editor, history, file system, OS environment, etc. Here is a simple version of Euler1:

#!/usr/local/bin/vimsh
" Euler1 in VimL

function! g:Euler1(size)
    let s:result = 0

    for i in range(1, a:size)
        if i % 3 == 0 || i % 5 == 0
            let s:result += i
        endif
    endfor

    return s:result
endfunc

:echo "Euler1 =" + g:Euler1(999)

This should be pretty easy to read even for the uninitiated - it's simple Procedural code. One interesting twist visible here is its optional, built-in scoping operators - g: denotes global, s: denotes local to this script, and a: denotes arguments, among others. Cool - it has a range() function. VimScript actually has a lot of built-in functions, complete with built-in documentation - just type e.g. ':help range()' in Vim.

Here's another annoyingly contrived version of Euler1 using an object prototype:

#!/usr/local/bin/vimsh
" Euler1 in VimL

" an object prototype (just a dictionary)
let Euler1 = {}

" the constructor
function! Euler1.New(size)
    let newObj = copy(self)
    let newObj.size = a:size
    return newObj
endfunc

" an instance method
function! Euler1.solve()
    let result = 0
    for i in range(1, self.size)
        if i % 3 == 0 || i % 5 == 0
            let result += i
        endif
    endfor
    let self.result = result
endfunc

" create an instance
let euler = Euler1.New(999)

:call euler.solve()

:echo "Euler1 =" + g:euler.result

Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function Euler1() is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

#!/usr/local/bin/vimsh
" Euler1 in VimL

set maxfuncdepth=1010

function! g:Euler1(n, acc)
    if a:n == 0
        return a:acc
    elseif a:n % 3 == 0 || a:n % 5 == 0
        return Euler1(a:n-1, a:acc+a:n)
    else
        return Euler1(a:n-1, a:acc)
    endif
endfunc

:echo "Euler1 =" g:Euler1(999, 0)

I was pleasantly surprised to find that VimScript actually has some functional operations built-in. It has map() and filter(), though it does not have reduce(), so I had to roll my own.

#!/usr/local/bin/vimsh
" Euler1 in VimL

function IsEuler(n)
    return a:n % 3 == 0 || a:n % 5 == 0
endfunc

function! Reduce(list, f)
  let [acc; tail] = a:list
  while !empty(tail)
    let [head; tail] = tail
    let acc = a:f(acc, head)
  endwhile
  return acc
endfunc

fun Add(a,b)
    return a:a + a:b
endfun

function! Euler1(size)
    let ints = range(1, a:size)

    let mapped = map(ints, 'v:val')
    let filtered = filter(mapped, 'IsEuler' . '(v:val)')
    let reduced = Reduce(filtered, function('Add'))
    return reduced
endfunc

:echo "Euler1 =" g:Euler1(999)

This syntax feels a little arbitrary. map() takes an array and a function, but here, I want map to just return the original values for illustration, so instead of a function I pass the value itself. The function passed to filter() uses string representation, while Reduce uses an actual function. It's cool that it supports function passing, but this seems a little, well, arbitrary. You can also see that VimScript reserves lowercase function names for itself; yours have to be uppercase. VimScript also has list destructuring, something I'm used to in functional languages but didn't expect here. Look at the Reduce() function - here, 'acc' gets assigned the first element of a collection, while 'tail' gets assigned the rest.

Here's another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together.

#!/usr/local/bin/vimsh
" Euler1 in VimL

:set maxfuncdepth=1010

function! Euler(ints)
  " if the list is empty, return 0
  if len(a:ints) == 0
    return 0
  endif

  let s:pivot = len(a:ints) / 2

  " recursively process the half of the list below the middle element
  let s:pre = 0
  if 0 < s:pivot
    let s:pre = g:Euler( s:sliced = a:ints[0 : s:pivot-1] )
  endif

  " recursively process the half of the list above the middle element
  let s:post = 0
  if s:pivot+1 <= len(a:ints)-1
    let s:post = g:Euler( a:ints[s:pivot+1 : len(a:ints)] )
  endif

  " return thisVal + the results from the first and last halves
  return s:pre + a:ints[s:pivot] + s:post
endfunc

function! Euler1(size)
  return g:Euler( range(1, a:size) )
endfunc

:echo "Euler1 =" g:Euler1(999)

Okay, this was HANDS-DOWN the worst performance I've seen by a language for this algorithm. It ran for minutes at 100% CPU. Clearly VimScript is not optimized for this kind of algorithm.

One more example - I just found this elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don't sweat it if this seems inscrutable; click the blog link above for an explanation. Here is my version:

#!/usr/local/bin/vimsh
" Euler1 in VimL

function! g:MySum(n, size)
    return (((a:size/a:n) * (a:size/a:n)) + (a:size/a:n)) * a:n / 2
endfunc

function! Euler1(size)
    return MySum(3, a:size) + MySum(5,a:size) - MySum(15,a:size)
endfunc

:echo "Euler1 =" g:Euler1(999)

Here, you'll notice that I needed to set Vim's recursion depth property in order for this to succeed. All of Vim's settings are available here.

To run a Vim script, you first load your script as a file into Vim and execute it using the command ':so %'. Output gets displayed in Vim's command line. But what if you want to simply run it as a command-line script? I found a shell script, vimsh, that does just that - it feeds your file into Vim and outputs the results to the command line. There's even a Windows batch file version. It's a kind of hacky process involving temp files, but it works. It choked on the scoping operators from my first example, but when I removed them, all was copacetic. Simply add the shebang at the top of your file and execute it.

$ ./euler1.vimsh

Euler1 = 233168

$