The Gluster Blog

Gluster blog stories provide high-level spotlights on our users all over the world

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.


  • 06 Dec 2020
    Looking back at 2020 – with g...

    2020 has not been a year we would have been able to predict. With a worldwide pandemic and lives thrown out of gear, as we head into 2021, we are thankful that our community and project continued to receive new developers, users and make small gains. For that and a...

    Read more
  • 27 Apr 2020
    Update from the team

    It has been a while since we provided an update to the Gluster community. Across the world various nations, states and localities have put together sets of guidelines around shelter-in-place and quarantine. We request our community members to stay safe, to care for their loved ones, to continue to be...

    Read more
  • 03 Feb 2020
    Building a longer term focus for Gl...

    The initial rounds of conversation around the planning of content for release 8 has helped the project identify one key thing – the need to stagger out features and enhancements over multiple releases. Thus, while release 8 is unlikely to be feature heavy as previous releases, it will be the...

    Read more