Advanced recursion and memoization in Puppet

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]

(IMAGE OF TIME PASSING)

Have you figured it out? The problem with the current implementation is that it will only work when run locally as a standalone Puppet program. The reason, is that exec types run on the client, and the templates run on the server. This type requires that both of those elements run on the same machine so that the save/load memoization can work correctly. Since this code runs on the same machine, this isn’t a problem! This split execution model is one of the features that can confuse new Puppet users.

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.

Advertisements

Iteration in Puppet

People often ask how to do iteration in Puppet. Most Puppet users have a background in imperative programming, and are already very familiar with for loops. Puppet is sometimes confusing at first, because it is actually (or technically, contains) a declarative, domain-specific language. In general, DSL’s aren’t always Turing complete, nor do they need to support loops, but this doesn’t mean you can’t iterate.

Until recently, Puppet didn’t have an explicit looping construct, and it is quite possible to build complex modules without using this new construct. There are even some who believe that the language shouldn’t even contain this feature. I’ll abstain from that debate for now, but instead, I would like to show you some iteration techniques that you can use to get your desired result.

Recursion

puppets-all-the-way-downMany people forget that recursion is a form of iteration. Even more don’t realize that you can do recursion in Puppet:

#!/usr/bin/puppet apply

define recursion(
    $count
) {
    # do something here...
    notify { "count-${count}":
    }
    $minus1 = inline_template('<%= count.to_i - 1 %>')
    if "${minus1}" == '0' {
        notify { 'done counting!':
        }
    } else {
        # recurse
        recursion { "count-${minus1}":
            count => $minus1,
        }
    }
}

# kick it off...
recursion { 'start':
    count => 4,
}

If you really want to Push Puppet, even more advanced recursion is possible. In general, I haven’t found this technique very useful for module design, but it’s worth mentioning as a form of iteration. If you do find a legitimate use of this technique, please let me know!

Type iteration

We’re used to seeing simple type declarations such as:

user { 'james':
    ensure => present,
    comment => 'james is awesome!',
}

In fact, the namevar can actually accept a list:

$users = ['kermit', 'beaker', 'statler', 'waldorf', 'tom']
user { $users:
    ensure => present,
    comment => 'who gave these muppets user accounts?',
}

Which will cause Puppet to effectively iterate across the elements in $users. This is the most important type of iteration in Puppet. Please get familiar with it.

This technique can be used with any type. It can even be used to express a many-to-one dependency relationship:

# where $bricks is a list of gluster::brick names
Gluster::Brick[$bricks] -> Gluster::Volume[$name]    # volume requires bricks

Suppose you’d like to use type iteration, but you’d also like to know the index of each element. This can be useful to avoid duplicate sub-types, or to provide a unique index:

define some_module::process_array(
    $foo,
    $array    # pass in the original $name
) {
    #notice(inline_template('NAME: <%= name.inspect %>'))

    # do something here...

    # build a unique name...
    $length = inline_template('<%= array.length %>')
    $ulength = inline_template('<%= array.uniq.length %>')
    if ( "${length}" != '0' ) and ( "${length}" != "${ulength}" ) {
        fail('Array must not have duplicates.')
    }
    # if array had duplicates, this wouldn't be a unique index
    $index = inline_template('<%= array.index(name) %>')

    # iterate, knowing your index
    some::type { "${foo}:${index}":
        foo => 'hello',
        index => "${index}",
    }
}

# a list
$some_array = ['a', 'b', 'c']    # must not have duplicates

# using the type requires that you pass in $some_array twice!
some_module::process_array { $some_array:    # array
    foo => 'bar',
    array => $some_array,    # same array as above
}

While this example might seem contrived, it is actually a modified excerpt from a module that I wrote.

create_resources

This is a similar technique for when you want to specify different arguments for each type:

$defaults = {
    ensure => present,
    comment => 'a muppet',
}
$data = {
    'kermit' => {
        comment => 'the frog',
    },
    'beaker' => {
        comment => 'keep him away from your glassware',
    },
    'fozzie' => {
        home => '/home/fozzie',
    },
    'tom' => {
        comment => 'the swedish chef',
    }
}
create_resources('user', $data, $defaults)

This creates each user resource with its own arguments. If an argument isn’t given in the $data, it is taken from the $defaults hash. A similar example, and the official documentation is found here.

Template iteration

You might want to iterate to perform a simple computation, or to modify an array in some way. For static value computations, you can often use a template. Remember that the template will get executed at compile time on the Puppet Master, so code accordingly. Here are a few contrived examples:

# filter out all the integers less than zero
$array_in = [-4,3,-8,-2,1,4,-2,1,5,-1,-7,9,-3,2,6,-8,5,3,5,-6,8,9,7,-5,9,3,-3]
$array_out = split(inline_template('<%= array_in.delete_if {|x| x < 0 }.join(",") %>'), ',')
notice($array_out)

We can also use the ruby map:

# build out a greeting string
$names = ['animal', 'gonzo', 'rowlf']
# NOTE: you can also use a regular multi-line template for readability
$message = inline_template('<% if names == [] %>Hello... Anyone there?<% else %><%= names.map {|x| "Hello "+x.capitalize}.join(", ") %>.<% end %>')
notice($message)

Use your imagination! Remember that you can also write a custom function if necessary, but first check that there isn’t already a built-in function, or a stdlib function that suits your needs.

Advanced template iteration

When you really need to get fancy, it’s often time to call in a custom function. Custom functions require that you split them off into separate files, and away from the module logic, instead of keeping the functions inline and accessible as lambdas. The downside to using these “inline_template” lambdas instead, is that they can quickly turn into parlous one-liners.

# transform the $data hash
$data = {
    'waldorf' => {
        'heckles' => 'absolutely',
        'comment' => 'a critic',
    },
    'statler' => {
        'heckles' => 'all the time',
        'comment' => 'another critic!',
    },
}
# rename and filter on the 'heckles' key
$yaml = inline_template('<%= data.inject({}) {|h, (x,y)| h[x] = {"applauds" => y.fetch("heckles", "yes")}; h}.to_yaml %>')
$output = parseyaml($yaml) # parseyaml is in the puppetlabs-stdlib
notice($output)

As with simple template iteration, the key problem is transferring the data in and out of the template. In the simple case, arrays can be joined and split as long as there is a reserved character that won’t be used in the data. For the advanced template iteration, we rely on the YAML transformation functions.

Some reminders

If you properly understand the functionality that your module is trying to model/manage, you can usually break it up into separate classes and defined types, such that re-use via type iteration can fulfill your needs. Usually you’ll end up with a more properly designed module.

Test using the same version of Ruby that will run your module. Newer versions of Ruby have some incompatible changes, and new features, with respect to older versions of Ruby.

Remember that templates and functions run on the Puppet Master, but facts and types run on the client (agent).

The Puppet language is mostly declarative. Because this might be an unfamiliar paradigm, try not to look for all the imperative features that you’re used to. Having a programming background can help, because there’s certainly programming mixed in, whether you’re writing custom functions, or erb templates.

Future parser

For completeness, I should mention that the future parser now supports native iteration. If you need it, it probably means that you’re writing a fairly advanced module, and you’re comfortable manual diving. If you have a legitimate use case that isn’t possible with the existing constructs, and isn’t only a readability improvement, please let me know.

Conclusion

I hope you enjoyed this article. The next time someone asks you how to iterate in Puppet, feel free to link them this way.

Happy hacking,

James

recursion in puppet (for no particular reason)

I’m working on some fancy puppet “code”, and I realized recursion could be very useful. I decided to try out a little hack to see if I could get it to work. I’ll jump right into the code:

#!/usr/bin/puppet

define recursion(
    $count
) {
    notify { "count-${count}":
    }
    $minus1 = inline_template('<%= count.to_i - 1 %>')
    if "${minus1}" == '0' {
        notify { 'done counting!':
        }
    } else {
        # recurse
        recursion { "count-${minus1}":
            count => $minus1,
        }
    }
}

# kick it off...
recursion { 'start':
    count => 4,
}

In theory, this should now work because of local variable scopes. Let’s see if we’ll blow up the puppet stack or not…

[james@computer tmp]$ ./rec.pp 
warning: Implicit invocation of 'puppet apply' by passing files (or flags) directly
to 'puppet' is deprecated, and will be removed in the 2.8 series.  Please
invoke 'puppet apply' directly in the future.

notice: count-4
notice: /Stage[main]//Recursion[start]/Notify[count-4]/message: defined 'message' as 'count-4'
notice: count-2
notice: /Stage[main]//Recursion[start]/Recursion[count-3]/Recursion[count-2]/Notify[count-2]/message: defined 'message' as 'count-2'
notice: count-3
notice: /Stage[main]//Recursion[start]/Recursion[count-3]/Notify[count-3]/message: defined 'message' as 'count-3'
notice: count-1
notice: /Stage[main]//Recursion[start]/Recursion[count-3]/Recursion[count-2]/Recursion[count-1]/Notify[count-1]/message: defined 'message' as 'count-1'
notice: done counting!
notice: /Stage[main]//Recursion[start]/Recursion[count-3]/Recursion[count-2]/Recursion[count-1]/Notify[done counting!]/message: defined 'message' as 'done counting!'
notice: Finished catalog run in 0.16 seconds
[james@computer tmp]$

…and amazingly this seems to work! Hopefully this will be useful for some upcoming trickery I have planned, and if not, it was a fun hack.

I decided to see if it could handle larger values, and for my simple tests, it seemed to do okay:

notice: /Stage[main]//Recursion[start]/Recursion[count-99]/Recursion[count-98]/Recursion[count-97]/Recursion[count-96]/Recursion[count-95]/Recursion[count-94]/Recursion[count-93]/Recursion[count-92]/Recursion[count-91]/Recursion[count-90]/Recursion[count-89]/Recursion[count-88]/Recursion[count-87]/Recursion[count-86]/Recursion[count-85]/Recursion[count-84]/Recursion[count-83]/Recursion[count-82]/Recursion[count-81]/Recursion[count-80]/Recursion[count-79]/Recursion[count-78]/Recursion[count-77]/Recursion[count-76]/Recursion[count-75]/Recursion[count-74]/Recursion[count-73]/Recursion[count-72]/Recursion[count-71]/Recursion[count-70]/Recursion[count-69]/Recursion[count-68]/Recursion[count-67]/Recursion[count-66]/Recursion[count-65]/Recursion[count-64]/Recursion[count-63]/Recursion[count-62]/Recursion[count-61]/Recursion[count-60]/Recursion[count-59]/Recursion[count-58]/Recursion[count-57]/Recursion[count-56]/Recursion[count-55]/Recursion[count-54]/Recursion[count-53]/Recursion[count-52]/Recursion[count-51]/Recursion[count-50]/Recursion[count-49]/Recursion[count-48]/Recursion[count-47]/Recursion[count-46]/Recursion[count-45]/Recursion[count-44]/Recursion[count-43]/Recursion[count-42]/Recursion[count-41]/Recursion[count-40]/Recursion[count-39]/Recursion[count-38]/Recursion[count-37]/Recursion[count-36]/Recursion[count-35]/Recursion[count-34]/Recursion[count-33]/Recursion[count-32]/Recursion[count-31]/Recursion[count-30]/Recursion[count-29]/Recursion[count-28]/Recursion[count-27]/Recursion[count-26]/Recursion[count-25]/Recursion[count-24]/Recursion[count-23]/Recursion[count-22]/Recursion[count-21]/Recursion[count-20]/Recursion[count-19]/Recursion[count-18]/Recursion[count-17]/Recursion[count-16]/Recursion[count-15]/Recursion[count-14]/Recursion[count-13]/Recursion[count-12]/Recursion[count-11]/Recursion[count-10]/Recursion[count-9]/Recursion[count-8]/Recursion[count-7]/Recursion[count-6]/Recursion[count-5]/Recursion[count-4]/Recursion[count-3]/Recursion[count-2]/Recursion[count-1]/Notify[done counting!]/message: defined 'message' as 'done counting!'
notice: Finished catalog run in 1.16 seconds

Running this with a count value of 1000 took 132.19 sec according to puppet, but much longer for the process to actually clean up and finish. This made my fan speed up, but at least it didn’t segfault.

Hopefully I’ll have something more useful to show you next time, but until then, keep on imagining and,

Happy hacking!

James

EDIT: A follow up is now available.