Featured Whitepapers
- Peer Code Review: An Agile Process
- Learn Ways to Keep Schedules and Costs in Line With Requirements Change Management
- Java Deployments in an Enterprise Environment
- Challenges & Characteristics of Enterprise Continuous Integration
- Build Release Plans That Deliver Customer Value!
- Improving Traceability and Auditability Across the Development Lifecycle
Upcoming & Recent Webcasts
Home 
Ask Mr. Make Learning GNU Make Functions with Arithmetic
Ask Mr. Make Learning GNU Make Functions with Arithmetic
|
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:
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:
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:
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
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,
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:
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:
Now that we have a representation we can also define built-in functions for addition, increment and decrement:
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,
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:
Things get interesting when implementing subtraction. Before we get there, let's implement max and min functions:
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))
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.
A similar pattern works for subtraction:
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:
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):
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:
And here's what happens when they are not:
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:
And another when the first number is less than the second:
Similarly, it's possible to define “not equal” (ne), “less than” (lt) and “less than or equal” (lte) operators:
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:
It just strings together its second argument for however many x's there are in the first. For example,
Division is the most complex function of the lot because it uses recursion:
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:
(gte returns a non-empty string so that recursion happens)
(gte returns an empty string so no more recursion)
We can avoid recursion in the special case of division by 2; we define the halve function to be the opposite of double:
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:
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:
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,
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 8 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:
John Graham-Cumming is Founder and VP of Engineering 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.
Set as favorite
Bookmark
Email this
Hits: 23433 Trackback(0)Comments (3)
|
TrackBack URI for this entry
Subscribe to this comment's feed |
... I'm sorry, but this does not demonstrate the power of make's builtin functions. It demonstrates the extraordinary lengths one must go to in order to do what ought to be very simple things. For example, in Makefiles sometimes I want to join a list of strings by commas, *without* a trailing comma. Perhaps I'm being dense, but I can't figure out a convenient way to do it, and I think this represents a hole in the functionalities provided by make. Arithmetic is another hole. The problem is that the make authors can't just start adding functions, because then Makefiles using those functions won't be compatible with older makes. |
James MacMillan
said:
|
... I think John's answer might be; because he can. Seriously, I just used the encode, decode, increment and lt calls to implement automatically incrementing build numbers in a make file at work. Very useful stuff. It demonstrates the power of make's builtin functions quite well. Thanks John. |
Joe Jilini
said:
|
... What is the usefullness of doing arthmatics with a make tool, cant you use other ways to do it? |
Write comment
You must be logged in to post a comment. Please register if you do not have an account yet.
