domingo, 3 de enero de 2016

Continuations as accumulators

Some months ago I read The Little Schemer, an amazing book that guides through many functional programming concepts in a very different way to other books.

To me, by far the most challenging part of the book whas that exercise in page 137 which uses a continuation as an accumulator. I remember being hours staring at it thinking "WTF?". In fact I also remembered that in SICP there was a code example (in the compiler chapter IIRC) that used this style of programming, and also got me puzzled, and I ended up letting it go, and continuing reading (after some time staring at it also).

Months after TLS and years after SICP, I'm reading Concepts, Techniques, and Models of Computer Programming (CTM), and at some point it talks about recursion, and accumulators. At the point it starts explaining multiple accumulators, I had an 'aha' moment, closing the multirember&co problem. In fact CTM doesn't talk about CPS (at least in that part). But somehow intuitively they're talking about the same concept.

def odd_even_part(l, &block)
  if l.empty?
    yield([], [])
  elsif l[0].even?
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds, evens + [l[0]])
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds + [l[0]], evens)

odd_even_part([1,2,3,4]) do |odds, evens|
  puts "odds => #{odds}"
  puts "evens => #{evens}"

I decided to reimplement a variant of it in ruby. Now that I look at it, it's super simple... I guess some things just need time to settle.

Here are some related links, talking about the technique or explanations of the original problem.