Rapid Programming Language Prototypes with Ruby & Racc, Commentary

I just watched a tolerable ruby conference video by Tom Lee on Rapid Programming Language Prototypes with Ruby & Racc.

What he showed he showed fairly well. His decision to "introduce compiler theory" was, he admitted, last-minute and the hesitation in its delivery bore testimony to that. The demonstration of the compiler pipeline using his intended tools (ruby and racc) was done quite well with a natural progression through the dependent concepts along the way. By the end of the talk he has a functional compiler construction tool chain going from EBNF-ish grammar through to generated (and using gcc, compiled) C code.

I was surprised that nobody in the audience asked the question I was burning to ask from half way through the live-coding session: Why not use Treetop? (or the more generic: why not use a peg parser generator or a parser generator that does more of the heavy lifting for you?)

The whole point of Tom's presentation is: use ruby+racc because it saves you from all the headaches of setting up the equivalent tool chain in C/C++. And it does, he's right. But it feels to me that Treetop does even more of that hard work for you, allowing you to more quickly get to the fun part of actually building your new language. I'm angling for simplicity here.

I could be wrong, though, so let me ask it here (as Confreaks seems to not allow comments): Why not treetop (or an equally 'simple' parser generator) for something like this? (and answers along the lines of EBNF > PEG are not really what I'm after, but if you have a concrete example of that I'd like to hear it too.)

On a completely separate note: Tom, you need to add some flying love to your Vim habits. :-)

Genetic Algorithms in VimL (Part I)

Burak Kanber is into machine learning. I was entertained by his Hello World genetic algorithm example and, in alignment with his implementation language agnosticism, I thought I'd write a version in VimL:

This depends on vim-rng for the random number stuff.

let s:Chromosome = {}

function! s:Chromosome.New(...)
  let chromosome = copy(self)
  let chromosome.code = ''
  let chromosome.cost = 9999
  let chromosome.pivot = 0

  if a:0
    let chromosome.code = a:1
    let chromosome.pivot = (strchars(chromosome.code) / 2) - 1
  endif

  return chromosome
endfunction

function! s:Chromosome.random(length)
  let self.code = RandomString(a:length)
  let self.pivot = (a:length / 2) - 1
  return self
endfunction

function! s:Chromosome.mutate(chance)
  if (RandomNumber(100) / 100.0) < a:chance
    let index = RandomNumber(1, strchars(self.code)) - 1
    let upOrDown = RandomNumber(100) <= 50 ? -1 : 1
    let exploded = split(self.code, '\zs')
    let change = nr2char(char2nr(exploded[index]) + upOrDown)
    if index == 0
      let self.code = change . join(exploded[index+1:], '')
    else
      let self.code = join(exploded[0:index-1], '') . change . join(exploded[index+1:], '')
    endif
  endif
  return self
endfunction

function! s:Chromosome.mate(chromosome)
  let child1 = strpart(self.code, 0, self.pivot) . strpart(a:chromosome.code, self.pivot)
  let child2 = strpart(a:chromosome.code, 0, self.pivot) . strpart(self.code, self.pivot)
  return [s:Chromosome.New(child1), s:Chromosome.New(child2)]
endfunction

function! s:Chromosome.calcCost(compareTo)
  let total = 0
  let i = 0
  while i < strchars(self.code)
    let diff = char2nr(self.code[i]) - char2nr(a:compareTo[i])
    let total += diff * diff
    let i += 1
  endwhile
  let self.cost = total
  return self
endfunction

function! s:Chromosome.to_s()
  return self.code . ' (' . string(self.cost) . ')'
endfunction


let s:Population = {}

function! s:Population.New(goal, size)
  let population = copy(self)
  let population.members = []
  let population.goal = a:goal
  let population.generationNumber = 0
  let population.solved = 0

  let size = a:size
  let length = strchars(population.goal)
  while size > 0
    let chromosome = s:Chromosome.New()
    call chromosome.random(length)
    call add(population.members, chromosome)
    let size -= 1
  endwhile

  return population
endfunction

function! s:Population.display()
  % delete
  call setline(1, "Generation: " . self.generationNumber)
  call setline(2, map(copy(self.members), 'v:val.to_s()'))
  redraw
  return self
endfunction

function! s:Population.costly(a, b)
  return float2nr(a:a.cost - a:b.cost)
endfunction

function! s:Population.sort()
  call sort(self.members, self.costly, self)
endfunction

function! s:Population.generation()
  call map(self.members, 'v:val.calcCost(self.goal)')

  call self.sort()
  call self.display()

  let children = self.members[0].mate(self.members[1])
  let self.members = extend(self.members[0:-3], children)

  let i = 0
  while i < len(self.members)
    call self.members[i].mutate(0.5)
    call self.members[i].calcCost(self.goal)
    if self.members[i].code == self.goal
      call self.sort()
      call self.display()
      let self.solved = 1
      break
    endif
    let i += 1
  endwhile

  let self.generationNumber += 1

  return self
endfunction

enew
let population = s:Population.New('Hello, world!', 20)
while population.solved != 1
  call population.generation()
endwhile

To see it run save it in a file and type   :so %   from within vim.

Why, dear bairui, you ask? Well, at this stage... I don't know. It just looked like fun. However, a couple of wild thoughts occurred to me: finding the ideal (good enough; as in 'correct' enough) combination of various vim options to achieve a desired look and behaviour. Take for example the various C indenting styles - what mad combination of &cinoptions, &cinkeys and &cinwords would you need to achieve Frankenstein's Indentation Style? What about getting &formatlistpat right for your preferred markup style? Sure, these might be totally hair-brained ideas -- but they might give you an idea for something less hairy and actually useful. Either way, I plan to keep playing with Burak's tutorial as he progresses through it. Thanks, Burak! :-)