evaluation - How to make a function that evaluates an expression?

I'm trying to make a function where the input is an expression, but somehow it just won't be evaluated. For example, this little function doesn't work:

test[exp_] := Module[{x}, NestList[Function[x, exp], 2, 3]]
test[x^2]
(* {2, x^2, x^2, x^2} *)

And I would really like this output:

NestList[Function[x, x^2], 2, 3]
(* {2, 4, 16, 256} *)

Can anybody help?

Answer

Good question (and one that has bitten me in the past:) The reason for your troubles is the ways scoping of Function works. That's easiest to demonstrate with module however.

Module[{x},x]
(*x$642*)

You see that instead of x x$nnn was returned. For more info I recommend reading this.

Block has the expected behavior by the way:

Block[{x},x]
(*x*)

How about function? The file states:

A small test

test[exp_] := Function[x, exp]
test[x^2]

(*Function[x$, x^2]*)

So we see that the formal parameters of function have been renamed to x$ and no longer match the x you have put in. Here are some solutions:

Pass the function to your method

As has been suggested in the comments, you can pass the function as the argument.

ClearAll[test];
test[f_] := Module[{x}, NestList[f, 2, 3]]
test[#^2 &]
test[Function[x, x^2]]


(* ==> {2, 4, 16, 256} *)    
(* ==> {2, 4, 16, 256} *)

Pass the variables along with the expression

ClearAll@test
test[exp_, vars_] := Function[Evaluate@vars, exp]
test[x^2, x]
(*Function[x, x^2]*)

Or inserted into your original example

test[exp_, vars_] := NestList[Function[Evaluate@vars, exp], 2, 3]
test[x^2, x]
(*{2, 4, 16, 256}*)

Oh and if you give your function the HoldAll attribute, then it will not be bothered by existing assignments to x

SetAttributes[test, HoldAll]
test[exp_, vars_] := NestList[Function[vars, exp], 2, 3]
x = 5
test[x^2, x]
(*{2, 4, 16, 256}*)