June 2002

Macros and Higher Order Methods

Introduction

This document explores the types of higher order methods and how macros are special.

Every "method" has three aspects, and each of these aspects can act as a handle for other parts of a program. It is important to know of these three aspects and their role in providing language expressibility.

Method Aspects

Return Value - The most used aspect of a method is the value it returns. The common use of this aspect is revealed by the semantic efficiency granted to it by most languages.

f₁(g(x=4, y=7))
f₂(h())

Here we are not referring to the methods, but the values that they can give us.

Method Itself - This is the act of passing methods for their ability to provide action. Being able to pass methods in this way means methods can be treated as "first order" and the methods that act on methods are called "second order" or "higher order" methods. Passing a method can take the form of the method's name, or in the form of a lamda. Lambda form shares some of macros' benefits, namely access to lexically scoped variables.

f₃(g, x=4, y=7)     //f₃ will simply call g with given parameters
f₄(g)               //f₄ may be getting g's parameters from the user
f₅(h)               //another example

Please note the difference between "h()", which is a (return) value, and "h" which is a method.

Method Specification - This is the ability to pass method specifications (source code) to other methods. Passing source code as a parameter to another method allows for great semantic efficiency over passing the method itself. The programmer can take advantage of lexical scope to reduce the number of explicit parameters that pass between the callee and caller.

This requires a more detailed discussion on Macros. Macros are simply specifications that allow one or more method specifications as parameters.

Macros are Useful

It may not be clear yet that macros and the ability to pass method specifications are even useful. The following will use an example how macros can extend a language in a minor way. We will also see that macros, like methods in general, are an abstraction point; allowing an interface contract separate from the implementation. (The implementation can be changed to suit the needs of the environment).

Using Macros to make Java Collections

Java (1.4 and earlier) makes it difficult to perform operations over a collection. Here is an example that will print and count the objects in MySet.

int count=0
Iterator iterator=MySet.iterator();
while(iterator.hasNext())
     Object object=iterator.next();
     System.out.println(""+object);
     count++;
//for

The need to manipulate an iterator each time is quite painful. It would be much nicer if we could do something similar to what Ruby or Python do:

int count=0
forall(object in MySet)
     System.out.println(""+object);
     count++;
//for

This is nice, but forall requires pattern identification and changes to the language parser. Instead, if we focus our attention on just the important parameters for this language feature. We notice three features: the free variable (object), the set (MySet), and the code to run. We can make our parsing easier by demanding that macro calls look like methods. We will quote source code in curly braces for clarity,

int count=0
forAll(object, MySet,
     System.out.println(""+object);
     count++;
)//for

Here you can see the advantage of macro's lexical scoping rules. Notice that if this same functionality was to be done with a plain second order method the count variable would also have to be passed into the body of the loop in order to update it.

The macro definition, in an appropriate language, would look something like:

MACRO forAll(variable AS Field, set AS Field, body AS Code)
     Iterator iterator=*set.iterator();
     while(iterator.hasNext())
          Object *variable=iterator.next();
          *body
     //for
//forAll

Notice that I use the * prefix to escape or unquote the parameters so I can distinguish between them and source code that might contain identical substrings. Choosing an appropriate escape character depends on the language you are quoting.

The macro definition looks like a method specification, but instead is a source code specification. The specification is not a series of instructions, but instead a series of concatenations. As you can imagine, the resulting code must be valid. If we were to make the same in Java we can see the majority of the macro commands are just code concatenation.

public String forAll(String variable, String set, String body)
     return "Iterator iterator="+set+ ".iterator();\n"+
     "while(iterator.hasNext())"+
          "Object "+variable+"=iterator.next();\n"
         body+
     "//for\n"
//for

Of course this Java version does not have any automated checks on the input parameters or the output parameters and we would still need a compiler to make the code useful.

Summary

Macros have two distinct advantages over higher order methods:

• Lexical variables are accessible - Macros use the lexically scoped variables as parameters, so they do not have to pass variables into the method body explicitly.
• Methods passed to macros do not require names or explicit definition - Simple quotation "" provides enough context to know that a method body is expected.

Macros are only advantageous in a context that has lexical scope. Therefore macros should be handled completely by the human (language) interface and not the underlying computing environment.

mar 2009, removed DBOS reference

june 2002, first draft