package com.alangpierce.lambdacalculusplayground.expression;

import javax.annotation.Nullable;

public class Expressions {
    /**
     * Evaluate an expression for a single step.
     *
     * @return An expression, or null if this expression cannot be computed any further.
     */
    public static @Nullable Expression step(Expression e) {
        return e.visit(new Expression.ExpressionVisitor<Expression>() {
            @Override
            public @Nullable Expression visit(Lambda lambda) {
                Expression newBody = step(lambda.body);
                if (newBody == null) {
                    return null;
                }
                return new Lambda(lambda.varName, newBody);
            }
            @Override
            public @Nullable Expression visit(final FuncCall funcCall) {
                if (funcCall.func instanceof Lambda) {
                    Lambda func = (Lambda)funcCall.func;
                    return replaceVariable(func.body, func.varName, funcCall.arg);
                }
                @Nullable Expression steppedFunc = step(funcCall.func);
                if (steppedFunc != null) {
                    return new FuncCall(steppedFunc, funcCall.arg);
                }
                @Nullable Expression steppedArg = step(funcCall.arg);
                if (steppedArg != null) {
                    return new FuncCall(funcCall.func, steppedArg);
                }
                return null;
            }
            @Override
            public @Nullable Expression visit(Variable variable) {
                return null;
            }
        });
    }

    public static Expression replaceVariable(Expression e, final String varName,
                                             final Expression replacement) {
        return e.visit(new Expression.ExpressionVisitor<Expression>() {
            @Override
            public Expression visit(Lambda lambda) {
                // Lambda variable shadows outer variable name.
                if (lambda.varName.equals(varName)) {
                    return lambda;
                }
                return new Lambda(lambda.varName,
                        replaceVariable(lambda.body, varName, replacement));
            }
            @Override
            public Expression visit(FuncCall funcCall) {
                return new FuncCall(replaceVariable(funcCall.func, varName, replacement),
                        replaceVariable(funcCall.arg, varName, replacement));
            }
            @Override
            public Expression visit(Variable variable) {
                if (variable.varName.equals(varName)) {
                    return replacement;
                } else {
                    return variable;
                }
            }
        });
    }
}

@@ -55,16 +55,106 @@
 ssion;%0A%0A
+import com.alangpierce.lambdacalculusplayground.expression.Expression.ExpressionVisitor;%0A%0A
 import j
@@ -2174,32 +2174,33 @@
               %7D%0A
+%0A
                 
@@ -2203,648 +2203,2091 @@
     
-return new Lambda(lambda.varName,%0A                        replaceVariable(lambda.body, varName, replacement));%0A            %7D%0A            @Override%0A            public Expression visit(FuncCall funcCall) %7B%0A                return new FuncCall(replaceVariable(funcCall.func, varName, replacement),%0A                        replaceVariable(funcCall.arg, varName, replacement));%0A            %7D%0A            @Override%0A            public Expression visit(Variable variable) %7B%0A                if (variable.varName.equals(varName)) %7B%0A                    return replacement;%0A                %7D else %7B%0A                    return variable;%0A                %7D
+/*%0A                 * If the lambda parameter exists in the replacement expression, we'll introduce a%0A                 * name clash. To solve this, bump our variable name to be different by adding a%0A                 * prime to the end, and do that replacement in the whole expression.%0A                 */%0A                String newVarName = lambda.varName;%0A                while (containsVariableUsage(replacement, newVarName)) %7B%0A                    newVarName += %22'%22;%0A                %7D%0A                Expression newBody = lambda.body;%0A                if (!newVarName.equals(lambda.varName)) %7B%0A                    newBody = replaceVariable(newBody, lambda.varName, new Variable(newVarName));%0A                %7D%0A                return new Lambda(newVarName, replaceVariable(newBody, varName, replacement));%0A            %7D%0A            @Override%0A            public Expression visit(FuncCall funcCall) %7B%0A                return new FuncCall(replaceVariable(funcCall.func, varName, replacement),%0A                        replaceVariable(funcCall.arg, varName, replacement));%0A            %7D%0A            @Override%0A            public Expression visit(Variable variable) %7B%0A                if (variable.varName.equals(varName)) %7B%0A                    return replacement;%0A                %7D else %7B%0A                    return variable;%0A                %7D%0A            %7D%0A        %7D);%0A    %7D%0A%0A    public static boolean containsVariableUsage(Expression e, String varName) %7B%0A        return e.visit(new ExpressionVisitor%3CBoolean%3E() %7B%0A            @Override%0A            public Boolean visit(Lambda lambda) %7B%0A                return lambda.varName.equals(varName) %7C%7C%0A                        containsVariableUsage(lambda.body, varName);%0A            %7D%0A            @Override%0A            public Boolean visit(FuncCall funcCall) %7B%0A                return containsVariableUsage(funcCall.func, varName) %7C%7C%0A                        containsVariableUsage(funcCall.arg, varName);%0A            %7D%0A            @Override%0A            public Boolean visit(Variable variable) %7B%0A                return variable.varName.equals(varName);
 %0A   

Fix evaluation bug caused by name conflicts