Learning Make with the Towers of Hanoi

[article]

disk from a to $*

and matches the % against c in a-c.D. This pattern is a rule that specifies how to move one disc from peg a to some other peg matched by %. When it runs it will print out

Move one disk from a to c

$* is an automatic variable set by GNU Make for this rule and it contains the value matched by the %, which GNU Make refers to as the stem. In this case the matching part was just the letter c. Since GNU Make only allows one % sign in the target of a pattern rule we have to write additional rules for moving a single disc from peg b and from peg c.

b-%.D: ; @echo Move one disk from b to $* c-%.D: ; @echo Move one disk from c to $*

To recap: GNU Make looks for explicit rules first, then searches for a pattern rule that uses the % wildcard and if it finds a match sets the $* variable for the part that matched the % sign. GNU Make has two ways of specifying the commands for a rule, the most familiar is the “line that starts with a tab” form:

foo.o: foo.c compileit

If there's only one command to run then the more compact “semicolon” form that's used in the puzzle Makefile can be used:

foo.o: foo.c ; compileit

It takes less space in the Makefile and has the added advantage that is can be copied and pasted without being concerned that the tab in the other form has been turned into spaces. Make GoalsNow consider a slightly more complex case, here we use the Makefile to solve the puzzle for two discs by running gmake DISCS=DD. In this case the all rule evaluates to

all: a-c.DD

and GNU Make looks for a rule to build a-c.DD. It finds another more complex pattern rule:

a-c.D%: ; @$(MAKE) a-b.$* a-c.D b-c.$*

In this case the % sign matches the second D in a-c.DD and $* will be set to that same single D. The command, when building a-c.DD is:

$(MAKE) a-b.D a-c.D b-c.D

which means “run make and build a-b.D, a-c.D and b-c.D.” The targets specified on the command-line of Make are called goals and they are built from left to right. That means that a-b.D will happen before a-c.D which will happen before b-c.D. In the language of Towers of Hanoi that means “move a disc from a to b then move a disc from a to c and finally move a disc from b to c” which is exactly what is required. Try tracing through the three disc case (DISCS=DDD). A Make goal is the name of any target specified in the Makefile (or a target that can be built by using a pattern rule) and directs Make to build that target (or targets). If no goal is specified then the first target seen in the Makefile is considered to be the goal. In the puzzle Makefile it's the phony target all. More Complex PatternsAlthough we don't use them in the example Makefile GNU Make has more complex pattern rules where a % sign can appear in the target and the prereq of the rule. A common example would be a rule for building a .o file from a .c:

%.o: %.c ; compileit

The two percent signs each have the same value: if we're building foo.o then this pattern would apply if there were a file called foo.c. The automatic variable $@ is set to the value of the file on the left-hand side

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