Jim Suruda

CIS 624 Extra Credit #7

The C preprocessor expands macros using a process superficially similar to beta reduction but that does not rename bound variables. Write a C macro which illustrates the problem of name capture. Try the same macro in Scheme and compare the results.

Part I: C macros

I wrote a macro in C that prints out the numbers from 1 to N:

#define count(N) {int i; for (i=1;i<=N;i++) {printf(" %d", i);} printf("\n");}

This macro works anywhere in a C program, and the compiler does not complain at all. But, it causes problems in this little program:

#include <stdio.h>

/* Count from 1 to n */
#define count(N) {int i; for (i=1;i<=N;i++) {printf(" %d", i);} printf("\n");}

int main()
{
  int i;

  printf("1 through 10:\n");
  count(10);

  printf("Counting practice:\n");
  for (i=0; i<10; i++) {
    count(i);
    }
}

The output:

 
1 through 10:
 1 2 3 4 5 6 7 8 9 10
Counting practice:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 
 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 
 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106  ...

Before my code compiles, the preprocessor expands the macro into in-line code. It replaces each occurrence of the formal parameter N in the macro with the actual argument, i. So, the loop in main becomes:

 
printf("Counting practice:\n");
  for (i=0; i<10; i++) {
{int i; for (i=1;i<=i;i++) {printf(" %d", i);} printf("\n");}
    }

Since the preprocessor did not rename the variables in the macro, the loop condition becomes i<=i, which never terminates. So, the macro can cause trouble if it is used in a block of code where i has already been defined.

Part II: Scheme macros

Here is the same macro in Scheme:

 
(define-syntax count
 (syntax-rules ()
  ((count number ...)
   (do ((i 1 (+ i 1)))
    ((> i number ...) 
     (newline))
    (write i)
    (write-char #\ ))
)))))

Which works well by itself:

> (count 10) 1 2 3 4 5 6 7 8 9 10

Now, here is a Scheme version of the problematic C program, which works just fine:

 
> (do ((i 0 (+ i 1)))
      ((> i 10)
      (write "all finished"))
      (count i)))

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
Scheme is not quite as dumb about macro expansion as C. The Scheme interpreter uses "hygienic rewrite rules" (that’s what they call it in Revised Report 4, page 42) to ensure referential transparency. If C were to rename variables in macros before it expanded them , then it could avoid these sort of problems. I thought about doing the same experiment with Java, but I don’t think Java supports macros. At least, I can’t find any information about Java macros anywhere...