How does Return work?

Question

It is not completely clear to me how Return[] works.

The documentation says:

Return[expr] returns the value expr from a function.

But in Mathematica it is not clear where are the boundaries of a "function" defined using patterns and Set(Delayed). The system simply applies replacement rules until there's nothing to change anymore.

Consider these examples:

a := (Module[{}, Return[0]; 1]; 2)    
a
(* 0 *)

It is not completely clear to me why Return breaks out from a, and not from Module or one of the CompoundExpression.

The following doesn't work, and simply returns the Return expression. It reminds me a bit of how Unevaluated is handled.

(Module[{}, Return[0]; 1]; 2)
(* Return[0] *)

If we add another layer of definitions, the effect of Return will stop there:

b := (a; 3)
(* 3 *)

Why do these three inputs give different results? What is the general rule for deciding where Return breaks out to precisely?

The answer lies somewhere in fully understanding the evaluation process.

Would someone care to elucidate this point, perhaps with pointers to the parts of the documentation which make this clear?

Answer 1

The exhaustive answer to this has been given in this thread (if you combine several answers there. The mentioned thread is also a generally recommended read for more information on this - at least one I am aware of). I will first reproduce here those bits of my answer from there which were correct.

There are two possible outcomes for any expression wrapped in Return: either it is inside some lexical (or dynamic) scoping construct for which the action of Return is defined - and then the presence of Return will lead to breaking-out-of-the-scoping-construct procedure, or it is not and then it is just a symbolic expression like any other. After breaking out of the scoping costruct (or just evaluation if it was not inside any scoping construct), Return gets discarded only if it was called from within the r.h.s. of a user-defined rule. Here is an example:

In[1]:= 
Clear[a,b,c]; 
c=(Return[a];3) 

Out[1]= Return[a] 

In[2]:= b:=(Return[a];3) 
In[3]:= b 
Out[3]= a 

This behavior can be explained by consulting the exact rules of the evaluation procedure. Lacking a more up-to-date account, I cite here David Withoff's "Mathematica internals" of 1992: The very last step of the evaluation loop is (Chapter 3 - evaluation, p. 7, on the bottom): "Discard the head Return, if present, for expressions generated through application of user-defined rules."

Thus, when you use SetDelayed, you create a user-defined delayed rule and then Return is discarded, while for "direct" evaluation like

In[4]:= Return[a] 
Out[4]= Return[a] 

it is not. But, in

In[5]:= 
ClearAll[a,c];
a:=Return[c];
a

Out[7]= c 

it is, and Return is discarded, even though there was no scoping construct to break out of. The same happens in your example where Module is wrapped around - Return breaks out of Module all right, but is not discarded since Module was not the r.h.s of any user-defined rule.

Here are the best descriptions of how Return works that I am aware of, due to Alan Hayes (can be found in this MathGroup thread) :

"In view of the recent thread on Holding Arguments in a Second Argument List the following notes on Return may be of interest:

• If Return[x] is generated as a value in Do or Scan then x is immediately returned;

• If Return[x] is generated as an entry in CompoundExpression or as a value of the body of a While or For loop then Return[x] (not x) is immediately returned;

• If Return[x] is generated as the value of a user-defined function then the function returns x (not Return[x])

• Otherwise Return[x] behaves as a ordinary expression. "

These "empirical" rules agree with the statement found in the Withoff's report, the latter making the former sound somewhat less magical.

It is also good to remember that Return has a second optional argument, which tells it from which surrounding scoping construct to break out:

In[242]:= (Module[{}, Return[0, CompoundExpression]]; 2)
Out[242]= 0

but

In[243]:= (Module[{}, (Return[0, CompoundExpression]; 0)]; 2)
Out[243]= 2

In your last example, the outer CompoundExpression defined in b in dynamically rather than lexically scoped (relative to the stuff defined in a), and therefore this won't work (in other words, your last result is also as expected).