Function Call and Scoping Algorithms

Here's a sketch of the FunCall and Function classes in a language similar to Epsilon:

class FunCall extends Expression {
Expression operator;
List<Expression> operands;

Value eval(Environment env) {
Function fun = operator.eval(env);
return fun.apply(operands, env);
}
}

class Function implements Value {
Environment defEnv;
List<Symbol> params;
Expression body;

Value apply(List<Expression> operands, Environment env) {
???
}
}

Substitution Algorithms

Applicative Order Substitution (eager)

In applicative order substitution parameters in the body are replaced by arguments:

Value apply(List<Expression> operands, Environment env) {
List<Value> args = new LinkedList<Value>();
for(Expression operand: operands) {
args.add(operand.eval(env));
}
for(int i = 0; i < params.size(); i++) {
body = substitute(body, params.get(i), args.get(i));
}
return body.eval(defEnv);
}

Normal Order Substitution (lazy)

In normal order substitution parameters in the body are replaced by operands:

Value apply(List<Expression> operands, Environment env) {
for(int i = 0; i < params.size(); i++) {
body = substitute(body, params.get(i), operands.get(i));
}
return body.eval(defEnv);
}

Environmental Algorithms

Pass-by-reference (eager)

In pass-by-reference parameters are bound to arguments in a temporary extension of the defining environment (or calling environment if dynamic scope rule is used):

Value apply(List<Expression> operands, Environment env) {
List<Value> args = new LinkedList<Value>();
for(Expression operand: operands) {
args.add(operand.eval(env));
}
Environment tempEnv = new Environment(defEnv);
for(int i = 0; i < params.size(); i++) {
tempEnv.put(params.get(i), args.get(i));
}
return body.eval(tempEnv);
}

Pass-by-value (eager)

Pass-by-value is similar to pass-by-reference except parameters are bound to argument clones in a temporary extension of the defining environment:

Value apply(List<Expression> operands, Environment env) {
List<Value> args = new LinkedList<Value>();
for(Expression operand: operands) {
Value val = operand.eval(env);
args.add(val.clone());
}
Environment tempEnv = new Environment(defEnv);
for(int i = 0; i < params.size(); i++) {
tempEnv.put(params.get(i), args.get(i));
}
return body.eval(tempEnv);
}

Pass-by-text (lazy)

In pass-by-text parameters are bound to operands in a temporary extension of the environment:

Value apply(List<Expression> operands, Environment env) {
Environment tempEnv = new Environment(defEnv);
for(int i = 0; i < params.size(); i++) {
tempEnv.put(params.get(i), operands.get(i));
}
return body.eval(tempEnv);
}

This assumes:

class Phrase implements Value { ... }

and:

class Symbol extends Expression {
Value eval(Environment env) {
Value val = env.get(this);
if (val instanceof Phrase) {
val = ((Phrase)val).eval(env);
}
return val;
}
}

Pass-by-name (lazy)

Pass-by-name is similar to pass-by-text except operands are first converted into parameterless functions called thunks:

Value apply(List<Expression> operands, Environment env) {
List<Function> thunks = new LinkedList<Function>();
for(Expression operand: operands) {
thunks.add(new Function(null, operand));
}
Environment tempEnv = new Environment(defEnv);
for(int i = 0; i < params.size(); i++) {
tempEnv.put(params.get(i), thunks.get(i));
}
return body.eval(tempEnv);
}

This assumes:

class Symbol extends Expression {
Value eval(Environment env) {
Value val = env.get(this);
if (val instanceof Function) {
val = ((Function)val).apply(null, env);
}
return val;
}
}

Examples

Pass-by-reference versus Pass-by-value

-> [define w (var 10)]
done
-> [define clear (proc (x) { {assign x 0})]
done
-> {clear w}
ok

In pass-by-reference w is cleared:

-> w
var<0>

In pass-by-value w is unaffected, w's clone was cleared:

-> w
var<10>

Pass-by-text versus Pass-by-name

Assume a is a global constant and a local constant inside inc:

-> [define a 10]
done
-> [define inc (fun (x) (let [[define a 20]] (+ a x)))]
done

Consider the call:

-> (inc (+ a 2))

In pass-by-text the parameter x is bound to the operand (+ a 2). Unfortunately, when we evaluate the body (+ a x) in the temporary environment (+ a 2) is interpreted as (+ 20 2). Thus we get the unpredictable result:

-> (inc (+ a 2))
42

In pass-by-name the parameter x is bound to the thunk (fun () (+ a 2)). When we evaluate the body (+ a x) in the temporary environment, we must call the thunk. However, due to the static scope rule the defining environment of the thunk is consulted when determining the value of the non-local a. This produces (+ 10 2). Thus:

-> (inc (+ a 2))
32

Lazy versus Eager

The following function has a parameter it doesn't use:

-> [define always0 (fun (x) 0)]
done

Consider the call:

-> (always0 (/ 1 0))

Eager algorithms eagerly evaluate the operand (/ 1 0), even though always0 doesn't need it. Thus:

-> (always0 (/ 1 0))
Error: can't divide by 0

In lazy algorithms operands that are not needed are ignored. Thus:

-> (always0 (/ 1 0))
0

Static versus Dynamic Scope

Epsilon employs the static scope rule. This means that the values of non-locals (i.e., symbols appearing in the body that are neither parameters nor symbols defined in a nested block) are determined by the function's defining environment, not its calling environment. Consider the following example:

-> [define a 100]
done
-> [deine addA
(let [[define a 50] [define b 30]] (fun (c) (+ a b c)))]
done
-> (let [[define b 500]] (addA 20))
100

The body of the addA function contains four symbols: +, a, b, and c. In the environment in which addA is defined a = 50, b = 30, + = the primitive add function, and c is a parameter. However, in the environment in which addA is called a = 100 and b = 500. Nevertheless, the value returned is (+ 50 30 20) = 100.

Implementation

When a function is created, the environment in which is was created is stored in the defEnv field:

class ExpAbstraction extends SpecialForm {
List<Symbol> params;
Expression body;
Value eval(Environment env) {
return new Function (params, env, body);
}
}

For example, assume the following declarations have been made:

-> [define a 100]
done
-> [define foo (let [[define b 20]] (fun (c) (+ a b c)))]
done

If we represent an instance of the Function class as a box with three compartments for each of the three fields: parameters, body, and defining environment. Then we can draw an environment diagram to represent what the environment looks like at this point:

Notice that the environment created by the call to the expression block persists after the block is exited. This is because there is still an active chain of references pointing to it from the global environment.

Next, we call foo inside of an expression block:

-> (let [[define a 50] [define b 10]] (foo (+ a b)))
180

Here's an environment diagram at the moment we call foo:

Notice that when we evaluate the body of foo: (+ a b c) we will search the defining environment for the values of the non-locals b and c.

If the dynamic scope rule is used, we will search the calling environment. This produces a different result:

-> (let [[define a 50] [define b 10]] (foo (+ a b)))
120