Is there a way to get a macro to do an extra evaluation before returning its result?

Question

I’m trying to get get my macro to do an extra evaluation of its result before returning it. Can this be done without eval?

I'm trying to solve the problem in exercise 4 below:

3. Define a macro nth-expr that takes an integer n and an arbitrary number of expressions, evaluates the nth expression and returns its value. This exercise is easy to solve, if you assume that the first argument is a literal integer.

4. As exercise 3, but assume that the first argument is an expression to be evaluated.

It's easy to get the macro to pick the right expression:

(defmacro nth-expr% (n &rest es)
  `(nth ,n ',es))

CL-USER> (defvar i 1)
I
CL-USER> (nth-expr% (1+ i) (+ 2 3) (- 4 3) (+ 3 1))
(+ 3 1)

The expression (+ 3 1) is the one we want, but we want the macro to evaluate it to 4 before returning it.

It can of course be done with eval:

(defmacro nth-expr%% (n &rest es)
  `(eval (nth ,n ',es)))

CL-USER> (nth-expr%% (1+ i) (+ 2 3) (- 4 3) (+ 3 1))
4

But is there another way?

It feels like the solution should be to put the body of nth-expr% in a helper macro and have the top level macro only contain an unquoted call to this helper:

(defmacro helper (n es)
  `(nth ,n ',es))

(defmacro nth-expr (n &rest es) ; doesn't work!
  (helper n es))

The idea is that the call to helper would return (+ 3 1), and this would then be the expansion of the call to nth-expr, which at run-time would evaluate to 4. It blows up, of course, because N and ES get treated like literals.

Squint

Answer 1

That's not that easy.

Using eval is not good, since eval does not evaluate the code in the local lexical environment.

Remember, if we allow an expression to be evaluated to determine the number of another expression to execute, then we don't know this number at macro expansion time - since the expression could be based on a value that needs to be computed - for example based on some variable:

(nth-expression
   foo
 (bar)
 (baz))

So we might want to think about code which does that:

(case foo
  (0 (bar))
  (1 (baz)))

CASE is evaluating foo and then uses the result to find a clause which has the same value in its head. The consequent forms of that clause then will be evaluated.

Now we need to write code which expands the former into the latter.

This would be a very simple version:

(defmacro nth-expression (n-form &body expressions)
  `(case ,n-form
     ,@(loop for e in expressions
             and i from 0
             collect `(,i ,e))))

Question: what might be drawbacks of using CASE like that?

Tortile

I'll need a hint for the drawbacks of case. The only thing I could think of was the number of arguments limit, but that would also apply to nth-expression. – Squint

@Knuto: how would a CASE construct find a matching clause? – Tortile

Still stumped. The case construct does its matching in a cond, and the equality predicate used is eql, which should be fine in our case, since eql works with integers, and n-form should always evaluate to an integer. – Squint

I can see how run-time performance could be bad, since evaluating the 300th expression would involve 300 calls to eql before a match is found. – Squint

@Knuto: right. The linear search is the problem. Usually we would think that this may not be a real problem if there are only few choices. But we may also keep in mind that in Lisp code can easily be computed and may generate a lot of choices. – Tortile

Answer 2

Knuto: Rainer Joswig may be asking you to think about how the case statement works. Namely, that after evaluating the keyform (ie, the first argument), it will be compared sequentially to the key in each clause until a match is found. The comparisons could be time consuming if there are many clauses. You can discover this by carefully reading the entry for case in the Hyperspec (as he more than once has insisted I do):

The keyform or keyplace is evaluated to produce the test-key. Each of the normal-clauses is then considered in turn.

Also note that constructing many case clauses will add to the time to expand and compile the macro at compile time.

Regarding your use of eval in nth-expr%%, you can still achieve the effect of an eval by switching to apply:

(defmacro nth-expr%% (n &rest es)
  `(let ((ne (nth ,n ',es)))
     (apply (car ne) (cdr ne))))

But see Plugging the Leaks at http://www.gigamonkeys.com/book/macros-defining-your-own.html about a more robust treatment.

In general, a more efficient way to process the expressions is as a simple vector, rather than a list. (The problem statement does not rule out a vector representation.) While nth and case involve searching through the expressions one-by-one, a function like aref or svref can directly index into it. Assuming a vector of expressions is passed to the macro along with an index, perhaps first requiring (coerce expressions 'simple-vector) if a list, then the result can be computed in constant time no matter how many expressions there are:

(defmacro nth-expr%%% (n es)
  `(let ((ne (svref ',es ,n)))
     (apply (car ne) (cdr ne))))

so that now

(defvar i 1)

(nth-expr%%% (1+ i) #((+ 2 3) (- 4 3) (+ 3 1))) -> 4

Elbring

yes. But using EVAL or APPLY does not solve the problem, that there is no access to lexical environments. The expressions in the vector are s-expressions. Not code. The alternative when working with a vector, is to construct function objects from lambda expressions, put them into a vector, then later select the one with an aref operation (which does not involve search) and call funcall on the function. Now this opens another can of worms. What is it? – Tortile

@Rainer Joswig, Do the worms have something to do with any variables that happen to be included in the initial expressions, such that their values would need to be compiled into the corresponding functions (before funcalling at runtime)? – Elbring