all posts tagged recursion

by on November 26, 2013

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:

$ ./
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(
	$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) ?, "r").read.to_i : -1) %>')
		$fn2 = inline_template('<%= f2=fibdir+"/"+minus2; (File.exist?(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 => [
					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…



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

	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 =, 'r').read.strip.to_i # read into int
			results[i] = v

results.keys.each do |x|
	Facter.add('pushing_fibonacci_'+x.to_s) do
		setcode {

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,


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.

by on November 17, 2013

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.


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(
) {
    # 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(
    $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.


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(",") %>'), ',')

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 %><%= {|x| "Hello "+x.capitalize}.join(", ") %>.<% end %>')

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

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.


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,