GNU Make has no built-in arithmetic capability. In this article, I present a collection of GNU Make macros that implement functions for addition, subtraction, multiplication, and division of integers. Functions are also provided for integer comparisons such as “greater than” and “not equal.” These macros are implemented entirely using GNU Make's built-in string manipulation functions.
GNU Make has no built-in arithmetic capability. In this article, I present a collection of GNU Make macros that implement functions for addition, subtraction, multiplication, and division of integers. Functions are also provided for integer comparisons such as “greater than” and “not equal.” These macros are implemented entirely using GNU Make's built-in string manipulation functions.
GNU Make provides good functionality for manipulating strings and through this article you will learn about the following: $(subst), $(filter), $(filter-out), $(words), $(wordlist), $(call), $(foreach), and $(if). You'll learn how GNU Make represents lists, and how to define and call your own functions.
In GNU Make a list is a string separated into list elements with spaces. For example, the following string:
foo “bar baz” bam
is a GNU Make list with four elements: foo, “bar, baz” and bam. Notice how GNU Make doesn't care about the quotation marks and splits the string simply on spaces. Because of this representation it is very hard to work with GNU Make functions that might be passed a path name containing spaces.
An example of a GNU Make function is $(words). In this example Makefile the variable LIST contains the four element list shown above and $(words) is used to find the number of elements in the list:
LIST := foo “bar baz” bam
all: ; @echo $(words $(LIST))
When run with GNU Make this Makefile outputs the number 4. There are two things to note here: firstly a function is called in GNU Make in a similar manner to a variable reference. GNU Make recognizes the function name because it is followed by a space. Secondly the arguments to the function, in this case $(LIST), are, in most cases, expanded before the function is called. So $(words $(LIST)) is the same as $(words foo “bar baz” bam). The $(words) function only has a single argument; other functions have multiple arguments separated by commas.
For example, the $(wordlist) function returns a sublist by specifying the start and end elements in the list. GNU Make lists are indexed with the first element being 1, so this example Makefile will print “bar baz” bam when run:
LIST := foo “bar baz” bam
all: ; @echo $(wordlist 2,4,$(LIST))
It asks for elements 2 through 4 of $(LIST). Here you can see that $(wordlist) has three arguments: the starting index, the ending index and the list itself. The arguments are separated by commas.
To create an arithmetic library in GNU Make we first need a representation of numbers. A simple way to represent a number is a list with the same number of items as the number being represented. For example, for the arithmetic library a number is a list of letter x's. So the number 5 is represented by
x x x x x
Given this representation we can use the $(words) function to convert from the internal form (all x's) to a human readable form. For example,
five := x x x x x
all: ; @echo $(words $(five))
will output 5. So the first user-defined function is decode which translates from the x's representation to a number. User-defined functions look like variable declarations. Here's decode:
decode = $(words $1)
To use decode in a Makefile we need the GNU Make function $(call) which can be used to call a user-defined function with a set of arguments. The arguments will be stored in temporary variables called $1, $2, $3, etc. In decode, which only takes a single argument, the number to decode, we just use $1:
five := x x x x x
all: ; @echo $(call decode,$(five))
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)
Gte will return a non-empty string if either of gt or eq do. The eq function is a bit of a mind bender. It works out the number of elements in its two elements and then treats one of them as a pattern and the other as a list and uses $(filter) to decide whether they are the same. Here's an example where they are equal:
$(call eq,$(five),$(five))
=> $(call eq,x x x x x,x x x x x)
=> $(filter $(words x x x x x),$(words x x x x x))
=> $(filter 5,5)
=> 5
And here's what happens when they are not:
$(call eq,$(five),$(six))
=> $(call eq,x x x x x,x x x x x x)
=> $(filter $(words x x x x x),$(words x x x x x x))
=> $(filter 5,6)
=>
So the $(filter) function acts as a kind of “string equality” operator; the two strings in our case are the lengths of the two number strings. The gt function is implemented in a similar way: it returns a non-empty string if the length of the first number string is not equal to the maximum of the two number strings. Here's an example:
$(call gt,$(six),$(five))
=> $(call gt,x x x x x x,x x x x x)
=> $(filter-out $(words x x x x x),
$(words $(call max,x x x x x x,x x x x x)))
=> $(filter-out $(words x x x x x),$(words x x x x x x))
=> $(filter-out 5,6)
=> 6
And another when the first number is less than the second:
$(call gt,$(five),$(six))
=> $(call gt,x x x x x,x x x x x)
=> $(filter-out $(words x x x x x x),
$(words $(call max,x x x x x x,x x x x x)))
=> $(filter-out $(words x x x x x x),$(words x x x x x x))
=> $(filter-out 6,6)
=>
Similarly, it's possible to define “not equal” (ne), “less than” (lt) and “less than or equal” (lte) operators:
lt = $(filter-out $(words $1),$(words $(call max,$1,$2)))
ne = $(filter-out $(words $1),$(words $2))
lte = $(call lt,$1,$2)$(call eq,$1,$2)
Just three more functions to define and we've got a pretty powerful package: multiply, divide and encode. The first two are clear, the last as a way to create a number string of x's from a integer; we'll leave that to last and then implement a simple calculator in GNU Make.
Multiplication uses the $(foreach VAR,LIST,DO) function. It sets that variable named VAR to each element of LIST and does whatever DO says. So multiplication is easy to implement:
multiply = $(foreach a,$1,$2)
It just strings together its second argument for however many x's there are in the first. For example,
$(call multiply,$(two),$(three))
=> $(call multiply,x x,x x x)
=> $(foreach a,x x,x x x)
=> x x x x x x
Division is the most complex function of the lot because it uses recursion:
divide = $(if $(call gte,$1,$2), \
x $(call divide,$(call subtract,$1,$2),$2),)
If its first argument is less than its second then division returns 0 because the ELSE part of the $(if) is empty (see the ,) at the end). If division is possible then divide works by repeated subtraction of the second argument from the first using the subtract function. Each time it subtracts it adds an x and calls divide again. Here's an example:
$(call divide,$(three),$(two))
=> $(call divide,x x x,x x)
=> $(if $(call gte,x x x,x x),
x $(call divide,$(call subtract,x x x,x x),x x),)
(gte returns a non-empty string so that recursion happens)
=> x $(call divide,$(call subtract,x x x,x x),x x)
=> x $(call divide,x,x x)
=> x $(if $(call gte,x,x x),
x $(call divide,$(call subtract,x,x x),x x),)
(gte returns an empty string so no more recursion)
=> x
We can avoid recursion in the special case of division by 2; we define the halve function to be the opposite of double:
halve = $(subst xx,x, \
$(filter-out xy x y, \
$(join $1,$(foreach a,$1,y x))))
By now you've seen all the functions used as part of halve; work through an example, say $(call halve,$(five)) to see how it works.
So, the only tricky thing to do is turn a number entered by the user into a string of x's. The encode function does this by chopping out a substring of x's from a predefined list of x's:
16 := x x x x x x x x x x x x x x x
input_int := $(foreach a,$(16), \
$(foreach b,$(16), \
$(foreach c,$(16),$(16)))))
encode = $(wordlist 1,$1,$(input_int))
Here we are limited to being able to enter numbers up to 65536. Once we've got the number in the encoding, only available memory limits the size of integers we can work with.
To really show off this library here's an implementation of a reverse polish notation calculator written entirely in GNU Make functions:
stack :=
push = $(eval stack := $$1 $(stack))
pop = $(word 1,$(stack))$(eval stack := $(wordlist 2,$(words \
$(stack)),$(stack)))
pope = $(call encode,$(call pop))
pushd = $(call push,$(call decode,$1))
comma := ,
calculate = $(foreach t,$(subst $(comma), ,$1),$(call \
handle,$t))$(stack)
seq = $(filter $1,$2)
handle = $(call pushd, \
$(if $(call seq,+,$1), \
$(call plus,$(call pope),$(call pope)), \
$(if $(call seq,-,$1), \
$(call subtract,$(call pope),$(call pope)), \
$(if $(call seq,*,$1), \
$(call multiply,$(call pope),$(call pope)), \
$(if $(call seq,/,$1), \
$(call divide,$(call pope),$(call pope)), \
$(call encode,$1))))))
.PHONY: calc
calc: ; @echo $(call calculate,$(calc))
You'll need to be using GNU Make 3.80 or later for this to work. The operators and numbers are passed into GNU Make in the calc variable separated by commas. For example,
make calc="1,3,-,3,21,5,*,+,/"
Will output 54. Clearly, that's not what GNU Make was designed for, and I don't have space here to explain how the calculator transforms its input into calls to our plus, minus,multiply and divide functions, but I hope I've shown you the power of GNU Make functions.
Now go read chapter eight of the GNU Make manual to learn about the other functions that I have not touched on here.
Appendix
Here's the complete commented Makefile:
# input_int consists of 65536 x's built from the 16 x's in 16
16 := x x x x x x x x x x x x x x x
input_int := $(foreach a,$(16),$(foreach b,$(16),$(foreach c,$(16),$(16)))))
# decode turns a number in x's representation into a integer for human
# consumption
decode = $(words $1)
# encode takes an integer and returns the appropriate x's
# representation of the number by chopping $1 x's from the start of
# input_int
encode = $(wordlist 1,$1,$(input_int))
# plus adds its two arguments, subtract subtracts its second argument
# from its first iff this would not result in a negative result.
plus = $1 $2
subtract = $(if $(call gte,$1,$2), \
$(filter-out xx,$(join $1,$2)), \
$(warning Subtraction underflow))
# multiply multiplies its two arguments and divide divides it first
# argument by its second
multiply = $(foreach a,$1,$2)
divide = $(if $(call gte,$1,$2), \
x $(call divide,$(call subtract,$1,$2),$2),)
# max returns the maximum of its arguments and min the minimum
max = $(subst xx,x,$(join $1,$2))
min = $(subst xx,x,$(filter xx,$(join $1,$2)))
# The following operators return a non-empty string if their result
# is true:
#
# gt First argument greater than second argument
# gte First argument greater than or equal to second argument
# lt First argument less than second argument
# lte First argument less than or equal to second argument
# eq First argument is numerically equal to the second argument
# ne First argument is not numerically equal to the second argument
gt = $(filter-out $(words $2),$(words $(call max,$1,$2)))
lt = $(filter-out $(words $1),$(words $(call max,$1,$2)))
eq = $(filter $(words $1),$(words $2))
ne = $(filter-out $(words $1),$(words $2))
gte = $(call gt,$1,$2)$(call eq,$1,$2)
lte = $(call lt,$1,$2)$(call eq,$1,$2)
# increment adds 1 to its argument, decrement subtracts 1. Note that
# decrement does not range check and hence will not underflow, but
# will incorrectly say that 0 - 1 = 0
increment = $1 x
decrement = $(wordlist 2,$(words $1),$1)
# double doubles its argument, and halve halves it
double = $1 $1
halve = $(subst xx,x,$(filter-out xy x y,$(join $1,$(foreach a,$1,y x))))
# This code implements a reverse polish notation calculator by
# transforming a comma-separated list of operators (+ - * /) and
# numbers stored in the calc variable into the appropriate calls to
# the arithmetic functions defined in this Makefile
# This is the current stack of numbers entered into the
# calculator. The push function puts an item onto the top of the stack
# (the start of the list) and pop removes the top item.
stack :=
push = $(eval stack := $$1 $(stack))
pop = $(word 1,$(stack))$(eval stack := $(wordlist 2,$(words $(stack)),$(stack)))
# pope and pushd are used to pop a number off the stack and encode it
# and push a number onto the stack after decoding
pope = $(call encode,$(call pop))
pushd = $(call push,$(call decode,$1))
# calculate runs through the input numbers and operations and either
# pushes a number on the stack, or pops two numbers off and does a
# calculation followed by pushing the result back. When calculate
# finished there will be one item on the stack which is the result.
comma := ,
calculate=$(foreach t,$(subst $(comma), ,$1),$(call handle,$t))$(stack)
# seq is a string equality operator that returns true (a non-empty
# string) if the two strings are equal
seq = $(filter $1,$2)
# handle is used by calculate to handle a single token. If it's an
# operator then the appropriate operator function is called, if it's a
# number then it is pushed.
handle = $(call pushd, \
$(if $(call seq,+,$1), \
$(call plus,$(call pope),$(call pope)), \
$(if $(call seq,-,$1), \
$(call subtract,$(call pope),$(call pope)), \
$(if $(call seq,*,$1), \
$(call multiply,$(call pope),$(call pope)), \
$(if $(call seq,/,$1), \
$(call divide,$(call pope),$(call pope)), \
$(call encode,$1))))))
.PHONY: calc
calc: ; @echo $(call calculate,$(calc))
