Learning Make with the Towers of Hanoi

[article]

per disc. For example if DISCS is DDD then this Makefile will solve the puzzle for 3 discs. We use this encoding (perhaps you'd call it a hack) because GNU Make does not include any facility for doing arithmetic. Here's a sample run for three discs:

% gmake DISCS=DDD Move one disk from a to c Move one disk from a to b Move one disk from c to b Move one disk from a to c Move one disk from b to a Move one disk from b to c Move one disk from a to c

Variable PrecedenceNotice how the value of the DISCS variable was specified on the command-line, overriding the definition of DISCS on the Makefile's first line. Another way to specify DISCS is in the environment. In bash if you do

% export DISCS=DDD % gmake Move one disk from a to b Move one disk from a to c Move one disk from b to c

you'll perhaps be surprised that the environment variable value of DISCS has been discarded and the value on the first line of the Makefile has been used (in this case DD and the two disc puzzle is solved). That's because GNU Make has a strict order in which it considers variables: A command-line definition takes precedence over...A Makefile definition which take precedence over...
An environment variable. If we want to switch the order of the last two, so that the environment takes precedence over definitions in the Makefile we run with the -e switch:

% export DISCS=DDD % gmake -e Move one disk from a to c Move one disk from a to b Move one disk from c to b Move one disk from a to c Move one disk from b to a Move one disk from b to c Move one disk from a to c

Phony TargetsThe first rule in the Makefile is for a target called all. There's also a line which specifies that all is phony. Normally, GNU Make considers targets to be actual files, marking a target as phony means that GNU Make treats the target as simply a name, and doesn't check to see if a file with the same name exists. If a target is not phony then GNU Make will check to see if the target exists to decide whether a rule needs to be run. Since we want our Makefile to always run the all rule, since it's the rule that fires off the Towers of Hanoi solution we mark it as phony. Even if there's a file called all the all rule runs. A Simple PatternIf we start with the simplest case, one disc, we can trace through the Makefile to see what happens when we type gmake DISCS=D. The all rule has a dependency on a-c.$(DISCS) and since DISCS is D that means the rule is equivalent to:

all: a-c.D

To build all we need to build a-c.D. To encode the different disc moves in the Makefile I've used targets in the form -.. So a-c.D means move one disc (the single D) from peg a to peg c. To build a-c.D GNU Make searches for an explicit rule to make it, that is a rule whose target is a-c.D. There isn't one in the Makefile so GNU Make searches for a pattern rule that applies. A pattern rule is a rule whose target contains a percent sign. The percent sign acts as a wildcard and matches any string (including the empty string). GNU Make finds the following matching rule:

a-%.D: ; @echo Move one

About the author

John Graham-Cumming's picture John Graham-Cumming

John Graham-Cumming is Co-Founder at Electric Cloud, Inc . Prior to joining Electric Cloud, John was a Venture Consultant with Accel Partners, VP of Internet Technology at Interwoven, Inc. (IWOV), VP of Engineering at Scriptics Corporation (acquired by Interwoven), and Chief Architect at Optimal Networks, Inc. John holds BA and MA degrees in Mathematics and Computation and a Doctorate in Computer Security from Oxford University. John is the creator of the highly acclaimed open source POPFile project. He also holds two patents in network analysis and has others pending.

AgileConnection is one of the growing communities of the TechWell network.

Featuring fresh, insightful stories, TechWell.com is the place to go for what is happening in software development and delivery.  Join the conversation now!

Upcoming Events

Nov 09
Nov 09
Apr 13
May 03