As a follow-up to my original article on recursion in Puppet, and in my attempt to Push Puppet (to its limit), I’ll now attempt some more advanced recursion techniques in Puppet.
In my original recursion example, the type does recurse, but the callee cannot return any value to the caller because it is a type, and not strictly a function. This limitation immediately limits the usefulness of this technique, but I’ll try to press on! Let’s try to write a Fibonacci series function in native Puppet.
For those who aren’t familiar, the Fibonacci series function is a canonical computer science recursion example. It is very easy to write as pseudo-code or to implement in python:
def F(n): if n == 0: return 0 elif n == 1: return 1 else: return F(n-1)+F(n-2)
You can download this function here. Let’s run that script to get a table of the first few values in the Fibonacci series:
$ ./fibonacci.py F(0) == 0 F(1) == 1 F(2) == 1 F(3) == 2 F(4) == 3 F(5) == 5 F(6) == 8 F(7) == 13 F(8) == 21 F(9) == 34 F(10) == 55 F(11) == 89 F(12) == 144 F(13) == 233 ...
Now, I’ll introduce my Puppet implementation:
#!/usr/bin/puppet apply
class fibdir {
# memoization directory
file { '/tmp/fibonacci/':
ensure => directory,
}
}
define fibonacci(
$n,
$intermediate = false # used for pretty printing
) {
include fibdir
$vardir = '/tmp'
$fibdir = "${vardir}/fibonacci"
if "${n}" == '0' {
# 0
exec { "${name}: F(0)":
command => "/bin/echo 0 > ${fibdir}/0",
creates => "${fibdir}/0",
require => File["${fibdir}/"],
}
} elsif "${n}" == '1' {
# 1
exec { "${name}: F(1)":
command => "/bin/echo 1 > ${fibdir}/1",
creates => "${fibdir}/1",
require => File["${fibdir}/"],
}
} else {
$minus1 = inline_template('<%= n.to_i - 1 %>')
fibonacci { "${name}: F(${n}-1)":
n => $minus1,
intermediate => true,
}
$minus2 = inline_template('<%= n.to_i - 2 %>')
fibonacci { "${name}: F(${n}-2)":
n => $minus2,
intermediate => true,
}
# who can figure out what the problem with this is ?
$fn1 = inline_template('<%= f1=fibdir+"/"+minus1; (File.exist?(f1) ? File.open(f1, "r").read.to_i : -1) %>')
$fn2 = inline_template('<%= f2=fibdir+"/"+minus2; (File.exist?(f2) ? File.open(f2, "r").read.to_i : -1) %>')
if (("${fn1}" == '-1') or ("${fn2}" == '-1')) {
$fn = '-1'
} else {
$fn = inline_template('<%= fn1.to_i+fn2.to_i %>')
}
if "${fn}" != '-1' { # did the lookup work ?
# store fibonacci number in 'table' (memoization)
exec { "${name}: F(${n})":
command => "/bin/echo ${fn} > ${fibdir}/${n}",
creates => "${fibdir}/${n}",
require => [
File["${fibdir}/"],
Fibonacci["${name}: F(${n}-1)"],
Fibonacci["${name}: F(${n}-2)"],
],
}
if ! $intermediate {
# display...
notify { "F(${n})":
message => "F(${n}) == ${fn}",
require => Exec["${name}: F(${n})"],
}
}
}
}
}
# kick it off...
fibonacci { 'start':
n => 8,
}
It is available for download. Try to read through the code yourself first. As you’ll see, if called with n == 0, or n == 1, the function creates a file with this value and exits. This is the secret to how the function (the type) passes values around. It first stores them in files, and then loads them in through templates.
Each time this runs, Puppet will complete the next step in the execution. To make this successive execution automatic, I’ve written a small bash wrapper to do this, but you can run it manually too. If you do use my wrapper, use it with the fibonacci.pp file provided in git.
The computer scientist might notice that as a side effect, we are actually memoizing. This means that if we run this type again with a larger input value, the previously completed intermediate step values are used as a starting point for the subsequent computations. Cool!
The Puppet wizard might notice that I cheated slightly. Take a minute to try to see where…
![[IMAGE OF TIME PASSING]](https://ttboj.files.wordpress.com/2013/11/muppets-clock.png)
(IMAGE OF TIME PASSING)
To adapt our function (technically a type) to work in any environment, we need to do some more hacking! We can continue to use our exec type for saving, but a fact needs to be used to load in the necessary values:
require 'facter'
fibdir = '/tmp/fibonacci/'
valid_fibdir = fibdir.gsub(/\/$/, '')+'/' # ensure trailing slash
results = {} # create list of values
if File.directory?(valid_fibdir)
Dir.glob(valid_fibdir+'*').each do |f|
b = File.basename(f)
i = b.to_i # invalid returns 0
if b == '0' or i != 0
v = File.open(f, 'r').read.strip.to_i # read into int
results[i] = v
end
end
end
results.keys.each do |x|
Facter.add('pushing_fibonacci_'+x.to_s) do
setcode {
results[x]
}
end
end
The templates from the first version of this type need to be replaced with fact variable lookups:
# these are 'fact' lookups
$fn1 = getvar("pushing_fibonacci_${minus1}")
$fn2 = getvar("pushing_fibonacci_${minus2}")
You can use git to download all of this code as a module.
I hope you enjoyed this. Please let me know! Comment below, or send me a message.
Happy hacking,
James
P.S.: While I think this is fun, I wrote this hack to demonstrate some techniques, and to set the stage for future hacks, future techniques, and future Puppet examples. If you’re using this as a good way to actually compute values in the Fibonacci series, you’re insane!
P.P.S.: The word is actually memoization, not memorization, despite the similarities between the two words, and the two concepts.
P.P.P.S: Gluster users get extra points if they can figure out how this will lead to a feature for Puppet-Gluster. It’s a bit tricky to see if you’re not following my git commits.
The Technical Blog of James 