Learning GNU Make Functions with Arithmetic

[article]

Now that we have a representation we can also define built-in functions for addition, increment and decrement:

    plus = $1 $2
increment = x $1
decrement = $(wordlist 2,$(words $1),$1)

So, the plus function just makes a list out of its two arguments; concatenation is enough to implement addition with the x's representation. increment just adds a single x to its argument. decrement strips the first x off of its argument by asking for the entire string of x's starting from index 2. For example,

    two := x x
three := x x x
four := x x x x
five := x x x x x
six := x x x x x x
all: ; @echo $(call decode,$(call plus,$(five),$(six)))

will output 11. Notice how we nested the call to plus inside a call to decode so that we output the number 11 instead of a list of 11 x's. Another simple function just doubles its argument:

    double = $1 $1

Things get interesting when implementing subtraction. Before we get there, let's implement max and min functions:

    max = $(subst xx,x,$(join $1,$2))
min = $(subst xx,x,$(filter xx,$(join $1,$2)))

The max function uses two GNU Make built-in functions: $(join) and $(subst). $(join LIST1,LIST2) takes two lists as arguments and joins the two lists together by concatenating the first element of LIST1 with the first element of LIST2 and so on through the list. If one list is longer than the other then the remaining items are just appended.

$(subst FROM,TO,LIST) runs through a list and substitutes elements that match a FROM pattern with the TO value. To see how max works consider the sequence of events in computing $(call max,$(five),$(six))

    $(call max,$(five),$(six))
=> $(call max,x x x x x,x x x x x x)
=> $(subst xx,x,$(join x x x x x,x x x x x x))
=> $(subst xx,x,xx xx xx xx xx x)
=> x x x x x x

First the $(join) joins the list with 5 x's with the list with 6 x's resulting in a list with 6 elements, the first five of which are xx. Then $(subst) is used to turn the first 5 xx's into x's. The final result is 6 x's, which is the maximum.

To implement min a similar trick is used, but we only keep the xx's and throw away the x's. The xx's represent where the two lists could be joined. There will only be xx's for the shorter of the two lists. The $(filter PATTERN,LIST) function runs through the list and removes elements that do not match the pattern.

    $(call min,$(five),$(six))
=> $(call min,x x x x x,x x x x x x)
=> $(subst xx,x,$(filter xx,$(join x x x x x,x x x x x x)))
=> $(subst xx,x,$(filter xx,xx xx xx xx xx x))
=> $(subst xx,x,xx xx xx xx xx)
=> x x x x x

A similar pattern works for subtraction:

    subtract = $(if $(call gte,$1,$2),                         \
$(filter-out xx,$(join $1,$2)), \
$(warning Subtraction underflow))

For a moment ignore the $(warning) and $(if) parts of the definition and focus on the $(filter-out). $(filter-out) is the opposite of $(filter): it removes elements from a list that match the pattern. So, following through an example, we can see that the $(filter-out) here implements subtraction:

    $(filter-out xx,$(join $(six),$(five)))
=> $(filter-out xx, $(join x x x x x x,x x x x x))
=> $(filter-out xx, xx xx xx xx xx x)
=> x

Unfortunately the same would work if 5 and 6 were reversed, so it is necessary to first check that the first argument is greater than or equal to the second. The $(if CONDITION,THEN,ELSE) function does whatever the THEN part says if the CONDITION is a non-empty string and the ELSE part if the CONDITION is an empty string. In our subtract definition the special function gte (greater than or equal) returns a non-empty string if its first argument is bigger than its second. We use that to decide whether to do the subtraction or output a warning message using $(warning).

The gte function is implemented using two other function for “greater than” (gt) and “equal” (eq):

     gt = $(filter-out $(words $2),$(words $(call max,$1,$2)))
eq = $(filter $(words $1),$(words $2))
gte = $(call gt,$1,$2)$(call eq,$1,$2)

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

Sep 22
Sep 24
Oct 12
Nov 09