Self generating code (or Why Recursion is a wonderful idea)

Self-modifying code is the fancy of every assembly language enthusiast. You can write self modifying code when code and data are in the same accessible area of memory, and your code can modify the instructions of itself. I have never written self-modifying code myself, but have always admired the possibilities of it.

Self-generating code is possible in dynamic languages like Ruby and Javascript through the eval statement. It's commonly referred to as metaprogramming in Ruby. I recently came across a very common problem that made me think of a metaprogramming solution. Imagine you have a set [A, B, C, D]. How do you find all the different combinations of it - [A], [B], [C], [D], [A,B], [A,C], [A,D], [B,C]......[A,B,C,D]?

Lets break down the problem. To find all different combinations, you need to find the combinations selecting 1 at a time, selecting 2 at a time and so on:
C = nC1 + nC2 + .... + nCn

To find the combination nCr, you can find the permutation and take the unique sets:

To find the permutation nPr (n=4, r=3), a simple pseudo code would look like

permutations= []
set = ['A','B','C','D']
for i in 0 to n-1
for j in 0 to n-1
for k in 0 to n-1
permutations << [set[i], set[j], set[k]]
end
end
end


It has n-levels of nested loops and its difficult to write n levels of nesting in code when n is dynamic. You can't write code for a fixed-n. The code must be intelligent enough to generate n-level nested loops (or you can recur, but lets hold on to a non-recursive solution). This can be expressed using Ruby each as:


set.each {|i1|
set.each {|i2|
set.each {|i3|
permutations << [i1, i2, i3]
}
}
}


Metaprogramming, like Recursion, is all about finding patterns, and you can easily spot code segments repeated thrice for r = 3. This can be expressed using eval as:


def permutate(set, r)
permutations = []
eval (1..r).collect {|i| "set.each{|i#{i}| "}.join('') +
'permutations << [' + (1..r).collect{|i| "i#{i}"}.join(',') + ']' + '}' * r
permutations
end


This code has a flaw because it included duplicates in each iteration. It can be fixed by not considering the elements of preceding iterations in the set for the current iteration. The modified code is:


set.each {|i1|
(set - [i1]).each {|i2|
(set - [i1] -[i2]).each {|i3|
permutations << [i1, i2, i3]
}
}
}


In eval, this translates to:


def permutate(set, r)
permutations = []
eval (1..r).collect {|i| "(set " + (1...i).collect {|j| " - [i#{j}]"}.join('') +").each{i#{i} "}.join('') +
'permutations << [' + (1..r).collect{|i| "i#{i}"}.join(',') + ']' + '}' * r permutation
end


Combination can be expressed using permutation as:


def combinate(set,n)
permutate(set_n).collect{|s| s.sort}.to_set.to_a
end


Now, the original problem can be solved by computing the combinations from 1 to n:


def combinations(set)
(1..set.size).collect {|i| combinate(set,i)}
end


It was a tricky use of eval and looping to generate code on the fly. But why bother with tricky syntactic details and code generation, when the compiler/interpreter can manage all the grunt work for you. Thats why Recursion is such a wonderful idea