SI413 Class 22: Macros vs. functions, applicative vs. normal order evaluation

Reading

Section 6.6.2 of Programming Language Pragmatics.

Homework

1. If you need to fetch the element 1/3rd of the way into an array range i..j frequently in a program, you might try a macro

   #define THIRD(A,i,j) A[i + (j-i)/3]
       

   or you might try an inline function

   inline int third(int *A, int i, int j) { return A[i + (j-i)/3]; }      
       

   1. What's the "inline" do?
   2. Fix the macro definition so that it's reliable.
   3. Are there any advantages to the macro?
   4. Why is it "THIRD(foo,a,b) = 4" will compile, but not "third(foo,a,b) = 4"

2. Why can't you make a macro out of:

   int gcd(int u, int v)
   {
     if (v == 0) 
       return u;
     return gcd(v,u%v);
   }
       

Recalling function evaluation vs. call site

The basic idea of a function in programming is that you have a function body, which is a chunk of code possibly containing references to some parameters, and potentially many call sites, which potentially include argument expressions. The fundamental issue is getting the arguments from the call site, called the actual parameters, bound to the associated names used in the function body, called the formal parameters.

Macros

It used to be quite common to use "macros" instead of functions, and you still see a lot of that kind of thing in C code. Understanding macros helps in understanding functions. The concept of a macro is simple replace a word or slightly more complicated pattern in a program with a new expression. For exaple, if you write

#define PI 3.14159

then following that macro, each occurrence of the text "PI" gets replaced with the text "3.14159" prior to compilation. Macros with patterns allow for something akin to functions. For example:

#define FOO(a,b) 0 < a && a < b && b < 1
if (FOO(1 - x*y, x + y) ---becomes---> if(0 < 1 - x*y && 1 - x*y < x + y && x + y < 1)

#define ODD(a) a & 1 int main() { int x,y,n; cin >> x >> y >> n; cout << (x + y*ODD(n)) << endl; } This totally doesn't work. If x=3,y=4,n=5 we get 3 + 4*5 & 1 ... and precdence ruins the whole thing.

#define ODD(a) (a & 1) int main() { int x,y,n; cin >> x >> y >> n; cout << (x + y*ODD(n)) << endl; } The extra parens fix the problem.

#define DIVIDES(a,b) (!(b%a)) int main() { int x,y; cin >> x >> y; cout << DIVIDES(x,y+1) << endl; } We got the outer parens, but there's still trouble, because we have an expression in the second slot, so we get (!(y + 1%x)) ... and once again precedence gets us!

#define DIVIDES(a,b) (!((b)%(a))) int main() { int x,y; cin >> x >> y; cout << DIVIDES(x,y+1) << endl; } We put each "argument" to the macro in enclosing parens to ensure that it doesn't mess with the expression we're generating.

So, textual substitution with macros has a lot of pitfalls. Why did anyone ever like it? Does it have any advantages over functions? Yes, it has advantages: macros avoid function calls. That means no stack manipulation or creation of frames or anything like that. So macros have always been popular for small jobs like the two above. However, C++ and C99 have an answer for that, they provide "inline" functions. The "inline" keyword is a hint to the compiler to try to substitute the function body into the surrounding program and avoid an actual function call, but to do this in a way that satisfies all the usual function semantics. So it has none of the pitfalls of a macro.

inline int divides(int a, int b) { return !(a % b); }

Note that this also makes the function implicitly static meaning that each compilation unit (file) can have its own definition, as opposed to a regular functions which allow only one definition for the whole program.

More differences between functions and macros

Suppose I have tuples (a1,a2) and (b1,b2) to compare lexicogrpahically. I might define the following macro:

#define LEXLESS(a1,a2,b1,b2) ((a1) < (b1) || (a1) == (b1) && (a2) < (b2))

int main()
{
  int x,y,u,v;
  cin >> x >> y >> u >> v;
  cout << LEXLESS(x,y,u,v) << endl;
}

This performs flawlessly; does exactly what we expect. Moreover, LEXLESS works great with any type that defines < and ==, so this work too:

double x,y,u,v; cin >> x >> y >> u >> v; cout << LEXLESS(x,y,u,v) << endl;

char x,y,u,v; cin >> x >> y >> u >> v; cout << LEXLESS(x,y,u,v) << endl;

string x,y,u,v; cin >> x >> y >> u >> v; cout << LEXLESS(x,y,u,v) << endl;

In other words, macros are generic. They produce code that work with any type that supports the operators that appear in the macro. In that sense, a regular old inline function is less powerful, since we would be forced to choose a type for the arguments. Of course C++ offers templates as a mechanism for producing generic code without resorting to macros:

<template T>
inline bool lexless(T a1,T a2,T b1,T b2) { return a1 < b1 || a1 == b1 && a2 < b2; }

At any rate, here's the final thing about this macro: let's use it slightly differently

#define LEXLESS(a1,a2,b1,b2) ((a1) < (b1) || (a1) == (b1) && (a2) < (b2)) int f(int k) { cout << "gotcha!" << endl; return k; } int main() { int x,y,u,v; cin >> x >> y >> u >> v; cout << LEXLESS(f(x),f(y),f(u),f(v)) << endl; }

> ./a.out 3 5 4 1 gotcha! gotcha! 1 > ./a.out 4 1 3 5 gotcha! gotcha! gotcha! gotcha! 0 > ./a.out 3 5 3 6 gotcha! gotcha! gotcha! gotcha! gotcha! gotcha! 1

What's going on here? Well, remember that we did textually replacement, which means that LEXLESS(f(x),f(y),f(u),f(v)) literally becomes

#define LEXLESS(a1,a2,b1,b2) ((f(x)) < (f(u)) || (f(x)) == (f(u)) && (f(y)) < (f(v)))

So if f(x) < f(u), short-circuit evaluation ensures we never evaluate anything else. If f(x) > f(u), we evaluate the (f(x)) < (f(u)) and get false, the evaluate (f(x)) == (f(u)) and get false again, at which point short-circuit evaluation takes over again. Notice we evaluated f(x) twice and f(u) twice. Finally in the other case we get six evaluations. Clearly, arguments to macros get evaluated differently than arguments to functions: at least functions in C/C++/Java/Scheme.

Applicative vs. Normal order evaluation

Functions in C/C++/Java/Scheme follow what's called applicative order evaluatiuon. That means that at a call site, we evaluate all of the actual parameters, bind them to the formal parameters, and only then do we evaluate the function. What macros do is called call-by-name, argument expressions are passed unevaluated to the macro body, and we only evaluate an argument expression if the corresponding formal parameter is encountered as the body is executed. Moreover, each time that formal parameter is encountered, we reevaluate the argument expression. An alternative way to handle the actual-formal parameter correspondence is to memoize call-by-name, i.e. evaluate an actual argument the first time the corresponding formal parameter is encountered, but rememeber that value for any subsequent encounters, rather than recomputing it. This is called normal order evaluation. Some languages, notably Haskell, use normal order evaluation. In a pure functional language with no side effects (referential transparency) it makes no difference in program behavior, and there is a potential time savings when some evaluations of a given function don't use every arguement.

Scheme: delay and force

Scheme has special form delay and a function force that allow one to pass unevaluated expressions around:

> (define foo (begin (display "Evaluating (+ 4 8)\n") (+ 4 8)))
Evaluating (+ 4 8)
> foo
12
> (define bar (delay (begin (display "Evaluating (+ 4 8)\n") (+ 4 8))))
> bar
#<promise>
> (force bar)
Evaluating (+ 4 8)
12
> (force bar)
12
> bar
#<promise!12>
> 

Notice that (+ 4 8) gets evaluated when foo is defined. However, due to the delay in the definition of bar, (+ 4 8) is not evaluated there. The result of the definition of bar is a "promise", i.e. an unevaluated form. To get the value you pass it to force. You can see from the printout that the first time you do this, (+ 4 8) is evaluted, while each subsequent time the value is simply remembered, not recomputed.